woa

1 files changed, 21 insertions, 15 deletions

diff --git a/src/set.hff b/src/set.hff
index 6ab44ea..82c213f 100644
--- a/src/set.hff
+++ b/src/set.hff
@@ -1,5 +1,4 @@
 import "vec.hff";
-import "all.hff";
 
 #{
 Traits:hash(K) u32 
@@ -12,6 +11,12 @@ struct Set<T, Traits> {
    N int,
    count int,
 
+
+   fn _nexthash(h *u32) u32 {
+      // return *h = (*h * 1664525) + 1013904223u; // double hashing
+      return ++*h; // linear probing
+   }
+
    fn intern(self *Set, x T) *const T {
       if self.set == #null {
          self.set = xcalloc(self.N = 16, sizeof int);
@@ -21,20 +26,22 @@ struct Set<T, Traits> {
          free(self.set);
          self.set = xcalloc(self.N *= 2, sizeof int);
          vec_each(p, i, self.buf,
-            let j = Traits:hash(p) & (self.N - 1);
+            let h = Traits:hash(p);
+            let j = h & (self.N - 1);
             for ;; {
                if self.set[j] == 0 {
                   self.set[j] = i + 1;
                   break;
                }
-               j = (j + 1) & (self.N - 1);
+               j = _nexthash(&h) & (self.N - 1);
             }
          )
       }
 
-      let i0 u32 = Traits:hash(x) & (self.N - 1);
-      let i int = i0;
-      do {
+      let h u32 = Traits:hash(x);
+      let i = h & (self.N - 1) & (self.N - 1);
+      let n = 0;
+      for ;; {
          if self.set[i] == 0 {
             ++self.count;
             self.buf->push(Traits:dup(x));
@@ -46,23 +53,22 @@ struct Set<T, Traits> {
                return x2;
             }
          }
-         i = (i + 1) & (self.N - 1);
-      } while i != i0;
-      assert(#f, "unreachable");
+         ++n;
+         i = _nexthash(&h) & (self.N - 1);
+      }
    }
    
    fn contains(self *Set, x T) bool {
-      let i0 u32 = Traits:hash(x) & (self.N - 1);
-      let i int = i0;
-      do {
+      let h u32 = Traits:hash(x);
+      let i = h & (self.N - 1);
+      for ;; {
          if self.set[i] == 0 {
             return #f;
          } else if Traits:eq(self.buf.dat[self.set[i] - 1], x) {
             return #t;
          }
-         i = (i + 1) & (self.N - 1);
-      } while i != i0;
-      assert(#f, "unreachable");
+         i = _nexthash(&h) & (self.N - 1);
+      }
    }
 
    fn put(self *Set, x T) void {