4 #include "setset_private.h"
5 #include "xbt/sysdep.h"
6 #include "simgrid_config.h" /*_XBT_WIN32*/
8 /*The function ffs doesn't exist for windows*/
15 for (i = 1; ; i++, bits >>= 1)
24 * \brief Create a new setset data structure
25 * \param size The initial size of the setset (in number of elements)
26 * \return The created setset
28 xbt_setset_t xbt_setset_new(unsigned int size)
30 xbt_setset_elm_entry_t first_elm = NULL;
31 xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1);
32 setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL);
33 setset->sets = xbt_fifo_new();
34 /* Expand the elements dynar to the size indicated by the user, */
35 /* then create the first element, get a pointer to it and add it to the */
36 /* free elements list */
37 xbt_dynar_shrink(setset->elm_array, size);
38 first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
39 first_elm->free.next = 0;
44 * \brief Destroy a setset and free all it's resources
45 * \param The setset to destroy
47 void xbt_setset_destroy(xbt_setset_t setset)
51 xbt_dynar_free(&setset->elm_array);
52 xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t){
53 xbt_setset_destroy_set(set);
55 xbt_fifo_free(setset->sets);
59 /* Add an object to the setset, this will calculate its ID */
60 void xbt_setset_elm_add(xbt_setset_t setset, void *obj)
62 xbt_setset_elm_entry_t new_entry = NULL;
63 xbt_setset_elm_entry_t first_elm = NULL;
64 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
65 xbt_assert0(e->ID == 0, "Adding element with non NULL ID");
66 first_elm = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0);
68 /* Before create a new elm entry check if there is one in the free elm list. */
69 /* If there is not free elm entries, then create a new one */
70 if(first_elm->free.next != 0){
71 e->ID = first_elm->free.next;
72 new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next);
73 first_elm->free.next = new_entry->free.next;
75 new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
76 e->ID = xbt_dynar_length(setset->elm_array) - 1;
79 new_entry->info.obj = e;
83 /* Remove an object from the setset */
84 void xbt_setset_elm_remove(xbt_setset_t setset, void *obj)
86 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
87 xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, e->ID);
88 xbt_setset_elm_entry_t first_free = NULL;
90 /* Link the elm entry to the list of free ones */
91 first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
92 e_entry->free.next = first_free->free.next;
93 first_free->free.next = e->ID;
96 /* Get the object associated to a given index */
97 /* WARNING: it must be a valid index! */
98 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
100 xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
101 return e_entry->info.obj;
105 * \brief Add a new set to the setset
106 * \param setset The setset that will contain the created set
107 * \returns The created set
109 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
111 xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
112 newset->setset = setset;
113 newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1;
114 newset->bitmap = xbt_new0(unsigned int, newset->size);
115 xbt_fifo_unshift(setset->sets, newset);
120 * \brief Destroy a set in the setset
121 * \param set The set to destroy
123 void xbt_setset_destroy_set(xbt_setset_set_t set)
125 xbt_free(set->bitmap);
126 xbt_fifo_remove(set->setset->sets, set);
133 * \brief Insert an element into a set
134 * \param set The set where the element is going to be added
135 * \param obj The element to add
137 void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
139 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
142 xbt_setset_elm_add(set->setset, e);
144 /* Check if we need to expand the bitmap */
145 if(set->size * BITS_INT - 1 < e->ID){
146 set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int));
147 memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
148 set->size = (e->ID / BITS_INT + 1);
151 _set_bit(e->ID, set->bitmap);
157 * \brief Remove an element from a set
158 * \param set The set from which the element is going to be removed
159 * \param obj The element to remove
161 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
163 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
164 /* If the index of the object is between the bitmap then unset it, otherwise
165 do not do anything, because we already know it is not in the set */
166 if(e->ID != 0 && e->ID <= set->size * BITS_INT)
167 _unset_bit(e->ID, set->bitmap);
173 * \brief Remove all the elements of a set
174 * \param set The set to empty
176 void xbt_setset_set_reset(xbt_setset_set_t set)
178 memset(set->bitmap, 0, set->size * sizeof(int));
182 * \brief Choose one element of a set (but do not remove it)
184 * \return An element that belongs to set \a set
186 void *xbt_setset_set_choose(xbt_setset_set_t set)
189 /* Traverse the set and return the first element */
190 for(i = 0; i < set->size; i++)
191 if(set->bitmap[i] != 0)
192 return _xbt_setset_idx_to_obj(set->setset,
193 i * BITS_INT + ffs(set->bitmap[i]) - 1);
198 * \brief Extract one element of a set (it removes it)
200 * \return An element that belonged to set \a set
202 void *xbt_setset_set_extract(xbt_setset_set_t set)
204 void *obj = xbt_setset_set_choose(set);
206 xbt_setset_set_remove(set, obj);
213 * \brief Test if an element belongs to a set
215 * \param obj The element
216 * \return TRUE if the element \a obj belongs to set \a set
218 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
220 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
221 if(e->ID != 0 && e->ID <= set->size * BITS_INT){
222 return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
227 int xbt_setset_set_size(xbt_setset_set_t set)
231 for(i=0; i < set->size; i++)
232 count += bitcount(set->bitmap[i]);
239 * \brief Add two sets
240 * Add two sets storing the result in the first one
241 * \param set1 The first set
242 * \param set2 The second set
244 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
248 /* Increase the size of set1 if necessary */
249 if(set1->size < set2->size){
250 xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
251 set1->size = set2->size;
254 for(i=0; i < set1->size; i++)
255 if(set2->bitmap[i] != 0)
256 set1->bitmap[i] |= set2->bitmap[i];
262 * \brief Substract two sets
263 * Substract two sets storing the result in the first one
264 * \param set1 The first set
265 * \param set2 The second set
267 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
271 for(i=0; i < MIN(set1->size, set2->size); i++)
272 if(set2->bitmap[i] != 0)
273 set1->bitmap[i] ^= set2->bitmap[i];
279 * \brief Intersect two sets
280 * Intersect two sets storing the result in the first one
281 * \param set1 The first set
282 * \param set2 The second set
284 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
288 for(i=0; i < MIN(set1->size, set2->size); i++)
289 if(set1->bitmap[i] && set2->bitmap[i])
290 set1->bitmap[i] &= set2->bitmap[i];
295 /* Get a cursor pointing to the first element of the set */
296 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
299 (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
300 (*cursor)->set = set;
302 for(i = 0; i < set->size; i++){
303 if(set->bitmap[i] != 0){
304 (*cursor)->idx = i * BITS_INT + ffs(set->bitmap[i]) - 1;
310 /* Get the data pointed by a cursor */
311 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
313 if(cursor->idx == 0){
318 *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
323 /* Advance a cursor to the next element */
324 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
329 while(cursor->idx < cursor->set->size * BITS_INT){
330 if((data = cursor->set->bitmap[cursor->idx / BITS_INT])){
331 mask = 1 << cursor->idx % BITS_INT;
332 while(mask){ /* FIXME: mask will never be 0! */
341 cursor->idx += BITS_INT;
347 /* Check if the nth bit of an integer is set or not*/
348 unsigned int _is_bit_set(unsigned int bit, unsigned int integer)
350 return (0x1 << bit) & integer ? TRUE : FALSE;
353 /* Set the nth bit of an array of integers */
354 void _set_bit(unsigned int bit, unsigned int *bitmap)
356 bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
359 /* Unset the nth bit of an array of integers */
360 void _unset_bit(unsigned int bit, unsigned int *bitmap)
362 bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
367 * taken from http://graphics.stanford.edu/~seander/bithacks.html
368 * Note: it assumes 4 byte integers
372 v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
373 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
374 return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; // count