The following code comes from an intrusive container library I am working on in C23. So far, it works correctly due to extensive testing and sample programs I have written with it. I have implemented a Flat Linear Probing Hash Table that can be allocating or non-allocating depending on the user initialization. The first snippet shows initialization, in case it is not clear what allocating and non-allocating mean in this context.
I am struggling with performance. In some rough initial performance testing the table is slower than std::unordered_map across most operations. However, there are some constraints on what types of optimizations I can make.
This implementation is a Robin Hood hash table with linear probing and backshift deletion. It caches the hash values for efficient distance calculations, resizing, and faster comparison before being forced to call user comparison callback. Here is why I chose this implementation for this library.
- Robin Hood hash tables don't require tombstones. They suffer from primary clustering under linear probing, but deletions do allow us to heal the table in some cases. We also try to mitigate primary clustering by choosing prime number table sizes. This is beneficial when the hash table is non-allocating. Long term use of a fixed size table must be supported.
- Strict-aliasing is an issue for more complex table schemes. We require an intrusive handle in the user type meaning the user can pass provide an array of their type to manage as a hash table. If we were to attempt to implement a small metadata array at the start and the user type after that--with no intrusive elements--we would need to likely expose some sort of new type to the user for initialization. They should not provide a generic char buffer they have on the data segment, stack, or heap; that would be a strict-aliasing violation.
- Callback resistance. Right now, the table caches the 64-bit hash for the user because it is needed to accurately calculate distances to the home slot for the Robin Hood. This makes calling the user provided comparator less likely. However, this is a large space overhead decision.
When attempting to improve this table we need to consider these points.
- The hash table must support a non-allocating mode without resizing to correct from tombstone overload; an in-place rehash would be the only option (I'm not sure how to implement this).
- It must work with the user choosing the memory source. The user may provide memory from the stack, heap, or data segment at compile or runtime.
- No strict-aliasing violations. I don't want to force compiler flags on the user that affect performance.
Here is a reduced interface with the core ideas. A comment contains a link to the full interface if you wish to use it. However, the provided snippets can be compiled on their own. I am open to any and all suggestions, even if that means a complete re-write. I know profiling is a good step but first wish to see if I am missing obvious design choices.
Initialization interface.
/** @file flat_hash_map.h
@brief The Flat Hash Map Interface
A Flat Hash Map stores elements by hash value and allows the user to retrieve
them by key in amortized O(1). Elements in the table may be copied and moved so
no pointer stability is available in this implementation. If pointer stability
is needed, store and hash pointers to those elements in this table.
A flat hash map requires the user to provide a struct with known key and flat
hash element fields as well as a hash function and key comparator function. The
hash function should be well tailored to the key being stored in the table to
prevent collisions. Currently, the flat hash map does not offer any default hash
functions or hash strengthening algorithms so strong hash functions should be
obtained by the user for the data set. */
#ifndef CCC_FLAT_HASH_MAP_H
#define CCC_FLAT_HASH_MAP_H
#include "buffer.h"
#include "types.h"
enum : uint64_t
{
CCC_FHM_EMPTY = 0,
};
struct ccc_fhmap_elem_
{
uint64_t hash_;
};
struct ccc_fhmap_
{
ccc_buffer buf_;
ccc_hash_fn *hash_fn_;
ccc_key_eq_fn *eq_fn_;
size_t key_offset_;
size_t hash_elem_offset_;
};
struct ccc_fhash_entry_
{
struct ccc_fhmap_ *h_;
uint64_t hash_;
struct ccc_ent_ entry_;
};
/* Allows us to return compound literal reference to user from
the interface macros for Entry-like interface from Rust.*/
union ccc_fhmap_entry_
{
struct ccc_fhash_entry_ impl_;
};
typedef union ccc_fhmap_entry_ ccc_fhmap_entry;
typedef struct ccc_fhmap_ ccc_flat_hash_map;
typedef struct ccc_fhmap_elem_ ccc_fhmap_elem;
/** @brief Initialize a map with a buffer of types at compile time or runtime.
@param [in] memory_ptr the pointer to the backing buffer array of user types.
May be NULL if the user provides a allocation function. The buffer will be
interpreted in units of type size that the user intends to store.
@param [in] fhash_elem_field the name of the fhmap_elem field.
@param [in] key_field the field of the struct used for key storage.
@param [in] hash_fn the ccc_hash_fn function the user desires for the table.
@param [in] key_eq_fn the ccc_key_eq_fn the user intends to use.
@param [in] alloc_fn the allocation function for resizing or NULL if no
resizing is allowed.
@param [in] aux_data auxiliary data that is needed for hashing or comparison.
@param [in] capacity the starting capacity of the provided buffer or 0.
@return the flat hash map directly initialized on the right hand side of the
equality operator (i.e. ccc_flat_hash_map fh = ccc_fhm_init(...);)
@warning if initializing with a fixed size table choose a prime number for the
table capacity for improved performance.
Initialize a static fixed size hash map at compile time that has
no allocation permission or auxiliary data needed.
struct val
{
ccc_fhmap_elem e;
int key;
int val;
};
// Hash and equality functions are defined by the user.
static flat_hash_map map
= fhm_init((static struct val[2999]){}, e, key, fhmap_int_to_u64,
fhmap_id_eq, NULL, NULL, 2999);
Initialize a dynamic hash table at compile time with allocation permission and
no auxiliary data. Use the same type as the previous example.
// Hash, equality, and allocation functions are defined by the user.
static flat_hash_map map
= fhm_init((struct val *)NULL, e, key, fhmap_int_to_u64,
fhmap_id_eq, std_alloc, NULL, 0);
Initialization at runtime is also possible. Stack-based or dynamic maps are
identical to the provided examples, except without the `static` keyword in
a runtime context. */
#define ccc_fhm_init(memory_ptr, fhash_elem_field, key_field, hash_fn, \
key_eq_fn, alloc_fn, aux_data, capacity) \
{ \
.buf_ \
= (ccc_buffer)ccc_buf_init((memory_ptr), (alloc_fn), (aux_data), capacity), \
.hash_fn_ = (hash_fn), \
.eq_fn_ = (key_eq_fn), \
.key_offset_ = offsetof(typeof(*(memory_ptr)), key_field), \
.hash_elem_offset_ \
= offsetof(typeof(*(memory_ptr)), fhash_elem_field), \
}
/** @brief Obtains an entry for the provided key in the table for future use.
@param [in] h the hash table to be searched.
@param [in] key the key used to search the table matching the stored key type.
@return a specialized hash entry for use with other functions in the Entry
Interface.
@warning the contents of an entry should not be examined or modified. Use the
provided functions, only.
An entry is a search result that provides either an Occupied or Vacant entry
in the table. An occupied entry signifies that the search was successful. A
Vacant entry means the search was not successful but we now have a handle to
where in the table such an element should be inserted.
An entry is rarely useful on its own. It should be passed in a functional style
to subsequent calls in the Entry Interface.*/
[[nodiscard]] ccc_fhmap_entry ccc_fhm_entry(ccc_flat_hash_map *h,
void const *key);
/** @brief Inserts the provided entry invariantly.
@param [in] e the entry returned from a call obtaining an entry.
@param [in] elem a handle to the struct the user intends to insert.
@return a pointer to the inserted element or NULL upon a memory error in which
the load factor would be exceeded when no allocation policy is defined or
resizing failed to find more memory.
This method can be used when the old value in the table does not need to
be preserved. See the regular insert method if the old value is of interest.
If an error occurs during the insertion process due to memory limitations
or a search error NULL is returned. Otherwise insertion should not fail. */
[[nodiscard]] void *ccc_fhm_insert_entry(ccc_fhmap_entry const *e,
ccc_fhmap_elem *elem);
/** @brief Remove the entry from the table if Occupied.
@param [in] e a pointer to the table entry.
@return an entry containing NULL. If Occupied an entry in the table existed and
was removed. If Vacant, no prior entry existed to be removed. */
[[nodiscard]] ccc_entry ccc_fhm_remove_entry(ccc_fhmap_entry const *e);
[[nodiscard]] void *ccc_fhm_unwrap_fhmap_entry(ccc_fhmap_entry const *e);
[[nodiscard]] ccc_tribool ccc_fhm_entry_occupied(ccc_entry const *e);
#endif /* CCC_FLAT_HASH_MAP_H */
The implementation.
/** @file flat_hash_map.c */
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "buffer.h"
#include "flat_hash_map.h"
#include "types.h"
#if defined(__GNUC__) || defined(__clang__)
# define unlikely(expr) __builtin_expect(!!(expr), 0)
# define likely(expr) __builtin_expect(!!(expr), 1)
#else
# define unlikely(expr) expr
# define likely(expr) expr
#endif
static ptrdiff_t const primes[] = {
11LL,
37LL,
79LL,
163LL,
331LL,
691LL,
1439LL,
2999LL,
6079LL,
12263LL,
25717LL,
53611LL,
111697LL,
232499LL,
483611LL,
1005761LL,
2091191LL,
4347799LL,
9039167LL,
18792019LL,
39067739LL,
81219493LL,
168849973LL,
351027263LL,
729760741LL,
1517120861LL,
3153985903LL,
6556911073LL,
13631348041LL,
28338593999LL,
58913902231LL,
122477772247LL,
254622492793LL,
529341875947LL,
1100463743389LL,
2287785087839LL,
4756140888377LL,
9887675318611LL,
20555766849589LL,
42733962953639LL,
88840839803449LL,
184693725350723LL,
383964990193007LL,
798235638020831LL,
1659474561692683LL,
3449928429320413LL,
7172153428667531LL,
14910391869919981LL,
30997633824443711LL,
64441854452711651LL,
133969987155270011LL,
278513981492471381LL,
579010564484755961LL,
1203721378684243091LL,
2502450294306576181LL,
5202414434410211531LL,
};
#define PRIMES_SIZE ((ptrdiff_t)(sizeof(primes) / sizeof(primes[0])))
/* Some claim that Robin Hood tables can support a much higher load factor. I
am not sure. The primary clustering effect in these types of tables can
quickly rise. Try to mitigate with a lower load factor and prime table sizes.
Measure. */
static double const load_factor = 0.8;
/* We may not have allocation permission and we need space for swapping so
instead of asking the user for memory we will sacrifice first two slots of
table. */
static ptrdiff_t const last_swap_slot = 1;
static ptrdiff_t const num_swap_slots = 2;
/*========================= Prototypes ==================================*/
static void erase(struct ccc_fhmap_ *, void *);
static void swap(char tmp[const], void *, void *, size_t);
static void *struct_base(struct ccc_fhmap_ const *,
struct ccc_fhmap_elem_ const *);
static struct ccc_ent_ entry(struct ccc_fhmap_ *, void const *key,
uint64_t hash);
static struct ccc_fhash_entry_ container_entry(struct ccc_fhmap_ *h,
void const *key);
static ptrdiff_t to_i(ptrdiff_t capacity, uint64_t hash);
static ptrdiff_t increment(ptrdiff_t capacity, ptrdiff_t i);
static ptrdiff_t distance(ptrdiff_t capacity, ptrdiff_t i, ptrdiff_t j);
static void *key_in_slot(struct ccc_fhmap_ const *h, void const *slot);
static struct ccc_fhmap_elem_ *elem_in_slot(struct ccc_fhmap_ const *h,
void const *slot);
static ccc_result maybe_resize(struct ccc_fhmap_ *h);
static struct ccc_ent_ find(struct ccc_fhmap_ const *h, void const *key,
uint64_t hash);
static void insert(struct ccc_fhmap_ *h, void const *e, uint64_t hash,
ptrdiff_t i);
static uint64_t *hash_at(struct ccc_fhmap_ const *h, ptrdiff_t i);
static uint64_t filter(struct ccc_fhmap_ const *h, void const *key);
static ptrdiff_t next_prime(ptrdiff_t n);
/*========================= Sample Interface =========================*/
void *
ccc_fhm_unwrap_fhmap_entry(ccc_fhmap_entry const *const e)
{
if (unlikely(!e) || !(e->impl_.entry_.stats_ & CCC_ENTRY_OCCUPIED))
{
return NULL;
}
return e->impl_.entry_.e_;
}
ccc_tribool
ccc_fhm_entry_occupied(ccc_entry const *const e)
{
if (!e)
{
return CCC_TRIBOOL_ERROR;
}
return (e->impl_.stats_ & CCC_ENTRY_OCCUPIED) != 0;
}
ccc_fhmap_entry
ccc_fhm_entry(ccc_flat_hash_map *const h, void const *const key)
{
if (unlikely(!h || !key))
{
return (ccc_fhmap_entry){{.entry_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}};
}
return (ccc_fhmap_entry){container_entry(h, key)};
}
void *
ccc_fhm_insert_entry(ccc_fhmap_entry const *const e, ccc_fhmap_elem *const elem)
{
if (unlikely(!e || !elem))
{
return NULL;
}
void *const user_struct = struct_base(e->impl_.h_, elem);
if (e->impl_.entry_.stats_ & CCC_ENTRY_OCCUPIED)
{
elem->hash_ = e->impl_.hash_;
if (e->impl_.entry_.e_ != user_struct && e->impl_.entry_.e_)
{
(void)memcpy(e->impl_.entry_.e_, user_struct,
ccc_buf_elem_size(&e->impl_.h_->buf_));
}
return e->impl_.entry_.e_;
}
if (e->impl_.entry_.stats_ & CCC_ENTRY_INSERT_ERROR)
{
return NULL;
}
insert(e->impl_.h_, user_struct, e->impl_.hash_,
ccc_buf_i(&e->impl_.h_->buf_, e->impl_.entry_.e_));
return e->impl_.entry_.e_;
}
ccc_entry
ccc_fhm_remove_entry(ccc_fhmap_entry const *const e)
{
if (unlikely(!e))
{
return (ccc_entry){{.stats_ = CCC_ENTRY_ARG_ERROR}};
}
if (e->impl_.entry_.stats_ != CCC_ENTRY_OCCUPIED)
{
return (ccc_entry){{.stats_ = CCC_ENTRY_VACANT}};
}
erase(e->impl_.h_, e->impl_.entry_.e_);
return (ccc_entry){{.stats_ = CCC_ENTRY_OCCUPIED}};
}
/*======================= Static Helpers =============================*/
static struct ccc_fhash_entry_
container_entry(struct ccc_fhmap_ *const h, void const *const key)
{
uint64_t const hash = filter(h, key);
return (struct ccc_fhash_entry_){
.h_ = h,
.hash_ = hash,
.entry_ = entry(h, key, hash),
};
}
static struct ccc_ent_
entry(struct ccc_fhmap_ *const h, void const *const key, uint64_t const hash)
{
ccc_entry_status upcoming_insertion_error = 0;
if (maybe_resize(h) != CCC_RESULT_OK)
{
upcoming_insertion_error = CCC_ENTRY_INSERT_ERROR;
}
struct ccc_ent_ res = find(h, key, hash);
res.stats_ |= upcoming_insertion_error;
return res;
}
static struct ccc_ent_
find(struct ccc_fhmap_ const *const h, void const *const key,
uint64_t const hash)
{
ptrdiff_t const cap = ccc_buf_capacity(&h->buf_);
/* A few sanity checks. The load factor should be managed a full table is
never allowed even under no allocation permission because that could
lead to an infinite loop and illustrates a degenerate table anyway. */
if (unlikely(!cap))
{
return (struct ccc_ent_){.e_ = NULL, .stats_ = CCC_ENTRY_VACANT};
}
if (unlikely(ccc_buf_size(&h->buf_) >= ccc_buf_capacity(&h->buf_)))
{
return (struct ccc_ent_){.e_ = NULL, .stats_ = CCC_ENTRY_ARG_ERROR};
}
ptrdiff_t i = to_i(cap, hash);
ptrdiff_t dist = 0;
do
{
void *const slot = ccc_buf_at(&h->buf_, i);
uint64_t const slot_hash = elem_in_slot(h, slot)->hash_;
if (slot_hash == CCC_FHM_EMPTY
|| dist > distance(cap, i, to_i(cap, slot_hash)))
{
return (struct ccc_ent_){
.e_ = slot, .stats_ = CCC_ENTRY_VACANT | CCC_ENTRY_NO_UNWRAP};
}
if (hash == slot_hash
&& h->eq_fn_((ccc_key_cmp){
.key_lhs = key, .user_type_rhs = slot, .aux = h->buf_.aux_}))
{
return (struct ccc_ent_){.e_ = slot, .stats_ = CCC_ENTRY_OCCUPIED};
}
++dist;
i = increment(cap, i);
} while (1);
}
/* Assumes that element to be inserted does not already exist in the table.
Assumes that the table has room for another insertion. Unexpected results
may occur if these assumptions are not accommodated. */
static void
insert(struct ccc_fhmap_ *const h, void const *const e, uint64_t const hash,
ptrdiff_t i)
{
size_t const elem_sz = ccc_buf_elem_size(&h->buf_);
ptrdiff_t const cap = ccc_buf_capacity(&h->buf_);
void *const tmp = ccc_buf_at(&h->buf_, 1);
void *const floater = ccc_buf_at(&h->buf_, 0);
if (floater != e)
{
(void)memcpy(floater, e, elem_sz);
}
elem_in_slot(h, floater)->hash_ = hash;
ptrdiff_t dist = distance(cap, i, to_i(cap, hash));
do
{
void *const slot = ccc_buf_at(&h->buf_, i);
uint64_t const slot_hash = elem_in_slot(h, slot)->hash_;
if (slot_hash == CCC_FHM_EMPTY)
{
if (slot != floater)
{
(void)memcpy(slot, floater, elem_sz);
}
(void)ccc_buf_size_plus(&h->buf_, 1);
elem_in_slot(h, floater)->hash_ = CCC_FHM_EMPTY;
elem_in_slot(h, tmp)->hash_ = CCC_FHM_EMPTY;
return;
}
ptrdiff_t const slot_dist = distance(cap, i, to_i(cap, slot_hash));
if (dist > slot_dist)
{
swap(tmp, floater, slot, elem_sz);
dist = slot_dist;
}
i = increment(cap, i);
++dist;
} while (1);
}
/* Backshift deletion is important for this table because it may not be able
to allocate. This prevents the need for tombstones which would hurt table
quality quickly if we can't resize. */
static void
erase(struct ccc_fhmap_ *const h, void *const e)
{
*hash_at(h, ccc_buf_i(&h->buf_, e)) = CCC_FHM_EMPTY;
ptrdiff_t const cap = ccc_buf_capacity(&h->buf_);
size_t const elem_sz = ccc_buf_elem_size(&h->buf_);
void *const tmp = ccc_buf_at(&h->buf_, 0);
ptrdiff_t i = ccc_buf_i(&h->buf_, e);
ptrdiff_t next = increment(cap, i);
do
{
void *const next_slot = ccc_buf_at(&h->buf_, next);
uint64_t const next_hash = elem_in_slot(h, next_slot)->hash_;
if (next_hash == CCC_FHM_EMPTY
|| !distance(cap, next, to_i(cap, next_hash)))
{
elem_in_slot(h, tmp)->hash_ = CCC_FHM_EMPTY;
(void)ccc_buf_size_minus(&h->buf_, 1);
return;
}
swap(tmp, next_slot, ccc_buf_at(&h->buf_, i), elem_sz);
i = next;
next = increment(cap, next);
} while (1);
}
static ccc_result
maybe_resize(struct ccc_fhmap_ *const h)
{
/* Lazy one-time initialization lets user initialize at compile time. */
if (unlikely(ccc_buf_capacity(&h->buf_)
&& ccc_buf_size(&h->buf_) < num_swap_slots))
{
(void)memset(h->buf_.mem_, CCC_FHM_EMPTY,
ccc_buf_capacity(&h->buf_) * ccc_buf_elem_size(&h->buf_));
(void)ccc_buf_size_set(&h->buf_, num_swap_slots);
}
if (ccc_buf_capacity(&h->buf_)
&& (double)(ccc_buf_size(&h->buf_)) / (double)ccc_buf_capacity(&h->buf_)
<= load_factor)
{
return CCC_RESULT_OK;
}
if (!h->buf_.alloc_)
{
return CCC_RESULT_NO_ALLOC;
}
struct ccc_fhmap_ new_hash = *h;
new_hash.buf_.sz_ = 0;
new_hash.buf_.capacity_ = new_hash.buf_.capacity_
? next_prime(ccc_buf_size(&h->buf_) * 2)
: primes[0];
if (new_hash.buf_.capacity_ <= h->buf_.capacity_)
{
return CCC_RESULT_MEM_ERROR;
}
new_hash.buf_.mem_ = new_hash.buf_.alloc_(
NULL, ccc_buf_elem_size(&h->buf_) * new_hash.buf_.capacity_,
h->buf_.aux_);
if (!new_hash.buf_.mem_)
{
return CCC_RESULT_MEM_ERROR;
}
/* Empty is intentionally chosen as zero so every byte is just set to
0 in this new array. */
(void)memset(ccc_buf_begin(&new_hash.buf_), CCC_FHM_EMPTY,
ccc_buf_capacity(&new_hash.buf_)
* ccc_buf_elem_size(&new_hash.buf_));
(void)ccc_buf_size_set(&new_hash.buf_, num_swap_slots);
for (void *slot = ccc_buf_begin(&h->buf_);
slot != ccc_buf_capacity_end(&h->buf_);
slot = ccc_buf_next(&h->buf_, slot))
{
struct ccc_fhmap_elem_ const *const e = elem_in_slot(h, slot);
if (e->hash_ != CCC_FHM_EMPTY)
{
struct ccc_ent_ const new_ent
= find(&new_hash, key_in_slot(h, slot), e->hash_);
insert(&new_hash, slot, e->hash_,
ccc_buf_i(&new_hash.buf_, new_ent.e_));
}
}
if (ccc_buf_alloc(&h->buf_, 0, h->buf_.alloc_) != CCC_RESULT_OK)
{
*h = new_hash;
return CCC_RESULT_MEM_ERROR;
}
*h = new_hash;
return CCC_RESULT_OK;
}
static ptrdiff_t
next_prime(ptrdiff_t const n)
{
for (ptrdiff_t i = 0; i < PRIMES_SIZE; ++i)
{
if (primes[i] > n)
{
return primes[i];
}
}
return 0;
}
static inline uint64_t *
hash_at(struct ccc_fhmap_ const *const h, ptrdiff_t const i)
{
return &((struct ccc_fhmap_elem_ *)((char *)ccc_buf_at(&h->buf_, i)
+ h->hash_elem_offset_))
->hash_;
}
static inline uint64_t
filter(struct ccc_fhmap_ const *const h, void const *const key)
{
uint64_t const hash
= h->hash_fn_((ccc_user_key){.user_key = key, .aux = h->buf_.aux_});
return hash == CCC_FHM_EMPTY ? hash + 1 : hash;
}
static inline struct ccc_fhmap_elem_ *
elem_in_slot(struct ccc_fhmap_ const *const h, void const *const slot)
{
return (struct ccc_fhmap_elem_ *)((char *)slot + h->hash_elem_offset_);
}
static inline void *
key_in_slot(struct ccc_fhmap_ const *const h, void const *const slot)
{
return (char *)slot + h->key_offset_;
}
static inline ptrdiff_t
distance(ptrdiff_t const capacity, ptrdiff_t const i, ptrdiff_t const j)
{
return i < j ? (capacity - j) + i - num_swap_slots : i - j;
}
static inline ptrdiff_t
increment(ptrdiff_t const capacity, ptrdiff_t const i)
{
return (i + 1) >= capacity ? last_swap_slot + 1 : i + 1;
}
static inline void *
struct_base(struct ccc_fhmap_ const *const h,
struct ccc_fhmap_elem_ const *const e)
{
return ((char *)&e->hash_) - h->hash_elem_offset_;
}
static inline void
swap(char tmp[const], void *const a, void *const b, size_t const ab_size)
{
if (a == b || !a || !b)
{
return;
}
(void)memcpy(tmp, a, ab_size);
(void)memcpy(a, b, ab_size);
(void)memcpy(b, tmp, ab_size);
}
/** This function converts a hash to its home index in the table. Because this
operation is in the hot path of all table functions and Robin Hood relies on
home slot distance calculations, this function tries to use Daniel Lemire's
fastrange library modulo calculation alternative:
https://github.com/lemire/fastrange
Such a technique is helpful because the prime table capacities used to mitigate
primary clustering of Robin Hood hash tables make efficient modulo calculations
more difficult than power of two table capacities. */
static inline ptrdiff_t
to_i(ptrdiff_t const capacity, uint64_t hash)
{
#ifdef __SIZEOF_INT128__
hash = (uint64_t)(((__uint128_t)hash * (__uint128_t)capacity) >> 64);
#else
hash %= capacity;
#endif
return (ptrdiff_t)hash <= last_swap_slot ? last_swap_slot + 1
: (ptrdiff_t)hash;
}
STOP HERE. If you only wanted to read the hash map implementation you can stop. If you want to actually compile the code from the question snippets, below you will find the definitions for the types used and the buffer interface and implementation.
Types.
/** @file types.h */
#ifndef CCC_TYPES_H
#define CCC_TYPES_H
#include <stddef.h>
#include <stdint.h>
typedef enum : int8_t
{
/** Intended value if CCC_FALSE or CCC_TRUE could not be returned. */
CCC_TRIBOOL_ERROR = -1,
/** Equivalent to boolean false, guaranteed to be falsey aka 0. */
CCC_FALSE,
/** Equivalent to boolean true, guaranteed to be truthy aka 1. */
CCC_TRUE,
} ccc_tribool;
typedef enum
{
/** The operation has occurred without error. */
CCC_RESULT_OK = 0,
/** Memory is needed but the container lacks allocation permission. */
CCC_RESULT_NO_ALLOC,
/** The container has allocation permission, but allocation failed. */
CCC_RESULT_MEM_ERROR,
/** Bad arguments have been provided to an operation. */
CCC_RESULT_ARG_ERROR,
/** Internal helper, never returned to user. Always last result. */
CCC_RESULT_SIZE,
} ccc_result;
typedef struct
{
/** Key matching the key field of the provided type to the container. */
void const *const key_lhs;
/** The complete user type stored in the container. */
void const *const user_type_rhs;
/** A reference to aux data provided to the container on initialization. */
void *aux;
} ccc_key_cmp;
typedef struct
{
/** A reference to the same type used for keys in the container. */
void const *const user_key;
/** A reference to aux data provided to the container on initialization. */
void *aux;
} ccc_user_key;
typedef ccc_tribool ccc_key_eq_fn(ccc_key_cmp);
typedef uint64_t ccc_hash_fn(ccc_user_key to_hash);
typedef void *ccc_alloc_fn(void *ptr, size_t size, void *aux);
typedef struct ccc_buf_ ccc_buffer;
enum ccc_entry_status_ : uint8_t
{
CCC_ENTRY_VACANT = 0,
CCC_ENTRY_OCCUPIED = 0x1,
CCC_ENTRY_INSERT_ERROR = 0x2,
CCC_ENTRY_ARG_ERROR = 0x4,
CCC_ENTRY_NO_UNWRAP = 0x8,
};
typedef enum ccc_entry_status_ ccc_entry_status;
struct ccc_ent_
{
void *e_;
enum ccc_entry_status_ stats_;
};
/* Allows us to return compound literal reference to user from
the interface macros for Entry-like interface from Rust.*/
union ccc_entry_
{
struct ccc_ent_ impl_;
};
typedef union ccc_entry_ ccc_entry;
#endif /* CCC_TYPES_H */
Buffer interface.
/** @file buffer.h */
#ifndef CCC_BUFFER_H
#define CCC_BUFFER_H
#include <stddef.h>
#include "types.h"
struct ccc_buf_
{
void *mem_;
size_t elem_sz_;
ptrdiff_t sz_;
ptrdiff_t capacity_;
ccc_alloc_fn *alloc_;
void *aux_;
};
typedef struct ccc_buf_ ccc_buffer;
#define IMPL_BUF_NON_IMPL_BUF_DEFAULT_SIZE(...) __VA_ARGS__
#define IMPL_BUF_DEFAULT_SIZE(...) 0
#define IMPL_BUF_OPTIONAL_SIZE(...) \
__VA_OPT__(IMPL_BUF_NON_)##IMPL_BUF_DEFAULT_SIZE(__VA_ARGS__)
#define ccc_impl_buf_init(mem, alloc_fn, aux_data, capacity, ...) \
{ \
.mem_ = (mem), \
.elem_sz_ = sizeof(*(mem)), \
.sz_ = IMPL_BUF_OPTIONAL_SIZE(__VA_ARGS__), \
.capacity_ = (capacity), \
.alloc_ = (alloc_fn), \
.aux_ = (aux_data), \
}
#define ccc_buf_init(mem_ptr, alloc_fn, aux_data, capacity, optional_size...) \
ccc_impl_buf_init(mem_ptr, alloc_fn, aux_data, capacity, optional_size)
[[nodiscard]] ptrdiff_t ccc_buf_capacity(ccc_buffer const *buf);
[[nodiscard]] size_t ccc_buf_elem_size(ccc_buffer const *buf);
[[nodiscard]] ptrdiff_t ccc_buf_size(ccc_buffer const *buf);
[[nodiscard]] ptrdiff_t ccc_buf_i(ccc_buffer const *buf, void const *slot);
[[nodiscard]] void *ccc_buf_at(ccc_buffer const *buf, ptrdiff_t i);
[[nodiscard]] ccc_tribool ccc_buf_is_empty(ccc_buffer const *buf);
[[nodiscard]] void *ccc_buf_begin(ccc_buffer const *buf);
[[nodiscard]] void *ccc_buf_next(ccc_buffer const *buf, void const *iter);
[[nodiscard]] void *ccc_buf_end(ccc_buffer const *buf);
[[nodiscard]] void *ccc_buf_capacity_end(ccc_buffer const *buf);
[[nodiscard]] ccc_result ccc_buf_alloc(ccc_buffer *buf, ptrdiff_t capacity,
ccc_alloc_fn *fn);
ccc_result ccc_buf_size_set(ccc_buffer *buf, ptrdiff_t n);
ccc_result ccc_buf_size_minus(ccc_buffer *buf, ptrdiff_t n);
ccc_result ccc_buf_size_plus(ccc_buffer *buf, ptrdiff_t n);
#endif /* CCC_BUFFER_H */
Buffer implementation.
/** @file buffer.c */
#include <stddef.h>
#include <string.h>
#include "buffer.h"
#include "types.h"
ccc_result
ccc_buf_alloc(ccc_buffer *const buf, ptrdiff_t const capacity,
ccc_alloc_fn *const fn)
{
if (!buf || capacity < 0)
{
return CCC_RESULT_ARG_ERROR;
}
if (!fn)
{
return CCC_RESULT_NO_ALLOC;
}
void *const new_mem = fn(buf->mem_, buf->elem_sz_ * capacity, buf->aux_);
if (capacity && !new_mem)
{
return CCC_RESULT_MEM_ERROR;
}
buf->mem_ = new_mem;
buf->capacity_ = capacity;
return CCC_RESULT_OK;
}
void *
ccc_buf_at(ccc_buffer const *const buf, ptrdiff_t const i)
{
if (!buf || i < 0 || i >= buf->capacity_)
{
return NULL;
}
return ((char *)buf->mem_ + (i * buf->elem_sz_));
}
ptrdiff_t
ccc_buf_size(ccc_buffer const *const buf)
{
return buf ? buf->sz_ : -1;
}
ptrdiff_t
ccc_buf_capacity(ccc_buffer const *const buf)
{
return buf ? buf->capacity_ : -1;
}
size_t
ccc_buf_elem_size(ccc_buffer const *const buf)
{
return buf ? buf->elem_sz_ : 0;
}
ccc_tribool
ccc_buf_is_empty(ccc_buffer const *const buf)
{
if (!buf)
{
return CCC_TRIBOOL_ERROR;
}
return !buf->sz_;
}
void *
ccc_buf_begin(ccc_buffer const *const buf)
{
return buf ? buf->mem_ : NULL;
}
void *
ccc_buf_next(ccc_buffer const *const buf, void const *const iter)
{
if (!buf || !buf->mem_)
{
return NULL;
}
if (iter >= ccc_buf_capacity_end(buf))
{
return ccc_buf_end(buf);
}
return (char *)iter + buf->elem_sz_;
}
void *
ccc_buf_end(ccc_buffer const *const buf)
{
if (!buf || !buf->mem_)
{
return NULL;
}
return (char *)buf->mem_ + (buf->sz_ * buf->elem_sz_);
}
void *
ccc_buf_capacity_end(ccc_buffer const *const buf)
{
if (!buf || !buf->mem_)
{
return NULL;
}
return (char *)buf->mem_ + (buf->elem_sz_ * buf->capacity_);
}
ptrdiff_t
ccc_buf_i(ccc_buffer const *const buf, void const *const slot)
{
if (!buf || !buf->mem_ || !slot || slot < buf->mem_
|| (char *)slot
>= ((char *)buf->mem_ + (buf->capacity_ * buf->elem_sz_)))
{
return -1;
}
return (ptrdiff_t)(((char *)slot - ((char *)buf->mem_)) / buf->elem_sz_);
}
ccc_result
ccc_buf_size_set(ccc_buffer *const buf, ptrdiff_t const n)
{
if (!buf || n < 0)
{
return CCC_RESULT_ARG_ERROR;
}
if (n > buf->capacity_)
{
buf->sz_ = buf->capacity_;
return CCC_RESULT_ARG_ERROR;
}
buf->sz_ = n;
return CCC_RESULT_OK;
}
ccc_result
ccc_buf_size_plus(ccc_buffer *const buf, ptrdiff_t const n)
{
if (!buf || n < 0)
{
return CCC_RESULT_ARG_ERROR;
}
ptrdiff_t const new_sz = buf->sz_ + n;
if (new_sz > buf->capacity_)
{
buf->sz_ = buf->capacity_;
return CCC_RESULT_ARG_ERROR;
}
buf->sz_ = new_sz;
return CCC_RESULT_OK;
}
ccc_result
ccc_buf_size_minus(ccc_buffer *const buf, ptrdiff_t const n)
{
if (!buf || n < 0)
{
return CCC_RESULT_ARG_ERROR;
}
if (n > buf->sz_)
{
buf->sz_ = 0;
return CCC_RESULT_ARG_ERROR;
}
buf->sz_ -= n;
return CCC_RESULT_OK;
}
A main.c and CmakeLists.txt file if you want to put it all together.
/** @file main.c */
#include "flat_hash_map.h"
struct val
{
ccc_fhmap_elem e;
int key;
int val;
};
ccc_tribool
fhmap_id_eq(ccc_key_cmp const cmp)
{
struct val const *const va = cmp.user_type_rhs;
return va->key == *((int *)cmp.key_lhs);
}
uint64_t
fhmap_int_to_u64(ccc_user_key const k)
{
int const id_int = *((int *)k.user_key);
uint64_t x = id_int;
x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
x = x ^ (x >> 31);
return x;
}
static struct val buf[2999];
static ccc_flat_hash_map fh = ccc_fhm_init(buf, e, key, fhmap_int_to_u64,
fhmap_id_eq, NULL, NULL, 2999);
int
main(void)
{
(void)fh;
return 0;
}
Cmake.
cmake_minimum_required(VERSION 3.24.2)
project(flat_hash_map_review C)
add_library(flat_hash_map)
target_sources(flat_hash_map
PRIVATE
buffer.c
flat_hash_map.c
PUBLIC
FILE_SET public_headers
TYPE HEADERS
BASE_DIRS ${PROJECT_SOURCE_DIR}
FILES
types.h
buffer.h
flat_hash_map.h
)
target_compile_features(flat_hash_map PUBLIC c_std_23)
add_executable(main main.c)
target_link_libraries(main flat_hash_map)
#includefiles. \$\endgroup\$