Generic hashtable. More...

#include <stddef.h>
#include <stdbool.h>
#include "datatypes.h"
#include "pool.h"

Data Structures
struct	HashTable
	Table containing lists of buckets to create associations between keys and values. More...

struct	HashTable::_Bucket
	Singly-linked list implementation storing keys & values. More...

struct	HashTable::_HashTablePair
	Found key-value pair. More...

struct	HashTableIter
	Structure to iterate over the elements of a HashTable. More...

Macros
#define	HASHTABLE_AUTO_RESIZE 0

#define	hashtable_pair_key(p) p->bucket->key

#define	hashtable_pair_value(p) p->bucket->data

#define	hashtable_iter_key(iter) iter.liter->key

#define	hashtable_iter_value(iter) iter.liter->data

Typedefs
typedef struct _HashTablePair	HashTablePair

Enumerations
enum	HashTableInsertResult { HASHTABLE_INSERT_RESULT_NEW , HASHTABLE_INSERT_RESULT_REPLACED , HASHTABLE_INSERT_RESULT_FAILED }
	result of hashtable_set() method. More...

Functions
HashTable *	hashtable_new (size_t size, HashFunc hash_func, EqualFunc compare_keys, FreeFunc free_key, FreeFunc free_value)

void	hashtable_init (HashTable *table, size_t size, HashFunc hash_func, EqualFunc compare_keys, FreeFunc free_key, FreeFunc free_value)

void	hashtable_destroy (HashTable *table)

void	hashtable_free (HashTable *table)

void	hashtable_clear (HashTable *table)

HashTableInsertResult	hashtable_set (HashTable table, void key, void *value, bool overwrite_key)

void	hashtable_remove (HashTable table, const void key)

HashTablePair *	hashtable_lookup (HashTable table, const void key)

void *	hashtable_pair_get_key (const HashTablePair *pair)

void *	hashtable_pair_get_value (const HashTablePair *pair)

void	hashtable_pair_set_value (HashTablePair pair, void value)

bool	hashtable_key_exists (const HashTable table, const void key)

size_t	hashtable_count (const HashTable *table)

void	hashtable_iter_init (const HashTable table, HashTableIter iter)

bool	hashtable_iter_next (HashTableIter *iter)

void *	hashtable_iter_get_key (const HashTableIter *iter)

void *	hashtable_iter_get_value (const HashTableIter *iter)

Detailed Description

Generic hashtable.

Author: Sebastian Fedrau sebas.nosp@m.tian.nosp@m..fedr.nosp@m.au@g.nosp@m.mail..nosp@m.com

Definition in file hashtable.h.

Data Structure Documentation

◆ HashTable

struct HashTable

Table containing lists of buckets to create associations between keys and values.

Definition at line 38 of file hashtable.h.

Data Fields
struct _Bucket **	buckets	Array containing pointers to buckets.
EqualFunc	compare_keys	Function to check equality of two keys.
size_t	count	Number of stored elements.
FreeFunc	free_key	Function to free keys.
FreeFunc	free_value	Function to free values.
bool	grow	Enable/disable auto-resize.
HashFunc	hash	Function to create a hash from a value.
struct _HashTablePair	pair	Last found key-value pair.
Pool *	pool	Pool used to create/destroy list elements.
size_t	size	Size of the hash table.
const size_t *	sizeptr	Pointer to a prime number specifying the current table size.

◆ HashTable::_Bucket

struct HashTable::_Bucket

Singly-linked list implementation storing keys & values.

Definition at line 61 of file hashtable.h.

Data Fields
void *	data	Value of the element.
void *	key	Key of the element.
struct _Bucket *	next	Pointer to next list element or NULL.

◆ HashTable::_HashTablePair

struct HashTable::_HashTablePair

Found key-value pair.

Definition at line 81 of file hashtable.h.

Data Fields
struct _Bucket *	bucket	Bucket containing the found key-value pair.
FreeFunc	free_value	Function to free the associated value.

◆ HashTableIter

struct HashTableIter

Structure to iterate over the elements of a HashTable.

Definition at line 97 of file hashtable.h.

Data Fields
bool	finished	true if iteration is completed.
struct _Bucket *	liter	Pointer to current list element.
size_t	offset	Index of current bucket.
const HashTable *	table	Pointer to the associated HashTable.

Macro Definition Documentation

◆ HASHTABLE_AUTO_RESIZE

#define HASHTABLE_AUTO_RESIZE 0

HashTable size used to enable auto-resizing.

Definition at line 32 of file hashtable.h.

◆ hashtable_iter_key

#define hashtable_iter_key ( iter ) iter.liter->key

Accesses the key of the current element directly.

Definition at line 270 of file hashtable.h.

◆ hashtable_iter_value

#define hashtable_iter_value ( iter ) iter.liter->data

Accesses the value of the current element directly.

Definition at line 281 of file hashtable.h.

◆ hashtable_pair_key

#define hashtable_pair_key ( p ) p->bucket->key

Accesses the key of a key-value pair directly.

Definition at line 206 of file hashtable.h.

◆ hashtable_pair_value

#define hashtable_pair_value ( p ) p->bucket->data

Accesses the value of a key-value pair directly.

Definition at line 217 of file hashtable.h.

Typedef Documentation

◆ HashTablePair

typedef struct _HashTablePair HashTablePair

A found key-value pair.

Definition at line 91 of file hashtable.h.

Enumeration Type Documentation

◆ HashTableInsertResult

enum HashTableInsertResult

result of hashtable_set() method.

Enumerator
HASHTABLE_INSERT_RESULT_NEW	Item has been inserted.
HASHTABLE_INSERT_RESULT_REPLACED	Item has been replaced.
HASHTABLE_INSERT_RESULT_FAILED	Item insertion failed.

Definition at line 113 of file hashtable.h.

Function Documentation

◆ hashtable_clear()

void hashtable_clear ( HashTable * table )

Parameters

table a HashTable

Removes all elements from the HashTable.

Definition at line 218 of file hashtable.c.

◆ hashtable_count()

size_t hashtable_count ( const HashTable * table )

Parameters

table a HashTable

Returns: number of stored elements

Gets the number of stored elements.

Definition at line 481 of file hashtable.c.

◆ hashtable_destroy()

void hashtable_destroy ( HashTable * table )

Parameters

table a HashTable

Frees all keys, values and the table pointer.

Definition at line 167 of file hashtable.c.

◆ hashtable_free()

void hashtable_free ( HashTable * table )

Parameters

table a HashTable

Frees all keys and values without freeing the table pointer.

Definition at line 208 of file hashtable.c.

◆ hashtable_init()

void hashtable_init	(	HashTable *	table,
		size_t	size,
		HashFunc	hash_func,
		EqualFunc	compare_keys,
		FreeFunc	free_key,
		FreeFunc	free_value
	)

Parameters

table	a HashTable
size	size of the hash table (number of buckets), HASHTABLE_AUTO_RESIZE to grow automatically
hash_func	function to create hash from a key
compare_keys	function to check equality of two keys
free_key	function to free keys or NULL
free_value	function to free values or NULL

Initializes a HashTable.

Definition at line 120 of file hashtable.c.

◆ hashtable_iter_get_key()

void * hashtable_iter_get_key ( const HashTableIter * iter )

Parameters

iter	a HashTableIter

Returns: key of current element

Retrieves the key of the current element.

Definition at line 537 of file hashtable.c.

◆ hashtable_iter_get_value()

void * hashtable_iter_get_value ( const HashTableIter * iter )

Parameters

iter	a HashTableIter

Returns: value of current element

Retrieves the value of the current element.

Definition at line 545 of file hashtable.c.

◆ hashtable_iter_init()

void hashtable_iter_init	(	const HashTable *	table,
		HashTableIter *	iter
	)

Parameters

table	a HashTable
iter	an uninitialized HashTableIter

Initializes a key/value pair iterator and associates it with the table. Modifying the table while using the iterator might lead to undefined behaviour.

Definition at line 489 of file hashtable.c.

◆ hashtable_iter_next()

bool hashtable_iter_next ( HashTableIter * iter )

Parameters

iter	a HashTableIter

Returns: false if end of the HashTable has been reached

Goes to next element of the HashTable.

Definition at line 513 of file hashtable.c.

◆ hashtable_key_exists()

bool hashtable_key_exists	(	const HashTable *	table,
		const void *	key
	)

Parameters

table	a HashTable
key	key to test

Returns: true if given key does exist

Checks if a key does exist.

Definition at line 470 of file hashtable.c.

◆ hashtable_lookup()

HashTablePair * hashtable_lookup	(	HashTable *	table,
		const void *	key
	)

Parameters

table	a HashTable
key	key to lookup

Returns: the found key-value pair or NULL

Looks up a key-value pair in the HashTable.

Definition at line 416 of file hashtable.c.

◆ hashtable_new()

HashTable * hashtable_new	(	size_t	size,
		HashFunc	hash_func,
		EqualFunc	compare_keys,
		FreeFunc	free_key,
		FreeFunc	free_value
	)

Parameters

size	size of the hash table (number of buckets), HASHTABLE_AUTO_RESIZE to grow automatically
hash_func	function to create hash from a key
compare_keys	function to check equality of two keys
free_key	function to free keys or NULL
free_value	function to free values or NULL

Returns: a new HashTable

Creates a new HashTable.

Definition at line 100 of file hashtable.c.

◆ hashtable_pair_get_key()

void * hashtable_pair_get_key ( const HashTablePair * pair )

Parameters

pair	a key-value pair

Returns: key of the pair

Retrieves the key of a key-value pair.

Definition at line 435 of file hashtable.c.

◆ hashtable_pair_get_value()

void * hashtable_pair_get_value ( const HashTablePair * pair )

Parameters

pair	a key-value pair

Returns: value of the pair

Retrieves the value of a key-value pair.

Definition at line 445 of file hashtable.c.

◆ hashtable_pair_set_value()

void hashtable_pair_set_value	(	HashTablePair *	pair,
		void *	value
	)

Parameters

pair	a HashTablePair
value	new value to set

Overwrites the value of a key-value pair.

Definition at line 455 of file hashtable.c.

◆ hashtable_remove()

void hashtable_remove	(	HashTable *	table,
		const void *	key
	)

Parameters

table	a HashTable
key	key of the element to remove

Removes an element from the HashTable.

Definition at line 367 of file hashtable.c.

◆ hashtable_set()

HashTableInsertResult hashtable_set	(	HashTable *	table,
		void *	key,
		void *	value,
		bool	overwrite_key
	)

Parameters

table	a HashTable
key	key to insert
value	the value to associate with the key
overwrite_key	true to overwrite already existing keys

Returns: type of the performed insert operation

Inserts a new key and value in the HashTable. If overwrite_key is set an existing key is freed using the specified free_key function before it gets replaced.

Definition at line 308 of file hashtable.c.

Data Structures

Macros

Typedefs

Enumerations

Functions

Detailed Description

Data Structure Documentation

◆ HashTable

◆ HashTable::_Bucket

◆ HashTable::_HashTablePair

◆ HashTableIter

Macro Definition Documentation

◆ HASHTABLE_AUTO_RESIZE

◆ hashtable_iter_key

◆ hashtable_iter_value

◆ hashtable_pair_key

◆ hashtable_pair_value

Typedef Documentation

◆ HashTablePair

Enumeration Type Documentation

◆ HashTableInsertResult

Function Documentation

◆ hashtable_clear()

◆ hashtable_count()

◆ hashtable_destroy()

◆ hashtable_free()

◆ hashtable_init()

◆ hashtable_iter_get_key()

◆ hashtable_iter_get_value()

◆ hashtable_iter_init()

◆ hashtable_iter_next()

◆ hashtable_key_exists()

◆ hashtable_lookup()

◆ hashtable_new()

◆ hashtable_pair_get_key()

◆ hashtable_pair_get_value()

◆ hashtable_pair_set_value()

◆ hashtable_remove()

◆ hashtable_set()