X-Git-Url: https://git.xonotic.org/?p=xonotic%2Fgmqcc.git;a=blobdiff_plain;f=util.c;h=73c5335e08e49a3d87929a75351bdfd5d3315ad5;hp=92f8e5e4405c0698d29171826826bf07910fe7ee;hb=b47e3ebccf562b26671247c2e99f4a0f6bc8e969;hpb=f2b21158d801e96b5f8d7c9491186267dc75a4dc diff --git a/util.c b/util.c index 92f8e5e..73c5335 100644 --- a/util.c +++ b/util.c @@ -192,8 +192,8 @@ void util_meminfo() { Total peak memory: %f (MB)\n\ Total leaked memory: %f (MB) in %llu allocations\n", mem_at, - (float)(mem_dt) / 1048576.0f, - mem_ab, + mem_dt, + (float)(mem_ab) / 1048576.0f, (float)(mem_db) / 1048576.0f, (float)(mem_pk) / 1048576.0f, (float)(mem_ab - mem_db) / 1048576.0f, @@ -226,6 +226,25 @@ char *_util_Estrdup(const char *s, const char *file, size_t line) { return ptr; } +char *_util_Estrdup_empty(const char *s, const char *file, size_t line) { + size_t len = 0; + char *ptr = NULL; + + /* in case of -DNOTRACK */ + (void)file; + (void)line; + + if (!s) + return NULL; + + len = strlen(s); + if ((ptr = (char*)mem_af(len+1, line, file))) { + memcpy(ptr, s, len); + ptr[len] = '\0'; + } + return ptr; +} + void util_debug(const char *area, const char *ms, ...) { va_list va; if (!OPTS_OPTION_BOOL(OPTION_DEBUG)) @@ -478,7 +497,7 @@ hash_node_t *_util_htnewpair(const char *key, void *value) { if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t)))) return NULL; - if (!(node->key = util_strdup(key))) { + if (!(node->key = util_strdupe(key))) { mem_d(node); return NULL; } @@ -601,7 +620,7 @@ void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) { * Free all allocated data in a hashtable, this is quite the amount * of work. */ -void util_htdel(hash_table_t *ht) { +void util_htrem(hash_table_t *ht, void (*callback)(void *data)) { size_t i = 0; for (; i < ht->size; i++) { hash_node_t *n = ht->table[i]; @@ -611,6 +630,8 @@ void util_htdel(hash_table_t *ht) { while (n) { if (n->key) mem_d(n->key); + if (callback) + callback(n->value); p = n; n = n->next; mem_d(p); @@ -622,145 +643,32 @@ 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 = (size_t*)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; -} +void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) { + hash_node_t **pair = &ht->table[bin]; + hash_node_t *tmp; -/* 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 (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0) + pair = &(*pair)->next; - while (set->items[iter]) { - if (set->items[iter] == hash) - return 1; + tmp = *pair; + if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0) + return; - iter = set->mask & (iter + GMQCC_HASHSET_PRIME1); - } + if (cb) + (*cb)(tmp->value); - return 0; + *pair = tmp->next; + mem_d(tmp->key); + mem_d(tmp); } -hash_set_t *util_hsnew(void) { - hash_set_t *set; - - if (!(set = (hash_set_t*)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 = (size_t*)mem_a(set->capacity * sizeof(size_t)); - - if (!set->items) { - util_hsdel(set); - return NULL; - } - - return set; +void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) { + util_htrmh(ht, key, util_hthash(ht, key), cb); } -void util_hsdel(hash_set_t *set) { - if (!set) return; - - if (set->items) - mem_d(set->items); - - mem_d(set); +void util_htdel(hash_table_t *ht) { + util_htrem(ht, NULL); } -#undef GMQCC_HASHSET_PRIME0 -#undef GMQCC_HASHSET_PRIME1 - /* * Portable implementation of vasprintf/asprintf. Assumes vsnprintf