/*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-

*

* hashtable.h -- a generic open addressing hashtable.

*

* Copyright (C) 2003 by Donovan Baarda <[email protected]>

*

* This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU Lesser General Public License as published by

* the Free Software Foundation; either version 2.1 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU Lesser General Public License for more details.

*

* You should have received a copy of the GNU Lesser General Public License

* along with this program; if not, write to the Free Software

* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

/** \file hashtable.h

* 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.

*

* \param ENTRY - the entry type basename.

*

* \param KEY - optional key type basename (default: ENTRY).

*

* \param MATCH - optional match type basename (default: KEY).

*

* \param NAME - optional hashtable type basename (default: ENTRY_hashtable).

*

* Example: \code

* 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);

* \endcode

*

* 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: \code

* 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);

* \endcode

*

* 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. */

#ifndef HASHTABLE_H

# define HASHTABLE_H

# include <stdbool.h>

/** The hashtable type. */

typedef struct hashtable {

int size; /**< Size of allocated hashtable. */

int count; /**< Number of entries in hashtable. */

unsigned tmask; /**< Mask to get the hashtable index. */

# ifndef HASHTABLE_NBLOOM

unsigned bshift; /**< Shift to get the bloomfilter index. */

# endif

# ifndef HASHTABLE_NSTATS

/* The following are for accumulating NAME_find() stats. */

long find_count; /**< The count of finds tried. */

long match_count; /**< The count of matches found. */

long hashcmp_count; /**< The count of hash compares done. */

long entrycmp_count; /**< The count of entry compares done. */

# endif

# ifndef HASHTABLE_NBLOOM

unsigned char *kbloom; /**< Bloom filter of hash keys with k=1. */

# endif

void **etable; /**< Table of pointers to entries. */

unsigned ktable[]; /**< Table of hash keys. */

} hashtable_t;

/* void* implementations for the type-safe static inline wrappers below. */

hashtable_t *_hashtable_new(int size);

void _hashtable_free(hashtable_t *t);

# ifndef HASHTABLE_NBLOOM

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

{

/* Use upper bits for a "different hash". */

unsigned const i = h >> t->bshift;

t->kbloom[i / 8] |= (unsigned char)(1 << (i % 8));

}

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

{

/* Use upper bits for a "different hash". */

unsigned const i = h >> t->bshift;

return (t->kbloom[i / 8] >> (i % 8)) & 1;

}

# endif

/** MurmurHash3 finalization mix function. */

static inline unsigned mix32(unsigned h)

{

h ^= h >> 16;

h *= 0x85ebca6b;

h ^= h >> 13;

h *= 0xc2b2ae35;

h ^= h >> 16;

return h;

}

/** Ensure hash's are never zero. */

static inline unsigned nozero(unsigned h)

{

return h ? h : (unsigned)-1;

}

#endif /* !HASHTABLE_H */

/* If ENTRY is defined, define type-dependent static inline methods. */

#ifdef ENTRY

# include <assert.h>

# include <stddef.h>

# define _JOIN2(x, y) x##y

# define _JOIN(x, y) _JOIN2(x, y)

# ifndef KEY

# define KEY ENTRY

# endif

# ifndef MATCH

# define MATCH KEY

# endif

# ifndef NAME

# define NAME _JOIN(ENTRY, _hashtable)

# endif

# define ENTRY_t _JOIN(ENTRY, _t) /**< The entry type. */

# define KEY_t _JOIN(KEY, _t) /**< The key type. */

# define MATCH_t _JOIN(MATCH, _t) /**< The match type. */

# define KEY_hash _JOIN(KEY, _hash) /**< The key hash(k) method. */

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

/* The names for all the hashtable methods. */

# 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)

/* Modified hash() with/without mix32() and reserving zero for empty buckets. */

# ifdef HASHTABLE_NMIX32

# define _KEY_HASH(k) nozero(KEY_hash((KEY_t *)k))

# else

# define _KEY_HASH(k) nozero(mix32(KEY_hash((KEY_t *)k)))

# endif

/* Loop macro for probing table t for key hash hk, iterating with index i and

entry hash h, terminating at an empty bucket. */

# define _for_probe(t, hk, i, h) \

unsigned const *const ktable = t->ktable;\

unsigned const tmask = t->tmask;\

unsigned i, s, h;\

for (i = hk & tmask, s = 0; (h = ktable[i]); i = (i + ++s) & tmask)

/* Conditional macro for incrementing stats counters. */

# ifndef HASHTABLE_NSTATS

# define _stats_inc(c) (c++)

# else

# define _stats_inc(c)

# endif

/** 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.

*

* \param size - The desired minimum size of the hash table.

*

* \return The initialized hashtable instance or NULL if it failed. */

static inline hashtable_t *NAME_new(int size)

{

return _hashtable_new(size);

}

/** 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.

*

* \param *t - The hashtable to destroy and free. */

static inline void NAME_free(hashtable_t *t)

{

_hashtable_free(t);

}

/** Initialize hashtable stats counters.

*

* This will reset all the stats counters for the hashtable,

*

* \param *t - The hashtable to initializ stats for. */

static inline void NAME_stats_init(hashtable_t *t)

{

# ifndef HASHTABLE_NSTATS

t->find_count = t->match_count = t->hashcmp_count = t->entrycmp_count = 0;

# endif

}

/** 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.

*

* \param *t - The hashtable to add to.

*

* \param *e - The entry object to add.

*

* \return The added entry, or NULL if the table is full. */

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

{

unsigned he = _KEY_HASH(e);

assert(e != NULL);

if (t->count + 1 == t->size)

return NULL;

# ifndef HASHTABLE_NBLOOM

hashtable_setbloom(t, he);

# endif

_for_probe(t, he, i, h);

t->count++;

t->ktable[i] = he;

return t->etable[i] = e;

}

/** Find an entry in a hashtable.

*

* Uses MATCH_cmp() to find the first matching entry in the table in the same

* hash() bucket.

*

* \param *t - The hashtable to search.

*

* \param *m - The key or match object to search for.

*

* \return The first found entry, or NULL if nothing was found. */

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

{

assert(m != NULL);

unsigned hm = _KEY_HASH(m);

ENTRY_t *e;

_stats_inc(t->find_count);

# ifndef HASHTABLE_NBLOOM

if (!hashtable_getbloom(t, hm))

return NULL;

# endif

_for_probe(t, hm, i, he) {

_stats_inc(t->hashcmp_count);

if (hm == he) {

_stats_inc(t->entrycmp_count);

if (!MATCH_cmp(m, e = t->etable[i])) {

_stats_inc(t->match_count);

return e;

}

}

}

/* Also count the compare for the empty bucket. */

_stats_inc(t->hashcmp_count);

return NULL;

}

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

/** Initialize a iteration and return the first entry.

*

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

* hashtable.

*

* Example: \code

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

* ...

* \endcode

*

* \param *t - the hashtable to iterate over.

*

* \param *i - the int iterator index to initialize.

*

* \return The first entry or NULL if the hashtable is empty. */

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

{

assert(t != NULL);

assert(i != NULL);

*i = 0;

return NAME_next(t, i);

}

/** 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.

*

* \param *t - the hashtable to iterate over.

*

* \param *i - the int iterator index to use.

*

* \return The next entry or NULL if the iterator is finished. */

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

{

assert(t != NULL);

assert(i != NULL);

ENTRY_t *e = NULL;

while ((*i < t->size) && !(e = t->etable[(*i)++])) ;

return e;

}

# undef ENTRY

# undef KEY

# undef MATCH

# undef NAME

# undef ENTRY_t

# undef KEY_t

# undef MATCH_t

# undef KEY_hash

# undef MATCH_cmp

# undef NAME_new

# undef NAME_free

# undef NAME_stats_init

# undef NAME_add

# undef NAME_find

# undef NAME_iter

# undef NAME_next

# undef _KEY_HASH

#endif /* ENTRY */