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 element to the setset, this will assign to it an index */
  44 xbt_setset_elm_entry_t _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_assert0(e->ID == 0, "Adding element with non NULL ID");
  49   xbt_setset_elm_entry_t first_elm =
  50     (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0);
  51
  52   /* Before create a new elm entry check if there is one in the free elm list. */
  53   /* If there is not free elm entries, then create a new one  */
  54   if(first_elm->free.next != 0){
  55     e->ID = first_elm->free.next;
  56     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next);
  57     first_elm->free.next = new_entry->free.next;
  58   }else{
  59     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
  60     e->ID = xbt_dynar_length(setset->elm_array) - 1;
  61   }
  62   /* Initialize the new element data structure and add it to the hash */
  63   new_entry->info.refcount = 0;
  64   new_entry->info.obj = e;
  65   return new_entry;
  66 }
  67
  68 /* Remove from the setset the object stored at idx */
  69 void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx)
  70 {
  71   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  72   xbt_setset_elm_entry_t first_free = NULL;
  73
  74   /* Decrease the refcount and proceed only if it is 0 */
  75   if(--e_entry->info.refcount > 0)
  76     return;
  77
  78   /* Erase object ID */
  79   /* FIXME: do not assume that the object still exists, it might be deallocated */
  80   /*e_entry->info.obj->ID = 0;*/
  81
  82   /* Link the elm entry to the list of free ones */
  83   first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
  84   e_entry->free.next = first_free->free.next;
  85   first_free->free.next = idx;
  86 }
  87
  88 /* Get the object associated to a given index */
  89 /* WARNING: it must be a valid index! */
  90 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
  91 {
  92   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
  93   return e_entry->info.obj;
  94 }
  95
  96 /* Increase the refcount of an element */
  97 void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx)
  98 {
  99   xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
 100   e_entry->info.refcount++;
 101 }
 102
 103 /**
 104  *  \brief Add a new set to the setset
 105  *  \param setset The setset that will contain the created set
 106  *  \returns The created set
 107  */
 108 xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
 109 {
 110   xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
 111   newset->setset = setset;
 112   newset->elmcount = 0;
 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_setset_set_reset(set);
 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   if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
 153     set->elmcount++;
 154     _xbt_setset_elm_use(set->setset, e->ID);
 155     _set_bit(e->ID, set->bitmap);
 156   }
 157
 158   return;
 159 }
 160
 161 /**
 162  *  \brief Remove an element from a set
 163  *  \param set The set from which the element is going to be removed
 164  *  \param obj The element to remove
 165  */
 166 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
 167 {
 168   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 169   if(e->ID != 0){
 170     /* If the index of the object is between the bitmap then unset it, otherwise
 171        do not do anything, because we already know it is not in the set */
 172     if(set->size * BITS_INT >= e->ID){
 173       if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
 174         set->elmcount--;
 175         _unset_bit(e->ID, set->bitmap);
 176         _xbt_setset_elm_remove(set->setset, e->ID);
 177       }
 178     }
 179   }
 180   return;
 181 }
 182
 183 /**
 184  *  \brief Remove all the elements of a set
 185  *  \param set The set to empty
 186  */
 187 void xbt_setset_set_reset(xbt_setset_set_t set)
 188 {
 189   int i,k;
 190   /* Traverse the set and remove every element */
 191   for(i=0; i < set->size; i++){
 192     if(set->bitmap[i] != 0){
 193       for(k=0; k < BITS_INT; k++){
 194         if(_is_bit_set(k,set->bitmap[i])){
 195           _xbt_setset_elm_remove(set->setset, i * BITS_INT + k);
 196         }
 197       }
 198     }
 199   }
 200   set->elmcount = 0;
 201 }
 202
 203 /**
 204  *  \brief Choose one element of a set (but do not remove it)
 205  *  \param set The set
 206  *  \return An element that belongs to set \a set
 207  */
 208 void *xbt_setset_set_choose(xbt_setset_set_t set)
 209 {
 210   int i,k;
 211   /* Traverse the set and return the first element */
 212   for(i=0; i < set->size; i++){
 213     if(set->bitmap[i] != 0){
 214       for(k=0; k < BITS_INT; k++){
 215         if(_is_bit_set(k,set->bitmap[i])){
 216           return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k);
 217         }
 218       }
 219     }
 220   }
 221   return NULL;
 222 }
 223
 224 /**
 225  *  \brief Extract one element of a set (it removes it)
 226  *  \param set The set
 227  *  \return An element that belonged to set \a set
 228  */
 229 void *xbt_setset_set_extract(xbt_setset_set_t set)
 230 {
 231   void *obj = xbt_setset_set_choose(set);
 232   if(obj){
 233     xbt_setset_set_remove(set, obj);
 234   }
 235   return obj;
 236 }
 237
 238
 239 /**
 240  *  \brief Test if an element belongs to a set
 241  *  \param set The set
 242  *  \param obj The element
 243  *  \return TRUE if the element \a obj belongs to set \a set
 244  */
 245 int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
 246 {
 247   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 248   if(e->ID != 0 && e->ID <= set->size * BITS_INT){
 249     return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
 250   }
 251   return FALSE;
 252 }
 253
 254 int xbt_setset_set_size(xbt_setset_set_t set)
 255 {
 256   return set->elmcount;
 257 }
 258
 259
 260 /**
 261  *  \brief Add two sets
 262  *         Add two sets storing the result in the first one
 263  *  \param set1 The first set
 264  *  \param set2 The second set
 265  */
 266 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
 267 {
 268   if(set1->size < set2->size){
 269     xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
 270     set1->size = set2->size;
 271   }
 272
 273   int i,k;
 274   /* Traverse the second set and add every element that is not member of the
 275      first set to it */
 276   for(i=0; i < set2->size; i++){
 277     if(set2->bitmap[i] != 0){
 278       for(k=0; k < BITS_INT; k++){
 279         if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){
 280           set1->elmcount++;
 281           _xbt_setset_elm_use(set1->setset, i * BITS_INT + k);
 282           _set_bit(i * BITS_INT + k, set1->bitmap);
 283         }
 284       }
 285     }
 286   }
 287   return;
 288 }
 289
 290 /**
 291  *  \brief Substract two sets
 292  *         Substract two sets storing the result in the first one
 293  *  \param set1 The first set
 294  *  \param set2 The second set
 295  */
 296 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
 297 {
 298   int i,k;
 299   /* Traverse the second set and remove every element that is member of it to
 300      the first set */
 301   for(i=0; i < min(set1->size,set2->size); i++){
 302     if(set2->bitmap[i] != 0){
 303       for(k=0; k < BITS_INT; k++){
 304         if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){
 305           set1->elmcount--;
 306           _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
 307           _unset_bit(i * BITS_INT + k, set1->bitmap);
 308         }
 309       }
 310     }
 311   }
 312   return;
 313 }
 314
 315 /**
 316  *  \brief Intersect two sets
 317  *         Intersect two sets storing the result in the first one
 318  *  \param set1 The first set
 319  *  \param set2 The second set
 320  */
 321 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
 322 {
 323   int i,k;
 324   /* Traverse the first set and remove every element that is not member of the second set */
 325   for(i=0; i < set1->size; i++){
 326     if(set1->bitmap[i] != 0){
 327       for(k=0; k < BITS_INT; k++){
 328         if(_is_bit_set(k, set1->bitmap[i]) &&
 329             (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){
 330           set1->elmcount--;
 331           _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
 332           _unset_bit(i * BITS_INT + k, set1->bitmap);
 333         }
 334       }
 335     }
 336   }
 337   return;
 338 }
 339
 340 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
 341 {
 342   int i;
 343   (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
 344   (*cursor)->set = set;
 345
 346   for(i = 0; i < set->size; i++){
 347     if(set->bitmap[i] != 0){
 348       (*cursor)->idx = i * BITS_INT + ffs(set->bitmap[i]) - 1;
 349       break;
 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   unsigned int mask;
 371   unsigned int data;
 372   cursor->idx++;
 373   while(cursor->idx < cursor->set->size * BITS_INT)
 374   {
 375     if((data = cursor->set->bitmap[cursor->idx / BITS_INT])){
 376       mask = 1 << cursor->idx % BITS_INT;
 377       while(mask){
 378         if(data & mask){
 379           return;
 380         }else{
 381           cursor->idx++;
 382           mask <<= 1;
 383         }
 384       }
 385     }else{
 386       cursor->idx += BITS_INT;
 387     }
 388   }
 389   cursor->idx = 0;
 390 }
 391
 392 /* Check if the nth bit of an integer is set or not*/
 393 unsigned int _is_bit_set(unsigned int bit, unsigned int integer)
 394 {
 395   return (0x1 << bit) & integer ? TRUE : FALSE;
 396 }
 397
 398 /* Set the nth bit of an array of integers */
 399 void _set_bit(unsigned int bit, unsigned int *bitmap)
 400 {
 401   bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT);
 402 }
 403
 404 /* Unset the nth bit of an array of integers */
 405 void _unset_bit(unsigned int bit, unsigned int *bitmap)
 406 {
 407   bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
 408 }