// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)

/*
 * Generic non-thread safe hash map implementation.
 *
 * Copyright (c) 2019 Facebook
 */
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <linux/err.h>
#include "hashmap.h"

/* start with 4 buckets */
#define HASHMAP_MIN_CAP_BITS 2

static void hashmap_add_entry(struct hashmap_entry **pprev,
                              struct hashmap_entry *entry)
{
        entry->next = *pprev;
        *pprev = entry;
}

static void hashmap_del_entry(struct hashmap_entry **pprev,
                              struct hashmap_entry *entry)
{
        *pprev = entry->next;
        entry->next = NULL;
}

void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
                   hashmap_equal_fn equal_fn, void *ctx)
{
        map->hash_fn = hash_fn;
        map->equal_fn = equal_fn;
        map->ctx = ctx;

        map->buckets = NULL;
        map->cap = 0;
        map->cap_bits = 0;
        map->sz = 0;
}

struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
                             hashmap_equal_fn equal_fn,
                             void *ctx)
{
        struct hashmap *map = malloc(sizeof(struct hashmap));

        if (!map)
                return ERR_PTR(-ENOMEM);
        hashmap__init(map, hash_fn, equal_fn, ctx);
        return map;
}

void hashmap__clear(struct hashmap *map)
{
        free(map->buckets);
        map->cap = map->cap_bits = map->sz = 0;
}

void hashmap__free(struct hashmap *map)
{
        if (!map)
                return;

        hashmap__clear(map);
        free(map);
}

size_t hashmap__size(const struct hashmap *map)
{
        return map->sz;
}

size_t hashmap__capacity(const struct hashmap *map)
{
        return map->cap;
}

static bool hashmap_needs_to_grow(struct hashmap *map)
{
        /* grow if empty or more than 75% filled */
        return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
}

static int hashmap_grow(struct hashmap *map)
{
        struct hashmap_entry **new_buckets;
        struct hashmap_entry *cur, *tmp;
        size_t new_cap_bits, new_cap;
        size_t h;
        int bkt;

        new_cap_bits = map->cap_bits + 1;
        if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
                new_cap_bits = HASHMAP_MIN_CAP_BITS;

        new_cap = 1UL << new_cap_bits;
        new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
        if (!new_buckets)
                return -ENOMEM;

        hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
                h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
                hashmap_add_entry(&new_buckets[h], cur);
        }

        map->cap = new_cap;
        map->cap_bits = new_cap_bits;
        free(map->buckets);
        map->buckets = new_buckets;

        return 0;
}

static bool hashmap_find_entry(const struct hashmap *map,
                               const void *key, size_t hash,
                               struct hashmap_entry ***pprev,
                               struct hashmap_entry **entry)
{
        struct hashmap_entry *cur, **prev_ptr;

        if (!map->buckets)
                return false;

        for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
             cur;
             prev_ptr = &cur->next, cur = cur->next) {
                if (map->equal_fn(cur->key, key, map->ctx)) {
                        if (pprev)
                                *pprev = prev_ptr;
                        *entry = cur;
                        return true;
                }
        }

        return false;
}

int hashmap__insert(struct hashmap *map, const void *key, void *value,
                    enum hashmap_insert_strategy strategy,
                    const void **old_key, void **old_value)
{
        struct hashmap_entry *entry;
        size_t h;
        int err;

        if (old_key)
                *old_key = NULL;
        if (old_value)
                *old_value = NULL;

        h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
        if (strategy != HASHMAP_APPEND &&
            hashmap_find_entry(map, key, h, NULL, &entry)) {
                if (old_key)
                        *old_key = entry->key;
                if (old_value)
                        *old_value = entry->value;

                if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
                        entry->key = key;
                        entry->value = value;
                        return 0;
                } else if (strategy == HASHMAP_ADD) {
                        return -EEXIST;
                }
        }

        if (strategy == HASHMAP_UPDATE)
                return -ENOENT;

        if (hashmap_needs_to_grow(map)) {
                err = hashmap_grow(map);
                if (err)
                        return err;
                h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
        }

        entry = malloc(sizeof(struct hashmap_entry));
        if (!entry)
                return -ENOMEM;

        entry->key = key;
        entry->value = value;
        hashmap_add_entry(&map->buckets[h], entry);
        map->sz++;

        return 0;
}

bool hashmap__find(const struct hashmap *map, const void *key, void **value)
{
        struct hashmap_entry *entry;
        size_t h;

        h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
        if (!hashmap_find_entry(map, key, h, NULL, &entry))
                return false;

        if (value)
                *value = entry->value;
        return true;
}

bool hashmap__delete(struct hashmap *map, const void *key,
                     const void **old_key, void **old_value)
{
        struct hashmap_entry **pprev, *entry;
        size_t h;

        h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
        if (!hashmap_find_entry(map, key, h, &pprev, &entry))
                return false;

        if (old_key)
                *old_key = entry->key;
        if (old_value)
                *old_value = entry->value;

        hashmap_del_entry(pprev, entry);
        free(entry);
        map->sz--;

        return true;
}