fix my hash table algorithm - argh

3 files changed, 67 insertions, 15 deletions

diff --git a/lib/cbit/htab.h b/lib/cbit/htab.h
index 054b423..7dbbf6b 100644
--- a/lib/cbit/htab.h
+++ b/lib/cbit/htab.h
@@ -105,25 +105,46 @@ struct htab_internal {
         return NULL; \
     } \
     \
-    /* slow but who cares */ \
+    /* a bit inefficient */ \
     void __htab_key_removeat_##name(struct htab_internal *restrict hi, \
                                     void *op, \
                                     size_t entry_size) { \
-        key_ty *orig = op; \
-        key_ty *end = (void *) ((char *) hi->base + hi->capacity * entry_size); \
-        key_ty *cur = orig; \
-        key_ty *prev; \
-        do { \
-            prev = cur; \
+        size_t capacity = hi->capacity; \
+        char *buckets = (char *) hi->base; \
+        key_ty *end = (void *) buckets + capacity * entry_size; \
+        key_ty *hole = op; \
+        key_ty *cur = hole; \
+        key_ty *last_cf_not_after_hole = NULL; \
+        while (1) { \
             cur = (void *) ((char *) cur + entry_size); \
-            if (cur == end) \
+            if (cur == end)\
                 cur = hi->base; \
-            if (null_func(cur)) \
-                break; \
-            memmove(prev, cur, entry_size); \
-            prev = cur; \
-        } while (cur != orig); \
-        memset(cur, nil_byte, entry_size); \
+            if (cur == hole || null_func(cur)) { \
+                if (!last_cf_not_after_hole) { \
+                    /* all of the elements in this chain have starting \
+                     * positions (hashes) strictly 'after' the hole position, \
+                     * so we can't move any of them into the hole.  but that \
+                     * also means it's safe to just erase the hole. */ \
+                    memset(hole, nil_byte, entry_size); \
+                    break; \
+                } else { \
+                    memcpy(hole, last_cf_not_after_hole, entry_size); \
+                    /* if we could get the last element which has the
+                     * 'earliest' hash in the chain, then it would be safe to
+                     * end here, but ... */ \
+                    cur = hole = last_cf_not_after_hole; \
+                    last_cf_not_after_hole = NULL; \
+                    continue; \
+                } \
+            } \
+            size_t cur_hash = (hash_func(cur)) % capacity; \
+            key_ty *cur_chain_first = (void *) buckets + cur_hash * entry_size; \
+            bool cf_after_hole /* cyclically */ = hole <= cur ? \
+                (hole < cur_chain_first) : \
+                (cur < cur_chain_first && cur_chain_first <= hole); \
+            if (!cf_after_hole) \
+                last_cf_not_after_hole = cur; \
+        } \
         hi->length--; \
     } \
     void __htab_key_memset_##name(void *ptr, size_t size) { \
diff --git a/script/mconfig.py b/script/mconfig.py
index 9b37089..ac47d01 100644
--- a/script/mconfig.py
+++ b/script/mconfig.py
@@ -870,6 +870,7 @@ class MakefileEmitter(Emitter):
             raise ValueError("your awful filename %r can't be encoded in make (probably)" % (fn,))
         return re.sub(r'([ :\$\\])', r'\\\1', fn)
     # depfile = ('makefile', filename) or ('msvc',)
+    # TODO TODO: the depfile out paths won't be relative, fix that somehow
     def add_command_raw(self, outs, ins, argvs, phony=False, depfile=None):
         bit = ''
         outs = ' '.join(map(self.filename_rel_and_escape, outs))
diff --git a/test/test-htab.c b/test/test-htab.c
index c85d620..57886f7 100644
--- a/test/test-htab.c
+++ b/test/test-htab.c
@@ -13,6 +13,13 @@ struct teststr {
 DECL_EXTERN_HTAB_KEY(teststr, const char *);
 DECL_HTAB(teststr_int, teststr, int);
 
+#define u32_hash(up) (*(up) % 100)
+#define u32_null(up) (!*(up))
+#define u32_eq(u1p, u2p) (*(u1p) == *(u2p))
+
+DECL_STATIC_HTAB_KEY(u32, uint32_t, u32_hash, u32_eq, u32_null, 0);
+DECL_HTAB(u32_u32, u32, uint32_t);
+
 int main() {
     /* test loop crap */
     LET(int y = 5)
@@ -31,7 +38,6 @@ int main() {
 
     struct htab_teststr_int *hp;
     HTAB_STORAGE(teststr_int) stor = HTAB_STORAGE_INIT_STATIC(&stor, teststr_int);
-    /*HTAB_STORAGE_INIT(&stor, teststr_int);*/
     hp = &stor.h;
     for(int i = 0; i < 100; i++) {
         const char *k;
@@ -55,6 +61,30 @@ int main() {
             printf("%s -> %d\n", *k, *v);
     }
     htab_free_storage_teststr_int(hp);
+
+    HTAB_STORAGE(u32_u32) h2;
+    HTAB_STORAGE_INIT(&h2, u32_u32);
+    uint32_t h2_raw[501];
+    memset(h2_raw, 0xff, sizeof(h2_raw));
+    for (int i = 0; i < 3000; i++) {
+        uint32_t op = arc4random() & 1;
+        uint32_t key = (arc4random() % 500) + 1;
+        if (op == 0) { /* set */
+            uint32_t val = arc4random() & 0x7fffffff;
+            *htab_setp_u32_u32(&h2.h, &key, NULL) = val;
+            h2_raw[key] = val;
+        } else { /* delete */
+            htab_remove_u32_u32(&h2.h, &key);
+            h2_raw[key] = -1;
+        }
+    }
+    for (uint32_t k = 1; k <= 500; k++) {
+        uint32_t raw = h2_raw[k];
+        uint32_t *hashedp = htab_getp_u32_u32(&h2.h, &k);
+        uint32_t hashed = hashedp ? *hashedp : -1;
+        /* printf("%d %x %x\n", k, raw, hashed); */
+        assert(hashed == raw);
+    }
 }
 
 /*