61#define FHASHTABLE_EMPTY_SLOT_OFFSET (UINT32_MAX)
75#define fhashtable_for_each(self, index, key_, value_) \
76 for ((index) = 0; (index) < (self)->capacity; (index)++) \
77 if ((self)->slots[(index)].offset != FHASHTABLE_EMPTY_SLOT_OFFSET \
78 && ((key_) = (self)->slots[(index)].key, (value_) = (self)->slots[(index)].value, true))
90#define fhashtable_calc_sizeof(fhashtable_name, capacity) \
91 (uint32_t)(offsetof(struct fhashtable_name, slots) + capacity * sizeof(((struct fhashtable_name *)0)->slots[0]))
103#define fhashtable_calc_sizeof_overflows(fhashtable_name, capacity) \
105 > (UINT32_MAX - offsetof(struct fhashtable_name, slots)) / sizeof(((struct fhashtable_name *)0)->slots[0]))
117#error "Must define NAME."
118#define NAME fhashtable
120#define FHASHTABLE_NAME NAME
131#error "Must define KEY_TYPE."
143#error "Must define VALUE_TYPE."
144#define VALUE_TYPE int
165#error "Must define KEY_IS_EQUAL."
166#define KEY_IS_EQUAL(a, b) ((a) == (b))
180#error "Must define HASH_FUNCTION."
181#define HASH_FUNCTION(key) (murmur3_32((uint8_t *)&(key), sizeof(KEY_TYPE), 0))
185#define FHASHTABLE_TYPE struct FHASHTABLE_NAME
186#define FHASHTABLE_SLOT_TYPE struct JOIN(FHASHTABLE_NAME, slot)
187#define FHASHTABLE_SLOT JOIN(FHASHTABLE_NAME, slot)
188#define FHASHTABLE_INIT JOIN(FHASHTABLE_NAME, init)
189#define FHASHTABLE_IS_FULL JOIN(FHASHTABLE_NAME, is_full)
190#define FHASHTABLE_CONTAINS_KEY JOIN(FHASHTABLE_NAME, contains_key)
191#define FHASHTABLE_CALC_SIZEOF JOIN(FHASHTABLE_NAME, calc_sizeof)
192#define FHASHTABLE_SWAP_SLOTS JOIN(internal, JOIN(FHASHTABLE_NAME, swap_slots))
193#define FHASHTABLE_BACKSHIFT JOIN(internal, JOIN(FHASHTABLE_NAME, backshift))
204struct JOIN(FHASHTABLE_NAME, slot) {
214struct FHASHTABLE_NAME {
217 FHASHTABLE_SLOT_TYPE slots[];
230static inline FHASHTABLE_TYPE *
JOIN(FHASHTABLE_NAME, init)(FHASHTABLE_TYPE *self,
const uint32_t pow2_capacity)
233 assert(
is_pow2(pow2_capacity));
236 self->capacity = pow2_capacity;
238 for (uint32_t i = 0; i < self->capacity; i++) {
256static inline FHASHTABLE_TYPE *
JOIN(FHASHTABLE_NAME, create)(
const uint32_t min_capacity)
258 if (min_capacity == 0 || min_capacity > UINT32_MAX / 2 + 1) {
270 FHASHTABLE_TYPE *self = (FHASHTABLE_TYPE *)calloc(1, size);
276 FHASHTABLE_INIT(self, capacity);
289static inline void JOIN(FHASHTABLE_NAME, destroy)(FHASHTABLE_TYPE *self)
303static inline bool JOIN(FHASHTABLE_NAME, is_empty)(
const FHASHTABLE_TYPE *self)
305 assert(self != NULL);
307 return self->count == 0;
317static inline bool JOIN(FHASHTABLE_NAME, is_full)(
const FHASHTABLE_TYPE *self)
319 assert(self != NULL);
321 return self->count == self->capacity;
332static inline bool JOIN(FHASHTABLE_NAME, contains_key)(
const FHASHTABLE_TYPE *self,
const KEY_TYPE key)
334 assert(self != NULL);
337 const uint32_t index_mask = self->capacity - 1;
339 uint32_t index = key_hash & index_mask;
340 uint32_t max_possible_offset = 0;
345 const bool below_max = max_possible_offset <= self->slots[index].offset;
347 if (!(not_empty && below_max)) {
357 max_possible_offset++;
377 assert(self != NULL);
380 const uint32_t index_mask = self->capacity - 1;
382 uint32_t index = key_hash & index_mask;
383 uint32_t max_possible_offset = 0;
388 const bool below_max = max_possible_offset <= self->slots[index].offset;
390 if (!(not_empty && below_max)) {
395 return &self->slots[index].value;
400 max_possible_offset++;
420 assert(self != NULL);
423 const uint32_t index_mask = self->capacity - 1;
425 uint32_t index = key_hash & index_mask;
426 uint32_t max_possible_offset = 0;
431 const bool below_max = max_possible_offset <= self->slots[index].offset;
433 if (!(not_empty && below_max)) {
438 return self->slots[index].value;
443 max_possible_offset++;
445 return default_value;
463 return JOIN(FHASHTABLE_NAME, get_value_mut)(self, key);
467static inline void JOIN(internal,
JOIN(FHASHTABLE_NAME, swap_slots))(FHASHTABLE_SLOT_TYPE *a, FHASHTABLE_SLOT_TYPE *b)
469 FHASHTABLE_SLOT_TYPE temp = *a;
485 assert(self != NULL);
486 assert(FHASHTABLE_CONTAINS_KEY(self, key) ==
false);
488 const uint32_t index_mask = self->capacity - 1;
491 uint32_t index = key_hash & index_mask;
492 FHASHTABLE_SLOT_TYPE current_slot = {.offset = 0, .key = key, .value = value};
501 if (current_slot.offset > self->slots[index].offset) {
502 FHASHTABLE_SWAP_SLOTS(&self->slots[index], ¤t_slot);
507 current_slot.offset++;
509 self->slots[index] = current_slot;
523 assert(self != NULL);
525 const uint32_t index_mask = self->capacity - 1;
528 uint32_t index = key_hash & index_mask;
529 FHASHTABLE_SLOT_TYPE current_slot = {.offset = 0, .key = key, .value = value};
538 const bool offset_is_same = current_slot.offset == self->slots[index].offset;
540 const bool key_is_equal =
KEY_IS_EQUAL(current_slot.key, self->slots[index].key);
542 if (offset_is_same && key_is_equal) {
543 self->slots[index].value = current_slot.value;
547 if (current_slot.offset > self->slots[index].offset) {
548 FHASHTABLE_SWAP_SLOTS(¤t_slot, &self->slots[index]);
553 current_slot.offset++;
556 self->slots[index] = current_slot;
561static inline void JOIN(internal,
JOIN(FHASHTABLE_NAME, backshift))(FHASHTABLE_TYPE *self,
const uint32_t index_mask,
566 uint32_t next_index = (index + 1) & index_mask;
571 const bool offset_is_non_zero = self->slots[next_index].offset > 0;
573 if (!(not_empty && offset_is_non_zero)) {
577 self->slots[index] = self->slots[next_index];
578 self->slots[index].offset--;
583 next_index = (index + 1) & index_mask;
597static inline bool JOIN(FHASHTABLE_NAME,
delete)(FHASHTABLE_TYPE *self,
const KEY_TYPE key)
599 assert(self != NULL);
601 const uint32_t index_mask = self->capacity - 1;
604 uint32_t index = key_hash & index_mask;
605 uint32_t max_possible_offset = 0;
610 const bool below_max = max_possible_offset <= self->slots[index].offset;
612 if (!(not_empty && below_max)) {
616 const bool key_is_equal =
KEY_IS_EQUAL(key, self->slots[index].key);
619 index = (index + 1) & index_mask;
620 max_possible_offset++;
627 FHASHTABLE_BACKSHIFT(self, index_mask, index);
639static inline void JOIN(FHASHTABLE_NAME, clear)(FHASHTABLE_TYPE *self)
641 assert(self != NULL);
643 for (uint32_t i = 0; i < self->capacity; i++) {
655static inline void JOIN(FHASHTABLE_NAME, copy)(FHASHTABLE_TYPE *restrict dest_ptr,
656 const FHASHTABLE_TYPE *restrict src_ptr)
658 assert(src_ptr != NULL);
659 assert(dest_ptr != NULL);
660 assert(src_ptr->capacity <= dest_ptr->capacity);
661 assert(dest_ptr->count == 0);
663 for (uint32_t i = 0; i < src_ptr->capacity; i++) {
664 dest_ptr->slots[i] = src_ptr->slots[i];
667 dest_ptr->count = src_ptr->count;
680#undef FHASHTABLE_TYPE
681#undef FHASHTABLE_SLOT_TYPE
682#undef FHASHTABLE_INIT
683#undef FHASHTABLE_IS_FULL
684#undef FHASHTABLE_CONTAINS_KEY
685#undef FHASHTABLE_CALC_SIZEOF
686#undef FHASHTABLE_SWAP_SLOTS
687#undef FHASHTABLE_BACKSHIFT
#define HASH_FUNCTION(key)
Used to compute indicies of keys. This must be manually defined before including this header file.
Definition fhashtable.h:181
#define fhashtable_calc_sizeof_overflows(fhashtable_name, capacity)
Check for a given capacity, if the equivalent size of the hashtable struct overflows.
Definition fhashtable.h:103
#define KEY_IS_EQUAL(a, b)
Used to compare two keys This must be manually defined before including this header file.
Definition fhashtable.h:166
#define FHASHTABLE_EMPTY_SLOT_OFFSET
Offset constant used to flag empty slots.
Definition fhashtable.h:61
#define VALUE_TYPE
The value type. This must be manually defined before including this header file.
Definition fhashtable.h:144
#define KEY_TYPE
The key type. This must be manually defined before including this header file.
Definition fhashtable.h:132
#define fhashtable_calc_sizeof(fhashtable_name, capacity)
Calculate the size of the hashtable struct. No overflow checks.
Definition fhashtable.h:90
Check if a number is a power of two.
static size_t is_pow2(const size_t x)
Check if a number is a power of two.
Definition is_pow2.h:34
Murmur3 hash hashing function.
C preprocessor macros for pasting tokens together.
#define JOIN(a, b)
First expand tokens, then paste them together with a _ in between.
Definition paste.h:35
Round up to the next power of two.
static uint32_t round_up_pow2_32(uint32_t x)
Definition round_up_pow2.h:39
uint32_t offset
Offset from the ideal slot index.
Definition fhashtable.h:205
VALUE_TYPE value
The value in this slot.
Definition fhashtable.h:207
KEY_TYPE key
The key in this slot.
Definition fhashtable.h:206
uint32_t count
Number of non-empty slots.
Definition fhashtable.h:215
uint32_t capacity
Number of slots.
Definition fhashtable.h:216