Checks now the Load_mode

[libfirm] / ir / adt / set.c

diff --git a/ir/adt/set.c b/ir/adt/set.c
index edd678f..f495bd1 100644 (file)
--- a/ir/adt/set.c
+++ b/ir/adt/set.c
@@ -36,14 +36,6 @@
 # include <config.h>
 #endif
 
-#ifndef INLINE
-#ifdef USE_GCC_INLINE
-#define INLINE inline
-#else
-#define INLINE
-#endif
-#endif
-
 /* bcopy is not ISO C *
 #define bcopy(X, Y, Z) memcpy((Y), (X), (Z))
 */
@@ -67,7 +59,6 @@
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
-#include "misc.h"
 #include "xmalloc.h"
 #ifdef PSET
 # include "pset.h"
@@ -84,11 +75,11 @@
 #define SEGMENT_SIZE           (1 << SEGMENT_SIZE_SHIFT)
 #define DIRECTORY_SIZE_SHIFT   8
 #define DIRECTORY_SIZE         (1 << DIRECTORY_SIZE_SHIFT)
-#define MAX_LOAD_FACTOR        4
+#define MAX_LOAD_FACTOR                4
 
 
 typedef struct element {
-  struct element *chain;
+  struct element *chain;       /* for chaining Elements */
   MANGLEP (entry) entry;
 } Element, *Segment;
 
@@ -103,9 +94,9 @@ struct SET {
   int iter_i, iter_j;
   Element *iter_tail;          /* non-NULL while iterating over elts */
 #ifdef PSET
-  Element *free_list;
+  Element *free_list;          /* list of free Elements */
 #endif
-  struct obstack obst;
+  struct obstack obst;         /* obstack for allocation all data */
 #ifdef STATS
   int naccess, ncollision, ndups;
   int max_chain_len;
@@ -206,7 +197,7 @@ SET *
     table->dir[i] = (Segment *)obstack_alloc (&table->obst,
                                              sizeof (Segment) * SEGMENT_SIZE);
 
-    memset (table->dir[i], 0, sizeof (Segment) * SEGMENT_SIZE);
+    memset(table->dir[i], 0, sizeof (Segment) * SEGMENT_SIZE);
     table->nseg++;
   }
 
@@ -231,7 +222,16 @@ PMANGLE(del) (SET *table)
   xfree (table);
 }
 
+int
+MANGLEP(count) (SET *table)
+{
+  return table->nkey;
+}
 
+/*
+ * do one iteration step, return 1
+ * if still data in the set, 0 else
+ */
 static INLINE int
 iter_step (SET *table)
 {
@@ -245,7 +245,9 @@ iter_step (SET *table)
   return 1;
 }
 
-
+/*
+ * finds the first entry in the table
+ */
 void *
 MANGLEP(first) (SET *table)
 {
@@ -260,13 +262,19 @@ MANGLEP(first) (SET *table)
   return table->iter_tail->entry.dptr;
 }
 
-
+/*
+ * returns next entry in the table
+ */
 void *
 MANGLEP(next) (SET *table)
 {
-  assert (table->iter_tail);
+  if (!table->iter_tail)
+    return NULL;
+
+  /* follow collision chain */
   table->iter_tail = table->iter_tail->chain;
   if (!table->iter_tail) {
+    /* go to next segment */
     do {
       if (!iter_step (table)) return NULL;
     } while (!table->dir[table->iter_i][table->iter_j]);
@@ -279,23 +287,27 @@ MANGLEP(next) (SET *table)
 void
 MANGLEP(break) (SET *table)
 {
-  assert (table->iter_tail);
   table->iter_tail = NULL;
 }
 
-
+/*
+ * limit the hash value
+ */
 static INLINE unsigned
 Hash (SET *table, unsigned h)
 {
   unsigned address;
 
-  address = h & (table->maxp - 1);
+  address = h & (table->maxp - 1);          /* h % table->maxp */
   if (address < (unsigned)table->p)
     address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
   return address;
 }
 
-
+/*
+ * returns non-zero if the number of elements in
+ * the set is greater then number of segments * MAX_LOAD_FACTOR
+ */
 static INLINE int
 loaded (SET *table)
 {
@@ -303,7 +315,14 @@ loaded (SET *table)
          > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
 }
 
-
+/*
+ * expand the hash-table: the algorithm is split, so on every
+ * insert, only ONE segment is rehashed!
+ *
+ * table->p contains the current segment to split
+ * after all segments were split, table->p is set to zero and
+ * table->maxp is duplicated.
+ */
 static void
 expand_table (SET *table)
 {
@@ -318,18 +337,20 @@ expand_table (SET *table)
 
   if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
     /* Locate the bucket to be split */
-    OldSegmentDir = table->p >> SEGMENT_SIZE_SHIFT;
-    OldSegment = table->dir[OldSegmentDir];
+    OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
+    OldSegment      = table->dir[OldSegmentDir];
     OldSegmentIndex = table->p & (SEGMENT_SIZE-1);
 
     /* Expand address space; if necessary create a new segment */
-    NewAddress = table->maxp + table->p;
-    NewSegmentDir = NewAddress >> SEGMENT_SIZE_SHIFT;
+    NewAddress      = table->maxp + table->p;
+    NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
     NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
     if (NewSegmentIndex == 0) {
       table->dir[NewSegmentDir] =
        (Segment *)obstack_alloc (&table->obst,
                                  sizeof(Segment) * SEGMENT_SIZE);
+      memset(table->dir[NewSegmentDir], 0, sizeof(Segment) * SEGMENT_SIZE);
+      table->nseg++;
     }
     NewSegment = table->dir[NewSegmentDir];
 
@@ -339,7 +360,6 @@ expand_table (SET *table)
       table->maxp <<= 1;       /* table->maxp *= 2     */
       table->p = 0;
     }
-    table->nseg++;
 
     /* Relocate records to the new bucket */
     Previous = &OldSegment[OldSegmentIndex];
@@ -350,9 +370,9 @@ expand_table (SET *table)
       if (Hash (table, Current->entry.hash) == NewAddress) {
        /* move to new chain */
        *LastOfNew = Current;
-       *Previous = Current->chain;
-       LastOfNew = &Current->chain;
-       Current = Current->chain;
+       *Previous  = Current->chain;
+       LastOfNew  = &Current->chain;
+       Current    = Current->chain;
        *LastOfNew = NULL;
       } else {
        /* leave on old chain */
@@ -390,7 +410,7 @@ MANGLE(_,_search) (SET *table,
 
   /* Find collision chain */
   h = Hash (table, hash);
-  SegmentIndex = h & (SEGMENT_SIZE-1);
+  SegmentIndex   = h & (SEGMENT_SIZE-1);
   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
   assert (CurrentSegment != NULL);
   q = CurrentSegment[SegmentIndex];
@@ -475,9 +495,24 @@ pset_remove (SET *table, const void *key, unsigned hash)
   stat_chain_len (table, chain_len);
 
   q = *p;
+
+  if (q == table->iter_tail) {
+    /* removing current element */
+    table->iter_tail = q->chain;
+    if (!table->iter_tail) {
+      /* go to next segment */
+      do {
+       if (!iter_step (table))
+         break;
+      } while (!table->dir[table->iter_i][table->iter_j]);
+      table->iter_tail = table->dir[table->iter_i][table->iter_j];
+    }
+  }
+
   *p = (*p)->chain;
   q->chain = table->free_list;
   table->free_list = q;
+  --table->nkey;
 
   return q->entry.dptr;
 }