librsync
2.0.2
|
A generic open addressing hashtable. More...
Go to the source code of this file.
Data Structures | |
struct | hashtable |
The hashtable type. More... | |
struct | hashtable_iter |
The hashtable iterator 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(k) _JOIN(KEY, _hash)(k) |
The key hash(k) method. More... | |
#define | MATCH_CMP(m, e) _JOIN(MATCH, _cmp)(m, e) |
The match cmp(m, e) method. More... | |
Typedefs | |
typedef struct hashtable | hashtable_t |
The hashtable type. More... | |
typedef struct hashtable_iter | hashtable_iter_t |
The hashtable iterator type. More... | |
Functions | |
static unsigned | mix32 (unsigned int h) |
MurmurHash3 finalization mix function. 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_iter (hashtable_iter_t *i, hashtable_t *t) |
Initialize a hashtable_iter_t and return the first entry. More... | |
static ENTRY_T * | NAME_next (hashtable_iter_t *i) |
Get the next entry from a hashtable iterator or NULL when finished. More... | |
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 used on the hash() output to avoid clustering. 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 hashtable_find() find/match/hashcmp/entrycmp stats counters that can be disabled by defining HASHTABLE_NSTATS.
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.
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:
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:
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.
#define ENTRY_T _JOIN(ENTRY, _t) |
The entry type.
Definition at line 183 of file hashtable.h.
#define KEY_T _JOIN(KEY, _t) |
The key type.
Definition at line 184 of file hashtable.h.
#define MATCH_T _JOIN(MATCH, _t) |
The match type.
Definition at line 185 of file hashtable.h.
#define KEY_HASH | ( | k | ) | _JOIN(KEY, _hash)(k) |
The key hash(k) method.
Definition at line 187 of file hashtable.h.
#define MATCH_CMP | ( | m, | |
e | |||
) | _JOIN(MATCH, _cmp)(m, e) |
The match cmp(m, e) method.
Definition at line 189 of file hashtable.h.
typedef struct hashtable hashtable_t |
The hashtable type.
typedef struct hashtable_iter hashtable_iter_t |
The hashtable iterator type.
|
inlinestatic |
MurmurHash3 finalization mix function.
Definition at line 153 of file hashtable.h.
|
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.
size | - The desired minimum size of the hash table. |
Definition at line 219 of file hashtable.h.
|
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.
*t | - The hashtable to destroy and free. |
Definition at line 230 of file hashtable.h.
|
inlinestatic |
Initialize hashtable stats counters.
This will reset all the stats counters for the hashtable,
*t | - The hashtable to initializ stats for. |
Definition at line 239 of file hashtable.h.
|
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 hashtable_find() to check for existing entries first.
*t | - The hashtable to add to. |
*e | - The entry object to add. |
Definition at line 256 of file hashtable.h.
|
inlinestatic |
Find an entry in a hashtable.
Uses MATCH_CMP() to find the first matching entry in the table in the same hash() bucket.
*t | - The hashtable to search. |
*m | - The key or match object to search for. |
Definition at line 276 of file hashtable.h.
|
inlinestatic |
Initialize a hashtable_iter_t and return the first entry.
This works together with hashtable_next() for iterating through all entries in a hashtable.
Example:
*i | - the hashtable iterator to initialize. |
*t | - the hashtable to iterate over. |
Definition at line 309 of file hashtable.h.
|
inlinestatic |
Get the next entry from a hashtable iterator or NULL when finished.
*i | - the hashtable iterator to use. |
Definition at line 318 of file hashtable.h.