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