stat.cpp

   1 #include <string.h>
   2 #include <stdlib.h>
   3
   4 #include "gmqcc.h"
   5
   6 /*
   7  * strdup does it's own malloc, we need to track malloc. We don't want
   8  * to overwrite malloc though, infact, we can't really hook it at all
   9  * without library specific assumptions. So we re implement strdup.
  10  */
  11 char *stat_mem_strdup(const char *src, bool empty) {
  12     size_t len = 0;
  13     char *ptr = nullptr;
  14
  15     if (!src)
  16         return nullptr;
  17
  18     len = strlen(src);
  19     if ((!empty ? len : true) && (ptr = (char*)mem_a(len + 1))) {
  20         memcpy(ptr, src, len);
  21         ptr[len] = '\0';
  22     }
  23
  24     return ptr;
  25 }
  26
  27 /*
  28  * The reallocate function for resizing vectors.
  29  */
  30 void _util_vec_grow(void **a, size_t i, size_t s) {
  31     vector_t *d = vec_meta(*a);
  32     size_t m = 0;
  33     void *p = nullptr;
  34
  35     if (*a) {
  36         m = 2 * d->allocated + i;
  37         p = mem_r(d, s * m + sizeof(vector_t));
  38     } else {
  39         m = i + 1;
  40         p = mem_a(s * m + sizeof(vector_t));
  41         ((vector_t*)p)->used = 0;
  42     }
  43
  44     d = (vector_t*)p;
  45     d->allocated = m;
  46     *a = d + 1;
  47 }
  48
  49 void _util_vec_delete(void *data) {
  50     mem_d(vec_meta(data));
  51 }
  52
  53 /*
  54  * Hash table for generic data, based on dynamic memory allocations
  55  * all around.  This is the internal interface, please look for
  56  * EXPOSED INTERFACE comment below
  57  */
  58 struct hash_node_t {
  59     char *key;   /* the key for this node in table */
  60     void *value; /* pointer to the data as void*   */
  61     hash_node_t *next;  /* next node (linked list)        */
  62 };
  63
  64 size_t hash(const char *key);
  65
  66 size_t util_hthash(hash_table_t *ht, const char *key) {
  67     return hash(key) % ht->size;
  68 }
  69
  70 static hash_node_t *_util_htnewpair(const char *key, void *value) {
  71     hash_node_t *node;
  72     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
  73         return nullptr;
  74
  75     if (!(node->key = util_strdupe(key))) {
  76         mem_d(node);
  77         return nullptr;
  78     }
  79
  80     node->value = value;
  81     node->next  = nullptr;
  82
  83     return node;
  84 }
  85
  86 /*
  87  * EXPOSED INTERFACE for the hashtable implementation
  88  * util_htnew(size)                             -- to make a new hashtable
  89  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
  90  * util_htget(table, key)                       -- to get something from the table
  91  * util_htdel(table)                            -- to delete the table
  92  */
  93 hash_table_t *util_htnew(size_t size) {
  94     hash_table_t *hashtable = nullptr;
  95
  96     if (size < 1)
  97         return nullptr;
  98
  99     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
 100         return nullptr;
 101
 102     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
 103         mem_d(hashtable);
 104         return nullptr;
 105     }
 106
 107     hashtable->size = size;
 108     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 109
 110     return hashtable;
 111 }
 112
 113 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 114     hash_node_t *newnode = nullptr;
 115     hash_node_t *next    = nullptr;
 116     hash_node_t *last    = nullptr;
 117
 118     next = ht->table[bin];
 119
 120     while (next && next->key && strcmp(key, next->key) > 0)
 121         last = next, next = next->next;
 122
 123     /* already in table, do a replace */
 124     if (next && next->key && strcmp(key, next->key) == 0) {
 125         next->value = value;
 126     } else {
 127         /* not found, grow a pair man :P */
 128         newnode = _util_htnewpair(key, value);
 129         if (next == ht->table[bin]) {
 130             newnode->next  = next;
 131             ht->table[bin] = newnode;
 132         } else if (!next) {
 133             last->next = newnode;
 134         } else {
 135             newnode->next = next;
 136             last->next = newnode;
 137         }
 138     }
 139 }
 140
 141 void util_htset(hash_table_t *ht, const char *key, void *value) {
 142     util_htseth(ht, key, util_hthash(ht, key), value);
 143 }
 144
 145 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 146     hash_node_t *pair = ht->table[bin];
 147
 148     while (pair && pair->key && strcmp(key, pair->key) > 0)
 149         pair = pair->next;
 150
 151     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 152         return nullptr;
 153
 154     return pair->value;
 155 }
 156
 157 void *util_htget(hash_table_t *ht, const char *key) {
 158     return util_htgeth(ht, key, util_hthash(ht, key));
 159 }
 160
 161 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin);
 162 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 163     hash_node_t *pair;
 164     size_t len, keylen;
 165     int cmp;
 166
 167     keylen = strlen(key);
 168
 169     pair = ht->table[bin];
 170     while (pair && pair->key) {
 171         len = strlen(pair->key);
 172         if (len < keylen) {
 173             pair = pair->next;
 174             continue;
 175         }
 176         if (keylen == len) {
 177             cmp = strcmp(key, pair->key);
 178             if (cmp == 0)
 179                 return pair->value;
 180             if (cmp < 0)
 181                 return nullptr;
 182             pair = pair->next;
 183             continue;
 184         }
 185         cmp = strcmp(key, pair->key + len - keylen);
 186         if (cmp == 0) {
 187             uintptr_t up = (uintptr_t)pair->value;
 188             up += len - keylen;
 189             return (void*)up;
 190         }
 191         pair = pair->next;
 192     }
 193     return nullptr;
 194 }
 195
 196 /*
 197  * Free all allocated data in a hashtable, this is quite the amount
 198  * of work.
 199  */
 200 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
 201     size_t i = 0;
 202
 203     for (; i < ht->size; ++i) {
 204         hash_node_t *n = ht->table[i];
 205         hash_node_t *p;
 206
 207         /* free in list */
 208         while (n) {
 209             if (n->key)
 210                 mem_d(n->key);
 211             if (callback)
 212                 callback(n->value);
 213             p = n;
 214             n = p->next;
 215             mem_d(p);
 216         }
 217
 218     }
 219     /* free table */
 220     mem_d(ht->table);
 221     mem_d(ht);
 222 }
 223
 224 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
 225     hash_node_t **pair = &ht->table[bin];
 226     hash_node_t *tmp;
 227
 228     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
 229         pair = &(*pair)->next;
 230
 231     tmp = *pair;
 232     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
 233         return;
 234
 235     if (cb)
 236         (*cb)(tmp->value);
 237
 238     *pair = tmp->next;
 239     mem_d(tmp->key);
 240     mem_d(tmp);
 241 }
 242
 243 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
 244     util_htrmh(ht, key, util_hthash(ht, key), cb);
 245 }
 246
 247 void util_htdel(hash_table_t *ht) {
 248     util_htrem(ht, nullptr);
 249 }