Logo AND Algorithmique Numérique Distribuée

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