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