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