Hash table

Types

typedef struct UHash_T UHash_T: Generic hash table type.

Note

This is a placeholder for documentation purposes. You should use the UHash(T) macro to reference a specific hash table type.

UHash(T)

References a specific hash table type.

Parameters:

T – Hash table type.

typedef HashTableKeyType uhash_T_key: Generic hash table key type.

Note

This is a placeholder for documentation purposes.

UHashKey(T)

Hash table key type.

Note

While you can use this macro to reference the key type of a UHash(T), it is usually better to directly use the type specified when defining the hash table type.

Parameters:

T – Hash table type.

typedef HashTableValueType uhash_T_val: Generic hash table value type.

Note

This is a placeholder for documentation purposes.

UHashVal(T)

Hash table value type.

Note

While you can use this macro to reference the value type of a UHash(T), it is usually better to directly use the type specified when defining the hash table type.

Parameters:

T – Hash table type.

uhash_decl(T)

Hash table type forward declaration.

Parameters:

T – symbol Hash table type.

enum uhash_ret

Return codes.

Values:

enumerator UHASH_ERR

The operation failed.

As of right now, it can only happen if memory cannot be allocated.

enumerator UHASH_OK: The operation succeeded.

enumerator UHASH_PRESENT: The key is already present.

enumerator UHASH_INSERTED: The key has been inserted (it was absent).

Builtin types

typedef struct UHash_ulib_int UHash_ulib_int: UHash(T) with ulib_int keys and ulib_ptr values.

typedef struct UHash_ulib_uint UHash_ulib_uint: UHash(T) with ulib_uint keys and ulib_ptr values.

typedef struct UHash_ulib_ptr UHash_ulib_ptr: UHash(T) with ulib_ptr keys and ulib_ptr values.

Note

Expects pointers used as keys to have an alignment of ULIB_MALLOC_ALIGN.

typedef struct UHash_UString UHash_UString: UHash(T) with UString keys and ulib_ptr values.

Constants

ulib_uint uhash_upper_bound(ulib_uint buckets)

Computes the maximum number of elements that the table can contain before it needs to be resized in order to enforce its load factor.

Note

The default load factor is 0.75.

Warning

Must return a value that is strictly less than the number of buckets.

Parameters:

buckets – Number of buckets.

Returns:

Upper bound.

UHASH_INDEX_MISSING: Index returned when a key is not present in the hash table.

UHASH_VAL_IGNORE: Use it as the value type in declarations if you’re only going to use the hash table as a set.

Hash functions

ulib_uint ulib_hash_int(ulib_int key)

Hash function for ulib_int and ulib_uint numbers.

Parameters:

key – Number.

Returns:

Hash value.

ulib_uint ulib_hash_int8(uint8_t key)

Hash function for 8 bit numbers.

Parameters:

key – Number.

Returns:

Hash value.

ulib_uint ulib_hash_int16(uint16_t key)

Hash function for 16 bit numbers.

Parameters:

key – Number.

Returns:

Hash value.

ulib_uint ulib_hash_int32(uint32_t key)

Hash function for 32 bit numbers.

Parameters:

key – Number.

Returns:

Hash value.

ulib_uint ulib_hash_int64(uint64_t key)

Hash function for 64 bit numbers.

Parameters:

key – Number.

Returns:

Hash value.

ulib_uint ulib_hash_ptr(T *key)

Hash function for pointers.

Parameters:

key – The pointer.

Returns:

The hash value.

ulib_uint ulib_hash_alloc_ptr(T *key)

Hash function for pointers to allocated memory.

This hash function accounts for the alignment of pointers to allocated memory returned by e.g. malloc and realloc by dividing them by ULIB_MALLOC_ALIGN. This is important because pointers to allocated memory are generally a multiple of some power of two, due to alignment requirements, making them very bad choices as hashes for hash tables whose size is a power of two (such as UHash(T)).

Parameters:

key – The pointer.

Returns:

The hash value.

ulib_uint ulib_hash_str(char const *key)

Hash function for strings.

Parameters:

key – Pointer to a NULL-terminated string.

Returns:

Hash value.

ulib_uint ulib_hash_kr2(char const *key)

Hash function for strings.

K&R 2nd edition hash function.

Parameters:

key – Pointer to a NULL-terminated string.

Returns:

Hash value.

ulib_uint ulib_hash_mem_kr2(ulib_uint init, void const *buf, size_t size)

Hash function for memory buffers.

K&R 2nd edition hash function.

Parameters:

init – Hash initialization constant.
buf – Pointer to the start of the buffer.
size – Size of the buffer.

Returns:

Hash value.

ulib_uint ulib_hash_djb2(char const *key)

Hash function for strings.

Daniel J. Bernstein’s “djb2” hash function.

Parameters:

key – Pointer to a NULL-terminated string.

Returns:

Hash value.

ulib_uint ulib_hash_djb2_mem(ulib_uint init, void const *buf, size_t size)

Hash function for memory buffers.

Daniel J. Bernstein’s “djb2” hash function.

Parameters:

init – Hash initialization constant.
buf – Pointer to the start of the buffer.
size – Size of the buffer.

Returns:

Hash value.

ulib_uint ulib_hash_combine(ulib_uint h1, ulib_uint h2)

Combines two hashes.

Parameters:

h1 – First hash.
h2 – Second hash.

Returns:

Combined hash.

Defining new hash table types

UHASH_DECL(T, uh_key, uh_val)

Declares a new hash table type.

Parameters:

T – symbol Hash table type.
uh_key – type Type of the keys.
uh_val – type Type of the values.

UHASH_DECL_SPEC(T, uh_key, uh_val, SPEC)

Declares a new hash table type, prepending a specifier to the generated declarations.

Parameters:

T – symbol Hash table type.
uh_key – type Type of the keys.
uh_val – type Type of the values.
SPEC – specifier Specifier.

UHASH_DECL_PI(T, uh_key, uh_val)

Declares a new hash table type with per-instance hash and equality functions.

Parameters:

T – symbol Hash table type.
uh_key – type Type of the keys.
uh_val – type Type of the values.

UHASH_DECL_PI_SPEC(T, uh_key, uh_val, SPEC)

Declares a new hash table type with per-instance hash and equality functions, prepending a specifier to the generated declarations.

Parameters:

T – symbol Hash table type.
uh_key – type Type of the keys.
uh_val – type Type of the values.
SPEC – specifier Specifier.

UHASH_IMPL(T, hash_func, equal_func)

Implements a previously declared hash table type.

Parameters:

T – symbol Hash table type.
hash_func – (UHashKey(T)) -> ulib_uint Hash function or expression.
equal_func – (UHashKey(T), UHashKey(T)) -> bool Equality function or expression.

UHASH_IMPL_PI(T, default_hfunc, default_efunc)

Implements a previously declared hash table type with per-instance hash and equality functions.

Parameters:

T – symbol Hash table type.
default_hfunc – (UHashKey(T)) -> ulib_uint Hash function.
default_efunc – (UHashKey(T), UHashKey(T)) -> bool Equality function.

UHASH_INIT(T, uh_key, uh_val, hash_func, equal_func)

Defines a new static hash table type.

Parameters:

T – symbol Hash table type.
uh_key – type Type of the keys.
uh_val – type Type of the values.
hash_func – (UHashKey(T)) -> ulib_uint Hash function or expression.
equal_func – (UHashKey(T), UHashKey(T)) -> bool Equality function or expression.

UHASH_INIT_PI(T, uh_key, uh_val, default_hfunc, default_efunc)

Defines a new static hash table type with per-instance hash and equality functions.

Parameters:

T – symbol Hash table type.
uh_key – type Type of the keys.
uh_val – type Type of the values.
default_hfunc – (UHashKey(T)) -> ulib_uint Hash function.
default_efunc – (UHashKey(T), UHashKey(T)) -> bool Equality function.

Common hash table operations

bool uhash_identical(T a, T b)

Identity function.

Deprecated:: Use ulib_eq instead.

Parameters:

a – LHS of the identity.
b – RHS of the identity.

Returns:

a == b

bool uhash_str_equals(char const *a, char const *b)

Equality function for strings.

Deprecated:: Use ulib_str_equals instead.

Parameters:

a – LHS of the equality relation (NULL-terminated string).
b – RHS of the equality relation (NULL-terminated string).

Returns:

True if a is equal to b, false otherwise.

ulib_uint uhash_int8_hash(uint8_t key)

Hash function for 8 bit integers.

Deprecated:: Use ulib_hash_int8 instead.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_int16_hash(uint16_t key)

Hash function for 16 bit integers.

Deprecated:: Use ulib_hash_int16 instead.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_int32_hash(uint32_t key)

Hash function for 32 bit integers.

Deprecated:: Use ulib_hash_int32 instead.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_int64_hash(uint64_t key)

Hash function for 64 bit integers.

Deprecated:: Use ulib_hash_int64 instead.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_ptr_hash(T *key)

Hash function for pointers.

Deprecated:: Use ulib_hash_ptr or ulib_hash_alloc_ptr instead.

Parameters:

key – The pointer.

Returns:

The hash value.

ulib_uint uhash_combine_hash(ulib_uint hash_1, ulib_uint hash_2)

Combines two hashes.

Deprecated:: Use ulib_hash_combine instead.

Parameters:

hash_1 – First hash.
hash_2 – Second hash.

Returns:

The hash value.

void uhash_deinit(symbol T, UHash_T *h)

Deinitializes the specified hash table.

Parameters:

T – Hash table type.
h – Hash table to deinitialize.

UHash_T uhash_move(symbol T, UHash_T *h)

Invalidates the hash table and returns its storage.

Note

The returned object must be destroyed by calling uhash_deinit.

Parameters:

T – Hash table type.
h – Hash table whose storage should be returned.

Returns:

Hash table storage.

uhash_ret uhash_copy(symbol T, UHash_T const *src, UHash_T *dest)

Copies the specified hash table.

Parameters:

T – Hash table type.
src – Hash table to copy.
dest – Hash table to copy into.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

uhash_ret uhash_copy_as_set(symbol T, UHash_T const *src, UHash_T *dest)

Returns a new hash set obtained by copying the keys of another hash table.

Parameters:

T – Hash table type.
src – Hash table to copy.
dest – Hash table to copy into.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

uhash_ret uhash_resize(symbol T, UHash_T *h, ulib_uint s)

Resizes the specified hash table.

Parameters:

T – Hash table type.
h – Hash table to resize.
s – Hash table size.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

uhash_ret uhash_shrink(symbol T, UHash_T *h)

Shrinks the specified hash table so that its allocated size is just large enough to hold the elements it currently contains.

Parameters:

T – Hash table type.
h – Hash table to shrink.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

bool uhash_is_map(symbol T, UHash_T const *h)

Checks whether the hash table is a map.

Parameters:

T – Hash table type.
h – Hash table instance.

Returns:

True if the hash table is a map, false otherwise.

uhash_ret uhash_put(symbol T, UHash_T *h, uhash_T_key k, ulib_uint *i)

Inserts a key into the specified hash table.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Key to insert.
i – [out] Index of the inserted element.

Returns:

Return code.

ulib_uint uhash_get(symbol T, UHash_T const *h, uhash_T_key k)

Retrieves the index of the bucket associated with the specified key.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Key whose index should be retrieved.

Returns:

Index of the key, or UHASH_INDEX_MISSING if it is absent.

void uhash_delete(symbol T, UHash_T *h, ulib_uint k)

Deletes the bucket at the specified index.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Index of the bucket to delete.

bool uhash_contains(symbol T, UHash_T const *h, uhash_T_key k)

Checks whether the hash table contains the specified key.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Key to test.

Returns:

True if the hash table contains the specified key, false otherwise.

bool uhash_exists(symbol T, UHash_T const *h, ulib_uint i)

Tests whether a bucket contains data.

Parameters:

T – Hash table type.
h – Hash table instance.
i – Index of the bucket to test.

Returns:

True if the bucket contains data, false otherwise.

uhash_T_key uhash_key(symbol T, UHash_T const *h, ulib_uint i)

Retrieves the key at the specified index.

Parameters:

T – Hash table type.
h – Hash table instance.
i – Index of the bucket whose key should be retrieved.

Returns:

Key.

uhash_T_val uhash_value(symbol T, UHash_T const *h, ulib_uint i)

Retrieves the value at the specified index.

Note

Undefined behavior if used on hash sets.

Parameters:

T – Hash table type.
h – Hash table instance.
i – Index of the bucket whose value should be retrieved.

Returns:

Value.

ulib_uint uhash_size(symbol T, UHash_T const *h)

Returns the maximum number of elements that can be held by the hash table.

Parameters:

T – Hash table type.
h – Hash table instance.

Returns:

Maximum number of elements.

ulib_uint uhash_count(symbol T, UHash_T const *h)

Returns the number of elements in the hash table.

Parameters:

T – Hash table type.
h – Hash table instance.

Returns:

Number of elements.

void uhash_clear(symbol T, UHash_T *h)

Resets the specified hash table without deallocating it.

Parameters:

T – Hash table type.
h – Hash table instance.

ulib_uint uhash_next(symbol T, UHash_T const *h, ulib_uint i)

Returns the index of the first bucket starting from (and including) i which contains data.

Parameters:

T – Hash table type.
h – Hash table instance.
i – Index of the bucket to start searching from.

Returns:

Index of the first bucket containing data.

uhash_foreach(T, ht, enum_name)

Iterates over the entries in the hash table.

Usage example:

uhash_foreach (ulib_int, h, entry) {
    ulib_int key = *entry.key;
    void *val = *entry.val;
    ...
}

Parameters:

T – symbol Hash table type.
ht – UHash(T) * Hash table instance.
enum_name – symbol Name of the variable holding the current index, key and value.

Hash maps

UHash_T uhmap(symbol T)

Initializes a new hash map.

Note

The returned object must be destroyed by calling uhash_deinit.

Parameters:

T – Hash table type.

Returns:

Hash table instance.

UHash_T uhmap_pi(symbol T, ulib_uint (*hash_func)(uhash_T_key key), bool (*equal_func)(uhash_T_key a, uhash_T_key b))

Initializes a new hash map with per-instance hash and equality functions.

Note

The returned object must be destroyed by calling uhash_deinit.

Parameters:

T – Hash table type.
hash_func – Hash function pointer.
equal_func – Equality function pointer.

Returns:

Hash table instance.

uhash_T_val uhmap_get(symbol T, UHash_T const *h, uhash_T_key k, uhash_T_val m)

Returns the value associated with the specified key.

Parameters:

T – Hash table type.
h – Hash table instance.
k – The key.
m – Value to return if the key is missing.

Returns:

Value associated with the specified key.

uhash_ret uhmap_set(symbol T, UHash_T *h, uhash_T_key k, uhash_T_val v, uhash_T_val *e)

Adds a key:value pair to the map, returning the replaced value (if any).

Parameters:

T – Hash table type.
h – Hash table instance.
k – The key.
v – The value.
e – [out] Existing value, only set if key was in the map.

Returns:

Return code.

uhash_ret uhmap_add(symbol T, UHash_T *h, uhash_T_key k, uhash_T_val v, uhash_T_val *e)

Adds a key:value pair to the map, only if the key is missing.

Parameters:

T – Hash table type.
h – Hash table instance.
k – The key.
v – The value.
e – [out] Existing value, only set if key was in the map.

Returns:

Return code.

bool uhmap_replace(symbol T, UHash_T *h, uhash_T_key k, uhash_T_val v, uhash_T_val *r)

Replaces a value in the map, only if its associated key exists.

Parameters:

T – Hash table type.
h – Hash table instance.
k – The key.
v – The value.
r – [out] Replaced value, only set if key was in the map.

Returns:

True if the value was replaced, false otherwise.

bool uhmap_remove(symbol T, UHash_T *h, uhash_T_key k)

Removes a key:value pair from the map.

Parameters:

T – Hash table type.
h – Hash table instance.
k – The key.

Returns:

True if the key was removed, false otherwise.

bool uhmap_pop(symbol T, UHash_T *h, uhash_T_key k, uhash_T_key *dk, uhash_T_val *dv)

Removes a key:value pair from the map, returning the removed key and value.

Parameters:

T – Hash table type.
h – Hash table instance.
k – The key.
dk – [out] Removed key, only set if key was in the map.
dv – [out] Removed value, only set if key was in the map.

Returns:

True if the key was present, false otherwise.

Hash sets

UHash_T uhset(symbol T)

Initializes a new hash set.

Note

The returned object must be destroyed by calling uhash_deinit.

Parameters:

T – Hash table type.

Returns:

Hash table instance.

UHash_T uhset_pi(symbol T, ulib_uint (*hash_func)(uhash_T_key key), bool (*equal_func)(uhash_T_key a, uhash_T_key b))

Initializes a new hash set with per-instance hash and equality functions.

Note

The returned object must be destroyed by calling uhash_deinit.

Parameters:

T – Hash table type.
hash_func – Hash function pointer.
equal_func – Equality function pointer.

Returns:

Hash table instance.

uhash_ret uhset_insert(symbol T, UHash_T *h, uhash_T_key k)

Inserts an element in the set.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Element to insert.

Returns:

Return code.

uhash_ret uhset_insert_get_existing(symbol T, UHash_T *h, uhash_T_key k, uhash_T_key *e)

Inserts an element in the set, returning the existing element if it was already present.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Element to insert.
e – [out] Existing element, only set if key was in the set.

Returns:

Return code.

uhash_ret uhset_insert_all(symbol T, UHash_T *h, uhash_T_key *a, ulib_uint n)

Populates the set with elements from an array.

Note

This function returns UHASH_INSERTED if at least one element in the array was missing from the set.

Parameters:

T – Hash table type.
h – Hash table instance.
a – Array of elements.
n – Size of the array.

Returns:

Return code.

bool uhset_replace(symbol T, UHash_T *h, uhash_T_key k, uhash_T_key *r)

Replaces an element in the set, only if it exists.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Element to replace.
r – [out] Replaced element, only set if key was in the set.

Returns:

True if the element was replaced, false otherwise.

bool uhset_remove(symbol T, UHash_T *h, uhash_T_key k)

Removes an element from the set.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Element to remove.

Returns:

True if the element was removed, false otherwise.

bool uhset_pop(symbol T, UHash_T *h, uhash_T_key k, uhash_T_key *d)

Removes and returns an element from the set.

Parameters:

T – Hash table type.
h – Hash table instance.
k – Element to remove.
d – [out] Removed element, only set if key was in the set.

Returns:

True if the element was removed, false otherwise.

bool uhset_is_superset(symbol T, UHash_T const *h1, UHash_T const *h2)

Checks whether the set is a superset of another set.

Parameters:

T – Hash table type.
h1 – Superset.
h2 – Subset.

Returns:

True if the superset relation holds, false otherwise.

uhash_ret uhset_union(symbol T, UHash_T *h1, UHash_T const *h2)

Performs the union between h1 and h2 (h1 || h2), mutating h1.

Parameters:

T – Hash table type.
h1 – Set to mutate, will contain h1 || h2.
h2 – Other set.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

uhash_ret uhset_diff_intersect(symbol T, UHash_T *h1, UHash_T *h12, UHash_T const *h2)

Splits h1 into two sets: one containing the elements that are in h1 but not in h2 (h1 - h2), and one containing the elements that are in both h1 and h2 (h1 && h2).

Parameters:

T – Hash table type.
h1 – Set to mutate, will contain h1 - h2.
h12 – Set that will contain h1 && h2.
h2 – Other set.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

bool uhset_equals(symbol T, UHash_T const *h1, UHash_T const *h2)

Checks whether the set is equal to another set.

Parameters:

T – Hash table type.
h1 – LHS of the equality relation.
h2 – RHS of the equality relation.

Returns:

True if the equality relation holds, false otherwise.

ulib_uint uhset_hash(symbol T, UHash_T const *h)

Computes the hash of the set.

The computed hash does not depend on the order of the elements.

Parameters:

T – Hash table type.
h – Hash table instance.

Returns:

Hash of the set.

uhash_T_key uhset_get_any(symbol T, UHash_T const *h, uhash_T_key m)

Returns one of the elements in the set.

Parameters:

T – Hash table type.
h – Hash table instance.
m – Value returned if the set is empty.

Returns:

One of the elements in the set.