From 985b1043b6285031cee976f5eeb8512a07e7acbb Mon Sep 17 00:00:00 2001
From: comex
Date: Sun, 12 Jul 2015 23:00:57 -0400
Subject: don't be n^2 for removal, lol.  i should probably switch to rust's
 robin hood hashing - it isn't that much code and supposedly performs much
 better when the table gets full.  *however*, it requires checking the hash of
 every entry in the chain during insert, which basically means storing it,
 which means more memory usage ... but by allowing fuller tables it could
 decrease memory usage.  but if you have a big table anyway to avoid copying,
 you don't want *extra*... and storing the hash twice in the simple case is so
 dumb feeling.  dunno.

---
 lib/cbit/htab.h | 33 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 21 deletions(-)

diff --git a/lib/cbit/htab.h b/lib/cbit/htab.h
index 7dbbf6b..2b3eeaa 100644
--- a/lib/cbit/htab.h
+++ b/lib/cbit/htab.h
@@ -114,36 +114,27 @@ struct htab_internal {
         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)\
-                cur = hi->base; \
+                cur = (void *) buckets; \
+            cur = (void *) ((char *) cur + 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; \
-                } \
+                /* 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, sizeof(key_ty)); \
+                break; \
             } \
             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; \
+            if (!cf_after_hole) { \
+                memcpy(hole, cur, entry_size); \
+                hole = cur; \
+            } \
         } \
         hi->length--; \
     } \
-- 
cgit v1.2.3