Logo AND Algorithmique Numérique Distribuée

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