A hash table utilizing separate chaining for collision resolution. More...

Data Structures
struct	cstl_hash_node
	Node to anchor an element within a hash. More...

struct	cstl_hash
	Hash object. More...

Macros
#define	CSTL_HASH_INITIALIZER(TYPE, MEMB)
	Constant initialization of a hash object.

#define	DECLARE_CSTL_HASH(NAME, TYPE, MEMB) struct cstl_hash NAME = CSTL_HASH_INITIALIZER(TYPE, MEMB)
	(Statically) declare and initialize a hash

Typedefs
typedef size_t	cstl_hash_func_t(size_t k, size_t m)
	Function type for hashing a key into a bucket.

Functions
static void	cstl_hash_init (struct cstl_hash *const h, const size_t off)
	Initialize a hash object.

size_t	cstl_hash_size (const struct cstl_hash *const h)
	Get the number of objects in the hash.

float	cstl_hash_load (const struct cstl_hash *const h)
	Get the average number of nodes per bucket.

void	cstl_hash_shrink_to_fit (struct cstl_hash *h)
	Free memory associated with excess buckets.

void	cstl_hash_resize (struct cstl_hash h, size_t n, cstl_hash_func_t f)
	Resize the hash table.

void	cstl_hash_rehash (struct cstl_hash *h)
	Rehash the hash table.

void	cstl_hash_insert (struct cstl_hash h, size_t k, void e)
	Insert an item into the hash.

void *	cstl_hash_find (struct cstl_hash h, size_t k, cstl_const_visit_func_t visit, void *priv)
	Lookup/find a previously inserted object in the hash.

void	cstl_hash_erase (struct cstl_hash h, void e)
	Remove an object from the hash.

int	cstl_hash_foreach (struct cstl_hash h, cstl_visit_func_t visit, void *priv)
	Visit each object within a hash table.

int	cstl_hash_foreach_const (const struct cstl_hash h, cstl_const_visit_func_t visit, void *priv)
	Visit each object within a hash table.

void	cstl_hash_clear (struct cstl_hash h, cstl_xtor_func_t clr)
	Remove all elements from the hash.

static void	cstl_hash_swap (struct cstl_hash const a, struct cstl_hash const b)
	Swap the hash objects at the two given locations.

Built-in key hashing functions
size_t	cstl_hash_div (size_t k, size_t m)
	Hash by division.

size_t	cstl_hash_mul (size_t k, size_t m)
	Hash by multiplication.

Detailed Description

A hash table utilizing separate chaining for collision resolution.

Macro Definition Documentation

◆ CSTL_HASH_INITIALIZER

#define CSTL_HASH_INITIALIZER	(	TYPE,
		MEMB
	)

Value:

    {                                           \
    .bucket = {                                 \
        .at = NULL,                             \
        .count = 0,                             \
        .capacity = 0,                          \
        .hash = NULL,                           \
        .cst = false,                           \
        .rh = {                                 \
            .hash = NULL,                       \
        },                                      \
    },                                          \
    .count = 0,                                 \
    .off = offsetof(TYPE, MEMB),                \
}

Constant initialization of a hash object.

Parameters

TYPE	The type of object that the hash will hold
MEMB	The name of the `cstl_hash_node` member within `TYPE`.

See also: cstl_hash_node for a description of the relationship between TYPE and MEMB

Definition at line 145 of file hash.h.

◆ DECLARE_CSTL_HASH

#define DECLARE_CSTL_HASH	(	NAME,
		TYPE,
		MEMB
	)	struct cstl_hash NAME = CSTL_HASH_INITIALIZER(TYPE, MEMB)

(Statically) declare and initialize a hash

Parameters

NAME	The name of the variable being declared
TYPE	The type of object that the hash will hold
MEMB	The name of the `cstl_hash_node` member within `TYPE`.

See also: cstl_hash_node for a description of the relationship between TYPE and MEMB

Definition at line 170 of file hash.h.

Typedef Documentation

◆ cstl_hash_func_t

typedef size_t cstl_hash_func_t(size_t k, size_t m)

Function type for hashing a key into a bucket.

Each element inserted into the hash has an integer associated with it, aka a "key". This key must be "hashed" in order to fit into the hash table. The function that does this hashing must be of this type.

Parameters

[in]	k	The key to be hashed
[in]	m	The size of the hash table

Returns: A value in the range [0, m)

Definition at line 35 of file hash.h.

Function Documentation

◆ cstl_hash_clear()

void cstl_hash_clear	(	struct cstl_hash *	h,
		cstl_xtor_func_t *	clr
	)

Remove all elements from the hash.

Parameters

[in]	h	A pointer to the hash
[in]	clr	A pointer to a function to be called for each element in the hash. The function may be NULL.

All elements are removed from the hash and the clr function is called for each element that was in the hash. The order in which the elements are removed and clr is called is not specified, but the callee may take ownership of an element at the time that clr is called for that element and not before.

Upon return from this function, the hash contains no elements, and is as it was immediately after being initialized. No further operations on the hash are necessary to make it ready to go out of scope or be destroyed.

Definition at line 474 of file hash.c.

◆ cstl_hash_div()

size_t cstl_hash_div	(	size_t	k,
		size_t	m
	)

Hash by division.

The key is hashed by dividing it by the number of buckets in the table and returning the remainder.

Parameters

[in]	k	The key to be hashed
[in]	m	The size of the hash table

Returns: A value in the range [0, m)

Definition at line 10 of file hash.c.

◆ cstl_hash_erase()

void cstl_hash_erase	(	struct cstl_hash *	h,
		void *	e
	)

Remove an object from the hash.

Parameters

[in]	h	A pointer to the hash object
[in]	e	A pointer to the object to be removed. This pointer must be to the actual object to be removed, not just to an object that would compare as equal

Definition at line 434 of file hash.c.

◆ cstl_hash_find()

void * cstl_hash_find	(	struct cstl_hash *	h,
		size_t	k,
		cstl_const_visit_func_t *	visit,
		void *	priv
	)

Lookup/find a previously inserted object in the hash.

Parameters

[in]	h	A pointer to the hash object
[in]	k	The key associated with the object being sought
[in]	visit	A pointer to a function that will be called for each object with a matching key. The called function should return a non-zero value when the desired object is found. The pointer may be NULL, in which case, the first object with a matching key will be returned.
[in]	priv	A pointer, belonging to the caller, that will be passed to each invocation of the `visit` function

Returns: A pointer to the object that was found

Return values

NULL	No object with a matching key was found, or the `visit` function did not identify a matching object

Definition at line 386 of file hash.c.

◆ cstl_hash_foreach()

int cstl_hash_foreach	(	struct cstl_hash *	h,
		cstl_visit_func_t *	visit,
		void *	priv
	)

Visit each object within a hash table.

Parameters

[in]	h	A pointer to the hash object
[in]	visit	A function to be called for each object in the table. The function should return zero to continue visiting objects or a non-zero value to terminate the foreach function. The visit function may alter the object (but not the key) and/or remove the current object from the table.
[in]	priv	A pointer, belonging to the caller, that will be passed to each invocation of the `visit` function

Note: This function will force an in-progress rehash to complete. Consider cstl_hash_foreach_const() if the visited nodes do not need to be modified or removed.

Returns: The value returned by the last invocation of visit or 0

Definition at line 205 of file hash.c.

◆ cstl_hash_foreach_const()

int cstl_hash_foreach_const	(	const struct cstl_hash *	h,
		cstl_const_visit_func_t *	visit,
		void *	priv
	)

Visit each object within a hash table.

Parameters

[in]	h	A pointer to the hash object
[in]	visit	A function to be called for each object in the table. The function should return zero to continue visiting objects or a non-zero value to terminate the foreach function.
[in]	priv	A pointer, belonging to the caller, that will be passed to each invocation of the `visit` function

Returns: The value returned by the last invocation of visit or 0

Definition at line 225 of file hash.c.

◆ cstl_hash_init()

static void cstl_hash_init	(	struct cstl_hash *const	h,
		const size_t	off
	)

inlinestatic

Initialize a hash object.

Parameters

[in,out]	h	A pointer to the object to be initialized
[in]	off	The offset of the `cstl_hash_node` object within the object(s) that will be stored in the hash

Note: The hash object is not ready for use until it has been resized via the cstl_hash_resize() function

Definition at line 183 of file hash.h.

◆ cstl_hash_insert()

void cstl_hash_insert	(	struct cstl_hash *	h,
		size_t	k,
		void *	e
	)

Insert an item into the hash.

Parameters

[in]	h	A pointer to the hash object
[in]	k	The key associated with the object being inserted
[in]	e	A pointer to the object to insert

If the caller maintains a pointer to the object or otherwise gets a pointer via cstl_hash_find() or cstl_hash_foreach(), the caller may modify the object as desired. However, the key associated with the object must not be changed.

Definition at line 330 of file hash.c.

◆ cstl_hash_load()

float cstl_hash_load ( const struct cstl_hash *const h )

Get the average number of nodes per bucket.

Returns: The average number of nodes per bucket, i.e. the total number of nodes divided by the number of buckets

Definition at line 216 of file hash.h.

◆ cstl_hash_mul()

size_t cstl_hash_mul	(	size_t	k,
		size_t	m
	)

Hash by multiplication.

The key is hashed by multiplying it by a value phi and then multiplying the fractional portion of that result by m. In this case, the value phi is the golden ratio (1.618034), as suggested by Knuth.

Parameters

[in]	k	The key to be hashed
[in]	m	The size of the hash table

Returns: A value in the range [0, m)

Definition at line 15 of file hash.c.

◆ cstl_hash_rehash()

void cstl_hash_rehash ( struct cstl_hash * h )

Rehash the hash table.

After resizing or changing the hash function for the table, all nodes in the table must be moved to new buckets. This is done incrementally, spreading the time cost over multiple operations on the table. However, this function may be used to force the operation to run to completion immediately.

If a rehash is not currently in progress, the function returns immediately.

Parameters

[in,out] h A pointer to the hash object

Definition at line 120 of file hash.c.

◆ cstl_hash_resize()

void cstl_hash_resize	(	struct cstl_hash *	h,
		size_t	n,
		cstl_hash_func_t *	f
	)

Resize the hash table.

Parameters

[in,out]	h	A pointer to the hash object
[in]	n	The desired number of buckets in the table
[in]	f	The function used by this hash object to hash keys. If this parameter is NULL, the existing hash function will be reused. If there is no existing hash function (because the hash object is in an initialized state), the cstl_hash_mul() function will be used.

If n is zero, this function does nothing. Once this function has been called, cstl_hash_clear() must be called to re/de-initialize the object. If the function fails, the original hash object is undisturbed.

Definition at line 255 of file hash.c.

◆ cstl_hash_shrink_to_fit()

void cstl_hash_shrink_to_fit ( struct cstl_hash * h )

Free memory associated with excess buckets.

As the table is resized, the number of buckets is increased or decreased. When decreasing, the memory associated with unused buckets is not released. This function releases that memory. The number of buckets is not changed.

Parameters

[in,out] h A pointer to a hash object

Definition at line 315 of file hash.c.

◆ cstl_hash_size()

size_t cstl_hash_size ( const struct cstl_hash *const h )

Get the number of objects in the hash.

Parameters

[in] h A pointer to the hash

Returns: The number of objects in the hash

Definition at line 205 of file hash.h.

◆ cstl_hash_swap()

static void cstl_hash_swap	(	struct cstl_hash *const	a,
		struct cstl_hash *const	b
	)

inlinestatic

Swap the hash objects at the two given locations.

Parameters

[in,out]	a	A pointer to a hash
[in,out]	b	A pointer to a(nother) hash

The hashes at the given locations will be swapped such that upon return, a will contain the hash previously pointed to by b and vice versa.

Definition at line 378 of file hash.h.

Data Structures

Macros

Typedefs

Functions

Built-in key hashing functions

Detailed Description

Macro Definition Documentation

◆ CSTL_HASH_INITIALIZER

◆ DECLARE_CSTL_HASH

Typedef Documentation

◆ cstl_hash_func_t

Function Documentation

◆ cstl_hash_clear()

◆ cstl_hash_div()

◆ cstl_hash_erase()

◆ cstl_hash_find()

◆ cstl_hash_foreach()

◆ cstl_hash_foreach_const()

◆ cstl_hash_init()

◆ cstl_hash_insert()

◆ cstl_hash_load()

◆ cstl_hash_mul()

◆ cstl_hash_rehash()

◆ cstl_hash_resize()

◆ cstl_hash_shrink_to_fit()

◆ cstl_hash_size()

◆ cstl_hash_swap()