Detailed Description

Author: hacatu

Version: 0.3.0 A fast hash table using quadratic probing and an incremental split table for growing. If the table needs to be extended, a second internal table will be created. All new entries will be placed in the second table, and all hash table operations will move one entry from the old table to the new table, to amortize the cost.

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Definition in file hash.h.

Go to the source code of this file.

Data Structures
struct	cr8r_hashtbl_t
	A hash table. More...

struct	cr8r_hashtbl_ft
	Function table for hash table. More...

struct	cr8r_htent_cstr_u64
	entry type for cstr -> uint64_t mapping More...

Functions
bool	cr8r_hash_ft_init (cr8r_hashtbl_ft , void data, uint64_t size, uint64_t(hash)(const cr8r_base_ft , const void ), int(cmp)(const cr8r_base_ft , const void , const void ), int(add)(cr8r_base_ft , void , void ), void(del)(cr8r_base_ft , void ))
	Convenience function to initialize a cr8r_hashtbl_ft. More...

int	cr8r_hash_init (cr8r_hashtbl_t , const cr8r_hashtbl_ft , uint64_t reserve)
	Initialize a hash table. More...

void *	cr8r_hash_get (cr8r_hashtbl_t , const cr8r_hashtbl_ft , const void *key)
	Get a pointer to an entry in the hash table. More...

void *	cr8r_hash_insert (cr8r_hashtbl_t , const cr8r_hashtbl_ft , const void key, int status)
	Insert an element into the hash table. More...

void *	cr8r_hash_append (cr8r_hashtbl_t , cr8r_hashtbl_ft , void key, int status)
	Insert an element into the hash table or modify its value. More...

int	cr8r_hash_remove (cr8r_hashtbl_t , cr8r_hashtbl_ft , const void *key)
	Remove the element with a given key. More...

void	cr8r_hash_delete (cr8r_hashtbl_t , cr8r_hashtbl_ft , void *ent)
	Remove an element of the hash table by pointer. More...

void	cr8r_hash_clear (cr8r_hashtbl_t , cr8r_hashtbl_ft )
	Remove all entries from the hash table. More...

void	cr8r_hash_destroy (cr8r_hashtbl_t , cr8r_hashtbl_ft )
	Free the resources held by the hashtable. More...

Variables
const uint64_t	cr8r_hash_u64_prime
	arbitrary large prime

cr8r_hashtbl_ft	cr8r_htft_u64_void
	function table for using hash table as set of uint64_t's

cr8r_hashtbl_ft	cr8r_htft_u64_u64
	function table for using hash table as map rom uint64_t's to uint64_t's

cr8r_hashtbl_ft	cr8r_htft_cstr_u64
	function table for using hash table as map from c strings to uint64_t's

Function Documentation

◆ cr8r_hash_ft_init()

bool cr8r_hash_ft_init	(	cr8r_hashtbl_ft *	,
		void *	data,
		uint64_t	size,
		uint64_t()(const cr8r_base_ft , const void *)	hash,
		int()(const cr8r_base_ft , const void , const void )	cmp,
		int()(cr8r_base_ft , void , void )	add,
		void()(cr8r_base_ft , void *)	del
	)

Convenience function to initialize a cr8r_hashtbl_ft.

Using standard structure initializer syntax with designated initializers may be simpler. However, this function provides basic checking (it checks the required functions aren't NULL).

Parameters

[in]	data	pointer to user defined data to associate with the function table. generally NULL is sufficient. see cr8r_base_ft for a more in-depth explaination
[in]	size	size of a single element in bytes
[in]	hash	hash function. should not be NULL. See cr8r_default_hash_u64 for a basic uint64_t implementation.
[in]	cmp	comparison function. should not be NULL. See cr8r_default_cmp for a basic generic implementation.
[in]	add	element composition function. can be NULL for all functions besides cr8r_hash_append. called to combine an existing and new element when this function is called and the element to insert is already in the tree.
[in]	del	called on any element before deleting it. can be NULL if no action is required.

Returns: 1 on success, 0 on failure (if hash or cmp is NULL)

◆ cr8r_hash_init()

int cr8r_hash_init	(	cr8r_hashtbl_t *	,
		const cr8r_hashtbl_ft *	,
		uint64_t	reserve
	)

Initialize a hash table.

The cr8r_hashtbl_ft argument should be configured manually. This is not likely to change.

Parameters

[in] reserve how many entries to reserve space for. This is rounded up to a power of 2 and then DOWN to a prime.

Returns: 1 on success, 0 on failure

◆ cr8r_hash_get()

void* cr8r_hash_get	(	cr8r_hashtbl_t *	,
		const cr8r_hashtbl_ft *	,
		const void *	key
	)

Get a pointer to an entry in the hash table.

This pointer could be invalidated if a new element is inserted into the hash table, or if any operation is performed while the secondary table is present. Thus the entry should be copied if it is needed after additional operations. If the hash table should be available from multiple threads, an external lock should be used.

Parameters

[in] key key to search the hash table for

Returns: a pointer to the element if found (which could be invalidated by another hash table operation) or NULL if absent

◆ cr8r_hash_insert()

void* cr8r_hash_insert	(	cr8r_hashtbl_t *	,
		const cr8r_hashtbl_ft *	,
		const void *	key,
		int *	status
	)

Insert an element into the hash table.

The element is copied from the pointer provided, so keep in mind both the "key" and "value" components of it should be initialized. Returns a pointer to the inserted element. As with cr8r_hash_get, this pointer could be invalidated if another hash table operation is called, and the hash table should be externally locked if the hash table should be available from multiple threads. This function will not modify the hash table if an entry with the same key already exists, but a pointer to the existing element will be returned. cr8r_hash_append can be used to change the behavior for existing keys. The status reported can be used to differentiate between the element being inserted and already being present. If the additional entry would bring the total number of entries over the capacity, the table expands with a second internal buffer. The capacity is recalculated according to the load factor supplied to this function, the number of elements to move per incremental rehash is recomputed (it is always 1 or 2 currently), and any future calls to most hash table operations will move this many elements from the old table to the new table until it can be free'd.

Parameters

[in]	key	element to insert. "key" and "value" components should be initialized.
[out]	status	if not NULL, this pointer is set to 1 on success, 2 if an element with the same key is present already, and 0 on allocation failure

Returns: a pointer to an element with the same key if one exists, otherwise a pointer to the element inserted into the hash table, as if cr8r_hash_get were called atomically afterwards

◆ cr8r_hash_append()

void* cr8r_hash_append	(	cr8r_hashtbl_t *	,
		cr8r_hashtbl_ft *	,
		void *	key,
		int *	status
	)

Insert an element into the hash table or modify its value.

Similar to cr8r_hash_insert except that if an element with the same key is present already, cr8r_hashtbl_ft::add is called to allow the existing element and even potentially the element pointed to by key to be modified. The latter is useful if elements "own" some resource, for example freeing a string in key after appending it to the string in the existing element. This function requires the add function to be specified.

Parameters

[in,out]	key	element to insert or modify existing element with. "key" and "value" components should be initialized. Can be modified if an element with the same key exists and the add function modifies its second argument.
[out]	status	if not NULL, this pointer is set to 1 on success, 2 if an element with the same key is present already, and 0 on allocation failure

Returns: a pointer to an element with the same key if one exists, otherwise a pointer to the element inserted into the hash table, as if cr8r_hash_get were called atomically afterwards

◆ cr8r_hash_remove()

int cr8r_hash_remove	(	cr8r_hashtbl_t *	,
		cr8r_hashtbl_ft *	,
		const void *	key
	)

Remove the element with a given key.

Equivalent to cr8r_hash_get followed by cr8r_hash_delete. Sets the deleted bit in the hash table, although this bit is currently unused.

Parameters

[in] key "key" of the element to remove

Returns: 1 if the element is found (and removed), 0 if the element is not found

◆ cr8r_hash_delete()

void cr8r_hash_delete	(	cr8r_hashtbl_t *	,
		cr8r_hashtbl_ft *	,
		void *	ent
	)

Remove an element of the hash table by pointer.

Useful if the element has already been found via cr8r_hash_get or cr8r_hash_next. Sets the deleted bit, although this is currently unused. Does NOT incrementally move entries from the old internal table.

Parameters

[in,out] ent the element to delete

◆ cr8r_hash_clear()

void cr8r_hash_clear	(	cr8r_hashtbl_t *	,
		cr8r_hashtbl_ft *
	)

Remove all entries from the hash table.

cr8r_hashtbl_ft::del is called on every entry if specified, otherwise this is constant time assuming free is. Does not set the unused deleted bit unless a delete function is specified. Frees the older, smaller internal table if two are present, which will also cause incremental moving to stop the next time it would occur.

◆ cr8r_hash_destroy()

void cr8r_hash_destroy	(	cr8r_hashtbl_t *	,
		cr8r_hashtbl_ft *
	)

Free the resources held by the hashtable.

If cr8r_hashtbl_ft::del is specified, it is called on every entry before free is called, otherwise, this function is constant time if free is.

Detailed Description

Data Structures

Functions

Variables

Function Documentation

◆ cr8r_hash_ft_init()

◆ cr8r_hash_init()

◆ cr8r_hash_get()

◆ cr8r_hash_insert()

◆ cr8r_hash_append()

◆ cr8r_hash_remove()

◆ cr8r_hash_delete()

◆ cr8r_hash_clear()

◆ cr8r_hash_destroy()