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