ok..

1 files changed, 91 insertions, 0 deletions

diff --git a/src/map.hff b/src/map.hff
new file mode 100644
index 0000000..d8bbf52
--- /dev/null
+++ b/src/map.hff
@@ -0,0 +1,91 @@
+import "all.hff";
+
+// KTraits:
+//        :hash(K) u32
+//        :eq(T, T) bool
+struct Map<K, V, KTraits> {
+   keys *K,
+   vals *V,
+   bitmap *u8,
+   N int,
+   count int,
+
+   fn _iempty(self *Map, i int) bool {
+      return (self.bitmap[i/8] & (1 << (i%8))) == 0;
+   }
+
+   fn get(self *Map, key K) *V {
+      if self.N == 0 {
+         return #null;
+      }
+      let i0 u32 = KTraits:hash(key);
+      let i = i0 & (self.N - 1);
+      do {
+         if self->_iempty(i) {
+            return #null;
+         } else if KTraits:eq(self.keys[i], key) {
+            return &self.vals[i];
+         }
+         i = (i + 1) & (self.N - 1);
+      } while i != i0;
+      assert(#f, "unreachable");
+   }
+
+   fn put(self *Map, key K, val V) void {
+      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);
+      }
+
+      if self.count == self.N / 2 {
+         // rehash
+      }
+      let i0 u32 = KTraits:hash(key);
+      let i = i0 & (self.N - 1);
+      do {
+         if self->_iempty(i) {
+            self.bitmap[i/8] |= (1 << (i%8));
+            ++self.count;
+            self.vals[i] = val;
+            return;
+         } else if KTraits:eq(self.keys[i], key) {
+            self.vals[i] = val;
+            return;
+         }
+         i = (i + 1) & (self.N - 1);
+      } while i != i0;
+      assert(#f, "unreachable");
+   }
+
+   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);
+      }
+
+      if self.count == self.N / 2 {
+         // rehash
+      }
+      let i0 u32 = KTraits:hash(key);
+      let i = i0 & (self.N - 1);
+      do {
+         if self->_iempty(i) {
+            self.bitmap[i/8] |= (1 << (i%8));
+            ++self.count;
+            self.vals[i] = {};
+            return &self.vals[i];
+         } else if KTraits:eq(self.keys[i], key) {
+            return &self.vals[i];
+         }
+         i = (i + 1) & (self.N - 1);
+      } while i != i0;
+      assert(#f, "unreachable");
+   }
+
+}