A generic open addressing hashtable. More...

Include dependency graph for hashtable.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	hashtable
	The hashtable type. More...

Macros
#define	ENTRY_t _JOIN(ENTRY, _t)
	The entry type. More...

#define	KEY_t _JOIN(KEY, _t)
	The key type. More...

#define	MATCH_t _JOIN(MATCH, _t)
	The match type. More...

#define	KEY_hash _JOIN(KEY, _hash)
	The key hash(k) method. More...

#define	MATCH_cmp _JOIN(MATCH, _cmp)
	The match cmp(m, e) method. More...

#define	NAME_new _JOIN(NAME, _new)

#define	NAME_free _JOIN(NAME, _free)

#define	NAME_stats_init _JOIN(NAME, _stats_init)

#define	NAME_add _JOIN(NAME, _add)

#define	NAME_find _JOIN(NAME, _find)

#define	NAME_iter _JOIN(NAME, _iter)

#define	NAME_next _JOIN(NAME, _next)

Typedefs
typedef struct hashtable	hashtable_t
	The hashtable type. More...

Functions
static void	hashtable_setbloom (hashtable_t *t, unsigned const h)

static bool	hashtable_getbloom (hashtable_t *t, unsigned const h)

static unsigned	mix32 (unsigned h)
	MurmurHash3 finalization mix function. More...

static unsigned	nozero (unsigned h)
	Ensure hash's are never zero. More...

static hashtable_t *	NAME_new (int size)
	Allocate and initialize a hashtable instance. More...

static void	NAME_free (hashtable_t *t)
	Destroy and free a hashtable instance. More...

static void	NAME_stats_init (hashtable_t *t)
	Initialize hashtable stats counters. More...

static ENTRY_t *	NAME_add (hashtable_t t, ENTRY_t e)
	Add an entry to a hashtable. More...

static ENTRY_t *	NAME_find (hashtable_t t, MATCH_t m)
	Find an entry in a hashtable. More...

static ENTRY_t *	NAME_next (hashtable_t t, int i)
	Get the next entry from a hashtable iterator or NULL when finished. More...

static ENTRY_t *	NAME_iter (hashtable_t t, int i)
	Initialize a iteration and return the first entry. More...

Detailed Description

A generic open addressing hashtable.

This is a minimal hashtable containing pointers to arbitrary entries with configurable hashtable size and support for custom hash() and cmp() methods. The cmp() method can either be a simple comparison between two keys, or can be against a special match object containing additional mutable state. This allows for things like deferred and cached evaluation of costly comparison data. The hash() function doesn't need to avoid clustering behaviour.

It uses open addressing with quadratic probing for collisions. The MurmurHash3 finalization function is optionally used on the hash() output to avoid clustering and can be disabled by setting HASHTABLE_NMIX32. There is no support for removing entries, only adding them. Multiple entries with the same key can be added, and you can use a fancy cmp() function to find particular entries by more than just their key. There is an iterator for iterating through all entries in the hashtable. There are optional NAME_find() find/match/hashcmp/entrycmp stats counters that can be disabled by defining HASHTABLE_NSTATS. There is an optional simple k=1 bloom filter for speed that can be disabled by defining HASHTABLE_NBLOOM.

The types and methods of the hashtable and its contents are specified by using #define parameters set to their basenames (the prefixes for the *_t type and *_func() methods) before doing #include "hashtable.h". This produces static inline type-safe methods that are either application optimized for speed or wrappers around void* implementation methods for compactness.

Parameters

ENTRY	- the entry type basename.
KEY	- optional key type basename (default: ENTRY).
MATCH	- optional match type basename (default: KEY).
NAME	- optional hashtable type basename (default: ENTRY_hashtable).

Example:

typedef ... mykey_t;
int mykey_hash(mykey_t const *e);
int mykey_cmp(mykey_t *e, mykey_t const *o);
 
typedef struct myentry {
  mykey_t key;  // Inherit from mykey_t.
  ...extra entry value data...
} myentry_t;
void myentry_init(myentry_t *e, ...);
 
#define ENTRY myentry
#define KEY mykey
#include "hashtable.h"
 
hashtable_t *t;
myentry_t entries[300];
mykey_t k;
myentry_t *e;
 
t = myentry_hashtable_new(300);
myentry_init(&entries[5], ...);
myentry_hashtable_add(t, &entries[5]);
k = ...;
e = myentry_hashtable_find(t, &k);
 
int i;
for (e = myentry_hashtable_iter(t, &i); e != NULL;
     e = myentry_hashtable_next(t, &i))
  ...
 
myentry_hashtable_free(t);

The mykey_hash() and mykey_cmp() fuctions will typically take pointers to mykey/myentry instances the same as the pointers stored in the hashtable. However it is also possible for them to take "match objects" that are a "subclass" of the entry type that contain additional state for complicated comparision operations.

Example:

typedef struct mymatch {
  mykey_t key;  // Inherit from mykey_t;
  ...extra match criteria and state data...
} mymatch_t;
int mymatch_cmp(mymatch_t *m, myentry_t const *e);
 
#define ENTRY myentry
#define KEY mykey
#define MATCH mymatch
#include "hashtable.h"
 
...
mymatch_t m;
 
t = myentry_hashtable_new(300);
...
m = ...;
e = myentry_hashtable_find(t, &m);

The mymatch_cmp() function is only called for finding hashtable entries and can mutate the mymatch_t object for doing things like deferred and cached evaluation of expensive match data. It can also access the whole myentry_t object to match against more than just the key.

Definition in file hashtable.h.

Macro Definition Documentation

◆ ENTRY_t

#define ENTRY_t _JOIN(ENTRY, _t)

The entry type.

Definition at line 209 of file hashtable.h.

◆ KEY_t

#define KEY_t _JOIN(KEY, _t)

The key type.

Definition at line 210 of file hashtable.h.

◆ MATCH_t

#define MATCH_t _JOIN(MATCH, _t)

The match type.

Definition at line 211 of file hashtable.h.

◆ KEY_hash

#define KEY_hash _JOIN(KEY, _hash)

The key hash(k) method.

Definition at line 212 of file hashtable.h.

◆ MATCH_cmp

#define MATCH_cmp _JOIN(MATCH, _cmp)

The match cmp(m, e) method.

Definition at line 213 of file hashtable.h.

◆ NAME_new

#define NAME_new _JOIN(NAME, _new)

Definition at line 215 of file hashtable.h.

◆ NAME_free

#define NAME_free _JOIN(NAME, _free)

Definition at line 216 of file hashtable.h.

◆ NAME_stats_init

#define NAME_stats_init _JOIN(NAME, _stats_init)

Definition at line 217 of file hashtable.h.

◆ NAME_add

#define NAME_add _JOIN(NAME, _add)

Definition at line 218 of file hashtable.h.

◆ NAME_find

#define NAME_find _JOIN(NAME, _find)

Definition at line 219 of file hashtable.h.

◆ NAME_iter

#define NAME_iter _JOIN(NAME, _iter)

Definition at line 220 of file hashtable.h.

◆ NAME_next

#define NAME_next _JOIN(NAME, _next)

Definition at line 221 of file hashtable.h.

Typedef Documentation

◆ hashtable_t

typedef struct hashtable hashtable_t

The hashtable type.

Function Documentation

◆ hashtable_setbloom()

static void hashtable_setbloom	(	hashtable_t *	t,
		unsigned const	h
	)

inlinestatic

Definition at line 154 of file hashtable.h.

◆ hashtable_getbloom()

static bool hashtable_getbloom	(	hashtable_t *	t,
		unsigned const	h
	)

inlinestatic

Definition at line 161 of file hashtable.h.

◆ mix32()

static unsigned mix32 ( unsigned h )

inlinestatic

MurmurHash3 finalization mix function.

Definition at line 170 of file hashtable.h.

◆ nozero()

static unsigned nozero ( unsigned h )

inlinestatic

Ensure hash's are never zero.

Definition at line 181 of file hashtable.h.

◆ NAME_new()

static hashtable_t * NAME_new ( int size )

inlinestatic

Allocate and initialize a hashtable instance.

The provided size is used as an indication of the number of entries you wish to add, but the allocated size will probably be larger depending on the implementation to enable optimisations or avoid degraded performance. It may be possible to fill the table beyond the requested size, but performance can start to degrade badly if it is over filled.

Parameters

size	- The desired minimum size of the hash table.

Returns: The initialized hashtable instance or NULL if it failed.

Definition at line 256 of file hashtable.h.

◆ NAME_free()

static void NAME_free ( hashtable_t * t )

inlinestatic

Destroy and free a hashtable instance.

This will free the hashtable, but will not free the entries in the hashtable. If you want to free the entries too, use a hashtable iterator to free the the entries first.

Parameters

*t	- The hashtable to destroy and free.

Definition at line 268 of file hashtable.h.

◆ NAME_stats_init()

static void NAME_stats_init ( hashtable_t * t )

inlinestatic

Initialize hashtable stats counters.

This will reset all the stats counters for the hashtable,

Parameters

*t	- The hashtable to initializ stats for.

Definition at line 278 of file hashtable.h.

◆ NAME_add()

static ENTRY_t * NAME_add	(	hashtable_t *	t,
		ENTRY_t *	e
	)

inlinestatic

Add an entry to a hashtable.

This doesn't use MATCH_cmp() or do any checks for existing copies or instances, so it will add duplicates. If you want to avoid adding duplicates, use NAME_find() to check for existing entries first.

Parameters

*t	- The hashtable to add to.
*e	- The entry object to add.

Returns: The added entry, or NULL if the table is full.

Definition at line 296 of file hashtable.h.

◆ NAME_find()

static ENTRY_t * NAME_find	(	hashtable_t *	t,
		MATCH_t *	m
	)

inlinestatic

Find an entry in a hashtable.

Uses MATCH_cmp() to find the first matching entry in the table in the same hash() bucket.

Parameters

*t	- The hashtable to search.
*m	- The key or match object to search for.

Returns: The first found entry, or NULL if nothing was found.

Definition at line 322 of file hashtable.h.

◆ NAME_next()

static ENTRY_t * NAME_next	(	hashtable_t *	t,
		int *	i
	)

inlinestatic

Get the next entry from a hashtable iterator or NULL when finished.

This works together with NAME_iter() for iterating through all entries in a hashtable.

Parameters

*t	- the hashtable to iterate over.
*i	- the int iterator index to use.

Returns: The next entry or NULL if the iterator is finished.

Definition at line 383 of file hashtable.h.

◆ NAME_iter()

static ENTRY_t * NAME_iter	(	hashtable_t *	t,
		int *	i
	)

inlinestatic

Initialize a iteration and return the first entry.

This works together with NAME_next() for iterating through all entries in a hashtable.

Example:

for (e = NAME_iter(t, &i); e != NULL; e = NAME_next(t, &i))

...

NAME_next

static ENTRY_t * NAME_next(hashtable_t *t, int *i)

Get the next entry from a hashtable iterator or NULL when finished.

Definition: hashtable.h:383

NAME_iter

static ENTRY_t * NAME_iter(hashtable_t *t, int *i)

Initialize a iteration and return the first entry.

Definition: hashtable.h:365

Parameters

*t	- the hashtable to iterate over.
*i	- the int iterator index to initialize.

Returns: The first entry or NULL if the hashtable is empty.

Definition at line 365 of file hashtable.h.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ ENTRY_t

◆ KEY_t

◆ MATCH_t

◆ KEY_hash

◆ MATCH_cmp

◆ NAME_new

◆ NAME_free

◆ NAME_stats_init

◆ NAME_add

◆ NAME_find

◆ NAME_iter

◆ NAME_next

Typedef Documentation

◆ hashtable_t

Function Documentation

◆ hashtable_setbloom()

◆ hashtable_getbloom()

◆ mix32()

◆ nozero()

◆ NAME_new()

◆ NAME_free()

◆ NAME_stats_init()

◆ NAME_add()

◆ NAME_find()

◆ NAME_next()

◆ NAME_iter()