comparison: src/map.c
src/map.c
- changeset 251
- fae240d633fc
- parent 250
- b7d1317b138e
- child 253
- e19825a1430a
equal
deleted
inserted
replaced
| 250:b7d1317b138e | 251:fae240d633fc |
|---|---|
| 1 /* | |
| 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | |
| 3 * | |
| 4 * Copyright 2017 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 */ | |
| 28 | |
| 29 #include "ucx/map.h" | |
| 30 | |
| 31 #include <stdlib.h> | |
| 32 #include <string.h> | |
| 33 | |
| 34 UcxMap *ucx_map_new(size_t size) { | |
| 35 return ucx_map_new_a(NULL, size); | |
| 36 } | |
| 37 | |
| 38 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) { | |
| 39 if(size == 0) { | |
| 40 size = 16; | |
| 41 } | |
| 42 | |
| 43 if(!allocator) { | |
| 44 allocator = ucx_default_allocator(); | |
| 45 } | |
| 46 | |
| 47 UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap)); | |
| 48 if (!map) { | |
| 49 return NULL; | |
| 50 } | |
| 51 | |
| 52 map->allocator = allocator; | |
| 53 map->map = (UcxMapElement**)alcalloc( | |
| 54 allocator, size, sizeof(UcxMapElement*)); | |
| 55 if(map->map == NULL) { | |
| 56 alfree(allocator, map); | |
| 57 return NULL; | |
| 58 } | |
| 59 map->size = size; | |
| 60 map->count = 0; | |
| 61 | |
| 62 return map; | |
| 63 } | |
| 64 | |
| 65 static void ucx_map_free_elmlist_contents(UcxMap *map) { | |
| 66 for (size_t n = 0 ; n < map->size ; n++) { | |
| 67 UcxMapElement *elem = map->map[n]; | |
| 68 if (elem != NULL) { | |
| 69 do { | |
| 70 UcxMapElement *next = elem->next; | |
| 71 alfree(map->allocator, elem->key.data); | |
| 72 alfree(map->allocator, elem); | |
| 73 elem = next; | |
| 74 } while (elem != NULL); | |
| 75 } | |
| 76 } | |
| 77 } | |
| 78 | |
| 79 void ucx_map_free(UcxMap *map) { | |
| 80 ucx_map_free_elmlist_contents(map); | |
| 81 alfree(map->allocator, map->map); | |
| 82 alfree(map->allocator, map); | |
| 83 } | |
| 84 | |
| 85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { | |
| 86 UcxMapIterator iter = ucx_map_iterator(map); | |
| 87 void *val; | |
| 88 UCX_MAP_FOREACH(key, val, iter) { | |
| 89 destr(val); | |
| 90 } | |
| 91 } | |
| 92 | |
| 93 void ucx_map_clear(UcxMap *map) { | |
| 94 if (map->count == 0) { | |
| 95 return; // nothing to do | |
| 96 } | |
| 97 ucx_map_free_elmlist_contents(map); | |
| 98 memset(map->map, 0, map->size*sizeof(UcxMapElement*)); | |
| 99 map->count = 0; | |
| 100 } | |
| 101 | |
| 102 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, | |
| 103 copy_func fnc, void *data) { | |
| 104 UcxMapIterator i = ucx_map_iterator(from); | |
| 105 void *value; | |
| 106 UCX_MAP_FOREACH(key, value, i) { | |
| 107 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { | |
| 108 return 1; | |
| 109 } | |
| 110 } | |
| 111 return 0; | |
| 112 } | |
| 113 | |
| 114 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { | |
| 115 size_t bs = (map->count * 5) >> 1; | |
| 116 UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); | |
| 117 if (!newmap) { | |
| 118 return NULL; | |
| 119 } | |
| 120 ucx_map_copy(map, newmap, fnc, data); | |
| 121 return newmap; | |
| 122 } | |
| 123 | |
| 124 int ucx_map_rehash(UcxMap *map) { | |
| 125 size_t load = (map->size * 3) >> 2; | |
| 126 if (map->count > load) { | |
| 127 UcxMap oldmap; | |
| 128 oldmap.map = map->map; | |
| 129 oldmap.size = map->size; | |
| 130 oldmap.count = map->count; | |
| 131 oldmap.allocator = map->allocator; | |
| 132 | |
| 133 map->size = (map->count * 5) >> 1; | |
| 134 map->map = (UcxMapElement**)alcalloc( | |
| 135 map->allocator, map->size, sizeof(UcxMapElement*)); | |
| 136 if (!map->map) { | |
| 137 *map = oldmap; | |
| 138 return 1; | |
| 139 } | |
| 140 map->count = 0; | |
| 141 ucx_map_copy(&oldmap, map, NULL, NULL); | |
| 142 | |
| 143 /* free the UcxMapElement list of oldmap */ | |
| 144 ucx_map_free_elmlist_contents(&oldmap); | |
| 145 alfree(map->allocator, oldmap.map); | |
| 146 } | |
| 147 return 0; | |
| 148 } | |
| 149 | |
| 150 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { | |
| 151 UcxAllocator *allocator = map->allocator; | |
| 152 | |
| 153 if (key.hash == 0) { | |
| 154 key.hash = ucx_hash((char*)key.data, key.len); | |
| 155 } | |
| 156 | |
| 157 size_t slot = key.hash%map->size; | |
| 158 UcxMapElement *restrict elm = map->map[slot]; | |
| 159 UcxMapElement *restrict prev = NULL; | |
| 160 | |
| 161 while (elm && elm->key.hash < key.hash) { | |
| 162 prev = elm; | |
| 163 elm = elm->next; | |
| 164 } | |
| 165 | |
| 166 if (!elm || elm->key.hash != key.hash) { | |
| 167 UcxMapElement *e = (UcxMapElement*)almalloc( | |
| 168 allocator, sizeof(UcxMapElement)); | |
| 169 if (!e) { | |
| 170 return -1; | |
| 171 } | |
| 172 e->key.data = NULL; | |
| 173 if (prev) { | |
| 174 prev->next = e; | |
| 175 } else { | |
| 176 map->map[slot] = e; | |
| 177 } | |
| 178 e->next = elm; | |
| 179 elm = e; | |
| 180 } | |
| 181 | |
| 182 if (!elm->key.data) { | |
| 183 void *kd = almalloc(allocator, key.len); | |
| 184 if (!kd) { | |
| 185 return -1; | |
| 186 } | |
| 187 memcpy(kd, key.data, key.len); | |
| 188 key.data = kd; | |
| 189 elm->key = key; | |
| 190 map->count++; | |
| 191 } | |
| 192 elm->data = data; | |
| 193 | |
| 194 return 0; | |
| 195 } | |
| 196 | |
| 197 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) { | |
| 198 if(key.hash == 0) { | |
| 199 key.hash = ucx_hash((char*)key.data, key.len); | |
| 200 } | |
| 201 | |
| 202 size_t slot = key.hash%map->size; | |
| 203 UcxMapElement *restrict elm = map->map[slot]; | |
| 204 UcxMapElement *restrict pelm = NULL; | |
| 205 while (elm && elm->key.hash <= key.hash) { | |
| 206 if(elm->key.hash == key.hash) { | |
| 207 int n = (key.len > elm->key.len) ? elm->key.len : key.len; | |
| 208 if (memcmp(elm->key.data, key.data, n) == 0) { | |
| 209 void *data = elm->data; | |
| 210 if (remove) { | |
| 211 if (pelm) { | |
| 212 pelm->next = elm->next; | |
| 213 } else { | |
| 214 map->map[slot] = elm->next; | |
| 215 } | |
| 216 alfree(map->allocator, elm->key.data); | |
| 217 alfree(map->allocator, elm); | |
| 218 map->count--; | |
| 219 } | |
| 220 | |
| 221 return data; | |
| 222 } | |
| 223 } | |
| 224 pelm = elm; | |
| 225 elm = pelm->next; | |
| 226 } | |
| 227 | |
| 228 return NULL; | |
| 229 } | |
| 230 | |
| 231 void *ucx_map_get(UcxMap *map, UcxKey key) { | |
| 232 return ucx_map_get_and_remove(map, key, 0); | |
| 233 } | |
| 234 | |
| 235 void *ucx_map_remove(UcxMap *map, UcxKey key) { | |
| 236 return ucx_map_get_and_remove(map, key, 1); | |
| 237 } | |
| 238 | |
| 239 UcxKey ucx_key(void *data, size_t len) { | |
| 240 UcxKey key; | |
| 241 key.data = data; | |
| 242 key.len = len; | |
| 243 key.hash = ucx_hash((const char*) data, len); | |
| 244 return key; | |
| 245 } | |
| 246 | |
| 247 | |
| 248 int ucx_hash(const char *data, size_t len) { | |
| 249 /* murmur hash 2 */ | |
| 250 | |
| 251 int m = 0x5bd1e995; | |
| 252 int r = 24; | |
| 253 | |
| 254 int h = 25 ^ len; | |
| 255 | |
| 256 int i = 0; | |
| 257 while (len >= 4) { | |
| 258 int k = data[i + 0] & 0xFF; | |
| 259 k |= (data[i + 1] & 0xFF) << 8; | |
| 260 k |= (data[i + 2] & 0xFF) << 16; | |
| 261 k |= (data[i + 3] & 0xFF) << 24; | |
| 262 | |
| 263 k *= m; | |
| 264 k ^= k >> r; | |
| 265 k *= m; | |
| 266 | |
| 267 h *= m; | |
| 268 h ^= k; | |
| 269 | |
| 270 i += 4; | |
| 271 len -= 4; | |
| 272 } | |
| 273 | |
| 274 switch (len) { | |
| 275 case 3: h ^= (data[i + 2] & 0xFF) << 16; | |
| 276 /* no break */ | |
| 277 case 2: h ^= (data[i + 1] & 0xFF) << 8; | |
| 278 /* no break */ | |
| 279 case 1: h ^= (data[i + 0] & 0xFF); h *= m; | |
| 280 /* no break */ | |
| 281 } | |
| 282 | |
| 283 h ^= h >> 13; | |
| 284 h *= m; | |
| 285 h ^= h >> 15; | |
| 286 | |
| 287 return h; | |
| 288 } | |
| 289 | |
| 290 UcxMapIterator ucx_map_iterator(UcxMap *map) { | |
| 291 UcxMapIterator i; | |
| 292 i.map = map; | |
| 293 i.cur = NULL; | |
| 294 i.index = 0; | |
| 295 return i; | |
| 296 } | |
| 297 | |
| 298 int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) { | |
| 299 UcxMapElement *e = i->cur; | |
| 300 | |
| 301 if (e) { | |
| 302 e = e->next; | |
| 303 } else { | |
| 304 e = i->map->map[0]; | |
| 305 } | |
| 306 | |
| 307 while (i->index < i->map->size) { | |
| 308 if (e) { | |
| 309 if (e->data) { | |
| 310 i->cur = e; | |
| 311 *elm = e->data; | |
| 312 *key = e->key; | |
| 313 return 1; | |
| 314 } | |
| 315 | |
| 316 e = e->next; | |
| 317 } else { | |
| 318 i->index++; | |
| 319 | |
| 320 if (i->index < i->map->size) { | |
| 321 e = i->map->map[i->index]; | |
| 322 } | |
| 323 } | |
| 324 } | |
| 325 | |
| 326 return 0; | |
| 327 } | |
| 328 |
