#include <stddef.h>#include <stdint.h>Go to the source code of this file.
Macros | |
| #define | SHT_NEW(hashfn, eqfn, etype, ...) |
| Create a new hash table. | |
| #define | SHT_ITER_FREE(iter) |
| Free a hash table iterator. | |
| #define | SHT_ITER_NEXT(iter) |
| Get the next entry from an iterator. | |
| #define | SHT_ITER_REPLACE(iter, entry) |
| Replace the last entry returned by an iterator. | |
| #define | SHT_ITER_ERR(iter) |
| Get the the error code of an iterator's last error. | |
| #define | SHT_ITER_MSG(iter) |
| Get a description of an iterator's last error. | |
Typedefs | |
| typedef uint32_t(* | sht_hashfn_t) (const void *restrict key, void *restrict context) |
| Hash function type. | |
| typedef _Bool(* | sht_eqfn_t) (const void *restrict key, const void *restrict entry, void *restrict context) |
| Equality comparison function type. | |
| typedef void(* | sht_freefn_t) (const void *restrict entry, void *restrict context) |
| Free function type. | |
Enumerations | |
| enum | sht_err : uint8_t |
| Error codes. More... | |
Functions | |
| struct sht_ht * | sht_new_ (sht_hashfn_t hashfn, sht_eqfn_t eqfn, size_t esize, size_t ealign, enum sht_err *err) |
| (Create a new hash table.) | |
| void | sht_set_hash_ctx (struct sht_ht *ht, void *context) |
| Set the "context" for a table's hash function. | |
| void | sht_set_eq_ctx (struct sht_ht *ht, void *context) |
| Set the "context" for a table's equality function. | |
| void | sht_set_freefn (struct sht_ht *ht, sht_freefn_t freefn, void *context) |
| Set the optional entry resource free function for a table. | |
| void | sht_set_lft (struct sht_ht *ht, uint8_t lft) |
| Set the load factor threshold for a table. | |
| void | sht_set_psl_limit (struct sht_ht *ht, uint8_t thold) |
| Set the PSL limit of a table. | |
| _Bool | sht_init (struct sht_ht *ht, uint32_t capacity) |
| Initialize a hash table. | |
| void | sht_free (struct sht_ht *ht) |
| Free the resources used by a hash table. | |
| int | sht_add (struct sht_ht *ht, const void *key, const void *entry) |
| Add an entry to the table, if its key is not already present. | |
| int | sht_set (struct sht_ht *ht, const void *key, const void *entry) |
| Unconditionally set the value associated with a key. | |
| const void * | sht_get (struct sht_ht *ht, const void *restrict key) |
| Lookup an entry in a table. | |
| uint32_t | sht_size (const struct sht_ht *ht) |
| Get the number of entries in a table. | |
| _Bool | sht_empty (const struct sht_ht *ht) |
| Determine whether a table is empty. | |
| _Bool | sht_delete (struct sht_ht *ht, const void *restrict key) |
| Remove an entry from the table. | |
| _Bool | sht_pop (struct sht_ht *ht, const void *restrict key, void *restrict out) |
| Remove and return an entry from the table. | |
| _Bool | sht_replace (struct sht_ht *ht, const void *key, const void *entry) |
| Replace the entry associated with an existing key. | |
| _Bool | sht_swap (struct sht_ht *ht, const void *key, const void *entry, void *out) |
| Exchange an existing entry and a new entry. | |
| struct sht_ro_iter * | sht_ro_iter (struct sht_ht *ht) |
| Create a new read-only iterator. | |
| struct sht_rw_iter * | sht_rw_iter (struct sht_ht *ht) |
| Create a new read/write iterator. | |
| void | sht_ro_iter_free_ (struct sht_ro_iter *iter) |
| (Free a read-only iterator.) | |
| void | sht_rw_iter_free_ (struct sht_rw_iter *iter) |
| (Free a read/write iterator.) | |
| const void * | sht_ro_iter_next_ (struct sht_ro_iter *iter) |
| (Get the next entry from a read-only iterator.) | |
| void * | sht_rw_iter_next_ (struct sht_rw_iter *iter) |
| (Get the next entry from a read/write iterator.) | |
| _Bool | sht_iter_delete (struct sht_rw_iter *iter) |
| Remove the last entry returned by a read/write iterator. | |
| _Bool | sht_ro_iter_replace_ (struct sht_ro_iter *iter, const void *restrict entry) |
| (Replace the last entry returned by a read-only iterator.) | |
| _Bool | sht_rw_iter_replace_ (struct sht_rw_iter *iter, const void *restrict entry) |
| (Replace the last entry returned by a read/write iterator.) | |
| enum sht_err | sht_get_err (const struct sht_ht *ht) |
| Get the error code of a table's last error. | |
| enum sht_err | sht_ro_iter_err_ (const struct sht_ro_iter *iter) |
| (Get the error code of a read-only iterator's last error.) | |
| enum sht_err | sht_rw_iter_err_ (const struct sht_rw_iter *iter) |
| (Get the error code of a read/write iterator's last error.) | |
| const char * | sht_msg (enum sht_err err) |
| Get the description for an error code. | |
| const char * | sht_get_msg (const struct sht_ht *ht) |
| Get a description of a table's last error. | |
| const char * | sht_ro_iter_msg_ (const struct sht_ro_iter *iter) |
| (Get a description of a read-only iterator's last error.) | |
| const char * | sht_rw_iter_msg_ (const struct sht_rw_iter *iter) |
| (Get a description of a read/write iterator's last error.) | |
Variables | |
| void(* | sht_abort_print )(const char *msg) |
| Critical error printing function. | |
| #define SHT_NEW | ( | hashfn, | |
| eqfn, | |||
| etype, | |||
| ... ) |
Create a new hash table.
This macro is a wrapper for sht_new_().
| hashfn | The function that will be used to compute the hash values of keys. | |
| eqfn | The function that will be used to compare keys for equality. | |
| etype | The type of the entries to be stored in the table. | |
| [out] | ... | Optional output pointer for error reporting. |
err (if it is not NULL).| #define SHT_ITER_FREE | ( | iter | ) |
Free a hash table iterator.
| iter | The iterator. |
| #define SHT_ITER_NEXT | ( | iter | ) |
Get the next entry from an iterator.
| iter | The iterator. |
| #define SHT_ITER_REPLACE | ( | iter, | |
| entry ) |
Replace the last entry returned by an iterator.
WARNING
The new entry must have the same key as the entry being replaced. Replacing an entry with an entry that contains a different key will corrupt the table.
| iter | The iterator. |
| entry | The new entry. |
| #define SHT_ITER_ERR | ( | iter | ) |
Get the the error code of an iterator's last error.
The value returned by this macro is only valid after a previous iterator function call indicated an error.
| iter | The iterator. |
| #define SHT_ITER_MSG | ( | iter | ) |
Get a description of an iterator's last error.
The value returned by this macro is only valid after a previous iterator function call indicated an error.
| iter | The iterator. |
| typedef uint32_t(* sht_hashfn_t) (const void *restrict key, void *restrict context) |
Hash function type.
Callback function type used to calculate hash values for keys.
32-bit example, using XXH32(), which requires a seed:
64-bit example, using XXH3_64bits(), which does not require a seed:
| key | The key to be hashed. |
| context | Optional function-specific context. |
| typedef _Bool(* sht_eqfn_t) (const void *restrict key, const void *restrict entry, void *restrict context) |
Equality comparison function type.
Callback function type used to compare a key with the key of an existing bucket. This function is only called when the lower 24 bits of the hash values of the two keys are equal.
| key | The key to be compared against the key in the bucket. |
| entry | The entry whose key is to be compared. |
| context | Optional function-specific context. |
key is equal to the key in entry. | typedef void(* sht_freefn_t) (const void *restrict entry, void *restrict context) |
Free function type.
Callback function type used to free entry resources. For example:
| entry | The entry whose resources should be freed. |
| context | Optional function-specific context. |
| enum sht_err : uint8_t |
Error codes.
| struct sht_ht * sht_new_ | ( | sht_hashfn_t | hashfn, |
| sht_eqfn_t | eqfn, | ||
| size_t | esize, | ||
| size_t | ealign, | ||
| enum sht_err * | err ) |
(Create a new hash table.)
NOTE
Do not call this function directly. Use SHT_NEW().
A table returned by this function cannot be used until it has been initialized.
| hashfn | The function that will be used to compute the hash values of keys. | |
| eqfn | The function that will be used to compare keys for equality. | |
| esize | The size of the entries to be stored in the table. | |
| ealign | The alignment of the entries to be stored in the table. | |
| [out] | err | Optional output pointer for error reporting. |
err (if it is not NULL).| void sht_set_hash_ctx | ( | struct sht_ht * | ht, |
| void * | context ) |
Set the "context" for a table's hash function.
Sets the value of the context argument for all calls to the table's hash function.
NOTE
This function cannot be called after the table has been initialized. (See Abort conditions.)
| ht | The hash table. |
| context | The function-specific context. |
| void sht_set_eq_ctx | ( | struct sht_ht * | ht, |
| void * | context ) |
Set the "context" for a table's equality function.
Sets the value of the context argument for all calls to the table's equality function.
NOTE
This function cannot be called after the table has been initialized. (See Abort conditions.)
| ht | The hash table. |
| context | The function-specific context. |
| void sht_set_freefn | ( | struct sht_ht * | ht, |
| sht_freefn_t | freefn, | ||
| void * | context ) |
Set the optional entry resource free function for a table.
An entry free function is used to automatically free resources associated with table entries. It is not required in order to free the entries themselves.
NOTE
This function cannot be called after the table has been initialized. (See Abort conditions.)
| ht | The hash table. |
| freefn | The function to be used to free entry resources. |
| context | Optional function-specific context. |
| void sht_set_lft | ( | struct sht_ht * | ht, |
| uint8_t | lft ) |
Set the load factor threshold for a table.
The load factor threshold (LFT) determines when a table is expanded, in order to accomodate additional entries. The size of the table is doubled when the number of entries it contains exceeds a certain percentage of its size. That percentage is determined by the LFT. Thus, the LFT must be between 1 and 100, although values much different from the default (85) are unlikely to be very useful.
NOTE
This function cannot be called after the table has been initialized, nor can it be called with an invalid
lftvalue. (See Abort conditions.)
| ht | The hash table. |
| lft | The load factor threshold (1 - 100). |
| void sht_set_psl_limit | ( | struct sht_ht * | ht, |
| uint8_t | limit ) |
Set the PSL limit of a table.
If an entry in the table has a PSL equal to the table's PSL limit, no further entries will be allowed until 1 or more entries that hash to the same "ideal" position are removed. (See Limits and assumptions.)
NOTE
This function cannot be called after the table has been initialized, nor can it be called with an invalid
limitvalue. (See Abort conditions.)
| ht | The hash table. |
| limit | The PSL limit (1 - 127). |
| _Bool sht_init | ( | struct sht_ht * | ht, |
| uint32_t | capacity ) |
Initialize a hash table.
capacity, along with the table's load factor threshold, is used to calculate the minimum initial size of the table. Setting an appropriate initial size will avoid the need to resize the table as it grows (but will consume unnecessary memory if fewer keys are stored in the table than expected).
If capacity is 0, a default initial capacity (currently 6) is used.
NOTE
If this function succeeds, it must not be called again on the same table. A failed call may be retried, possibly with a lower
capacity. (See Abort conditions.)
| ht | The hash table to be initialized. |
| capacity | The initial capacity of the hash table (or 0). |
| void sht_free | ( | struct sht_ht * | ht | ) |
Free the resources used by a hash table.
NOTE
This function cannot be called on a table that has one or more iterators. (See Abort conditions.)
| ht | The hash table. |
| int sht_add | ( | struct sht_ht * | ht, |
| const void * | key, | ||
| const void * | entry ) |
Add an entry to the table, if its key is not already present.
NOTE
This function cannot be called on an unitialized table or a table that has one or more iterators. (See Abort conditions.)
| ht | The hash table. |
| key | The key of the new entry. |
| entry | The new entry. |
| int sht_set | ( | struct sht_ht * | ht, |
| const void * | key, | ||
| const void * | entry ) |
Unconditionally set the value associated with a key.
NOTE
This function cannot be called on an unitialized table or a table that has one or more iterators. (See Abort conditions.)
| ht | The hash table. |
| key | The key of the new entry. |
| entry | The new entry. |
| const void * sht_get | ( | struct sht_ht * | ht, |
| const void *restrict | key ) |
Lookup an entry in a table.
WARNING
The pointer returned by this function is only valid until the next time the table is changed. Structural changes to the table (adding or removing keys) can cause other entries to be moved within the table, making pointers to those entries invalid.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| key | The key for which the entry is to be retrieved. |
| uint32_t sht_size | ( | const struct sht_ht * | ht | ) |
Get the number of entries in a table.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| _Bool sht_empty | ( | const struct sht_ht * | ht | ) |
Determine whether a table is empty.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| _Bool sht_delete | ( | struct sht_ht * | ht, |
| const void *restrict | key ) |
Remove an entry from the table.
NOTE
This function cannot be called on an unitialized table or a table that has one or more iterators. (See Abort conditions.)
| ht | The hash table. |
| key | The key for which the entry is to be removed. |
| _Bool sht_pop | ( | struct sht_ht * | ht, |
| const void *restrict | key, | ||
| void *restrict | out ) |
Remove and return an entry from the table.
NOTE
This function cannot be called on an unitialized table or a table that has one or more iterators. (See Abort conditions.)
| ht | The hash table. | |
| key | The key for which the entry is to be "popped." | |
| [out] | out | Entry output buffer. Must be large enough to hold an entry. |
out. Otherwise, false (0) is returned (and the contents of out are unchanged).| _Bool sht_replace | ( | struct sht_ht * | ht, |
| const void * | key, | ||
| const void * | entry ) |
Replace the entry associated with an existing key.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| key | The key for which the value is to be replaced. |
| entry | The new entry for the key. |
| _Bool sht_swap | ( | struct sht_ht * | ht, |
| const void * | key, | ||
| const void * | entry, | ||
| void * | out ) |
Exchange an existing entry and a new entry.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| key | The key for which the value is to be replaced. |
| entry | The new entry for the key. |
| out | Output buffer for the previous entry. Must be large enough to hold an entry. (out may point to the same object as entry.) |
out. Otherwise, false (0) is returned, and the contents of out are unchanged.| struct sht_ro_iter * sht_ro_iter | ( | struct sht_ht * | ht | ) |
Create a new read-only iterator.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| struct sht_rw_iter * sht_rw_iter | ( | struct sht_ht * | ht | ) |
Create a new read/write iterator.
NOTE
This function cannot be called on an unitialized table. (See Abort conditions.)
| ht | The hash table. |
| void sht_ro_iter_free_ | ( | struct sht_ro_iter * | iter | ) |
(Free a read-only iterator.)
NOTE
Do not call this function directly. Use SHT_ITER_FREE().
| iter | The iterator. |
| void sht_rw_iter_free_ | ( | struct sht_rw_iter * | iter | ) |
(Free a read/write iterator.)
NOTE
Do not call this function directly. Use SHT_ITER_FREE().
| iter | The iterator. |
| const void * sht_ro_iter_next_ | ( | struct sht_ro_iter * | iter | ) |
(Get the next entry from a read-only iterator.)
NOTE
Do not call this function directly. Use SHT_ITER_NEXT().
| iter | The iterator. |
| void * sht_rw_iter_next_ | ( | struct sht_rw_iter * | iter | ) |
(Get the next entry from a read/write iterator.)
NOTE
Do not call this function directly. Use SHT_ITER_NEXT().
| iter | The iterator. |
| _Bool sht_iter_delete | ( | struct sht_rw_iter * | iter | ) |
| _Bool sht_ro_iter_replace_ | ( | struct sht_ro_iter * | iter, |
| const void *restrict | entry ) |
(Replace the last entry returned by a read-only iterator.)
NOTE
Do not call this function directly. Use SHT_ITER_REPLACE().
WARNING
The new entry must have the same key as the entry being replaced. Replacing an entry with an entry that contains a different key will corrupt the table.
| iter | The iterator. |
| entry | The new entry. |
| _Bool sht_rw_iter_replace_ | ( | struct sht_rw_iter * | iter, |
| const void *restrict | entry ) |
(Replace the last entry returned by a read/write iterator.)
NOTE
Do not call this function directly. Use SHT_ITER_REPLACE().
WARNING
The new entry must have the same key as the entry being replaced. Replacing an entry with an entry that contains a different key will corrupt the table.
| iter | The iterator. |
| entry | The new entry. |
| enum sht_err sht_get_err | ( | const struct sht_ht * | ht | ) |
| enum sht_err sht_ro_iter_err_ | ( | const struct sht_ro_iter * | iter | ) |
(Get the error code of a read-only iterator's last error.)
NOTE
Do not call this function directly. Use SHT_ITER_ERR().
The value returned by this function is only valid after a previous iterator function call indicated an error.
| iter | The iterator. |
| enum sht_err sht_rw_iter_err_ | ( | const struct sht_rw_iter * | iter | ) |
(Get the error code of a read/write iterator's last error.)
NOTE
Do not call this function directly. Use SHT_ITER_ERR().
The value returned by this function is only valid after a previous iterator function call indicated an error.
| iter | The iterator. |
| const char * sht_msg | ( | enum sht_err | err | ) |
Get the description for an error code.
NOTE: This function will abort the calling program if an invalid value of err is specified.
| err | The error code. Must in the range SHT_ERR_OK to SHT_ERR_COUNT - 1. |
| const char * sht_get_msg | ( | const struct sht_ht * | ht | ) |
| const char * sht_ro_iter_msg_ | ( | const struct sht_ro_iter * | iter | ) |
(Get a description of a read-only iterator's last error.)
NOTE
Do not call this function directly. Use SHT_ITER_MSG().
The value returned by this function is only valid after a previous iterator function call indicated an error.
| iter | The iterator. |
| const char * sht_rw_iter_msg_ | ( | const struct sht_rw_iter * | iter | ) |
(Get a description of a read/write iterator's last error.)
NOTE
Do not call this function directly. Use SHT_ITER_MSG().
The value returned by this function is only valid after a previous iterator function call indicated an error.
| iter | The iterator. |
|
extern |
Critical error printing function.
If the calling program violates this library's contract, the library will print an error message and abort the program. (See Abort conditions.) This variable can be set to customize how the error message is printed or logged.
| msg | The error message (not newline terminated). |