Mercurial > hg > webserver / file comparison

comparison: src/ucx/map.c

src/ucx/map.c

changeset 385
a1f4cb076d2f
parent 260
4779a6fb4fbe
equal deleted inserted replaced
210:21274e5950af 385:a1f4cb076d2f
1 /* 1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 * 3 *
4 * Copyright 2016 Olaf Wintermann. All rights reserved. 4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
5 * 5 *
6 * Redistribution and use in source and binary forms, with or without 6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met: 7 * modification, are permitted provided that the following conditions are met:
8 * 8 *
9 * 1. Redistributions of source code must retain the above copyright 9 * 1. Redistributions of source code must retain the above copyright
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 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 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "ucx/map.h"
30
29 #include <stdlib.h> 31 #include <stdlib.h>
30 #include <string.h> 32 #include <string.h>
31
32 #include "map.h"
33 33
34 UcxMap *ucx_map_new(size_t size) { 34 UcxMap *ucx_map_new(size_t size) {
35 return ucx_map_new_a(NULL, size); 35 return ucx_map_new_a(NULL, size);
36 } 36 }
37 37
84 84
85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { 85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) {
86 UcxMapIterator iter = ucx_map_iterator(map); 86 UcxMapIterator iter = ucx_map_iterator(map);
87 void *val; 87 void *val;
88 UCX_MAP_FOREACH(key, val, iter) { 88 UCX_MAP_FOREACH(key, val, iter) {
89 destr(val); 89 if (destr) {
90 destr(val);
91 } else {
92 alfree(map->allocator, val);
93 }
90 } 94 }
91 } 95 }
92 96
93 void ucx_map_clear(UcxMap *map) { 97 void ucx_map_clear(UcxMap *map) {
94 if (map->count == 0) { 98 if (map->count == 0) {
97 ucx_map_free_elmlist_contents(map); 101 ucx_map_free_elmlist_contents(map);
98 memset(map->map, 0, map->size*sizeof(UcxMapElement*)); 102 memset(map->map, 0, map->size*sizeof(UcxMapElement*));
99 map->count = 0; 103 map->count = 0;
100 } 104 }
101 105
102 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, 106 int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) {
103 copy_func fnc, void *data) {
104 UcxMapIterator i = ucx_map_iterator(from); 107 UcxMapIterator i = ucx_map_iterator(from);
105 void *value; 108 void *value;
106 UCX_MAP_FOREACH(key, value, i) { 109 UCX_MAP_FOREACH(key, value, i) {
107 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { 110 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) {
108 return 1; 111 return 1;
109 } 112 }
110 } 113 }
111 return 0; 114 return 0;
112 } 115 }
113 116
114 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { 117 UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data) {
118 return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data);
119 }
120
121 UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
122 UcxMap const *map, copy_func fnc, void *data) {
115 size_t bs = (map->count * 5) >> 1; 123 size_t bs = (map->count * 5) >> 1;
116 UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); 124 UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size);
117 if (!newmap) { 125 if (!newmap) {
118 return NULL; 126 return NULL;
119 } 127 }
120 ucx_map_copy(map, newmap, fnc, data); 128 ucx_map_copy(map, newmap, fnc, data);
121 return newmap; 129 return newmap;
149 157
150 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { 158 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
151 UcxAllocator *allocator = map->allocator; 159 UcxAllocator *allocator = map->allocator;
152 160
153 if (key.hash == 0) { 161 if (key.hash == 0) {
154 key.hash = ucx_hash((char*)key.data, key.len); 162 key.hash = ucx_hash((const char*)key.data, key.len);
155 } 163 }
156 164
157 size_t slot = key.hash%map->size; 165 struct UcxMapKey mapkey;
158 UcxMapElement *restrict elm = map->map[slot]; 166 mapkey.hash = key.hash;
159 UcxMapElement *restrict prev = NULL; 167
160 168 size_t slot = mapkey.hash%map->size;
161 while (elm && elm->key.hash < key.hash) { 169 UcxMapElement *elm = map->map[slot];
170 UcxMapElement *prev = NULL;
171
172 while (elm && elm->key.hash < mapkey.hash) {
162 prev = elm; 173 prev = elm;
163 elm = elm->next; 174 elm = elm->next;
164 } 175 }
165 176
166 if (!elm || elm->key.hash != key.hash) { 177 if (!elm || elm->key.hash != mapkey.hash) {
167 UcxMapElement *e = (UcxMapElement*)almalloc( 178 UcxMapElement *e = (UcxMapElement*)almalloc(
168 allocator, sizeof(UcxMapElement)); 179 allocator, sizeof(UcxMapElement));
169 if (!e) { 180 if (!e) {
170 return -1; 181 return -1;
171 } 182 }
183 void *kd = almalloc(allocator, key.len); 194 void *kd = almalloc(allocator, key.len);
184 if (!kd) { 195 if (!kd) {
185 return -1; 196 return -1;
186 } 197 }
187 memcpy(kd, key.data, key.len); 198 memcpy(kd, key.data, key.len);
188 key.data = kd; 199 mapkey.data = kd;
189 elm->key = key; 200 mapkey.len = key.len;
201 elm->key = mapkey;
190 map->count++; 202 map->count++;
191 } 203 }
192 elm->data = data; 204 elm->data = data;
193 205
194 return 0; 206 return 0;
195 } 207 }
196 208
197 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) { 209 static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) {
198 if(key.hash == 0) { 210 if(key.hash == 0) {
199 key.hash = ucx_hash((char*)key.data, key.len); 211 key.hash = ucx_hash((const char*)key.data, key.len);
200 } 212 }
201 213
202 size_t slot = key.hash%map->size; 214 size_t slot = key.hash%map->size;
203 UcxMapElement *restrict elm = map->map[slot]; 215 UcxMapElement *elm = map->map[slot];
204 UcxMapElement *restrict pelm = NULL; 216 UcxMapElement *pelm = NULL;
205 while (elm && elm->key.hash <= key.hash) { 217 while (elm && elm->key.hash <= key.hash) {
206 if(elm->key.hash == key.hash) { 218 if(elm->key.hash == key.hash) {
207 int n = (key.len > elm->key.len) ? elm->key.len : key.len; 219 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
208 if (memcmp(elm->key.data, key.data, n) == 0) { 220 if (memcmp(elm->key.data, key.data, n) == 0) {
209 void *data = elm->data; 221 void *data = elm->data;
226 } 238 }
227 239
228 return NULL; 240 return NULL;
229 } 241 }
230 242
231 void *ucx_map_get(UcxMap *map, UcxKey key) { 243 void *ucx_map_get(UcxMap const *map, UcxKey key) {
232 return ucx_map_get_and_remove(map, key, 0); 244 return ucx_map_get_and_remove((UcxMap *)map, key, 0);
233 } 245 }
234 246
235 void *ucx_map_remove(UcxMap *map, UcxKey key) { 247 void *ucx_map_remove(UcxMap *map, UcxKey key) {
236 return ucx_map_get_and_remove(map, key, 1); 248 return ucx_map_get_and_remove(map, key, 1);
237 } 249 }
238 250
239 UcxKey ucx_key(void *data, size_t len) { 251 UcxKey ucx_key(const void *data, size_t len) {
240 UcxKey key; 252 UcxKey key;
241 key.data = data; 253 key.data = data;
242 key.len = len; 254 key.len = len;
243 key.hash = ucx_hash((const char*) data, len); 255 key.hash = ucx_hash((const char*)data, len);
244 return key; 256 return key;
245 } 257 }
246 258
247 259
248 int ucx_hash(const char *data, size_t len) { 260 int ucx_hash(const char *data, size_t len) {
285 h ^= h >> 15; 297 h ^= h >> 15;
286 298
287 return h; 299 return h;
288 } 300 }
289 301
290 UcxMapIterator ucx_map_iterator(UcxMap *map) { 302 UcxMapIterator ucx_map_iterator(UcxMap const *map) {
291 UcxMapIterator i; 303 UcxMapIterator i;
292 i.map = map; 304 i.map = map;
293 i.cur = NULL; 305 i.cur = NULL;
294 i.index = 0; 306 i.index = 0;
295 return i; 307 return i;
307 while (i->index < i->map->size) { 319 while (i->index < i->map->size) {
308 if (e) { 320 if (e) {
309 if (e->data) { 321 if (e->data) {
310 i->cur = e; 322 i->cur = e;
311 *elm = e->data; 323 *elm = e->data;
312 *key = e->key; 324 key->data = e->key.data;
325 key->hash = e->key.hash;
326 key->len = e->key.len;
313 return 1; 327 return 1;
314 } 328 }
315 329
316 e = e->next; 330 e = e->next;
317 } else { 331 } else {
324 } 338 }
325 339
326 return 0; 340 return 0;
327 } 341 }
328 342
343 UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
344 copy_func cpfnc, void* cpdata) {
345 return ucx_map_union_a(ucx_default_allocator(),
346 first, second, cpfnc, cpdata);
347 }
348
349 UcxMap* ucx_map_union_a(UcxAllocator *allocator,
350 const UcxMap *first, const UcxMap *second,
351 copy_func cpfnc, void* cpdata) {
352 UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata);
353 ucx_map_copy(second, result, cpfnc, cpdata);
354 return result;
355 }
356
357 UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
358 copy_func cpfnc, void* cpdata) {
359 return ucx_map_intersection_a(ucx_default_allocator(),
360 first, second, cpfnc, cpdata);
361 }
362
363 UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
364 const UcxMap *first, const UcxMap *second,
365 copy_func cpfnc, void* cpdata) {
366 UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ?
367 first->size : second->size);
368
369 UcxMapIterator iter = ucx_map_iterator(first);
370 void* value;
371 UCX_MAP_FOREACH(key, value, iter) {
372 if (ucx_map_get(second, key)) {
373 ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
374 }
375 }
376
377 return result;
378 }
379
380 UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
381 copy_func cpfnc, void* cpdata) {
382 return ucx_map_difference_a(ucx_default_allocator(),
383 first, second, cpfnc, cpdata);
384 }
385
386 UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
387 const UcxMap *first, const UcxMap *second,
388 copy_func cpfnc, void* cpdata) {
389
390 UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);
391
392 UcxMapIterator iter = ucx_map_iterator(first);
393 void* value;
394 UCX_MAP_FOREACH(key, value, iter) {
395 if (!ucx_map_get(second, key)) {
396 ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
397 }
398 }
399
400 ucx_map_rehash(result);
401 return result;
402 }

Mercurial Repository: webserver

mercurial