hashtable.c File Reference

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

Include dependency graph for hashtable.c:

Go to the source code of this file.

Data Structures
struct	hash_node
struct	hashtable
struct	hashtable_itor

Macros
#define	LOADFACTOR_NUMERATOR   2
#define	LOADFACTOR_DENOMINATOR   3

Typedefs
typedef struct hash_node	hash_node

Functions
hashtable *	hashtable_new (dict_compare_func cmp_func, dict_hash_func hash_func, unsigned 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 |size| slots: the count is rounded up to the next entry of an internal table of primes (11, 17, 37, 67, ... roughly doubling).
dict *	hashtable_dict_new (dict_compare_func cmp_func, dict_hash_func hash_func, unsigned size)
	Like hashtable_new(), but wrapped in a generic dict for use with the dict_* macros.
size_t	hashtable_free (hashtable *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	hashtable_insert (hashtable *table, void *key)
	Insert |key| unless an equal key is present.
void **	hashtable_search (hashtable *table, const void *key)
	Return the address of the datum stored for |key|, or NULL if |key| is not present.
dict_remove_result	hashtable_remove (hashtable *table, const void *key)
	Remove the element with key |key|.
size_t	hashtable_clear (hashtable *table, dict_delete_func delete_func)
	Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
size_t	hashtable_traverse (hashtable *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	hashtable_count (const hashtable *table)
	Return the number of elements.
size_t	hashtable_size (const hashtable *table)
	Return the current number of slots in the table.
size_t	hashtable_slots_used (const hashtable *table)
	Return the number of slots whose chain is not empty.
bool	hashtable_resize (hashtable *table, unsigned new_size)
	Rehash the table into at least |size| slots, rounded up as in hashtable_new().
bool	hashtable_verify (const hashtable *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.
hashtable_itor *	hashtable_itor_new (hashtable *table)
	Create an iterator over |table| that is not positioned on any element yet.
dict_itor *	hashtable_dict_itor_new (hashtable *table)
	Like hashtable_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
void	hashtable_itor_free (hashtable_itor *itor)
	Free an iterator.
bool	hashtable_itor_valid (const hashtable_itor *itor)
	Return whether |itor| is positioned on an element.
void	hashtable_itor_invalidate (hashtable_itor *itor)
	Unposition |itor|, so that it is not positioned on any element.
bool	hashtable_itor_next (hashtable_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	hashtable_itor_prev (hashtable_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	hashtable_itor_nextn (hashtable_itor *itor, size_t count)
	Move |itor| |count| elements forward and return whether it is still positioned.
bool	hashtable_itor_prevn (hashtable_itor *itor, size_t count)
	Move |itor| |count| elements back and return whether it is still positioned.
bool	hashtable_itor_first (hashtable_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	hashtable_itor_last (hashtable_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	hashtable_itor_search (hashtable_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 *	hashtable_itor_key (const hashtable_itor *itor)
	Return the key |itor| is positioned on, or NULL if it is not positioned.
void **	hashtable_itor_datum (hashtable_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	hashtable_itor_remove (hashtable_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 hashtable.c.

LOADFACTOR_NUMERATOR

#define LOADFACTOR_NUMERATOR   2

Definition at line 39 of file hashtable.c.

Typedef Documentation

hash_node

typedef struct hash_node hash_node

Definition at line 45 of file hashtable.c.

Function Documentation

hashtable_clear()

size_t hashtable_clear	(	hashtable *	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 290 of file hashtable.c.

hashtable_count()

size_t hashtable_count

(

const hashtable *

table

)

Return the number of elements.

Takes O(1) time.

Definition at line 323 of file hashtable.c.

hashtable_dict_itor_new()

dict_itor * hashtable_dict_itor_new

(

hashtable *

table

)

Like hashtable_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 420 of file hashtable.c.

Here is the call graph for this function:

hashtable_dict_new()

dict * hashtable_dict_new	(	dict_compare_func	cmp_func,
		dict_hash_func	hash_func,
		unsigned	size )

Like hashtable_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 168 of file hashtable.c.

Here is the call graph for this function:

hashtable_free()

size_t hashtable_free	(	hashtable *	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 187 of file hashtable.c.

Here is the call graph for this function:

hashtable_insert()

dict_insert_result hashtable_insert	(	hashtable *	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 198 of file hashtable.c.

Here is the call graph for this function:

hashtable_itor_datum()

void ** hashtable_itor_datum

(

hashtable_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 600 of file hashtable.c.

hashtable_itor_first()

bool hashtable_itor_first

(

hashtable_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 539 of file hashtable.c.

hashtable_itor_free()

void hashtable_itor_free

(

hashtable_itor *

itor

)

Free an iterator.

Definition at line 434 of file hashtable.c.

hashtable_itor_invalidate()

void hashtable_itor_invalidate

(

hashtable_itor *

itor

)

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

Definition at line 465 of file hashtable.c.

hashtable_itor_key()

const void * hashtable_itor_key

(

const hashtable_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 594 of file hashtable.c.

Here is the call graph for this function:

hashtable_itor_last()

bool hashtable_itor_last

(

hashtable_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 555 of file hashtable.c.

hashtable_itor_new()

hashtable_itor * hashtable_itor_new

(

hashtable *

table

)

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

Returns NULL if memory cannot be allocated.

Definition at line 407 of file hashtable.c.

hashtable_itor_next()

bool hashtable_itor_next

(

hashtable_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 472 of file hashtable.c.

hashtable_itor_nextn()

bool hashtable_itor_nextn	(	hashtable_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 519 of file hashtable.c.

Here is the call graph for this function:

hashtable_itor_prev()

bool hashtable_itor_prev

(

hashtable_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 494 of file hashtable.c.

hashtable_itor_prevn()

bool hashtable_itor_prevn	(	hashtable_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 529 of file hashtable.c.

Here is the call graph for this function:

hashtable_itor_remove()

bool hashtable_itor_remove

(

hashtable_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 606 of file hashtable.c.

hashtable_itor_search()

bool hashtable_itor_search	(	hashtable_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 574 of file hashtable.c.

hashtable_itor_valid()

bool hashtable_itor_valid

(

const hashtable_itor *

itor

)

Return whether |itor| is positioned on an element.

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

Definition at line 459 of file hashtable.c.

hashtable_new()

hashtable * hashtable_new	(	dict_compare_func	cmp_func,
		dict_hash_func	hash_func,
		unsigned	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 |size| slots: the count is rounded up to the next entry of an internal table of primes (11, 17, 37, 67, ... roughly doubling).

Returns NULL if memory cannot be allocated.

Definition at line 144 of file hashtable.c.

Here is the call graph for this function:

hashtable_remove()

dict_remove_result hashtable_remove	(	hashtable *	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 272 of file hashtable.c.

hashtable_resize()

bool hashtable_resize	(	hashtable *	table,
		unsigned	size )

Rehash the table into at least |size| slots, rounded up as in hashtable_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, or if the slot array would not fit in a size_t. A successful resize invalidates every iterator over the table.

Definition at line 345 of file hashtable.c.

Here is the call graph for this function:

hashtable_search()

void ** hashtable_search	(	hashtable *	table,
		const void *	key )

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

Definition at line 243 of file hashtable.c.

hashtable_size()

size_t hashtable_size

(

const hashtable *

table

)

Return the current number of slots in the table.

Definition at line 329 of file hashtable.c.

hashtable_slots_used()

size_t hashtable_slots_used

(

const hashtable *

table

)

Return the number of slots whose chain is not empty.

Definition at line 335 of file hashtable.c.

hashtable_traverse()

size_t hashtable_traverse	(	hashtable *	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.

Returns the number of calls made.

Definition at line 310 of file hashtable.c.

hashtable_verify()

bool hashtable_verify

(

const hashtable *

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 386 of file hashtable.c.