X-Git-Url: https://git.xonotic.org/?a=blobdiff_plain;f=util.c;h=aac66aa572ec1142f8f9e8ba0be94b284f0cfb35;hb=d72cb42b0883b7f382d9bd1240e78cab34ab14ca;hp=078f3046f0fb5f183a9b0a1b9c73cbe28f0c9e0d;hpb=9e3399df197c7cea44028a86c961a14df6e62d20;p=xonotic%2Fgmqcc.git diff --git a/util.c b/util.c index 078f304..aac66aa 100644 --- a/util.c +++ b/util.c @@ -1,6 +1,7 @@ /* * 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 @@ -134,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) { @@ -245,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); } @@ -477,47 +478,24 @@ int util_getline(char **lineptr, size_t *n, FILE *stream) { size_t util_strtocmd(const char *in, char *out, size_t outsz) { size_t sz = 1; - for (; *in && sz < outsz; ++in, ++out, ++sz) { - if (*in == '-') - *out = '_'; - else if (isalpha(*in) && !isupper(*in)) - *out = *in + 'A' - 'a'; - else - *out = *in; - } + for (; *in && sz < outsz; ++in, ++out, ++sz) + *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in; *out = 0; return sz-1; } size_t util_strtononcmd(const char *in, char *out, size_t outsz) { size_t sz = 1; - for (; *in && sz < outsz; ++in, ++out, ++sz) { - if (*in == '_') - *out = '-'; - else if (isalpha(*in) && isupper(*in)) - *out = *in + 'a' - 'A'; - else - *out = *in; - - *out = (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in; - } + for (; *in && sz < outsz; ++in, ++out, ++sz) + *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in; *out = 0; return sz-1; } -bool util_filexists(const char *file) { - FILE *fp = fopen(file, "rb"); - if (!fp) return false; - - /* it exists */ - fclose(fp); - return true; -} - 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; @@ -542,49 +520,123 @@ void _util_vec_grow(void **a, size_t i, size_t s) { * EXPOSED INTERFACE comment below */ typedef struct hash_node_t { - char *key; /* the key for this node in table */ - void *value; /* allocated memory storing data */ - size_t size; /* size of data */ - struct hash_node_t *next; /* next node (linked list) */ + 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, 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; -size_t _util_hthash(hash_table_t *ht, const char *key) { - uint64_t val; - 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++; + return (uint32_t)(hash % ht->size); +} + +#else +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; } - - return val % ht->size; + + 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, size_t size) { +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; } - - if (!(node->value = mem_a(size))) { - mem_d(node->key); - mem_d(node); - return NULL; - } - - memcpy(node->value, value, size); - node->size = size; - node->next = NULL; - + + node->value = value; + node->next = NULL; + return node; } @@ -599,42 +651,37 @@ 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 size) { - 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)) { - mem_d(next->value); - next->value = mem_a(size); - next->size = size; - memcpy(next->value, value, size); + 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, size); + newnode = _util_htnewpair(key, value); if (next == ht->table[bin]) { newnode->next = next; ht->table[bin] = newnode; @@ -647,19 +694,26 @@ void util_htset(hash_table_t *ht, const char *key, void *value, size_t size) { } } -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. @@ -668,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); - if (n->value) mem_d(n->value); + if (n->key) + mem_d(n->key); + p = n; n = n->next; + mem_d(p); } - + } /* free table */ mem_d(ht->table);