+typedef struct hash_node_t {
+ char *key; /* the key for this node in table */
+ void *value; /* pointer to the data as void* */
+ struct hash_node_t *next; /* next node (linked list) */
+} hash_node_t;
+
+/*
+ * x86 and x86_64 optimized murmur hash functions for the hashtable
+ * we have individual implementations for optimal performance.
+ *
+ * Forced inlined as we wrap these up in the actual utility function
+ * below. These should be autovectorized by gcc.
+ */
+#ifdef __x86_64__
+GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, register size_t seed) {
+ const uint64_t mix = 0xC6A4A7935BD1E995;
+ const int rot = 47;
+ size_t size = strlen(key);
+ uint64_t hash = seed ^ (size - mix);
+ uint64_t alias = 0;
+ const uint64_t *beg = (const uint64_t*)key;
+ const uint64_t *end = beg + (size / 8);
+ const unsigned char *final = NULL;
+
+ while (beg != end) {
+ alias = *beg++;
+
+ alias *= mix;
+ alias ^= alias >> rot;
+ alias *= mix;
+
+ hash ^= alias;
+ hash *= mix;
+ }
+
+ final = (const unsigned char *)beg;
+
+ switch (size & 7) {
+ case 7: hash ^= (uint64_t)(final[6]) << 48;
+ case 6: hash ^= (uint64_t)(final[5]) << 40;
+ case 5: hash ^= (uint64_t)(final[4]) << 32;
+ case 4: hash ^= (uint64_t)(final[3]) << 24;
+ case 3: hash ^= (uint64_t)(final[2]) << 16;
+ case 2: hash ^= (uint64_t)(final[1]) << 8;
+ case 1: hash ^= (uint64_t)(final[0]);
+ hash *= mix;
+ }
+
+ hash ^= hash >> rot;
+ hash *= mix;
+ hash ^= hash >> rot;
+
+ return (uint32_t)(hash % ht->size);
+}
+
+#else
+GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, register size_t seed) {
+ const uint32_t mix = 0x5BD1E995;
+ const uint32_t rot = 24;
+ size_t size = strlen(key);
+ uint32_t hash = seed ^ size;
+ uint32_t alias = 0;
+ const unsigned char *data = (const unsigned char*)key;
+
+ while (size >= 4) {
+ alias = *(uint32_t*)data;
+
+ alias *= mix;
+ alias ^= alias >> rot;
+ alias *= mix;
+
+ hash *= mix;
+ hash ^= alias;
+
+ data += 4;
+ size -= 4;
+ }
+
+ switch (size) {
+ case 3: hash ^= data[2] << 16;
+ case 2: hash ^= data[1] << 8;
+ case 1: hash ^= data[0];
+ hash *= mix;
+ }
+
+ hash ^= hash >> 13;
+ hash *= mix;
+ hash ^= hash >> 15;
+
+ return hash % ht->size;
+}
+#endif
+
+/* we use the crc table as seeds for the murmur hash :P */
+size_t util_hthash(hash_table_t *ht, const char *key) {
+ static size_t seed = 0;
+ register size_t hash = util_hthashfunc(ht, key, util_crc32_table[seed]);
+
+ /* reset seed */
+ if (seed >= sizeof(util_crc32_table) / sizeof(*util_crc32_table))
+ seed = 0;
+
+ return hash;
+}
+
+hash_node_t *_util_htnewpair(const char *key, void *value) {
+ hash_node_t *node;
+ if (!(node = mem_a(sizeof(hash_node_t))))
+ return NULL;
+
+ if (!(node->key = util_strdup(key))) {
+ mem_d(node);
+ return NULL;
+ }
+
+ node->value = value;
+ node->next = NULL;
+
+ return node;
+}
+
+/*
+ * EXPOSED INTERFACE for the hashtable implementation
+ * util_htnew(size) -- to make a new hashtable
+ * util_htset(table, key, value, sizeof(value)) -- to set something in the table
+ * util_htget(table, key) -- to get something from the table
+ * util_htdel(table) -- to delete the table
+ */
+hash_table_t *util_htnew(size_t size) {
+ hash_table_t *hashtable = NULL;
+ if (size < 1)
+ return NULL;
+
+ if (!(hashtable = mem_a(sizeof(hash_table_t))))
+ return NULL;
+
+ if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
+ mem_d(hashtable);
+ return NULL;
+ }
+
+ hashtable->size = size;
+ memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
+
+ return hashtable;
+}
+
+void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
+ hash_node_t *newnode = NULL;
+ hash_node_t *next = NULL;
+ hash_node_t *last = NULL;
+
+ next = ht->table[bin];
+
+ while (next && next->key && strcmp(key, next->key) > 0)
+ last = next, next = next->next;
+
+ /* already in table, do a replace */
+ if (next && next->key && strcmp(key, next->key) == 0) {
+ next->value = value;
+ } else {
+ /* not found, grow a pair man :P */
+ newnode = _util_htnewpair(key, value);
+ if (next == ht->table[bin]) {
+ newnode->next = next;
+ ht->table[bin] = newnode;
+ } else if (!next) {
+ last->next = newnode;
+ } else {
+ newnode->next = next;
+ last->next = newnode;
+ }
+ }
+}
+
+void util_htset(hash_table_t *ht, const char *key, void *value) {
+ util_htseth(ht, key, util_hthash(ht, key), value);
+}
+
+void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
+ hash_node_t *pair = ht->table[bin];
+
+ while (pair && pair->key && strcmp(key, pair->key) > 0)
+ pair = pair->next;
+
+ if (!pair || !pair->key || strcmp(key, pair->key) != 0)
+ return NULL;
+
+ return pair->value;
+}
+
+void *util_htget(hash_table_t *ht, const char *key) {
+ return util_htgeth(ht, key, util_hthash(ht, key));
+}
+
+/*
+ * Free all allocated data in a hashtable, this is quite the amount
+ * of work.
+ */
+void util_htdel(hash_table_t *ht) {
+ size_t i = 0;
+ for (; i < ht->size; i++) {
+ hash_node_t *n = ht->table[i];
+ hash_node_t *p;
+
+ /* free in list */
+ while (n) {
+ if (n->key)
+ mem_d(n->key);
+ p = n;
+ n = n->next;
+ mem_d(p);
+ }
+