hashMap.c File Reference

Data Structures
struct	hashNode_t
	A single key-value pair in the hash map. More...
struct	hashBucket
	A single element of the hash map array, holding either one value or a list of values. More...
struct	hashIterState
	The internal state of a hash map iterator. More...
union	hashBucket.__unnamed25__

Macros
#define	HASH_LOG(...)

Typedefs
typedef struct hashBucket	hashBucket_t
	A single element of the hash map array, holding either one value or a list of values.
typedef struct hashIterState	hashIterState_t
	The internal state of a hash map iterator.

Functions
uint32_t	hashString (const void *str)
	Convert a NULL-terminated string to a hash value.
bool	strEq (const void *a, const void *b)
	Compare two NUL-terminated strings.
uint32_t	hashBytes (const uint8_t *bytes, size_t length)
	Convert an arbitrary byte sequence to a hash value.
bool	bytesEq (const uint8_t *a, size_t aLength, const uint8_t *b, size_t bLength)
	Compare two byte arrays.
uint32_t	hashInt (const void *intKey)
	Convert a pointer address or integral value to a hash value.
bool	intsEq (const void *keyA, const void *keyB)
	Compare two void pointers based on their address, or two integer types cast to a void pointer.
void	hashPut (hashMap_t *map, const char *key, void *value)
	Create or update a key-value pair in the hash map with a string key.
void *	hashGet (hashMap_t *map, const char *key)
	Return the value in the hash map associated with the given string key.
void *	hashRemove (hashMap_t *map, const char *key)
	Remove the value with a given string key from the hash map.
void	hashPutBin (hashMap_t *map, const void *key, void *value)
	Create or update a key-value pair in the hash map with a non-string key.
void *	hashGetBin (hashMap_t *map, const void *key)
	Return the value in the hash map associated with the given key.
void *	hashRemoveBin (hashMap_t *map, const void *key)
	Remove the value with a given non-string key from the hash map.
void	hashInit (hashMap_t *map, int initialSize)
	Initialize a hash map for string keys.
void	hashInitBin (hashMap_t *map, int initialSize, hashFunction_t hashFunc, eqFunction_t eqFunc)
	Initialize a hash map for non-string keys, using the given functions for hashing and comparison.
void	hashDeinit (hashMap_t *map)
	Deinitialize and free all memory associated with the given hash map.
bool	hashIterate (const hashMap_t *map, hashIterator_t *iterator)
	Advance the given iterator to the next item, or return false if there is no next item.
bool	hashIterRemove (hashMap_t *map, hashIterator_t *iter)
	Remove the last item returned by the iterator from the hash map.
void	hashIterReset (hashIterator_t *iterator)
	Reset the given iterator struct, freeing any memory associated with it.
void	hashReport (const hashMap_t *map)
	Prints out a detailed report on the hash map state.

---

Data Structure Documentation

hashNode_t

struct hashNode_t

Data Fields
uint32_t	hash	< The key's hash value The key of this pair, or NULL if this node is empty
const void *	key	The value of this pair.
void *	value

hashBucket

struct hashBucket

Data Fields
bool	hasMulti	< Whether the bucket contains multiple or a single item
union hashBucket.__unnamed25__	__unnamed__

hashIterState

struct hashIterState

Data Fields
hashBucket_t *	curBucket	< The bucket containing the current item The list node containing the current item, if within a multi bucket
node_t *	curListNode	The node containing the current item.
hashNode_t *	curNode	The number of items returned by the iterator.
int	returned	Whether the iterator has already been advanced, after removing the previous item.
bool	removed

hashBucket.__unnamed25__

union hashBucket.__unnamed25__

Data Fields
hashNode_t	single	< The node's single-item contents, when hasMulti is false The node's multi-item contents, when hasMulti is true
list_t	multi

Macro Definition Documentation

HASH_LOG

#define HASH_LOG

(

...

)

Typedef Documentation

hashBucket_t

typedef struct hashBucket hashBucket_t

A single element of the hash map array, holding either one value or a list of values.

While holding a single value, the item's key, hash, and value are held directly in the struct. While holding multiple values, each item is stored as a value in a linked list, heap-allocated.

hashIterState_t

typedef struct hashIterState hashIterState_t

The internal state of a hash map iterator.

Function Documentation

hashString()

uint32_t hashString

(

const void *

str

)

Convert a NULL-terminated string to a hash value.

Uses the 'djb2' algorithm, described at http://www.cse.yorku.ca/~oz/hash.html

Parameters

str	The string to hash

Returns

uint32_t The hash value

strEq()

bool strEq	(	const void *	a,
		const void *	b )

Compare two NUL-terminated strings.

Parameters

a	The first string to compare
b	The second string to compare

Returns

true when the two strings are equal or the same pointer

false when the two strings differ

hashBytes()

uint32_t hashBytes	(	const uint8_t *	bytes,
		size_t	length )

Convert an arbitrary byte sequence to a hash value.

Uses the 'djb2' algorithm, described at http://www.cse.yorku.ca/~oz/hash.html

Parameters

bytes	A pointer to a byte array to hash
length	The length of the byte array

Returns

uint32_t The hash value

bytesEq()

bool bytesEq	(	const uint8_t *	a,
		size_t	aLength,
		const uint8_t *	b,
		size_t	bLength )

Compare two byte arrays.

Parameters

a	A pointer to the first byte array
aLength	The length of the first byte array
b	A pointer to the second byte array
bLength	The length of the second byte array

Returns

true when the byte arrays are equal or the same pointer

false when the byte arrays differ

hashInt()

uint32_t hashInt

(

const void *

intKey

)

Convert a pointer address or integral value to a hash value.

The pointer is not dereferenced.

Parameters

intKey

A void pointer whose address will be hashed, or any integral type cast to a void pointer

Returns

uint32_t The hash value

intsEq()

bool intsEq	(	const void *	keyA,
		const void *	keyB )

Compare two void pointers based on their address, or two integer types cast to a void pointer.

The pointers are not dereferenced.

Parameters

keyA	The first pointer value
keyB	The second pointer value

Returns

true If both pointers are the same value

false If the pointers are differ

hashPut()

void hashPut	(	hashMap_t *	map,
		const char *	key,
		void *	value )

Create or update a key-value pair in the hash map with a string key.

Warning

A reference to the key will be stored in the map until the entry is removed

Parameters

map	The hash map to update
key	The string key to associate the value with
value	The value to add to the map

hashGet()

void * hashGet	(	hashMap_t *	map,
		const char *	key )

Return the value in the hash map associated with the given string key.

Parameters

map	The hash map to search
key	The string key to retrieve the value for

Returns

void* A pointer to the mapped value, or NULL if it was not found

hashRemove()

void * hashRemove	(	hashMap_t *	map,
		const char *	key )

Remove the value with a given string key from the hash map.

Parameters

map	The hash map to remove from
key	The string key to remove the value for

Returns

void* The item that was removed, or NULL if no item was found for the given key

hashPutBin()

void hashPutBin	(	hashMap_t *	map,
		const void *	key,
		void *	value )

Create or update a key-value pair in the hash map with a non-string key.

Parameters

map	The hash map to update
key	The key to associate the value with
value	The value to add to the map

hashGetBin()

void * hashGetBin	(	hashMap_t *	map,
		const void *	key )

Return the value in the hash map associated with the given key.

Parameters

map	The hash map to search
key	The key to retrieve the value for

Returns

void* A pointer to the mapped value, or NULL if it was not found

hashRemoveBin()

void * hashRemoveBin	(	hashMap_t *	map,
		const void *	key )

Remove the value with a given non-string key from the hash map.

Parameters

map	The hash map to remove from
key	The non-string key to remove the value for

Returns

void* The item that was removed, or NULL if no item was found for the given key

hashInit()

void hashInit	(	hashMap_t *	map,
		int	initialSize )

Initialize a hash map for string keys.

Parameters

map	A pointer to a hashMap_t struct to be initialized
initialSize	The initial size of the hash map

hashInitBin()

void hashInitBin	(	hashMap_t *	map,
		int	initialSize,
		hashFunction_t	hashFunc,
		eqFunction_t	eqFunc )

Initialize a hash map for non-string keys, using the given functions for hashing and comparison.

Parameters

map	A pointer to a hashMap_t struct to be initialized
initialSize	The initial size of the hash map
hashFunc	The hash function to use for the key datatype
eqFunc	The comparison function to use for the key datatype

hashDeinit()

void hashDeinit

(

hashMap_t *

map

)

Deinitialize and free all memory associated with the given hash map.

Parameters

map	The map to deinitialize

hashIterate()

bool hashIterate	(	const hashMap_t *	map,
		hashIterator_t *	iterator )

Advance the given iterator to the next item, or return false if there is no next item.

The iterator should point to a zero-initialized struct at the start of iteration. Once iteration completes and this function returns false, iterator will be reset. If iteration is stopped before this function returns false, the iterator must be reset with hashIterReset() to prevent memory leaks.

Items in the hash map are not returned in any particular order.

It is possible to remove items during iteration, but this must be done with hashIterRemove(). Using hashRemove() or hashRemoveBin() during iteration is not allowed and will cause undefined behavior.

Adding or udpating items during iteration is permitted, with the caveat that a new item inserted during iteration may or may not later be returned by the iterator.

Parameters

[in]	map	The map to iterate over
[in,out]	iterator	A pointer to a hashIterator_t struct

Returns

true if the iterator returned an item

false if iteration is complete and no item was returned

hashIterRemove()

bool hashIterRemove	(	hashMap_t *	map,
		hashIterator_t *	iter )

Remove the last item returned by the iterator from the hash map.

This function does not need to search and so it always runs in constant time.

If you want to remove an item from the hash map while iterating over it, this function is the only safe way to do it.

Warning

If this function returns false, iteration is complete.

Parameters

map	The hash map to remove the item from
iter	The iterator whose current item to remove from the hash map

Returns

true if there are still items remaining in the iterator

false if there are no more items remaining in the iterator

hashIterReset()

void hashIterReset

(

hashIterator_t *

iterator

)

Reset the given iterator struct, freeing any memory associated with it.

Parameters

iterator

A pointer to the iterator struct to be reset

hashReport()

void hashReport

(

const hashMap_t *

map

)

Prints out a detailed report on the hash map state.

This can be useful when testing to determine the effectiveness of a hash function.

Parameters

map	The hash map to print the state of