fhashtable.h

Go to the documentation of this file.

/*  fhashtable.h
 *
 *  Copyright (C) 2023 abxh
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *  See the file LICENSE included with this distribution for more
 *  information. */
 
// macro definitions: {{{
 
#ifndef FHASHTABLE_H
#define FHASHTABLE_H
 
#include "fnvhash.h"       // fnvhash_32, fnvhash_32_str
#include "is_pow2.h"       // is_pow2
#include "murmurhash.h"    // murmur_32
#include "paste.h"         // PASTE, XPASTE, JOIN
#include "round_up_pow2.h" // round_up_pow2_32
 
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
#define FHASHTABLE_EMPTY_SLOT_OFFSET (UINT32_MAX)
 
#define fhashtable_for_each(self, index, key_, value_)                    \
    for ((index) = 0; (index) < (self)->capacity; (index)++)              \
        if ((self)->slots[(index)].offset != FHASHTABLE_EMPTY_SLOT_OFFSET \
            && ((key_) = (self)->slots[(index)].key, (value_) = (self)->slots[(index)].value, true))
 
#define fhashtable_calc_sizeof(fhashtable_name, capacity) \
    (uint32_t)(offsetof(struct fhashtable_name, slots) + capacity * sizeof(((struct fhashtable_name *)0)->slots[0]))
 
#define fhashtable_calc_sizeof_overflows(fhashtable_name, capacity) \
    (capacity                                                       \
     > (UINT32_MAX - offsetof(struct fhashtable_name, slots)) / sizeof(((struct fhashtable_name *)0)->slots[0]))
 
#endif // FHASHTABLE_H
 
#ifndef NAME
#error "Must define NAME."
#define NAME fhashtable
#else
#define FHASHTABLE_NAME NAME
#endif
 
#ifndef KEY_TYPE
#error "Must define KEY_TYPE."
#define KEY_TYPE int
#endif
 
#ifndef VALUE_TYPE
#error "Must define VALUE_TYPE."
#define VALUE_TYPE int
#endif
 
#ifndef KEY_IS_EQUAL
#error "Must define KEY_IS_EQUAL."
#define KEY_IS_EQUAL(a, b) ((a) == (b))
#endif
 
#ifndef HASH_FUNCTION
#error "Must define HASH_FUNCTION."
#define HASH_FUNCTION(key) (murmur3_32((uint8_t *)&(key), sizeof(KEY_TYPE), 0))
#endif
 
#define FHASHTABLE_TYPE         struct FHASHTABLE_NAME
#define FHASHTABLE_SLOT_TYPE    struct JOIN(FHASHTABLE_NAME, slot)
#define FHASHTABLE_SLOT         JOIN(FHASHTABLE_NAME, slot)
#define FHASHTABLE_INIT         JOIN(FHASHTABLE_NAME, init)
#define FHASHTABLE_IS_FULL      JOIN(FHASHTABLE_NAME, is_full)
#define FHASHTABLE_CONTAINS_KEY JOIN(FHASHTABLE_NAME, contains_key)
#define FHASHTABLE_CALC_SIZEOF  JOIN(FHASHTABLE_NAME, calc_sizeof)
#define FHASHTABLE_SWAP_SLOTS   JOIN(internal, JOIN(FHASHTABLE_NAME, swap_slots))
#define FHASHTABLE_BACKSHIFT    JOIN(internal, JOIN(FHASHTABLE_NAME, backshift))
 
// }}}
 
// type definitions: {{{
 
struct JOIN(FHASHTABLE_NAME, slot) {
    uint32_t offset;  
    KEY_TYPE key;     
    VALUE_TYPE value; 
};
 
struct FHASHTABLE_NAME {
    uint32_t count;               
    uint32_t capacity;            
    FHASHTABLE_SLOT_TYPE slots[]; 
};
 
// }}}
 
// function definitions: {{{
 
static inline FHASHTABLE_TYPE *JOIN(FHASHTABLE_NAME, init)(FHASHTABLE_TYPE *self, const uint32_t pow2_capacity)
{
    assert(self);
    assert(is_pow2(pow2_capacity));
 
    self->count = 0;
    self->capacity = pow2_capacity;
 
    for (uint32_t i = 0; i < self->capacity; i++) {
        self->slots[i].offset = FHASHTABLE_EMPTY_SLOT_OFFSET;
    }
 
    return self;
}
 
static inline FHASHTABLE_TYPE *JOIN(FHASHTABLE_NAME, create)(const uint32_t min_capacity)
{
    if (min_capacity == 0 || min_capacity > UINT32_MAX / 2 + 1) {
        return NULL;
    }
 
    const uint32_t capacity = round_up_pow2_32(min_capacity);
 
    if (fhashtable_calc_sizeof_overflows(FHASHTABLE_NAME, capacity)) {
        return NULL;
    }
 
    const uint32_t size = fhashtable_calc_sizeof(FHASHTABLE_NAME, capacity);
 
    FHASHTABLE_TYPE *self = (FHASHTABLE_TYPE *)calloc(1, size);
 
    if (!self) {
        return NULL;
    }
 
    FHASHTABLE_INIT(self, capacity);
 
    return self;
}
 
static inline void JOIN(FHASHTABLE_NAME, destroy)(FHASHTABLE_TYPE *self)
{
    assert(self);
 
    free(self);
}
 
static inline bool JOIN(FHASHTABLE_NAME, is_empty)(const FHASHTABLE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == 0;
}
 
static inline bool JOIN(FHASHTABLE_NAME, is_full)(const FHASHTABLE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == self->capacity;
}
 
static inline bool JOIN(FHASHTABLE_NAME, contains_key)(const FHASHTABLE_TYPE *self, const KEY_TYPE key)
{
    assert(self != NULL);
 
    const uint32_t key_hash = HASH_FUNCTION(key);
    const uint32_t index_mask = self->capacity - 1;
 
    uint32_t index = key_hash & index_mask;
    uint32_t max_possible_offset = 0;
 
    while (true) {
        const bool not_empty = self->slots[index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        const bool below_max = max_possible_offset <= self->slots[index].offset;
 
        if (!(not_empty && below_max)) {
            break;
        }
 
        if (KEY_IS_EQUAL(self->slots[index].key, key)) {
            return true;
        }
 
        index++;
        index &= index_mask;
        max_possible_offset++;
    }
    return false;
}
 
static inline VALUE_TYPE *JOIN(FHASHTABLE_NAME, get_value_mut)(FHASHTABLE_TYPE *self, const KEY_TYPE key)
{
    assert(self != NULL);
 
    const uint32_t key_hash = HASH_FUNCTION(key);
    const uint32_t index_mask = self->capacity - 1;
 
    uint32_t index = key_hash & index_mask;
    uint32_t max_possible_offset = 0;
 
    while (true) {
        const bool not_empty = self->slots[index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        const bool below_max = max_possible_offset <= self->slots[index].offset;
 
        if (!(not_empty && below_max)) {
            break;
        }
 
        if (KEY_IS_EQUAL(self->slots[index].key, key)) {
            return &self->slots[index].value;
        }
 
        index++;
        index &= index_mask;
        max_possible_offset++;
    }
    return NULL;
}
 
static inline VALUE_TYPE JOIN(FHASHTABLE_NAME, get_value)(const FHASHTABLE_TYPE *self, const KEY_TYPE key,
                                                          VALUE_TYPE default_value)
{
    assert(self != NULL);
 
    const uint32_t key_hash = HASH_FUNCTION(key);
    const uint32_t index_mask = self->capacity - 1;
 
    uint32_t index = key_hash & index_mask;
    uint32_t max_possible_offset = 0;
 
    while (true) {
        const bool not_empty = self->slots[index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        const bool below_max = max_possible_offset <= self->slots[index].offset;
 
        if (!(not_empty && below_max)) {
            break;
        }
 
        if (KEY_IS_EQUAL(self->slots[index].key, key)) {
            return self->slots[index].value;
        }
 
        index++;
        index &= index_mask;
        max_possible_offset++;
    }
    return default_value;
}
 
static inline VALUE_TYPE *JOIN(FHASHTABLE_NAME, search)(FHASHTABLE_TYPE *self, const KEY_TYPE key)
{
    return JOIN(FHASHTABLE_NAME, get_value_mut)(self, key);
}
 
static inline void JOIN(internal, JOIN(FHASHTABLE_NAME, swap_slots))(FHASHTABLE_SLOT_TYPE *a, FHASHTABLE_SLOT_TYPE *b)
{
    FHASHTABLE_SLOT_TYPE temp = *a;
    *a = *b;
    *b = temp;
}
 
static inline void JOIN(FHASHTABLE_NAME, insert)(FHASHTABLE_TYPE *self, KEY_TYPE key, VALUE_TYPE value)
{
    assert(self != NULL);
    assert(FHASHTABLE_CONTAINS_KEY(self, key) == false);
 
    const uint32_t index_mask = self->capacity - 1;
    const uint32_t key_hash = HASH_FUNCTION(key);
 
    uint32_t index = key_hash & index_mask;
    FHASHTABLE_SLOT_TYPE current_slot = {.offset = 0, .key = key, .value = value};
 
    while (true) {
        const bool not_empty = self->slots[index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        if (!not_empty) {
            break;
        }
 
        if (current_slot.offset > self->slots[index].offset) {
            FHASHTABLE_SWAP_SLOTS(&self->slots[index], &current_slot);
        }
 
        index++;
        index &= index_mask;
        current_slot.offset++;
    }
    self->slots[index] = current_slot;
    self->count++;
}
 
static inline void JOIN(FHASHTABLE_NAME, update)(FHASHTABLE_TYPE *self, KEY_TYPE key, VALUE_TYPE value)
{
    assert(self != NULL);
 
    const uint32_t index_mask = self->capacity - 1;
    const uint32_t key_hash = HASH_FUNCTION(key);
 
    uint32_t index = key_hash & index_mask;
    FHASHTABLE_SLOT_TYPE current_slot = {.offset = 0, .key = key, .value = value};
 
    while (true) {
        const bool not_empty = self->slots[index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        if (!not_empty) {
            break;
        }
 
        const bool offset_is_same = current_slot.offset == self->slots[index].offset;
 
        const bool key_is_equal = KEY_IS_EQUAL(current_slot.key, self->slots[index].key);
 
        if (offset_is_same && key_is_equal) {
            self->slots[index].value = current_slot.value;
            return;
        }
 
        if (current_slot.offset > self->slots[index].offset) {
            FHASHTABLE_SWAP_SLOTS(&current_slot, &self->slots[index]);
        }
 
        index++;
        index &= index_mask;
        current_slot.offset++;
    }
 
    self->slots[index] = current_slot;
    self->count++;
}
 
static inline void JOIN(internal, JOIN(FHASHTABLE_NAME, backshift))(FHASHTABLE_TYPE *self, const uint32_t index_mask,
                                                                    uint32_t index)
{
    assert(self);
 
    uint32_t next_index = (index + 1) & index_mask;
 
    while (true) {
        const bool not_empty = self->slots[next_index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        const bool offset_is_non_zero = self->slots[next_index].offset > 0;
 
        if (!(not_empty && offset_is_non_zero)) {
            break;
        }
 
        self->slots[index] = self->slots[next_index];
        self->slots[index].offset--;
 
        self->slots[next_index].offset = FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        index = next_index;
        next_index = (index + 1) & index_mask;
    }
}
 
static inline bool JOIN(FHASHTABLE_NAME, delete)(FHASHTABLE_TYPE *self, const KEY_TYPE key)
{
    assert(self != NULL);
 
    const uint32_t index_mask = self->capacity - 1;
    const uint32_t key_hash = HASH_FUNCTION(key);
 
    uint32_t index = key_hash & index_mask;
    uint32_t max_possible_offset = 0;
 
    while (true) {
        const bool not_empty = self->slots[index].offset != FHASHTABLE_EMPTY_SLOT_OFFSET;
 
        const bool below_max = max_possible_offset <= self->slots[index].offset;
 
        if (!(not_empty && below_max)) {
            break;
        }
 
        const bool key_is_equal = KEY_IS_EQUAL(key, self->slots[index].key);
 
        if (!key_is_equal) {
            index = (index + 1) & index_mask;
            max_possible_offset++;
            continue;
        }
 
        self->slots[index].offset = FHASHTABLE_EMPTY_SLOT_OFFSET;
        self->count--;
 
        FHASHTABLE_BACKSHIFT(self, index_mask, index);
 
        return true;
    }
    return false;
}
 
static inline void JOIN(FHASHTABLE_NAME, clear)(FHASHTABLE_TYPE *self)
{
    assert(self != NULL);
 
    for (uint32_t i = 0; i < self->capacity; i++) {
        self->slots[i].offset = FHASHTABLE_EMPTY_SLOT_OFFSET;
    }
    self->count = 0;
}
 
static inline void JOIN(FHASHTABLE_NAME, copy)(FHASHTABLE_TYPE *restrict dest_ptr,
                                               const FHASHTABLE_TYPE *restrict src_ptr)
{
    assert(src_ptr != NULL);
    assert(dest_ptr != NULL);
    assert(src_ptr->capacity <= dest_ptr->capacity);
    assert(dest_ptr->count == 0);
 
    for (uint32_t i = 0; i < src_ptr->capacity; i++) {
        dest_ptr->slots[i] = src_ptr->slots[i];
    }
 
    dest_ptr->count = src_ptr->count;
}
 
// }}}
 
// macro undefs: {{{
 
#undef NAME
#undef KEY_TYPE
#undef VALUE_TYPE
#undef KEY_IS_EQUAL
#undef HASH_FUNCTION
 
#undef FHASHTABLE_TYPE
#undef FHASHTABLE_SLOT_TYPE
#undef FHASHTABLE_INIT
#undef FHASHTABLE_IS_FULL
#undef FHASHTABLE_CONTAINS_KEY
#undef FHASHTABLE_CALC_SIZEOF
#undef FHASHTABLE_SWAP_SLOTS
#undef FHASHTABLE_BACKSHIFT
 
// }}}
 
// vim: ft=c fdm=marker