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 <stdlib.h>
olaf@20: #include <string.h>
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: