stat.c

   1 /*
   2  * Copyright (C) 2012, 2013, 2014, 2015
   3  *     Dale Weiler
   4  *     Wolfgang Bumiller
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   7  * this software and associated documentation files (the "Software"), to deal in
   8  * the Software without restriction, including without limitation the rights to
   9  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  10  * of the Software, and to permit persons to whom the Software is furnished to do
  11  * so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in all
  14  * copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24 #include <string.h>
  25 #include <stdlib.h>
  26
  27 #include "gmqcc.h"
  28
  29 /*
  30  * strdup does it's own malloc, we need to track malloc. We don't want
  31  * to overwrite malloc though, infact, we can't really hook it at all
  32  * without library specific assumptions. So we re implement strdup.
  33  */
  34 char *stat_mem_strdup(const char *src, bool empty) {
  35     size_t len = 0;
  36     char *ptr = NULL;
  37
  38     if (!src)
  39         return NULL;
  40
  41     len = strlen(src);
  42     if ((!empty ? len : true) && (ptr = (char*)mem_a(len + 1))) {
  43         memcpy(ptr, src, len);
  44         ptr[len] = '\0';
  45     }
  46
  47     return ptr;
  48 }
  49
  50 /*
  51  * The reallocate function for resizing vectors.
  52  */
  53 void _util_vec_grow(void **a, size_t i, size_t s) {
  54     vector_t *d = vec_meta(*a);
  55     size_t m = 0;
  56     void *p = NULL;
  57
  58     if (*a) {
  59         m = 2 * d->allocated + i;
  60         p = mem_r(d, s * m + sizeof(vector_t));
  61     } else {
  62         m = i + 1;
  63         p = mem_a(s * m + sizeof(vector_t));
  64         ((vector_t*)p)->used = 0;
  65     }
  66
  67     d = (vector_t*)p;
  68     d->allocated = m;
  69     *a = d + 1;
  70 }
  71
  72 void _util_vec_delete(void *data, size_t line, const char *file) {
  73     mem_d(vec_meta(data));
  74 }
  75
  76 /*
  77  * Hash table for generic data, based on dynamic memory allocations
  78  * all around.  This is the internal interface, please look for
  79  * EXPOSED INTERFACE comment below
  80  */
  81 typedef struct hash_node_t {
  82     char               *key;   /* the key for this node in table */
  83     void               *value; /* pointer to the data as void*   */
  84     struct hash_node_t *next;  /* next node (linked list)        */
  85 } hash_node_t;
  86
  87 size_t hash(const char *key);
  88
  89 size_t util_hthash(hash_table_t *ht, const char *key) {
  90     return hash(key) % ht->size;
  91 }
  92
  93 static hash_node_t *_util_htnewpair(const char *key, void *value) {
  94     hash_node_t *node;
  95     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
  96         return NULL;
  97
  98     if (!(node->key = util_strdupe(key))) {
  99         mem_d(node);
 100         return NULL;
 101     }
 102
 103     node->value = value;
 104     node->next  = NULL;
 105
 106     return node;
 107 }
 108
 109 /*
 110  * EXPOSED INTERFACE for the hashtable implementation
 111  * util_htnew(size)                             -- to make a new hashtable
 112  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 113  * util_htget(table, key)                       -- to get something from the table
 114  * util_htdel(table)                            -- to delete the table
 115  */
 116 hash_table_t *util_htnew(size_t size) {
 117     hash_table_t *hashtable = NULL;
 118
 119     if (size < 1)
 120         return NULL;
 121
 122     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
 123         return NULL;
 124
 125     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
 126         mem_d(hashtable);
 127         return NULL;
 128     }
 129
 130     hashtable->size = size;
 131     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 132
 133     return hashtable;
 134 }
 135
 136 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 137     hash_node_t *newnode = NULL;
 138     hash_node_t *next    = NULL;
 139     hash_node_t *last    = NULL;
 140
 141     next = ht->table[bin];
 142
 143     while (next && next->key && strcmp(key, next->key) > 0)
 144         last = next, next = next->next;
 145
 146     /* already in table, do a replace */
 147     if (next && next->key && strcmp(key, next->key) == 0) {
 148         next->value = value;
 149     } else {
 150         /* not found, grow a pair man :P */
 151         newnode = _util_htnewpair(key, value);
 152         if (next == ht->table[bin]) {
 153             newnode->next  = next;
 154             ht->table[bin] = newnode;
 155         } else if (!next) {
 156             last->next = newnode;
 157         } else {
 158             newnode->next = next;
 159             last->next = newnode;
 160         }
 161     }
 162 }
 163
 164 void util_htset(hash_table_t *ht, const char *key, void *value) {
 165     util_htseth(ht, key, util_hthash(ht, key), value);
 166 }
 167
 168 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 169     hash_node_t *pair = ht->table[bin];
 170
 171     while (pair && pair->key && strcmp(key, pair->key) > 0)
 172         pair = pair->next;
 173
 174     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 175         return NULL;
 176
 177     return pair->value;
 178 }
 179
 180 void *util_htget(hash_table_t *ht, const char *key) {
 181     return util_htgeth(ht, key, util_hthash(ht, key));
 182 }
 183
 184 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin);
 185 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 186     hash_node_t *pair;
 187     size_t len, keylen;
 188     int cmp;
 189
 190     keylen = strlen(key);
 191
 192     pair = ht->table[bin];
 193     while (pair && pair->key) {
 194         len = strlen(pair->key);
 195         if (len < keylen) {
 196             pair = pair->next;
 197             continue;
 198         }
 199         if (keylen == len) {
 200             cmp = strcmp(key, pair->key);
 201             if (cmp == 0)
 202                 return pair->value;
 203             if (cmp < 0)
 204                 return NULL;
 205             pair = pair->next;
 206             continue;
 207         }
 208         cmp = strcmp(key, pair->key + len - keylen);
 209         if (cmp == 0) {
 210             uintptr_t up = (uintptr_t)pair->value;
 211             up += len - keylen;
 212             return (void*)up;
 213         }
 214         pair = pair->next;
 215     }
 216     return NULL;
 217 }
 218
 219 /*
 220  * Free all allocated data in a hashtable, this is quite the amount
 221  * of work.
 222  */
 223 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
 224     size_t i = 0;
 225
 226     for (; i < ht->size; ++i) {
 227         hash_node_t *n = ht->table[i];
 228         hash_node_t *p;
 229
 230         /* free in list */
 231         while (n) {
 232             if (n->key)
 233                 mem_d(n->key);
 234             if (callback)
 235                 callback(n->value);
 236             p = n;
 237             n = p->next;
 238             mem_d(p);
 239         }
 240
 241     }
 242     /* free table */
 243     mem_d(ht->table);
 244     mem_d(ht);
 245 }
 246
 247 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
 248     hash_node_t **pair = &ht->table[bin];
 249     hash_node_t *tmp;
 250
 251     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
 252         pair = &(*pair)->next;
 253
 254     tmp = *pair;
 255     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
 256         return;
 257
 258     if (cb)
 259         (*cb)(tmp->value);
 260
 261     *pair = tmp->next;
 262     mem_d(tmp->key);
 263     mem_d(tmp);
 264 }
 265
 266 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
 267     util_htrmh(ht, key, util_hthash(ht, key), cb);
 268 }
 269
 270 void util_htdel(hash_table_t *ht) {
 271     util_htrem(ht, NULL);
 272 }
 273
 274 void stat_info() {
 275 }
 276 #undef ST_SIZE