htable.h File Reference

Datatypes and functions for hashtables. More...

#include "../basics.h"

Go to the source code of this file.

Typedefs
typedef struct _jw_htable	jw_htable
typedef struct _jw_hnode	jw_hnode
typedef unsigned int(*	jw_htable_hashfunc) (const void *key)
typedef int(*	jw_htable_cmpfunc) (const void *key1, const void *key2)
typedef int(*	jw_htable_walkfunc) (void *user_data, const void *key, void *data)
typedef void(*	jw_htable_cleanfunc) (bool replace, bool destroy_key, void *key, void *data)

Functions
JABBERWERX_API const void *	jw_hnode_get_key (jw_hnode *node)
JABBERWERX_API void *	jw_hnode_get_value (jw_hnode *node)
JABBERWERX_API void	jw_hnode_put_value (jw_hnode *node, void *data, jw_htable_cleanfunc cleaner)
JABBERWERX_API bool	jw_htable_create (int buckets, jw_htable_hashfunc hash, jw_htable_cmpfunc cmp, jw_htable **tbl, jw_err *err)
JABBERWERX_API void	jw_htable_destroy (jw_htable *tbl)
JABBERWERX_API unsigned int	jw_htable_get_count (jw_htable *tbl)
JABBERWERX_API jw_hnode *	jw_htable_get_node (jw_htable *tbl, const void *key)
JABBERWERX_API void	jw_htable_remove_node (jw_htable *tbl, jw_hnode *node)
JABBERWERX_API void *	jw_htable_get (jw_htable *tbl, const void *key)
JABBERWERX_API bool	jw_htable_put (jw_htable *tbl, const void *key, void *value, jw_htable_cleanfunc cleaner, jw_err *err)
JABBERWERX_API void	jw_htable_remove (jw_htable *tbl, const void *key)
JABBERWERX_API void	jw_htable_clear (jw_htable *tbl)
JABBERWERX_API jw_hnode *	jw_htable_get_first_node (jw_htable *tbl)
JABBERWERX_API jw_hnode *	jw_htable_get_next_node (jw_htable *tbl, jw_hnode *cur)
JABBERWERX_API unsigned int	jw_htable_walk (jw_htable *tbl, jw_htable_walkfunc func, void *user_data)
JABBERWERX_API unsigned int	jw_str_hashcode (const void *key)
JABBERWERX_API unsigned int	jw_strcase_hashcode (const void *key)
JABBERWERX_API unsigned int	jw_int_hashcode (const void *key)
JABBERWERX_API int	jw_int_compare (const void *key1, const void *key2)
JABBERWERX_API void	jw_htable_free_data_cleaner (bool replace, bool destroy_key, void *key, void *data)

Variables
JABBERWERX_API jw_htable_cmpfunc	jw_str_compare
JABBERWERX_API jw_htable_cmpfunc	jw_strcase_compare

Detailed Description

Datatypes and functions for hashtables.

NOTE: Instances of jw_htable do not take ownership of keys and values. Users MUST ensure any memory allocated for keys and values is released when they are no longer in use.

NOTE: This API is not thread-safe. Users MUST ensure access to all instances of a hashtable is limited to a single thread.

Copyrights

Portions created or assigned to Cisco Systems, Inc. are Copyright (c) 2010-2015 Cisco Systems, Inc. All Rights Reserved. See LICENSE for details.

Typedef Documentation

typedef struct _jw_hnode jw_hnode

A node in the hashtable

typedef struct _jw_htable jw_htable

An instance of a hashtable

typedef void(* jw_htable_cleanfunc) (bool replace, bool destroy_key, void *key, void *data)

Function pointer for cleaning up a hashtable entry.

Parameters

replace	If true, the data for the given key is being replaced, not added.
destroy_key	If true, any non-static data in the key should be destroyed. destroy_key will always be true if replace is false. destroy_key will be false if the new key has pointer equality with the old key.
key	The old key being cleaned.
data	The old data being cleaned. This is usually freed in the called function.

typedef int(* jw_htable_cmpfunc) (const void *key1, const void *key2)

Pointer to a function for comparing keys.

Parameters

key1	The first key to compare
key2	The second key to compare

Return values

int	less than 0 if key1 is before key2, greater than 0 if key1 is after key2, 0 if key1 and key2 are equal

See also

jw_int_compare

typedef unsigned int(* jw_htable_hashfunc) (const void *key)

Pointer to a function for generating hashcodes.

Parameters

key	The key to generate a hashcode for

Return values

int	The hashcode for key

See also

jw_int_hashcode

jw_str_hashcode

jw_strcase_hashcode

typedef int(* jw_htable_walkfunc) (void *user_data, const void *key, void *data)

Function pointer for walking all the elements in a hashtable

Parameters

user_data	Optional data provided
key	The current key being visited
data	The current data being visited

Return values

int	0 to stop walking the hashtable's elements, or 1 to continue.

Function Documentation

JABBERWERX_API const void* jw_hnode_get_key

(

jw_hnode *

node

)

Retrieves the key for the given hashtable node

Invariant

node != NULL

Parameters

node	The node to retrieve the key of

Return values

void	*The key of node

JABBERWERX_API void* jw_hnode_get_value

(

jw_hnode *

node

)

Retrieves the value for the given hashtable node

Invariant

node != NULL

Parameters

node	The node to retrieve the value of

Return values

void	*The value of node

JABBERWERX_API void jw_hnode_put_value	(	jw_hnode *	node,
		void *	data,
		jw_htable_cleanfunc	cleaner
	)

Changes the value of the given hashtable node

Invariant

node != NULL

Parameters

[in]	node	The node to change the value of
[in]	data	The new value
[in]	cleaner	Function to call when data is replaced or deleted (provide NULL to ignore)

JABBERWERX_API void jw_htable_clear

(

jw_htable *

tbl

)

Frees all elements in a hashtable, calling the cleaner function for each item to free it.

Invariant

tbl != NULL

Parameters

tbl	Hash table to clear out.

JABBERWERX_API bool jw_htable_create	(	int	buckets,
		jw_htable_hashfunc	hash,
		jw_htable_cmpfunc	cmp,
		jw_htable **	tbl,
		jw_err *	err
	)

Creates a new hashtable.

This function can generate the following errors (set when returning false):

• JW_ERR_NO_MEMORY if the hashtable could not be allocated

Invariant

hash != NULL

cmp != NULL

tbl != NULL

Parameters

[in]	buckets	Number of buckets to allocate for the hash table; this value should be a prime number for maximum efficiency. If this value is 0, a default will be used.
[in]	hash	The key hashcode function to use.
[in]	cmp	The key comparison function to use.
[out]	tbl	The pointer to hold the initialized hashtable
[out]	err	The error information (provide NULL to ignore)

Return values

bool	true if successful, false otherwise.

JABBERWERX_API void jw_htable_destroy

(

jw_htable *

tbl

)

Destroys a hashtable.

NOTE: This function WILL clean up memory allocated for the actual keys and values by calling the cleaner function supplied when the values were inserted with jw_htable_put. It is no longer necessary to call jw_htable_clear first.

Invariant

tbl != NULL

Parameters

tbl	Hashtable to be destroyed.

JABBERWERX_API void jw_htable_free_data_cleaner	(	bool	replace,
		bool	destroy_key,
		void *	key,
		void *	data
	)

Calls jw_data_free only on the data associated with a node. Use this when the keys are always static strings, and jw_data_free(data) is correct.

Parameters

replace	Ignored
destroy_key	Ignored
key	Ignored
data	The data that will be freed with jw_data_free.

JABBERWERX_API void* jw_htable_get	(	jw_htable *	tbl,
		const void *	key
	)

Retrieves a value stored in the hashtable.

Invariant

tbl != NULL

Parameters

tbl	the hashtable to look in.
key	the key value to search on.

Return values

void	* Value corresponding to the specified key, NULL if not found.

JABBERWERX_API unsigned int jw_htable_get_count

(

jw_htable *

tbl

)

Returns the number of elements stored in the given hashtable

Invariant

tbl != NULL

Parameters

tbl	The hashtable

Return values

unsigned

int The number of elements in tbl

JABBERWERX_API jw_hnode* jw_htable_get_first_node

(

jw_htable *

tbl

)

Returns the first element in the hashtable.

Invariant

tbl != NULL

Parameters

tbl	the hashtable to look in

Return values

jw_hnode

the first node in the hashtable or NULL if there isn't one.

JABBERWERX_API jw_hnode* jw_htable_get_next_node	(	jw_htable *	tbl,
		jw_hnode *	cur
	)

Returns the next node in the hashtable

Invariant

tbl != NULL

Parameters

tbl	the hashtable to look in
cur	the current node

Return values

jw_hnode

a pointer to the next node or NULL if there isn't one.

JABBERWERX_API jw_hnode* jw_htable_get_node	(	jw_htable *	tbl,
		const void *	key
	)

Retrieves the node stored in the hashtable.

Invariant

tbl != NULL

Parameters

tbl	the hashtable to look in.
key	the key value to search on.

Return values

jw_hnode

the node corresponding to the specified key, or NULL if not found.

JABBERWERX_API bool jw_htable_put	(	jw_htable *	tbl,
		const void *	key,
		void *	value,
		jw_htable_cleanfunc	cleaner,
		jw_err *	err
	)

Associates a key with a value in this hashtable. If there is already a value for this key, it is replaced, and the previous cleaner function (if any) is called for the previous value. If required for the new value, a new cleaner function should be provided even when replacing.

This function can generate the following errors (set when returning false):

• JW_ERR_NO_MEMORY if the hashtable could not be allocated

Invariant

tbl != NULL

Parameters

[in]	tbl	Hashtable to add/update.
[in]	key	Key to use for the value in the table.
[in]	value	Value to add for this key.
[in]	cleaner	Function to call when the item is deleted or replaced. (provide NULL to ignore)
[out]	err	The error information (provide NULL to ignore)

Return values

bool	if successful; false otherwise.

JABBERWERX_API void jw_htable_remove	(	jw_htable *	tbl,
		const void *	key
	)

Removes an entry from a hashtable, given its key. Note, the cleaner function will be called.

Invariant

tbl != NULL

Parameters

tbl	Hashtable to remove from.
key	Key of value to remove.

JABBERWERX_API void jw_htable_remove_node	(	jw_htable *	tbl,
		jw_hnode *	node
	)

Removes the node from the hashtable, calling whatever cleaner function is registered.

Invariant

tbl != NULL

node != NULL

Parameters

tbl	The table to remove from
node	The node to remove

JABBERWERX_API unsigned int jw_htable_walk	(	jw_htable *	tbl,
		jw_htable_walkfunc	func,
		void *	user_data
	)

Iterates through a hashtable, calling a callback function for each element stored in it.

Parameters

tbl	Hashtable to walk.
func	Function to be called for each node.
user_data	Value to use as the first parameter for the callback function.

Returns

int Number of nodes visited up to and including the one for which the callback function returned 0, if it did

JABBERWERX_API int jw_int_compare	(	const void *	key1,
		const void *	key2
	)

Compares two integers for relative positioning.

Parameters

key1	The first integer to compare
key2	The second integer to compare

Return values

int	less than 0 if i1 is before i2; greater than 0 if i1 is after i2; 0 if i1 and i2 are equal

JABBERWERX_API unsigned int jw_int_hashcode

(

const void *

key

)

Generates hashcodes for integers.

Parameters

key	The integer to hash

Return values

unsigned

int The hashcode for i

JABBERWERX_API unsigned int jw_str_hashcode

(

const void *

key

)

Generates hashcodes for strings (case-sensitive).

Parameters

key	The NULL-terminated string to hash

Return values

unsigned

int The hashcode for s

JABBERWERX_API unsigned int jw_strcase_hashcode

(

const void *

key

)

Generates hashcodes for strings (case-insensitive).

Parameters

key	The NULL-terminated string to hash

Return values

unsigned

int The hashcode for s

Variable Documentation

JABBERWERX_API jw_htable_cmpfunc jw_str_compare

Compares string keys (case-sensitive). This is a casting of strcmp to overcome warnings about incompatible pointer types, and to provide a compliment to jw_str_hashcode().

Parameters

key1	The first NULL-terminated key to compare
key2	The second NULL-terminated key to compare

Return values

int	less than 0 if key1 is before key2; greater than 0 if key1 is after key2; 0 if key1 is equal to key2

JABBERWERX_API jw_htable_cmpfunc jw_strcase_compare

Compares string keys (case-insensitive). This is a casting of strcasecmp to overcome warnings about incompatible pointer types, and to provide a compliment to jw_strcase_hashcode().

Parameters

key1	The first NULL-terminated key to compare
key2	The second NULL-terminated key to compare

Return values

int	less than 0 if key1 is before key2; greater than 0 if key1 is after key2; 0 if key1 is equal to key2