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

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.

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:
UHASH_IMPL_PI(T, default_hfunc, default_efunc)

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

Parameters:
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_equals() 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.

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.