ucx/map.c

/*
 * 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;
}