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