vessel/core/hmap.c

#include "include/conf.h"

#include "include/def.h"
#include "include/hmap.h"
#include "include/thread.h"
#include "include/hashing.h"

#include <wchar.h>
#include <time.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

static const vs_HMapID vs_null_hmap_id = { 0 };

static bool vs_HMap_init_raw(vs_HMap *hmap, const bool safe) {
    if (!vs_Lock_init(&hmap->_lock)) {
        return false;
    }

    if (!safe && !vs_Lock_disable(&hmap->_lock)) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        vs_Lock_destroy(&hmap->_lock);
        return false;
    }

    hmap->entries = VS_CALLOC(VS_HMAP_INITIAL_CAP, sizeof(*hmap->entries));
    if (!hmap->entries) {
        vs_Lock_unlock(&hmap->_lock);
        vs_Lock_destroy(&hmap->_lock);

        return false;
    }

    hmap->_occupied_ents_cap = VS_HMAP_INITIAL_CAP / 2;
    hmap->occupied_ents =
        (vs_HMapEntry **)VS_MALLOC(hmap->_occupied_ents_cap * sizeof(*hmap->occupied_ents));
    if (!hmap->occupied_ents) {
        VS_FREE(hmap->entries);
        vs_Lock_unlock(&hmap->_lock);
        vs_Lock_destroy(&hmap->_lock);
        return false;
    }

    hmap->size = 0;
    hmap->_cap = VS_HMAP_INITIAL_CAP;
    hmap->_id  = 0;

    const uint8_t size = sizeof(*hmap->_siphash64_seed) * 2;
    if (size != vs_get_rand_bytes(hmap->_siphash64_seed, size)) {
        VS_FREE(hmap->entries);
        VS_FREE((void *)hmap->occupied_ents);
        vs_Lock_unlock(&hmap->_lock);
        vs_Lock_destroy(&hmap->_lock);
        return false;
    }

    if (!vs_Lock_unlock(&hmap->_lock)) {
        VS_FREE(hmap->entries);
        VS_FREE((void *)hmap->occupied_ents);
        /* We cannot unlock nor destroy... */
        return false;
    }

    return true;
}

#ifdef VS_WITH_UINT128
static inline uint64_t vs_mod_mul(uint64_t multiplicand, uint64_t multiplier, uint64_t modulus) {
    return (uint64_t)(((unsigned __int128)multiplicand * (unsigned __int128)multiplier) %
                      (unsigned __int128)modulus);
}
#else
static inline uint64_t vs_mod_mul(uint64_t multiplicand, uint64_t multiplier, uint64_t modulus) {
    uint64_t product_result = 0;

    multiplicand %= modulus;

    while (multiplier) {
        if (multiplier & (uint64_t)1) {
            product_result = (product_result + multiplicand) % modulus;
        }

        multiplicand = (multiplicand << (uint64_t)1) % modulus;
        multiplier >>= (uint64_t)1;
    }

    return product_result;
}
#endif

static inline uint64_t vs_mod_exp(uint64_t base, uint64_t exponent, uint64_t modulus) {
    uint64_t power_result = 1;

    base %= modulus;

    while (exponent) {
        if (exponent & (uint64_t)1) {
            power_result = vs_mod_mul(power_result, base, modulus);
        }

        base = vs_mod_mul(base, base, modulus);
        exponent >>= (uint64_t)1;
    }

    return power_result;
}

static inline bool vs_miller_rabin(uint64_t candidate_number) {
    if (candidate_number < 2) {
        return false;
    }
    if (candidate_number < 4) {
        return true;
    }
    if ((candidate_number & (uint64_t)1) == 0) {
        return false;
    }

    uint64_t odd_component       = candidate_number - 1;
    size_t   factor_of_two_count = 0;
    while ((odd_component & (uint64_t)1) == 0) {
        odd_component >>= (uint64_t)1;
        ++factor_of_two_count;
    }

    /* Proven by Jaeschke and verified by Sorenson: For any 64-bit number, checking these bases
     * ensures correct primality. */
    static const uint64_t witness_bases[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

    for (size_t idx = 0; idx < VS_ARRLEN(witness_bases); ++idx) {
        const uint64_t witness = witness_bases[idx];

        if (witness >= candidate_number) {
            continue;
        }

        uint64_t current_power = vs_mod_exp(witness, odd_component, candidate_number);
        if (current_power == 1 || current_power == candidate_number - 1) {
            continue;
        }

        bool is_composite = true;
        for (size_t jdx = 1; jdx < factor_of_two_count; ++jdx) {
            current_power = vs_mod_mul(current_power, current_power, candidate_number);

            if (current_power == candidate_number - 1) {
                is_composite = false;
                break;
            }
        }

        if (is_composite) {
            return false;
        }
    }

    return true;
}

#define VS_HMAP_LARGEST_64BIT_PRIME     ((uint64_t)18446744073709551557ULL)
#define VS_HMAP_LARGEST_64BIT_4K3_PRIME ((uint64_t)18446744073709551427ULL)

#if 0
static inline uint64_t vs_find_next_prime(uint64_t start_value) {
    if (start_value <= 2) {
        return 2;
    }
    if ((start_value & (uint64_t)1) == 0) {
        ++start_value;
    }

    while (!vs_miller_rabin(start_value)) {
        if (start_value >= VS_HMAP_LARGEST_64BIT_PRIME) {
            return VS_HMAP_LARGEST_64BIT_PRIME;
        }

        start_value += 2;
    }

    return start_value;
}
#else
/*
 * CMSC 420 Lecture 14 (UMD) on hashing:
 * https://www.cs.umd.edu/class/fall2020/cmsc420-0201/Lects/lect14-hashing.pdf
 *
 * "If the table size m is a prime number of the form 4k + 3, then quadratic probing will succeed in
 * probing every table entry before repeating an entry."
 */
static inline uint64_t vs_find_next_prime(uint64_t start_value) {
    /* The smallest prime of form 4k+3 is 3 */
    if (start_value <= 3) {
        return 3;
    }

    /* Round start_value up to the next number congruent to 3 mod 4 */
    uint64_t candidate = start_value;
    uint64_t mod4      = candidate % 4;
    if (mod4 != 3) {
        candidate += (3 + 4 - mod4) % 4; /* advance to next 4k+3 number */
    }

    while (true) {
        if (candidate >= VS_HMAP_LARGEST_64BIT_4K3_PRIME) {
            return VS_HMAP_LARGEST_64BIT_4K3_PRIME;
        }

        if (vs_miller_rabin(candidate)) {
            return candidate;
        }

        candidate += 4; /* next number of form 4k+3 */
    }
}
#endif

bool vs_HMapID_is_valid(vs_HMapID hid) { return (hid)._id != 0; }

vs_HMapID vs_HMapID_get(const vs_HMapEntry *entry) {
    vs_HMapID hid = { ._hash = entry->hash, ._id = entry->id };
    return hid;
}

static inline vs_HMapID vs_HMapID_new(size_t hash, size_t eid) {
    vs_HMapID hid = { ._hash = hash, ._id = eid };
    return hid;
}

bool vs_HMap_init(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    hmap->_is_hset = false;
    return vs_HMap_init_raw(hmap, true);
}

bool vs_HMap_init_set(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    hmap->_is_hset = true;
    return vs_HMap_init_raw(hmap, true);
}

bool vs_HMap_init_unsafe(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    hmap->_is_hset = false;
    return vs_HMap_init_raw(hmap, false);
}

bool vs_HMap_init_set_unsafe(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    hmap->_is_hset = true;
    return vs_HMap_init_raw(hmap, false);
}

/* Mainly for performance reasons */
#define VS_HMAP_HASH_INLINE(key, key_length, seed) \
    vs_u64_to_hash_size(                           \
        vs_siphash64(key, key_length, seed, VS_HMAP_SIPHASH_C_ROUNDS, VS_HMAP_SIPHASH_D_ROUNDS))
#define VS_HMAP_PROBE0_INLINE(hash, cap) ((hash) % (cap))

#if 0
#    define VS_HMAP_PROBE_INLINE(index, probe, cap) \
        (((index) + (probe) + (probe) * (probe)) % ((cap)))
#else
/* probe i: index + (-1)^i * (i*i), mod cap */
static inline size_t vs_hmap_probe_inline(size_t index, size_t probe, size_t cap) {
    const size_t offset = (probe * probe) % cap;

    if (probe & (size_t)1) { /* odd probe number: subtract offset */
        return (index + cap - offset) % cap;
    }

    /* even probe number: add offset */
    return (index + offset) % cap;
}
#    define VS_HMAP_PROBE_INLINE(index, probe, cap) vs_hmap_probe_inline(index, probe, cap)
#endif

size_t vs_HMap_hash(const void *key, size_t key_length, const uint64_t seed[2]) {
    return VS_HMAP_HASH_INLINE(key, key_length, seed);
}

size_t vs_HMap_probe(size_t index, size_t probe, size_t cap) {
    return VS_HMAP_PROBE_INLINE(index, probe, cap);
}

size_t vs_HMap_probe0(size_t hash, size_t cap) { return VS_HMAP_PROBE0_INLINE(hash, cap); }

bool vs_HMap_rehash(vs_HMap *hmap, bool force) {
    if (!hmap) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return false;
    }

    if (!force && ((float)hmap->size / (float)hmap->_cap) < VS_HMAP_LOAD_FACTOR) {
        return vs_Lock_unlock(&hmap->_lock);
    }

    size_t new_cap =
        (size_t)vs_find_next_prime((size_t)((double)hmap->_cap * VS_HMAP_MULTIPLIER) + 1);

    /* Playing it safe for clarity: calloc() for future realloc() */
    vs_HMapEntry *new_entries = VS_MALLOC(sizeof(*new_entries) * new_cap);
    if (!new_entries) {
        vs_Lock_unlock(&hmap->_lock);
        return false;
    }
    memset(new_entries, 0, sizeof(*new_entries) * new_cap);

    vs_HMapEntry **new_occupied_ents =
        (vs_HMapEntry **)VS_MALLOC(hmap->_occupied_ents_cap * sizeof(*new_occupied_ents));
    if (!new_occupied_ents) {
        vs_Lock_unlock(&hmap->_lock);
        VS_FREE(new_entries);
        return false;
    }

    for (uint8_t retry = 0; retry < 5 && new_cap < SIZE_MAX - 1 && new_cap > hmap->_cap; ++retry) {
        size_t size     = 0;
        bool   rehashed = true;

        for (size_t idx = 0; idx < hmap->size; ++idx) {
            const vs_HMapEntry *old_entry = hmap->occupied_ents[idx];

            /* Always occupied */
            size_t probe = 0;
            size_t index = VS_HMAP_PROBE0_INLINE(old_entry->hash, new_cap);

            while (probe < new_cap && new_entries[index]._occupied) {
                ++probe;
                index = VS_HMAP_PROBE_INLINE(index, probe, new_cap);
            }

            if (probe == new_cap) {
                /* Collision: Increase hash space, probably resolving collisions */
                new_cap = (size_t)vs_find_next_prime(
                    (size_t)((double)new_cap * VS_HMAP_MULTIPLIER_COLLISION));

                /* Reallocate MOARRR entries */
                vs_HMapEntry *col_new_entries =
                    VS_REALLOC(new_entries, sizeof(*new_entries) * new_cap);
                if (!col_new_entries) {
                    vs_Lock_unlock(&hmap->_lock);

                    VS_FREE(new_entries);
                    VS_FREE((void *)new_occupied_ents);
                    return false;
                }
                memset(col_new_entries, 0, sizeof(*new_entries) * new_cap);
                new_entries = col_new_entries;

                rehashed = false;
                break;
            }

            new_entries[index]                    = *old_entry;
            new_entries[index]._occupied_ents_idx = size;

            new_occupied_ents[size++] = &new_entries[index];
        }

        if (rehashed) {
            VS_FREE(hmap->entries);
            VS_FREE((void *)hmap->occupied_ents);

            hmap->entries       = new_entries;
            hmap->occupied_ents = new_occupied_ents;
            hmap->_cap          = new_cap;
            hmap->size          = size;

            return vs_Lock_unlock(&hmap->_lock);
        }
    }

    vs_Lock_unlock(&hmap->_lock);

    VS_FREE(new_entries);
    VS_FREE((void *)new_occupied_ents);

    return false;
}

vs_HMapID vs_HMap_insertn(vs_HMap *hmap, const void *key, size_t len, void *value) {
    if (!hmap || !key || len < 1 || !vs_HMap_rehash(hmap, false)) {
        return vs_null_hmap_id;
    }

    if (hmap->_is_hset) {
        value = NULL;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return vs_null_hmap_id;
    }

    /* Checking if we *can* even insert anything. */

    if (hmap->size >= SIZE_MAX - 1) {
        vs_Lock_unlock(&hmap->_lock);
        return vs_null_hmap_id;
    }

    for (uint8_t retry = 0; retry < 5; ++retry) {
        const size_t hash  = VS_HMAP_HASH_INLINE(key, len, hmap->_siphash64_seed);
        size_t       index = VS_HMAP_PROBE0_INLINE(hash, hmap->_cap);

        size_t probe = 0;

        while (probe < hmap->_cap) {
            vs_HMapEntry *entry = &hmap->entries[index];

            if (!entry->_occupied) {
                /* Found an empty entry, insert here */
                void *dup_key = vs_dupmem(key, len);

                if (!dup_key) {
                    vs_Lock_unlock(&hmap->_lock);
                    return vs_null_hmap_id;
                }

                /* Reallocate occupied entries array */
                if (hmap->size >= hmap->_occupied_ents_cap) {
                    hmap->_occupied_ents_cap =
                        (size_t)((double)hmap->_occupied_ents_cap * VS_HMAP_OCCPIED_MULTIPLIER) + 1;

                    vs_HMapEntry **realloced_occupied_ents = (vs_HMapEntry **)VS_REALLOC(
                        (void *)hmap->occupied_ents,
                        hmap->_occupied_ents_cap * sizeof(*hmap->occupied_ents));

                    if (!realloced_occupied_ents) {
                        VS_FREE(dup_key);
                        vs_Lock_unlock(&hmap->_lock);
                        return vs_null_hmap_id;
                    }

                    hmap->occupied_ents = realloced_occupied_ents;
                }

                entry->key                = dup_key;
                entry->key_length         = len;
                entry->value              = value;
                entry->_occupied          = true;
                entry->hash               = hash;
                entry->_occupied_ents_idx = hmap->size;

                if ((++hmap->_id) == 0) {
                    hmap->_id = 1;
                }

                const size_t eid = hmap->_id;
                entry->id        = eid;

                hmap->occupied_ents[hmap->size++] = entry;

                return vs_Lock_unlock(&hmap->_lock) ? vs_HMapID_new(hash, eid) : vs_null_hmap_id;
            }

            if (entry->hash == hash && entry->key_length == len &&
                memcmp(entry->key, key, len) == 0) {
                entry->value     = value;
                const size_t eid = entry->id;
                return vs_Lock_unlock(&hmap->_lock) ? vs_HMapID_new(hash, eid) : vs_null_hmap_id;
            }

            ++probe;
            index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
        }

        /* Were not able to find a spot to insert: resolve colision (increase hash space). */
        vs_Lock_unlock(&hmap->_lock);
        if (!vs_HMap_rehash(hmap, true)) {
            return vs_null_hmap_id;
        }
        vs_Lock_lock(&hmap->_lock);
    }

    vs_Lock_unlock(&hmap->_lock);
    return vs_null_hmap_id;
}

vs_HMapID vs_HMap_insert(vs_HMap *hmap, const char *key, void *value) {
    if (!hmap || !key || !*key || !vs_HMap_rehash(hmap, false)) {
        return vs_null_hmap_id;
    }

    return vs_HMap_insertn(hmap, key, strlen(key), value);
}

bool vs_HMap_deleten(vs_HMap *hmap, const void *key, size_t len) {
    if (!hmap || !key || len < 1) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return false;
    }

    const size_t hash = VS_HMAP_HASH_INLINE(key, len, hmap->_siphash64_seed);

    size_t index = VS_HMAP_PROBE0_INLINE(hash, hmap->_cap);
    size_t probe = 0;

    while (probe < hmap->_cap) {
        vs_HMapEntry *entry = &hmap->entries[index];

        if (entry->_occupied && entry->hash == hash && entry->key_length == len &&
            memcmp(entry->key, key, len) == 0) {
            VS_FREE(entry->key);

            const size_t new_idx = entry->_occupied_ents_idx;
            hmap->occupied_ents[new_idx] =
                hmap->occupied_ents[--hmap->size];                      /* Move last element */
            hmap->occupied_ents[new_idx]->_occupied_ents_idx = new_idx; /* Update order */

            entry->_occupied = false;

            return vs_Lock_unlock(&hmap->_lock);
        }

        ++probe;
        index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
    }

    vs_Lock_unlock(&hmap->_lock);
    return false;
}

bool vs_HMap_delete(vs_HMap *hmap, const char *key) {
    if (!hmap || !key || !*key) {
        return false;
    }

    return vs_HMap_deleten(hmap, key, strlen(key));
}

bool vs_HMap_delete_id(vs_HMap *hmap, vs_HMapID hid) {
    if (!hmap || !vs_HMapID_is_valid(hid)) {
        return false;
    }

    size_t index = VS_HMAP_PROBE0_INLINE(hid._hash, hmap->_cap);
    size_t probe = 0;

    while (probe < hmap->_cap) {
        vs_HMapEntry *entry = &hmap->entries[index];

        if (entry->_occupied && entry->hash == hid._hash && entry->id == hid._id) {
            VS_FREE(entry->key);

            const size_t new_idx = entry->_occupied_ents_idx;
            hmap->occupied_ents[new_idx] =
                hmap->occupied_ents[--hmap->size];                      /* Move last element */
            hmap->occupied_ents[new_idx]->_occupied_ents_idx = new_idx; /* Update order */

            entry->_occupied = false;

            return vs_Lock_unlock(&hmap->_lock);
        }

        ++probe;
        index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
    }

    vs_Lock_unlock(&hmap->_lock);
    return false;
}

vs_HMapEntry *vs_HMap_findn(vs_HMap *hmap, const void *key, size_t len) {
    if (!hmap || !key || len == 0) {
        return NULL;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return NULL;
    }

    const size_t hash = VS_HMAP_HASH_INLINE(key, len, hmap->_siphash64_seed);

    size_t index = VS_HMAP_PROBE0_INLINE(hash, hmap->_cap);
    size_t probe = 0;

    while (probe < hmap->_cap && hmap->entries[index]._occupied) {
        vs_HMapEntry *entry = &hmap->entries[index];

        if (entry->hash == hash && entry->key_length == len && memcmp(entry->key, key, len) == 0) {
            return vs_Lock_unlock(&hmap->_lock) ? entry : NULL;
        }

        ++probe;
        index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
    }

    vs_Lock_unlock(&hmap->_lock);
    return NULL;
}

vs_HMapEntry *vs_HMap_find(vs_HMap *hmap, const char *key) {
    if (!hmap || !key || !*key) {
        return NULL;
    }

    return vs_HMap_findn(hmap, key, strlen(key));
}

vs_HMapEntry *vs_HMap_find_id(vs_HMap *hmap, vs_HMapID hid) {
    if (!hmap || !vs_HMapID_is_valid(hid)) {
        return NULL;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return NULL;
    }

    size_t index = VS_HMAP_PROBE0_INLINE(hid._hash, hmap->_cap);
    size_t probe = 0;

    while (probe < hmap->_cap && hmap->entries[index]._occupied) {
        vs_HMapEntry *entry = &hmap->entries[index];

        if (entry->hash == hid._hash && entry->id == hid._id) {
            return vs_Lock_unlock(&hmap->_lock) ? entry : NULL;
        }

        ++probe;
        index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
    }

    vs_Lock_unlock(&hmap->_lock);
    return NULL;
}

const vs_HMapEntry *vs_HMap_findn_unsafe(const vs_HMap *hmap, const void *key, size_t len) {
    if (!hmap || !key || len == 0) {
        return NULL;
    }

    const size_t hash = VS_HMAP_HASH_INLINE(key, len, hmap->_siphash64_seed);

    size_t index = VS_HMAP_PROBE0_INLINE(hash, hmap->_cap);
    size_t probe = 0;

    while (probe < hmap->_cap && hmap->entries[index]._occupied) {
        vs_HMapEntry *entry = &hmap->entries[index];

        if (entry->hash == hash && entry->key_length == len && memcmp(entry->key, key, len) == 0) {
            return entry;
        }

        ++probe;
        index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
    }

    return NULL;
}

const vs_HMapEntry *vs_HMap_find_unsafe(const vs_HMap *hmap, const char *key) {
    if (!hmap || !key || !*key) {
        return NULL;
    }

    return vs_HMap_findn_unsafe(hmap, key, strlen(key));
}

const vs_HMapEntry *vs_HMap_find_id_unsafe(const vs_HMap *hmap, vs_HMapID hid) {
    if (!hmap || !vs_HMapID_is_valid(hid)) {
        return NULL;
    }

    size_t index = VS_HMAP_PROBE0_INLINE(hid._hash, hmap->_cap);
    size_t probe = 0;

    while (probe < hmap->_cap && hmap->entries[index]._occupied) {
        vs_HMapEntry *entry = &hmap->entries[index];

        if (entry->hash == hid._hash && entry->id == hid._id) {
            return entry;
        }

        ++probe;
        index = VS_HMAP_PROBE_INLINE(index, probe, hmap->_cap);
    }

    return NULL;
}

vs_HMapEntry *vs_HMap_find_val(vs_HMap *hmap, const void *val, size_t *counter) {
    if (!hmap || hmap->_is_hset) {
        return NULL;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return NULL;
    }

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        vs_HMapEntry *entry = hmap->occupied_ents[idx];

        if (entry->value == val) {
            if (counter && *counter != 0) {
                --(*counter);
                continue;
            }

            return vs_Lock_unlock(&hmap->_lock) ? entry : NULL;
        }
    }

    vs_Lock_unlock(&hmap->_lock);
    return NULL;
}

const vs_HMapEntry *vs_HMap_find_val_unsafe(const vs_HMap *hmap, const void *val, size_t *counter) {
    if (!hmap || hmap->_is_hset) {
        return NULL;
    }

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        vs_HMapEntry *entry = hmap->occupied_ents[idx];

        if (entry->value == val) {
            if (counter && *counter != 0) {
                --(*counter);
                continue;
            }

            return entry;
        }
    }

    return NULL;
}

bool vs_HMap_clear(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return false;
    }

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        vs_HMapEntry *entry = hmap->occupied_ents[idx];
        VS_FREE(entry->key);
        entry->_occupied = false;
    }

    hmap->size = 0;

    return vs_Lock_unlock(&hmap->_lock);
}

/* Repeating the logic to not double the time from O(n) to O(2n) (to be fair
 * they are the same as O(2n) = O(n), but the n is double as large, so no) */

bool vs_HMap_clear_free(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return false;
    }

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        vs_HMapEntry *entry = hmap->occupied_ents[idx];

        VS_FREE(entry->key);
        if (entry->value) {
            VS_FREE(entry->value);
        }
        entry->_occupied = false;
    }

    hmap->size = 0;
    return vs_Lock_unlock(&hmap->_lock);
}

bool vs_HMap_destroy(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return false;
    }

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        VS_FREE(hmap->occupied_ents[idx]->key);
    }

    VS_FREE(hmap->entries);
    VS_FREE((void *)hmap->occupied_ents);

    const bool unlocked       = vs_Lock_unlock(&hmap->_lock);
    const bool lock_destroyed = vs_Lock_destroy(&hmap->_lock);

    return unlocked && lock_destroyed;
}

bool vs_HMap_destroy_free(vs_HMap *hmap) {
    if (!hmap) {
        return false;
    }

    if (!vs_Lock_lock(&hmap->_lock)) {
        return false;
    }

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        if (hmap->occupied_ents[idx]->value) {
            VS_FREE(hmap->occupied_ents[idx]->value);
        }
    }

    const bool unlocked  = vs_Lock_unlock(&hmap->_lock);
    const bool destroyed = vs_HMap_destroy(hmap);

    return unlocked && destroyed;
}

void vs_HMap_print_as_str(const vs_HMap *hmap) {
    /* We don't need to lock it as it's mainly a debugging function. */

    (void)fputs(hmap->_is_hset ? "{" : "{\n", stdout);

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        const vs_HMapEntry *entry = hmap->occupied_ents[idx];

        if (hmap->_is_hset) {
            printf("\"%s\" (%zu)%s",
                   (const char *)entry->key,
                   entry->id,
                   idx == hmap->size - 1 ? "" : ", ");
        } else {
            if (entry->value) {
                printf("    \"%s\" (%zu): \"%s\",\n",
                       (const char *)entry->key,
                       entry->id,
                       (const char *)entry->value);
            } else {
                printf("    \"%s\" (%zu): null,\n", (const char *)entry->key, entry->id);
            }
        }
    }

    puts("}");
}

void vs_HMap_print_as_wstr(const vs_HMap *hmap) {
    /* We don't need to lock it as it's mainly a debugging function. */

    (void)fputs(hmap->_is_hset ? "{" : "{\n", stdout);

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        const vs_HMapEntry *entry = hmap->occupied_ents[idx];

        if (hmap->_is_hset) {
            printf("\"%s\" (%zu)%s",
                   (const char *)entry->key,
                   entry->id,
                   idx == hmap->size - 1 ? "" : ", ");
        } else {
            if (entry->value) {
                printf("    \"%s\" (%zu): \"%ls\",\n",
                       (const char *)entry->key,
                       entry->id,
                       (const wchar_t *)entry->value);
            } else {
                printf("    \"%s\" (%zu): null,\n", (const char *)entry->key, entry->id);
            }
        }
    }

    puts("}");
}

void vs_HMap_print_as_ptr(const vs_HMap *hmap) {
    /* We don't need to lock it as it's mainly a debugging function. */

    (void)fputs(hmap->_is_hset ? "{" : "{\n", stdout);

    for (size_t idx = 0; idx < hmap->size; ++idx) {
        const vs_HMapEntry *entry = hmap->occupied_ents[idx];

        if (hmap->_is_hset) {
            printf("\"%s\" (%zu)%s",
                   (const char *)entry->key,
                   entry->id,
                   idx == hmap->size - 1 ? "" : ", ");
        } else {
            printf("    \"%s\" (%zu): %p,\n", (const char *)entry->key, entry->id, entry->value);
        }
    }

    puts("}");
}