1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. |
|
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 "ucx/map.h" |
|
30 |
|
31 #include <stdlib.h> |
|
32 #include <string.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 |
|
47 UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap)); |
|
48 if (!map) { |
|
49 return NULL; |
|
50 } |
|
51 |
|
52 map->allocator = allocator; |
|
53 map->map = (UcxMapElement**)alcalloc( |
|
54 allocator, size, sizeof(UcxMapElement*)); |
|
55 if(map->map == NULL) { |
|
56 alfree(allocator, map); |
|
57 return NULL; |
|
58 } |
|
59 map->size = size; |
|
60 map->count = 0; |
|
61 |
|
62 return map; |
|
63 } |
|
64 |
|
65 static void ucx_map_free_elmlist_contents(UcxMap *map) { |
|
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; |
|
71 alfree(map->allocator, elem->key.data); |
|
72 alfree(map->allocator, elem); |
|
73 elem = next; |
|
74 } while (elem != NULL); |
|
75 } |
|
76 } |
|
77 } |
|
78 |
|
79 void ucx_map_free(UcxMap *map) { |
|
80 ucx_map_free_elmlist_contents(map); |
|
81 alfree(map->allocator, map->map); |
|
82 alfree(map->allocator, map); |
|
83 } |
|
84 |
|
85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { |
|
86 UcxMapIterator iter = ucx_map_iterator(map); |
|
87 void *val; |
|
88 UCX_MAP_FOREACH(key, val, iter) { |
|
89 if (destr) { |
|
90 destr(val); |
|
91 } else { |
|
92 alfree(map->allocator, val); |
|
93 } |
|
94 } |
|
95 } |
|
96 |
|
97 void ucx_map_clear(UcxMap *map) { |
|
98 if (map->count == 0) { |
|
99 return; // nothing to do |
|
100 } |
|
101 ucx_map_free_elmlist_contents(map); |
|
102 memset(map->map, 0, map->size*sizeof(UcxMapElement*)); |
|
103 map->count = 0; |
|
104 } |
|
105 |
|
106 int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data) { |
|
107 UcxMapIterator i = ucx_map_iterator(from); |
|
108 void *value; |
|
109 UCX_MAP_FOREACH(key, value, i) { |
|
110 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { |
|
111 return 1; |
|
112 } |
|
113 } |
|
114 return 0; |
|
115 } |
|
116 |
|
117 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { |
|
118 size_t bs = (map->count * 5) >> 1; |
|
119 UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); |
|
120 if (!newmap) { |
|
121 return NULL; |
|
122 } |
|
123 ucx_map_copy(map, newmap, fnc, data); |
|
124 return newmap; |
|
125 } |
|
126 |
|
127 int ucx_map_rehash(UcxMap *map) { |
|
128 size_t load = (map->size * 3) >> 2; |
|
129 if (map->count > load) { |
|
130 UcxMap oldmap; |
|
131 oldmap.map = map->map; |
|
132 oldmap.size = map->size; |
|
133 oldmap.count = map->count; |
|
134 oldmap.allocator = map->allocator; |
|
135 |
|
136 map->size = (map->count * 5) >> 1; |
|
137 map->map = (UcxMapElement**)alcalloc( |
|
138 map->allocator, map->size, sizeof(UcxMapElement*)); |
|
139 if (!map->map) { |
|
140 *map = oldmap; |
|
141 return 1; |
|
142 } |
|
143 map->count = 0; |
|
144 ucx_map_copy(&oldmap, map, NULL, NULL); |
|
145 |
|
146 /* free the UcxMapElement list of oldmap */ |
|
147 ucx_map_free_elmlist_contents(&oldmap); |
|
148 alfree(map->allocator, oldmap.map); |
|
149 } |
|
150 return 0; |
|
151 } |
|
152 |
|
153 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { |
|
154 UcxAllocator *allocator = map->allocator; |
|
155 |
|
156 if (key.hash == 0) { |
|
157 key.hash = ucx_hash((const char*)key.data, key.len); |
|
158 } |
|
159 |
|
160 struct UcxMapKey mapkey; |
|
161 mapkey.hash = key.hash; |
|
162 |
|
163 size_t slot = mapkey.hash%map->size; |
|
164 UcxMapElement *elm = map->map[slot]; |
|
165 UcxMapElement *prev = NULL; |
|
166 |
|
167 while (elm && elm->key.hash < mapkey.hash) { |
|
168 prev = elm; |
|
169 elm = elm->next; |
|
170 } |
|
171 |
|
172 if (!elm || elm->key.hash != mapkey.hash) { |
|
173 UcxMapElement *e = (UcxMapElement*)almalloc( |
|
174 allocator, sizeof(UcxMapElement)); |
|
175 if (!e) { |
|
176 return -1; |
|
177 } |
|
178 e->key.data = NULL; |
|
179 if (prev) { |
|
180 prev->next = e; |
|
181 } else { |
|
182 map->map[slot] = e; |
|
183 } |
|
184 e->next = elm; |
|
185 elm = e; |
|
186 } |
|
187 |
|
188 if (!elm->key.data) { |
|
189 void *kd = almalloc(allocator, key.len); |
|
190 if (!kd) { |
|
191 return -1; |
|
192 } |
|
193 memcpy(kd, key.data, key.len); |
|
194 mapkey.data = kd; |
|
195 mapkey.len = key.len; |
|
196 elm->key = mapkey; |
|
197 map->count++; |
|
198 } |
|
199 elm->data = data; |
|
200 |
|
201 return 0; |
|
202 } |
|
203 |
|
204 static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) { |
|
205 if(key.hash == 0) { |
|
206 key.hash = ucx_hash((const char*)key.data, key.len); |
|
207 } |
|
208 |
|
209 size_t slot = key.hash%map->size; |
|
210 UcxMapElement *elm = map->map[slot]; |
|
211 UcxMapElement *pelm = NULL; |
|
212 while (elm && elm->key.hash <= key.hash) { |
|
213 if(elm->key.hash == key.hash) { |
|
214 int n = (key.len > elm->key.len) ? elm->key.len : key.len; |
|
215 if (memcmp(elm->key.data, key.data, n) == 0) { |
|
216 void *data = elm->data; |
|
217 if (remove) { |
|
218 if (pelm) { |
|
219 pelm->next = elm->next; |
|
220 } else { |
|
221 map->map[slot] = elm->next; |
|
222 } |
|
223 alfree(map->allocator, elm->key.data); |
|
224 alfree(map->allocator, elm); |
|
225 map->count--; |
|
226 } |
|
227 |
|
228 return data; |
|
229 } |
|
230 } |
|
231 pelm = elm; |
|
232 elm = pelm->next; |
|
233 } |
|
234 |
|
235 return NULL; |
|
236 } |
|
237 |
|
238 void *ucx_map_get(UcxMap *map, UcxKey key) { |
|
239 return ucx_map_get_and_remove(map, key, 0); |
|
240 } |
|
241 |
|
242 void *ucx_map_remove(UcxMap *map, UcxKey key) { |
|
243 return ucx_map_get_and_remove(map, key, 1); |
|
244 } |
|
245 |
|
246 UcxKey ucx_key(const void *data, size_t len) { |
|
247 UcxKey key; |
|
248 key.data = data; |
|
249 key.len = len; |
|
250 key.hash = ucx_hash((const char*)data, len); |
|
251 return key; |
|
252 } |
|
253 |
|
254 |
|
255 int ucx_hash(const char *data, size_t len) { |
|
256 /* murmur hash 2 */ |
|
257 |
|
258 int m = 0x5bd1e995; |
|
259 int r = 24; |
|
260 |
|
261 int h = 25 ^ len; |
|
262 |
|
263 int i = 0; |
|
264 while (len >= 4) { |
|
265 int k = data[i + 0] & 0xFF; |
|
266 k |= (data[i + 1] & 0xFF) << 8; |
|
267 k |= (data[i + 2] & 0xFF) << 16; |
|
268 k |= (data[i + 3] & 0xFF) << 24; |
|
269 |
|
270 k *= m; |
|
271 k ^= k >> r; |
|
272 k *= m; |
|
273 |
|
274 h *= m; |
|
275 h ^= k; |
|
276 |
|
277 i += 4; |
|
278 len -= 4; |
|
279 } |
|
280 |
|
281 switch (len) { |
|
282 case 3: h ^= (data[i + 2] & 0xFF) << 16; |
|
283 /* no break */ |
|
284 case 2: h ^= (data[i + 1] & 0xFF) << 8; |
|
285 /* no break */ |
|
286 case 1: h ^= (data[i + 0] & 0xFF); h *= m; |
|
287 /* no break */ |
|
288 } |
|
289 |
|
290 h ^= h >> 13; |
|
291 h *= m; |
|
292 h ^= h >> 15; |
|
293 |
|
294 return h; |
|
295 } |
|
296 |
|
297 UcxMapIterator ucx_map_iterator(UcxMap *map) { |
|
298 UcxMapIterator i; |
|
299 i.map = map; |
|
300 i.cur = NULL; |
|
301 i.index = 0; |
|
302 return i; |
|
303 } |
|
304 |
|
305 int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) { |
|
306 UcxMapElement *e = i->cur; |
|
307 |
|
308 if (e) { |
|
309 e = e->next; |
|
310 } else { |
|
311 e = i->map->map[0]; |
|
312 } |
|
313 |
|
314 while (i->index < i->map->size) { |
|
315 if (e) { |
|
316 if (e->data) { |
|
317 i->cur = e; |
|
318 *elm = e->data; |
|
319 key->data = e->key.data; |
|
320 key->hash = e->key.hash; |
|
321 key->len = e->key.len; |
|
322 return 1; |
|
323 } |
|
324 |
|
325 e = e->next; |
|
326 } else { |
|
327 i->index++; |
|
328 |
|
329 if (i->index < i->map->size) { |
|
330 e = i->map->map[i->index]; |
|
331 } |
|
332 } |
|
333 } |
|
334 |
|
335 return 0; |
|
336 } |
|
337 |
|