htbl.h File Reference

#include <stdbool.h>
#include <stdlib.h>
#include <stdint.h>
#include "sysmacros.h"
#include "types.h"
#include "list.h"

Include dependency graph for htbl.h:

Go to the source code of this file.

Data Structures
struct	htbl_t
struct	htbl2_t

Macros
#define	HTBL_VALUE_MULTI(x)   htbl_value_multi(x)

Typedefs
typedef struct htbl2_multi_value_s	htbl2_multi_value_t

Functions
void	htbl_create (htbl_t *htbl, size_t tbl_sz, size_t key_sz, bool_t multi_value)
void	htbl_destroy (htbl_t *htbl)
void	htbl2_create (htbl2_t *htbl, size_t tbl_sz, size_t key_sz, size_t value_sz, bool multi_value)
void	htbl2_destroy (htbl2_t *htbl)
void	htbl_empty (htbl_t *htbl, void(*func)(void *value, void *userinfo), void *userinfo)
void	htbl2_empty (htbl2_t *htbl, size_t value_sz, void(*func)(void *value, void *userinfo), void *userinfo)
size_t	htbl_count (const htbl_t *htbl)
size_t	htbl2_count (const htbl2_t *htbl)
void	htbl_set (htbl_t *htbl, const void *key, void *value)
void	htbl2_set (htbl2_t *htbl, const void *key, size_t key_sz, void *value, size_t value_sz)
void	htbl_remove (htbl_t *htbl, const void *key, bool_t nil_ok)
void	htbl2_remove (htbl2_t *htbl, const void *key, size_t key_sz, bool nil_ok)
void	htbl_remove_multi (htbl_t *htbl, const void *key, htbl_multi_value_t *list_item)
void	htbl2_remove_multi (htbl2_t *htbl, const void *key, size_t key_sz, htbl2_multi_value_t *list_item)
void *	htbl_lookup (const htbl_t *htbl, const void *key)
void *	htbl2_lookup (const htbl2_t *htbl, const void *key, size_t key_sz, size_t value_sz)
const list_t *	htbl_lookup_multi (const htbl_t *htbl, const void *key)
const list_t *	htbl2_lookup_multi (const htbl2_t *htbl, const void *key, size_t key_sz)
void *	htbl_value_multi (const htbl_multi_value_t *mv)
void *	htbl2_value_multi (const htbl2_multi_value_t *mv, size_t value_sz)
void	htbl_foreach (const htbl_t *htbl, void(*func)(const void *key, void *value, void *userinfo), void *userinfo)
void	htbl2_foreach (const htbl2_t *htbl, size_t key_sz, size_t value_sz, void(*func)(const void *key, void *value, void *userinfo), void *userinfo)
char *	htbl_dump (const htbl_t *htbl, bool_t printable_keys)
static void	htbl_free (void *obj, void *unused)

Detailed Description

This module implements a simple general-purpose hash table.

Note

The hash table functionality is dependent on the CRC64 subsystem, so be sure to call crc64_init() before initializing the first hash table.

See also

htbl_t

Definition in file htbl.h.

Macro Definition Documentation

HTBL_VALUE_MULTI

#define HTBL_VALUE_MULTI

(

x

)

htbl_value_multi(x)

Legacy backwards compatibility macro that just invokes htbl_value_multi().

Definition at line 127 of file htbl.h.

Typedef Documentation

htbl2_multi_value_t

typedef struct htbl2_multi_value_s htbl2_multi_value_t

Definition at line 77 of file htbl.h.

Function Documentation

htbl2_count()

size_t htbl2_count

(

const htbl2_t *

htbl

)

Definition at line 241 of file htbl.c.

htbl2_create()

void htbl2_create	(	htbl2_t *	htbl,
		size_t	tbl_sz,
		size_t	key_sz,
		size_t	value_sz,
		bool	multi_value
	)

Definition at line 134 of file htbl.c.

htbl2_destroy()

void htbl2_destroy

(

htbl2_t *

htbl

)

Definition at line 165 of file htbl.c.

htbl2_empty()

void htbl2_empty	(	htbl2_t *	htbl,
		size_t	value_sz,
		void(*)(void *value, void *userinfo)	func,
		void *	userinfo
	)

Definition at line 223 of file htbl.c.

htbl2_foreach()

void htbl2_foreach	(	const htbl2_t *	htbl,
		size_t	key_sz,
		size_t	value_sz,
		void(*)(const void *key, void *value, void *userinfo)	func,
		void *	userinfo
	)

Definition at line 550 of file htbl.c.

htbl2_lookup()

void * htbl2_lookup	(	const htbl2_t *	htbl,
		const void *	key,
		size_t	key_sz,
		size_t	value_sz
	)

Definition at line 471 of file htbl.c.

htbl2_lookup_multi()

const list_t * htbl2_lookup_multi	(	const htbl2_t *	htbl,
		const void *	key,
		size_t	key_sz
	)

Definition at line 501 of file htbl.c.

htbl2_remove()

void htbl2_remove	(	htbl2_t *	htbl,
		const void *	key,
		size_t	key_sz,
		bool	nil_ok
	)

Definition at line 370 of file htbl.c.

htbl2_remove_multi()

void htbl2_remove_multi	(	htbl2_t *	htbl,
		const void *	key,
		size_t	key_sz,
		htbl2_multi_value_t *	list_item
	)

Definition at line 427 of file htbl.c.

htbl2_set()

void htbl2_set	(	htbl2_t *	htbl,
		const void *	key,
		size_t	key_sz,
		void *	value,
		size_t	value_sz
	)

Definition at line 319 of file htbl.c.

htbl2_value_multi()

void * htbl2_value_multi	(	const htbl2_multi_value_t *	mv,
		size_t	value_sz
	)

Definition at line 587 of file htbl.c.

htbl_count()

size_t htbl_count

(

const htbl_t *

htbl

)

Returns

The number of values stored in the hash table.

Definition at line 234 of file htbl.c.

htbl_create()

void htbl_create	(	htbl_t *	htbl,
		size_t	tbl_sz,
		size_t	key_sz,
		bool_t	multi_value
	)

Initializes a new hash table.

Note

The hash table functionality is dependent on the CRC64 subsystem, so be sure to call crc64_init() before initializing the first hash table.

Parameters

htbl	Pointer to the hash table which is to be initialized.
tbl_sz	Hash table size. Once initialized, hash tables retain a fixed size and cannot be changed, so pick a size wisely here. The size affects the hash table's memory-vs-time performance. The bigger the hash table, the less of a chance of hash collisions requiring an extensive search, but that also uses more memory. A good rule of thumb is to size the hash table to double the maximum number of elements expected to be in the hash table.
key_sz	Size of the hash keys to be used in the hash table. This will be the size of the key objects used in htbl_lookup(), htbl_set() and similar.
multi_value	Controls whether the hash table will support duplicate values. This then changes how you need to look up entries inside of the hash table (see htbl_lookup() and htbl_lookup_multi()).

Definition at line 127 of file htbl.c.

htbl_destroy()

void htbl_destroy

(

htbl_t *

htbl

)

Deinitializes a hash table which was initialized using htbl_create(). The hash table must be empty at the time that htbl_destroy() is called. If you want to quickly empty the entire hash table, see htbl_empty().

Note

This doesn't call free() on the htbl_t argument. If you have dynamically allocated the htbl_t object, you will need to free it yourself after calling htbl_destroy(). Also note that simply free()ing a htbl_t isn't enough to free all memory associated with a hash table. You must call htbl_destroy() on every hash table which you have initialized using htbl_create().

See also

htbl_create()

Definition at line 154 of file htbl.c.

htbl_dump()

char * htbl_dump	(	const htbl_t *	htbl,
		bool_t	printable_keys
	)

Deprecated:

Dumps a hash table's context in text form. This has limited usefulness and shouldn't be used too much.

Returns

A string containing a printable description of the contents of the hash table. Free with lacf_free().

Definition at line 602 of file htbl.c.

htbl_empty()

void htbl_empty	(	htbl_t *	htbl,
		void(*)(void *value, void *userinfo)	func,
		void *	userinfo
	)

Removes all entries from a hash table. This can be used to either reset the hash table to a clean, or to prepare the hash table for deinitialization via htbl_destroy().

Parameters

func

Optional callback, which will be invoked for every element in the hash table, as it's being removed. You can use this to free memory of the table values, or to deinitialize them in some way. The first argument to the function will be the hash table value, while the second one will be the userinfo you provide in this call. If you do not want to use this callback, pass NULL here. If your values only need to be freed using the standard free() function, you can pass htbl_free() in this this argument and setting userinfo to NULL. This is a simple utility function which calls free() using your own heap allocator on every value it receives as part of the htbl_empty() call.

userinfo

Optional argument, which will be passed to the func callback above in the second argument.

Definition at line 203 of file htbl.c.

htbl_foreach()

void htbl_foreach	(	const htbl_t *	htbl,
		void(*)(const void *key, void *value, void *userinfo)	func,
		void *	userinfo
	)

Walks the hash table, iterating over each value in the table. It is safe to add or remove entries from the hash table from within the callback, although the walk may not pass over the newly added values.

Parameters

htbl	The hash table to walk.
func	A callback which will be invoked for every value stored in the hash table. The first and second arguments to the callback will be set to the key and value respectively. The third argument is the value of the userinfo parameter.
userinfo	Optional parameter which will be passed on to the func argument in the third parameter.

Definition at line 521 of file htbl.c.

htbl_free()

static void htbl_free ( void *  obj, void *  unused  )

static

Utility function that can be passed in the second argument of htbl_empty() if your values only require a standard C free() call using your own heap allocator. You can use this as a shorthand to freeing all the values in a hash table, instead of having to write a custom callback every time.

Note

This only calls free() and does no other deinitialization of the memory pointed to by the hash table value. Do NOT use this if your values need more complex deinitialization.

Definition at line 149 of file htbl.h.

htbl_lookup()

void * htbl_lookup	(	const htbl_t *	htbl,
		const void *	key
	)

Performs a hash table lookup. The hash table must have been initialized with multi_value set to B_FALSE in htbl_create().

Parameters

key	The key under which the value was stored. This must point to a memory buffer of size key_sz as passed in the initial htbl_create() call.

Returns

The original value which was stored under the key, if it exists in the hash table. If no value was stored under key, this returns NULL instead.

Definition at line 462 of file htbl.c.

htbl_lookup_multi()

const list_t * htbl_lookup_multi	(	const htbl_t *	htbl,
		const void *	key
	)

Performs a hash table lookup. The hash table must have been initialized with multi_value set to B_TRUE in htbl_create().

Parameters

key	The key under which the value was stored. This must point to a memory buffer of size key_sz as passed in the initial htbl_create() call.

Returns

If at least one value exists stored under key, this function returns a list_t of htbl_multi_value_t structures. You must not modify any of the fields of the returned structure, only access the value stored within using htbl_value_multi().

If no values are stored under key, returns NULL.

Definition at line 492 of file htbl.c.

htbl_remove()

void htbl_remove	(	htbl_t *	htbl,
		const void *	key,
		bool_t	nil_ok
	)

Removes a value from a hash table. If the hash table was created with multi_value set to B_TRUE in htbl_create(), then this will remove all values stored under key. If you want more fine-grained control over which values to remove in a multi-value table, use htbl_remove_multi().

Parameters

key	The key under which the value was stored. This must point to a memory buffer of size key_sz as passed in the initial htbl_create() call.
nil_ok	If set to B_TRUE, the value not existing in the hash table is considered OK. If set to B_FALSE, if the value in the hash table doesn't exist, an assertion failure is triggered.

Definition at line 341 of file htbl.c.

htbl_remove_multi()

void htbl_remove_multi	(	htbl_t *	htbl,
		const void *	key,
		htbl_multi_value_t *	list_item
	)

Removes a single value from a multi-value enabled hash table. The normal htbl_remove() function removes all values paired to a single key, so this function gives you finer control to only remove specific values.

Parameters

key	The key for which to remove the value.
list_item	The htbl_multi_value_t as contained in the list returned by htbl_lookup_multi().

Example

list_t *values = htbl_lookup_multi(my_hash_table, my_key);
if (values != NULL) {
   for (htbl_multi_value_t *mv = list_head(values), *mv_next = NULL;
       mv != NULL; mv = mv_next) {
       // Get the next element in the list early, in case we need
       // to remove the current one (which would mean we can no
       // longer use it in list_next()).
       mv_next = list_next(values, mv);
       if (want_to_remove_this_item(htbl_value_multi(mv)) {
           htbl_remove_multi(my_hash_table, my_key, mv);
       }
   }
}

Definition at line 402 of file htbl.c.

htbl_set()

void htbl_set	(	htbl_t *	htbl,
		const void *	key,
		void *	value
	)

Stores a new value in a hash table. If the value already exists, what happens depends on whether the hash table was created with multi_value set to B_TRUE or B_FALSE in htbl_create():

• If multi-values were disabled, the old value is transparently replaced in the hash table.
• If multi-values were enable, the new value is stored side-by-side in the hash table. You can then find both values in the hash table using htbl_lookup_multi().

  Parameters

  key	The hash key under which to store the value. This must point to a memory buffer of size key_sz as passed in the initial htbl_create() call. The key itself is copied into the hash table, so you don't have to keep the memory pointed at by key allocated after the call to htbl_set() returns.
  value	The value which will be stored under key. Hash table values are stored by reference, so be sure not to de-allocate object pointed to by value, if you need to dereference the stored pointer.

Definition at line 313 of file htbl.c.

htbl_value_multi()

void * htbl_value_multi

(

const htbl_multi_value_t *

mv

)

Returns

The value contained in a multi-value element, which are the contents of the list_t returned from htbl_lookup_multi().

Example

htbl_t *my_hash_table = ...; // previously initialized hash table
 
list_t *values = htbl_lookup_multi(my_hash_table, my_key);
if (values != NULL) {
   // key found in hash table, walk the list of values
   for (htbl_multi_value_t *mv = list_head(values); mv != NULL;
       mv = list_next(values, mv)) {
       my_struct_t *value = htbl_value_multi(mv);
       // do something with `value'
   }
}

Definition at line 578 of file htbl.c.