UHash

struct UHash

A type safe, generic hash table.

Type definitions

UHASH_DECL(T, uhkey_t, uhval_t)

Declares a new hash table type.

Parameters

  • T: [symbol] Hash table name.

  • uhkey_t: [symbol] Type of the keys.

  • uhval_t: [symbol] Type of the values.

UHASH_DECL_SPEC(T, uhkey_t, uhval_t, SPEC)

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

Parameters

  • T: [symbol] Hash table name.

  • uhkey_t: [symbol] Type of the keys.

  • uhval_t: [symbol] 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 name.

  • __hash_func: [(uhkey_t) -> uhash_uint_t] Hash function.

  • __equal_func: [(uhkey_t, uhkey_t) -> bool] Equality function.

UHASH_INIT(T, uhkey_t, uhval_t, __hash_func, __equal_func)

Defines a new static hash table type.

Parameters

  • T: [symbol] Hash table name.

  • uhkey_t: [symbol] Type of the keys.

  • uhval_t: [symbol] Type of the values.

  • __hash_func: [(uhkey_t) -> uhash_uint_t] Hash function.

  • __equal_func: [(uhkey_t, uhkey_t) -> bool] Equality function.

Hash and equality functions

uhash_identical(a, b)

Identity macro.

Return

a == b

Parameters

  • a: LHS of the identity.

  • b: RHS of the identity.

uhash_str_equals(a, b)

Equality function for strings.

Return

[bool] True if a is equal to b, false otherwise.

Parameters

  • a: [char const *] LHS of the equality relation (NULL terminated string).

  • b: [char const *] RHS of the equality relation (NULL terminated string).

uhash_int8_hash(key)

Hash function for 8 bit integers.

Return

[uhash_uint_t] The hash value.

Parameters

  • key: [int8_t/uint8_t] The integer.

uhash_int16_hash(key)

Hash function for 16 bit integers.

Return

[uhash_uint_t] The hash value.

Parameters

  • key: [int16_t/uint16_t] The integer.

uhash_int32_hash(key)

Hash function for 32 bit integers.

Return

[uhash_uint_t] The hash value.

Parameters

  • key: [int32_t/uint32_t] The integer.

uhash_int64_hash(key)

Hash function for 64 bit integers.

Return

[uhash_uint_t] The hash value.

Parameters

  • key: [int64_t/uint64_t] The integer.

uhash_str_hash(key)

Hash function for strings.

Return

[uhash_uint_t] The hash value.

Parameters

  • key: [char const *] Pointer to a NULL-terminated string.

uhash_ptr_hash(key)

Hash function for pointers.

Return

[uhash_uint_t] The hash value.

Parameters

  • key: [pointer] The pointer.

Declaration

UHash(T)

Declares a new hash table variable.

Parameters

  • T: [symbol] Hash table name.

uhash_struct(T)

Expands to ‘struct UHash_T’, useful for forward-declarations.

Parameters

  • T: [symbol] Hash table name.

Memory management

uhash_free(T, h)

Deallocates the specified hash table.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table to deallocate.

uhash_copy(T, h)

Copies the specified hash table.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table to copy.

uhash_copy_as_set(T, h)

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

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table to copy.

uhash_resize(T, h, s)

Resizes the specified hash table.

Return

[uhash_ret_t] UHASH_OK if the operation succeeded, UHASH_ERR on error.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table to resize.

  • s: [uhash_uint_t] Hash table size.

Primitives

uhash_put(T, h, k, i)

Inserts a key into the specified hash table.

Return

[uhash_ret_t] Return code (see uhash_ret_t).

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Key to insert.

  • [out] i: [uhash_uint_t*] Index of the inserted element.

uhash_get(T, h, k)

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

Return

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

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Key whose index should be retrieved.

uhash_delete(T, h, k)

Deletes the bucket at the specified index.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_uint_t] Index of the bucket to delete.

uhash_contains(T, h, k)

Checks whether the hash table contains the specified key.

Return

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

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Key to test.

uhash_exists(h, x)

Tests whether a bucket contains data.

Return

[bool] True if the bucket contains data, false otherwise.

Parameters

  • h: [UHash(T)*] Hash table instance.

  • x: [uhash_uint_t] Index of the bucket to test.

uhash_key(h, x)

Retrieves the key at the specified index.

Return

[uhash_T_key] Key.

Parameters

  • h: [UHash(T)*] Hash table instance.

  • x: [uhash_uint_t] Index of the bucket whose key should be retrieved.

uhash_value(h, x)

Retrieves the value at the specified index.

Return

[T value type] Value.

Note

Undefined behavior if used on hash sets.

Parameters

  • h: [UHash(T)*] Hash table instance.

  • x: [uhash_uint_t] Index of the bucket whose value should be retrieved.

uhash_begin(h)

Retrieves the start index.

Return

[uhash_uint_t] Start index.

Parameters

uhash_end(h)

Retrieves the end index.

Return

[uhash_uint_t] End index.

Parameters

uhash_count(h)

Returns the number of elements in the hash table.

Return

[uhash_uint_t] Number of elements.

Note

For convenience, this macro returns ‘0’ for NULL hash tables.

Parameters

uhash_clear(T, h)

Resets the specified hash table without deallocating it.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

Map-specific API

uhmap_alloc(T)

Allocates a new hash map.

Return

[UHash(T)*] Hash table instance.

Parameters

  • T: [symbol] Hash table name.

uhmap_get(T, h, k, m)

Returns the value associated with the specified key.

Return

[uhash_T_val] Value associated with the specified key.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] The key.

  • m: [uhash_T_val] Value to return if the key is missing.

uhmap_set(T, h, k, v, e)

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

Return

[uhash_ret_t] Return code (see uhash_ret_t).

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] The key.

  • v: [uhash_T_val] The value.

  • [out] e: [uhash_T_val*] Existing value, only set if key was already in the map.

uhmap_add(T, h, k, v, e)

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

Return

[uhash_ret_t] Return code (see uhash_ret_t).

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] The key.

  • v: [uhash_T_val] The value.

  • [out] e: [uhash_T_val*] Existing value, only set if key was already in the map.

uhmap_replace(T, h, k, v, r)

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

Return

[bool] True if the value was replaced (its key was present), false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] The key.

  • v: [uhash_T_val] The value.

  • [out] r: [uhash_T_val*] Replaced value, only set if the return value is true.

uhmap_remove(T, h, k)

Removes a key:value pair from the map.

Return

[bool] True if the key was present (it was deleted), false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] The key.

uhmap_pop(T, h, k, dk, dv)

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

Return

[bool] True if the key was present (it was deleted), false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] The key.

  • [out] dk: [uhash_T_key*] Deleted key, only set if key was present in the map.

  • [out] dv: [uhash_T_val*] Deleted value, only set if key was present in the map.

Set-specific API

uhset_alloc(T)

Allocates a new hash set.

Return

[UHash(T)*] Hash table instance.

Parameters

  • T: [symbol] Hash table name.

uhset_insert(T, h, k)

Inserts an element in the set.

Return

[uhash_ret_t] Return code (see uhash_ret_t).

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Element to insert.

uhset_insert_get_existing(T, h, k, e)

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

Return

[uhash_ret_t] Return code (see uhash_ret_t).

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Element to insert.

  • [out] e: [uhash_T_key*] Existing element, only set if it was already in the set.

uhset_insert_all(T, h, a, n)

Populates the set with elements from an array.

Return

[uhash_ret_t] Return code (see uhash_ret_t).

Note

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

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • a: [uhash_T_key*] Array of elements.

  • n: [uhash_uint_t] Size of the array.

uhset_replace(T, h, k, r)

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

Return

[bool] True if the element was replaced (it was present), false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Element to replace.

  • [out] r: [uhash_T_key*] Replaced element, only set if the return value is true.

uhset_remove(T, h, k)

Removes an element from the set.

Return

[bool] True if the element was removed (it was present), false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Element to remove.

uhset_pop(T, h, k, d)

Removes an element from the set, returning the deleted element.

Return

[bool] True if the element was removed (it was present), false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • k: [uhash_T_key] Element to remove.

  • [out] d: [uhash_T_key*] Deleted element, only set if element was present in the set.

uhset_is_superset(T, h1, h2)

Checks whether the set is a superset of another set.

Return

[bool] True if the superset relation holds, false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h1: [UHash(T)*] Superset.

  • h2: [UHash(T)*] Subset.

uhset_union(T, h1, h2)

Performs the union between two sets, mutating the first.

Return

[uhash_ret_t] UHASH_OK if the operation succeeded, UHASH_ERR on error.

Parameters

  • T: [symbol] Hash table name.

  • h1: [UHash(T)*] Set to mutate.

  • h2: [UHash(T)*] Other set.

uhset_intersect(T, h1, h2)

Performs the intersection between two sets, mutating the first.

Parameters

  • T: [symbol] Hash table name.

  • h1: [UHash(T)*] Set to mutate.

  • h2: [UHash(T)*] Other set.

uhset_equals(T, h1, h2)

Checks whether the set is equal to another set.

Return

[bool] True if the equality relation holds, false otherwise.

Parameters

  • T: [symbol] Hash table name.

  • h1: [UHash(T)*] LHS of the equality relation.

  • h2: [UHash(T)*] RHS of the equality relation.

uhset_hash(T, h)

Computes the hash of the set.

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

Return

[uhash_uint_t] Hash of the set.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

uhset_get_any(T, h, m)

Returns one of the elements in the set.

Return

[uhash_T_key] One of the elements in the set.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • m: [uhash_T_key] Value returned if the set is empty.

Iteration

uhash_foreach(T, h, key_name, val_name, code)

Iterates over the entries in the hash table.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • key_name: [symbol] Name of the variable to which the key will be assigned.

  • val_name: [symbol] Name of the variable to which the value will be assigned.

  • code: [code] Code block to execute.

uhash_foreach_key(T, h, key_name, code)

Iterates over the keys in the hash table.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • key_name: [symbol] Name of the variable to which the key will be assigned.

  • code: [code] Code block to execute.

uhash_foreach_value(T, h, val_name, code)

Iterates over the values in the hash table.

Parameters

  • T: [symbol] Hash table name.

  • h: [UHash(T)*] Hash table instance.

  • val_name: [symbol] Name of the variable to which the value will be assigned.

  • code: [code] Code block to execute.

Public Types

enum uhash_ret_t

Return codes.

Values:

typedef uint32_t uhash_uint_t

Unsigned integer type.