X-Git-Url: https://git.xonotic.org/?p=xonotic%2Fgmqcc.git;a=blobdiff_plain;f=util.c;h=3961c74f81d996d3b28e41641fcbc2a3be57b376;hp=5157d1cd1027027e1f6e32cdbad25e30af6cf23a;hb=3e8435783c0112a294588c7ec72fe03559888ed1;hpb=32c928ab6d527199b4404f9789ae8e7a4818e06f diff --git a/util.c b/util.c index 5157d1c..3961c74 100644 --- a/util.c +++ b/util.c @@ -135,7 +135,7 @@ void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file void util_meminfo() { struct memblock_t *info; - if (!opts_memchk) + if (!opts.memchk) return; for (info = mem_start; info; info = info->next) { @@ -246,15 +246,15 @@ bool util_strncmpexact(const char *src, const char *ned, size_t len) { 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); } @@ -495,7 +495,7 @@ size_t util_strtononcmd(const char *in, char *out, size_t outsz) { 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; @@ -525,36 +525,118 @@ typedef struct hash_node_t { 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; } @@ -569,35 +651,33 @@ 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_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 */ @@ -614,19 +694,26 @@ void util_htset(hash_table_t *ht, const char *key, void *value) { } } -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. @@ -635,14 +722,17 @@ 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); } - + } /* free table */ mem_d(ht->table);