path: root/src/hashmap.c

/* SPDX-License-Identifier: BSD-3-Clause */
/*
 * Copyright © 2010, Zed A. Shaw.
 * Copyright © 2020 rsiddharth <s@ricketyspace.net>
 */

#undef NDEBUG
#include <stdint.h>
#include <darray_algos.h>
#include <hashmap.h>
#include <dbg.h>
#include <bstrlib.h>

static int default_compare(void *a, void *b)
{
    return bstrcmp((bstring) a, (bstring) b);
}

/**
 * Simple Bob Jenkin's hash algorithm taken from the wikipedia
 * description.
 */
static uint32_t default_hash(void *a)
{
    size_t len = blength((bstring) a);
    char *key = bdata((bstring) a);
    uint32_t hash = 0;
    uint32_t i = 0;

    for (hash = i = 0; i < len; ++i) {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

/**
 * Fucked up version of FNV hash
 */
uint32_t fnv_hash(void *a)
{
    size_t len = blength((bstring) a);
    char *key = bdata((bstring) a);
    uint32_t hash =  0;
    uint32_t i =  0;
    uint32_t fnv_prime = 16777619;
    uint32_t fnv_offset_basis = 2166136261;

    hash = fnv_offset_basis;
    for (i = 0; i < len; ++i) {
        hash *= fnv_prime;
        hash ^= key[i];
    }

    return hash;
}

Hashmap *Hashmap_create(Hashmap_compare compare, Hashmap_hash hash)
{
    Hashmap *map = calloc(1, sizeof(Hashmap));
    check_mem(map);

    map->compare = compare == NULL ? default_compare : compare;
    map->hash = hash == NULL ? default_hash : hash;
    map->salt = rand() >> 16;
    map->buckets = DArray_create(
                                 sizeof(DArray *), DEFAULT_NUMBER_OF_BUCKETS);
    map->buckets->end = map->buckets->max; // fake out expanding it.
    check_mem(map->buckets);

    return map;

 error:
    if (map) {
        Hashmap_destroy(map);
    }

    return NULL;
}

void Hashmap_destroy(Hashmap *map)
{
    int i = 0;
    int j = 0;

    if (map) {
        if (map->buckets) {
            for (i = 0; i < DArray_count(map->buckets); i++) {
                DArray *bucket = DArray_get(map->buckets, i);
                if (bucket) {
                    for (j = 0; j < DArray_count(bucket); j++) {
                        free(DArray_get(bucket, j));
                    }
                    DArray_destroy(bucket);
                }
            }
            DArray_destroy(map->buckets);
        }

        free(map);
    }
}

static inline HashmapNode *Hashmap_node_create(int hash, void *key,
                                               void *data)
{
    HashmapNode *node = calloc(1, sizeof(HashmapNode));
    check_mem(node);

    node->key = key;
    node->data = data;
    node->hash = hash;

    return node;

 error:
    return NULL;
}

static inline DArray *Hashmap_find_bucket(Hashmap *map, void *key,
                                          int create,
                                          uint32_t *hash_out)
{
    uint32_t hash = map->hash(key) + map->salt;
    int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
    check(bucket_n >= 0, "Invalid bucket found %d", bucket_n);
    // store it for the return so the caller can use it
    *hash_out = hash;

    DArray *bucket = DArray_get(map->buckets, bucket_n);

    if (!bucket && create) {
        // new bucket, set it up
        bucket = DArray_create(
                               sizeof(void *), DEFAULT_NUMBER_OF_BUCKETS);
        check_mem(bucket);
        DArray_set(map->buckets, bucket_n, bucket);
    }

    return bucket;

 error:
    return NULL;
}

int Hashmap_delete_bucket(Hashmap *map, uint32_t hash)
{
    int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
    check(bucket_n >= 0, "Invalid bucket found %d", bucket_n);

    // Get bucket.
    DArray *bucket = DArray_get(map->buckets, bucket_n);
    if(bucket) {
        // Remove bucket.
        DArray_clear_destroy(bucket);
        DArray_remove(map->buckets, bucket_n);
    }

    return 0;
 error:
    return -1;
}

int Hashmap_set(Hashmap *map, void *key, void *data)
{
    uint32_t hash = 0;
    DArray *bucket = Hashmap_find_bucket(map, key, 1, &hash);
    check(bucket, "Error can't create bucket");

    HashmapNode *node = Hashmap_node_create(hash, key, data);
    check_mem(node);

    DArray_push(bucket, node);

    // Sort the bucket.
    int rc = DArray_heapsort(bucket, (DArray_compare) map->compare);
    check(rc == 0, "Error sorting bucket");

    return 0;

 error:
    return -1;
}

static inline int Hashmap_get_node(Hashmap *map, uint32_t hash,
                                   DArray *bucket, void *key)
{
    int i = 0;

    for (i = 0; i < DArray_end(bucket); i++) {
        debug("TRY: %d", i);
        HashmapNode *node = DArray_get(bucket, i);
        if (node->hash == hash && map->compare(node->key, key) == 0) {
            return i;
        }
    }

    return -1;
}

void *Hashmap_get(Hashmap *map, void *key)
{
    uint32_t hash = 0;
    DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
    if (!bucket) return NULL;

    int i = Hashmap_get_node(map, hash, bucket, key);
    if (i == -1) return NULL;

    HashmapNode *node = DArray_get(bucket, i);
    check(node != NULL,
          "Failed to get node from bucket when it should exist.");

    return node->data;

 error:
    return NULL;
}

/**
 * Sets key <-> data iff key is not already present in Hashmap.
 */
int Hashmap_set_fucked(Hashmap *map, void *key, void *data)
{
    uint32_t hash = 0;
    DArray *bucket = Hashmap_find_bucket(map, key, 1, &hash);
    check(bucket, "Error can't create bucket");

    int i = Hashmap_get_node(map, hash, bucket, key);
    if (i >= 0) {
        // Element with `key` already exists. Do nothing.
        return 0;
    }

    // Element with `key` does not exist. Add it to Hashmap.
    HashmapNode *node = Hashmap_node_create(hash, key, data);
    check_mem(node);

    DArray_push(bucket, node);

    // Sort the bucket.
    int rc = DArray_heapsort(bucket, (DArray_compare) map->compare);
    check(rc == 0, "Error sorting bucket");

    return 1;
 error:
    return -1;
}

int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb traverse_cb)
{
    int i = 0;
    int j = 0;
    int rc = 0;

    for (i = 0; i < DArray_count(map->buckets); i++) {
        DArray *bucket = DArray_get(map->buckets, i);
        if (bucket) {
            for (j = 0; j < DArray_count(bucket); j++) {
                HashmapNode *node = DArray_get(bucket, j);
                rc = traverse_cb(node);
                if (rc != 0)
                    return rc;
            }
        }
    }

    return 0;
}

/**
 * Returns all keys of the hashmap as a DArray.
 *
 * Use DArray_destroy on the 'keys' returned by this function after
 * use.
 */
DArray *Hashmap_keys(Hashmap *map)
{
    check(map != NULL, "map is NULL");

    DArray *keys = DArray_create(sizeof(void *),
                                 DEFAULT_NUMBER_OF_KEYS);
    check(keys != NULL, "Unable to initialize keys");

    int i = 0;
    int j = 0;

    for (i = 0; i < DArray_count(map->buckets); i++) {
        DArray *bucket = DArray_get(map->buckets, i);
        if (bucket) {
            for (j = 0; j < DArray_count(bucket); j++) {
                HashmapNode *node = DArray_get(bucket, j);

                if (node) {
                    DArray_push(keys, node->key);
                }
            }
        }
    }

    return keys;
 error:
    return NULL;
}

void *Hashmap_delete(Hashmap *map, void *key)
{
    uint32_t hash = 0;
    DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
    if (!bucket)
        return NULL;

    int i = Hashmap_get_node(map, hash, bucket, key);
    if (i == -1)
        return NULL;

    HashmapNode *node = DArray_get(bucket, i);
    void *data = node->data;
    free(node);

    HashmapNode *ending = DArray_pop(bucket);

    if (ending != node) {
        // alright looks like it's not the last one, swap it.
        DArray_set(bucket, i, ending);
    } else {
        // alright looks like it's the last one, destroy bucket.
        check(Hashmap_delete_bucket(map, hash) == 0,
              "Error destroy bucket");
    }

    return data;
 error:
    return NULL;
}