fhashtable_template.h

Go to the documentation of this file.

 
#ifdef __cplusplus
#ifdef __GNUC__
#define restrict __restrict__
#else
#define restrict
#endif
extern "C" {
#endif
 
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
// macro definitions: {{{

#ifndef PASTE
#define PASTE(a, b) a##b
#endif

#ifndef XPASTE
#define XPASTE(a, b) PASTE(a, b)
#endif

#ifndef JOIN
#define JOIN(a, b) XPASTE(a, XPASTE(_, b))
#endif

#ifndef IS_POW2
#define IS_POW2(X) ((X) != 0 && ((X) & ((X) - 1)) == 0)
#endif

#ifndef FHASHTABLE_EMPTY_SLOT_OFFSET
#define FHASHTABLE_EMPTY_SLOT_OFFSET (UINT32_MAX)
#endif

#ifndef FHASHTABLE_FOR_EACH
#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))
#endif

#ifndef FHASHTABLE_CALC_SIZEOF
#define FHASHTABLE_CALC_SIZEOF(fhashtable_name, capacity) \
    (uint32_t)(offsetof(struct fhashtable_name, slots) + capacity * sizeof(((struct fhashtable_name *)0)->slots[0]))
#endif

#ifndef FHASHTABLE_CALC_SIZEOF_OVERFLOWS
#define FHASHTABLE_CALC_SIZEOF_OVERFLOWS(fhashtable_name, capacity) \
    (capacity                                                       \
     > (UINT32_MAX - offsetof(struct fhashtable_name, slots)) / sizeof(((struct fhashtable_name *)0)->slots[0]))
#endif

#ifndef NAME
#error "Must define NAME."
#else
#define FHASHTABLE_NAME NAME
#endif

#ifndef KEY_TYPE
#define KEY_TYPE int
#define FUNCTION_DEFINITIONS
#define TYPE_DEFINITIONS
#error "Must define KEY_TYPE."
#endif

#ifndef VALUE_TYPE
#define VALUE_TYPE int
#error "Must define VALUE_TYPE."
#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) (0)
#endif

#ifndef FUNCTION_LINKAGE
#define FUNCTION_LINKAGE
#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_SWAP_SLOTS   JOIN(internal, JOIN(FHASHTABLE_NAME, swap_slots))
#define FHASHTABLE_BACKSHIFT    JOIN(internal, JOIN(FHASHTABLE_NAME, backshift))
 
// }}}
 
// type definitions: {{{

#ifdef 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[]; 
};
 
#endif
 
// }}}
 
// function declarations: {{{

FUNCTION_LINKAGE FHASHTABLE_TYPE *JOIN(FHASHTABLE_NAME, init)(FHASHTABLE_TYPE *self, const uint32_t pow2_capacity);

FUNCTION_LINKAGE FHASHTABLE_TYPE *JOIN(FHASHTABLE_NAME, create)(const uint32_t min_capacity);

FUNCTION_LINKAGE void JOIN(FHASHTABLE_NAME, destroy)(FHASHTABLE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FHASHTABLE_NAME, is_empty)(const FHASHTABLE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FHASHTABLE_NAME, is_full)(const FHASHTABLE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FHASHTABLE_NAME, contains_key)(const FHASHTABLE_TYPE *self, const KEY_TYPE key);

FUNCTION_LINKAGE VALUE_TYPE *JOIN(FHASHTABLE_NAME, get_value_mut)(FHASHTABLE_TYPE *self, const KEY_TYPE key);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FHASHTABLE_NAME, get_value)(const FHASHTABLE_TYPE *self, const KEY_TYPE key,
                                                             VALUE_TYPE default_value);

FUNCTION_LINKAGE VALUE_TYPE *JOIN(FHASHTABLE_NAME, search)(FHASHTABLE_TYPE *self, const KEY_TYPE key);

FUNCTION_LINKAGE void JOIN(FHASHTABLE_NAME, insert)(FHASHTABLE_TYPE *self, KEY_TYPE key, VALUE_TYPE value);

FUNCTION_LINKAGE void JOIN(FHASHTABLE_NAME, update)(FHASHTABLE_TYPE *self, KEY_TYPE key, VALUE_TYPE value);

FUNCTION_LINKAGE bool JOIN(FHASHTABLE_NAME, delete)(FHASHTABLE_TYPE *self, const KEY_TYPE key);

FUNCTION_LINKAGE void JOIN(FHASHTABLE_NAME, clear)(FHASHTABLE_TYPE *self);

FUNCTION_LINKAGE void JOIN(FHASHTABLE_NAME, copy)(FHASHTABLE_TYPE *restrict dest_ptr,
                                                  const FHASHTABLE_TYPE *restrict src_ptr);
 
// @}}}
 
// function definitions: {{{

#ifdef FUNCTION_DEFINITIONS
 
#include "round_up_pow2_32.h" // round_up_pow2_32
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE void JOIN(FHASHTABLE_NAME, destroy)(FHASHTABLE_TYPE *self)
{
    assert(self);
 
    free(self);
}
 
FUNCTION_LINKAGE bool JOIN(FHASHTABLE_NAME, is_empty)(const FHASHTABLE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == 0;
}
 
FUNCTION_LINKAGE bool JOIN(FHASHTABLE_NAME, is_full)(const FHASHTABLE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == self->capacity;
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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++;
}
 
FUNCTION_LINKAGE 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;
    }
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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;
}
 
FUNCTION_LINKAGE 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);
 
    uint32_t index;
    KEY_TYPE key;
    VALUE_TYPE value;
    FHASHTABLE_FOR_EACH(src_ptr, index, key, value) {
        JOIN(FHASHTABLE_NAME, insert)(dest_ptr, key, value);
    }
}
 
#endif
 
// }}}
 
// macro undefs: {{{
 
#undef NAME
#undef KEY_TYPE
#undef VALUE_TYPE
#undef KEY_IS_EQUAL
#undef HASH_FUNCTION
#undef FUNCTION_LINKAGE
#undef FUNCTION_DEFINITIONS
#undef TYPE_DEFINITIONS
 
#undef FHASHTABLE_NAME
#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
 
// }}}
 
#ifdef __cplusplus
}
#endif
 
// vim: ft=c fdm=marker