librsync  2.3.1
Data Structures | Macros | Typedefs | Functions
hashtable.h File Reference

Go to the source code of 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_tNAME_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_tNAME_add (hashtable_t *t, ENTRY_t *e)
 Add an entry to a hashtable. More...
 
static ENTRY_tNAME_find (hashtable_t *t, MATCH_t *m)
 Find an entry in a hashtable. More...
 
static ENTRY_tNAME_next (hashtable_t *t, int *i)
 Get the next entry from a hashtable iterator or NULL when finished. More...
 
static ENTRY_tNAME_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"
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 208 of file hashtable.h.

◆ KEY_t

#define KEY_t   _JOIN(KEY, _t)

The key type.

Definition at line 209 of file hashtable.h.

◆ MATCH_t

#define MATCH_t   _JOIN(MATCH, _t)

The match type.

Definition at line 210 of file hashtable.h.

◆ KEY_hash

#define KEY_hash   _JOIN(KEY, _hash)

The key hash(k) method.

Definition at line 211 of file hashtable.h.

◆ MATCH_cmp

#define MATCH_cmp   _JOIN(MATCH, _cmp)

The match cmp(m, e) method.

Definition at line 212 of file hashtable.h.

Typedef Documentation

◆ hashtable_t

typedef struct hashtable hashtable_t

The hashtable type.

Function Documentation

◆ mix32()

static unsigned mix32 ( unsigned  h)
inlinestatic

MurmurHash3 finalization mix function.

Definition at line 172 of file hashtable.h.

◆ nozero()

static unsigned nozero ( unsigned  h)
inlinestatic

Ensure hash's are never zero.

Definition at line 183 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 255 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 267 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 277 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 295 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 321 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 382 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))
...
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 364 of file hashtable.h.

NAME_iter
static ENTRY_t * NAME_iter(hashtable_t *t, int *i)
Initialize a iteration and return the first entry.
Definition: hashtable.h:364
hashtable.h
hashtable
The hashtable type.
Definition: hashtable.h:130
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:382