Thu, 04 Oct 2012 19:46:10 +0200
map counts elements
1 /*
2 *
3 */
5 #include <stdlib.h>
6 #include <string.h>
8 #include "map.h"
10 UcxMap *ucx_map_new(size_t size) {
11 if(size == 0) {
12 size = 16;
13 }
15 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
16 if(map == NULL) {
17 return NULL;
18 }
20 map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*));
21 if(map->map == NULL) {
22 free(map);
23 return NULL;
24 }
25 map->size = size;
26 map->count = 0;
28 return map;
29 }
31 void ucx_map_free(UcxMap *map) {
32 for (size_t n = 0 ; n < map->size ; n++) {
33 UcxMapElement *elem = map->map[n];
34 if (elem != NULL) {
35 do {
36 UcxMapElement *next = elem->next;
37 free(elem->key.data);
38 free(elem);
39 elem = next;
40 } while (elem != NULL);
41 }
42 }
43 free(map->map);
44 free(map);
45 }
47 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {
48 size_t bs = (map->count * 5) >> 2;
49 UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);
50 UcxMapIterator i = ucx_map_iterator(map);
51 void *value;
52 UCX_MAP_FOREACH(value, i) {
53 ucx_map_put(newmap, i.cur->key, fnc ? fnc(value, data) : value);
54 }
55 return newmap;
56 }
58 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
59 if(key.hash == 0) {
60 key.hash = ucx_hash((char*)key.data, key.len);
61 }
63 size_t slot = key.hash%map->size;
64 UcxMapElement *elm = map->map[slot];
65 UcxMapElement *prev = NULL;
67 while (elm != NULL && elm->key.hash < key.hash) {
68 prev = elm;
69 elm = elm->next;
70 }
72 if (elm == NULL || elm->key.hash != key.hash) {
73 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
74 if(e == NULL) {
75 return -1;
76 }
77 e->key.data = NULL;
78 if (prev == NULL) {
79 map->map[slot] = e;
80 } else {
81 prev->next = e;
82 }
83 e->next = elm;
84 elm = e;
85 }
87 if(elm->key.data == NULL) {
88 void *kd = malloc(key.len);
89 if (kd == NULL) {
90 return -1;
91 }
92 memcpy(kd, key.data, key.len);
93 key.data = kd;
94 elm->key = key;
95 map->count++;
96 }
97 elm->data = data;
99 return 0;
100 }
102 void* ucx_map_get(UcxMap *map, UcxKey key) {
103 if(key.hash == 0) {
104 key.hash = ucx_hash((char*)key.data, key.len);
105 }
107 UcxMapElement *elm = map->map[key.hash%map->size];
108 while (elm != NULL && elm->key.hash <= key.hash) {
109 if(elm->key.hash == key.hash) {
110 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
111 if (memcmp(elm->key.data, key.data, n) == 0) {
112 return elm->data;
113 }
114 }
115 elm = elm->next;
116 }
118 return NULL;
119 }
121 UcxKey ucx_key(void *data, size_t len) {
122 UcxKey key;
123 key.data = data;
124 key.len = len;
125 key.hash = ucx_hash(data, len);
126 return key;
127 }
130 int ucx_hash(char *data, size_t len) {
131 /* murmur hash 2 */
133 int m = 0x5bd1e995;
134 int r = 24;
136 int h = 25 ^ len;
138 int i = 0;
139 while (len >= 4) {
140 int k = data[i + 0] & 0xFF;
141 k |= (data[i + 1] & 0xFF) << 8;
142 k |= (data[i + 2] & 0xFF) << 16;
143 k |= (data[i + 3] & 0xFF) << 24;
145 k *= m;
146 k ^= k >> r;
147 k *= m;
149 h *= m;
150 h ^= k;
152 i += 4;
153 len -= 4;
154 }
156 switch (len) {
157 case 3: h ^= (data[i + 2] & 0xFF) << 16;
158 /* no break */
159 case 2: h ^= (data[i + 1] & 0xFF) << 8;
160 /* no break */
161 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
162 /* no break */
163 }
165 h ^= h >> 13;
166 h *= m;
167 h ^= h >> 15;
169 return h;
170 }
172 UcxMapIterator ucx_map_iterator(UcxMap *map) {
173 UcxMapIterator i;
174 i.map = map;
175 i.cur = NULL;
176 i.index = 0;
177 return i;
178 }
180 int ucx_map_iter_next(UcxMapIterator *i, void **elm) {
181 UcxMapElement *e = i->cur;
183 if(e == NULL) {
184 e = i->map->map[0];
185 } else {
186 e = e->next;
187 }
189 while(i->index < i->map->size) {
190 if(e != NULL) {
191 if(e->data != NULL) {
192 i->cur = e;
193 *elm = e->data;
194 return 0;
195 }
197 e = e->next;
198 } else {
199 i->index++;
201 if(i->index < i->map->size) {
202 e = i->map->map[i->index];
203 }
204 }
205 }
207 return 1;
208 }
210 int ucx_map_load(UcxMap *map, FILE *f) {
212 int c; int r, n;
214 char *key, *value;
216 while ((c = fgetc(f)) > 0) {
217 /* Discard leading spaces and comments */
218 if (c < 33) continue;
219 if (c == '#' || c == '!') {
220 while ((c = (char) fgetc(f)) > 0) {
221 if (c == '\n') break;
222 }
223 continue;
224 }
226 /* read into key buffer */
227 n = 16;
228 key = malloc(n);
229 r = 0;
230 do {
231 if (c == '=') break;
232 if (r > n - 2) {
233 n *= 2;
234 key = realloc(key, n);
235 }
236 key[r] = c;
237 r++;
238 } while ((c = fgetc(f)) > 0);
239 if (c <= 0) {
240 free(key);
241 return 1;
242 }
243 key[r] = 0;
244 while (key[--r] == ' ') key[r] = 0;
246 /* skip whitespaces */
247 while ((c = fgetc(f)) > 0) {
248 if (c > 32) break;
249 }
250 if (c <= 0) {
251 free(key);
252 return 1;
253 }
255 /* read into value buffer */
256 n = 64;
257 value = malloc(n);
258 r = 0;
259 do {
260 if (c == '\n') break;
261 if (r > n - 2) {
262 n *= 2;
263 value = realloc(value, n);
264 }
265 value[r] = c;
266 r++;
267 } while ((c = fgetc(f)) > 0);
268 value[r] = 0;
269 while (value[--r] < 33) value[r] = 0;
270 value = realloc(value, r+2);
272 ucx_map_cstr_put(map, key, value);
273 free(key);
274 }
276 return 0;
277 }
279 int ucx_map_store(UcxMap *map, FILE *f) {
280 UcxMapIterator iter = ucx_map_iterator(map);
281 char *k, *v;
282 sstr_t key, value;
283 int written;
285 UCX_MAP_FOREACH(v, iter) {
286 k = (char*) iter.cur->key.data;
287 key = sstr(k); value = sstr(v);
289 written = 0;
290 written += fwrite(key.ptr, 1, key.length, f);
291 written += fwrite(" = ", 1, 3, f);
292 written += fwrite(value.ptr, 1, value.length, f);
293 written += fwrite("\n", 1, 1, f);
295 if (written != key.length + value.length + 4) return 1;
296 }
298 return 0;
299 }