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

diff --git a/src/xbt/setset.c b/src/xbt/setset.c
index a583713620..79d25575e9 100644
--- a/src/xbt/setset.c
+++ b/src/xbt/setset.c
@@ -3,6 +3,22 @@
 #include <string.h>
 #include "setset_private.h"
 #include "xbt/sysdep.h"
+#include "gras_config.h" /*_XBT_WIN32*/
+
+/*The function ffs doesn't exist for windows*/
+#ifdef _XBT_WIN32
+int ffs(int bits)
+{
+  int i;
+  if (bits == 0)
+    return (0);
+  for (i = 1;; i++, bits >>= 1) {
+    if (bits & 1)
+      break;
+  }
+  return (i);
+}
+#endif
 
 /**
  *  \brief Create a new setset data structure
@@ -13,13 +29,15 @@ xbt_setset_t xbt_setset_new(unsigned int size)
 {
   xbt_setset_elm_entry_t first_elm = NULL;
   xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1);
-  setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL);
+  setset->elm_array =
+      xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL);
   setset->sets = xbt_fifo_new();
   /* Expand the elements dynar to the size indicated by the user, */
   /* then create the first element, get a pointer to it and add it to the */
   /* free elements list */
-  xbt_dynar_shrink(setset->elm_array, size);  
-  first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
+  xbt_dynar_shrink(setset->elm_array, size);
+  first_elm =
+      (xbt_setset_elm_entry_t) xbt_dynar_push_ptr(setset->elm_array);
   first_elm->free.next = 0;
   return setset;
 }
@@ -33,7 +51,7 @@ void xbt_setset_destroy(xbt_setset_t setset)
   xbt_fifo_item_t item;
   xbt_setset_set_t set;
   xbt_dynar_free(&setset->elm_array);
-  xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t){
+  xbt_fifo_foreach(setset->sets, item, set, xbt_setset_set_t) {
     xbt_setset_destroy_set(set);
   }
   xbt_fifo_free(setset->sets);
@@ -44,20 +62,24 @@ void xbt_setset_destroy(xbt_setset_t setset)
 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;
+  xbt_setset_elm_entry_t first_elm = NULL;
+  xbt_setset_elm_t e = (xbt_setset_elm_t) obj;
   xbt_assert0(e->ID == 0, "Adding element with non NULL ID");
-  xbt_setset_elm_entry_t first_elm = 
-    (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0);
-  
+  first_elm =
+      (xbt_setset_elm_entry_t) xbt_dynar_get_ptr(setset->elm_array, 0);
+
   /* Before create a new elm entry check if there is one in the free elm list. */
   /* If there is not free elm entries, then create a new one  */
-  if(first_elm->free.next != 0){
+  if (first_elm->free.next != 0) {
     e->ID = first_elm->free.next;
-    new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next);
+    new_entry =
+        (xbt_setset_elm_entry_t) xbt_dynar_get_ptr(setset->elm_array,
+                                                   first_elm->free.next);
     first_elm->free.next = new_entry->free.next;
-  }else{
-    new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array);
-    e->ID = xbt_dynar_length(setset->elm_array) - 1;    
+  } else {
+    new_entry =
+        (xbt_setset_elm_entry_t) xbt_dynar_push_ptr(setset->elm_array);
+    e->ID = xbt_dynar_length(setset->elm_array) - 1;
   }
 
   new_entry->info.obj = e;
@@ -67,8 +89,9 @@ void xbt_setset_elm_add(xbt_setset_t setset, void *obj)
 /* Remove an object from the setset */
 void xbt_setset_elm_remove(xbt_setset_t setset, void *obj)
 {
-  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_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;
 
   /* Link the elm entry to the list of free ones */
@@ -81,7 +104,8 @@ void xbt_setset_elm_remove(xbt_setset_t setset, void *obj)
 /* WARNING: it must be a valid index! */
 void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx)
 {
-  xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx);
+  xbt_setset_elm_entry_t e_entry =
+      xbt_dynar_get_ptr(setset->elm_array, idx);
   return e_entry->info.obj;
 }
 
@@ -109,7 +133,7 @@ void xbt_setset_destroy_set(xbt_setset_set_t set)
   xbt_free(set->bitmap);
   xbt_fifo_remove(set->setset->sets, set);
   xbt_free(set);
-  
+
   return;
 }
 
@@ -118,22 +142,24 @@ void xbt_setset_destroy_set(xbt_setset_set_t set)
  *  \param set The set where the element is going to be added
  *  \param obj The element to add
  */
-void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
+void xbt_setset_set_insert(xbt_setset_set_t set, void *obj)
 {
-  xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
+  xbt_setset_elm_t e = (xbt_setset_elm_t) obj;
 
-  if(e->ID == 0)
+  if (e->ID == 0)
     xbt_setset_elm_add(set->setset, e);
-  
+
   /* Check if we need to expand the bitmap */
-  if(set->size * BITS_INT - 1 < e->ID){
-    set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int));
-    memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
+  if (set->size * BITS_INT - 1 < e->ID) {
+    set->bitmap =
+        xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int));
+    memset(&set->bitmap[set->size], 0,
+           ((e->ID / BITS_INT + 1) - set->size) * sizeof(int));
     set->size = (e->ID / BITS_INT + 1);
   }
 
   _set_bit(e->ID, set->bitmap);
-  
+
   return;
 }
 
@@ -142,12 +168,12 @@ void xbt_setset_set_insert(xbt_setset_set_t set, void* obj)
  *  \param set The set from which the element is going to be removed
  *  \param obj The element to remove
  */
-void xbt_setset_set_remove(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;
+  xbt_setset_elm_t e = (xbt_setset_elm_t) obj;
   /* 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)
+  if (e->ID != 0 && e->ID <= set->size * BITS_INT)
     _unset_bit(e->ID, set->bitmap);
 
   return;
@@ -171,10 +197,11 @@ void *xbt_setset_set_choose(xbt_setset_set_t set)
 {
   int i;
   /* Traverse the set and return the first element */
-  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);
+  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;
 }
 
@@ -186,7 +213,7 @@ void *xbt_setset_set_choose(xbt_setset_set_t set)
 void *xbt_setset_set_extract(xbt_setset_set_t set)
 {
   void *obj = xbt_setset_set_choose(set);
-  if(obj){
+  if (obj) {
     xbt_setset_set_remove(set, obj);
   }
   return obj;
@@ -199,10 +226,10 @@ void *xbt_setset_set_extract(xbt_setset_set_t set)
  *  \param obj The element
  *  \return TRUE if the element \a obj belongs to set \a set
  */
-int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
+int xbt_setset_set_belongs(xbt_setset_set_t set, void *obj)
 {
-  xbt_setset_elm_t e = (xbt_setset_elm_t)obj;
-  if(e->ID != 0 && e->ID <= set->size * BITS_INT){  
+  xbt_setset_elm_t e = (xbt_setset_elm_t) obj;
+  if (e->ID != 0 && e->ID <= set->size * BITS_INT) {
     return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]);
   }
   return FALSE;
@@ -211,10 +238,10 @@ int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj)
 int xbt_setset_set_size(xbt_setset_set_t set)
 {
   int i, count = 0;
-  
-  for(i=0; i < set->size; i++)
+
+  for (i = 0; i < set->size; i++)
     count += bitcount(set->bitmap[i]);
-    
+
   return count;
 }
 
@@ -230,13 +257,13 @@ 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){
+  if (set1->size < set2->size) {
     xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int));
     set1->size = set2->size;
   }
 
-  for(i=0; i < set1->size; i++)
-    if(set2->bitmap[i] != 0)
+  for (i = 0; i < set1->size; i++)
+    if (set2->bitmap[i] != 0)
       set1->bitmap[i] |= set2->bitmap[i];
 
   return;
@@ -252,8 +279,8 @@ void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2)
 {
   int i;
 
-  for(i=0; i < MIN(set1->size, set2->size); i++)
-    if(set2->bitmap[i] != 0)
+  for (i = 0; i < MIN(set1->size, set2->size); i++)
+    if (set2->bitmap[i] != 0)
       set1->bitmap[i] ^= set2->bitmap[i];
 
   return;
@@ -269,24 +296,25 @@ void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2)
 {
   int i;
 
-  for(i=0; i < MIN(set1->size, set2->size); i++)
-    if(set1->bitmap[i] && set2->bitmap[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 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)
+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;
- 
-  for(i = 0; i < set->size; i++){
-    if(set->bitmap[i] != 0){
+
+  for (i = 0; i < set->size; i++) {
+    if (set->bitmap[i] != 0) {
       (*cursor)->idx = i * BITS_INT + ffs(set->bitmap[i]) - 1;
-      break; 
+      break;
     }
   }
 }
@@ -294,11 +322,11 @@ void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor)
 /* Get the data pointed by a cursor */
 int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data)
 {
-  if(cursor->idx == 0){
+  if (cursor->idx == 0) {
     xbt_free(cursor);
     *data = NULL;
     return FALSE;
-  }else{
+  } else {
     *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx);
     return TRUE;
   }
@@ -310,22 +338,22 @@ void xbt_setset_cursor_next(xbt_setset_cursor_t cursor)
   unsigned int mask;
   unsigned int data;
   cursor->idx++;
-  while(cursor->idx < cursor->set->size * BITS_INT){
-    if((data = cursor->set->bitmap[cursor->idx / BITS_INT])){
+  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){
+      while (mask) {            /* FIXME: mask will never be 0! */
+        if (data & mask) {
           return;
-        }else{
+        } else {
           cursor->idx++;
           mask <<= 1;
         }
       }
-    }else{
+    } else {
       cursor->idx += BITS_INT;
     }
   }
-  cursor->idx = 0; 
+  cursor->idx = 0;
 }
 
 /* Check if the nth bit of an integer is set or not*/
@@ -353,7 +381,7 @@ void _unset_bit(unsigned int bit, unsigned int *bitmap)
  */
 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
+  v = v - ((v >> 1) & 0x55555555);      // reuse input as temporary
+  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);       // temp
+  return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;      // count
+}