vl_hashtable.h File Reference

#include "vl_arena.h"
#include "vl_hash.h"

Include dependency graph for vl_hashtable.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	vl_hashtable
	A dynamically-sized hash table. More...

Macros
#define	VL_HASHTABLE_ITER_INVALID   0
#define	VL_HASHTABLE_RESIZE_FACTOR   0.8
#define	VL_HASHTABLE_DEFAULT_SIZE   128
#define	VL_HASHTABLE_FOREACH(table, trackVar)   for(vl_hash_iter trackVar = vlHashTableFront(table); trackVar != VL_HASHTABLE_ITER_INVALID; trackVar = vlHashTableNext(table, trackVar))

Typedefs
typedef vl_arena_ptr	vl_hash_iter

Functions
void	vlHashTableInit (vl_hashtable *table, vl_hash_function hashFunc)
	Initializes the specified table. Specifies the hash function to use on keys.
void	vlHashTableFree (vl_hashtable *table)
	Frees the specified table.
vl_hashtable *	vlHashTableNew (vl_hash_function func)
	Allocates on the heap, initializes, and returns a new hash table. Specifies the hash function to use on keys.
void	vlHashTableDelete (vl_hashtable *table)
vl_hash_iter	vlHashTableInsert (vl_hashtable *table, const void *key, vl_memsize_t keySize, vl_memsize_t dataSize)
	Claims a chunk of memory associated with the specified key. If the key already exists, the associated chunk is reallocated to match the specified size.
void	vlHashTableRemoveKey (vl_hashtable *table, const void *key, vl_memsize_t keyLen)
void	vlHashTableRemoveIter (vl_hashtable *table, vl_hash_iter iter)
void	vlHashTableClear (vl_hashtable *table)
	Clears the specified hash table so it can be used as if it was just created.
vl_hashtable *	vlHashTableClone (const vl_hashtable *table, vl_hashtable *dest)
	Clones the specified hashtable to another.
vl_hash_iter	vlHashTableCopyElement (vl_hashtable *src, vl_hash_iter iter, vl_hashtable *dest)
	Copies a single element of a hashtable from one table to another.
int	vlHashTableCopy (vl_hashtable *src, vl_hashtable *dest)
	Copies the entirety of one hashtable to another.
void	vlHashTableReserve (vl_hashtable *table, vl_memsize_t buckets, vl_memsize_t heapSize)
	Reserves memory in the hashtable before requiring it.
vl_hash_iter	vlHashTableFind (vl_hashtable *table, const void *key, vl_memsize_t keySize)
const vl_transient *	vlHashTableSampleKey (vl_hashtable *table, vl_hash_iter iter, vl_memsize_t *size)
vl_transient *	vlHashTableSampleValue (vl_hashtable *table, vl_hash_iter iter, vl_memsize_t *size)
vl_hash_iter	vlHashTableFront (vl_hashtable *table)
vl_hash_iter	vlHashTableNext (vl_hashtable *table, vl_hash_iter iter)

---

Data Structure Documentation

vl_hashtable

struct vl_hashtable

A dynamically-sized hash table.

The vl_hashtable structure represents a HashTable/Hashmap/Unordered map. It is implemented on top of a vl_arena, which holds the underlying node data. A vl_memory* allocation is used to hold mappings between hash nodes and their respective vl_arena_ptr values into the virtual arena allocator.

This hashtable resolves collisions through separate chaining.

The structure retains a counter that represents the total number of elements it contains. Should the total number of elements become larger or equal to the size of the table * VL_HASHTABLE_RESIZE_FACTOR, the table grows in size by doubling its capacity. The table and collision chains will then be rebuilt according to this new size with a complexity of O(n).

This table does not waste time by iterating over empty space.

See also

vl_arena

Collaboration diagram for vl_hashtable:

Data Fields
vl_arena	data
vl_hash_function	hashFunc
vl_memory *	table
vl_dsidx_t	totalElements

Macro Definition Documentation

VL_HASHTABLE_DEFAULT_SIZE

#define VL_HASHTABLE_DEFAULT_SIZE   128

VL_HASHTABLE_FOREACH

#define VL_HASHTABLE_FOREACH	(		table,
			trackVar )   for(vl_hash_iter trackVar = vlHashTableFront(table); trackVar != VL_HASHTABLE_ITER_INVALID; trackVar = vlHashTableNext(table, trackVar))

This is a convenience macro for iterating over the entirety of a hashtable.

Parameters

table	table pointer
trackVar	name of the variable used as the iterator.

VL_HASHTABLE_ITER_INVALID

#define VL_HASHTABLE_ITER_INVALID   0

VL_HASHTABLE_RESIZE_FACTOR

#define VL_HASHTABLE_RESIZE_FACTOR   0.8

Typedef Documentation

vl_hash_iter

typedef vl_arena_ptr vl_hash_iter

Function Documentation

vlHashTableClear()

void vlHashTableClear

(

vl_hashtable *

table

)

Clears the specified hash table so it can be used as if it was just created.

No data in the underlying virtual arena allocator is touched. Rather, book-keeping variables are reset to their initial state.

Parameters

table

pointer

Complexity of O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableClone()

vl_hashtable * vlHashTableClone	(	const vl_hashtable *	table,
		vl_hashtable *	dest )

Clones the specified hashtable to another.

Clones the entirety of the src table to the dest table.

The 'src' table must be non-null and initialized. The 'dest' table may be null, but if it is not null it must be initialized.

If the 'dest' table pointer is null, a new list is created via vlHashTableNew.

See also

vlHashTableNew

Parameters

src	pointer
dest	pointer

Returns

pointer to table that was copied to or created.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableCopy()

int vlHashTableCopy	(	vl_hashtable *	src,
		vl_hashtable *	dest )

Copies the entirety of one hashtable to another.

Both tables must have the same hash function, otherwise this is a no-op. If any elements with matching keys exist between the two maps, they are overwritten by the contents of the element in the source table.

Parameters

src	pointer
dest	pointer

Returns

total number of elements copied

Here is the call graph for this function:

vlHashTableCopyElement()

vl_hash_iter vlHashTableCopyElement	(	vl_hashtable *	src,
		vl_hash_iter	iter,
		vl_hashtable *	dest )

Copies a single element of a hashtable from one table to another.

Both tables must have the same hash function, otherwise this is a no-op and will return VL_HASHTABLE_ITER_INVALID.

If an element by the key specified by the iterator already exists in the dest table, its element data is overwritten by the contents of the element in the source table.

Parameters

src	pointer
iter	element to copy
dest	pointer

Returns

iterator to element inserted into dest table, or VL_HASHTABLE_ITER_INVALID.

Here is the call graph for this function:

vlHashTableDelete()

void vlHashTableDelete

(

vl_hashtable *

table

)

Deallocates and deinitializes the specified table. The table MUST be initialized via vlHashTableNew.

See also

vlHashTableNew

Parameters

table

pointer

Complexity O(1) constant.

Here is the call graph for this function:

vlHashTableFind()

vl_hash_iter vlHashTableFind	(	vl_hashtable *	table,
		const void *	key,
		vl_memsize_t	keySize )

Searches the hashtable for an element with the specified key.

Parameters

table	pointer
key
keySize

Complexity of O(1) constant.

Returns

found element, or VL_HASHTABLE_ITER_INVALID on failure.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableFree()

void vlHashTableFree

(

vl_hashtable *

table

)

Frees the specified table.

The table instance should have been initialized via vlHashTableInit.

See also

vlHashTableInit

Parameters

table

pointer

Complexity O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableFront()

vl_hash_iter vlHashTableFront

(

vl_hashtable *

table

)

Returns the "first" iterator for the specified table.

Parameters

table

pointer

Complexity of O(1) constant.

Returns

iterator to some "first" element, or VL_HASHTABLE_ITER_INVALID if none exists.

Here is the call graph for this function:

vlHashTableInit()

void vlHashTableInit	(	vl_hashtable *	table,
		vl_hash_function	hashFunc )

Initializes the specified table. Specifies the hash function to use on keys.

The table instance should be freed via vlHashTableFree.

See also

vlHashTableFree

Parameters

table	pointer
hashFunc	hash function pointer

Complexity O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableInsert()

vl_hash_iter vlHashTableInsert	(	vl_hashtable *	table,
		const void *	key,
		vl_memsize_t	keySize,
		vl_memsize_t	dataSize )

Claims a chunk of memory associated with the specified key. If the key already exists, the associated chunk is reallocated to match the specified size.

Parameters

table	pointer
key	pointer to key data
keySize	size of key data, in bytes
dataSize	size of element data, in bytes

Complexity O(1) constant.

Returns

iterator to inserted element.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableNew()

vl_hashtable * vlHashTableNew

(

vl_hash_function

func

)

Allocates on the heap, initializes, and returns a new hash table. Specifies the hash function to use on keys.

The created hashtable instance should be deleted via vlHashTableDelete.

See also

vlHashTableDelete

Parameters

func

Complexity O(1) constant.

Returns

hashtable pointer.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableNext()

vl_hash_iter vlHashTableNext	(	vl_hashtable *	table,
		vl_hash_iter	iter )

Returns the "next" iterator relative to the specified iterator.

Parameters

table	pointer
iter

Complexity of O(1) constant.

Returns

iterator to some "next" element, or VL_HASHTABLE_ITER_INVALID if none exists.

Here is the call graph for this function:

vlHashTableRemoveIter()

void vlHashTableRemoveIter	(	vl_hashtable *	table,
		vl_hash_iter	iter )

Removes the hash element represented by the specified iterator.

Parameters

table	pointer
iter

Complexity of O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableRemoveKey()

void vlHashTableRemoveKey	(	vl_hashtable *	table,
		const void *	key,
		vl_memsize_t	keyLen )

Removes the element represented by the specified key.

Parameters

table	pointer
key	pointer to key data
keyLen	length of key data, in bytes.

Complexity O(1) constant.

Here is the call graph for this function:

vlHashTableReserve()

void vlHashTableReserve	(	vl_hashtable *	table,
		vl_memsize_t	buckets,
		vl_memsize_t	heapSize )

Reserves memory in the hashtable before requiring it.

This function will reserve memory for buckets, element, and key data.

This is used to avoid resizing the underlying virtual heap and bucket allocations. Resizing is a costly operation which can noticeably harm the efficiency of the table if done frequently.

Parameters

table	pointer
buckets	total buckets to reserve (spots in the table)
heapSize	total bytes to reserve for element and key data

Complexity of O(1) constant.

Here is the call graph for this function:

vlHashTableSampleKey()

const vl_transient * vlHashTableSampleKey	(	vl_hashtable *	table,
		vl_hash_iter	iter,
		vl_memsize_t *	size )

Samples the key of the key-value pair indicated by the specified iterator.

Parameters

table	pointer
iter
size	output pointer representing size of the key, in bytes. may be null.

Complexity of O(1) constant.

Returns

read-only pointer to key

Here is the call graph for this function:

Here is the caller graph for this function:

vlHashTableSampleValue()

vl_transient * vlHashTableSampleValue	(	vl_hashtable *	table,
		vl_hash_iter	iter,
		vl_memsize_t *	size )

Samples the value of the key-value pair indicated by the specified iterator.

Parameters

table	pointer
iter
size	output pointer representing the size of the value, in bytes. may be null.

Complexity of O(1) constant.

Returns

read-write pointer to value

Here is the call graph for this function:

Here is the caller graph for this function: