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_assert(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 }