/*
* Copyright (C) 2012
* Dale Weiler
+ * Wolfgang Bumiller
*
* Permission is hereby granted, free of charge, to any person obtaining a copy of
* this software and associated documentation files (the "Software"), to deal in
void util_meminfo() {
struct memblock_t *info;
- if (!opts_memchk)
+ if (!opts.memchk)
return;
for (info = mem_start; info; info = info->next) {
void util_debug(const char *area, const char *ms, ...) {
va_list va;
- if (!opts_debug)
+ if (!opts.debug)
return;
- if (!strcmp(area, "MEM") && !opts_memchk)
+ if (!strcmp(area, "MEM") && !opts.memchk)
return;
va_start(va, ms);
con_out ("[%s] ", area);
- con_vout(ms, va);
+ con_vout(ms, va);
va_end (va);
}
FILE *util_fopen(const char *filename, const char *mode)
{
-#ifdef WIN32
+#ifdef _MSC_VER
FILE *out;
if (fopen_s(&out, filename, mode) != 0)
return NULL;
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__
+static GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, size_t seed) {
+ const uint64_t mix = 0xC6A4A7935BD1E995UL;
+ 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;
+ }
-size_t _util_hthash(hash_table_t *ht, const char *key) {
- uint64_t val = 0;
- size_t len = strlen(key);
- size_t itr = 0;
-
-
- while (val < ((uint64_t)~1) /* MAX SIZE OF UINT64 */ && itr < len) {
- val = val << 8;
- val += key[itr];
-
- itr++;
+ 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;
}
-
- return val % ht->size;
+
+ hash ^= hash >> rot;
+ hash *= mix;
+ hash ^= hash >> rot;
+
+ return (uint32_t)(hash % ht->size);
+}
+
+#else
+static GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, 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;
}
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_htset(hash_table_t *ht, const char *key, void *value) {
- size_t bin = 0;
+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;
-
- bin = _util_hthash(ht, key);
+
next = ht->table[bin];
-
- while (next && next->key && strcmp(key, next->key))
+
+ 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)) {
+ if (next && next->key && strcmp(key, next->key) == 0) {
next->value = value;
} else {
/* not found, grow a pair man :P */
}
}
-void *util_htget(hash_table_t *ht, const char *key) {
- size_t bin = _util_hthash(ht, key);
+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.
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);
}
-
+
}
/* free table */
mem_d(ht->table);
projects / xonotic / gmqcc.git / blobdiff