Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
a5837136208458b285f268e2a80807e1f3766fdc
[simgrid.git] / src / xbt / setset.c
1 #include <stddef.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include "setset_private.h"
5 #include "xbt/sysdep.h"
6
7 /**
8  *  \brief Create a new setset data structure
9  *  \param size The initial size of the setset (in number of elements)
10  *  \return The created setset
11  */
12 xbt_setset_t xbt_setset_new(unsigned int size)
13 {
14   xbt_setset_elm_entry_t first_elm = NULL;
15   xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1);
16   setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL);
17   setset->sets = xbt_fifo_new();
18   /* Expand the elements dynar to the size indicated by the user, */
19   /* then create the first element, get a pointer to it and add it to the */
20   /* free elements list */
21   xbt_dynar_shrink(setset->elm_array, size);  
22   first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
23   first_elm->free.next = 0;
24   return setset;
25 }
26
27 /**
28  *  \brief Destroy a setset and free all it's resources
29  *  \param The setset to destroy
30  */
31 void xbt_setset_destroy(xbt_setset_t setset)
32 {
33   xbt_fifo_item_t item;
34   xbt_setset_set_t set;
35   xbt_dynar_free(&setset->elm_array);
36   xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t){
37     xbt_setset_destroy_set(set);
38   }
39   xbt_fifo_free(setset->sets);
40   xbt_free(setset);
41 }
42
43 /* Add an object to the setset, this will calculate its ID */
44 void xbt_setset_elm_add(xbt_setset_t setset, void *obj)
45 {
46   xbt_setset_elm_entry_t new_entry = NULL;
47   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
48   xbt_assert0(e->ID == 0, "Adding element with non NULL ID");
49   xbt_setset_elm_entry_t first_elm = 
50     (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0);
51   
52   /* Before create a new elm entry check if there is one in the free elm list. */
53   /* If there is not free elm entries, then create a new one  */
54   if(first_elm->free.next != 0){
55     e->ID = first_elm->free.next;
56     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next);
57     first_elm->free.next = new_entry->free.next;
58   }else{
59     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
60     e->ID = xbt_dynar_length(setset->elm_array) - 1;    
61   }
62
63   new_entry->info.obj = e;
64   return;
65 }
66
67 /* Remove an object from the setset */
68 void xbt_setset_elm_remove(xbt_setset_t setset, void *obj)
69 {
70   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
71   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, e->ID);
72   xbt_setset_elm_entry_t first_free = NULL;
73
74   /* Link the elm entry to the list of free ones */
75   first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
76   e_entry->free.next = first_free->free.next;
77   first_free->free.next = e->ID;
78 }
79
80 /* Get the object associated to a given index */
81 /* WARNING: it must be a valid index! */
82 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
83 {
84   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
85   return e_entry->info.obj;
86 }
87
88 /**
89  *  \brief Add a new set to the setset
90  *  \param setset The setset that will contain the created set
91  *  \returns The created set
92  */
93 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
94 {
95   xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
96   newset->setset = setset;
97   newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1;
98   newset->bitmap = xbt_new0(unsigned int, newset->size);
99   xbt_fifo_unshift(setset->sets, newset);
100   return newset;
101 }
102
103 /**
104  *  \brief Destroy a set in the setset
105  *  \param set The set to destroy
106  */
107 void xbt_setset_destroy_set(xbt_setset_set_t set)
108 {
109   xbt_free(set->bitmap);
110   xbt_fifo_remove(set->setset->sets, set);
111   xbt_free(set);
112   
113   return;
114 }
115
116 /**
117  *  \brief Insert an element into a set
118  *  \param set The set where the element is going to be added
119  *  \param obj The element to add
120  */
121 void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
122 {
123   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
124
125   if(e->ID == 0)
126     xbt_setset_elm_add(set->setset, e);
127   
128   /* Check if we need to expand the bitmap */
129   if(set->size * BITS_INT - 1 < e->ID){
130     set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int));
131     memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
132     set->size = (e->ID / BITS_INT + 1);
133   }
134
135   _set_bit(e->ID, set->bitmap);
136   
137   return;
138 }
139
140 /**
141  *  \brief Remove an element from a set
142  *  \param set The set from which the element is going to be removed
143  *  \param obj The element to remove
144  */
145 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
146 {
147   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
148   /* If the index of the object is between the bitmap then unset it, otherwise
149      do not do anything, because we already know it is not in the set */
150   if(e->ID != 0 && e->ID <= set->size * BITS_INT)
151     _unset_bit(e->ID, set->bitmap);
152
153   return;
154 }
155
156 /**
157  *  \brief Remove all the elements of a set
158  *  \param set The set to empty
159  */
160 void xbt_setset_set_reset(xbt_setset_set_t set)
161 {
162   memset(set->bitmap, 0, set->size * sizeof(int));
163 }
164
165 /**
166  *  \brief Choose one element of a set (but do not remove it)
167  *  \param set The set
168  *  \return An element that belongs to set \a set
169  */
170 void *xbt_setset_set_choose(xbt_setset_set_t set)
171 {
172   int i;
173   /* Traverse the set and return the first element */
174   for(i = 0; i < set->size; i++)
175     if(set->bitmap[i] != 0)
176       return _xbt_setset_idx_to_obj(set->setset, 
177                                     i * BITS_INT + ffs(set->bitmap[i]) - 1);
178   return NULL;
179 }
180
181 /**
182  *  \brief Extract one element of a set (it removes it)
183  *  \param set The set
184  *  \return An element that belonged to set \a set
185  */
186 void *xbt_setset_set_extract(xbt_setset_set_t set)
187 {
188   void *obj = xbt_setset_set_choose(set);
189   if(obj){
190     xbt_setset_set_remove(set, obj);
191   }
192   return obj;
193 }
194
195
196 /**
197  *  \brief Test if an element belongs to a set
198  *  \param set The set
199  *  \param obj The element
200  *  \return TRUE if the element \a obj belongs to set \a set
201  */
202 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
203 {
204   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
205   if(e->ID != 0 && e->ID <= set->size * BITS_INT){  
206     return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
207   }
208   return FALSE;
209 }
210
211 int xbt_setset_set_size(xbt_setset_set_t set)
212 {
213   int i, count = 0;
214   
215   for(i=0; i < set->size; i++)
216     count += bitcount(set->bitmap[i]);
217     
218   return count;
219 }
220
221
222 /**
223  *  \brief Add two sets
224  *         Add two sets storing the result in the first one
225  *  \param set1 The first set
226  *  \param set2 The second set
227  */
228 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
229 {
230   int i;
231
232   /* Increase the size of set1 if necessary */
233   if(set1->size < set2->size){
234     xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
235     set1->size = set2->size;
236   }
237
238   for(i=0; i < set1->size; i++)
239     if(set2->bitmap[i] != 0)
240       set1->bitmap[i] |= set2->bitmap[i];
241
242   return;
243 }
244
245 /**
246  *  \brief Substract two sets
247  *         Substract two sets storing the result in the first one
248  *  \param set1 The first set
249  *  \param set2 The second set
250  */
251 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
252 {
253   int i;
254
255   for(i=0; i < MIN(set1->size, set2->size); i++)
256     if(set2->bitmap[i] != 0)
257       set1->bitmap[i] ^= set2->bitmap[i];
258
259   return;
260 }
261
262 /**
263  *  \brief Intersect two sets
264  *         Intersect two sets storing the result in the first one
265  *  \param set1 The first set
266  *  \param set2 The second set
267  */
268 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
269 {
270   int i;
271
272   for(i=0; i < MIN(set1->size, set2->size); i++)
273     if(set1->bitmap[i] && set2->bitmap[i])
274       set1->bitmap[i] &= set2->bitmap[i];
275
276   return;
277 }
278
279 /* Get a cursor pointing to the first element of the set */
280 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
281 {
282   int i;
283   (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
284   (*cursor)->set = set;
285  
286   for(i = 0; i < set->size; i++){
287     if(set->bitmap[i] != 0){
288       (*cursor)->idx = i * BITS_INT + ffs(set->bitmap[i]) - 1;
289       break; 
290     }
291   }
292 }
293
294 /* Get the data pointed by a cursor */
295 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
296 {
297   if(cursor->idx == 0){
298     xbt_free(cursor);
299     *data = NULL;
300     return FALSE;
301   }else{
302     *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
303     return TRUE;
304   }
305 }
306
307 /* Advance a cursor to the next element */
308 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
309 {
310   unsigned int mask;
311   unsigned int data;
312   cursor->idx++;
313   while(cursor->idx < cursor->set->size * BITS_INT){
314     if((data = cursor->set->bitmap[cursor->idx / BITS_INT])){
315       mask = 1 << cursor->idx % BITS_INT;
316       while(mask){    /* FIXME: mask will never be 0! */
317         if(data & mask){
318           return;
319         }else{
320           cursor->idx++;
321           mask <<= 1;
322         }
323       }
324     }else{
325       cursor->idx += BITS_INT;
326     }
327   }
328   cursor->idx = 0; 
329 }
330
331 /* Check if the nth bit of an integer is set or not*/
332 unsigned int _is_bit_set(unsigned int bit, unsigned int integer)
333 {
334   return (0x1 << bit) & integer ? TRUE : FALSE;
335 }
336
337 /* Set the nth bit of an array of integers */
338 void _set_bit(unsigned int bit, unsigned int *bitmap)
339 {
340   bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
341 }
342
343 /* Unset the nth bit of an array of integers */
344 void _unset_bit(unsigned int bit, unsigned int *bitmap)
345 {
346   bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
347 }
348
349 /**
350  * Bitcount function 
351  * taken from http://graphics.stanford.edu/~seander/bithacks.html 
352  * Note: it assumes 4 byte integers
353  */
354 int bitcount(int v)
355 {
356   v = v - ((v >> 1) & 0x55555555);                        // reuse input as temporary
357   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);         // temp
358   return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;  // count
359 }