vl_hashtable.c File Reference

#include "vl_hashtable.h"
#include <stdlib.h>
#include <string.h>

Include dependency graph for vl_hashtable.c:

Functions
vl_memsize_t	vl_HashTableGrow (vl_hashtable *table)
void	vlHashTableInit (vl_hashtable *table, vl_hash_function hashFunc)
	Initializes the specified table with a hash function.
void	vlHashTableFree (vl_hashtable *table)
	De-initializes and frees the internal resources of the specified table.
vl_hashtable *	vlHashTableNew (vl_hash_function func)
	Allocates on the heap, initializes, and returns a new hash table instance.
void	vlHashTableDelete (vl_hashtable *table)
	De-initializes and deletes the specified table and its resources.
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.
vl_hash_iter	vlHashTableFind (vl_hashtable *table, const void *key, vl_memsize_t keySize)
	Searches the hashtable for an element with the specified key.
void	vlHashTableRemoveKey (vl_hashtable *table, const void *key, vl_memsize_t keyLen)
	Removes the element represented by the specified key.
void	vlHashTableRemoveIter (vl_hashtable *table, vl_hash_iter iter)
	Removes the hash element represented by the specified iterator.
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 *src, 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.
const vl_transient *	vlHashTableSampleKey (vl_hashtable *table, vl_hash_iter iter, vl_memsize_t *outSize)
	Samples the key of the key-value pair indicated by the specified iterator.
vl_transient *	vlHashTableSampleValue (vl_hashtable *table, vl_hash_iter iter, vl_memsize_t *outSize)
	Samples the value of the key-value pair indicated by the specified iterator.
vl_hash_iter	vlHashTableFront (vl_hashtable *table)
	Returns the "first" iterator for the specified table.
vl_hash_iter	vlHashTableNext (vl_hashtable *table, vl_hash_iter iter)
	Returns the "next" iterator relative to the specified iterator.

Function Documentation

vl_HashTableGrow()

vl_memsize_t vl_HashTableGrow

(

vl_hashtable *

table

)

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Contract

• Ownership: Unchanged.
• Lifetime: All previously returned iterators and sampled pointers become invalid.
• Thread Safety: Not thread-safe.
• Nullability: table must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: None.
• Return-value Semantics: None (void).

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, including all elements and their data.

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.

Contract

• Ownership: If dest is NULL, the caller owns the returned vl_hashtable. If dest is provided, ownership remains with the caller.
• Lifetime: The cloned table remains valid until deleted or freed.
• Thread Safety: Not thread-safe.
• Nullability: src must not be NULL. dest can be NULL.
• Error Conditions: Returns NULL on allocation failure.
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: May allocate a new table struct and expansion of its internal resources.
• Return-value Semantics: Returns the pointer to the cloned table, or NULL on failure.

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.

Contract

• Ownership: dest maintains copies of all keys and data.
• Lifetime: Unchanged.
• Thread Safety: Not thread-safe.
• Nullability: src and dest must not be NULL.
• Error Conditions: Returns 0 if hash functions don't match.
• Undefined Behavior: None.
• Memory Allocation Expectations: May trigger expansion of the destination table and its arena.
• Return-value Semantics: Returns the total number of elements successfully copied.

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.

Contract

• Ownership: dest maintains copies of the key and data.
• Lifetime: Unchanged.
• Thread Safety: Not thread-safe.
• Nullability: src and dest must not be NULL.
• Error Conditions: Returns VL_HASHTABLE_ITER_INVALID if hash functions don't match or if insertion fails.
• Undefined Behavior: Passing an invalid iterator.
• Memory Allocation Expectations: May trigger expansion of the destination table and its arena.
• Return-value Semantics: Returns the vl_hash_iter of the element in the destination table, or VL_HASHTABLE_ITER_INVALID on failure.

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

)

De-initializes and deletes the specified table and its resources.

Contract

• Ownership: Releases ownership of the internal bucket array, data arena, and the vl_hashtable struct.
• Lifetime: The table pointer and all its iterators become invalid.
• Thread Safety: Not thread-safe.
• Nullability: Safe to call if table is NULL.
• Error Conditions: None.
• Undefined Behavior: Double deletion.
• Memory Allocation Expectations: Deallocates internal resources and the table struct.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: Unchanged.
• Lifetime: Unchanged.
• Thread Safety: Safe for concurrent reads.
• Nullability: table must not be NULL. key must not be NULL.
• Error Conditions: Returns VL_HASHTABLE_ITER_INVALID if the key is not found.
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns a vl_hash_iter to the found element, or VL_HASHTABLE_ITER_INVALID if not found.

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

)

De-initializes and frees the internal resources of the specified table.

Contract

• Ownership: Releases ownership of the internal bucket array and the data arena. Does NOT release the table struct itself.
• Lifetime: The table and all its iterators become invalid.
• Thread Safety: Not thread-safe.
• Nullability: table must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Double free.
• Memory Allocation Expectations: Deallocates internal memory via vlMemFree.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: None.
• Lifetime: Valid until the element is removed or the table is reallocated/destroyed.
• Thread Safety: Safe for concurrent reads.
• Nullability: Returns VL_HASHTABLE_ITER_INVALID if the table is empty.
• Error Conditions: None.
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns a vl_hash_iter to some "first" element in the 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 with a hash function.

Contract

• Ownership: The caller maintains ownership of the table struct. The function initializes the internal arena and bucket table.
• Lifetime: The table is valid until vlHashTableFree or vlHashTableDelete.
• Thread Safety: Not thread-safe. Concurrent access must be synchronized.
• Nullability: table must not be NULL. hashFunc must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Passing an already initialized table without first calling vlHashTableFree (causes memory leak).
• Memory Allocation Expectations: Allocates initial bucket array and initializes the internal arena.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: The hashtable maintains copies of the key and allocates space for the data. The caller maintains ownership of their input key and dataSize is the amount of memory reserved for the caller to own within the table.
• Lifetime: The returned iterator is valid until the element is removed, the table is cleared, or the table is destroyed.
• Thread Safety: Not thread-safe.
• Nullability: table must not be NULL. key must not be NULL.
• Error Conditions: Returns VL_HASHTABLE_ITER_INVALID if node allocation or expansion fails.
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: May trigger expansion of the underlying bucket array and the internal data arena.
• Return-value Semantics: Returns a vl_hash_iter handle to the element, or VL_HASHTABLE_ITER_INVALID on failure.

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 instance.

Contract

• Ownership: The caller owns the returned vl_hashtable pointer and is responsible for calling vlHashTableDelete.
• Lifetime: The table is valid until vlHashTableDelete.
• Thread Safety: Not thread-safe.
• Nullability: Returns NULL if heap allocation for the table struct fails.
• Error Conditions: Returns NULL on allocation failure.
• Undefined Behavior: None.
• Memory Allocation Expectations: Allocates memory for the vl_hashtable struct and its internal resources.
• Return-value Semantics: Returns a pointer to the newly allocated and initialized table, or NULL.

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.

Contract

• Ownership: None.
• Lifetime: Same as vlHashTableFront.
• Thread Safety: Same as vlHashTableFront.
• Nullability: Returns VL_HASHTABLE_ITER_INVALID if no more elements exist.
• Error Conditions: None.
• Undefined Behavior: Passing an invalid iterator.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns the next vl_hash_iter in the sequence.

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.

Contract

• Ownership: Releases ownership of the internal key copy and data block.
• Lifetime: The passed iterator becomes invalid.
• Thread Safety: Not thread-safe.
• Nullability: table must not be NULL. iter should not be VL_HASHTABLE_ITER_INVALID.
• Error Conditions: None.
• Undefined Behavior: Passing an invalid iterator or an iterator from a different table.
• Memory Allocation Expectations: None.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: Releases ownership of the internal key copy and data block.
• Lifetime: Iterators to the removed element become invalid.
• Thread Safety: Not thread-safe.
• Nullability: table must not be NULL. key must not be NULL.
• Error Conditions: None (no-op if key is not found).
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: None.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: Unchanged.
• Lifetime: Unchanged.
• Thread Safety: Not thread-safe.
• Nullability: table must not be NULL.
• Error Conditions: Allocation failure during reservation.
• Undefined Behavior: Passing an uninitialized table.
• Memory Allocation Expectations: Triggers reallocation of the bucket array and the internal data arena.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: Ownership remains with the table. The caller must not modify or free the returned pointer.
• Lifetime: The returned pointer is valid until the element is removed or the table is reallocated/destroyed.
• Thread Safety: Safe for concurrent reads.
• Nullability: Returns NULL if iter is VL_HASHTABLE_ITER_INVALID.
• Error Conditions: None.
• Undefined Behavior: Passing an invalid iterator.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns a read-only pointer to the key data.

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.

Contract

• Ownership: Ownership remains with the table. The caller can modify the data at the returned pointer but must not free it.
• Lifetime: The returned pointer is valid until the element is removed or the table is reallocated/destroyed.
• Thread Safety: Safe for concurrent reads if no thread is writing. Not thread-safe for concurrent writes to the same value.
• Nullability: Returns NULL if iter is VL_HASHTABLE_ITER_INVALID.
• Error Conditions: None.
• Undefined Behavior: Passing an invalid iterator.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns a read-write pointer to the value data.

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: