1 files changed, 258 insertions, 0 deletions
diff --git a/external/hash/ht_hash_function.h b/external/hash/ht_hash_function.h
new file mode 100644
index 0000000..1f65ee5
--- /dev/null
+++ b/external/hash/ht_hash_function.h
@@ -0,0 +1,258 @@
+#ifndef HT_HASH_FUNCTION_H
+#define HT_HASH_FUNCTION_H
+
+#include <stddef.h>
+
+#ifdef _MSC_VER
+/* `inline` only advisory anyway. */
+#pragma warning(disable: 4710) /* function not inlined */
+#endif
+
+/* Avoid 0 special case in hash functions and allow for configuration with unguessable seed. */
+#ifndef HT_HASH_SEED
+#define HT_HASH_SEED UINT32_C(0x2f693b52)
+#endif
+
+#ifndef HT_HASH_32
+
+#include "cmetrohash.h"
+
+static inline size_t ht_default_hash_function(const void *key, size_t len)
+{
+    uint64_t out;
+
+    cmetrohash64_1((const uint8_t *)key, len, HT_HASH_SEED, (uint8_t *)&out);
+    return (unsigned int)out;
+}
+
+/* When using the pointer directly as a hash key. */
+static inline size_t ht_ptr_hash_function(const void *key, size_t len)
+{
+    /* MurmurHash3 64-bit finalizer */
+    uint64_t x;
+
+    (void)len;
+
+    x = ((uint64_t)(size_t)key) ^ (HT_HASH_SEED);
+
+    x ^= x >> 33;
+    x *= 0xff51afd7ed558ccdULL;
+    x ^= x >> 33;
+    x *= 0xc4ceb9fe1a85ec53ULL;
+    x ^= x >> 33;
+    return (size_t)x;
+}
+
+#else
+
+#include "PMurHash.h"
+
+static inline size_t ht_default_hash_function(const void *key, size_t len)
+{
+    return (size_t)PMurHash32((HT_HASH_SEED), key, (int)len);
+}
+
+/* When using the pointer directly as a hash key. */
+static inline size_t ht_ptr_hash_function(const void *key, size_t len)
+{
+    /* http://stackoverflow.com/a/12996028 */
+    size_t x;
+
+    x = (size_t)key ^ (HT_HASH_SEED);
+
+    x = ((x >> 16) ^ x) * 0x45d9f3bUL;
+    x = ((x >> 16) ^ x) * 0x45d9f3bUL;
+    x = ((x >> 16) ^ x);
+    return x;
+}
+
+#endif /* HT_HASH_32 */
+
+
+/* This assumes the key points to a 32-bit aligned random value that is its own hash function. */
+static inline size_t ht_uint32_identity_hash_function(const void *key, size_t len)
+{
+    (void)len;
+    return (size_t)*(uint32_t *)key;
+}
+
+/* This assumes the key points to a 64-bit aligned random value that is its own hash function. */
+static inline size_t ht_uint64_identity_hash_function(const void *key, size_t len)
+{
+    (void)len;
+    return (size_t)*(uint64_t *)key;
+}
+
+/* This assumes the key points to a 32-bit aligned value. */
+static inline size_t ht_uint32_hash_function(const void *key, size_t len)
+{
+    uint32_t x = *(uint32_t *)key + (uint32_t)(HT_HASH_SEED);
+
+    (void)len;
+
+    /* http://stackoverflow.com/a/12996028 */
+    x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b);
+    x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b);
+    x = ((x >> 16) ^ x);
+    return x;
+}
+
+/* This assumes the key points to a 64-bit aligned value. */
+static inline size_t ht_uint64_hash_function(const void *key, size_t len)
+{
+    uint64_t x = *(uint64_t *)key + UINT64_C(0x9e3779b97f4a7c15) + (uint64_t)(HT_HASH_SEED);
+
+    (void)len;
+
+    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
+    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
+    return (size_t)(x ^ (x >> 31));
+}
+
+/*
+ * Suited for set operations of low-valued integers where the stored
+ * hash pointer is the key and the value.
+ *
+ * This function is especially useful for small hash tables (<1000)
+ * where collisions are cheap due to caching but also works for integer
+ * sets up to at least 1,000,000.
+ *
+ * NOTE: The multiplicative hash function by Knuth requires the modulo
+ * to table size be done by shifting the upper bits down, since this is
+ * where the quality bits reside. This yields significantly fewer
+ * collisions which is important for e.g. chained hashing. However, our
+ * interface does not provide the required information.
+ *
+ * When used in open hashing with load factors below 0.7 where the
+ * stored pointer is also the key, collision checking is very cheap and
+ * this pays off in a large range of table sizes where a more
+ * complicated hash simply doesn't pay off.
+ * 
+ * When used with a pointer set where the pointer is also the key, it is
+ * not likely to work as well because the pointer acts as a large
+ * integer which works against the design of the hash function. Here a
+ * better mix function is probably worthwhile - therefore we also have
+ * ht_ptr_hash_function.
+ */
+static inline size_t ht_int_hash_function(const void *key, size_t len)
+{
+    (void)len;
+    return ((size_t)key ^ (HT_HASH_SEED)) * 2654435761UL;
+}
+
+/* Bernsteins hash function, assumes string is zero terminated, len is ignored. */
+static inline size_t ht_str_hash_function(const void *key, size_t len)
+{
+    const unsigned char *str = key;
+    size_t hash = 5381 ^ (HT_HASH_SEED);
+    size_t c;
+
+    (void)len;
+
+    while ((c = (size_t)*str++))
+        hash = ((hash << 5) + hash) ^ c; /* (hash * 33) xor c */
+
+    return hash;
+}
+
+/* Hashes at most len characters or until zero termination. */
+static inline size_t ht_strn_hash_function(const void *key, size_t len)
+{
+    const unsigned char *str = key;
+    size_t hash = 5381 ^ (HT_HASH_SEED);
+    size_t c;
+
+    while (--len && (c = (size_t)*str++))
+        hash = ((hash << 5) + hash) ^ c; /* (hash * 33) xor c */
+
+    return hash;
+}
+
+static inline uint32_t ht_fnv1a32_hash_function(const void *key, size_t len)
+{
+#ifndef FNV1A_NOMUL
+    const uint32_t prime = UINT32_C(0x1000193);
+#endif
+    uint32_t hash = UINT32_C(0x811c9dc5);
+    const uint8_t *p = key;
+
+    while (len--) {
+        hash ^= (uint64_t)*p++;
+#ifndef FNV1A_NOMUL
+        hash *= prime;
+#else
+        hash += (hash << 1) + (hash << 4) + (hash << 7) +
+            (hash << 8) + (hash << 24);
+#endif
+    }
+    return hash;
+}
+
+static inline uint64_t ht_fnv1a64_hash_function(const void *key, size_t len)
+{
+#ifndef FNV1A_NOMUL
+    const uint64_t prime = UINT64_C(0x100000001b3);
+#endif
+    uint64_t hash = UINT64_C(0xcbf29ce484222325);
+    const uint8_t *p = key;
+
+    while (len--) {
+        hash ^= (uint64_t)*p++;
+#ifndef FNV1A_NOMUL
+        hash *= prime;
+#else
+        hash += (hash << 1) + (hash << 4) + (hash << 5) +
+		    (hash << 7) + (hash << 8) + (hash << 40);
+#endif
+    }
+    return hash;
+}
+
+/* Hashes until string termination and ignores length argument. */
+static inline uint32_t ht_fnv1a32_str_hash_function(const void *key, size_t len)
+{
+#ifndef FNV1A_NOMUL
+    const uint32_t prime = UINT32_C(0x1000193);
+#endif
+    uint32_t hash = UINT32_C(0x811c9dc5);
+    const uint8_t *p = key;
+
+    (void)len;
+
+    while (*p) {
+        hash ^= (uint64_t)*p++;
+#ifndef FNV1A_NOMUL
+        hash *= prime;
+#else
+        hash += (hash << 1) + (hash << 4) + (hash << 7) +
+            (hash << 8) + (hash << 24);
+#endif
+    }
+    return hash;
+}
+
+/* Hashes until string termination and ignores length argument. */
+static inline uint64_t ht_fnv1a64_str_hash_function(const void *key, size_t len)
+{
+#ifndef FNV1A_NOMUL
+    const uint64_t prime = UINT64_C(0x100000001b3);
+#endif
+    uint64_t hash = UINT64_C(0xcbf29ce484222325);
+    const uint8_t *p = key;
+
+    (void)len;
+
+    while (*p) {
+        hash ^= (uint64_t)*p++;
+#ifndef FNV1A_NOMUL
+        hash *= prime;
+#else
+        hash += (hash << 1) + (hash << 4) + (hash << 5) +
+		    (hash << 7) + (hash << 8) + (hash << 40);
+#endif
+    }
+    return hash;
+}
+
+
+#endif /* HT_HASH_FUNCTION_H */