2 * Copyright (C) 2012, 2013, 2014, 2015
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:
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
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
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.
34 char *stat_mem_strdup(const char *src, bool empty) {
42 if ((!empty ? len : true) && (ptr = (char*)mem_a(len + 1))) {
43 memcpy(ptr, src, len);
51 * The reallocate function for resizing vectors.
53 void _util_vec_grow(void **a, size_t i, size_t s) {
54 vector_t *d = vec_meta(*a);
59 m = 2 * d->allocated + i;
60 p = mem_r(d, s * m + sizeof(vector_t));
63 p = mem_a(s * m + sizeof(vector_t));
64 ((vector_t*)p)->used = 0;
72 void _util_vec_delete(void *data, size_t line, const char *file) {
73 mem_d(vec_meta(data));
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
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) */
87 size_t hash(const char *key);
89 size_t util_hthash(hash_table_t *ht, const char *key) {
90 return hash(key) % ht->size;
93 static hash_node_t *_util_htnewpair(const char *key, void *value) {
95 if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
98 if (!(node->key = util_strdupe(key))) {
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
116 hash_table_t *util_htnew(size_t size) {
117 hash_table_t *hashtable = NULL;
122 if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
125 if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
130 hashtable->size = size;
131 memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
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;
141 next = ht->table[bin];
143 while (next && next->key && strcmp(key, next->key) > 0)
144 last = next, next = next->next;
146 /* already in table, do a replace */
147 if (next && next->key && strcmp(key, next->key) == 0) {
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;
156 last->next = newnode;
158 newnode->next = next;
159 last->next = newnode;
164 void util_htset(hash_table_t *ht, const char *key, void *value) {
165 util_htseth(ht, key, util_hthash(ht, key), value);
168 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
169 hash_node_t *pair = ht->table[bin];
171 while (pair && pair->key && strcmp(key, pair->key) > 0)
174 if (!pair || !pair->key || strcmp(key, pair->key) != 0)
180 void *util_htget(hash_table_t *ht, const char *key) {
181 return util_htgeth(ht, key, util_hthash(ht, key));
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) {
190 keylen = strlen(key);
192 pair = ht->table[bin];
193 while (pair && pair->key) {
194 len = strlen(pair->key);
200 cmp = strcmp(key, pair->key);
208 cmp = strcmp(key, pair->key + len - keylen);
210 uintptr_t up = (uintptr_t)pair->value;
220 * Free all allocated data in a hashtable, this is quite the amount
223 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
226 for (; i < ht->size; ++i) {
227 hash_node_t *n = ht->table[i];
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];
251 while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
252 pair = &(*pair)->next;
255 if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
266 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
267 util_htrmh(ht, key, util_hthash(ht, key), cb);
270 void util_htdel(hash_table_t *ht) {
271 util_htrem(ht, NULL);