Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
More windows compatibility for context.
[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 #include "simgrid_config.h" /*_XBT_WIN32*/
7
8 /*The function ffs doesn't exist for windows*/
9 #ifdef _XBT_WIN32
10         int ffs(int bits)
11     {
12                 int i;
13                 if (bits == 0)
14                         return (0);
15                 for (i = 1; ; i++, bits >>= 1)
16                 {
17                         if (bits & 1) break;
18                 }
19                 return (i);
20         }
21 #endif
22
23 /**
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
27  */
28 xbt_setset_t xbt_setset_new(unsigned int size)
29 {
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;
40   return setset;
41 }
42
43 /**
44  *  \brief Destroy a setset and free all it's resources
45  *  \param The setset to destroy
46  */
47 void xbt_setset_destroy(xbt_setset_t setset)
48 {
49   xbt_fifo_item_t item;
50   xbt_setset_set_t set;
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);
54   }
55   xbt_fifo_free(setset->sets);
56   xbt_free(setset);
57 }
58
59 /* Add an object to the setset, this will calculate its ID */
60 void xbt_setset_elm_add(xbt_setset_t setset, void *obj)
61 {
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);
67   
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;
74   }else{
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;    
77   }
78
79   new_entry->info.obj = e;
80   return;
81 }
82
83 /* Remove an object from the setset */
84 void xbt_setset_elm_remove(xbt_setset_t setset, void *obj)
85 {
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;
89
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;
94 }
95
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)
99 {
100   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
101   return e_entry->info.obj;
102 }
103
104 /**
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
108  */
109 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
110 {
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);
116   return newset;
117 }
118
119 /**
120  *  \brief Destroy a set in the setset
121  *  \param set The set to destroy
122  */
123 void xbt_setset_destroy_set(xbt_setset_set_t set)
124 {
125   xbt_free(set->bitmap);
126   xbt_fifo_remove(set->setset->sets, set);
127   xbt_free(set);
128   
129   return;
130 }
131
132 /**
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
136  */
137 void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
138 {
139   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
140
141   if(e->ID == 0)
142     xbt_setset_elm_add(set->setset, e);
143   
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);
149   }
150
151   _set_bit(e->ID, set->bitmap);
152   
153   return;
154 }
155
156 /**
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
160  */
161 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
162 {
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);
168
169   return;
170 }
171
172 /**
173  *  \brief Remove all the elements of a set
174  *  \param set The set to empty
175  */
176 void xbt_setset_set_reset(xbt_setset_set_t set)
177 {
178   memset(set->bitmap, 0, set->size * sizeof(int));
179 }
180
181 /**
182  *  \brief Choose one element of a set (but do not remove it)
183  *  \param set The set
184  *  \return An element that belongs to set \a set
185  */
186 void *xbt_setset_set_choose(xbt_setset_set_t set)
187 {
188   int i;
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);
194   return NULL;
195 }
196
197 /**
198  *  \brief Extract one element of a set (it removes it)
199  *  \param set The set
200  *  \return An element that belonged to set \a set
201  */
202 void *xbt_setset_set_extract(xbt_setset_set_t set)
203 {
204   void *obj = xbt_setset_set_choose(set);
205   if(obj){
206     xbt_setset_set_remove(set, obj);
207   }
208   return obj;
209 }
210
211
212 /**
213  *  \brief Test if an element belongs to a set
214  *  \param set The set
215  *  \param obj The element
216  *  \return TRUE if the element \a obj belongs to set \a set
217  */
218 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
219 {
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]);
223   }
224   return FALSE;
225 }
226
227 int xbt_setset_set_size(xbt_setset_set_t set)
228 {
229   int i, count = 0;
230   
231   for(i=0; i < set->size; i++)
232     count += bitcount(set->bitmap[i]);
233     
234   return count;
235 }
236
237
238 /**
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
243  */
244 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
245 {
246   int i;
247
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;
252   }
253
254   for(i=0; i < set1->size; i++)
255     if(set2->bitmap[i] != 0)
256       set1->bitmap[i] |= set2->bitmap[i];
257
258   return;
259 }
260
261 /**
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
266  */
267 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
268 {
269   int i;
270
271   for(i=0; i < MIN(set1->size, set2->size); i++)
272     if(set2->bitmap[i] != 0)
273       set1->bitmap[i] ^= set2->bitmap[i];
274
275   return;
276 }
277
278 /**
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
283  */
284 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
285 {
286   int i;
287
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];
291
292   return;
293 }
294
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)
297 {
298   int i;
299   (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
300   (*cursor)->set = set;
301  
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;
305       break; 
306     }
307   }
308 }
309
310 /* Get the data pointed by a cursor */
311 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
312 {
313   if(cursor->idx == 0){
314     xbt_free(cursor);
315     *data = NULL;
316     return FALSE;
317   }else{
318     *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
319     return TRUE;
320   }
321 }
322
323 /* Advance a cursor to the next element */
324 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
325 {
326   unsigned int mask;
327   unsigned int data;
328   cursor->idx++;
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! */
333         if(data & mask){
334           return;
335         }else{
336           cursor->idx++;
337           mask <<= 1;
338         }
339       }
340     }else{
341       cursor->idx += BITS_INT;
342     }
343   }
344   cursor->idx = 0; 
345 }
346
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)
349 {
350   return (0x1 << bit) & integer ? TRUE : FALSE;
351 }
352
353 /* Set the nth bit of an array of integers */
354 void _set_bit(unsigned int bit, unsigned int *bitmap)
355 {
356   bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
357 }
358
359 /* Unset the nth bit of an array of integers */
360 void _unset_bit(unsigned int bit, unsigned int *bitmap)
361 {
362   bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
363 }
364
365 /**
366  * Bitcount function 
367  * taken from http://graphics.stanford.edu/~seander/bithacks.html 
368  * Note: it assumes 4 byte integers
369  */
370 int bitcount(int v)
371 {
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
375 }