sht.c File Reference

#include "sht.h"
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Functions
enum sht_err	sht_get_err (const struct sht_ht *ht)
	Get the error code of a table'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.
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 limit)
	Set the PSL limit of a table.
_Bool	sht_init (struct sht_ht *ht, uint32_t capacity)
	Initialize a hash 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.
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.
_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.
_Bool	sht_pop (struct sht_ht *ht, const void *restrict key, void *restrict out)
	Remove and return an entry from the table.
_Bool	sht_delete (struct sht_ht *ht, const void *restrict key)
	Remove an entry from the table.
void	sht_free (struct sht_ht *ht)
	Free the resources used by a hash table.
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.
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_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.)
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.)
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.)

Function Documentation

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 185 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 201 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 234 of file sht.c.

sht_new_()

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.

Parameters

	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.

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 298 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 350 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 374 of file sht.c.

sht_set_freefn()

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

Parameters

ht	The hash table.
freefn	The function to be used to free entry resources.
context	Optional function-specific context.

See also

sht_freefn_t

Abort conditions

Definition at line 400 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 429 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 459 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 558 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 601 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 623 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 928 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 956 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 984 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 1096 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 1123 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 1311 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 1334 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 1351 of file sht.c.

sht_ro_iter()

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

Parameters

ht	The hash table.

Returns

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

See also

Abort conditions

Definition at line 1448 of file sht.c.

sht_rw_iter()

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

Parameters

ht	The hash table.

Returns

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

See also

Abort conditions

Definition at line 1469 of file sht.c.

sht_ro_iter_err_()

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.

Parameters

iter	The iterator.

Returns

A code that describes the error.

See also

SHT_ITER_STATUS()

Definition at line 1490 of file sht.c.

sht_rw_iter_err_()

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.

Parameters

iter	The iterator.

Returns

A code that describes the error.

See also

SHT_ITER_STATUS()

Definition at line 1511 of file sht.c.

sht_ro_iter_msg_()

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.

Parameters

iter	The iterator.

Returns

A string that describes the error.

See also

SHT_ITER_MSG()

Definition at line 1532 of file sht.c.

sht_rw_iter_msg_()

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.

Parameters

iter	The iterator.

Returns

A string that describes the error.

See also

SHT_ITER_MSG()

Definition at line 1553 of file sht.c.

sht_ro_iter_next_()

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

Parameters

iter	The iterator.

Returns

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

See also

SHT_ITER_NEXT()

Definition at line 1611 of file sht.c.

sht_rw_iter_next_()

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

Parameters

iter	The iterator.

Returns

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

See also

SHT_ITER_NEXT()

Definition at line 1630 of file sht.c.

sht_iter_delete()

_Bool sht_iter_delete

(

struct sht_rw_iter *

iter

)

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

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 1643 of file sht.c.

sht_ro_iter_replace_()

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

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.

See also

SHT_ITER_REPLACE()

Definition at line 1717 of file sht.c.

sht_rw_iter_replace_()

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

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.

See also

SHT_ITER_REPLACE()

Definition at line 1744 of file sht.c.

sht_ro_iter_free_()

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

Parameters

iter	The iterator.

See also

SHT_ITER_FREE()

Definition at line 1788 of file sht.c.

sht_rw_iter_free_()

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

Parameters

iter	The iterator.

See also

SHT_ITER_FREE()

Definition at line 1804 of file sht.c.