stdx_hashtable.h

home

STDX - Generic Hashtable
Part of the STDX General Purpose C Library by marciovmf
License: MIT
https://github.com/marciovmf/stdx

Overview

Provides a generic, type-agnostic hashtable implementation with customizable hash and equality functions. Supports arbitrary key
and value types, optional custom allocators, and built-in iteration.
Includes helpers for common cases like string keys.

How to compile

To compile the implementation define XIMPLHASHTABLE
in one source file before including this header.

To customize how this module allocates memory, define
XHASHTABLEALLOC / XHASHTABLEREALLOC / XHASHTABLEFREE before including.

Typed usage (recommended)

The hashtable core operates on void* and explicit key/value sizes. For convenience, this header also provides macros that generate type-safe wrappers on top of the generic API.

These macros create:

a typed alias for XHashtable
typed wrapper functions (create, set, get, has, remove, count)

This removes the need for manual casts and makes the API easier to use.

Example

X_HASHTABLE_TYPE(int32_t, float)
XHashtable_int32_t_float* ht = x_hashtable_int32_t_float_create();
x_hashtable_int32_t_float_set(ht, 10, 2.5f);
float value;
if (x_hashtable_int32_t_float_get(ht, 10, &value))
{
    printf("value = %f\n", value);
}

Named variants

If the key or value type is not a valid identifier (for example char*, unsigned int, or complex types), use the named version:

X_HASHTABLE_TYPE_NAMED(char*, int32_t, cstr_i32)
XHashtable_cstr_i32* ht = x_hashtable_cstr_i32_create();

Specialized macros

Some key/value combinations require explicit semantics. The following helpers are provided:

X_HASHTABLE_TYPE_PTR_KEY_NAMED
X_HASHTABLE_TYPE_CSTR_KEY_NAMED
X_HASHTABLE_TYPE_PTR_VALUE_NAMED
X_HASHTABLE_TYPE_PTR_KEY_PTR_VALUE_NAMED
X_HASHTABLE_TYPE_CSTR_KEY_PTR_VALUE_NAMED

These macros declare the correct ownership and comparison behavior for pointer keys, string keys, or pointer values.

Example with string keys

X_HASHTABLE_TYPE_CSTR_KEY_NAMED(int32_t, cstr_i32)
XHashtable_cstr_i32* ht = x_hashtable_cstr_i32_create();
x_hashtable_cstr_i32_set(ht, "ONE", 1);
x_hashtable_cstr_i32_set(ht, "TWO", 2);

Internally these wrappers call the generic API, so there is no additional runtime overhead.

Macro

X_HASHTABLE_VERSION_MAJOR

#define X_HASHTABLE_VERSION_MAJOR 1

Macro

X_HASHTABLE_VERSION_MINOR

#define X_HASHTABLE_VERSION_MINOR 0

Macro

X_HASHTABLE_VERSION_PATCH

#define X_HASHTABLE_VERSION_PATCH 0

Macro

X_HASHTABLE_VERSION

#define X_HASHTABLE_VERSION(X_HASHTABLE_VERSION_MAJOR *10000+X_HASHTABLE_VERSION_MINOR *100+X_HASHTABLE_VERSION_PATCH)

Macro

X_HASHTABLE_INITIAL_CAPACITY

#define X_HASHTABLE_INITIAL_CAPACITY 16

Macro

X_HASHTABLE_LOAD_FACTOR

#define X_HASHTABLE_LOAD_FACTOR 0.75

Typedef

XHashFnHash

typedef size_t(*XHashFnHash)(const void *key, size_t);

Typedef

XHashFnCompare

typedef bool(*XHashFnCompare)(const void *a, const void *b);

Typedef

XHashFnClone

typedef void(*XHashFnClone)(void *dst, const void *src);

Typedef

XHashFnDestroy

typedef void(*XHashFnDestroy)(void *ptr);

Struct

XHashEntry

typedef struct{
  enum XEntryState{X_HASH_ENTRY_FREE, X_HASH_ENTRY_OCCUPIED, X_HASH_ENTRY_DELETED,}state;
}XHashEntry;

Struct

XHashtable

typedef struct{
  size_t key_size;
  size_t value_size;
  size_t count;
  size_t capacity;
  XHashEntry *entries;
  void *keys;
  void *values;
  bool key_is_pointer;
  bool value_is_pointer;
  bool key_is_null_terminated;
  bool value_is_null_terminated;
  XHashFnHash fn_key_hash;
  XHashFnCompare fn_key_compare;
  XHashFnClone fn_key_copy;
  XHashFnDestroy fn_key_free;
  XHashFnClone fn_value_copy;
  XHashFnDestroy fn_value_free;
}XHashtable;

Struct

XHashtableIter

typedef struct{
  XHashtable *table;
  size_t index;
}XHashtableIter;

Function

x_hashtable_create_ex

Create a hashtable using raw size and explicit string/pointer traits for keys and values.

X_HASHTABLE_API XHashtable * x_hashtable_create_ex(
 size_t key_size,
 bool key_null_terminated,
 bool key_is_pointer,
 size_t value_size,
 bool value_null_terminated,
 bool value_is_pointer
);

Parameters

size_t key_size: Size in bytes of the key type.
bool key_null_terminated: True if the key is a NUL-terminated string (C string).
bool key_is_pointer: True if the key is stored as a pointer value.
size_t value_size: Size in bytes of the value type.
bool value_null_terminated: True if the value is a NUL-terminated string (C string).
bool value_is_pointer: True if the value is stored as a pointer value.

Returns

Pointer to a newly created hashtable, or NULL on failure.

Function

x_hashtable_create_full

Create a fully-configurable hashtable with custom hashing, comparison, cloning, and destruction.

XHashtable * x_hashtable_create_full(
 size_t key_size,
 size_t value_size,
 XHashFnHash fn_key_hash,
 XHashFnCompare fn_key_compare,
 XHashFnClone fn_key_copy,
 XHashFnDestroy fn_key_free,
 XHashFnClone fn_value_copy,
 XHashFnDestroy fn_value_free
);

Parameters

size_t key_size: Size in bytes of the key type.
size_t value_size: Size in bytes of the value type.
XHashFnHash fn_key_hash: Function used to hash keys.
XHashFnCompare fn_key_compare: Function used to compare keys for equality.
XHashFnClone fn_key_copy: Function used to clone/copy keys into the table.
XHashFnDestroy fn_key_free: Function used to destroy/free keys owned by the table.
XHashFnClone fn_value_copy: Function used to clone/copy values into the table.
XHashFnDestroy fn_value_free: Function used to destroy/free values owned by the table.

Returns

Pointer to a newly created hashtable, or NULL on failure.

Function

x_hashtable_set

Insert or update a key/value pair in the hashtable.

X_HASHTABLE_API bool x_hashtable_set(
 XHashtable *table,
 const void *key,
 const void *value
);

Parameters

XHashtable *table: Hashtable instance.
const void *key: Pointer to the key data.
const void *value: Pointer to the value data.

Returns

True on success, false on failure (e.g., allocation failure).

Function

x_hashtable_get

Retrieve a value from the hashtable by key.

X_HASHTABLE_API bool x_hashtable_get(
 XHashtable *table,
 const void *key,
 void *out_value
);

Parameters

XHashtable *table: Hashtable instance.
const void *key: Pointer to the key data.
void *out_value: Output buffer to receive the value.

Returns

True if the key was found and out_value was written, false otherwise.

Function

x_hashtable_destroy

Destroy a hashtable and free all associated resources.

X_HASHTABLE_API void x_hashtable_destroy(XHashtable *table);

Parameters

XHashtable *table: Hashtable instance to destroy.

Returns

Nothing.

Function

x_hashtable_count

Get the number of stored entries in the hashtable.

X_HASHTABLE_API size_t x_hashtable_count(const XHashtable *table);

Parameters

const XHashtable *table: Hashtable instance.

Returns

Number of key/value pairs currently stored.

Function

stdx_str_eq

Compare two NUL-terminated strings for equality.

X_HASHTABLE_API bool stdx_str_eq(
 const void *a,
 const void *b
);

Parameters

const void *a: Pointer to the first string (const char*).
const void *b: Pointer to the second string (const char*).

Returns

True if equal, false otherwise.

Function

x_hashtable_has

Check whether the hashtable contains a key.

X_HASHTABLE_API bool x_hashtable_has(
 XHashtable *table,
 const void *key
);

Parameters

XHashtable *table: Hashtable instance.
const void *key: Pointer to the key data.

Returns

True if the key exists, false otherwise.

Function

x_hashtable_remove

Remove an entry from the hashtable by key.

X_HASHTABLE_API bool x_hashtable_remove(
 XHashtable *table,
 const void *key
);

Parameters

XHashtable *table: Hashtable instance.
const void *key: Pointer to the key data.

Returns

True if an entry was removed, false if the key was not found.

Function

x_hashtable_hash_bytes

Hash an arbitrary byte buffer.

X_HASHTABLE_API size_t x_hashtable_hash_bytes(
 const void *ptr,
 size_t size
);

Parameters

const void *ptr: Pointer to the bytes to hash.
size_t size: Number of bytes to hash.

Returns

Hash value for the given byte buffer.

Function

x_hashtable_hash_cstr

Hash a NUL-terminated C string (or string-like buffer) for hashtable use.

X_HASHTABLE_API size_t x_hashtable_hash_cstr(
 const void *ptr,
 size_t size
);

Parameters

const void *ptr: Pointer to the string data (typically const char*).
size_t size: Size parameter (typically ignored for C strings, or used as a limit depending on implementation).

Returns

Hash value for the string.

Function

x_hashtable_clone_cstr

Clone a NUL-terminated C string into destination storage.

X_HASHTABLE_API void x_hashtable_clone_cstr(
 void *dest,
 const void *src
);

Parameters

void *dest: Destination storage receiving the cloned string (implementation-defined: may store char*).
const void *src: Source string pointer (const char*).

Returns

Nothing.

Function

x_hashtable_compare_cstr

Compare two NUL-terminated C strings for hashtable key equality.

X_HASHTABLE_API bool x_hashtable_compare_cstr(
 const void *a,
 const void *b
);

Parameters

const void *a: First string pointer (const char*).
const void *b: Second string pointer (const char*).

Returns

True if equal, false otherwise.

Function

x_hashtable_free_cstr

Free a cloned NUL-terminated C string previously allocated by x_hashtable_clone_cstr().

X_HASHTABLE_API void x_hashtable_free_cstr(void *a);

Parameters

void *a: Pointer to the stored string (typically a char* or pointer slot containing it).

Returns

Nothing.

Function

x_hashtable_iter_begin

Initialize an iterator for a hashtable.

X_HASHTABLE_API bool x_hashtable_iter_begin(
 XHashtable *table,
 XHashtableIter *it
);

Parameters

XHashtable *table: Hashtable instance.
XHashtableIter *it: Iterator to initialize.

Returns

True if the iterator was initialized (even if empty table), false on invalid args.

Function

x_hashtable_iter_next

Advance iterator to the next occupied entry.

X_HASHTABLE_API bool x_hashtable_iter_next(
 XHashtableIter *it,
 void **out_key,
 void **out_value
);

Parameters

XHashtableIter *it: Iterator.
void **out_key: Receives pointer to key (user-facing: dereferenced if stored as pointer/string).
void **out_value: Receives pointer to value (user-facing: dereferenced if stored as pointer/string).

Returns

True if an entry was produced, false if iteration finished or invalid args.

Function

x_hashtable_iter_next_const

Const-friendly variant of x_hashtable_iter_next().

X_HASHTABLE_API bool x_hashtable_iter_next_const(
 XHashtableIter *it,
 const void **out_key,
 const void **out_value
);

Function

x_hashtable_iter_slot

Get the raw slot index of the current entry (mainly for debugging).

X_HASHTABLE_API size_t x_hashtable_iter_slot(const XHashtableIter *it);

Parameters

const XHashtableIter *it: Iterator.

Returns

Current slot index, or table->capacity if finished/invalid.

Macro

X_HASHTABLE_TYPE

#define X_HASHTABLE_TYPE(tk, tv) X_HASHTABLE_TYPE_NAMED(tk, tv, tk##_##tv)

Macro

X_HASHTABLE_TYPE_NAMED

#define X_HASHTABLE_TYPE_NAMED(tk, tv, suffix) \
typedef XHashtable XHashtable_##suffix;\
static inline XHashtable_##suffix *x_hashtable_##suffix##_create(void)\
{\
return(XHashtable_##suffix *)x_hashtable_create_ex(sizeof(tk), false, false, sizeof(tv), false, false);\
}\
static inline bool x_hashtable_##suffix##_set(XHashtable_##suffix *table, tk key, tv value)\
{\
return x_hashtable_set((XHashtable *)table,&key,&value);\
}\
static inline bool x_hashtable_##suffix##_get(XHashtable_##suffix *table, tk key, tv *out_value)\
{\
return x_hashtable_get((XHashtable *)table,&key, out_value);\
}\
static inline bool x_hashtable_##suffix##_has(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_has((XHashtable *)table,&key);\
}\
static inline bool x_hashtable_##suffix##_remove(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_remove((XHashtable *)table,&key);\
}\
static inline void x_hashtable_##suffix##_destroy(XHashtable_##suffix *table)\
{\
x_hashtable_destroy((XHashtable *)table);\
}\
static inline size_t x_hashtable_##suffix##_count(const XHashtable_##suffix *table)\
{\
return x_hashtable_count((const XHashtable *)table);\
}

Macro

X_HASHTABLE_TYPE_PTR_KEY_NAMED

#define X_HASHTABLE_TYPE_PTR_KEY_NAMED(tk, tv, suffix) \
typedef XHashtable XHashtable_##suffix;\
static inline XHashtable_##suffix *x_hashtable_##suffix##_create(void)\
{\
return(XHashtable_##suffix *)x_hashtable_create_ex(sizeof(tk), false, true, sizeof(tv), false, false);\
}\
static inline bool x_hashtable_##suffix##_set(XHashtable_##suffix *table, tk key, tv value)\
{\
return x_hashtable_set((XHashtable *)table, key,&value);\
}\
static inline bool x_hashtable_##suffix##_get(XHashtable_##suffix *table, tk key, tv *out_value)\
{\
return x_hashtable_get((XHashtable *)table, key, out_value);\
}\
static inline bool x_hashtable_##suffix##_has(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_has((XHashtable *)table, key);\
}\
static inline bool x_hashtable_##suffix##_remove(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_remove((XHashtable *)table, key);\
}\
static inline void x_hashtable_##suffix##_destroy(XHashtable_##suffix *table)\
{\
x_hashtable_destroy((XHashtable *)table);\
}\
static inline size_t x_hashtable_##suffix##_count(const XHashtable_##suffix *table)\
{\
return x_hashtable_count((const XHashtable *)table);\
}

Macro

X_HASHTABLE_TYPE_CSTR_KEY_NAMED

#define X_HASHTABLE_TYPE_CSTR_KEY_NAMED(tv, suffix) \
typedef XHashtable XHashtable_##suffix;\
static inline XHashtable_##suffix *x_hashtable_##suffix##_create(void)\
{\
return(XHashtable_##suffix *)x_hashtable_create_ex(sizeof(char *), true, true, sizeof(tv), false, false);\
}\
static inline bool x_hashtable_##suffix##_set(XHashtable_##suffix *table, const char *key, tv value)\
{\
return x_hashtable_set((XHashtable *)table, key,&value);\
}\
static inline bool x_hashtable_##suffix##_get(XHashtable_##suffix *table, const char *key, tv *out_value)\
{\
return x_hashtable_get((XHashtable *)table, key, out_value);\
}\
static inline bool x_hashtable_##suffix##_has(XHashtable_##suffix *table, const char *key)\
{\
return x_hashtable_has((XHashtable *)table, key);\
}\
static inline bool x_hashtable_##suffix##_remove(XHashtable_##suffix *table, const char *key)\
{\
return x_hashtable_remove((XHashtable *)table, key);\
}\
static inline void x_hashtable_##suffix##_destroy(XHashtable_##suffix *table)\
{\
x_hashtable_destroy((XHashtable *)table);\
}\
static inline size_t x_hashtable_##suffix##_count(const XHashtable_##suffix *table)\
{\
return x_hashtable_count((const XHashtable *)table);\
}

Macro

X_HASHTABLE_TYPE_PTR_VALUE_NAMED

#define X_HASHTABLE_TYPE_PTR_VALUE_NAMED(tk, tv, suffix) \
typedef XHashtable XHashtable_##suffix;\
static inline XHashtable_##suffix *x_hashtable_##suffix##_create(void)\
{\
return(XHashtable_##suffix *)x_hashtable_create_ex(sizeof(tk), false, false, sizeof(tv), false, true);\
}\
static inline bool x_hashtable_##suffix##_set(XHashtable_##suffix *table, tk key, tv value)\
{\
return x_hashtable_set((XHashtable *)table,&key, value);\
}\
static inline bool x_hashtable_##suffix##_get(XHashtable_##suffix *table, tk key, tv *out_value)\
{\
return x_hashtable_get((XHashtable *)table,&key, out_value);\
}\
static inline bool x_hashtable_##suffix##_has(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_has((XHashtable *)table,&key);\
}\
static inline bool x_hashtable_##suffix##_remove(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_remove((XHashtable *)table,&key);\
}\
static inline void x_hashtable_##suffix##_destroy(XHashtable_##suffix *table)\
{\
x_hashtable_destroy((XHashtable *)table);\
}\
static inline size_t x_hashtable_##suffix##_count(const XHashtable_##suffix *table)\
{\
return x_hashtable_count((const XHashtable *)table);\
}

Macro

X_HASHTABLE_TYPE_PTR_KEY_PTR_VALUE_NAMED

#define X_HASHTABLE_TYPE_PTR_KEY_PTR_VALUE_NAMED(tk, tv, suffix) \
typedef XHashtable XHashtable_##suffix;\
static inline XHashtable_##suffix *x_hashtable_##suffix##_create(void)\
{\
return(XHashtable_##suffix *)x_hashtable_create_ex(sizeof(tk), false, true, sizeof(tv), false, true);\
}\
static inline bool x_hashtable_##suffix##_set(XHashtable_##suffix *table, tk key, tv value)\
{\
return x_hashtable_set((XHashtable *)table, key, value);\
}\
static inline bool x_hashtable_##suffix##_get(XHashtable_##suffix *table, tk key, tv *out_value)\
{\
return x_hashtable_get((XHashtable *)table, key, out_value);\
}\
static inline bool x_hashtable_##suffix##_has(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_has((XHashtable *)table, key);\
}\
static inline bool x_hashtable_##suffix##_remove(XHashtable_##suffix *table, tk key)\
{\
return x_hashtable_remove((XHashtable *)table, key);\
}\
static inline void x_hashtable_##suffix##_destroy(XHashtable_##suffix *table)\
{\
x_hashtable_destroy((XHashtable *)table);\
}\
static inline size_t x_hashtable_##suffix##_count(const XHashtable_##suffix *table)\
{\
return x_hashtable_count((const XHashtable *)table);\
}

Macro

X_HASHTABLE_TYPE_CSTR_KEY_PTR_VALUE_NAMED

#define X_HASHTABLE_TYPE_CSTR_KEY_PTR_VALUE_NAMED(tv, suffix) \
typedef XHashtable XHashtable_##suffix;\
static inline XHashtable_##suffix *x_hashtable_##suffix##_create(void)\
{\
return(XHashtable_##suffix *)x_hashtable_create_ex(sizeof(char *), true, true, sizeof(tv), false, true);\
}\
static inline bool x_hashtable_##suffix##_set(XHashtable_##suffix *table, const char *key, tv value)\
{\
return x_hashtable_set((XHashtable *)table, key, value);\
}\
static inline bool x_hashtable_##suffix##_get(XHashtable_##suffix *table, const char *key, tv *out_value)\
{\
return x_hashtable_get((XHashtable *)table, key, out_value);\
}\
static inline bool x_hashtable_##suffix##_has(XHashtable_##suffix *table, const char *key)\
{\
return x_hashtable_has((XHashtable *)table, key);\
}\
static inline bool x_hashtable_##suffix##_remove(XHashtable_##suffix *table, const char *key)\
{\
return x_hashtable_remove((XHashtable *)table, key);\
}\
static inline void x_hashtable_##suffix##_destroy(XHashtable_##suffix *table)\
{\
x_hashtable_destroy((XHashtable *)table);\
}\
static inline size_t x_hashtable_##suffix##_count(const XHashtable_##suffix *table)\
{\
return x_hashtable_count((const XHashtable *)table);\
}

Macro

X_HASHTABLE_ALLOC

Internal macro for allocating memory. To override how this header allocates memory, define this macro with a different implementation before including this header.

#define X_HASHTABLE_ALLOC(sz) malloc(sz)

Parameters

sz: The size of memory to alloc.

Macro

X_HASHTABLE_CALLOC

Internal macro for allocating zero-initialized memory. To override how this header allocates zero-initialized memory, define this macro with a different implementation before including this header.

#define X_HASHTABLE_CALLOC(n, sz) calloc((n), (sz))

Parameters

n: The number of elements to alloc.
sz: The size of each element.

Macro

X_HASHTABLE_FREE

Internal macro for freeing memory. To override how this header frees memory, define this macro with a different implementation before including this header.

#define X_HASHTABLE_FREE(p) free(p)

Parameters

p: The address of memory region to free.