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