set template

1 files changed, 46 insertions, 0 deletions

diff --git a/src/set.hff b/src/set.hff
new file mode 100644
index 0000000..acff95b
--- /dev/null
+++ b/src/set.hff
@@ -0,0 +1,46 @@
+import "vec.hff";
+import "all.hff";
+
+struct Set<T, Traits> {
+   buf Vec<T>,
+   set **const T,
+   N int,
+   count int,
+
+   fn intern(self *Set, x T) *const T {
+      if self.set == #null {
+         self.set = xcalloc(self.N = 16, sizeof *T);
+      }
+
+      if self.count == self.N / 2 {
+         free(self.set);
+         self.set = xcalloc(self.N *= 2, sizeof *T);
+         vec_each(p, i, self.buf,
+            let i = Traits:hash(p) & (self.N - 1);
+            for ;; {
+               if self.set[i] == #null {
+                  self.set[i] = &self.buf.dat[i];
+                  break;
+               }
+               i = (i + 1) & (self.N - 1);
+            }
+         )
+      }
+
+      let i0 = Traits:hash(x) & (self.N - 1);
+      let i int = i0;
+      do {
+         if self.set[i] == #null {
+            ++self.count;
+            self.buf->push(Traits:dup(x));
+            return self.set[i] = &self.buf.dat[self.buf.len - 1];
+         } else if Traits:eq(*self.set[i], x) {
+            fprintf(stderr, "found %s\n", x);
+            return self.set[i];
+         }
+         i = (i + 1) & (self.N - 1);
+      } while i != i0;
+      assert(#f, "unreachable");
+   }
+
+}