Basic hash table for fast lookups. More...

#include "hashtable.h"
#include <assert.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include "common.h"
#include "mem.h"

Include dependency graph for hashtable.cpp:

Go to the source code of this file.

Data Structures
struct	hashItem_s
	The linked list item. More...
struct	hashBucket_s
	The hash bucket structure, contains a linked list of items. More...
struct	hashTable_s
	The hash table structure, contains an array of buckets being indexed by the hash function. More...

Macros
#define	HASH_TABLE_SIZE 256

Functions
static void *	_hash_alloc (memPool_t *pool, int n, size_t s)
static void	_hash_free (void *p)
static HASH_INDEX	default_hash (const void *key, int len)
	Default hash function to map keys into a 0..255 index.
static int	default_compare (const void key1, int len1, const void key2, int len2)
	Default compare function for comparing key values.
static hashItem_s *	_find_bucket_entry (hashBucket_s b, hashTable_compare c, const void key, int nkey, hashItem_s **prev)
	Internal function to scan the list of entries in the bucket for an exact match.
static void	_release_entry (hashItem_s **i, bool ownsKeys, bool ownsValues)
	Internal function, release an entry including key and value if owned.
static void	_release_bucket (hashBucket_s **b, bool ownsKeys, bool ownsValues)
	Internal function, releases bucket including entries.
static void	_release_table (hashTable_s **t, bool full)
	Internal function, releases entire table.
static hashItem_s *	_iterator_first (hashTable_s *t)
	start iterating with the first item.
static hashItem_s *	_iterator_next (hashTable_s t, hashItem_s i)
	iterate to next item
hashTable_s *	HASH_NewTable (bool ownsKeys, bool ownsValues, bool duplicateOverwrite)
	Creates a new hash table and sets it initial capacity.
hashTable_s *	HASH_NewTable (bool ownsKeys, bool ownsValues, bool duplicateOverwrite, hashTable_hash h, hashTable_compare c)
	Creates a new hash table and sets it initial capacity.
hashTable_s *	HASH_NewTable (bool ownsKeys, bool ownsValues, bool duplicateOverwrite, hashTable_hash h, hashTable_compare c, memPool_t keys, memPool_t values, memPool_t *table)
	Creates a new hash table and sets it initial capacity.
hashTable_s *	HASH_CloneTable (hashTable_s *source)
void	HASH_DeleteTable (hashTable_s **t)
	Deletes a hash table and sets the pointer to NULL.
bool	HASH_Insert (hashTable_s t, const void key, int nkey, const void *value, int nvalue)
	Inserts a new value with given key into the hash table.
void *	HASH_Remove (hashTable_s t, const void key, int nkey)
	Removes an existing value with given key from the hash table.
void	HASH_Clear (hashTable_s *t)
	Clears the hash table.
void *	HASH_Get (hashTable_s t, const void key, int nkey)
	Returns the value for a given key.
int	HASH_Count (hashTable_s *t)
	Returns the number of entries in the hash table.

Detailed Description

Basic hash table for fast lookups.

Definition in file hashtable.cpp.

Macro Definition Documentation

◆ HASH_TABLE_SIZE

#define HASH_TABLE_SIZE 256

Definition at line 60 of file hashtable.cpp.

Referenced by _iterator_first(), _iterator_next(), _release_table(), default_hash(), and HASH_Count().

Function Documentation

◆ _find_bucket_entry()

hashItem_s * _find_bucket_entry	(	hashBucket_s *	b,
		hashTable_compare	c,
		const void *	key,
		int	nkey,
		hashItem_s **	prev )

static

Internal function to scan the list of entries in the bucket for an exact match.

Parameters

[in]	b	The bucket to search in.
[in]	c	The compare function to use.
[in]	key	The key value to search for.
[in]	nkey	The lenght of the key value.
[out]	prev	A reference to a hashItem_s pointer for the entry preceding the found item. Set to NULL if the preceding entry is not needed.

Returns: If an exact match is found, a hashItem_s* to the entry, else NULL.

Note: The value of prev is set to NULL if there is no preceding item.

Definition at line 181 of file hashtable.cpp.

References i, key, and hashBucket_s::root.

Referenced by HASH_Get(), HASH_Insert(), and HASH_Remove().

◆ _hash_alloc()

void * _hash_alloc	(	memPool_t *	pool,
		int	n,
		size_t	s )

static

Definition at line 122 of file hashtable.cpp.

References Mem_Alloc, and Mem_PoolAlloc.

Referenced by HASH_Insert(), and HASH_NewTable().

◆ _hash_free()

void _hash_free ( void * p )

static

Definition at line 130 of file hashtable.cpp.

References Mem_Free.

Referenced by _release_bucket(), _release_entry(), and _release_table().

◆ _iterator_first()

hashItem_s * _iterator_first ( hashTable_s * t )

static

start iterating with the first item.

Note: the order is not necessarily sorted

Definition at line 244 of file hashtable.cpp.

References HASH_TABLE_SIZE, hashBucket_s::root, and hashTable_s::table.

Referenced by HASH_CloneTable().

◆ _iterator_next()

hashItem_s * _iterator_next	(	hashTable_s *	t,
		hashItem_s *	i )

static

iterate to next item

Note: the order is not necessarily sorted

Definition at line 257 of file hashtable.cpp.

References hashTable_s::hash, HASH_TABLE_SIZE, i, hashBucket_s::root, and hashTable_s::table.

Referenced by HASH_CloneTable().

◆ _release_bucket()

void _release_bucket	(	hashBucket_s **	b,
		bool	ownsKeys,
		bool	ownsValues )

static

Internal function, releases bucket including entries.

Definition at line 210 of file hashtable.cpp.

References _hash_free(), _release_entry(), and i.

Referenced by _release_table().

◆ _release_entry()

void _release_entry	(	hashItem_s **	i,
		bool	ownsKeys,
		bool	ownsValues )

static

Internal function, release an entry including key and value if owned.

Definition at line 200 of file hashtable.cpp.

References _hash_free(), and i.

Referenced by _release_bucket(), and HASH_Remove().

◆ _release_table()

void _release_table	(	hashTable_s **	t,
		bool	full )

static

Internal function, releases entire table.

Parameters

[out]	t	table pointer to release
[in]	full	If true, the tabel node is also freed.

Definition at line 229 of file hashtable.cpp.

References _hash_free(), _release_bucket(), HASH_TABLE_SIZE, and i.

Referenced by HASH_Clear(), and HASH_DeleteTable().

◆ default_compare()

int default_compare	(	const void *	key1,
		int	len1,
		const void *	key2,
		int	len2 )

static

Default compare function for comparing key values.

Parameters

[in]	key1	The first key value to compare.
[in]	len1	The length in bytes of the first key value.
[in]	key2	The second key value to compare.
[in]	len2	The length in bytes of the second key value.

Returns: A value of 0 if key1 == key2, -1 if key1 < key2 and +1 if key1 > key2.

Note: The default compare uses byte-by-byte comparison. If the key value is a basic data type, a custom compare function should be supplied.

Definition at line 165 of file hashtable.cpp.

Referenced by HASH_NewTable().

◆ default_hash()

HASH_INDEX default_hash	(	const void *	key,
		int	len )

static

Default hash function to map keys into a 0..255 index.

Parameters

[in]	key	A pointer to a key value.
[in]	len	The length of the key value.

Note: The algorithm is based on Fowler-Noll-Vo.

Definition at line 143 of file hashtable.cpp.

References HASH_TABLE_SIZE, i, key, and len.

Referenced by HASH_NewTable().

◆ HASH_Clear()

void HASH_Clear ( hashTable_s * t )

Clears the hash table.

Definition at line 460 of file hashtable.cpp.

References _release_table().

◆ HASH_CloneTable()

hashTable_s * HASH_CloneTable ( hashTable_s * source )

Definition at line 336 of file hashtable.cpp.

References _iterator_first(), _iterator_next(), hashTable_s::compare, hashTable_s::duplicateOverwrite, hashTable_s::hash, HASH_Insert(), HASH_NewTable(), hashItem_s::key, hashItem_s::nkey, hashItem_s::nvalue, hashTable_s::ownsKeys, hashTable_s::ownsValues, and hashItem_s::value.

Referenced by UI_CloneNode().

◆ HASH_Count()

int HASH_Count ( hashTable_s * t )

Returns the number of entries in the hash table.

Definition at line 481 of file hashtable.cpp.

References hashBucket_s::count, HASH_TABLE_SIZE, i, and hashTable_s::table.

◆ HASH_DeleteTable()

void HASH_DeleteTable ( hashTable_s ** t )

Deletes a hash table and sets the pointer to NULL.

Parameters

[in,out] t A reference to a hashTable_s pointer.

Definition at line 351 of file hashtable.cpp.

References _release_table().

Referenced by CL_ShutdownLua(), and uiNode::deleteNode().

◆ HASH_Get()

void * HASH_Get	(	hashTable_s *	t,
		const void *	key,
		int	nkey )

Returns the value for a given key.

Definition at line 467 of file hashtable.cpp.

References _find_bucket_entry(), hashTable_s::compare, hashTable_s::hash, i, key, and hashTable_s::table.

Referenced by CL_ExecuteCallback(), UI_GetBehaviourMethod(), and UI_GetNodeMethod().

◆ HASH_Insert()

bool HASH_Insert	(	hashTable_s *	t,
		const void *	key,
		int	nkey,
		const void *	value,
		int	nvalue )

Inserts a new value with given key into the hash table.

Parameters

[in]	t	A pointer to a hashTable_s structure.
[in]	key	A pointer to a key.
[in]	nkey	The length of the key value in bytes.
[in]	value	A pointer to a value.
[in]	nvalue	The length of the value in bytes.

Returns: True if the insert succeeds, false otherwise.

Note: If DEBUG then insert will assert when trying to insert a duplicate key value on a list created with duplicateOverwrite = false.; By default the hash table creates duplicates of the inserted key and values. Should this behaviour be modified, the user is responsible for making sure the pointers remain valid during the lifespan of the hash table.

Definition at line 369 of file hashtable.cpp.

References _find_bucket_entry(), _hash_alloc(), hashTable_s::compare, hashBucket_s::count, hashTable_s::duplicateOverwrite, hashTable_s::hash, i, hashTable_s::internalPool, key, hashTable_s::keyPool, hashTable_s::ownsKeys, hashTable_s::ownsValues, hashBucket_s::root, hashTable_s::table, and hashTable_s::valuePool.

Referenced by CL_RegisterCallback(), HASH_CloneTable(), UI_AddBehaviourMethod(), and UI_AddNodeMethod().

◆ HASH_NewTable() [1/3]

hashTable_s * HASH_NewTable	(	bool	ownsKeys,
		bool	ownsValues,
		bool	duplicateOverwrite )

Creates a new hash table and sets it initial capacity.

Parameters

[in]	ownsKeys	If true, the hash table stores a copy of the key.
[in]	ownsValues	If true, the hash table stores a copy of the value.
[in]	duplicateOverwrite	If true, inserting a value twice will overwrite the old value. If false, the operation asserts.

Returns: A pointer to a hashTable_s.

Note: The table hash an initial index of HASH_TABLE_SIZE buckets.; The hash table will use the default hash function and default compare function.

Definition at line 287 of file hashtable.cpp.

References default_compare(), default_hash(), and HASH_NewTable().

Referenced by CL_InitLua(), HASH_CloneTable(), HASH_NewTable(), HASH_NewTable(), UI_AddBehaviourMethod(), and UI_AddNodeMethod().

◆ HASH_NewTable() [2/3]

hashTable_s * HASH_NewTable	(	bool	ownsKeys,
		bool	ownsValues,
		bool	duplicateOverwrite,
		hashTable_hash	h,
		hashTable_compare	c )

Creates a new hash table and sets it initial capacity.

Parameters

[in]	ownsKeys	If true, the hash table stores a copy of the key.
[in]	ownsValues	If true, the hash table stores a copy of the value.
[in]	duplicateOverwrite	If true, inserting a value twice will overwrite the old value. If false, the operation asserts.
[in]	h	The hash function to be used when indexing.
[in]	c	The compare function to be used when comparing.

Returns: A pointer to a hashTable_s.

Note: The table hash an initial index of HASH_TABLE_SIZE buckets.

Definition at line 303 of file hashtable.cpp.

References HASH_NewTable().

◆ HASH_NewTable() [3/3]

hashTable_s * HASH_NewTable	(	bool	ownsKeys,
		bool	ownsValues,
		bool	duplicateOverwrite,
		hashTable_hash	h,
		hashTable_compare	c,
		memPool_t *	keys,
		memPool_t *	values,
		memPool_t *	table )

Creates a new hash table and sets it initial capacity.

Parameters

[in]	ownsKeys	If true, the hash table stores a copy of the key.
[in]	ownsValues	If true, the hash table stores a copy of the value.
[in]	duplicateOverwrite	If true, inserting a value twice will overwrite the old value. If false, the operation asserts.
[in]	h	The hash function to be used when indexing.
[in]	c	The compare function to be used when comparing.
[in]	keys	If not null, should point to a memory pool used to allocate key values.
[in]	values	If not null, should point to a memory pool used to allocated copies of inserted values.
[in]	table	If not null, should point to a memory pool used to allocate the table internal structures, including the hashTable_s structure returned.

Returns: A pointer to a hashTable_s.

Note: The table hash an initial index of HASH_TABLE_SIZE buckets.

Definition at line 322 of file hashtable.cpp.

References _hash_alloc(), hashTable_s::compare, hashTable_s::duplicateOverwrite, hashTable_s::hash, hashTable_s::internalPool, hashTable_s::keyPool, hashTable_s::ownsKeys, hashTable_s::ownsValues, and hashTable_s::valuePool.

◆ HASH_Remove()

void * HASH_Remove	(	hashTable_s *	t,
		const void *	key,
		int	nkey )

Removes an existing value with given key from the hash table.

Returns: If the hash table does not own the data, returns the value pointer stored, otherwise returns NULL.

Definition at line 429 of file hashtable.cpp.

References _find_bucket_entry(), _release_entry(), hashTable_s::compare, hashBucket_s::count, hashTable_s::hash, i, key, hashItem_s::next, hashTable_s::ownsKeys, hashTable_s::ownsValues, hashBucket_s::root, hashTable_s::table, and v.

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ HASH_TABLE_SIZE

Function Documentation

◆ _find_bucket_entry()

◆ _hash_alloc()

◆ _hash_free()

◆ _iterator_first()

◆ _iterator_next()

◆ _release_bucket()

◆ _release_entry()

◆ _release_table()

◆ default_compare()

◆ default_hash()

◆ HASH_Clear()

◆ HASH_CloneTable()

◆ HASH_Count()

◆ HASH_DeleteTable()

◆ HASH_Get()

◆ HASH_Insert()

◆ HASH_NewTable() [1/3]

◆ HASH_NewTable() [2/3]

◆ HASH_NewTable() [3/3]

◆ HASH_Remove()