/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2017 Mike Becker, 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 "ucx/map.h"
#include <stdlib.h>
#include <string.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) {
if (destr) {
destr(val);
} else {
alfree(map->allocator, 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 const *from, UcxMap *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 const *map, copy_func fnc, void *data) {
return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data);
}
UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
UcxMap const *map, copy_func fnc, void *data) {
size_t bs = (map->count * 5) >> 1;
UcxMap *newmap = ucx_map_new_a(allocator, 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((const char*)key.data, key.len);
}
struct UcxMapKey mapkey;
mapkey.hash = key.hash;
size_t slot = mapkey.hash%map->size;
UcxMapElement *elm = map->map[slot];
UcxMapElement *prev = NULL;
while (elm && elm->key.hash < mapkey.hash) {
prev = elm;
elm = elm->next;
}
if (!elm || elm->key.hash != mapkey.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);
mapkey.data = kd;
mapkey.len = key.len;
elm->key = mapkey;
map->count++;
}
elm->data = data;
return 0;
}
static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) {
if(key.hash == 0) {
key.hash = ucx_hash((const char*)key.data, key.len);
}
size_t slot = key.hash%map->size;
UcxMapElement *elm = map->map[slot];
UcxMapElement *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 const *map, UcxKey key) {
return ucx_map_get_and_remove((UcxMap *)map, key, 0);
}
void *ucx_map_remove(UcxMap *map, UcxKey key) {
return ucx_map_get_and_remove(map, key, 1);
}
UcxKey ucx_key(const 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 const *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->data = e->key.data;
key->hash = e->key.hash;
key->len = e->key.len;
return 1;
}
e = e->next;
} else {
i->index++;
if (i->index < i->map->size) {
e = i->map->map[i->index];
}
}
}
return 0;
}
UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
copy_func cpfnc, void* cpdata) {
return ucx_map_union_a(ucx_default_allocator(),
first, second, cpfnc, cpdata);
}
UcxMap* ucx_map_union_a(UcxAllocator *allocator,
const UcxMap *first, const UcxMap *second,
copy_func cpfnc, void* cpdata) {
UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata);
ucx_map_copy(second, result, cpfnc, cpdata);
return result;
}
UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
copy_func cpfnc, void* cpdata) {
return ucx_map_intersection_a(ucx_default_allocator(),
first, second, cpfnc, cpdata);
}
UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
const UcxMap *first, const UcxMap *second,
copy_func cpfnc, void* cpdata) {
UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ?
first->size : second->size);
UcxMapIterator iter = ucx_map_iterator(first);
void* value;
UCX_MAP_FOREACH(key, value, iter) {
if (ucx_map_get(second, key)) {
ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
}
}
return result;
}
UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
copy_func cpfnc, void* cpdata) {
return ucx_map_difference_a(ucx_default_allocator(),
first, second, cpfnc, cpdata);
}
UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
const UcxMap *first, const UcxMap *second,
copy_func cpfnc, void* cpdata) {
UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);
UcxMapIterator iter = ucx_map_iterator(first);
void* value;
UCX_MAP_FOREACH(key, value, iter) {
if (!ucx_map_get(second, key)) {
ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
}
}
ucx_map_rehash(result);
return result;
}