sht.h File Reference

SHT library API. More...

#include <stddef.h>
#include <stdint.h>

Go to the source code of this file.

Macros
#define	SHT_NEW(hashfn, eqfn, freefn, etype, ...)
	Create a new hash table.

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_iter_type : bool
	Iterator types. More...
enum	sht_err : uint8_t
	Error codes. More...

Functions
struct sht_ht *	sht_new_ (sht_hashfn_t hashfn, sht_eqfn_t eqfn, sht_freefn_t freefn, size_t esize, size_t ealign, enum sht_err *err)
	Create a new hash table (call via SHT_NEW()).
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_free_ctx (struct sht_ht *ht, void *context)
	Set the "context" for a table's free function.
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 limit)
	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.
uint8_t	sht_peak_psl (const struct sht_ht *ht)
	Get the "peak" probe sequence length (PSL) of a table.
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_iter *	sht_iter_new (struct sht_ht *ht, enum sht_iter_type type)
	Create a new iterator.
void	sht_iter_free (struct sht_iter *iter)
	Free an iterator.
const void *	sht_iter_next (struct sht_iter *iter)
	Get the next entry from an iterator.
bool	sht_iter_delete (struct sht_iter *iter)
	Remove the last entry returned by a read/write iterator.
bool	sht_iter_replace (struct sht_iter *iter, const void *restrict entry)
	Replace the last entry returned by an 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_iter_err (const struct sht_iter *iter)
	Get the error code of an 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_iter_msg (const struct sht_iter *iter)
	Get a description of an iterator's last error.

Variables
void(*	sht_abort_print )(const char *msg)
	Critical error printing function.

Detailed Description

SHT library API.

Definition in file sht.h.

Macro Definition Documentation

SHT_NEW

#define SHT_NEW	(		hashfn,
			eqfn,
			freefn,
			etype,
			... )

Create a new hash table.

This macro is a wrapper for sht_new_().

struct entry {
    const char      *name;
    struct in_addr  address;
};
 
struct sht_ht *ht;
enum sht_err err;
 
ht = sht_new(hashfn, eqfn, NULL, sizeof(struct entry),
             alignof(struct entry), &err);
 
// Rewrite as ...
ht = SHT_NEW(hashfn, eqfn, NULL, struct entry, &err);
 
// Without error reporting ...
ht = sht_new(hashfn, eqfn, NULL, sizeof(struct entry),
             alignof(struct entry), NULL);
 
// Becomes ...
ht = SHT_NEW(hashfn, eqfn, NULL, struct entry);

Parameters

	hashfn	Function to be used to compute the hash values of keys.
	eqfn	Function to be used to compare keys for equality.
	freefn	Function to be used to free entry resources. (May be NULL.)
	etype	The type of the entries to be stored in the table.
[out]	...	Optional output pointer for error reporting.

Returns

On success, a pointer to the new hash table is returned. On error, NULL is returned, and an error code is returned in err (if it is not NULL).

See also

sht_new_()

Definition at line 426 of file sht.h.

Typedef Documentation

sht_hashfn_t

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:

uint32_t myhash32(const void *restrict key, void *restrict context)
{
    const struct mykey *k = key;
    const XXH32_hash_t *seed = ctx;
 
    return XXH32(k, sizeof *k, *seed);
}

64-bit example, using XXH3_64bits(), which does not require a seed:

uint32_t myhash64(const void *restrict key, const void *restrict)
{
    const struct mykey *k = key;
 
    // Throw away the upper 32 bits
    return (uint32_t)XXH3_64bits(k, sizeof *k);
}

Parameters

key	The key to be hashed.
context	Optional function-specific context.

Returns

The hash value of the key.

Definition at line 103 of file sht.h.

sht_eqfn_t

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.

struct my_entry {
    const char      *name;
    struct in_addr  address;
};
 
bool my_cmp(const void *restrict key, const void *restrict entry,
             void *restrict)
{
    const char *const name = key;
    const struct my_entry *const e = entry;
 
    return strcmp(name, e->name) == 0;
}

Parameters

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.

Returns

A boolean value that indicates whether key is equal to the key in entry.

Definition at line 137 of file sht.h.

sht_freefn_t

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:

struct my_entry {
    const char      *name;
    struct in_addr  address;
};
 
void my_free(const void *restrict entry, void *restrict)
{
    const struct my_entry *const e = entry;
    free(e->name);
}

Parameters

entry	The entry whose resources should be freed.
context	Optional function-specific context.

Definition at line 162 of file sht.h.

Enumeration Type Documentation

sht_iter_type

enum sht_iter_type : bool

Iterator types.

Enumerator
SHT_ITER_RO	Read-only iterator.
SHT_ITER_RW	Read/write iterator.

Definition at line 182 of file sht.h.

sht_err

enum sht_err : uint8_t

Error codes.

Enumerator
SHT_ERR_OK	No error.
SHT_ERR_ALLOC	Memory allocation failed.
SHT_ERR_BAD_ESIZE	Entry size too large (> 16KiB).
SHT_ERR_TOOBIG	Requested table size too large.
SHT_ERR_BAD_HASH	Too many hash collisions.
SHT_ERR_ITER_LOCK	Can't acquire iterator lock.
SHT_ERR_ITER_COUNT	Table has too many iterators.
SHT_ERR_ITER_NO_LAST	Iterator at beginning or end.
SHT_ERR_COUNT	(Not an error; used for bounds checks.)

Definition at line 195 of file sht.h.

Function Documentation

sht_new_()

struct sht_ht * sht_new_	(	sht_hashfn_t	hashfn,
		sht_eqfn_t	eqfn,
		sht_freefn_t	freefn,
		size_t	esize,
		size_t	ealign,
		enum sht_err *	err )

Create a new hash table (call via SHT_NEW()).

NOTE

Do not call this function directly. Use SHT_NEW().

A table returned by this function cannot be used until it has been initialized.

Parameters

	hashfn	Function to be used to compute the hash values of keys.
	eqfn	Function to be used to compare keys for equality.
	freefn	Function to be used to free entry resources. (May be NULL.)
	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.

Returns

On success, a pointer to the new hash table is returned. On error, NULL is returned, and an error code is returned in err (if it is not NULL).

See also

SHT_NEW()

Definition at line 283 of file sht.c.

sht_set_hash_ctx()

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.)

Parameters

ht	The hash table.
context	The function-specific context.

See also

sht_hashfn_t

Abort conditions

Definition at line 336 of file sht.c.

sht_set_eq_ctx()

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.)

Parameters

ht	The hash table.
context	The function-specific context.

See also

sht_eqfn_t

Abort conditions

Definition at line 360 of file sht.c.

sht_set_free_ctx()

void sht_set_free_ctx	(	struct sht_ht *	ht,
		void *	context )

Set the "context" for a table's free function.

Sets the value of the context argument for all calls to the table's free function.

NOTE

This function cannot be called after the table has been initialized. (See Abort conditions.)

Parameters

ht	The hash table.
context	Optional function-specific context.

See also

sht_freefn_t

Abort conditions

Definition at line 384 of file sht.c.

sht_set_lft()

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 lft value. (See Abort conditions.)

Parameters

ht	The hash table.
lft	The load factor threshold (1 - 100).

See also

Abort conditions

Definition at line 412 of file sht.c.

sht_set_psl_limit()

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 limit value. (See Abort conditions.)

Parameters

ht	The hash table.
limit	The PSL limit (1 - 127).

See also

Limits and assumptions

Abort conditions

Definition at line 442 of file sht.c.

sht_init()

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.)

Parameters

ht	The hash table to be initialized.
capacity	The initial capacity of the hash table (or 0).

Returns

On success, true (1) is returned. On failure, false (0) is returned, and the table's error status is set.

See also

Abort conditions

Definition at line 541 of file sht.c.

sht_free()

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.)

Parameters

ht	The hash table.

See also

Abort conditions

Definition at line 1352 of file sht.c.

sht_add()

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.)

Parameters

ht	The hash table.
key	The key of the new entry.
entry	The new entry.

Returns

If an error occurs, -1 is returned, the error status of the table is set, and the state of the table is otherwise unchanged. On success, 0 is returned if the key was not already present in the table, and the new entry has been added; 1 indicates that the key was already present in the table, and the state of the table is unchanged.

See also

sht_set()

Abort conditions

Definition at line 929 of file sht.c.

sht_set()

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.)

Parameters

ht	The hash table.
key	The key of the new entry.
entry	The new entry.

Returns

If an error occurs, -1 is returned, the error status of the table is set, and the state of the table is otherwise unchanged. On success, 0 is returned if the key was not already present in the table, and the new entry has been added; 1 indicates that the key was already present in the table, and the new entry has replaced it.

See also

sht_add()

Abort conditions

Definition at line 957 of file sht.c.

sht_get()

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.)

Parameters

ht	The hash table.
key	The key for which the entry is to be retrieved.

Returns

If the the key is present in the table, a pointer to the key's entry is returned. Otherwise, NULL is returned.

See also

Abort conditions

Definition at line 985 of file sht.c.

sht_size()

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.)

Parameters

ht	The hash table.

Returns

The number of entries in the table.

See also

Abort conditions

Definition at line 584 of file sht.c.

sht_empty()

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.)

Parameters

ht	The hash table.

Returns

True (1) if the table is empty; false (0) if it has at least one entry.

See also

Abort conditions

Definition at line 606 of file sht.c.

sht_peak_psl()

uint8_t sht_peak_psl

(

const struct sht_ht *

ht

)

Get the "peak" probe sequence length (PSL) of a table.

The peak PSL is the highest PSL value of any entry in the table since the time that the table was expanded (or created). It provides an indication of the performance of the table's hash function.

At the default load factor threshold (85%), PSL values should generally remain in the single digits, or the low teens at most, unless the hash function being used is extremely poor.

Parameters

ht	The hash table.

Definition at line 626 of file sht.c.

sht_delete()

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.)

Parameters

ht	The hash table.
key	The key for which the entry is to be removed.

Returns

If the key was present in the table, true (1) is returned. Otherwise, false (0) is returned.

See also

sht_pop()

Abort conditions

Definition at line 1335 of file sht.c.

sht_pop()

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.)

Parameters

	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.

Returns

If the key was present in the table, true (1) is returned, and its entry is stored in out. Otherwise, false (0) is returned (and the contents of out are unchanged).

See also

sht_delete()

Abort conditions

Definition at line 1312 of file sht.c.

sht_replace()

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.)

Parameters

ht	The hash table.
key	The key for which the value is to be replaced.
entry	The new entry for the key.

Returns

If the key was present in the table, true (1) is returned, and the entry associated with the key is replaced with the new entry. Otherwise, false (0) is returned.

See also

Abort conditions

Definition at line 1097 of file sht.c.

sht_swap()

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.)

Parameters

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.)

Returns

If the key was present in the table, true (1) is returned, the entry associated with the key is replaced with the new entry, and the previous entry is copied to out. Otherwise, false (0) is returned, and the contents of out are unchanged.

See also

Abort conditions

Definition at line 1124 of file sht.c.

sht_iter_new()

struct sht_iter * sht_iter_new	(	struct sht_ht *	ht,
		enum sht_iter_type	type )

Create a new iterator.

Parameters

ht	The hash table.
type	The type of the iterator (read-only or read/write).

Returns

On success, a pointer to the new iterator is returned. If memory allocation fails, NULL is returned, and the error status of the table is set.

Definition at line 1386 of file sht.c.

sht_iter_free()

void sht_iter_free

(

struct sht_iter *

iter

)

Free an iterator.

Parameters

iter	The iterator.

Definition at line 1564 of file sht.c.

sht_iter_next()

const void * sht_iter_next

(

struct sht_iter *

iter

)

Get the next entry from an iterator.

Parameters

iter	The iterator.

Returns

A pointer to the next entry, if any. If no more entries are available, NULL is returned.

Definition at line 1467 of file sht.c.

sht_iter_delete()

bool sht_iter_delete

(

struct sht_iter *

iter

)

Remove the last entry returned by a read/write iterator.

NOTE

This function cannot be called on a read-only iterator. (See Abort conditions.)

Parameters

iter	The iterator.

Returns

On success, true (1) is returned. On error, false (0) is returned and the error status of the iterator is set.

Definition at line 1507 of file sht.c.

sht_iter_replace()

bool sht_iter_replace	(	struct sht_iter *	iter,
		const void *restrict	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.

Parameters

iter	The iterator.
entry	The new entry.

Returns

On success, true (1) is returned. On error, false (0) is returned and the error status of the iterator is set.

Definition at line 1544 of file sht.c.

sht_get_err()

enum sht_err sht_get_err

(

const struct sht_ht *

ht

)

Get the error code of a table's last error.

The value returned by this function is only valid after a previous function call indicated an error.

Parameters

ht	The hash table.

Returns

A code that describes the error.

Definition at line 170 of file sht.c.

sht_iter_err()

enum sht_err sht_iter_err

(

const struct sht_iter *

iter

)

Get the error code of an iterator's last error.

The value returned by this function is only valid after a previous iterator function call indicated an error.

Parameters

iter	The iterator

Returns

A code that describes the error.

Definition at line 1439 of file sht.c.

sht_msg()

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.

Parameters

err	The error code. Must in the range SHT_ERR_OK to SHT_ERR_COUNT - 1.

Returns

A string describing the error code.

Definition at line 186 of file sht.c.

sht_get_msg()

const char * sht_get_msg

(

const struct sht_ht *

ht

)

Get a description of a table's last error.

The value returned by this function is only valid after a previous function call indicated an error.

Parameters

ht	The hash table.

Returns

A string describing the error.

Definition at line 218 of file sht.c.

sht_iter_msg()

const char * sht_iter_msg

(

const struct sht_iter *

iter

)

Get a description of an iterator's last error.

The value returned by this function is only valid after a previous iterator function call indicated an error.

Parameters

iter	The iterator.

Returns

A string that describes the error.

Definition at line 1454 of file sht.c.

Variable Documentation

sht_abort_print

void(* sht_abort_print) (const char *msg) ( const char * msg )

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.

static void log_sht_err(const char *msg)
{
    syslog(LOG_CRIT, "SHT library error: %s", msg);
}
 
sht_abort_print = log_sht_err;

Parameters

msg	The error message (not newline terminated).

See also

Abort conditions

Definition at line 146 of file sht.c.