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 }