Changeset 0db0df2 in mainline for common

Timestamp:

2025-04-07T17:53:53Z (3 months ago)

Author:

Jiří Zárevúcky <zarevucky.jiri@…>

Branches:

master

Children:

45226285, 93de384

Parents:

8f8818ac

git-author:

Jiří Zárevúcky <zarevucky.jiri@…> (2025-04-07 16:41:57)

git-committer:

Jiří Zárevúcky <zarevucky.jiri@…> (2025-04-07 17:53:53)

Message:

Hash table improvements

Implement hash_table_foreach macro, analogous to list_foreach.

Remove superfluous argument to hash_table_find_next().
(If the user needs to recheck the part of the list already
checked by hash_table_find(), they can just rerun that function.)

Add hash argument to hash_table_ops_t::key_equal.
The big change here is that users with big keys can store the hash
value alongside key in their entries, and for the low low cost of
sizeof(size_t) bytes eliminate a bunch of expensive key comparisons.

Also added a hash function for strings and arbitrary data.
Found this one by asking ChatGPT, because the latency of accesses
to my book collection is currently a couple of hours.

+ Some drive-by unused #include removal.

Location:

common

Files:

• adt/hash_table.c (modified) (5 diffs)
• include/adt/hash.h (modified) (1 diff)
• include/adt/hash_table.h (modified) (3 diffs)

common/adt/hash_table.c

@@ -247 +247 @@
         assert(h && h->bucket);
 
-        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
+        size_t hash = h->op->key_hash(key);
+        size_t idx = hash % h->bucket_cnt;
 
         list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
-                /*
-                 * Is this is the item we are looking for? We could have first
-                 * checked if the hashes match but op->key_equal() may very well be
-                 * just as fast as op->hash().
-                 */
-                if (h->op->key_equal(key, cur_link)) {
+                if (h->op->key_equal(key, hash, cur_link))
                         return cur_link;
-                }
         }
 
@@ -265 +260 @@
 /** Find the next item equal to item. */
 ht_link_t *
-hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
+hash_table_find_next(const hash_table_t *h, ht_link_t *item)
 {
         assert(item);
@@ -271 +266 @@
 
         size_t idx = h->op->hash(item) % h->bucket_cnt;
-
-        /* Traverse the circular list until we reach the starting item again. */
-        for (link_t *cur = item->link.next; cur != &first->link;
-            cur = cur->next) {
-                assert(cur);
-
-                if (cur == &h->bucket[idx].head)
-                        continue;
-
+        list_t *list = &h->bucket[idx];
+        link_t *cur = list_next(&item->link, list);
+
+        /* Traverse the list until we reach its end. */
+        for (; cur != NULL; cur = list_next(cur, list)) {
                 ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-                /*
-                 * Is this is the item we are looking for? We could have first
-                 * checked if the hashes match but op->equal() may very well be
-                 * just as fast as op->hash().
-                 */
-                if (h->op->equal(cur_link, item)) {
+
+                if (h->op->equal(cur_link, item))
                         return cur_link;
-                }
         }
 
@@ -309 +295 @@
         assert(!h->apply_ongoing);
 
-        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
+        size_t hash = h->op->key_hash(key);
+        size_t idx = hash % h->bucket_cnt;
 
         size_t removed = 0;
@@ -316 +303 @@
                 ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
 
-                if (h->op->key_equal(key, cur_link)) {
+                if (h->op->key_equal(key, hash, cur_link)) {
                         ++removed;
                         list_remove(cur);

common/include/adt/hash.h

@@ -108 +108 @@
 }
 
+/** Hash a NUL-terminated string.
+ * The algorithm may change in the future, so never use it for hashes
+ * that will be stored to a file or sent over a network.
+ */
+static inline size_t hash_string(const char *str)
+{
+        /* djb2 hash + extra mixing at the end */
+
+        char c;
+        size_t hash = 5381;
+
+        while ((c = *(str++)))
+                hash = (hash << 5) + hash + c;
+
+        return hash_mix(hash);
+}
+
+/** Hash an arbitrarily sized sequence of bytes.
+ * The algorithm may change in the future, so never use it for hashes
+ * that will be stored to a file or sent over a network.
+ */
+static inline size_t hash_bytes(const void *b, size_t len)
+{
+        /* djb2 hash + extra mixing at the end */
+
+        // TODO: work in bigger chunks for faster hashing
+
+        const char *str = b;
+
+        size_t hash = 5381;
+
+        for (size_t i = 0; i < len; i++)
+                hash = (hash << 5) + hash + str[i];
+
+        return hash_mix(hash);
+}
+
 #endif

common/include/adt/hash_table.h

@@ -60 +60 @@
 
         /** Returns true if the key is equal to the item's lookup key. */
-        bool (*key_equal)(const void *key, const ht_link_t *item);
+        bool (*key_equal)(const void *key, size_t hash, const ht_link_t *item);
 
         /** Hash table item removal callback.
@@ -85 +85 @@
         member_to_inst((item), type, member)
 
+#define hash_table_foreach(ht, key, member, itype, iterator) \
+        for (itype *iterator = NULL; \
+            iterator == NULL; iterator = (itype *) INTPTR_MAX) \
+                for (ht_link_t *__link = hash_table_find((ht), (key)); \
+                    __link != NULL && ((iterator = member_to_inst(__link, itype, member))); \
+                        __link = hash_table_find_next((ht), __link))
+
 extern bool hash_table_create(hash_table_t *, size_t, size_t,
     const hash_table_ops_t *);
@@ -96 +103 @@
 extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
 extern ht_link_t *hash_table_find(const hash_table_t *, const void *);
-extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *,
-    ht_link_t *);
+extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
 extern size_t hash_table_remove(hash_table_t *, const void *);
 extern void hash_table_remove_item(hash_table_t *, ht_link_t *);