#include "hashtable2.h"
#include <string.h>
#include "dict_private.h"
#include "hashtable_common.h"

Include dependency graph for hashtable2.c:

Data Structures
struct	hash_node

struct	hashtable2

struct	hashtable2_itor

Macros
#define	LOADFACTOR_NUMERATOR 2

#define	LOADFACTOR_DENOMINATOR 3

Functions
hashtable2 *	hashtable2_new (dict_compare_func cmp_func, dict_hash_func hash_func, unsigned initial_size)
	Create an empty hash table that compares keys with \|cmp_func\| and hashes them with \|hash_func\| (neither may be NULL), starting with at least \|initial_size\| slots: the count is rounded up to the next entry of an internal table of primes (11, 17, 37, 67, ... roughly doubling).

dict *	hashtable2_dict_new (dict_compare_func cmp_func, dict_hash_func hash_func, unsigned initial_size)
	Like hashtable2_new(), but wrapped in a generic dict for use with the dict_* macros.

size_t	hashtable2_free (hashtable2 *table, dict_delete_func delete_func)
	Remove every element, calling \|delete_func\|(key, datum) for each unless \|delete_func\| is NULL, and free the table.

dict_insert_result	hashtable2_insert (hashtable2 table, void key)
	Insert \|key\| unless an equal key is present.

void **	hashtable2_search (hashtable2 table, const void key)
	Return the address of the datum stored for \|key\|, or NULL if \|key\| is not present.

dict_remove_result	hashtable2_remove (hashtable2 table, const void key)
	Remove the element with key \|key\|.

size_t	hashtable2_clear (hashtable2 *table, dict_delete_func delete_func)
	Remove every element, calling \|delete_func\|(key, datum) for each unless \|delete_func\| is NULL.

size_t	hashtable2_traverse (hashtable2 table, dict_visit_func visit, void user_data)
	Call \|visit\|(key, datum, \|user_data\|) for each element in table order (unspecified), stopping early if \|visit\| returns false.

size_t	hashtable2_count (const hashtable2 *table)
	Return the number of elements.

size_t	hashtable2_size (const hashtable2 *table)
	Return the current number of slots in the table.

size_t	hashtable2_slots_used (const hashtable2 *table)
	Return the number of occupied slots, which for open addressing equals the number of elements.

bool	hashtable2_resize (hashtable2 *table, unsigned new_size)
	Rehash the table into at least \|size\| slots, rounded up as in hashtable2_new().

bool	hashtable2_verify (const hashtable2 *table)
	Check the internal invariants of the table and return true if they hold, or print the first failed check to stderr and return false.

hashtable2_itor *	hashtable2_itor_new (hashtable2 *table)
	Create an iterator over \|table\| that is not positioned on any element yet.

dict_itor *	hashtable2_dict_itor_new (hashtable2 *table)
	Like hashtable2_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.

void	hashtable2_itor_free (hashtable2_itor *itor)
	Free an iterator.

bool	hashtable2_itor_valid (const hashtable2_itor *itor)
	Return whether \|itor\| is positioned on an element.

void	hashtable2_itor_invalidate (hashtable2_itor *itor)
	Unposition \|itor\|, so that it is not positioned on any element.

bool	hashtable2_itor_next (hashtable2_itor *itor)
	Move \|itor\| to the next element in table order (unspecified) and return true, or unposition it and return false if there is none.

bool	hashtable2_itor_prev (hashtable2_itor *itor)
	Move \|itor\| to the previous element in table order (unspecified) and return true, or unposition it and return false if there is none.

bool	hashtable2_itor_nextn (hashtable2_itor *itor, size_t count)
	Move \|itor\| \|count\| elements forward and return whether it is still positioned.

bool	hashtable2_itor_prevn (hashtable2_itor *itor, size_t count)
	Move \|itor\| \|count\| elements back and return whether it is still positioned.

bool	hashtable2_itor_first (hashtable2_itor *itor)
	Position \|itor\| on the first element in table order (unspecified) and return true, or unposition it and return false if the table is empty.

bool	hashtable2_itor_last (hashtable2_itor *itor)
	Position \|itor\| on the last element in table order (unspecified) and return true, or unposition it and return false if the table is empty.

bool	hashtable2_itor_search (hashtable2_itor itor, const void key)
	Position \|itor\| on \|key\| and return true, or unposition it and return false if \|key\| is not present.

const void *	hashtable2_itor_key (const hashtable2_itor *itor)
	Return the key \|itor\| is positioned on, or NULL if it is not positioned.

void **	hashtable2_itor_datum (hashtable2_itor *itor)
	Return the address of the datum \|itor\| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.

bool	hashtable2_itor_remove (hashtable2_itor *itor)
	Remove the element \|itor\| is positioned on and unposition \|itor\|; return false if it was not positioned.

Macro Definition Documentation

◆ LOADFACTOR_DENOMINATOR

#define LOADFACTOR_DENOMINATOR 3

Definition at line 40 of file hashtable2.c.

◆ LOADFACTOR_NUMERATOR

#define LOADFACTOR_NUMERATOR 2

Definition at line 39 of file hashtable2.c.

Function Documentation

◆ hashtable2_clear()

size_t hashtable2_clear	(	hashtable2 *	table,
		dict_delete_func	delete_func )

Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.

Returns the number of elements removed. The table stays usable. See Iterator invalidation for which iterators this invalidates.

Definition at line 329 of file hashtable2.c.

◆ hashtable2_count()

size_t hashtable2_count ( const hashtable2 * table )

Return the number of elements.

Takes O(1) time.

Definition at line 362 of file hashtable2.c.

◆ hashtable2_dict_itor_new()

dict_itor * hashtable2_dict_itor_new ( hashtable2 * table )

Like hashtable2_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.

Free it with dict_itor_free().

Definition at line 454 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_dict_new()

dict * hashtable2_dict_new	(	dict_compare_func	cmp_func,
		dict_hash_func	hash_func,
		unsigned	initial_size )

Like hashtable2_new(), but wrapped in a generic dict for use with the dict_* macros.

Free it with dict_free(). Returns NULL if memory cannot be allocated.

Definition at line 164 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_free()

size_t hashtable2_free	(	hashtable2 *	table,
		dict_delete_func	delete_func )

Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the table.

Returns the number of elements removed. Iterators over the table may afterwards only be freed.

Definition at line 183 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_insert()

dict_insert_result hashtable2_insert	(	hashtable2 *	table,
		void *	key )

Insert |key| unless an equal key is present.

Returns {&datum, true} for a new key, whose datum starts as NULL; the table stores the |key| pointer itself, it does not copy the key. If an equal key is present, returns {&datum, false} with that key's datum, and |key| is not stored and still belongs to the caller. Returns {NULL, false} if memory cannot be allocated. May grow the table first, which invalidates every iterator over it; inserting a key that is already present never does.

Definition at line 224 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_itor_datum()

void ** hashtable2_itor_datum ( hashtable2_itor * itor )

Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.

Definition at line 609 of file hashtable2.c.

◆ hashtable2_itor_first()

bool hashtable2_itor_first ( hashtable2_itor * itor )

Position |itor| on the first element in table order (unspecified) and return true, or unposition it and return false if the table is empty.

Definition at line 553 of file hashtable2.c.

◆ hashtable2_itor_free()

void hashtable2_itor_free ( hashtable2_itor * itor )

Free an iterator.

Definition at line 468 of file hashtable2.c.

◆ hashtable2_itor_invalidate()

void hashtable2_itor_invalidate ( hashtable2_itor * itor )

Unposition |itor|, so that it is not positioned on any element.

Definition at line 501 of file hashtable2.c.

◆ hashtable2_itor_key()

const void * hashtable2_itor_key ( const hashtable2_itor * itor )

Return the key |itor| is positioned on, or NULL if it is not positioned.

The key belongs to the container and must not be modified in a way that changes how it compares.

Definition at line 603 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_itor_last()

bool hashtable2_itor_last ( hashtable2_itor * itor )

Position |itor| on the last element in table order (unspecified) and return true, or unposition it and return false if the table is empty.

Definition at line 567 of file hashtable2.c.

◆ hashtable2_itor_new()

hashtable2_itor * hashtable2_itor_new ( hashtable2 * table )

Create an iterator over |table| that is not positioned on any element yet.

Returns NULL if memory cannot be allocated.

Definition at line 442 of file hashtable2.c.

◆ hashtable2_itor_next()

bool hashtable2_itor_next ( hashtable2_itor * itor )

Move |itor| to the next element in table order (unspecified) and return true, or unposition it and return false if there is none.

An unpositioned iterator stays unpositioned and returns false.

Definition at line 507 of file hashtable2.c.

◆ hashtable2_itor_nextn()

bool hashtable2_itor_nextn	(	hashtable2_itor *	itor,
		size_t	count )

Move |itor| |count| elements forward and return whether it is still positioned.

It becomes unpositioned if it runs past the last element.

Definition at line 535 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_itor_prev()

bool hashtable2_itor_prev ( hashtable2_itor * itor )

Move |itor| to the previous element in table order (unspecified) and return true, or unposition it and return false if there is none.

An unpositioned iterator stays unpositioned and returns false.

Definition at line 521 of file hashtable2.c.

◆ hashtable2_itor_prevn()

bool hashtable2_itor_prevn	(	hashtable2_itor *	itor,
		size_t	count )

Move |itor| |count| elements back and return whether it is still positioned.

It becomes unpositioned if it runs past the first element.

Definition at line 544 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_itor_remove()

bool hashtable2_itor_remove ( hashtable2_itor * itor )

Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.

No delete function is called, so fetch the key and datum first if they need freeing. See Iterator invalidation for which iterators this invalidates.

Definition at line 615 of file hashtable2.c.

◆ hashtable2_itor_search()

bool hashtable2_itor_search	(	hashtable2_itor *	itor,
		const void *	key )

Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.

Definition at line 581 of file hashtable2.c.

◆ hashtable2_itor_valid()

bool hashtable2_itor_valid ( const hashtable2_itor * itor )

Return whether |itor| is positioned on an element.

False also after a modification of the table that invalidated it.

Definition at line 491 of file hashtable2.c.

◆ hashtable2_new()

hashtable2 * hashtable2_new	(	dict_compare_func	cmp_func,
		dict_hash_func	hash_func,
		unsigned	initial_size )

Returns NULL if memory cannot be allocated.

Definition at line 140 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_remove()

dict_remove_result hashtable2_remove	(	hashtable2 *	table,
		const void *	key )

Remove the element with key |key|.

Returns {key, datum, true}, handing the stored key and datum back to the caller (no delete function is called), or {NULL, NULL, false} if |key| is not present. See Iterator invalidation for which iterators this invalidates.

Definition at line 303 of file hashtable2.c.

◆ hashtable2_resize()

bool hashtable2_resize	(	hashtable2 *	table,
		unsigned	size )

Rehash the table into at least |size| slots, rounded up as in hashtable2_new().

Returns true on success, or if the table already has that many slots. Returns false, leaving the table unchanged, if memory cannot be allocated, if fewer slots than elements are requested, or if the slot array would not fit in a size_t. A successful resize invalidates every iterator over the table.

Definition at line 380 of file hashtable2.c.

Here is the call graph for this function:

◆ hashtable2_search()

void ** hashtable2_search	(	hashtable2 *	table,
		const void *	key )

Return the address of the datum stored for |key|, or NULL if |key| is not present.

Definition at line 245 of file hashtable2.c.

◆ hashtable2_size()

size_t hashtable2_size ( const hashtable2 * table )

Return the current number of slots in the table.

Definition at line 368 of file hashtable2.c.

◆ hashtable2_slots_used()

size_t hashtable2_slots_used ( const hashtable2 * table )

Return the number of occupied slots, which for open addressing equals the number of elements.

Definition at line 374 of file hashtable2.c.

◆ hashtable2_traverse()

size_t hashtable2_traverse	(	hashtable2 *	table,
		dict_visit_func	visit,
		void *	user_data )

Returns the number of calls made.

Definition at line 348 of file hashtable2.c.

◆ hashtable2_verify()

bool hashtable2_verify ( const hashtable2 * table )

Check the internal invariants of the table and return true if they hold, or print the first failed check to stderr and return false.

Meant for testing and debugging; takes O(n) time.

Definition at line 425 of file hashtable2.c.

Data Structures

Macros

Functions

Macro Definition Documentation

◆ LOADFACTOR_DENOMINATOR

◆ LOADFACTOR_NUMERATOR

Function Documentation

◆ hashtable2_clear()

◆ hashtable2_count()

◆ hashtable2_dict_itor_new()

◆ hashtable2_dict_new()

◆ hashtable2_free()

◆ hashtable2_insert()

◆ hashtable2_itor_datum()

◆ hashtable2_itor_first()

◆ hashtable2_itor_free()

◆ hashtable2_itor_invalidate()

◆ hashtable2_itor_key()

◆ hashtable2_itor_last()

◆ hashtable2_itor_new()

◆ hashtable2_itor_next()

◆ hashtable2_itor_nextn()

◆ hashtable2_itor_prev()

◆ hashtable2_itor_prevn()

◆ hashtable2_itor_remove()

◆ hashtable2_itor_search()

◆ hashtable2_itor_valid()

◆ hashtable2_new()

◆ hashtable2_remove()

◆ hashtable2_resize()

◆ hashtable2_search()

◆ hashtable2_size()

◆ hashtable2_slots_used()

◆ hashtable2_traverse()

◆ hashtable2_verify()