/* Declarations for hash tables.
*
* IRC Services is copyright (c) 1996-2007 Andrew Church.
* E-mail: <achurch@achurch.org>
* Parts written by Andrew Kempe and others.
* This program is free but copyrighted software; see the file COPYING for
* details.
*/
/* This file allows code to define a simple hash table and associated
* functions using a simple macro. After including this file, hash tables
* can be defined with DEFINE_HASH() or DEFINE_HASH_SCALAR(); the former is
* for string (char *) keys, the latter for scalar (int, etc.) keys. The
* format for these macros is:
* DEFINE_HASH[_SCALAR](name, type, key [, keytype])
* where:
* `name' is the name to be used in the hash table functions,
* `type' is the type of the elements to be stored in the hash table
* (e.g. `struct mystruct' or `MyType'); this must be a
* structured type,
* `key' is the field in `type' containing the key to be used to
* index the element, and
* `keytype' (only for DEFINE_HASH_SCALAR) is the type of `key'.
* By default, hash tables use a hash function which converts the first two
* bytes of `key' to a pair of five-bit values, for total of 1024 slots;
* the conversion is controlled by the `hashlookup' array, defined (static
* const) by this file. If you want a different hash function, redefine
* HASHFUNC and HASHSIZE (see below) before defining the hash table; in
* particular, scalar keys cannot be used with the default hash function,
* and require a different hash function to be defined.
*
* The functions defined by this file are as follows (the strings `<name>',
* `<type>', and `<keytype>' refer to the corresponding parameters given to
* the DEFINE_HASH[_SCALAR] macro):
*
* void add_<name>(<type> *node)
* Adds the given node to the hash table.
*
* void del_<name>(<type> *node)
* Removes the given node from the hash table.
*
* <type> *get_<name>(const char *key) (for string keys)
* <type> *get_<name>(<keytype> key) (for scalar keys)
* If an element with the given key is stored in the hash table,
* returns a pointer to that element; otherwise, returns NULL.
*
* <type> *first_<name>(void)
* <type> *next_<name>(void)
* These functions iterate over all elements in the hash table.
* returning them in lexical order by key. first_<name>()
* initializes the iterator to the lexically first element in the
* hash table and returns it; next_<name>() returns subsequent
* elements, one at a time, until all elements have been returned, at
* which point it returns NULL until first_<name>() is called again.
* If there are no elements in the hash table, first_<name>() will
* return NULL (as will next_<name>()). It is safe to delete
* elements, including the current element, while iterating. If an
* element is added while iterating that is lexically later than the
* current element, it will be returned by next_<name>() when it is
* reached.
*
* This file and the hash tables it generates are controlled by the
* following #define's:
* EXPIRE_CHECK(node): Define to an expression used to check whether a
* given entry has expired. Initially defined to
* `0' (no expiration) if not otherwise defined when
* this file is included.
* HASH_STATIC: Define to either `static' or nothing, to control whether
* hash functions are declared static or not. Defaults to
* nothing (functions are not static). The hash table
* structures themselves are always static.
* HASHFUNC: Define this (and HASHSIZE) if you want your own hash
* function. Defaults to the standard hash function.
* HASH_HAVELOOKUP: Define before including this file if you use the
* standard hash function but separately define a
* `hashlookup' array, or if you don't use the standard
* hash function and don't need the array.
*
* Note that the above defines (except HASH_HAVELOOKUP) take effect when
* hash tables are actually defined, not when this file is included, so the
* defines can be changed at will for different hashes.
*/
#ifndef HASH_H
#define HASH_H
/*************************************************************************/
#ifndef EXPIRE_CHECK
# define EXPIRE_CHECK(node) 0
#endif
#ifndef HASH_STATIC
# define HASH_STATIC /*nothing*/
#endif
/*************************************************************************/
#ifndef HASHFUNC
/* Generic hash function and associated lookup table. */
# define HASHFUNC(key) (hashlookup[(uint8)(*(key))]<<5 \
| (*(key) ? hashlookup[(uint8)((key)[1])] : 0))
# define HASHSIZE 1024
#endif /* !HASHFUNC */
#ifndef HASH_HAVELOOKUP
static const uint8 hashlookup[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29, 0, 0,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,30,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
};
#endif /* !HASH_HAVELOOKUP */
/*************************************************************************/
/* Templates for creating hash table definitions and functions.
* HASH_STATIC should be defined to either `static' or nothing beforehand.
*/
#undef DEFINE_HASHTABLE
#define DEFINE_HASHTABLE(name, type) \
static type *hashtable_##name[HASHSIZE];
#undef DEFINE_HASH_ITER
#define DEFINE_HASH_ITER(name,type) \
static type *hashiter_##name; \
static int hashpos_##name; \
static void _next_##name(void) \
{ \
if (hashiter_##name) \
hashiter_##name = hashiter_##name->next; \
while (hashiter_##name == NULL && ++hashpos_##name < HASHSIZE) \
hashiter_##name = hashtable_##name[hashpos_##name]; \
} \
HASH_STATIC type *next_##name(void) \
{ \
type *retval; \
do { \
retval = hashiter_##name; \
if (retval == NULL) \
return NULL; \
_next_##name(); \
} while (!noexpire && EXPIRE_CHECK(retval)); \
return retval; \
} \
HASH_STATIC type *first_##name(void) \
{ \
hashpos_##name = -1; \
hashiter_##name = NULL; \
_next_##name(); \
return next_##name(); \
}
#undef DEFINE_HASH_ADD
#define DEFINE_HASH_ADD(name,type,key) \
HASH_STATIC void add_##name(type *node) \
{ \
type **listptr = &hashtable_##name[HASHFUNC(node->key)]; \
LIST_INSERT_ORDERED(node, *listptr, irc_stricmp, key); \
}
#undef DEFINE_HASH_ADD_SCALAR
#define DEFINE_HASH_ADD_SCALAR(name,type,key) \
HASH_STATIC void add_##name(type *node) \
{ \
type **listptr = &hashtable_##name[HASHFUNC(node->key)]; \
LIST_INSERT(node, *listptr); \
}
#undef DEFINE_HASH_DEL
#define DEFINE_HASH_DEL(name,type,key) \
HASH_STATIC void del_##name(type *node) \
{ \
if (node == hashiter_##name) \
_next_##name(); \
LIST_REMOVE(node, hashtable_##name[HASHFUNC(node->key)]); \
}
#undef DEFINE_HASH_GET
#define DEFINE_HASH_GET(name,type,key) \
HASH_STATIC type *get_##name(const char *what) \
{ \
type *result; \
LIST_SEARCH_ORDERED(hashtable_##name[HASHFUNC(what)], \
key, what, irc_stricmp, result); \
if (result && !noexpire && EXPIRE_CHECK(result)) \
result = NULL; \
return result; \
}
#undef DEFINE_HASH_GET_SCALAR
#define DEFINE_HASH_GET_SCALAR(name,type,key,keytype) \
HASH_STATIC type *get_##name(keytype what) \
{ \
type *result; \
LIST_SEARCH_SCALAR(hashtable_##name[HASHFUNC(what)], \
key, what, result); \
if (result && !noexpire && EXPIRE_CHECK(result)) \
result = NULL; \
return result; \
}
/* Macros to create everything at once for a given type.
* name: Name to use in the hash functions (the XXX in add_XXX, etc.)
* type: Type of the hash (NickInfo, etc.)
* key: Key field in given type
*/
#undef DEFINE_HASH
#define DEFINE_HASH(name,type,key) \
DEFINE_HASHTABLE(name, type) \
DEFINE_HASH_ITER(name, type) \
DEFINE_HASH_ADD(name, type, key) \
DEFINE_HASH_DEL(name, type, key) \
DEFINE_HASH_GET(name, type, key)
#undef DEFINE_HASH_SCALAR
#define DEFINE_HASH_SCALAR(name,type,key,keytype) \
DEFINE_HASHTABLE(name, type) \
DEFINE_HASH_ITER(name, type) \
DEFINE_HASH_ADD_SCALAR(name, type, key) \
DEFINE_HASH_DEL(name, type, key) \
DEFINE_HASH_GET_SCALAR(name, type, key, keytype)
/*************************************************************************/
#endif /* HASH_H */
syntax highlighted by Code2HTML, v. 0.9.1