ucx/map.c@08018864fb91
ucx/map.c
Thu, 28 Feb 2013 08:50:24 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 28 Feb 2013 08:50:24 +0100
- changeset 103
- 08018864fb91
- parent 95
- ecfdc1c4a552
- child 107
- 86b19c98b5fd
- permissions
- -rw-r--r--
added license and copyright notice to all files
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 */
29 #include <stdlib.h>
30 #include <string.h>
32 #include "map.h"
34 UcxMap *ucx_map_new(size_t size) {
35 if(size == 0) {
36 size = 16;
37 }
39 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
40 if(map == NULL) {
41 return NULL;
42 }
44 map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*));
45 if(map->map == NULL) {
46 free(map);
47 return NULL;
48 }
49 map->size = size;
50 map->count = 0;
52 return map;
53 }
55 void ucx_map_free_elmlist(UcxMap *map) {
56 for (size_t n = 0 ; n < map->size ; n++) {
57 UcxMapElement *elem = map->map[n];
58 if (elem != NULL) {
59 do {
60 UcxMapElement *next = elem->next;
61 free(elem->key.data);
62 free(elem);
63 elem = next;
64 } while (elem != NULL);
65 }
66 }
67 free(map->map);
68 }
70 void ucx_map_free(UcxMap *map) {
71 ucx_map_free_elmlist(map);
72 free(map);
73 }
75 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,
76 copy_func fnc, void *data) {
77 UcxMapIterator i = ucx_map_iterator(from);
78 void *value;
79 UCX_MAP_FOREACH(value, i) {
80 int ret = ucx_map_put(to, i.cur->key, fnc ? fnc(value, data) : value);
81 if(ret != 0) {
82 return 1;
83 }
84 }
85 return 0;
86 }
88 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {
89 size_t bs = (map->count * 5) >> 1;
90 UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);
91 if(newmap == NULL) {
92 return NULL;
93 }
94 ucx_map_copy(map, newmap, fnc, data);
95 return newmap;
96 }
98 int ucx_map_rehash(UcxMap *map) {
99 size_t load = (map->size * 3) >> 2;
100 if (map->count > load) {
101 UcxMap oldmap;
102 oldmap.map = map->map;
103 oldmap.size = map->size;
104 oldmap.count = map->count;
106 map->size = (map->count * 5) >> 1;
107 map->map = (UcxMapElement**)calloc(map->size, sizeof(UcxMapElement*));
108 if(map->map == NULL) {
109 *map = oldmap;
110 return 1;
111 }
112 map->count = 0;
113 ucx_map_copy(&oldmap, map, NULL, NULL);
115 /* free the UcxMapElement list of oldmap */
116 ucx_map_free_elmlist(&oldmap);
117 }
118 return 0;
119 }
121 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
122 if(key.hash == 0) {
123 key.hash = ucx_hash((char*)key.data, key.len);
124 }
126 size_t slot = key.hash%map->size;
127 UcxMapElement *restrict elm = map->map[slot];
128 UcxMapElement *restrict prev = NULL;
130 while (elm != NULL && elm->key.hash < key.hash) {
131 prev = elm;
132 elm = elm->next;
133 }
135 if (elm == NULL || elm->key.hash != key.hash) {
136 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
137 if(e == NULL) {
138 return -1;
139 }
140 e->key.data = NULL;
141 if (prev) {
142 prev->next = e;
143 } else {
144 map->map[slot] = e;
145 }
146 e->next = elm;
147 elm = e;
148 }
150 if(elm->key.data == NULL) {
151 void *kd = malloc(key.len);
152 if (kd == NULL) {
153 return -1;
154 }
155 memcpy(kd, key.data, key.len);
156 key.data = kd;
157 elm->key = key;
158 map->count++;
159 }
160 elm->data = data;
162 return 0;
163 }
165 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {
166 if(key.hash == 0) {
167 key.hash = ucx_hash((char*)key.data, key.len);
168 }
170 size_t slot = key.hash%map->size;
171 UcxMapElement *restrict elm = map->map[slot];
172 UcxMapElement *restrict pelm = NULL;
173 while (elm && elm->key.hash <= key.hash) {
174 if(elm->key.hash == key.hash) {
175 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
176 if (memcmp(elm->key.data, key.data, n) == 0) {
177 void *data = elm->data;
178 if (remove) {
179 if (pelm) {
180 pelm->next = elm->next;
181 } else {
182 map->map[slot] = elm->next;
183 }
184 free(elm);
185 map->count--;
186 }
188 return data;
189 }
190 }
191 pelm = elm;
192 elm = pelm->next;
193 }
195 return NULL;
196 }
198 void *ucx_map_get(UcxMap *map, UcxKey key) {
199 return ucx_map_get_and_remove(map, key, 0);
200 }
202 void *ucx_map_remove(UcxMap *map, UcxKey key) {
203 return ucx_map_get_and_remove(map, key, 1);
204 }
206 UcxKey ucx_key(void *data, size_t len) {
207 UcxKey key;
208 key.data = data;
209 key.len = len;
210 key.hash = ucx_hash((const char*) data, len);
211 return key;
212 }
215 int ucx_hash(const char *data, size_t len) {
216 /* murmur hash 2 */
218 int m = 0x5bd1e995;
219 int r = 24;
221 int h = 25 ^ len;
223 int i = 0;
224 while (len >= 4) {
225 int k = data[i + 0] & 0xFF;
226 k |= (data[i + 1] & 0xFF) << 8;
227 k |= (data[i + 2] & 0xFF) << 16;
228 k |= (data[i + 3] & 0xFF) << 24;
230 k *= m;
231 k ^= k >> r;
232 k *= m;
234 h *= m;
235 h ^= k;
237 i += 4;
238 len -= 4;
239 }
241 switch (len) {
242 case 3: h ^= (data[i + 2] & 0xFF) << 16;
243 /* no break */
244 case 2: h ^= (data[i + 1] & 0xFF) << 8;
245 /* no break */
246 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
247 /* no break */
248 }
250 h ^= h >> 13;
251 h *= m;
252 h ^= h >> 15;
254 return h;
255 }
257 UcxMapIterator ucx_map_iterator(UcxMap *map) {
258 UcxMapIterator i;
259 i.map = map;
260 i.cur = NULL;
261 i.index = 0;
262 return i;
263 }
265 int ucx_map_iter_next(UcxMapIterator *i, void **elm) {
266 UcxMapElement *e = i->cur;
268 if(e == NULL) {
269 e = i->map->map[0];
270 } else {
271 e = e->next;
272 }
274 while(i->index < i->map->size) {
275 if(e != NULL) {
276 if(e->data != NULL) {
277 i->cur = e;
278 *elm = e->data;
279 return 0;
280 }
282 e = e->next;
283 } else {
284 i->index++;
286 if(i->index < i->map->size) {
287 e = i->map->map[i->index];
288 }
289 }
290 }
292 return 1;
293 }
295 int ucx_map_load_enc(UcxMap *map, FILE *f, UcxAllocator allocator,
296 ucx_map_coder decoder, void* decdata) {
298 int c; int r, n;
300 char *key, *value;
302 while ((c = fgetc(f)) > 0) {
303 /* Discard leading spaces and comments */
304 if (c < 33) continue;
305 if (c == '#' || c == '!') {
306 while ((c = (char) fgetc(f)) > 0) {
307 if (c == '\n') break;
308 }
309 continue;
310 }
312 /* read into key buffer */
313 n = 16;
314 key = (char*) malloc(n);
315 r = 0;
316 do {
317 if (c == '=') break;
318 if (r > n - 2) {
319 n *= 2;
320 key = (char*) realloc(key, n);
321 }
322 key[r] = c;
323 r++;
324 } while ((c = fgetc(f)) > 0);
325 if (c <= 0) {
326 free(key);
327 return 1;
328 }
329 key[r] = 0;
330 while (key[--r] == ' ') key[r] = 0;
332 /* skip whitespaces */
333 while ((c = fgetc(f)) > 0) {
334 if (c > 32) break;
335 }
336 if (c <= 0) {
337 free(key);
338 return 1;
339 }
341 /* read into value buffer */
342 n = 64;
343 value = (char*) malloc(n);
344 r = 0;
345 do {
346 if (c == '\n') break;
347 if (r > n - 2) {
348 n *= 2;
349 value = (char*) realloc(value, n);
350 }
351 value[r] = c;
352 r++;
353 } while ((c = fgetc(f)) > 0);
354 value[r] = 0;
355 while (value[--r] < 33) value[r] = 0;
357 if (decoder) {
358 size_t decodedSize;
359 void *decoded = decoder(value, decdata, &decodedSize);
360 free(value);
361 value = (char*) decoded;
362 r = decodedSize;
363 } else {
364 r += 2;
365 value = (char*) realloc(value, r);
366 }
368 if (allocator.pool) {
369 void *pooledValue = allocator.malloc(allocator.pool, r);
370 memcpy(pooledValue, value, r);
371 free(value);
372 value = (char*) pooledValue;
373 }
375 ucx_map_cstr_put(map, key, value);
376 free(key);
377 }
379 return 0;
380 }
382 int ucx_map_store_enc(UcxMap *map, FILE *f,
383 ucx_map_coder encoder, void *encdata) {
384 UcxMapIterator iter = ucx_map_iterator(map);
385 char *k, *v;
386 sstr_t key, value;
387 size_t written;
389 UCX_MAP_FOREACH(v, iter) {
390 k = (char*) iter.cur->key.data;
391 key = sstrn(k, iter.cur->key.len);
392 if (encoder) {
393 size_t encodedSize;
394 void *encoded = encoder(v, encdata, &encodedSize);
395 value = sstrn((char*) encoded,encodedSize - 1);
396 } else {
397 value = sstr(v);
398 }
400 written = 0;
401 written += fwrite(key.ptr, 1, key.length, f);
402 written += fwrite(" = ", 1, 3, f);
403 written += fwrite(value.ptr, 1, value.length, f);
404 written += fwrite("\n", 1, 1, f);
406 if (encoder) {
407 free(value.ptr);
408 }
410 if (written != key.length + value.length + 4) return 1;
411 }
413 return 0;
414 }
