Changeset 0db0df2 in mainline for common/include/adt/hash.h

Timestamp:

2025-04-07T17:53:53Z (11 days ago)

Author:

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

Branches:

master

Children:

0c6fc7a, 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.

File:

• common/include/adt/hash.h (modified) (1 diff)

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