X-Git-Url: https://git.xonotic.org/?a=blobdiff_plain;f=util.c;h=6853393e0487f384dfe602d331db5027b345a785;hb=e2602e6b872e292cbbab27ebbe9af6f53732271d;hp=8b54251c76ed447e52c4b15f38b70b7888745c98;hpb=baf69f3725f8eef6a7a34ef4c94264f7daecb9f5;p=xonotic%2Fgmqcc.git diff --git a/util.c b/util.c index 8b54251..6853393 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 @@ -450,16 +451,10 @@ int util_getline(char **lineptr, size_t *n, FILE *stream) { int c = getc(stream); if (chr < 2) { - char *tmp = (char*)mem_a((*n+=(*n>16)?*n:64)); - if (!tmp) - return -1; - - memcpy(tmp, *lineptr, pos - *lineptr); + *n += (*n > 16) ? *n : 64; chr = *n + *lineptr - pos; - if (!(*lineptr = tmp)) { - mem_d (tmp); + if (!(*lineptr = (char*)mem_r(*lineptr,*n))) return -1; - } pos = *n - chr + *lineptr; } @@ -483,32 +478,21 @@ 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; - } + for (; *in && sz < outsz; ++in, ++out, ++sz) + *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in; *out = 0; return sz-1; } + FILE *util_fopen(const char *filename, const char *mode) { #ifdef WIN32 @@ -521,15 +505,6 @@ FILE *util_fopen(const char *filename, const char *mode) #endif } -bool util_filexists(const char *file) { - FILE *fp = fopen(file, "rb"); - if (!fp) return false; - - /* it exists */ - fclose(fp); - return true; -} - void _util_vec_grow(void **a, size_t i, size_t s) { size_t m = *a ? 2*_vec_beg(*a)+i : i+1; void *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2); @@ -538,3 +513,146 @@ void _util_vec_grow(void **a, size_t i, size_t s) { *a = (void*)((size_t*)p + 2); _vec_beg(*a) = m; } + +/* + * Hash table for generic data, based on dynamic memory allocations + * all around. This is the internal interface, please look for + * EXPOSED INTERFACE comment below + */ +typedef struct hash_node_t { + 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; + + +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++; + } + + return val % ht->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; + } + + node->value = value; + node->next = NULL; + + return node; +} + +/* + * EXPOSED INTERFACE for the hashtable implementation + * util_htnew(size) -- to make a new hashtable + * util_htset(table, key, value, sizeof(value)) -- to set something in the table + * util_htget(table, key) -- to get something from the table + * util_htdel(table) -- to delete the table + */ +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_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; + + next = ht->table[bin]; + + 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) == 0) { + next->value = value; + } else { + /* not found, grow a pair man :P */ + newnode = _util_htnewpair(key, value); + if (next == ht->table[bin]) { + newnode->next = next; + ht->table[bin] = newnode; + } else if (!next) { + last->next = newnode; + } else { + newnode->next = next; + last->next = newnode; + } + } +} + +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. + */ +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); + mem_d(ht); +}