hm

1 files changed, 93 insertions, 0 deletions

diff --git a/mem.c b/mem.c
index 11c1c8c..c16fe54 100644
--- a/mem.c
+++ b/mem.c
@@ -114,4 +114,97 @@ freearena(struct arena *ar)
    }
 }
 
+#if 0
+
+int
+map_get_(struct mapbase *m, int k)
+{
+   if (!m->N) return 0;
+   for (int i = k;; ++i) {
+      bool notempty = bstest(m->bs, k);
+      i &= m->N - 1;
+      if (notempty && m->k[i] == k)
+         return i;
+      if (!notempty)
+         return -1;
+   }
+}
+
+
+void
+map_init_(struct mapbase *m, void **v, uint vsiz, uint N)
+{
+   uint sizk = N*sizeof(int),
+        sizv = N*vsiz,
+        sizbs = BSCOUNT(N)*sizeof(struct bitset);
+
+   assert(N && (N & (N - 1)) == 0);
+   m->k = xcalloc(sizk + sizv + sizbs, "map_rehash");
+   *v = (char *)m->k + sizk;
+   m->bs = (struct bitset *)((char *)*v + sizv);
+   m->N = N;
+}
+
+static void
+map_rehash(struct mapbase *m, void **v, uint vsiz)
+{
+   int *newk, i, k, j;
+   void *newv;
+   struct bitset *newbs;
+   uint N2 = m->N << 1,
+        sizk = N2*sizeof(int),
+        sizv = N2*vsiz,
+        sizbs = BSCOUNT(N2)*sizeof(struct bitset);
+
+   assert(N2);
+   newk = xrealloc(NULL, sizk + sizv + sizbs, "map_rehash");
+   newv = (char *)newk + sizk;
+   newbs = (struct bitset *)((char *)newv + sizv);
+   for (i = 0; i < m->N; ++i) {
+      if (!bstest(m->bs, i))
+         continue;
+      j = k = m->k[i];
+      for (;; ++j) {
+         j &= N2 - 1;
+         if (!bstest(newbs, i)) {
+            bsset(newbs, i);
+            m->k[j] = k;
+            memcpy((char *)newv + j*vsiz, (char *)*v + i*vsiz, vsiz);
+            break;
+         }
+      }
+   }
+   free(m->k);
+   free(*v);
+   free(m->bs);
+   m->k = newk;
+   *v = newv;
+   m->bs = newbs;
+   m->N = N2;
+}
+
+int
+map_set_(struct mapbase *m, void **v, uint vsiz, int k)
+{
+   if (!m->N) return 0;
+   if (m->n >= m->N >> 1) {
+      map_rehash(m, v, vsiz);
+      assert(m->n < m->N);
+   }
+   for (int i = k;; ++i) {
+      bool notempty = bstest(m->bs, k);
+      i &= m->N - 1;
+      if (notempty && m->k[i] == k)
+         return i;
+      if (!notempty) {
+         m->k[i] = k;
+         bsset(m->bs, i);
+         ++m->n;
+         return i;
+      }
+   }
+}
+
+#endif
+
 /* vim:set ts=3 sw=3 expandtab: */