X-Git-Url: https://git.xonotic.org/?p=xonotic%2Fgmqcc.git;a=blobdiff_plain;f=util.c;h=5d0d683a0f11f3ac69cd9aa0101d62545c68662e;hp=26803c898276897ed2d1b1abedf075be3d09c98e;hb=686394654fff6ecfc4f6b9a76bec599585d56795;hpb=fa155f8a42a95111099b8c97a6617cb81317ea6c diff --git a/util.c b/util.c index 26803c8..5d0d683 100644 --- a/util.c +++ b/util.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 2012 + * Copyright (C) 2012, 2013 * Dale Weiler * Wolfgang Bumiller * @@ -514,6 +514,40 @@ void *util_htget(hash_table_t *ht, const char *key) { return util_htgeth(ht, key, util_hthash(ht, key)); } +void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) { + hash_node_t *pair; + size_t len, keylen; + int cmp; + + keylen = strlen(key); + + pair = ht->table[bin]; + while (pair && pair->key) { + len = strlen(pair->key); + if (len < keylen) { + pair = pair->next; + continue; + } + if (keylen == len) { + cmp = strcmp(key, pair->key); + if (cmp == 0) + return pair->value; + if (cmp < 0) + return NULL; + pair = pair->next; + continue; + } + cmp = strcmp(key, pair->key + len - keylen); + if (cmp == 0) { + uintptr_t up = (uintptr_t)pair->value; + up += len - keylen; + return (void*)up; + } + pair = pair->next; + } + return NULL; +} + /* * Free all allocated data in a hashtable, this is quite the amount * of work. @@ -539,6 +573,220 @@ void util_htdel(hash_table_t *ht) { mem_d(ht); } +/* + * A basic implementation of a hash-set. Unlike a hashtable, a hash + * set doesn't maintain key-value pairs. It simply maintains a key + * that can be set, removed, and checked for. + * + * See EXPOSED interface comment below + */ +#define GMQCC_HASHSET_PRIME0 0x0049 +#define GMQCC_HASHSET_PRIME1 0x1391 + +static int util_hsput(hash_set_t *set, void *item) { + size_t hash = (size_t)item; /* shouldn't drop the bits */ + size_t iter; + + /* a == 0 || a == 1 */ + if (hash >> 1) + return -1; + + iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash); + + /* while (set->items[iter] != 0 && set->items[iter] != 1) */ + while (!(set->items[iter] >> 1)) { + if (set->items[iter] == hash) + return 0; + + iter = set->mask & (iter + GMQCC_HASHSET_PRIME1); + } + + set->total ++; + set->items[iter] = hash; + + return 1; +} + +static void util_hsupdate(hash_set_t *set) { + size_t *old; + size_t end; + size_t itr; + + /* time to rehash? */ + if ((float)set->total >= (size_t)((double)set->capacity * 0.85)) { + old = set->items; + end = set->capacity; + + set->bits ++; + set->capacity = (size_t)(1 << set->bits); + set->mask = set->capacity - 1; + set->items = mem_a(set->capacity * sizeof(size_t)); + set->total = 0; + + /*assert(set->items);*/ + + /* + * this shouldn't be slow? if so unroll it a little perhaps + * (shouldn't be though) + */ + for (itr = 0; itr < end; itr++) + util_hsput(set, (void*)old[itr]); + + mem_d(old); + } +} + +/* + * EXPOSED interface: all of these functions are exposed to the outside + * for use. The stuff above is static because it's the "internal" mechanics + * for syncronizing the set for updating, and putting data into the set. + */ +int util_hsadd(hash_set_t *set, void *item) { + int run = util_hsput(set, item); /* inlined */ + util_hsupdate(set); + + return run; +} + +/* remove item in set */ +int util_hsrem(hash_set_t *set, void *item) { + size_t hash = (size_t)item; + size_t iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash); + + while (set->items[iter]) { + if (set->items[iter] == hash) { + set->items[iter] = 1; + set->total --; + + return 1; + } + iter = set->mask & (iter + GMQCC_HASHSET_PRIME1); + } + + return 0; +} + +/* check if item is set */ +int util_hshas(hash_set_t *set, void *item) { + size_t hash = (size_t)item; + size_t iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash); + + while (set->items[iter]) { + if (set->items[iter] == hash) + return 1; + + iter = set->mask & (iter + GMQCC_HASHSET_PRIME1); + } + + return 0; +} + +hash_set_t *util_hsnew(void) { + hash_set_t *set; + + if (!(set = mem_a(sizeof(hash_set_t)))) + return NULL; + + set->bits = 3; + set->total = 0; + set->capacity = (size_t)(1 << set->bits); + set->mask = set->capacity - 1; + set->items = mem_a(set->capacity * sizeof(size_t)); + + if (!set->items) { + util_hsdel(set); + return NULL; + } + + return set; +} + +void util_hsdel(hash_set_t *set) { + if (!set) return; + + if (set->items) + mem_d(set->items); + + mem_d(set); +} +#undef GMQCC_HASHSET_PRIME0 +#undef GMQCC_HASHSET_PRIME1 + + +/* + * Portable implementation of vasprintf/asprintf. Assumes vsnprintf + * exists, otherwise compiler error. + * + * TODO: fix for MSVC .... + */ +int util_vasprintf(char **dat, const char *fmt, va_list args) { + int ret; + int len; + char *tmp = NULL; + + /* + * For visuals tido _vsnprintf doesn't tell you the length of a + * formatted string if it overflows. However there is a MSVC + * intrinsic (which is documented wrong) called _vcsprintf which + * will return the required amount to allocate. + */ + #ifdef _MSC_VER + char *str; + if ((len = _vscprintf(fmt, args)) < 0) { + *dat = NULL; + return -1; + } + + tmp = mem_a(len + 1); + if ((ret = _vsnprintf(tmp, len+1, fmt, args)) != len) { + mem_d(tmp); + *dat = NULL; + return -1; + } + *dat = tmp; + return len; + #else + /* + * For everything else we have a decent conformint vsnprintf that + * returns the number of bytes needed. We give it a try though on + * a short buffer, since efficently speaking, it could be nice to + * above a second vsnprintf call. + */ + char buf[128]; + va_list cpy; + va_copy(cpy, args); + len = vsnprintf(buf, sizeof(buf), fmt, cpy); + va_end (cpy); + + if (len < (int)sizeof(buf)) { + *dat = util_strdup(buf); + return len; + } + + /* not large enough ... */ + tmp = mem_a(len + 1); + if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) { + mem_d(tmp); + *dat = NULL; + return -1; + } + + *dat = tmp; + return len; + #endif + /* never reached ... */ + return -1; +} +int util_asprintf(char **ret, const char *fmt, ...) { + va_list args; + int read; + va_start(args, fmt); + read = util_vasprintf(ret, fmt, args); + va_end (args); + + return read; +} + /* * Implementation of the Mersenne twister PRNG (pseudo random numer * generator). Implementation of MT19937. Has a period of 2^19937-1 @@ -595,12 +843,12 @@ static GMQCC_INLINE void mt_generate() { * to [0, MT_SIZE) (634 iterations). */ for (i = 0; i < MT_SPACE; ++i) { - y = (0x800000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]); + y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]); mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1]; i ++; /* loop unroll */ - y = (0x800000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]); + y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]); mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1]; }