tip/ucx/hash_map.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2021 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 "cx/hash_map.h"

#include <string.h>
#include <assert.h>
#include <errno.h>

struct cx_hash_map_element_s {
    /** A pointer to the next element in the current bucket. */
    struct cx_hash_map_element_s *next;

    /** The corresponding key. */
    CxHashKey key;

    /** The value data. */
    char data[];
};

static void cx_hash_map_clear(struct cx_map_s *map) {
    struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    for (size_t i = 0; i < hash_map->bucket_count; i++) {
        struct cx_hash_map_element_s *elem = hash_map->buckets[i];
        if (elem != NULL) {
            do {
                struct cx_hash_map_element_s *next = elem->next;
                // invoke the destructor
                cx_invoke_destructor(map, elem->data);
                // free the key data
                cxFree(map->collection.allocator, (void *) elem->key.data);
                // free the node
                cxFree(map->collection.allocator, elem);
                // proceed
                elem = next;
            } while (elem != NULL);

            // do not leave a dangling pointer
            hash_map->buckets[i] = NULL;
        }
    }
    map->collection.size = 0;
}

static void cx_hash_map_destructor(struct cx_map_s *map) {
    struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;

    // free the buckets
    cx_hash_map_clear(map);
    cxFree(map->collection.allocator, hash_map->buckets);

    // free the map structure
    cxFree(map->collection.allocator, map);
}

static void *cx_hash_map_put(
        CxMap *map,
        CxHashKey key,
        void *value
) {
    struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    const CxAllocator *allocator = map->collection.allocator;

    uint64_t hash = key.hash;
    if (hash == 0) {
        cx_hash_murmur(&key);
        hash = key.hash;
    }

    size_t slot = hash % hash_map->bucket_count;
    struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
    struct cx_hash_map_element_s *prev = NULL;

    while (elm != NULL && elm->key.hash < hash) {
        prev = elm;
        elm = elm->next;
    }

    if (elm != NULL && cx_hash_key_cmp(&elm->key, &key) == 0) {
        // overwrite existing element, but call destructors first
        cx_invoke_destructor(map, elm->data);
        if (value == NULL) {
            memset(elm->data, 0, map->collection.elem_size);
        } else if (map->collection.store_pointer) {
            memcpy(elm->data, &value, sizeof(void *));
        } else {
            memcpy(elm->data, value, map->collection.elem_size);
        }
    } else {
        // allocate new element
        struct cx_hash_map_element_s *e = cxMalloc(
                allocator,
                sizeof(struct cx_hash_map_element_s) + map->collection.elem_size
        );
        if (e == NULL) return NULL; // LCOV_EXCL_LINE

        // write the value
        if (value == NULL) {
            memset(e->data, 0, map->collection.elem_size);
        } else if (map->collection.store_pointer) {
            memcpy(e->data, &value, sizeof(void *));
        } else {
            memcpy(e->data, value, map->collection.elem_size);
        }

        // copy the key
        void *kd = cxMalloc(allocator, key.len);
        if (kd == NULL) { // LCOV_EXCL_START
            cxFree(allocator, e);
            return NULL;
        } // LCOV_EXCL_STOP
        memcpy(kd, key.data, key.len);
        e->key.data = kd;
        e->key.len = key.len;
        e->key.hash = hash;

        // insert the element into the linked list
        if (prev == NULL) {
            hash_map->buckets[slot] = e;
        } else {
            prev->next = e;
        }
        e->next = elm;
        elm = e;

        // increase the size
        map->collection.size++;
    }

    // return pointer to the element
    return elm->data;
}

static void cx_hash_map_unlink(
        struct cx_hash_map_s *hash_map,
        size_t slot,
        struct cx_hash_map_element_s *prev,
        struct cx_hash_map_element_s *elm
) {
    // unlink
    if (prev == NULL) {
        hash_map->buckets[slot] = elm->next;
    } else {
        prev->next = elm->next;
    }
    // free element
    cxFree(hash_map->base.collection.allocator, (void *) elm->key.data);
    cxFree(hash_map->base.collection.allocator, elm);
    // decrease size
    hash_map->base.collection.size--;
}

/**
 * Helper function to avoid code duplication.
 *
 * If @p remove is true, and @p targetbuf is @c NULL, the element
 * will be destroyed when found.
 *
 * If @p remove is true, and @p targetbuf is set, the element will
 * be copied to that buffer and no destructor function is called.
 *
 * If @p remove is false, @p targetbuf must not be non-null and
 * either the pointer, when the map is storing pointers, is copied
 * to the target buffer, or a pointer to the stored object will
 * be copied to the target buffer.
 *
 * @param map the map
 * @param key the key to look up
 * @param targetbuf see description
 * @param remove flag indicating whether the looked up entry shall be removed
 * @return zero, if the key was found, non-zero otherwise
 */
static int cx_hash_map_get_remove(
        CxMap *map,
        CxHashKey key,
        void *targetbuf,
        bool remove
) {
    struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;

    uint64_t hash = key.hash;
    if (hash == 0) {
        cx_hash_murmur(&key);
        hash = key.hash;
    }

    size_t slot = hash % hash_map->bucket_count;
    struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
    struct cx_hash_map_element_s *prev = NULL;
    while (elm && elm->key.hash <= hash) {
        if (cx_hash_key_cmp(&elm->key, &key) == 0) {
            if (remove) {
                if (targetbuf == NULL) {
                    cx_invoke_destructor(map, elm->data);
                } else {
                    memcpy(targetbuf, elm->data, map->collection.elem_size);
                }
                cx_hash_map_unlink(hash_map, slot, prev, elm);
            } else {
                assert(targetbuf != NULL);
                void *data = NULL;
                if (map->collection.store_pointer) {
                    data = *(void **) elm->data;
                } else {
                    data = elm->data;
                }
                memcpy(targetbuf, &data, sizeof(void *));
            }
            return 0;
        }
        prev = elm;
        elm = prev->next;
    }

    return 1;
}

static void *cx_hash_map_get(
        const CxMap *map,
        CxHashKey key
) {
    // we can safely cast, because we know the map stays untouched
    void *ptr = NULL;
    int found = cx_hash_map_get_remove((CxMap *) map, key, &ptr, false);
    return found == 0 ? ptr : NULL;
}

static int cx_hash_map_remove(
        CxMap *map,
        CxHashKey key,
        void *targetbuf
) {
    return cx_hash_map_get_remove(map, key, targetbuf, true);
}

static void *cx_hash_map_iter_current_entry(const void *it) {
    const CxMapIterator *iter = it;
    // we have to cast away const, because of the signature
    return (void*) &iter->entry;
}

static void *cx_hash_map_iter_current_key(const void *it) {
    const CxMapIterator *iter = it;
    return (void*) iter->entry.key;
}

static void *cx_hash_map_iter_current_value(const void *it) {
    const CxMapIterator *iter = it;
    return iter->entry.value;
}

static bool cx_hash_map_iter_valid(const void *it) {
    const CxMapIterator *iter = it;
    return iter->elem != NULL;
}

static void cx_hash_map_iter_next(void *it) {
    CxMapIterator *iter = it;
    CxMap *map = iter->map;
    struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
    struct cx_hash_map_element_s *elm = iter->elem;

    // remove current element, if asked
    if (iter->base.remove) {

        // clear the flag
        iter->base.remove = false;

        // determine the next element
        struct cx_hash_map_element_s *next = elm->next;

        // search the previous element
        struct cx_hash_map_element_s *prev = NULL;
        if (hmap->buckets[iter->slot] != elm) {
            prev = hmap->buckets[iter->slot];
            while (prev->next != elm) {
                prev = prev->next;
            }
        }

        // destroy
        cx_invoke_destructor(map, elm->data);

        // unlink
        cx_hash_map_unlink(hmap, iter->slot, prev, elm);
        iter->elem_count--;

        // advance
        elm = next;
    } else {
        // just advance
        elm = elm->next;
        iter->index++;
    }

    // search the next bucket, if required
    while (elm == NULL && ++iter->slot < hmap->bucket_count) {
        elm = hmap->buckets[iter->slot];
    }
    iter->elem = elm;

    // copy data to a location where the iterator can point to
    // we need to do it here, because the iterator function call
    // must not modify the iterator (the parameter is const)
    if (elm != NULL) {
        iter->entry.key = &elm->key;
        if (map->collection.store_pointer) {
            iter->entry.value = *(void **) elm->data;
        } else {
            iter->entry.value = elm->data;
        }
    }
}

static CxMapIterator cx_hash_map_iterator(
        const CxMap *map,
        enum cx_map_iterator_type type
) {
    CxMapIterator iter;

    iter.map = (CxMap*) map;
    iter.elem_count = map->collection.size;

    switch (type) {
        case CX_MAP_ITERATOR_PAIRS:
            iter.elem_size = sizeof(CxMapEntry);
            iter.base.current = cx_hash_map_iter_current_entry;
            break;
        case CX_MAP_ITERATOR_KEYS:
            iter.elem_size = sizeof(CxHashKey);
            iter.base.current = cx_hash_map_iter_current_key;
            break;
        case CX_MAP_ITERATOR_VALUES:
            iter.elem_size = map->collection.elem_size;
            iter.base.current = cx_hash_map_iter_current_value;
            break;
        default:
            assert(false); // LCOV_EXCL_LINE
    }

    iter.base.valid = cx_hash_map_iter_valid;
    iter.base.next = cx_hash_map_iter_next;
    iter.base.remove = false;
    iter.base.allow_remove = true;

    iter.slot = 0;
    iter.index = 0;

    if (map->collection.size > 0) {
        struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
        struct cx_hash_map_element_s *elm = hash_map->buckets[0];
        while (elm == NULL) {
            elm = hash_map->buckets[++iter.slot];
        }
        iter.elem = elm;
        iter.entry.key = &elm->key;
        if (map->collection.store_pointer) {
            iter.entry.value = *(void **) elm->data;
        } else {
            iter.entry.value = elm->data;
        }
    } else {
        iter.elem = NULL;
    }

    return iter;
}

static cx_map_class cx_hash_map_class = {
        cx_hash_map_destructor,
        cx_hash_map_clear,
        cx_hash_map_put,
        cx_hash_map_get,
        cx_hash_map_remove,
        cx_hash_map_iterator,
};

CxMap *cxHashMapCreate(
        const CxAllocator *allocator,
        size_t itemsize,
        size_t buckets
) {
    if (allocator == NULL) {
        allocator = cxDefaultAllocator;
    }

    if (buckets == 0) {
        // implementation defined default
        buckets = 16;
    }

    struct cx_hash_map_s *map = cxCalloc(allocator, 1,
                                         sizeof(struct cx_hash_map_s));
    if (map == NULL) return NULL;

    // initialize hash map members
    map->bucket_count = buckets;
    map->buckets = cxCalloc(allocator, buckets,
                            sizeof(struct cx_hash_map_element_s *));
    if (map->buckets == NULL) { // LCOV_EXCL_START
        cxFree(allocator, map);
        return NULL;
    } // LCOV_EXCL_STOP

    // initialize base members
    map->base.cl = &cx_hash_map_class;
    map->base.collection.allocator = allocator;

    if (itemsize > 0) {
        map->base.collection.elem_size = itemsize;
    } else {
        map->base.collection.elem_size = sizeof(void *);
        map->base.collection.store_pointer = true;
    }

    return (CxMap *) map;
}

int cxMapRehash(CxMap *map) {
    struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) {

        size_t new_bucket_count = (map->collection.size * 5) >> 1;
        if (new_bucket_count < hash_map->bucket_count) {
            // LCOV_EXCL_START
            errno = EOVERFLOW;
            return 1;
        } // LCOV_EXCL_STOP
        struct cx_hash_map_element_s **new_buckets = cxCalloc(
                map->collection.allocator,
                new_bucket_count, sizeof(struct cx_hash_map_element_s *)
        );

        if (new_buckets == NULL) return 1; // LCOV_EXCL_LINE

        // iterate through the elements and assign them to their new slots
        for (size_t slot = 0; slot < hash_map->bucket_count; slot++) {
            struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
            while (elm != NULL) {
                struct cx_hash_map_element_s *next = elm->next;
                size_t new_slot = elm->key.hash % new_bucket_count;

                // find position where to insert
                struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];
                struct cx_hash_map_element_s *bucket_prev = NULL;
                while (bucket_next != NULL &&
                       bucket_next->key.hash < elm->key.hash) {
                    bucket_prev = bucket_next;
                    bucket_next = bucket_next->next;
                }

                // insert
                if (bucket_prev == NULL) {
                    elm->next = new_buckets[new_slot];
                    new_buckets[new_slot] = elm;
                } else {
                    bucket_prev->next = elm;
                    elm->next = bucket_next;
                }

                // advance
                elm = next;
            }
        }

        // assign result to the map
        hash_map->bucket_count = new_bucket_count;
        cxFree(map->collection.allocator, hash_map->buckets);
        hash_map->buckets = new_buckets;
    }
    return 0;
}