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