fix arena

1 files changed, 47 insertions, 12 deletions

diff --git a/src/map.hff b/src/map.hff
index 6900878..87d0506 100644
--- a/src/map.hff
+++ b/src/map.hff
@@ -18,8 +18,8 @@ struct Map<K, V, KTraits> {
       if self.N == 0 {
          return #null;
       }
-      let i0 u32 = KTraits:hash(key);
-      let i = i0 & (self.N - 1);
+      let h u32 = KTraits:hash(key);
+      let i = h & (self.N - 1);
       do {
          if self->_iempty(i) {
             return #null;
@@ -27,24 +27,59 @@ struct Map<K, V, KTraits> {
             return &self.vals[i];
          }
          i = (i + 1) & (self.N - 1);
-      } while i != i0;
+      } while i != h;
       assert(#f, "unreachable");
    }
 
+   fn _reallockvb(self *Map) void {
+      let p = xcalloc((self.N * (sizeof K + sizeof V)) + (self.N / 8), 1);
+      self.keys = p;
+      self.vals = as(*V)(self.keys + self.N);
+      self.bitmap = as(*u8)(self.vals + self.N);
+   }
+
+   fn _rehash(self *Map, newN int) void {
+      let oldks = self.keys,
+          oldvs = self.vals,
+          oldbmp = self.bitmap;
+      self.N *= 2;
+      self->_reallockvb();
+      for let i = 0; i < self.N / 2; ++i {
+         let k = oldks[i],
+             v = oldvs[i],
+             b = (oldbmp[i/8] & (1 << (i%8))) != 0;
+         if (b) {
+            let h u32 = KTraits:hash(k);
+            let i = h & (self.N - 1);
+            for ;; {
+               if self->_iempty(i) {
+                  self.keys[i] = k;
+                  self.vals[i] = v;
+                  self.bitmap[i/8] |= 1 << (i%8);
+               } else if KTraits:eq(self.keys[i], k) {
+                  assert(#f, "unreachable");
+               }
+               i = (i + 1) & (self.N - 1);
+            }
+
+         }
+      }
+      free(oldks);
+   }
+
    fn get_slot(self *Map, key K) *V {
       if self.keys == #null {
-         assert(self.vals == #null and self.bitmap == #null and self.N == 0 and self.count == 0,
-               "?");
-         self.keys = xcalloc(self.N = 16, sizeof K);
-         self.vals = xcalloc(self.N, sizeof V);
-         self.bitmap = xcalloc(self.N / 8, 1);
+         assert(self.vals == #null and self.bitmap == #null and self.N == 0 and self.count == 0, "?");
+         self.N = 16;
+         _reallockvb(self);
       }
 
       if self.count == self.N / 2 {
-         // rehash
+         self->_rehash(self.N * 2);
       }
-      let i0 u32 = KTraits:hash(key);
-      let i = i0 & (self.N - 1);
+
+      let h u32 = KTraits:hash(key);
+      let i = h & (self.N - 1);
       do {
          if self->_iempty(i) {
             self.bitmap[i/8] |= (1 << (i%8));
@@ -55,7 +90,7 @@ struct Map<K, V, KTraits> {
             return &self.vals[i];
          }
          i = (i + 1) & (self.N - 1);
-      } while i != i0;
+      } while i != h;
       assert(#f, "unreachable");
    }