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   /* FIXME: we should free all the sets in the fifo setset->sets */
  34   xbt_fifo_free(setset->sets);
  35   xbt_free(setset);
  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   /* FIXME: do not assume that the object still exists, it might be deallocated */
  75   /*e_entry->info.obj->ID = 0;*/
  76
  77   /* Link the elm entry to the list of free ones */
  78   first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
  79   e_entry->free.next = first_free->free.next;
  80   first_free->free.next = idx;
  81 }
  82
  83 /* Get the object associated to a given index */
  84 /* WARNING: it must be a valid index! */
  85 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
  86 {
  87   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  88   return e_entry->info.obj;
  89 }
  90
  91 /* Increase the refcount of an element */
  92 void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx)
  93 {
  94   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  95   e_entry->info.refcount++;
  96 }
  97
  98 /**
  99  *  \brief Add a new set to the setset
 100  *  \param setset The setset that will contain the created set
 101  *  \returns The created set
 102  */
 103 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
 104 {
 105   xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
 106   newset->setset = setset;
 107   newset->elmcount = 0;
 108   newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1;
 109   newset->bitmap = xbt_new0(unsigned int, newset->size);
 110   xbt_fifo_unshift(setset->sets, newset);
 111   return newset;
 112 }
 113
 114 /**
 115  *  \brief Destroy a set in the setset
 116  *  \param set The set to destroy
 117  */
 118 void xbt_setset_destroy_set(xbt_setset_set_t set)
 119 {
 120   xbt_setset_set_reset(set);
 121   xbt_free(set->bitmap);
 122   xbt_fifo_remove(set->setset->sets, set);
 123   xbt_free(set);
 124
 125   return;
 126 }
 127
 128 /**
 129  *  \brief Insert an element into a set
 130  *  \param set The set where the element is going to be added
 131  *  \param obj The element to add
 132  */
 133 void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
 134 {
 135   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 136
 137   if(e->ID == 0)
 138     _xbt_setset_elm_add(set->setset, e);
 139
 140   /* Check if we need to expand the bitmap */
 141   if(set->size * BITS_INT - 1 < e->ID){
 142     set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int));
 143     memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
 144     set->size = (e->ID / BITS_INT + 1);
 145   }
 146
 147   if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
 148     set->elmcount++;
 149     _xbt_setset_elm_use(set->setset, e->ID);
 150     _set_bit(e->ID, set->bitmap);
 151   }
 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(e->ID != 0){
 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(set->size * BITS_INT >= e->ID){
 168       if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
 169         set->elmcount--;
 170         _unset_bit(e->ID, set->bitmap);
 171         _xbt_setset_elm_remove(set->setset, e->ID);
 172       }
 173     }
 174   }
 175   return;
 176 }
 177
 178 /**
 179  *  \brief Remove all the elements of a set
 180  *  \param set The set to empty
 181  */
 182 void xbt_setset_set_reset(xbt_setset_set_t set)
 183 {
 184   int i,k;
 185   /* Traverse the set and remove every element */
 186   for(i=0; i < set->size; i++){
 187     if(set->bitmap[i] != 0){
 188       for(k=0; k < BITS_INT; k++){
 189         if(_is_bit_set(k,set->bitmap[i])){
 190           _xbt_setset_elm_remove(set->setset, i * BITS_INT + k);
 191         }
 192       }
 193     }
 194   }
 195   set->elmcount = 0;
 196 }
 197
 198 /**
 199  *  \brief Choose one element of a set (but do not remove it)
 200  *  \param set The set
 201  *  \return An element that belongs to set \a set
 202  */
 203 void *xbt_setset_set_choose(xbt_setset_set_t set)
 204 {
 205   int i,k;
 206   /* Traverse the set and return the first element */
 207   for(i=0; i < set->size; i++){
 208     if(set->bitmap[i] != 0){
 209       for(k=0; k < BITS_INT; k++){
 210         if(_is_bit_set(k,set->bitmap[i])){
 211           return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k);
 212         }
 213       }
 214     }
 215   }
 216   return NULL;
 217 }
 218
 219 /**
 220  *  \brief Extract one element of a set (it removes it)
 221  *  \param set The set
 222  *  \return An element that belonged to set \a set
 223  */
 224 void *xbt_setset_set_extract(xbt_setset_set_t set)
 225 {
 226   void *obj = xbt_setset_set_choose(set);
 227   if(obj){
 228     xbt_setset_set_remove(set, obj);
 229   }
 230   return obj;
 231 }
 232
 233
 234 /**
 235  *  \brief Test if an element belongs to a set
 236  *  \param set The set
 237  *  \param obj The element
 238  *  \return TRUE if the element \a obj belongs to set \a set
 239  */
 240 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
 241 {
 242   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 243   if(e->ID != 0 && e->ID <= set->size * BITS_INT){
 244     return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
 245   }
 246   return FALSE;
 247 }
 248
 249 int xbt_setset_set_size(xbt_setset_set_t set)
 250 {
 251   return set->elmcount;
 252 }
 253
 254
 255 /**
 256  *  \brief Add two sets
 257  *         Add two sets storing the result in the first one
 258  *  \param set1 The first set
 259  *  \param set2 The second set
 260  */
 261 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
 262 {
 263   if(set1->size < set2->size){
 264     xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
 265     set1->size = set2->size;
 266   }
 267
 268   int i,k;
 269   /* Traverse the second set and add every element that is not member of the
 270      first set to it */
 271   for(i=0; i < set2->size; i++){
 272     if(set2->bitmap[i] != 0){
 273       for(k=0; k < BITS_INT; k++){
 274         if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){
 275           set1->elmcount++;
 276           _xbt_setset_elm_use(set1->setset, i * BITS_INT + k);
 277           _set_bit(i * BITS_INT + k, set1->bitmap);
 278         }
 279       }
 280     }
 281   }
 282   return;
 283 }
 284
 285 /**
 286  *  \brief Substract two sets
 287  *         Substract two sets storing the result in the first one
 288  *  \param set1 The first set
 289  *  \param set2 The second set
 290  */
 291 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
 292 {
 293   int i,k;
 294   /* Traverse the second set and remove every element that is member of it to
 295      the first set */
 296   for(i=0; i < min(set1->size,set2->size); i++){
 297     if(set2->bitmap[i] != 0){
 298       for(k=0; k < BITS_INT; k++){
 299         if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){
 300           set1->elmcount--;
 301           _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
 302           _unset_bit(i * BITS_INT + k, set1->bitmap);
 303         }
 304       }
 305     }
 306   }
 307   return;
 308 }
 309
 310 /**
 311  *  \brief Intersect two sets
 312  *         Intersect two sets storing the result in the first one
 313  *  \param set1 The first set
 314  *  \param set2 The second set
 315  */
 316 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
 317 {
 318   int i,k;
 319   /* Traverse the first set and remove every element that is not member of the second set */
 320   for(i=0; i < set1->size; i++){
 321     if(set1->bitmap[i] != 0){
 322       for(k=0; k < BITS_INT; k++){
 323         if(_is_bit_set(k, set1->bitmap[i]) &&
 324             (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){
 325           set1->elmcount--;
 326           _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
 327           _unset_bit(i * BITS_INT + k, set1->bitmap);
 328         }
 329       }
 330     }
 331   }
 332   return;
 333 }
 334
 335 /* Get the cursor to point to the first element of a set */
 336 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
 337 {
 338   (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
 339   (*cursor)->set = set;
 340   int i,k;
 341   /* Traverse the set and point the cursor to the first element */
 342   for(i=0; i < set->size; i++){
 343     if(set->bitmap[i] != 0){
 344       for(k=0; k < BITS_INT; k++){
 345         if(_is_bit_set(k,set->bitmap[i])){
 346           (*cursor)->idx = i * BITS_INT + k;
 347           return;
 348         }
 349       }
 350     }
 351   }
 352 }
 353
 354 /* Get the data pointed by a cursor */
 355 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
 356 {
 357   if(cursor->idx == 0){
 358     xbt_free(cursor);
 359     *data = NULL;
 360     return FALSE;
 361   }else{
 362     *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
 363     return TRUE;
 364   }
 365 }
 366
 367 /* Advance a cursor to the next element */
 368 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
 369 {
 370  int i,k;
 371   cursor->idx++;
 372   /* Traverse the set and point the cursor to the first element */
 373   for(i = cursor->idx / BITS_INT; i < cursor->set->size; i++){
 374     if(cursor->set->bitmap[i] != 0){
 375       for(k = cursor->idx % BITS_INT; k < BITS_INT; k++){
 376         if(_is_bit_set(k,cursor->set->bitmap[i])){
 377           cursor->idx = i * BITS_INT + k;
 378           return;
 379         }
 380       }
 381     }
 382   }
 383   cursor->idx = 0;
 384 }
 385
 386 /* Check if the nth bit of an integer is set or not*/
 387 unsigned int _is_bit_set(unsigned int bit, unsigned int integer)
 388 {
 389   return (0x1 << bit) & integer ? TRUE : FALSE;
 390 }
 391
 392 /* Set the nth bit of an array of integers */
 393 void _set_bit(unsigned int bit, unsigned int *bitmap)
 394 {
 395   bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
 396 }
 397
 398 /* Unset the nth bit of an array of integers */
 399 void _unset_bit(unsigned int bit, unsigned int *bitmap)
 400 {
 401   bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
 402 }
 403
 404
 405
 406
 407
 408
 409
 410