tests: xor peephole optimization regression test
[xonotic/gmqcc.git] / 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 }