1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/map.c Tue Oct 17 16:15:41 2017 +0200
1.3 @@ -0,0 +1,328 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2017 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 + destr(val);
1.93 + }
1.94 +}
1.95 +
1.96 +void ucx_map_clear(UcxMap *map) {
1.97 + if (map->count == 0) {
1.98 + return; // nothing to do
1.99 + }
1.100 + ucx_map_free_elmlist_contents(map);
1.101 + memset(map->map, 0, map->size*sizeof(UcxMapElement*));
1.102 + map->count = 0;
1.103 +}
1.104 +
1.105 +int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,
1.106 + copy_func fnc, void *data) {
1.107 + UcxMapIterator i = ucx_map_iterator(from);
1.108 + void *value;
1.109 + UCX_MAP_FOREACH(key, value, i) {
1.110 + if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) {
1.111 + return 1;
1.112 + }
1.113 + }
1.114 + return 0;
1.115 +}
1.116 +
1.117 +UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {
1.118 + size_t bs = (map->count * 5) >> 1;
1.119 + UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);
1.120 + if (!newmap) {
1.121 + return NULL;
1.122 + }
1.123 + ucx_map_copy(map, newmap, fnc, data);
1.124 + return newmap;
1.125 +}
1.126 +
1.127 +int ucx_map_rehash(UcxMap *map) {
1.128 + size_t load = (map->size * 3) >> 2;
1.129 + if (map->count > load) {
1.130 + UcxMap oldmap;
1.131 + oldmap.map = map->map;
1.132 + oldmap.size = map->size;
1.133 + oldmap.count = map->count;
1.134 + oldmap.allocator = map->allocator;
1.135 +
1.136 + map->size = (map->count * 5) >> 1;
1.137 + map->map = (UcxMapElement**)alcalloc(
1.138 + map->allocator, map->size, sizeof(UcxMapElement*));
1.139 + if (!map->map) {
1.140 + *map = oldmap;
1.141 + return 1;
1.142 + }
1.143 + map->count = 0;
1.144 + ucx_map_copy(&oldmap, map, NULL, NULL);
1.145 +
1.146 + /* free the UcxMapElement list of oldmap */
1.147 + ucx_map_free_elmlist_contents(&oldmap);
1.148 + alfree(map->allocator, oldmap.map);
1.149 + }
1.150 + return 0;
1.151 +}
1.152 +
1.153 +int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
1.154 + UcxAllocator *allocator = map->allocator;
1.155 +
1.156 + if (key.hash == 0) {
1.157 + key.hash = ucx_hash((char*)key.data, key.len);
1.158 + }
1.159 +
1.160 + size_t slot = key.hash%map->size;
1.161 + UcxMapElement *restrict elm = map->map[slot];
1.162 + UcxMapElement *restrict prev = NULL;
1.163 +
1.164 + while (elm && elm->key.hash < key.hash) {
1.165 + prev = elm;
1.166 + elm = elm->next;
1.167 + }
1.168 +
1.169 + if (!elm || elm->key.hash != key.hash) {
1.170 + UcxMapElement *e = (UcxMapElement*)almalloc(
1.171 + allocator, sizeof(UcxMapElement));
1.172 + if (!e) {
1.173 + return -1;
1.174 + }
1.175 + e->key.data = NULL;
1.176 + if (prev) {
1.177 + prev->next = e;
1.178 + } else {
1.179 + map->map[slot] = e;
1.180 + }
1.181 + e->next = elm;
1.182 + elm = e;
1.183 + }
1.184 +
1.185 + if (!elm->key.data) {
1.186 + void *kd = almalloc(allocator, key.len);
1.187 + if (!kd) {
1.188 + return -1;
1.189 + }
1.190 + memcpy(kd, key.data, key.len);
1.191 + key.data = kd;
1.192 + elm->key = key;
1.193 + map->count++;
1.194 + }
1.195 + elm->data = data;
1.196 +
1.197 + return 0;
1.198 +}
1.199 +
1.200 +void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {
1.201 + if(key.hash == 0) {
1.202 + key.hash = ucx_hash((char*)key.data, key.len);
1.203 + }
1.204 +
1.205 + size_t slot = key.hash%map->size;
1.206 + UcxMapElement *restrict elm = map->map[slot];
1.207 + UcxMapElement *restrict pelm = NULL;
1.208 + while (elm && elm->key.hash <= key.hash) {
1.209 + if(elm->key.hash == key.hash) {
1.210 + int n = (key.len > elm->key.len) ? elm->key.len : key.len;
1.211 + if (memcmp(elm->key.data, key.data, n) == 0) {
1.212 + void *data = elm->data;
1.213 + if (remove) {
1.214 + if (pelm) {
1.215 + pelm->next = elm->next;
1.216 + } else {
1.217 + map->map[slot] = elm->next;
1.218 + }
1.219 + alfree(map->allocator, elm->key.data);
1.220 + alfree(map->allocator, elm);
1.221 + map->count--;
1.222 + }
1.223 +
1.224 + return data;
1.225 + }
1.226 + }
1.227 + pelm = elm;
1.228 + elm = pelm->next;
1.229 + }
1.230 +
1.231 + return NULL;
1.232 +}
1.233 +
1.234 +void *ucx_map_get(UcxMap *map, UcxKey key) {
1.235 + return ucx_map_get_and_remove(map, key, 0);
1.236 +}
1.237 +
1.238 +void *ucx_map_remove(UcxMap *map, UcxKey key) {
1.239 + return ucx_map_get_and_remove(map, key, 1);
1.240 +}
1.241 +
1.242 +UcxKey ucx_key(void *data, size_t len) {
1.243 + UcxKey key;
1.244 + key.data = data;
1.245 + key.len = len;
1.246 + key.hash = ucx_hash((const char*) data, len);
1.247 + return key;
1.248 +}
1.249 +
1.250 +
1.251 +int ucx_hash(const char *data, size_t len) {
1.252 + /* murmur hash 2 */
1.253 +
1.254 + int m = 0x5bd1e995;
1.255 + int r = 24;
1.256 +
1.257 + int h = 25 ^ len;
1.258 +
1.259 + int i = 0;
1.260 + while (len >= 4) {
1.261 + int k = data[i + 0] & 0xFF;
1.262 + k |= (data[i + 1] & 0xFF) << 8;
1.263 + k |= (data[i + 2] & 0xFF) << 16;
1.264 + k |= (data[i + 3] & 0xFF) << 24;
1.265 +
1.266 + k *= m;
1.267 + k ^= k >> r;
1.268 + k *= m;
1.269 +
1.270 + h *= m;
1.271 + h ^= k;
1.272 +
1.273 + i += 4;
1.274 + len -= 4;
1.275 + }
1.276 +
1.277 + switch (len) {
1.278 + case 3: h ^= (data[i + 2] & 0xFF) << 16;
1.279 + /* no break */
1.280 + case 2: h ^= (data[i + 1] & 0xFF) << 8;
1.281 + /* no break */
1.282 + case 1: h ^= (data[i + 0] & 0xFF); h *= m;
1.283 + /* no break */
1.284 + }
1.285 +
1.286 + h ^= h >> 13;
1.287 + h *= m;
1.288 + h ^= h >> 15;
1.289 +
1.290 + return h;
1.291 +}
1.292 +
1.293 +UcxMapIterator ucx_map_iterator(UcxMap *map) {
1.294 + UcxMapIterator i;
1.295 + i.map = map;
1.296 + i.cur = NULL;
1.297 + i.index = 0;
1.298 + return i;
1.299 +}
1.300 +
1.301 +int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) {
1.302 + UcxMapElement *e = i->cur;
1.303 +
1.304 + if (e) {
1.305 + e = e->next;
1.306 + } else {
1.307 + e = i->map->map[0];
1.308 + }
1.309 +
1.310 + while (i->index < i->map->size) {
1.311 + if (e) {
1.312 + if (e->data) {
1.313 + i->cur = e;
1.314 + *elm = e->data;
1.315 + *key = e->key;
1.316 + return 1;
1.317 + }
1.318 +
1.319 + e = e->next;
1.320 + } else {
1.321 + i->index++;
1.322 +
1.323 + if (i->index < i->map->size) {
1.324 + e = i->map->map[i->index];
1.325 + }
1.326 + }
1.327 + }
1.328 +
1.329 + return 0;
1.330 +}
1.331 +
