src/xbt/setset.c

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