X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/aea9fab393c4680b1165fb8af70e28736c5dbd07..4fef14624811a33d03bb19ceb48661d07a1720bb:/src/xbt/setset.c

diff --git a/src/xbt/setset.c b/src/xbt/setset.c
index ece4fa5a87..a583713620 100644
--- a/src/xbt/setset.c
+++ b/src/xbt/setset.c
@@ -1,5 +1,6 @@
 #include <stddef.h>
 #include <stdio.h>
+#include <string.h>
 #include "setset_private.h"
 #include "xbt/sysdep.h"
 
@@ -29,14 +30,18 @@ xbt_setset_t xbt_setset_new(unsigned int size)
  */
 void xbt_setset_destroy(xbt_setset_t setset)
 {
+  xbt_fifo_item_t item;
+  xbt_setset_set_t set;
   xbt_dynar_free(&setset->elm_array);
-  /* FIXME: we should free all the sets in the fifo setset->sets */
+  xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t){
+    xbt_setset_destroy_set(set);
+  }
   xbt_fifo_free(setset->sets);
   xbt_free(setset);
 }
 
-/* Add an element to the setset, this will assign to it an index */
-xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj)
+/* Add an object to the setset, this will calculate its ID */
+void xbt_setset_elm_add(xbt_setset_t setset, void *obj)
 {
   xbt_setset_elm_entry_t new_entry = NULL;
   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
@@ -54,30 +59,22 @@ xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj)
     new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
     e->ID = xbt_dynar_length(setset->elm_array) - 1;    
   }
-  /* Initialize the new element data structure and add it to the hash */
-  new_entry->info.refcount = 0;
+
   new_entry->info.obj = e;
-  return new_entry;
+  return;
 }
 
-/* Remove from the setset the object stored at idx */
-void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx)
+/* Remove an object from the setset */
+void xbt_setset_elm_remove(xbt_setset_t setset, void *obj)
 {
-  xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
+  xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
+  xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, e->ID);
   xbt_setset_elm_entry_t first_free = NULL;
 
-  /* Decrease the refcount and proceed only if it is 0 */
-  if(--e_entry->info.refcount > 0)
-    return;
-
-  /* Erase object ID */
-  /* FIXME: do not assume that the object still exists, it might be deallocated */
-  /*e_entry->info.obj->ID = 0;*/
-  
   /* Link the elm entry to the list of free ones */
   first_free = xbt_dynar_get_ptr(setset->elm_array, 0);
   e_entry->free.next = first_free->free.next;
-  first_free->free.next = idx;
+  first_free->free.next = e->ID;
 }
 
 /* Get the object associated to a given index */
@@ -88,13 +85,6 @@ void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
   return e_entry->info.obj;
 }
 
-/* Increase the refcount of an element */
-void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx)
-{
-  xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
-  e_entry->info.refcount++;  
-}
-
 /**
  *  \brief Add a new set to the setset
  *  \param setset The setset that will contain the created set
@@ -104,7 +94,6 @@ xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
 {
   xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1);
   newset->setset = setset;
-  newset->elmcount = 0;
   newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1;
   newset->bitmap = xbt_new0(unsigned int, newset->size);
   xbt_fifo_unshift(setset->sets, newset);
@@ -117,7 +106,6 @@ xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset)
  */
 void xbt_setset_destroy_set(xbt_setset_set_t set)
 {
-  xbt_setset_set_reset(set);
   xbt_free(set->bitmap);
   xbt_fifo_remove(set->setset->sets, set);
   xbt_free(set);
@@ -135,7 +123,7 @@ void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
 
   if(e->ID == 0)
-    _xbt_setset_elm_add(set->setset, e);
+    xbt_setset_elm_add(set->setset, e);
   
   /* Check if we need to expand the bitmap */
   if(set->size * BITS_INT - 1 < e->ID){
@@ -143,13 +131,9 @@ void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
     memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
     set->size = (e->ID / BITS_INT + 1);
   }
-  
-  if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
-    set->elmcount++;
-    _xbt_setset_elm_use(set->setset, e->ID);
-    _set_bit(e->ID, set->bitmap);
-  }
 
+  _set_bit(e->ID, set->bitmap);
+  
   return;
 }
 
@@ -161,17 +145,11 @@ void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
 void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
 {
   xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
-  if(e->ID != 0){
-    /* If the index of the object is between the bitmap then unset it, otherwise
-       do not do anything, because we already know it is not in the set */
-    if(set->size * BITS_INT >= e->ID){
-      if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){
-        set->elmcount--;
-        _unset_bit(e->ID, set->bitmap);
-        _xbt_setset_elm_remove(set->setset, e->ID);
-      }
-    }
-  }
+  /* If the index of the object is between the bitmap then unset it, otherwise
+     do not do anything, because we already know it is not in the set */
+  if(e->ID != 0 && e->ID <= set->size * BITS_INT)
+    _unset_bit(e->ID, set->bitmap);
+
   return;
 }
 
@@ -181,18 +159,7 @@ void xbt_setset_set_remove(xbt_setset_set_t set, void* obj)
  */
 void xbt_setset_set_reset(xbt_setset_set_t set)
 {
-  int i,k;
-  /* Traverse the set and remove every element */
-  for(i=0; i < set->size; i++){
-    if(set->bitmap[i] != 0){
-      for(k=0; k < BITS_INT; k++){
-        if(_is_bit_set(k,set->bitmap[i])){
-          _xbt_setset_elm_remove(set->setset, i * BITS_INT + k);
-        }
-      }
-    }
-  }
-  set->elmcount = 0;
+  memset(set->bitmap, 0, set->size * sizeof(int));
 }
 
 /**
@@ -202,17 +169,12 @@ void xbt_setset_set_reset(xbt_setset_set_t set)
  */
 void *xbt_setset_set_choose(xbt_setset_set_t set)
 {
-  int i,k;
+  int i;
   /* Traverse the set and return the first element */
-  for(i=0; i < set->size; i++){
-    if(set->bitmap[i] != 0){
-      for(k=0; k < BITS_INT; k++){
-        if(_is_bit_set(k,set->bitmap[i])){
-          return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k);
-        }
-      }
-    }
-  }
+  for(i = 0; i < set->size; i++)
+    if(set->bitmap[i] != 0)
+      return _xbt_setset_idx_to_obj(set->setset, 
+                                    i * BITS_INT + ffs(set->bitmap[i]) - 1);
   return NULL;
 }
 
@@ -248,7 +210,12 @@ int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
 
 int xbt_setset_set_size(xbt_setset_set_t set)
 {
-  return set->elmcount;
+  int i, count = 0;
+  
+  for(i=0; i < set->size; i++)
+    count += bitcount(set->bitmap[i]);
+    
+  return count;
 }
 
 
@@ -260,25 +227,18 @@ int xbt_setset_set_size(xbt_setset_set_t set)
  */
 void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
 {
+  int i;
+
+  /* Increase the size of set1 if necessary */
   if(set1->size < set2->size){
     xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
     set1->size = set2->size;
   }
 
-  int i,k;
-  /* Traverse the second set and add every element that is not member of the
-     first set to it */
-  for(i=0; i < set2->size; i++){
-    if(set2->bitmap[i] != 0){
-      for(k=0; k < BITS_INT; k++){
-        if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){
-          set1->elmcount++;
-          _xbt_setset_elm_use(set1->setset, i * BITS_INT + k);
-          _set_bit(i * BITS_INT + k, set1->bitmap);
-        }
-      }
-    }
-  }
+  for(i=0; i < set1->size; i++)
+    if(set2->bitmap[i] != 0)
+      set1->bitmap[i] |= set2->bitmap[i];
+
   return;
 }
 
@@ -290,20 +250,12 @@ void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2)
  */
 void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
 {
-  int i,k;
-  /* Traverse the second set and remove every element that is member of it to
-     the first set */
-  for(i=0; i < min(set1->size,set2->size); i++){
-    if(set2->bitmap[i] != 0){
-      for(k=0; k < BITS_INT; k++){
-        if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){
-          set1->elmcount--;
-          _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
-          _unset_bit(i * BITS_INT + k, set1->bitmap);
-        }
-      }
-    }
-  }
+  int i;
+
+  for(i=0; i < MIN(set1->size, set2->size); i++)
+    if(set2->bitmap[i] != 0)
+      set1->bitmap[i] ^= set2->bitmap[i];
+
   return;
 }
 
@@ -315,38 +267,26 @@ void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
  */
 void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
 {
-  int i,k;
-  /* Traverse the first set and remove every element that is not member of the second set */
-  for(i=0; i < set1->size; i++){
-    if(set1->bitmap[i] != 0){
-      for(k=0; k < BITS_INT; k++){
-        if(_is_bit_set(k, set1->bitmap[i]) && 
-            (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){
-          set1->elmcount--;
-          _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k);
-          _unset_bit(i * BITS_INT + k, set1->bitmap);
-        }
-      }
-    }
-  }
+  int i;
+
+  for(i=0; i < MIN(set1->size, set2->size); i++)
+    if(set1->bitmap[i] && set2->bitmap[i])
+      set1->bitmap[i] &= set2->bitmap[i];
+
   return;
 }
 
-/* Get the cursor to point to the first element of a set */
+/* Get a cursor pointing to the first element of the set */
 void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
 {
+  int i;
   (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1);
   (*cursor)->set = set;
-  int i,k;
-  /* Traverse the set and point the cursor to the first element */
-  for(i=0; i < set->size; i++){
+ 
+  for(i = 0; i < set->size; i++){
     if(set->bitmap[i] != 0){
-      for(k=0; k < BITS_INT; k++){
-        if(_is_bit_set(k,set->bitmap[i])){
-          (*cursor)->idx = i * BITS_INT + k;
-          return; 
-        }
-      }
+      (*cursor)->idx = i * BITS_INT + ffs(set->bitmap[i]) - 1;
+      break; 
     }
   }
 }
@@ -367,17 +307,22 @@ int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
 /* Advance a cursor to the next element */
 void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
 {
- int i,k;
+  unsigned int mask;
+  unsigned int data;
   cursor->idx++;
-  /* Traverse the set and point the cursor to the first element */
-  for(i = cursor->idx / BITS_INT; i < cursor->set->size; i++){
-    if(cursor->set->bitmap[i] != 0){
-      for(k = cursor->idx % BITS_INT; k < BITS_INT; k++){
-        if(_is_bit_set(k,cursor->set->bitmap[i])){
-          cursor->idx = i * BITS_INT + k;
-          return; 
+  while(cursor->idx < cursor->set->size * BITS_INT){
+    if((data = cursor->set->bitmap[cursor->idx / BITS_INT])){
+      mask = 1 << cursor->idx % BITS_INT;
+      while(mask){    /* FIXME: mask will never be 0! */
+        if(data & mask){
+          return;
+        }else{
+          cursor->idx++;
+          mask <<= 1;
         }
       }
+    }else{
+      cursor->idx += BITS_INT;
     }
   }
   cursor->idx = 0; 
@@ -401,10 +346,14 @@ void _unset_bit(unsigned int bit, unsigned int *bitmap)
   bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT));
 }
 
-
-
-
-
-
-
-
+/**
+ * Bitcount function 
+ * taken from http://graphics.stanford.edu/~seander/bithacks.html 
+ * Note: it assumes 4 byte integers
+ */
+int bitcount(int v)
+{
+  v = v - ((v >> 1) & 0x55555555);                        // reuse input as temporary
+  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);         // temp
+  return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;  // count
+}
\ No newline at end of file