fix

[libfirm] / ir / adt / set.c

diff --git a/ir/adt/set.c b/ir/adt/set.c
index f81fa39..f22c897 100644 (file)
--- a/ir/adt/set.c
+++ b/ir/adt/set.c
@@ -59,7 +59,6 @@
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
-#include "misc.h"
 #include "xmalloc.h"
 #ifdef PSET
 # include "pset.h"
@@ -86,13 +85,13 @@ typedef struct element {
 
 
 struct SET {
-  short        p;                      /* Next bucket to be split      */
-  short        maxp;                   /* upper bound on p during expansion    */
-  int nkey;                    /* current # keys       */
-  short        nseg;                   /* current # segments   */
+  unsigned p;                  /* Next bucket to be split      */
+  unsigned maxp;               /* upper bound on p during expansion    */
+  unsigned nkey;               /* current # keys       */
+  unsigned nseg;               /* current # segments   */
   Segment *dir[DIRECTORY_SIZE];
   MANGLEP(cmp_fun) cmp;                /* function comparing entries */
-  int iter_i, iter_j;
+  unsigned iter_i, iter_j;
   Element *iter_tail;          /* non-NULL while iterating over elts */
 #ifdef PSET
   Element *free_list;          /* list of free Elements */
@@ -145,14 +144,14 @@ stat_chain_len (SET *table, int chain_len)
 const char *MANGLEP(tag);
 
 
-static void
+void
 MANGLEP(describe) (SET *table)
 {
-  int i, j, collide;
+  unsigned i, j, collide;
   Element *ptr;
   Segment *seg;
 
-  printf ("p=%d maxp=%d nkey=%d nseg=%d\n",
+  printf ("p=%u maxp=%u nkey=%u nseg=%u\n",
          table->p, table->maxp, table->nkey, table->nseg);
   for (i = 0;  i < table->nseg;  i++) {
     seg = table->dir[i];
@@ -162,7 +161,7 @@ MANGLEP(describe) (SET *table)
       while (ptr) {
        if (collide) printf ("<%3d>", collide);
        else printf ("table");
-       printf ("[%d][%3d]: %u %p\n", i, j, ptr->entry.hash, ptr->entry.dptr);
+       printf ("[%d][%3d]: %u %p\n", i, j, ptr->entry.hash, (void *)ptr->entry.dptr);
        ptr = ptr->chain;
        collide++;
       }
@@ -179,10 +178,14 @@ SET *
   int i;
   SET *table = xmalloc (sizeof (SET));
 
-  /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
-  assert (nslots >= 0);
-  for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1) assert (i < (i << 1));
-  nslots = i >> SEGMENT_SIZE_SHIFT;
+  if (nslots > SEGMENT_SIZE * DIRECTORY_SIZE)
+    n_slots = DIRECTORY_SIZE;
+  else {
+    assert (nslots >= 0);
+    /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
+    for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1);
+    nslots = i >> SEGMENT_SIZE_SHIFT;
+  }
 
   table->nseg = table->p = table->nkey = 0;
   table->maxp = nslots << SEGMENT_SIZE_SHIFT;
@@ -198,7 +201,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++;
   }
 
@@ -223,6 +226,12 @@ 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
@@ -263,7 +272,8 @@ MANGLEP(first) (SET *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;
@@ -281,7 +291,6 @@ MANGLEP(next) (SET *table)
 void
 MANGLEP(break) (SET *table)
 {
-  assert (table->iter_tail);
   table->iter_tail = NULL;
 }
 
@@ -345,6 +354,7 @@ expand_table (SET *table)
        (Segment *)obstack_alloc (&table->obst,
                                  sizeof(Segment) * SEGMENT_SIZE);
       memset(table->dir[NewSegmentDir], 0, sizeof(Segment) * SEGMENT_SIZE);
+      table->nseg++;
     }
     NewSegment = table->dir[NewSegmentDir];
 
@@ -354,7 +364,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];
@@ -490,9 +499,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;
 }