olaf@20: /* universe@103: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. olaf@20: * universe@250: * Copyright 2017 Olaf Wintermann. All rights reserved. universe@103: * universe@103: * Redistribution and use in source and binary forms, with or without universe@103: * modification, are permitted provided that the following conditions are met: universe@103: * universe@103: * 1. Redistributions of source code must retain the above copyright universe@103: * notice, this list of conditions and the following disclaimer. universe@103: * universe@103: * 2. Redistributions in binary form must reproduce the above copyright universe@103: * notice, this list of conditions and the following disclaimer in the universe@103: * documentation and/or other materials provided with the distribution. universe@103: * universe@103: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@103: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@103: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@103: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@103: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@103: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@103: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@103: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@103: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@103: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@103: * POSSIBILITY OF SUCH DAMAGE. olaf@20: */ olaf@2: universe@251: #include "ucx/map.h" universe@251: olaf@20: #include olaf@20: #include olaf@20: olaf@20: UcxMap *ucx_map_new(size_t size) { olaf@137: return ucx_map_new_a(NULL, size); olaf@107: } olaf@107: olaf@137: UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) { olaf@45: if(size == 0) { olaf@45: size = 16; olaf@45: } olaf@108: olaf@107: if(!allocator) { olaf@107: allocator = ucx_default_allocator(); olaf@107: } olaf@107: universe@173: UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap)); universe@139: if (!map) { olaf@20: return NULL; olaf@20: } olaf@107: olaf@107: map->allocator = allocator; universe@173: map->map = (UcxMapElement**)alcalloc( universe@173: allocator, size, sizeof(UcxMapElement*)); olaf@20: if(map->map == NULL) { universe@173: alfree(allocator, map); olaf@20: return NULL; olaf@20: } olaf@20: map->size = size; olaf@45: map->count = 0; olaf@20: olaf@20: return map; olaf@20: } olaf@20: universe@206: static void ucx_map_free_elmlist_contents(UcxMap *map) { universe@29: for (size_t n = 0 ; n < map->size ; n++) { universe@29: UcxMapElement *elem = map->map[n]; universe@29: if (elem != NULL) { universe@29: do { universe@29: UcxMapElement *next = elem->next; universe@173: alfree(map->allocator, elem->key.data); universe@173: alfree(map->allocator, elem); universe@29: elem = next; universe@29: } while (elem != NULL); universe@29: } universe@29: } olaf@70: } olaf@70: olaf@70: void ucx_map_free(UcxMap *map) { universe@206: ucx_map_free_elmlist_contents(map); universe@206: alfree(map->allocator, map->map); universe@173: alfree(map->allocator, map); universe@29: } universe@29: universe@209: void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { universe@208: UcxMapIterator iter = ucx_map_iterator(map); universe@208: void *val; universe@208: UCX_MAP_FOREACH(key, val, iter) { universe@209: destr(val); universe@208: } universe@208: } universe@208: universe@206: void ucx_map_clear(UcxMap *map) { universe@207: if (map->count == 0) { universe@207: return; // nothing to do universe@207: } universe@206: ucx_map_free_elmlist_contents(map); universe@206: memset(map->map, 0, map->size*sizeof(UcxMapElement*)); universe@206: map->count = 0; universe@206: } universe@206: universe@67: int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, universe@67: copy_func fnc, void *data) { olaf@52: UcxMapIterator i = ucx_map_iterator(from); olaf@52: void *value; olaf@111: UCX_MAP_FOREACH(key, value, i) { universe@138: if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { olaf@52: return 1; olaf@52: } olaf@52: } olaf@52: return 0; olaf@52: } olaf@52: olaf@44: UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { universe@51: size_t bs = (map->count * 5) >> 1; olaf@45: UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); universe@138: if (!newmap) { olaf@52: return NULL; olaf@44: } olaf@52: ucx_map_copy(map, newmap, fnc, data); olaf@44: return newmap; olaf@44: } olaf@44: olaf@52: int ucx_map_rehash(UcxMap *map) { universe@51: size_t load = (map->size * 3) >> 2; universe@51: if (map->count > load) { olaf@52: UcxMap oldmap; olaf@52: oldmap.map = map->map; olaf@52: oldmap.size = map->size; olaf@52: oldmap.count = map->count; olaf@107: oldmap.allocator = map->allocator; olaf@52: olaf@52: map->size = (map->count * 5) >> 1; universe@173: map->map = (UcxMapElement**)alcalloc( universe@173: map->allocator, map->size, sizeof(UcxMapElement*)); universe@138: if (!map->map) { olaf@52: *map = oldmap; olaf@52: return 1; olaf@52: } olaf@52: map->count = 0; olaf@52: ucx_map_copy(&oldmap, map, NULL, NULL); olaf@70: olaf@70: /* free the UcxMapElement list of oldmap */ universe@206: ucx_map_free_elmlist_contents(&oldmap); universe@206: alfree(map->allocator, oldmap.map); universe@51: } olaf@52: return 0; universe@51: } universe@51: olaf@20: int ucx_map_put(UcxMap *map, UcxKey key, void *data) { olaf@107: UcxAllocator *allocator = map->allocator; olaf@107: universe@138: if (key.hash == 0) { olaf@20: key.hash = ucx_hash((char*)key.data, key.len); olaf@20: } olaf@20: universe@29: size_t slot = key.hash%map->size; universe@67: UcxMapElement *restrict elm = map->map[slot]; universe@67: UcxMapElement *restrict prev = NULL; universe@29: universe@138: while (elm && elm->key.hash < key.hash) { universe@29: prev = elm; universe@29: elm = elm->next; universe@29: } universe@29: universe@138: if (!elm || elm->key.hash != key.hash) { universe@173: UcxMapElement *e = (UcxMapElement*)almalloc( universe@173: allocator, sizeof(UcxMapElement)); universe@138: if (!e) { olaf@20: return -1; olaf@20: } olaf@30: e->key.data = NULL; universe@53: if (prev) { universe@53: prev->next = e; universe@53: } else { universe@29: map->map[slot] = e; universe@29: } universe@29: e->next = elm; olaf@20: elm = e; olaf@20: } universe@29: universe@138: if (!elm->key.data) { universe@173: void *kd = almalloc(allocator, key.len); universe@138: if (!kd) { olaf@30: return -1; olaf@30: } olaf@30: memcpy(kd, key.data, key.len); olaf@30: key.data = kd; olaf@30: elm->key = key; olaf@45: map->count++; olaf@30: } olaf@20: elm->data = data; olaf@20: olaf@20: return 0; olaf@20: } olaf@20: universe@53: void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) { olaf@20: if(key.hash == 0) { olaf@20: key.hash = ucx_hash((char*)key.data, key.len); olaf@20: } olaf@20: universe@53: size_t slot = key.hash%map->size; universe@67: UcxMapElement *restrict elm = map->map[slot]; universe@67: UcxMapElement *restrict pelm = NULL; universe@53: while (elm && elm->key.hash <= key.hash) { olaf@20: if(elm->key.hash == key.hash) { olaf@20: int n = (key.len > elm->key.len) ? elm->key.len : key.len; universe@29: if (memcmp(elm->key.data, key.data, n) == 0) { universe@53: void *data = elm->data; universe@53: if (remove) { universe@53: if (pelm) { universe@53: pelm->next = elm->next; universe@53: } else { universe@53: map->map[slot] = elm->next; universe@53: } universe@173: alfree(map->allocator, elm->key.data); universe@173: alfree(map->allocator, elm); universe@53: map->count--; universe@53: } universe@53: universe@53: return data; olaf@20: } olaf@20: } universe@53: pelm = elm; universe@53: elm = pelm->next; olaf@20: } olaf@20: olaf@20: return NULL; olaf@20: } olaf@20: universe@53: void *ucx_map_get(UcxMap *map, UcxKey key) { universe@53: return ucx_map_get_and_remove(map, key, 0); universe@53: } universe@53: universe@53: void *ucx_map_remove(UcxMap *map, UcxKey key) { universe@53: return ucx_map_get_and_remove(map, key, 1); universe@53: } universe@53: olaf@20: UcxKey ucx_key(void *data, size_t len) { olaf@20: UcxKey key; olaf@20: key.data = data; olaf@20: key.len = len; universe@69: key.hash = ucx_hash((const char*) data, len); olaf@20: return key; olaf@20: } olaf@20: olaf@20: universe@67: int ucx_hash(const char *data, size_t len) { olaf@20: /* murmur hash 2 */ olaf@20: olaf@20: int m = 0x5bd1e995; olaf@20: int r = 24; olaf@20: olaf@20: int h = 25 ^ len; olaf@20: olaf@20: int i = 0; olaf@20: while (len >= 4) { olaf@20: int k = data[i + 0] & 0xFF; olaf@20: k |= (data[i + 1] & 0xFF) << 8; olaf@20: k |= (data[i + 2] & 0xFF) << 16; olaf@20: k |= (data[i + 3] & 0xFF) << 24; olaf@20: olaf@20: k *= m; olaf@20: k ^= k >> r; olaf@20: k *= m; olaf@20: olaf@20: h *= m; olaf@20: h ^= k; olaf@20: olaf@20: i += 4; olaf@20: len -= 4; olaf@20: } olaf@20: olaf@20: switch (len) { olaf@20: case 3: h ^= (data[i + 2] & 0xFF) << 16; universe@38: /* no break */ olaf@20: case 2: h ^= (data[i + 1] & 0xFF) << 8; universe@38: /* no break */ olaf@20: case 1: h ^= (data[i + 0] & 0xFF); h *= m; universe@38: /* no break */ olaf@20: } olaf@20: olaf@20: h ^= h >> 13; olaf@20: h *= m; olaf@20: h ^= h >> 15; olaf@20: olaf@20: return h; olaf@20: } olaf@31: olaf@31: UcxMapIterator ucx_map_iterator(UcxMap *map) { olaf@31: UcxMapIterator i; olaf@31: i.map = map; olaf@31: i.cur = NULL; olaf@31: i.index = 0; olaf@31: return i; olaf@31: } olaf@31: olaf@111: int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) { olaf@31: UcxMapElement *e = i->cur; olaf@31: universe@138: if (e) { universe@138: e = e->next; universe@138: } else { olaf@31: e = i->map->map[0]; olaf@31: } olaf@31: universe@138: while (i->index < i->map->size) { universe@138: if (e) { universe@138: if (e->data) { olaf@31: i->cur = e; olaf@31: *elm = e->data; olaf@111: *key = e->key; universe@138: return 1; olaf@31: } olaf@31: olaf@31: e = e->next; olaf@31: } else { olaf@31: i->index++; olaf@31: universe@138: if (i->index < i->map->size) { olaf@31: e = i->map->map[i->index]; olaf@31: } olaf@31: } olaf@31: } olaf@31: universe@138: return 0; olaf@31: } universe@42: