3 #include "setset_private.h"
4 #include "xbt/sysdep.h"
7 * \brief Create a new setset data structure
8 * \param size The initial size of the setset (in number of elements)
9 * \return The created setset
11 xbt_setset_t xbt_setset_new(unsigned int size)
13 xbt_setset_elm_entry_t first_elm = NULL;
14 xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1);
15 setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL);
16 setset->sets = xbt_fifo_new();
17 /* Expand the elements dynar to the size indicated by the user, */
18 /* then create the first element, get a pointer to it and add it to the */
19 /* free elements list */
20 xbt_dynar_shrink(setset->elm_array, size);
21 first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
22 first_elm->free.next = 0;
27 * \brief Destroy a setset and free all it's resources
28 * \param The setset to destroy
30 void xbt_setset_destroy(xbt_setset_t setset)
34 xbt_dynar_free(&setset->elm_array);
35 xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t){
36 xbt_setset_destroy_set(set);
38 xbt_fifo_free(setset->sets);
42 /* Add an element to the setset, this will assign to it an index */
43 xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj)
45 xbt_setset_elm_entry_t new_entry = NULL;
46 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
47 xbt_assert0(e->ID == 0, "Adding element with non NULL ID");
48 xbt_setset_elm_entry_t first_elm =
49 (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0);
51 /* Before create a new elm entry check if there is one in the free elm list. */
52 /* If there is not free elm entries, then create a new one */
53 if(first_elm->free.next != 0){
54 e->ID = first_elm->free.next;
55 new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next);
56 first_elm->free.next = new_entry->free.next;
58 new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
59 e->ID = xbt_dynar_length(setset->elm_array) - 1;
61 /* Initialize the new element data structure and add it to the hash */
62 new_entry->info.refcount = 0;
63 new_entry->info.obj = e;
67 /* Remove from the setset the object stored at idx */
68 void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx)
70 xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
71 xbt_setset_elm_entry_t first_free = NULL;
73 /* Decrease the refcount and proceed only if it is 0 */
74 if(--e_entry->info.refcount > 0)
78 /* FIXME: do not assume that the object still exists, it might be deallocated */
79 /*e_entry->info.obj->ID = 0;*/
81 /* Link the elm entry to the list of free ones */
82 first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
83 e_entry->free.next = first_free->free.next;
84 first_free->free.next = idx;
87 /* Get the object associated to a given index */
88 /* WARNING: it must be a valid index! */
89 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
91 xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
92 return e_entry->info.obj;
95 /* Increase the refcount of an element */
96 void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx)
98 xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
99 e_entry->info.refcount++;
103 * \brief Add a new set to the setset
104 * \param setset The setset that will contain the created set
105 * \returns The created set
107 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
109 xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
110 newset->setset = setset;
111 newset->elmcount = 0;
112 newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1;
113 newset->bitmap = xbt_new0(unsigned int, newset->size);
114 xbt_fifo_unshift(setset->sets, newset);
119 * \brief Destroy a set in the setset
120 * \param set The set to destroy
122 void xbt_setset_destroy_set(xbt_setset_set_t set)
124 xbt_setset_set_reset(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 if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
153 _xbt_setset_elm_use(set->setset, e->ID);
154 _set_bit(e->ID, set->bitmap);
161 * \brief Remove an element from a set
162 * \param set The set from which the element is going to be removed
163 * \param obj The element to remove
165 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
167 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
169 /* If the index of the object is between the bitmap then unset it, otherwise
170 do not do anything, because we already know it is not in the set */
171 if(set->size * BITS_INT >= e->ID){
172 if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
174 _unset_bit(e->ID, set->bitmap);
175 _xbt_setset_elm_remove(set->setset, e->ID);
183 * \brief Remove all the elements of a set
184 * \param set The set to empty
186 void xbt_setset_set_reset(xbt_setset_set_t set)
189 /* Traverse the set and remove every element */
190 for(i=0; i < set->size; i++){
191 if(set->bitmap[i] != 0){
192 for(k=0; k < BITS_INT; k++){
193 if(_is_bit_set(k,set->bitmap[i])){
194 _xbt_setset_elm_remove(set->setset, i * BITS_INT + k);
203 * \brief Choose one element of a set (but do not remove it)
205 * \return An element that belongs to set \a set
207 void *xbt_setset_set_choose(xbt_setset_set_t set)
210 /* Traverse the set and return the first element */
211 for(i=0; i < set->size; i++){
212 if(set->bitmap[i] != 0){
213 for(k=0; k < BITS_INT; k++){
214 if(_is_bit_set(k,set->bitmap[i])){
215 return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k);
224 * \brief Extract one element of a set (it removes it)
226 * \return An element that belonged to set \a set
228 void *xbt_setset_set_extract(xbt_setset_set_t set)
230 void *obj = xbt_setset_set_choose(set);
232 xbt_setset_set_remove(set, obj);
239 * \brief Test if an element belongs to a set
241 * \param obj The element
242 * \return TRUE if the element \a obj belongs to set \a set
244 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
246 xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
247 if(e->ID != 0 && e->ID <= set->size * BITS_INT){
248 return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
253 int xbt_setset_set_size(xbt_setset_set_t set)
255 return set->elmcount;
260 * \brief Add two sets
261 * Add two sets storing the result in the first one
262 * \param set1 The first set
263 * \param set2 The second set
265 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
267 if(set1->size < set2->size){
268 xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
269 set1->size = set2->size;
273 /* Traverse the second set and add every element that is not member of the
275 for(i=0; i < set2->size; i++){
276 if(set2->bitmap[i] != 0){
277 for(k=0; k < BITS_INT; k++){
278 if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){
280 _xbt_setset_elm_use(set1->setset, i * BITS_INT + k);
281 _set_bit(i * BITS_INT + k, set1->bitmap);
290 * \brief Substract two sets
291 * Substract two sets storing the result in the first one
292 * \param set1 The first set
293 * \param set2 The second set
295 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
298 /* Traverse the second set and remove every element that is member of it to
300 for(i=0; i < min(set1->size,set2->size); i++){
301 if(set2->bitmap[i] != 0){
302 for(k=0; k < BITS_INT; k++){
303 if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){
305 _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
306 _unset_bit(i * BITS_INT + k, set1->bitmap);
315 * \brief Intersect two sets
316 * Intersect two sets storing the result in the first one
317 * \param set1 The first set
318 * \param set2 The second set
320 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
323 /* Traverse the first set and remove every element that is not member of the second set */
324 for(i=0; i < set1->size; i++){
325 if(set1->bitmap[i] != 0){
326 for(k=0; k < BITS_INT; k++){
327 if(_is_bit_set(k, set1->bitmap[i]) &&
328 (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){
330 _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
331 _unset_bit(i * BITS_INT + k, set1->bitmap);
339 /* Get the cursor to point to the first element of a set */
340 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
342 (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
343 (*cursor)->set = set;
345 /* Traverse the set and point the cursor to the first element */
346 for(i=0; i < set->size; i++){
347 if(set->bitmap[i] != 0){
348 for(k=0; k < BITS_INT; k++){
349 if(_is_bit_set(k,set->bitmap[i])){
350 (*cursor)->idx = i * BITS_INT + k;
358 /* Get the data pointed by a cursor */
359 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
361 if(cursor->idx == 0){
366 *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
371 /* Advance a cursor to the next element */
372 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
376 /* Traverse the set and point the cursor to the first element */
377 for(i = cursor->idx / BITS_INT; i < cursor->set->size; i++){
378 if(cursor->set->bitmap[i] != 0){
379 for(k = cursor->idx % BITS_INT; k < BITS_INT; k++){
380 if(_is_bit_set(k,cursor->set->bitmap[i])){
381 cursor->idx = i * BITS_INT + k;
390 /* Check if the nth bit of an integer is set or not*/
391 unsigned int _is_bit_set(unsigned int bit, unsigned int integer)
393 return (0x1 << bit) & integer ? TRUE : FALSE;
396 /* Set the nth bit of an array of integers */
397 void _set_bit(unsigned int bit, unsigned int *bitmap)
399 bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
402 /* Unset the nth bit of an array of integers */
403 void _unset_bit(unsigned int bit, unsigned int *bitmap)
405 bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));