Sat, 11 Nov 2017 12:22:16 +0100
UiInteger uses int64 now
0 | 1 | /* |
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | |
3 | * | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
4 | * Copyright 2015 Olaf Wintermann. All rights reserved. |
0 | 5 | * |
6 | * Redistribution and use in source and binary forms, with or without | |
7 | * modification, are permitted provided that the following conditions are met: | |
8 | * | |
9 | * 1. Redistributions of source code must retain the above copyright | |
10 | * notice, this list of conditions and the following disclaimer. | |
11 | * | |
12 | * 2. Redistributions in binary form must reproduce the above copyright | |
13 | * notice, this list of conditions and the following disclaimer in the | |
14 | * documentation and/or other materials provided with the distribution. | |
15 | * | |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
26 | * POSSIBILITY OF SUCH DAMAGE. | |
27 | */ | |
28 | ||
29 | #include <stdlib.h> | |
30 | #include <string.h> | |
31 | ||
32 | #include "map.h" | |
33 | ||
34 | UcxMap *ucx_map_new(size_t size) { | |
35 | return ucx_map_new_a(NULL, size); | |
36 | } | |
37 | ||
38 | UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) { | |
39 | if(size == 0) { | |
40 | size = 16; | |
41 | } | |
42 | ||
43 | if(!allocator) { | |
44 | allocator = ucx_default_allocator(); | |
45 | } | |
46 | ||
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
47 | UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap)); |
0 | 48 | if (!map) { |
49 | return NULL; | |
50 | } | |
51 | ||
52 | map->allocator = allocator; | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
53 | map->map = (UcxMapElement**)alcalloc( |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
54 | allocator, size, sizeof(UcxMapElement*)); |
0 | 55 | if(map->map == NULL) { |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
56 | alfree(allocator, map); |
0 | 57 | return NULL; |
58 | } | |
59 | map->size = size; | |
60 | map->count = 0; | |
61 | ||
62 | return map; | |
63 | } | |
64 | ||
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
65 | static void ucx_map_free_elmlist_contents(UcxMap *map) { |
0 | 66 | for (size_t n = 0 ; n < map->size ; n++) { |
67 | UcxMapElement *elem = map->map[n]; | |
68 | if (elem != NULL) { | |
69 | do { | |
70 | UcxMapElement *next = elem->next; | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
71 | alfree(map->allocator, elem->key.data); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
72 | alfree(map->allocator, elem); |
0 | 73 | elem = next; |
74 | } while (elem != NULL); | |
75 | } | |
76 | } | |
77 | } | |
78 | ||
79 | void ucx_map_free(UcxMap *map) { | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
80 | ucx_map_free_elmlist_contents(map); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
81 | alfree(map->allocator, map->map); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
82 | alfree(map->allocator, map); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
83 | } |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
84 | |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
85 | void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
86 | UcxMapIterator iter = ucx_map_iterator(map); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
87 | void *val; |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
88 | UCX_MAP_FOREACH(key, val, iter) { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
89 | destr(val); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
90 | } |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
91 | } |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
92 | |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
93 | void ucx_map_clear(UcxMap *map) { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
94 | if (map->count == 0) { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
95 | return; // nothing to do |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
96 | } |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
97 | ucx_map_free_elmlist_contents(map); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
98 | memset(map->map, 0, map->size*sizeof(UcxMapElement*)); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
99 | map->count = 0; |
0 | 100 | } |
101 | ||
102 | int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, | |
103 | copy_func fnc, void *data) { | |
104 | UcxMapIterator i = ucx_map_iterator(from); | |
105 | void *value; | |
106 | UCX_MAP_FOREACH(key, value, i) { | |
107 | if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { | |
108 | return 1; | |
109 | } | |
110 | } | |
111 | return 0; | |
112 | } | |
113 | ||
114 | UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { | |
115 | size_t bs = (map->count * 5) >> 1; | |
116 | UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); | |
117 | if (!newmap) { | |
118 | return NULL; | |
119 | } | |
120 | ucx_map_copy(map, newmap, fnc, data); | |
121 | return newmap; | |
122 | } | |
123 | ||
124 | int ucx_map_rehash(UcxMap *map) { | |
125 | size_t load = (map->size * 3) >> 2; | |
126 | if (map->count > load) { | |
127 | UcxMap oldmap; | |
128 | oldmap.map = map->map; | |
129 | oldmap.size = map->size; | |
130 | oldmap.count = map->count; | |
131 | oldmap.allocator = map->allocator; | |
132 | ||
133 | map->size = (map->count * 5) >> 1; | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
134 | map->map = (UcxMapElement**)alcalloc( |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
135 | map->allocator, map->size, sizeof(UcxMapElement*)); |
0 | 136 | if (!map->map) { |
137 | *map = oldmap; | |
138 | return 1; | |
139 | } | |
140 | map->count = 0; | |
141 | ucx_map_copy(&oldmap, map, NULL, NULL); | |
142 | ||
143 | /* free the UcxMapElement list of oldmap */ | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
144 | ucx_map_free_elmlist_contents(&oldmap); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
145 | alfree(map->allocator, oldmap.map); |
0 | 146 | } |
147 | return 0; | |
148 | } | |
149 | ||
150 | int ucx_map_put(UcxMap *map, UcxKey key, void *data) { | |
151 | UcxAllocator *allocator = map->allocator; | |
152 | ||
153 | if (key.hash == 0) { | |
154 | key.hash = ucx_hash((char*)key.data, key.len); | |
155 | } | |
156 | ||
157 | size_t slot = key.hash%map->size; | |
158 | UcxMapElement *restrict elm = map->map[slot]; | |
159 | UcxMapElement *restrict prev = NULL; | |
160 | ||
161 | while (elm && elm->key.hash < key.hash) { | |
162 | prev = elm; | |
163 | elm = elm->next; | |
164 | } | |
165 | ||
166 | if (!elm || elm->key.hash != key.hash) { | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
167 | UcxMapElement *e = (UcxMapElement*)almalloc( |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
168 | allocator, sizeof(UcxMapElement)); |
0 | 169 | if (!e) { |
170 | return -1; | |
171 | } | |
172 | e->key.data = NULL; | |
173 | if (prev) { | |
174 | prev->next = e; | |
175 | } else { | |
176 | map->map[slot] = e; | |
177 | } | |
178 | e->next = elm; | |
179 | elm = e; | |
180 | } | |
181 | ||
182 | if (!elm->key.data) { | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
183 | void *kd = almalloc(allocator, key.len); |
0 | 184 | if (!kd) { |
185 | return -1; | |
186 | } | |
187 | memcpy(kd, key.data, key.len); | |
188 | key.data = kd; | |
189 | elm->key = key; | |
190 | map->count++; | |
191 | } | |
192 | elm->data = data; | |
193 | ||
194 | return 0; | |
195 | } | |
196 | ||
197 | void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) { | |
198 | if(key.hash == 0) { | |
199 | key.hash = ucx_hash((char*)key.data, key.len); | |
200 | } | |
201 | ||
202 | size_t slot = key.hash%map->size; | |
203 | UcxMapElement *restrict elm = map->map[slot]; | |
204 | UcxMapElement *restrict pelm = NULL; | |
205 | while (elm && elm->key.hash <= key.hash) { | |
206 | if(elm->key.hash == key.hash) { | |
207 | int n = (key.len > elm->key.len) ? elm->key.len : key.len; | |
208 | if (memcmp(elm->key.data, key.data, n) == 0) { | |
209 | void *data = elm->data; | |
210 | if (remove) { | |
211 | if (pelm) { | |
212 | pelm->next = elm->next; | |
213 | } else { | |
214 | map->map[slot] = elm->next; | |
215 | } | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
216 | alfree(map->allocator, elm->key.data); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
217 | alfree(map->allocator, elm); |
0 | 218 | map->count--; |
219 | } | |
220 | ||
221 | return data; | |
222 | } | |
223 | } | |
224 | pelm = elm; | |
225 | elm = pelm->next; | |
226 | } | |
227 | ||
228 | return NULL; | |
229 | } | |
230 | ||
231 | void *ucx_map_get(UcxMap *map, UcxKey key) { | |
232 | return ucx_map_get_and_remove(map, key, 0); | |
233 | } | |
234 | ||
235 | void *ucx_map_remove(UcxMap *map, UcxKey key) { | |
236 | return ucx_map_get_and_remove(map, key, 1); | |
237 | } | |
238 | ||
239 | UcxKey ucx_key(void *data, size_t len) { | |
240 | UcxKey key; | |
241 | key.data = data; | |
242 | key.len = len; | |
243 | key.hash = ucx_hash((const char*) data, len); | |
244 | return key; | |
245 | } | |
246 | ||
247 | ||
248 | int ucx_hash(const char *data, size_t len) { | |
249 | /* murmur hash 2 */ | |
250 | ||
251 | int m = 0x5bd1e995; | |
252 | int r = 24; | |
253 | ||
254 | int h = 25 ^ len; | |
255 | ||
256 | int i = 0; | |
257 | while (len >= 4) { | |
258 | int k = data[i + 0] & 0xFF; | |
259 | k |= (data[i + 1] & 0xFF) << 8; | |
260 | k |= (data[i + 2] & 0xFF) << 16; | |
261 | k |= (data[i + 3] & 0xFF) << 24; | |
262 | ||
263 | k *= m; | |
264 | k ^= k >> r; | |
265 | k *= m; | |
266 | ||
267 | h *= m; | |
268 | h ^= k; | |
269 | ||
270 | i += 4; | |
271 | len -= 4; | |
272 | } | |
273 | ||
274 | switch (len) { | |
275 | case 3: h ^= (data[i + 2] & 0xFF) << 16; | |
276 | /* no break */ | |
277 | case 2: h ^= (data[i + 1] & 0xFF) << 8; | |
278 | /* no break */ | |
279 | case 1: h ^= (data[i + 0] & 0xFF); h *= m; | |
280 | /* no break */ | |
281 | } | |
282 | ||
283 | h ^= h >> 13; | |
284 | h *= m; | |
285 | h ^= h >> 15; | |
286 | ||
287 | return h; | |
288 | } | |
289 | ||
290 | UcxMapIterator ucx_map_iterator(UcxMap *map) { | |
291 | UcxMapIterator i; | |
292 | i.map = map; | |
293 | i.cur = NULL; | |
294 | i.index = 0; | |
295 | return i; | |
296 | } | |
297 | ||
298 | int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) { | |
299 | UcxMapElement *e = i->cur; | |
300 | ||
301 | if (e) { | |
302 | e = e->next; | |
303 | } else { | |
304 | e = i->map->map[0]; | |
305 | } | |
306 | ||
307 | while (i->index < i->map->size) { | |
308 | if (e) { | |
309 | if (e->data) { | |
310 | i->cur = e; | |
311 | *elm = e->data; | |
312 | *key = e->key; | |
313 | return 1; | |
314 | } | |
315 | ||
316 | e = e->next; | |
317 | } else { | |
318 | i->index++; | |
319 | ||
320 | if (i->index < i->map->size) { | |
321 | e = i->map->map[i->index]; | |
322 | } | |
323 | } | |
324 | } | |
325 | ||
326 | return 0; | |
327 | } | |
328 |