1.1 --- a/src/map.c Mon Dec 30 09:54:10 2019 +0100 1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 1.3 @@ -1,402 +0,0 @@ 1.4 -/* 1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 - * 1.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. 1.8 - * 1.9 - * Redistribution and use in source and binary forms, with or without 1.10 - * modification, are permitted provided that the following conditions are met: 1.11 - * 1.12 - * 1. Redistributions of source code must retain the above copyright 1.13 - * notice, this list of conditions and the following disclaimer. 1.14 - * 1.15 - * 2. Redistributions in binary form must reproduce the above copyright 1.16 - * notice, this list of conditions and the following disclaimer in the 1.17 - * documentation and/or other materials provided with the distribution. 1.18 - * 1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 - * POSSIBILITY OF SUCH DAMAGE. 1.30 - */ 1.31 - 1.32 -#include "ucx/map.h" 1.33 - 1.34 -#include <stdlib.h> 1.35 -#include <string.h> 1.36 - 1.37 -UcxMap *ucx_map_new(size_t size) { 1.38 - return ucx_map_new_a(NULL, size); 1.39 -} 1.40 - 1.41 -UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) { 1.42 - if(size == 0) { 1.43 - size = 16; 1.44 - } 1.45 - 1.46 - if(!allocator) { 1.47 - allocator = ucx_default_allocator(); 1.48 - } 1.49 - 1.50 - UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap)); 1.51 - if (!map) { 1.52 - return NULL; 1.53 - } 1.54 - 1.55 - map->allocator = allocator; 1.56 - map->map = (UcxMapElement**)alcalloc( 1.57 - allocator, size, sizeof(UcxMapElement*)); 1.58 - if(map->map == NULL) { 1.59 - alfree(allocator, map); 1.60 - return NULL; 1.61 - } 1.62 - map->size = size; 1.63 - map->count = 0; 1.64 - 1.65 - return map; 1.66 -} 1.67 - 1.68 -static void ucx_map_free_elmlist_contents(UcxMap *map) { 1.69 - for (size_t n = 0 ; n < map->size ; n++) { 1.70 - UcxMapElement *elem = map->map[n]; 1.71 - if (elem != NULL) { 1.72 - do { 1.73 - UcxMapElement *next = elem->next; 1.74 - alfree(map->allocator, elem->key.data); 1.75 - alfree(map->allocator, elem); 1.76 - elem = next; 1.77 - } while (elem != NULL); 1.78 - } 1.79 - } 1.80 -} 1.81 - 1.82 -void ucx_map_free(UcxMap *map) { 1.83 - ucx_map_free_elmlist_contents(map); 1.84 - alfree(map->allocator, map->map); 1.85 - alfree(map->allocator, map); 1.86 -} 1.87 - 1.88 -void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { 1.89 - UcxMapIterator iter = ucx_map_iterator(map); 1.90 - void *val; 1.91 - UCX_MAP_FOREACH(key, val, iter) { 1.92 - if (destr) { 1.93 - destr(val); 1.94 - } else { 1.95 - alfree(map->allocator, val); 1.96 - } 1.97 - } 1.98 -} 1.99 - 1.100 -void ucx_map_clear(UcxMap *map) { 1.101 - if (map->count == 0) { 1.102 - return; // nothing to do 1.103 - } 1.104 - ucx_map_free_elmlist_contents(map); 1.105 - memset(map->map, 0, map->size*sizeof(UcxMapElement*)); 1.106 - map->count = 0; 1.107 -} 1.108 - 1.109 -int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) { 1.110 - UcxMapIterator i = ucx_map_iterator(from); 1.111 - void *value; 1.112 - UCX_MAP_FOREACH(key, value, i) { 1.113 - if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { 1.114 - return 1; 1.115 - } 1.116 - } 1.117 - return 0; 1.118 -} 1.119 - 1.120 -UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data) { 1.121 - return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data); 1.122 -} 1.123 - 1.124 -UcxMap *ucx_map_clone_a(UcxAllocator *allocator, 1.125 - UcxMap const *map, copy_func fnc, void *data) { 1.126 - size_t bs = (map->count * 5) >> 1; 1.127 - UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size); 1.128 - if (!newmap) { 1.129 - return NULL; 1.130 - } 1.131 - ucx_map_copy(map, newmap, fnc, data); 1.132 - return newmap; 1.133 -} 1.134 - 1.135 -int ucx_map_rehash(UcxMap *map) { 1.136 - size_t load = (map->size * 3) >> 2; 1.137 - if (map->count > load) { 1.138 - UcxMap oldmap; 1.139 - oldmap.map = map->map; 1.140 - oldmap.size = map->size; 1.141 - oldmap.count = map->count; 1.142 - oldmap.allocator = map->allocator; 1.143 - 1.144 - map->size = (map->count * 5) >> 1; 1.145 - map->map = (UcxMapElement**)alcalloc( 1.146 - map->allocator, map->size, sizeof(UcxMapElement*)); 1.147 - if (!map->map) { 1.148 - *map = oldmap; 1.149 - return 1; 1.150 - } 1.151 - map->count = 0; 1.152 - ucx_map_copy(&oldmap, map, NULL, NULL); 1.153 - 1.154 - /* free the UcxMapElement list of oldmap */ 1.155 - ucx_map_free_elmlist_contents(&oldmap); 1.156 - alfree(map->allocator, oldmap.map); 1.157 - } 1.158 - return 0; 1.159 -} 1.160 - 1.161 -int ucx_map_put(UcxMap *map, UcxKey key, void *data) { 1.162 - UcxAllocator *allocator = map->allocator; 1.163 - 1.164 - if (key.hash == 0) { 1.165 - key.hash = ucx_hash((const char*)key.data, key.len); 1.166 - } 1.167 - 1.168 - struct UcxMapKey mapkey; 1.169 - mapkey.hash = key.hash; 1.170 - 1.171 - size_t slot = mapkey.hash%map->size; 1.172 - UcxMapElement *elm = map->map[slot]; 1.173 - UcxMapElement *prev = NULL; 1.174 - 1.175 - while (elm && elm->key.hash < mapkey.hash) { 1.176 - prev = elm; 1.177 - elm = elm->next; 1.178 - } 1.179 - 1.180 - if (!elm || elm->key.hash != mapkey.hash) { 1.181 - UcxMapElement *e = (UcxMapElement*)almalloc( 1.182 - allocator, sizeof(UcxMapElement)); 1.183 - if (!e) { 1.184 - return -1; 1.185 - } 1.186 - e->key.data = NULL; 1.187 - if (prev) { 1.188 - prev->next = e; 1.189 - } else { 1.190 - map->map[slot] = e; 1.191 - } 1.192 - e->next = elm; 1.193 - elm = e; 1.194 - } 1.195 - 1.196 - if (!elm->key.data) { 1.197 - void *kd = almalloc(allocator, key.len); 1.198 - if (!kd) { 1.199 - return -1; 1.200 - } 1.201 - memcpy(kd, key.data, key.len); 1.202 - mapkey.data = kd; 1.203 - mapkey.len = key.len; 1.204 - elm->key = mapkey; 1.205 - map->count++; 1.206 - } 1.207 - elm->data = data; 1.208 - 1.209 - return 0; 1.210 -} 1.211 - 1.212 -static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) { 1.213 - if(key.hash == 0) { 1.214 - key.hash = ucx_hash((const char*)key.data, key.len); 1.215 - } 1.216 - 1.217 - size_t slot = key.hash%map->size; 1.218 - UcxMapElement *elm = map->map[slot]; 1.219 - UcxMapElement *pelm = NULL; 1.220 - while (elm && elm->key.hash <= key.hash) { 1.221 - if(elm->key.hash == key.hash) { 1.222 - int n = (key.len > elm->key.len) ? elm->key.len : key.len; 1.223 - if (memcmp(elm->key.data, key.data, n) == 0) { 1.224 - void *data = elm->data; 1.225 - if (remove) { 1.226 - if (pelm) { 1.227 - pelm->next = elm->next; 1.228 - } else { 1.229 - map->map[slot] = elm->next; 1.230 - } 1.231 - alfree(map->allocator, elm->key.data); 1.232 - alfree(map->allocator, elm); 1.233 - map->count--; 1.234 - } 1.235 - 1.236 - return data; 1.237 - } 1.238 - } 1.239 - pelm = elm; 1.240 - elm = pelm->next; 1.241 - } 1.242 - 1.243 - return NULL; 1.244 -} 1.245 - 1.246 -void *ucx_map_get(UcxMap const *map, UcxKey key) { 1.247 - return ucx_map_get_and_remove((UcxMap *)map, key, 0); 1.248 -} 1.249 - 1.250 -void *ucx_map_remove(UcxMap *map, UcxKey key) { 1.251 - return ucx_map_get_and_remove(map, key, 1); 1.252 -} 1.253 - 1.254 -UcxKey ucx_key(const void *data, size_t len) { 1.255 - UcxKey key; 1.256 - key.data = data; 1.257 - key.len = len; 1.258 - key.hash = ucx_hash((const char*)data, len); 1.259 - return key; 1.260 -} 1.261 - 1.262 - 1.263 -int ucx_hash(const char *data, size_t len) { 1.264 - /* murmur hash 2 */ 1.265 - 1.266 - int m = 0x5bd1e995; 1.267 - int r = 24; 1.268 - 1.269 - int h = 25 ^ len; 1.270 - 1.271 - int i = 0; 1.272 - while (len >= 4) { 1.273 - int k = data[i + 0] & 0xFF; 1.274 - k |= (data[i + 1] & 0xFF) << 8; 1.275 - k |= (data[i + 2] & 0xFF) << 16; 1.276 - k |= (data[i + 3] & 0xFF) << 24; 1.277 - 1.278 - k *= m; 1.279 - k ^= k >> r; 1.280 - k *= m; 1.281 - 1.282 - h *= m; 1.283 - h ^= k; 1.284 - 1.285 - i += 4; 1.286 - len -= 4; 1.287 - } 1.288 - 1.289 - switch (len) { 1.290 - case 3: h ^= (data[i + 2] & 0xFF) << 16; 1.291 - /* no break */ 1.292 - case 2: h ^= (data[i + 1] & 0xFF) << 8; 1.293 - /* no break */ 1.294 - case 1: h ^= (data[i + 0] & 0xFF); h *= m; 1.295 - /* no break */ 1.296 - } 1.297 - 1.298 - h ^= h >> 13; 1.299 - h *= m; 1.300 - h ^= h >> 15; 1.301 - 1.302 - return h; 1.303 -} 1.304 - 1.305 -UcxMapIterator ucx_map_iterator(UcxMap const *map) { 1.306 - UcxMapIterator i; 1.307 - i.map = map; 1.308 - i.cur = NULL; 1.309 - i.index = 0; 1.310 - return i; 1.311 -} 1.312 - 1.313 -int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) { 1.314 - UcxMapElement *e = i->cur; 1.315 - 1.316 - if (e) { 1.317 - e = e->next; 1.318 - } else { 1.319 - e = i->map->map[0]; 1.320 - } 1.321 - 1.322 - while (i->index < i->map->size) { 1.323 - if (e) { 1.324 - if (e->data) { 1.325 - i->cur = e; 1.326 - *elm = e->data; 1.327 - key->data = e->key.data; 1.328 - key->hash = e->key.hash; 1.329 - key->len = e->key.len; 1.330 - return 1; 1.331 - } 1.332 - 1.333 - e = e->next; 1.334 - } else { 1.335 - i->index++; 1.336 - 1.337 - if (i->index < i->map->size) { 1.338 - e = i->map->map[i->index]; 1.339 - } 1.340 - } 1.341 - } 1.342 - 1.343 - return 0; 1.344 -} 1.345 - 1.346 -UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second, 1.347 - copy_func cpfnc, void* cpdata) { 1.348 - return ucx_map_union_a(ucx_default_allocator(), 1.349 - first, second, cpfnc, cpdata); 1.350 -} 1.351 - 1.352 -UcxMap* ucx_map_union_a(UcxAllocator *allocator, 1.353 - const UcxMap *first, const UcxMap *second, 1.354 - copy_func cpfnc, void* cpdata) { 1.355 - UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata); 1.356 - ucx_map_copy(second, result, cpfnc, cpdata); 1.357 - return result; 1.358 -} 1.359 - 1.360 -UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second, 1.361 - copy_func cpfnc, void* cpdata) { 1.362 - return ucx_map_intersection_a(ucx_default_allocator(), 1.363 - first, second, cpfnc, cpdata); 1.364 -} 1.365 - 1.366 -UcxMap* ucx_map_intersection_a(UcxAllocator *allocator, 1.367 - const UcxMap *first, const UcxMap *second, 1.368 - copy_func cpfnc, void* cpdata) { 1.369 - UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ? 1.370 - first->size : second->size); 1.371 - 1.372 - UcxMapIterator iter = ucx_map_iterator(first); 1.373 - void* value; 1.374 - UCX_MAP_FOREACH(key, value, iter) { 1.375 - if (ucx_map_get(second, key)) { 1.376 - ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value); 1.377 - } 1.378 - } 1.379 - 1.380 - return result; 1.381 -} 1.382 - 1.383 -UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second, 1.384 - copy_func cpfnc, void* cpdata) { 1.385 - return ucx_map_difference_a(ucx_default_allocator(), 1.386 - first, second, cpfnc, cpdata); 1.387 -} 1.388 - 1.389 -UcxMap* ucx_map_difference_a(UcxAllocator *allocator, 1.390 - const UcxMap *first, const UcxMap *second, 1.391 - copy_func cpfnc, void* cpdata) { 1.392 - 1.393 - UcxMap *result = ucx_map_new_a(allocator, first->size - second->count); 1.394 - 1.395 - UcxMapIterator iter = ucx_map_iterator(first); 1.396 - void* value; 1.397 - UCX_MAP_FOREACH(key, value, iter) { 1.398 - if (!ucx_map_get(second, key)) { 1.399 - ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value); 1.400 - } 1.401 - } 1.402 - 1.403 - ucx_map_rehash(result); 1.404 - return result; 1.405 -} 1.406 \ No newline at end of file