src/xbt/setset.c

   1 #include <stddef.h>
   2 #include <stdio.h>
   3 #include "setset_private.h"
   4 #include "xbt/sysdep.h"
   5
   6 /**
   7  *  \brief Create a new setset data structure
   8  *  \param size The initial size of the setset (in number of elements)
   9  *  \return The created setset
  10  */
  11 xbt_setset_t xbt_setset_new(unsigned int size)
  12 {
  13   xbt_setset_elm_entry_t first_elm = NULL;
  14   xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1);
  15   setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL);
  16   setset->sets = xbt_fifo_new();
  17   /* Expand the elements dynar to the size indicated by the user, */
  18   /* then create the first element, get a pointer to it and add it to the */
  19   /* free elements list */
  20   xbt_dynar_shrink(setset->elm_array, size);
  21   first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
  22   first_elm->free.next = 0;
  23   return setset;
  24 }
  25
  26 /**
  27  *  \brief Destroy a setset and free all it's resources
  28  *  \param The setset to destroy
  29  */
  30 void xbt_setset_destroy(xbt_setset_t setset)
  31 {
  32   xbt_dynar_free(&setset->elm_array);
  33   xbt_fifo_free(setset->sets);
  34   xbt_free(setset);
  35   /* FIXME: check if we should trash the stored objects */
  36 }
  37
  38 /* Add an element to the setset, this will assign to it an index */
  39 xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj)
  40 {
  41   xbt_setset_elm_entry_t new_entry = NULL;
  42   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
  43   xbt_assert0(e->ID == 0, "Adding element with non NULL ID");
  44   xbt_setset_elm_entry_t first_elm =
  45     (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0);
  46
  47   /* Before create a new elm entry check if there is one in the free elm list.*/
  48   /* If there is not free elm entries, then create a new one  */
  49   if(first_elm->free.next != 0){
  50     e->ID = first_elm->free.next;
  51     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next);
  52     first_elm->free.next = new_entry->free.next;
  53   }else{
  54     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
  55     e->ID = xbt_dynar_length(setset->elm_array) - 1;
  56   }
  57   /* Initialize the new element data structure and add it to the hash */
  58   new_entry->info.refcount = 0;
  59   new_entry->info.obj = e;
  60   return new_entry;
  61 }
  62
  63 /* Remove from the setset the object stored at idx */
  64 void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx)
  65 {
  66   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  67   xbt_setset_elm_entry_t first_free = NULL;
  68
  69   /* Decrease the refcount and proceed only if it is 0 */
  70   if(--e_entry->info.refcount > 0)
  71     return;
  72
  73   /* Erase object ID */
  74   e_entry->info.obj->ID = 0;
  75
  76   /* Link the elm entry to the list of free ones */
  77   first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
  78   e_entry->free.next = first_free->free.next;
  79   first_free->free.next = idx;
  80 }
  81
  82 /* Get the object associated to a given index */
  83 /* WARNING: it must be a valid index! */
  84 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
  85 {
  86   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  87   return e_entry->info.obj;
  88 }
  89
  90 /* Increase the refcount of an element */
  91 void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx)
  92 {
  93   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  94   e_entry->info.refcount++;
  95 }
  96
  97 /**
  98  *  \brief Add a new set to the setset
  99  *  \param setset The setset that will contain the created set
 100  *  \returns The created set
 101  */
 102 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
 103 {
 104   xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
 105   newset->setset = setset;
 106   newset->elmcount = 0;
 107   newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1;
 108   newset->bitmap = xbt_new0(unsigned int, newset->size);
 109   xbt_fifo_unshift(setset->sets, newset);
 110   return newset;
 111 }
 112
 113 /**
 114  *  \brief Destroy a set in the setset
 115  *  \param set The set to destroy
 116  */
 117 void xbt_setset_destroy_set(xbt_setset_set_t set)
 118 {
 119   xbt_setset_set_reset(set);
 120   xbt_free(set->bitmap);
 121   xbt_fifo_remove(set->setset->sets, set);
 122   xbt_free(set);
 123
 124   return;
 125 }
 126
 127 /**
 128  *  \brief Insert an element into a set
 129  *  \param set The set where the element is going to be added
 130  *  \param obj The element to add
 131  */
 132 void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
 133 {
 134   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 135
 136   if(e->ID == 0)
 137     _xbt_setset_elm_add(set->setset, e);
 138
 139   /* Check if we need to expand the bitmap */
 140   if(set->size * BITS_INT - 1 < e->ID){
 141     set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int));
 142     memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
 143     set->size = (e->ID / BITS_INT + 1);
 144   }
 145
 146   if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
 147     set->elmcount++;
 148     _xbt_setset_elm_use(set->setset, e->ID);
 149     _set_bit(e->ID, set->bitmap);
 150   }
 151
 152   return;
 153 }
 154
 155 /**
 156  *  \brief Remove an element from a set
 157  *  \param set The set from which the element is going to be removed
 158  *  \param obj The element to remove
 159  */
 160 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
 161 {
 162   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 163   if(e->ID != 0){
 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(set->size * BITS_INT >= e->ID){
 167       if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
 168         set->elmcount--;
 169         _unset_bit(e->ID, set->bitmap);
 170         _xbt_setset_elm_remove(set->setset, e->ID);
 171       }
 172     }
 173   }
 174   return;
 175 }
 176
 177 /**
 178  *  \brief Remove all the elements of a set
 179  *  \param set The set to empty
 180  */
 181 void xbt_setset_set_reset(xbt_setset_set_t set)
 182 {
 183   int i,k;
 184   /* Traverse the set and remove every element */
 185   for(i=0; i < set->size; i++){
 186     if(set->bitmap[i] != 0){
 187       for(k=0; k < BITS_INT; k++){
 188         if(_is_bit_set(k,set->bitmap[i])){
 189           _xbt_setset_elm_remove(set->setset, i * BITS_INT + k);
 190         }
 191       }
 192     }
 193   }
 194   set->elmcount = 0;
 195 }
 196
 197 /**
 198  *  \brief Choose one element of a set (but do not remove it)
 199  *  \param set The set
 200  *  \return An element that belongs to set \a set
 201  */
 202 void *xbt_setset_set_choose(xbt_setset_set_t set)
 203 {
 204   int i,k;
 205   /* Traverse the set and return the first element */
 206   for(i=0; i < set->size; i++){
 207     if(set->bitmap[i] != 0){
 208       for(k=0; k < BITS_INT; k++){
 209         if(_is_bit_set(k,set->bitmap[i])){
 210           return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k);
 211         }
 212       }
 213     }
 214   }
 215   return NULL;
 216 }
 217
 218 /**
 219  *  \brief Extract one element of a set (it removes it)
 220  *  \param set The set
 221  *  \return An element that belonged to set \a set
 222  */
 223 void *xbt_setset_set_extract(xbt_setset_set_t set)
 224 {
 225   void *obj = xbt_setset_set_choose(set);
 226   if(obj){
 227     xbt_setset_set_remove(set, obj);
 228   }
 229   return obj;
 230 }
 231
 232
 233 /**
 234  *  \brief Test if an element belongs to a set
 235  *  \param set The set
 236  *  \param obj The element
 237  *  \return TRUE if the element \a obj belongs to set \a set
 238  */
 239 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
 240 {
 241   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 242   if(e->ID != 0 && e->ID <= set->size * BITS_INT){
 243     return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
 244   }
 245   return FALSE;
 246 }
 247
 248 int xbt_setset_set_size(xbt_setset_set_t set)
 249 {
 250   return set->elmcount;
 251 }
 252
 253
 254 /**
 255  *  \brief Add two sets
 256  *         Add two sets storing the result in the first one
 257  *  \param set1 The first set
 258  *  \param set2 The second set
 259  */
 260 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
 261 {
 262   if(set1->size < set2->size){
 263     xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
 264     set1->size = set2->size;
 265   }
 266
 267   int i,k;
 268   /* Traverse the second set and add every element that is not member of the
 269      first set to it */
 270   for(i=0; i < set2->size; i++){
 271     if(set2->bitmap[i] != 0){
 272       for(k=0; k < BITS_INT; k++){
 273         if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){
 274           set1->elmcount++;
 275           _xbt_setset_elm_use(set1->setset, i * BITS_INT + k);
 276           _set_bit(i * BITS_INT + k, set1->bitmap);
 277         }
 278       }
 279     }
 280   }
 281   return;
 282 }
 283
 284 /**
 285  *  \brief Substract two sets
 286  *         Substract two sets storing the result in the first one
 287  *  \param set1 The first set
 288  *  \param set2 The second set
 289  */
 290 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
 291 {
 292   int i,k;
 293   /* Traverse the second set and remove every element that is member of it to
 294      the first set */
 295   for(i=0; i < min(set1->size,set2->size); i++){
 296     if(set2->bitmap[i] != 0){
 297       for(k=0; k < BITS_INT; k++){
 298         if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){
 299           set1->elmcount--;
 300           _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
 301           _unset_bit(i * BITS_INT + k, set1->bitmap);
 302         }
 303       }
 304     }
 305   }
 306   return;
 307 }
 308
 309 /**
 310  *  \brief Intersect two sets
 311  *         Intersect two sets storing the result in the first one
 312  *  \param set1 The first set
 313  *  \param set2 The second set
 314  */
 315 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
 316 {
 317   int i,k;
 318   /* Traverse the first set and remove every element that is not member of the second set */
 319   for(i=0; i < set1->size; i++){
 320     if(set1->bitmap[i] != 0){
 321       for(k=0; k < BITS_INT; k++){
 322         if(_is_bit_set(k, set1->bitmap[i]) &&
 323             (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){
 324           set1->elmcount--;
 325           _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
 326           _unset_bit(i * BITS_INT + k, set1->bitmap);
 327         }
 328       }
 329     }
 330   }
 331   return;
 332 }
 333
 334 /* Get the cursor to point to the first element of a set */
 335 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
 336 {
 337   (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
 338   (*cursor)->set = set;
 339   int i,k;
 340   /* Traverse the set and point the cursor to the first element */
 341   for(i=0; i < set->size; i++){
 342     if(set->bitmap[i] != 0){
 343       for(k=0; k < BITS_INT; k++){
 344         if(_is_bit_set(k,set->bitmap[i])){
 345           (*cursor)->idx = i * BITS_INT + k;
 346           return;
 347         }
 348       }
 349     }
 350   }
 351 }
 352
 353 /* Get the data pointed by a cursor */
 354 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
 355 {
 356   if(cursor->idx == 0){
 357     xbt_free(cursor);
 358     *data = NULL;
 359     return FALSE;
 360   }else{
 361     *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
 362     return TRUE;
 363   }
 364 }
 365
 366 /* Advance a cursor to the next element */
 367 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
 368 {
 369  int i,k;
 370   cursor->idx++;
 371   /* Traverse the set and point the cursor to the first element */
 372   for(i = cursor->idx / BITS_INT; i < cursor->set->size; i++){
 373     if(cursor->set->bitmap[i] != 0){
 374       for(k = cursor->idx % BITS_INT; k < BITS_INT; k++){
 375         if(_is_bit_set(k,cursor->set->bitmap[i])){
 376           cursor->idx = i * BITS_INT + k;
 377           return;
 378         }
 379       }
 380     }
 381   }
 382   cursor->idx = 0;
 383 }
 384
 385 /* Check if the nth bit of an integer is set or not*/
 386 unsigned int _is_bit_set(unsigned int bit, unsigned int integer)
 387 {
 388   return (0x1 << bit) & integer ? TRUE : FALSE;
 389 }
 390
 391 /* Set the nth bit of an array of integers */
 392 void _set_bit(unsigned int bit, unsigned int *bitmap)
 393 {
 394   bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
 395 }
 396
 397 /* Unset the nth bit of an array of integers */
 398 void _unset_bit(unsigned int bit, unsigned int *bitmap)
 399 {
 400   bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
 401 }
 402
 403
 404
 405
 406
 407
 408
 409