rehash types set

1 files changed, 24 insertions, 1 deletions

diff --git a/bootstrap/types.c b/bootstrap/types.c
index 386ad58..7b223f6 100644
--- a/bootstrap/types.c
+++ b/bootstrap/types.c
@@ -23,7 +23,7 @@ inittypes() {
       free(types.buckets);
 
    types.size = 0;
-   types.buckets = calloc(types.nbuckets = 64, sizeof(struct typesnode *));   
+   types.buckets = calloc(types.nbuckets = 16, sizeof(struct typesnode *));
 }
 
 static u32
@@ -118,6 +118,29 @@ typesput(const struct type *key) {
    types.size++;
    n->hash = hash;
    *(struct type *)&n->ty = *key;
+
+   if (++types.size > types.nbuckets) {
+      // rehash
+      struct typesnode *nodes = NULL;
+      for (int i = 0; i < types.nbuckets; ++i) {
+         for (struct typesnode *n = types.buckets[i], *next; n; n = next) {
+            next = n->next;
+            n->next = nodes;
+            nodes = n;
+         }
+      }
+      types.buckets = xrealloc(types.buckets,
+                              (types.nbuckets *= 2) * sizeof(struct typesnode));
+      memset(types.buckets, 0, types.nbuckets * sizeof(struct typesnode));
+
+      for (struct typesnode *next; nodes; nodes = next) {
+         u32 idx = nodes->hash & (types.nbuckets - 1);
+         next = nodes->next;
+         nodes->next = types.buckets[idx];
+         types.buckets[idx] = nodes;
+      }
+   }
+
    n->next = types.buckets[idx];
    types.buckets[idx] = n;
    return &n->ty;