comparison: ucx/map.c
ucx/map.c
- changeset 1
- 1bcaac272cdf
- child 5
- 88625853ae74
equal
deleted
inserted
replaced
| 0:0f94d369bb02 | 1:1bcaac272cdf |
|---|---|
| 1 /* | |
| 2 * | |
| 3 */ | |
| 4 | |
| 5 #include <stdlib.h> | |
| 6 #include <string.h> | |
| 7 | |
| 8 #include "map.h" | |
| 9 | |
| 10 UcxMap *ucx_map_new(size_t size) { | |
| 11 if(size == 0) { | |
| 12 size = 16; | |
| 13 } | |
| 14 | |
| 15 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap)); | |
| 16 if(map == NULL) { | |
| 17 return NULL; | |
| 18 } | |
| 19 | |
| 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; | |
| 27 | |
| 28 return map; | |
| 29 } | |
| 30 | |
| 31 void ucx_map_free_elmlist(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 } | |
| 45 | |
| 46 void ucx_map_free(UcxMap *map) { | |
| 47 ucx_map_free_elmlist(map); | |
| 48 free(map); | |
| 49 } | |
| 50 | |
| 51 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, | |
| 52 copy_func fnc, void *data) { | |
| 53 UcxMapIterator i = ucx_map_iterator(from); | |
| 54 void *value; | |
| 55 UCX_MAP_FOREACH(value, i) { | |
| 56 int ret = ucx_map_put(to, i.cur->key, fnc ? fnc(value, data) : value); | |
| 57 if(ret != 0) { | |
| 58 return 1; | |
| 59 } | |
| 60 } | |
| 61 return 0; | |
| 62 } | |
| 63 | |
| 64 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { | |
| 65 size_t bs = (map->count * 5) >> 1; | |
| 66 UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); | |
| 67 if(newmap == NULL) { | |
| 68 return NULL; | |
| 69 } | |
| 70 ucx_map_copy(map, newmap, fnc, data); | |
| 71 return newmap; | |
| 72 } | |
| 73 | |
| 74 int ucx_map_rehash(UcxMap *map) { | |
| 75 size_t load = (map->size * 3) >> 2; | |
| 76 if (map->count > load) { | |
| 77 UcxMap oldmap; | |
| 78 oldmap.map = map->map; | |
| 79 oldmap.size = map->size; | |
| 80 oldmap.count = map->count; | |
| 81 | |
| 82 map->size = (map->count * 5) >> 1; | |
| 83 map->map = (UcxMapElement**)calloc(map->size, sizeof(UcxMapElement*)); | |
| 84 if(map->map == NULL) { | |
| 85 *map = oldmap; | |
| 86 return 1; | |
| 87 } | |
| 88 map->count = 0; | |
| 89 ucx_map_copy(&oldmap, map, NULL, NULL); | |
| 90 | |
| 91 /* free the UcxMapElement list of oldmap */ | |
| 92 ucx_map_free_elmlist(&oldmap); | |
| 93 } | |
| 94 return 0; | |
| 95 } | |
| 96 | |
| 97 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { | |
| 98 if(key.hash == 0) { | |
| 99 key.hash = ucx_hash((char*)key.data, key.len); | |
| 100 } | |
| 101 | |
| 102 size_t slot = key.hash%map->size; | |
| 103 UcxMapElement *restrict elm = map->map[slot]; | |
| 104 UcxMapElement *restrict prev = NULL; | |
| 105 | |
| 106 while (elm != NULL && elm->key.hash < key.hash) { | |
| 107 prev = elm; | |
| 108 elm = elm->next; | |
| 109 } | |
| 110 | |
| 111 if (elm == NULL || elm->key.hash != key.hash) { | |
| 112 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement)); | |
| 113 if(e == NULL) { | |
| 114 return -1; | |
| 115 } | |
| 116 e->key.data = NULL; | |
| 117 if (prev) { | |
| 118 prev->next = e; | |
| 119 } else { | |
| 120 map->map[slot] = e; | |
| 121 } | |
| 122 e->next = elm; | |
| 123 elm = e; | |
| 124 } | |
| 125 | |
| 126 if(elm->key.data == NULL) { | |
| 127 void *kd = malloc(key.len); | |
| 128 if (kd == NULL) { | |
| 129 return -1; | |
| 130 } | |
| 131 memcpy(kd, key.data, key.len); | |
| 132 key.data = kd; | |
| 133 elm->key = key; | |
| 134 map->count++; | |
| 135 } | |
| 136 elm->data = data; | |
| 137 | |
| 138 return 0; | |
| 139 } | |
| 140 | |
| 141 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) { | |
| 142 if(key.hash == 0) { | |
| 143 key.hash = ucx_hash((char*)key.data, key.len); | |
| 144 } | |
| 145 | |
| 146 size_t slot = key.hash%map->size; | |
| 147 UcxMapElement *restrict elm = map->map[slot]; | |
| 148 UcxMapElement *restrict pelm = NULL; | |
| 149 while (elm && elm->key.hash <= key.hash) { | |
| 150 if(elm->key.hash == key.hash) { | |
| 151 int n = (key.len > elm->key.len) ? elm->key.len : key.len; | |
| 152 if (memcmp(elm->key.data, key.data, n) == 0) { | |
| 153 void *data = elm->data; | |
| 154 if (remove) { | |
| 155 if (pelm) { | |
| 156 pelm->next = elm->next; | |
| 157 } else { | |
| 158 map->map[slot] = elm->next; | |
| 159 } | |
| 160 free(elm); | |
| 161 map->count--; | |
| 162 } | |
| 163 | |
| 164 return data; | |
| 165 } | |
| 166 } | |
| 167 pelm = elm; | |
| 168 elm = pelm->next; | |
| 169 } | |
| 170 | |
| 171 return NULL; | |
| 172 } | |
| 173 | |
| 174 void *ucx_map_get(UcxMap *map, UcxKey key) { | |
| 175 return ucx_map_get_and_remove(map, key, 0); | |
| 176 } | |
| 177 | |
| 178 void *ucx_map_remove(UcxMap *map, UcxKey key) { | |
| 179 return ucx_map_get_and_remove(map, key, 1); | |
| 180 } | |
| 181 | |
| 182 UcxKey ucx_key(void *data, size_t len) { | |
| 183 UcxKey key; | |
| 184 key.data = data; | |
| 185 key.len = len; | |
| 186 key.hash = ucx_hash((const char*) data, len); | |
| 187 return key; | |
| 188 } | |
| 189 | |
| 190 | |
| 191 int ucx_hash(const char *data, size_t len) { | |
| 192 /* murmur hash 2 */ | |
| 193 | |
| 194 int m = 0x5bd1e995; | |
| 195 int r = 24; | |
| 196 | |
| 197 int h = 25 ^ len; | |
| 198 | |
| 199 int i = 0; | |
| 200 while (len >= 4) { | |
| 201 int k = data[i + 0] & 0xFF; | |
| 202 k |= (data[i + 1] & 0xFF) << 8; | |
| 203 k |= (data[i + 2] & 0xFF) << 16; | |
| 204 k |= (data[i + 3] & 0xFF) << 24; | |
| 205 | |
| 206 k *= m; | |
| 207 k ^= k >> r; | |
| 208 k *= m; | |
| 209 | |
| 210 h *= m; | |
| 211 h ^= k; | |
| 212 | |
| 213 i += 4; | |
| 214 len -= 4; | |
| 215 } | |
| 216 | |
| 217 switch (len) { | |
| 218 case 3: h ^= (data[i + 2] & 0xFF) << 16; | |
| 219 /* no break */ | |
| 220 case 2: h ^= (data[i + 1] & 0xFF) << 8; | |
| 221 /* no break */ | |
| 222 case 1: h ^= (data[i + 0] & 0xFF); h *= m; | |
| 223 /* no break */ | |
| 224 } | |
| 225 | |
| 226 h ^= h >> 13; | |
| 227 h *= m; | |
| 228 h ^= h >> 15; | |
| 229 | |
| 230 return h; | |
| 231 } | |
| 232 | |
| 233 UcxMapIterator ucx_map_iterator(UcxMap *map) { | |
| 234 UcxMapIterator i; | |
| 235 i.map = map; | |
| 236 i.cur = NULL; | |
| 237 i.index = 0; | |
| 238 return i; | |
| 239 } | |
| 240 | |
| 241 int ucx_map_iter_next(UcxMapIterator *i, void **elm) { | |
| 242 UcxMapElement *e = i->cur; | |
| 243 | |
| 244 if(e == NULL) { | |
| 245 e = i->map->map[0]; | |
| 246 } else { | |
| 247 e = e->next; | |
| 248 } | |
| 249 | |
| 250 while(i->index < i->map->size) { | |
| 251 if(e != NULL) { | |
| 252 if(e->data != NULL) { | |
| 253 i->cur = e; | |
| 254 *elm = e->data; | |
| 255 return 0; | |
| 256 } | |
| 257 | |
| 258 e = e->next; | |
| 259 } else { | |
| 260 i->index++; | |
| 261 | |
| 262 if(i->index < i->map->size) { | |
| 263 e = i->map->map[i->index]; | |
| 264 } | |
| 265 } | |
| 266 } | |
| 267 | |
| 268 return 1; | |
| 269 } | |
| 270 | |
| 271 int ucx_map_load_enc(UcxMap *map, FILE *f, UcxAllocator allocator, | |
| 272 ucx_map_coder decoder, void* decdata) { | |
| 273 | |
| 274 int c; int r, n; | |
| 275 | |
| 276 char *key, *value; | |
| 277 | |
| 278 while ((c = fgetc(f)) > 0) { | |
| 279 /* Discard leading spaces and comments */ | |
| 280 if (c < 33) continue; | |
| 281 if (c == '#' || c == '!') { | |
| 282 while ((c = (char) fgetc(f)) > 0) { | |
| 283 if (c == '\n') break; | |
| 284 } | |
| 285 continue; | |
| 286 } | |
| 287 | |
| 288 /* read into key buffer */ | |
| 289 n = 16; | |
| 290 key = (char*) malloc(n); | |
| 291 r = 0; | |
| 292 do { | |
| 293 if (c == '=') break; | |
| 294 if (r > n - 2) { | |
| 295 n *= 2; | |
| 296 key = (char*) realloc(key, n); | |
| 297 } | |
| 298 key[r] = c; | |
| 299 r++; | |
| 300 } while ((c = fgetc(f)) > 0); | |
| 301 if (c <= 0) { | |
| 302 free(key); | |
| 303 return 1; | |
| 304 } | |
| 305 key[r] = 0; | |
| 306 while (key[--r] == ' ') key[r] = 0; | |
| 307 | |
| 308 /* skip whitespaces */ | |
| 309 while ((c = fgetc(f)) > 0) { | |
| 310 if (c > 32) break; | |
| 311 } | |
| 312 if (c <= 0) { | |
| 313 free(key); | |
| 314 return 1; | |
| 315 } | |
| 316 | |
| 317 /* read into value buffer */ | |
| 318 n = 64; | |
| 319 value = (char*) malloc(n); | |
| 320 r = 0; | |
| 321 do { | |
| 322 if (c == '\n') break; | |
| 323 if (r > n - 2) { | |
| 324 n *= 2; | |
| 325 value = (char*) realloc(value, n); | |
| 326 } | |
| 327 value[r] = c; | |
| 328 r++; | |
| 329 } while ((c = fgetc(f)) > 0); | |
| 330 value[r] = 0; | |
| 331 while (value[--r] < 33) value[r] = 0; | |
| 332 | |
| 333 if (decoder) { | |
| 334 size_t decodedSize; | |
| 335 void *decoded = decoder(value, decdata, &decodedSize); | |
| 336 free(value); | |
| 337 value = (char*) decoded; | |
| 338 r = decodedSize; | |
| 339 } else { | |
| 340 r += 2; | |
| 341 value = (char*) realloc(value, r); | |
| 342 } | |
| 343 | |
| 344 if (allocator.pool) { | |
| 345 void *pooledValue = allocator.malloc(allocator.pool, r); | |
| 346 memcpy(pooledValue, value, r); | |
| 347 free(value); | |
| 348 value = (char*) pooledValue; | |
| 349 } | |
| 350 | |
| 351 ucx_map_cstr_put(map, key, value); | |
| 352 free(key); | |
| 353 } | |
| 354 | |
| 355 return 0; | |
| 356 } | |
| 357 | |
| 358 int ucx_map_store_enc(UcxMap *map, FILE *f, | |
| 359 ucx_map_coder encoder, void *encdata) { | |
| 360 UcxMapIterator iter = ucx_map_iterator(map); | |
| 361 char *k, *v; | |
| 362 sstr_t key, value; | |
| 363 int written; | |
| 364 | |
| 365 UCX_MAP_FOREACH(v, iter) { | |
| 366 k = (char*) iter.cur->key.data; | |
| 367 key = sstr(k); | |
| 368 if (encoder) { | |
| 369 size_t encodedSize; | |
| 370 void *encoded = encoder(v, encdata, &encodedSize); | |
| 371 value = sstrn((char*) encoded,encodedSize - 1); | |
| 372 } else { | |
| 373 value = sstr(v); | |
| 374 } | |
| 375 | |
| 376 written = 0; | |
| 377 written += fwrite(key.ptr, 1, key.length, f); | |
| 378 written += fwrite(" = ", 1, 3, f); | |
| 379 written += fwrite(value.ptr, 1, value.length, f); | |
| 380 written += fwrite("\n", 1, 1, f); | |
| 381 | |
| 382 if (encoder) { | |
| 383 free(value.ptr); | |
| 384 } | |
| 385 | |
| 386 if (written != key.length + value.length + 4) return 1; | |
| 387 } | |
| 388 | |
| 389 return 0; | |
| 390 } |
