ucx/map.c@ff3dd1ee7dee
ucx/map.c
Thu, 04 Oct 2012 16:03:18 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 04 Oct 2012 16:03:18 +0200
- changeset 42
- ff3dd1ee7dee
- parent 38
- 35f67a8ef875
- child 43
- 02f38adea013
- permissions
- -rw-r--r--
(broken-commit) - added load and store functions, tests failing
some evil crash happens when executing the test - remove the strcmp calls in the test case for the store and load function and everything "works"
the error must be somewhere else - maybe something that should not be freed is freed during the test
1 /*
2 *
3 */
5 #include <stdlib.h>
6 #include <string.h>
8 #include "map.h"
10 UcxMap *ucx_map_new(size_t size) {
11 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
12 if(map == NULL) {
13 return NULL;
14 }
16 map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*));
17 if(map->map == NULL) {
18 free(map);
19 return NULL;
20 }
21 map->size = size;
23 return map;
24 }
26 void ucx_map_free(UcxMap *map) {
27 for (size_t n = 0 ; n < map->size ; n++) {
28 UcxMapElement *elem = map->map[n];
29 if (elem != NULL) {
30 do {
31 UcxMapElement *next = elem->next;
32 free(elem->key.data);
33 free(elem);
34 elem = next;
35 } while (elem != NULL);
36 }
37 }
38 free(map->map);
39 free(map);
40 }
42 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
43 if(key.hash == 0) {
44 key.hash = ucx_hash((char*)key.data, key.len);
45 }
47 size_t slot = key.hash%map->size;
48 UcxMapElement *elm = map->map[slot];
49 UcxMapElement *prev = NULL;
51 while (elm != NULL && elm->key.hash < key.hash) {
52 prev = elm;
53 elm = elm->next;
54 }
56 if (elm == NULL || elm->key.hash != key.hash) {
57 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
58 if(e == NULL) {
59 return -1;
60 }
61 e->key.data = NULL;
62 if (prev == NULL) {
63 map->map[slot] = e;
64 } else {
65 prev->next = e;
66 }
67 e->next = elm;
68 elm = e;
69 }
71 if(elm->key.data == NULL) {
72 void *kd = malloc(key.len);
73 if (kd == NULL) {
74 return -1;
75 }
76 memcpy(kd, key.data, key.len);
77 key.data = kd;
78 elm->key = key;
79 }
80 elm->data = data;
82 return 0;
83 }
85 void* ucx_map_get(UcxMap *map, UcxKey key) {
86 if(key.hash == 0) {
87 key.hash = ucx_hash((char*)key.data, key.len);
88 }
90 UcxMapElement *elm = map->map[key.hash%map->size];
91 while (elm != NULL && elm->key.hash <= key.hash) {
92 if(elm->key.hash == key.hash) {
93 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
94 if (memcmp(elm->key.data, key.data, n) == 0) {
95 return elm->data;
96 }
97 }
98 elm = elm->next;
99 }
101 return NULL;
102 }
104 UcxKey ucx_key(void *data, size_t len) {
105 UcxKey key;
106 key.data = data;
107 key.len = len;
108 key.hash = ucx_hash(data, len);
109 return key;
110 }
113 int ucx_hash(char *data, size_t len) {
114 /* murmur hash 2 */
116 int m = 0x5bd1e995;
117 int r = 24;
119 int h = 25 ^ len;
121 int i = 0;
122 while (len >= 4) {
123 int k = data[i + 0] & 0xFF;
124 k |= (data[i + 1] & 0xFF) << 8;
125 k |= (data[i + 2] & 0xFF) << 16;
126 k |= (data[i + 3] & 0xFF) << 24;
128 k *= m;
129 k ^= k >> r;
130 k *= m;
132 h *= m;
133 h ^= k;
135 i += 4;
136 len -= 4;
137 }
139 switch (len) {
140 case 3: h ^= (data[i + 2] & 0xFF) << 16;
141 /* no break */
142 case 2: h ^= (data[i + 1] & 0xFF) << 8;
143 /* no break */
144 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
145 /* no break */
146 }
148 h ^= h >> 13;
149 h *= m;
150 h ^= h >> 15;
152 return h;
153 }
155 UcxMapIterator ucx_map_iterator(UcxMap *map) {
156 UcxMapIterator i;
157 i.map = map;
158 i.cur = NULL;
159 i.index = 0;
160 return i;
161 }
163 int ucx_map_iter_next(UcxMapIterator *i, void **elm) {
164 UcxMapElement *e = i->cur;
166 if(e == NULL) {
167 e = i->map->map[0];
168 } else {
169 e = e->next;
170 }
172 while(i->index < i->map->size) {
173 if(e != NULL) {
174 if(e->data != NULL) {
175 i->cur = e;
176 *elm = e->data;
177 return 0;
178 }
180 e = e->next;
181 } else {
182 i->index++;
184 if(i->index < i->map->size) {
185 e = i->map->map[i->index];
186 }
187 }
188 }
190 return 1;
191 }
193 int ucx_map_load(UcxMap *map, FILE *f) {
195 char c; int r, n;
197 char *key, *value;
199 while ((c = (char) fgetc(f)) > 0) {
200 /* Discard leading spaces and comments */
201 if (c == ' ') continue;
202 if (c == '#' || c == '!') {
203 while ((c = (char) fgetc(f)) > 0) {
204 if (c == '\n') break;
205 }
206 continue;
207 }
209 /* read into key buffer */
210 n = 16;
211 key = malloc(n);
212 r = 0;
213 do {
214 if (c == '=') break;
215 if (r > n - 2) {
216 n *= 2;
217 key = realloc(key, n);
218 }
219 key[r] = c;
220 r++;
221 } while ((c = (char) fgetc(f)) > 0);
222 if (c == 0) {
223 free(key);
224 return 1;
225 }
226 key[r] = 0;
228 /* read into value buffer */
229 n = 64;
230 value = malloc(n);
231 r = 0;
232 while ((c = (char) fgetc(f)) > 0) {
233 if (c == '\n') break;
234 if (r > n - 1) {
235 n *= 2;
236 value = realloc(value, n);
237 }
238 value[r] = c;
239 r++;
240 }
241 value = realloc(value, r+1);
242 value[r] = 0;
244 ucx_map_cstr_put(map, key, value);
245 free(key);
246 }
248 return 0;
249 }
251 int ucx_map_store(UcxMap *map, FILE *f) {
252 UcxMapIterator iter = ucx_map_iterator(map);
253 char *k, *v;
254 sstr_t key, value;
255 int written;
257 UCX_MAP_FOREACH(v, iter) {
258 k = (char*) iter.cur->key.data;
259 key = sstr(k); value = sstr(v);
261 written = 0;
262 written += fwrite(key.ptr, 1, key.length, f);
263 written += fwrite(" = ", 1, 3, f);
264 written += fwrite(value.ptr, 1, value.length, f);
265 written += fwrite("\n", 1, 1, f);
267 if (written != key.length + value.length + 4) return 1;
268 }
270 return 0;
271 }
