X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/b582c36a70a50b376da63ceacf2354d1a47c5ac7..a846b9415542cdaa8ba5d0f7efeadecb56ba7c2c:/src/xbt/setset.c diff --git a/src/xbt/setset.c b/src/xbt/setset.c index cbdb2b8f21..79d25575e9 100644 --- a/src/xbt/setset.c +++ b/src/xbt/setset.c @@ -1,7 +1,24 @@ #include #include +#include #include "setset_private.h" #include "xbt/sysdep.h" +#include "gras_config.h" /*_XBT_WIN32*/ + +/*The function ffs doesn't exist for windows*/ +#ifdef _XBT_WIN32 +int ffs(int bits) +{ + int i; + if (bits == 0) + return (0); + for (i = 1;; i++, bits >>= 1) { + if (bits & 1) + break; + } + return (i); +} +#endif /** * \brief Create a new setset data structure @@ -12,13 +29,15 @@ xbt_setset_t xbt_setset_new(unsigned int size) { xbt_setset_elm_entry_t first_elm = NULL; xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1); - setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL); + setset->elm_array = + xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL); setset->sets = xbt_fifo_new(); /* Expand the elements dynar to the size indicated by the user, */ /* then create the first element, get a pointer to it and add it to the */ /* free elements list */ - xbt_dynar_shrink(setset->elm_array, size); - first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array); + xbt_dynar_shrink(setset->elm_array, size); + first_elm = + (xbt_setset_elm_entry_t) xbt_dynar_push_ptr(setset->elm_array); first_elm->free.next = 0; return setset; } @@ -29,71 +48,67 @@ xbt_setset_t xbt_setset_new(unsigned int size) */ void xbt_setset_destroy(xbt_setset_t setset) { + xbt_fifo_item_t item; + xbt_setset_set_t set; xbt_dynar_free(&setset->elm_array); + xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t) { + xbt_setset_destroy_set(set); + } xbt_fifo_free(setset->sets); xbt_free(setset); - /* FIXME: check if we should trash the stored objects */ } -/* Add an element to the setset, this will assign to it an index */ -xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj) +/* Add an object to the setset, this will calculate its ID */ +void xbt_setset_elm_add(xbt_setset_t setset, void *obj) { xbt_setset_elm_entry_t new_entry = NULL; - xbt_setset_elm_t e = (xbt_setset_elm_t)obj; + xbt_setset_elm_entry_t first_elm = NULL; + xbt_setset_elm_t e = (xbt_setset_elm_t) obj; xbt_assert0(e->ID == 0, "Adding element with non NULL ID"); - xbt_setset_elm_entry_t first_elm = - (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0); - - /* Before create a new elm entry check if there is one in the free elm list.*/ + first_elm = + (xbt_setset_elm_entry_t) xbt_dynar_get_ptr(setset->elm_array, 0); + + /* Before create a new elm entry check if there is one in the free elm list. */ /* If there is not free elm entries, then create a new one */ - if(first_elm->free.next != 0){ + if (first_elm->free.next != 0) { e->ID = first_elm->free.next; - new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next); + new_entry = + (xbt_setset_elm_entry_t) xbt_dynar_get_ptr(setset->elm_array, + first_elm->free.next); first_elm->free.next = new_entry->free.next; - }else{ - new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array); - e->ID = xbt_dynar_length(setset->elm_array) - 1; + } else { + new_entry = + (xbt_setset_elm_entry_t) xbt_dynar_push_ptr(setset->elm_array); + e->ID = xbt_dynar_length(setset->elm_array) - 1; } - /* Initialize the new element data structure and add it to the hash */ - new_entry->info.refcount = 0; + new_entry->info.obj = e; - return new_entry; + return; } -/* Remove from the setset the object stored at idx */ -void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx) +/* Remove an object from the setset */ +void xbt_setset_elm_remove(xbt_setset_t setset, void *obj) { - xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx); + xbt_setset_elm_t e = (xbt_setset_elm_t) obj; + xbt_setset_elm_entry_t e_entry = + xbt_dynar_get_ptr(setset->elm_array, e->ID); xbt_setset_elm_entry_t first_free = NULL; - - /* Decrease the refcount and proceed only if it is 0 */ - if(--e_entry->info.refcount > 0) - return; - - /* Erase object ID */ - e_entry->info.obj->ID = 0; - + /* Link the elm entry to the list of free ones */ first_free = xbt_dynar_get_ptr(setset->elm_array, 0); e_entry->free.next = first_free->free.next; - first_free->free.next = idx; + first_free->free.next = e->ID; } /* Get the object associated to a given index */ /* WARNING: it must be a valid index! */ void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx) { - xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx); + xbt_setset_elm_entry_t e_entry = + xbt_dynar_get_ptr(setset->elm_array, idx); return e_entry->info.obj; } -/* Increase the refcount of an element */ -void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx) -{ - xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx); - e_entry->info.refcount++; -} - /** * \brief Add a new set to the setset * \param setset The setset that will contain the created set @@ -103,7 +118,6 @@ xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset) { xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1); newset->setset = setset; - newset->elmcount = 0; newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1; newset->bitmap = xbt_new0(unsigned int, newset->size); xbt_fifo_unshift(setset->sets, newset); @@ -116,11 +130,10 @@ xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset) */ void xbt_setset_destroy_set(xbt_setset_set_t set) { - xbt_setset_set_reset(set); xbt_free(set->bitmap); xbt_fifo_remove(set->setset->sets, set); xbt_free(set); - + return; } @@ -129,25 +142,23 @@ void xbt_setset_destroy_set(xbt_setset_set_t set) * \param set The set where the element is going to be added * \param obj The element to add */ -void xbt_setset_set_insert(xbt_setset_set_t set, void* obj) +void xbt_setset_set_insert(xbt_setset_set_t set, void *obj) { - xbt_setset_elm_t e = (xbt_setset_elm_t)obj; + xbt_setset_elm_t e = (xbt_setset_elm_t) obj; + + if (e->ID == 0) + xbt_setset_elm_add(set->setset, e); - if(e->ID == 0) - _xbt_setset_elm_add(set->setset, e); - /* Check if we need to expand the bitmap */ - if(set->size * BITS_INT - 1 < e->ID){ - set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int)); - memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int)); + if (set->size * BITS_INT - 1 < e->ID) { + set->bitmap = + xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int)); + memset(&set->bitmap[set->size], 0, + ((e->ID / BITS_INT + 1) - set->size) * sizeof(int)); set->size = (e->ID / BITS_INT + 1); } - - if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){ - set->elmcount++; - _xbt_setset_elm_use(set->setset, e->ID); - _set_bit(e->ID, set->bitmap); - } + + _set_bit(e->ID, set->bitmap); return; } @@ -157,20 +168,14 @@ void xbt_setset_set_insert(xbt_setset_set_t set, void* obj) * \param set The set from which the element is going to be removed * \param obj The element to remove */ -void xbt_setset_set_remove(xbt_setset_set_t set, void* obj) +void xbt_setset_set_remove(xbt_setset_set_t set, void *obj) { - xbt_setset_elm_t e = (xbt_setset_elm_t)obj; - if(e->ID != 0){ - /* If the index of the object is between the bitmap then unset it, otherwise - do not do anything, because we already know it is not in the set */ - if(set->size * BITS_INT >= e->ID){ - if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){ - set->elmcount--; - _unset_bit(e->ID, set->bitmap); - _xbt_setset_elm_remove(set->setset, e->ID); - } - } - } + xbt_setset_elm_t e = (xbt_setset_elm_t) obj; + /* If the index of the object is between the bitmap then unset it, otherwise + do not do anything, because we already know it is not in the set */ + if (e->ID != 0 && e->ID <= set->size * BITS_INT) + _unset_bit(e->ID, set->bitmap); + return; } @@ -180,18 +185,7 @@ void xbt_setset_set_remove(xbt_setset_set_t set, void* obj) */ void xbt_setset_set_reset(xbt_setset_set_t set) { - int i,k; - /* Traverse the set and remove every element */ - for(i=0; i < set->size; i++){ - if(set->bitmap[i] != 0){ - for(k=0; k < BITS_INT; k++){ - if(_is_bit_set(k,set->bitmap[i])){ - _xbt_setset_elm_remove(set->setset, i * BITS_INT + k); - } - } - } - } - set->elmcount = 0; + memset(set->bitmap, 0, set->size * sizeof(int)); } /** @@ -201,17 +195,13 @@ void xbt_setset_set_reset(xbt_setset_set_t set) */ void *xbt_setset_set_choose(xbt_setset_set_t set) { - int i,k; + int i; /* Traverse the set and return the first element */ - for(i=0; i < set->size; i++){ - if(set->bitmap[i] != 0){ - for(k=0; k < BITS_INT; k++){ - if(_is_bit_set(k,set->bitmap[i])){ - return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k); - } - } - } - } + for (i = 0; i < set->size; i++) + if (set->bitmap[i] != 0) + return _xbt_setset_idx_to_obj(set->setset, + i * BITS_INT + ffs(set->bitmap[i]) - + 1); return NULL; } @@ -223,7 +213,7 @@ void *xbt_setset_set_choose(xbt_setset_set_t set) void *xbt_setset_set_extract(xbt_setset_set_t set) { void *obj = xbt_setset_set_choose(set); - if(obj){ + if (obj) { xbt_setset_set_remove(set, obj); } return obj; @@ -236,10 +226,10 @@ void *xbt_setset_set_extract(xbt_setset_set_t set) * \param obj The element * \return TRUE if the element \a obj belongs to set \a set */ -int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj) +int xbt_setset_set_belongs(xbt_setset_set_t set, void *obj) { - xbt_setset_elm_t e = (xbt_setset_elm_t)obj; - if(e->ID != 0 && e->ID <= set->size * BITS_INT){ + xbt_setset_elm_t e = (xbt_setset_elm_t) obj; + if (e->ID != 0 && e->ID <= set->size * BITS_INT) { return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]); } return FALSE; @@ -247,7 +237,12 @@ int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj) int xbt_setset_set_size(xbt_setset_set_t set) { - return set->elmcount; + int i, count = 0; + + for (i = 0; i < set->size; i++) + count += bitcount(set->bitmap[i]); + + return count; } @@ -259,25 +254,18 @@ int xbt_setset_set_size(xbt_setset_set_t set) */ void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2) { - if(set1->size < set2->size){ + int i; + + /* Increase the size of set1 if necessary */ + if (set1->size < set2->size) { xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int)); set1->size = set2->size; } - int i,k; - /* Traverse the second set and add every element that is not member of the - first set to it */ - for(i=0; i < set2->size; i++){ - if(set2->bitmap[i] != 0){ - for(k=0; k < BITS_INT; k++){ - if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){ - set1->elmcount++; - _xbt_setset_elm_use(set1->setset, i * BITS_INT + k); - _set_bit(i * BITS_INT + k, set1->bitmap); - } - } - } - } + for (i = 0; i < set1->size; i++) + if (set2->bitmap[i] != 0) + set1->bitmap[i] |= set2->bitmap[i]; + return; } @@ -289,20 +277,12 @@ void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2) */ void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2) { - int i,k; - /* Traverse the second set and remove every element that is member of it to - the first set */ - for(i=0; i < min(set1->size,set2->size); i++){ - if(set2->bitmap[i] != 0){ - for(k=0; k < BITS_INT; k++){ - if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){ - set1->elmcount--; - _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k); - _unset_bit(i * BITS_INT + k, set1->bitmap); - } - } - } - } + int i; + + for (i = 0; i < MIN(set1->size, set2->size); i++) + if (set2->bitmap[i] != 0) + set1->bitmap[i] ^= set2->bitmap[i]; + return; } @@ -314,38 +294,27 @@ void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2) */ void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2) { - int i,k; - /* Traverse the first set and remove every element that is not member of the second set */ - for(i=0; i < set1->size; i++){ - if(set1->bitmap[i] != 0){ - for(k=0; k < BITS_INT; k++){ - if(_is_bit_set(k, set1->bitmap[i]) && - (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){ - set1->elmcount--; - _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k); - _unset_bit(i * BITS_INT + k, set1->bitmap); - } - } - } - } + int i; + + for (i = 0; i < MIN(set1->size, set2->size); i++) + if (set1->bitmap[i] && set2->bitmap[i]) + set1->bitmap[i] &= set2->bitmap[i]; + return; } -/* Get the cursor to point to the first element of a set */ -void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor) +/* Get a cursor pointing to the first element of the set */ +void xbt_setset_cursor_first(xbt_setset_set_t set, + xbt_setset_cursor_t * cursor) { + int i; (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1); (*cursor)->set = set; - int i,k; - /* Traverse the set and point the cursor to the first element */ - for(i=0; i < set->size; i++){ - if(set->bitmap[i] != 0){ - for(k=0; k < BITS_INT; k++){ - if(_is_bit_set(k,set->bitmap[i])){ - (*cursor)->idx = i * BITS_INT + k; - return; - } - } + + for (i = 0; i < set->size; i++) { + if (set->bitmap[i] != 0) { + (*cursor)->idx = i * BITS_INT + ffs(set->bitmap[i]) - 1; + break; } } } @@ -353,11 +322,11 @@ void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor) /* Get the data pointed by a cursor */ int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data) { - if(cursor->idx == 0){ + if (cursor->idx == 0) { xbt_free(cursor); *data = NULL; return FALSE; - }else{ + } else { *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx); return TRUE; } @@ -366,20 +335,25 @@ int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data) /* Advance a cursor to the next element */ void xbt_setset_cursor_next(xbt_setset_cursor_t cursor) { - int i,k; + unsigned int mask; + unsigned int data; cursor->idx++; - /* Traverse the set and point the cursor to the first element */ - for(i = cursor->idx / BITS_INT; i < cursor->set->size; i++){ - if(cursor->set->bitmap[i] != 0){ - for(k = cursor->idx % BITS_INT; k < BITS_INT; k++){ - if(_is_bit_set(k,cursor->set->bitmap[i])){ - cursor->idx = i * BITS_INT + k; - return; + while (cursor->idx < cursor->set->size * BITS_INT) { + if ((data = cursor->set->bitmap[cursor->idx / BITS_INT])) { + mask = 1 << cursor->idx % BITS_INT; + while (mask) { /* FIXME: mask will never be 0! */ + if (data & mask) { + return; + } else { + cursor->idx++; + mask <<= 1; } } + } else { + cursor->idx += BITS_INT; } } - cursor->idx = 0; + cursor->idx = 0; } /* Check if the nth bit of an integer is set or not*/ @@ -400,10 +374,14 @@ void _unset_bit(unsigned int bit, unsigned int *bitmap) bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT)); } - - - - - - - +/** + * Bitcount function + * taken from http://graphics.stanford.edu/~seander/bithacks.html + * Note: it assumes 4 byte integers + */ +int bitcount(int v) +{ + v = v - ((v >> 1) & 0x55555555); // reuse input as temporary + v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp + return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; // count +}