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.

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

Constants

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.

UHASH_MAX_LOAD: Hash table maximum load factor.

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.

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.

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.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_int16_hash(uint16_t key)

Hash function for 16 bit integers.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_int32_hash(uint32_t key)

Hash function for 32 bit integers.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_int64_hash(uint64_t key)

Hash function for 64 bit integers.

Parameters:

key – The integer.

Returns:

The hash value.

ulib_uint uhash_str_hash(char const *key)

Hash function for strings.

Parameters:

key – Pointer to a NULL-terminated string.

Returns:

The hash value.

ulib_uint uhash_ptr_hash(T *key)

Hash function for pointers.

Parameters:

key – The pointer.

Returns:

The hash value.

ulib_uint uhash_combine_hash(ulib_uint hash_1, ulib_uint hash_2)

Combines two hashes.

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.

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 x)

Tests whether a bucket contains data.

Parameters:

T – Hash table type.
h – Hash table instance.
x – 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 x)

Retrieves the key at the specified index.

Parameters:

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

Returns:

Key.

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

Retrieves the value at the specified index.

Note

Undefined behavior if used on hash sets.

Parameters:

T – Hash table type.
h – Hash table instance.
x – 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 two sets, mutating the first.

Parameters:

T – Hash table type.
h1 – Set to mutate.
h2 – Other set.

Returns:

UHASH_OK if the operation succeeded, UHASH_ERR on error.

void uhset_intersect(symbol T, UHash_T *h1, UHash_T const *h2)

Performs the intersection between two sets, mutating the first.

Parameters:

T – Hash table type.
h1 – Set to mutate.
h2 – Other set.

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.