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