viewcvs.cgi/hybrid-ircservices-1/hash.h

/* Declarations for hash tables.
 *
 * IRC Services is copyright (c) 1996-2009 Andrew Church.
 *     E-mail: <achurch@achurch.org>
 * Parts written by Andrew Kempe and others.
 * This program is free but copyrighted software; see the file GPL.txt 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, keyfield [, 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,
 *    `keyfield' 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 `keyfield'.
 *
 * The default hash function:
 *    - if HASH_SORTED is defined to a nonzero value, converts the first
 *      two bytes of the value of `keyfield' to a pair of five-bit values,
 *      for a total of 1024 slots, with the conversion controlled by the
 *      `hashlookup' array (defined static const by this file);
 *    - if HASH_SORTED is not defined or is defined to 0, treats `keyfield'
 *      as a string and generates a hash key from the entire string,
 *      hashing into a table of 65537 slots.
 * 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.
 *       For hashes with string keys, elements are returned in lexical
 *       order by key if HASH_SORTED is defined (see below).
 *       first_<name>() initializes the iterator to the 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, it is undefined whether that
 *       element will be returned by next_<name>() before the end of the
 *       hash table 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 these if you want your own hash function.  Defaults
 *    HASHSIZE: to the standard hash function.  If you redefine these once,
 *              you can restore them to the defaults by defining them to
 *              DEFAULT_HASHFUNC(key) and DEFAULT_HASHSIZE.
 *    HASH_SORTED: Define (to a nonzero value) or undefine _before_
 *                 including this file_ to select the type of default hash
 *                 function (see above).
 *
 * Note that the above defines (except HASH_SORTED) 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

/*************************************************************************/

/* Generic hash function and associated lookup table. */

#if HASH_SORTED

# define DEFAULT_HASHFUNC(key) \
    (__hashlookup[(uint8)(*(key))]<<5 \
     | (*(key) ? __hashlookup[(uint8)((key)[1])] : 0))
# define DEFAULT_HASHSIZE 1024
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,
};

#else  /* !HASH_SORTED */

# define DEFAULT_HASHFUNC(key) (__default_hashfunc(key))
# define DEFAULT_HASHSIZE 65537
static const uint8 __hashlookup_unsorted[256] = {
    0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
    0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
    0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
    0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
    0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
    0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
    0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
    0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,

    0x40,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
    0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
    0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
    0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x5E,0x5F,
    0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
    0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
    0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
    0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,

    0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
    0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
    0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,
    0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
    0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,
    0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
    0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,
    0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,

    0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,
    0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
    0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,
    0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
    0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,
    0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
    0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,
    0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF,
};
static inline int __default_hashfunc(const char *key_) {
    const uint8 *key = (const uint8 *)key_;
    int hash = 0;
    while (*key) {
        hash = (hash*31 + __hashlookup_unsorted[*key]) % DEFAULT_HASHSIZE;
        key++;
    }
    return hash;
}

#endif  /* HASH_SORTED */


#ifndef HASHFUNC
# define HASHFUNC(key) DEFAULT_HASHFUNC(key)
#endif

#ifndef HASHSIZE
# define HASHSIZE DEFAULT_HASHSIZE
#endif

/*************************************************************************/

/* 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 int hashpos_##name;                                          \
    static type *hashiter_##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,keyfield)                             \
    HASH_STATIC void add_##name(type *node)                             \
    {                                                                   \
        type **listptr = &hashtable_##name[HASHFUNC(node->keyfield)];   \
        LIST_INSERT_ORDERED(node, *listptr, irc_stricmp, keyfield);     \
    }

#undef DEFINE_HASH_ADD_SCALAR
#define DEFINE_HASH_ADD_SCALAR(name,type,keyfield)                      \
    HASH_STATIC void add_##name(type *node)                             \
    {                                                                   \
        type **listptr = &hashtable_##name[HASHFUNC(node->keyfield)];   \
        LIST_INSERT(node, *listptr);                                    \
    }

#undef DEFINE_HASH_DEL
#define DEFINE_HASH_DEL(name,type,keyfield)                             \
    HASH_STATIC void del_##name(type *node)                             \
    {                                                                   \
        if (node == hashiter_##name)                                    \
            _next_##name();                                             \
        LIST_REMOVE(node, hashtable_##name[HASHFUNC(node->keyfield)]);  \
    }

#undef DEFINE_HASH_GET
#define DEFINE_HASH_GET(name,type,keyfield)                             \
    HASH_STATIC type *get_##name(const char *what)                      \
    {                                                                   \
        type *result;                                                   \
        LIST_SEARCH_ORDERED(hashtable_##name[HASHFUNC(what)],           \
                            keyfield, 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,keyfield,keytype)              \
    HASH_STATIC type *get_##name(keytype what)                          \
    {                                                                   \
        type *result;                                                   \
        LIST_SEARCH_SCALAR(hashtable_##name[HASHFUNC(what)],            \
                           keyfield, 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.)
 *      keyfield: Key field in given type
 */

#undef DEFINE_HASH
#define DEFINE_HASH(name,type,keyfield)                 \
    DEFINE_HASHTABLE(name, type)                        \
    DEFINE_HASH_ITER(name, type)                        \
    DEFINE_HASH_ADD(name, type, keyfield)               \
    DEFINE_HASH_DEL(name, type, keyfield)               \
    DEFINE_HASH_GET(name, type, keyfield)

#undef DEFINE_HASH_SCALAR
#define DEFINE_HASH_SCALAR(name,type,keyfield,keytype)  \
    DEFINE_HASHTABLE(name, type)                        \
    DEFINE_HASH_ITER(name, type)                        \
    DEFINE_HASH_ADD_SCALAR(name, type, keyfield)        \
    DEFINE_HASH_DEL(name, type, keyfield)               \
    DEFINE_HASH_GET_SCALAR(name, type, keyfield, keytype)

/*************************************************************************/

#endif  /* HASH_H */

/*
 * Local variables:
 *   c-file-style: "stroustrup"
 *   c-file-offsets: ((case-label . *) (statement-case-intro . *))
 *   indent-tabs-mode: nil
 * End:
 *
 * vim: expandtab shiftwidth=4:
 */
Revision:	1201
Committed:	Mon Aug 22 18:55:33 2011 UTC (15 years, 1 month ago) by michael
Content type:	text/x-chdr
File size:	14538 byte(s)
Error occurred while calculating annotation data.
Log Message:	- I decided to make the services 'hybrid only'. That said, I'm not going to continue the ircservices project in an official manner, since maintaining compatibility for a wide range of ircds would require an enormous amount of effort.
#	Content
1	/* Declarations for hash tables.
2	*
3	* IRC Services is copyright (c) 1996-2009 Andrew Church.
4	* E-mail: <achurch@achurch.org>
5	* Parts written by Andrew Kempe and others.
6	* This program is free but copyrighted software; see the file GPL.txt for
7	* details.
8	*/
9
10	/* This file allows code to define a simple hash table and associated
11	* functions using a simple macro. After including this file, hash tables
12	* can be defined with DEFINE_HASH() or DEFINE_HASH_SCALAR(); the former is
13	* for string (char *) keys, the latter for scalar (int, etc.) keys. The
14	* format for these macros is:
15	* DEFINE_HASH[_SCALAR](name, type, keyfield [, keytype])
16	* where:
17	* `name' is the name to be used in the hash table functions,
18	* `type' is the type of the elements to be stored in the hash table
19	* (e.g. `struct mystruct' or `MyType'); this must be a
20	* structured type,
21	* `keyfield' is the field in `type' containing the key to be used to
22	* index the element, and
23	* `keytype' (only for DEFINE_HASH_SCALAR) is the type of `keyfield'.
24	*
25	* The default hash function:
26	* - if HASH_SORTED is defined to a nonzero value, converts the first
27	* two bytes of the value of `keyfield' to a pair of five-bit values,
28	* for a total of 1024 slots, with the conversion controlled by the
29	* `hashlookup' array (defined static const by this file);
30	* - if HASH_SORTED is not defined or is defined to 0, treats `keyfield'
31	* as a string and generates a hash key from the entire string,
32	* hashing into a table of 65537 slots.
33	* If you want a different hash function, redefine HASHFUNC and HASHSIZE
34	* (see below) before defining the hash table; in particular, scalar keys
35	* cannot be used with the default hash function, and require a different
36	* hash function to be defined.
37	*
38	* The functions defined by this file are as follows (the strings `<name>',
39	* `<type>', and `<keytype>' refer to the corresponding parameters given to
40	* the DEFINE_HASH[_SCALAR] macro):
41	*
42	* void add_<name>(<type> *node)
43	* Adds the given node to the hash table.
44	*
45	* void del_<name>(<type> *node)
46	* Removes the given node from the hash table.
47	*
48	* <type> get_<name>(const char key) (for string keys)
49	* <type> *get_<name>(<keytype> key) (for scalar keys)
50	* If an element with the given key is stored in the hash table,
51	* returns a pointer to that element; otherwise, returns NULL.
52	*
53	* <type> *first_<name>(void)
54	* <type> *next_<name>(void)
55	* These functions iterate over all elements in the hash table.
56	* For hashes with string keys, elements are returned in lexical
57	* order by key if HASH_SORTED is defined (see below).
58	* first_<name>() initializes the iterator to the first element in
59	* the hash table and returns it; next_<name>() returns subsequent
60	* elements, one at a time, until all elements have been returned, at
61	* which point it returns NULL until first_<name>() is called again.
62	* If there are no elements in the hash table, first_<name>() will
63	* return NULL (as will next_<name>()). It is safe to delete
64	* elements, including the current element, while iterating. If an
65	* element is added while iterating, it is undefined whether that
66	* element will be returned by next_<name>() before the end of the
67	* hash table is reached.
68	*
69	* This file and the hash tables it generates are controlled by the
70	* following #define's:
71	* EXPIRE_CHECK(node): Define to an expression used to check whether a
72	* given entry has expired. Initially defined to
73	* `0' (no expiration) if not otherwise defined when
74	* this file is included.
75	* HASH_STATIC: Define to either `static' or nothing, to control whether
76	* hash functions are declared static or not. Defaults to
77	* nothing (functions are not static). The hash table
78	* structures themselves are always static.
79	* HASHFUNC/ Define these if you want your own hash function. Defaults
80	* HASHSIZE: to the standard hash function. If you redefine these once,
81	* you can restore them to the defaults by defining them to
82	* DEFAULT_HASHFUNC(key) and DEFAULT_HASHSIZE.
83	* HASH_SORTED: Define (to a nonzero value) or undefine _before_
84	* including this file_ to select the type of default hash
85	* function (see above).
86	*
87	* Note that the above defines (except HASH_SORTED) take effect when hash
88	* tables are actually defined, not when this file is included, so the
89	* defines can be changed at will for different hashes.
90	*/
91
92	#ifndef HASH_H
93	#define HASH_H
94
95	/*************************************************************************/
96
97	#ifndef EXPIRE_CHECK
98	# define EXPIRE_CHECK(node) 0
99	#endif
100
101	#ifndef HASH_STATIC
102	# define HASH_STATIC /nothing/
103	#endif
104
105	/*************************************************************************/
106
107	/* Generic hash function and associated lookup table. */
108
109	#if HASH_SORTED
110
111	# define DEFAULT_HASHFUNC(key) \
112	(__hashlookup[(uint8)(*(key))]<<5 \
113	\| (*(key) ? __hashlookup[(uint8)((key)[1])] : 0))
114	# define DEFAULT_HASHSIZE 1024
115	static const uint8 __hashlookup[256] = {
116	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
117	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
118	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
119	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
120
121	0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,
122	16,17,18,19,20,21,22,23,24,25,26,27,28,29, 0, 0,
123	0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,
124	16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,30,
125
126	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
127	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
128	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
129	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
130
131	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
132	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
133	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
134	31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,
135	};
136
137	#else /* !HASH_SORTED */
138
139	# define DEFAULT_HASHFUNC(key) (__default_hashfunc(key))
140	# define DEFAULT_HASHSIZE 65537
141	static const uint8 __hashlookup_unsorted[256] = {
142	0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
143	0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
144	0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
145	0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
146	0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
147	0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
148	0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
149	0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
150
151	0x40,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
152	0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
153	0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
154	0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x5E,0x5F,
155	0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
156	0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
157	0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
158	0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
159
160	0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
161	0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
162	0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,
163	0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
164	0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,
165	0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
166	0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,
167	0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
168
169	0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,
170	0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
171	0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,
172	0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
173	0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,
174	0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
175	0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,
176	0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF,
177	};
178	static inline int __default_hashfunc(const char *key_) {
179	const uint8 key = (const uint8 )key_;
180	int hash = 0;
181	while (*key) {
182	hash = (hash31 + __hashlookup_unsorted[key]) % DEFAULT_HASHSIZE;
183	key++;
184	}
185	return hash;
186	}
187
188	#endif /* HASH_SORTED */
189
190
191	#ifndef HASHFUNC
192	# define HASHFUNC(key) DEFAULT_HASHFUNC(key)
193	#endif
194
195	#ifndef HASHSIZE
196	# define HASHSIZE DEFAULT_HASHSIZE
197	#endif
198
199	/*************************************************************************/
200
201	/* Templates for creating hash table definitions and functions.
202	* HASH_STATIC should be defined to either `static' or nothing beforehand.
203	*/
204
205	#undef DEFINE_HASHTABLE
206	#define DEFINE_HASHTABLE(name, type) \
207	static type *hashtable_##name[HASHSIZE];
208
209	#undef DEFINE_HASH_ITER
210	#define DEFINE_HASH_ITER(name,type) \
211	static int hashpos_##name; \
212	static type *hashiter_##name; \
213	static void _next_##name(void) \
214	{ \
215	if (hashiter_##name) \
216	hashiter_##name = hashiter_##name->next; \
217	while (hashiter_##name == NULL && ++hashpos_##name < HASHSIZE) \
218	hashiter_##name = hashtable_##name[hashpos_##name]; \
219	} \
220	HASH_STATIC type *next_##name(void) \
221	{ \
222	type *retval; \
223	do { \
224	retval = hashiter_##name; \
225	if (retval == NULL) \
226	return NULL; \
227	_next_##name(); \
228	} while (!noexpire && EXPIRE_CHECK(retval)); \
229	return retval; \
230	} \
231	HASH_STATIC type *first_##name(void) \
232	{ \
233	hashpos_##name = -1; \
234	hashiter_##name = NULL; \
235	_next_##name(); \
236	return next_##name(); \
237	}
238
239	#undef DEFINE_HASH_ADD
240	#define DEFINE_HASH_ADD(name,type,keyfield) \
241	HASH_STATIC void add_##name(type *node) \
242	{ \
243	type **listptr = &hashtable_##name[HASHFUNC(node->keyfield)]; \
244	LIST_INSERT_ORDERED(node, *listptr, irc_stricmp, keyfield); \
245	}
246
247	#undef DEFINE_HASH_ADD_SCALAR
248	#define DEFINE_HASH_ADD_SCALAR(name,type,keyfield) \
249	HASH_STATIC void add_##name(type *node) \
250	{ \
251	type **listptr = &hashtable_##name[HASHFUNC(node->keyfield)]; \
252	LIST_INSERT(node, *listptr); \
253	}
254
255	#undef DEFINE_HASH_DEL
256	#define DEFINE_HASH_DEL(name,type,keyfield) \
257	HASH_STATIC void del_##name(type *node) \
258	{ \
259	if (node == hashiter_##name) \
260	_next_##name(); \
261	LIST_REMOVE(node, hashtable_##name[HASHFUNC(node->keyfield)]); \
262	}
263
264	#undef DEFINE_HASH_GET
265	#define DEFINE_HASH_GET(name,type,keyfield) \
266	HASH_STATIC type get_##name(const char what) \
267	{ \
268	type *result; \
269	LIST_SEARCH_ORDERED(hashtable_##name[HASHFUNC(what)], \
270	keyfield, what, irc_stricmp, result); \
271	if (result && !noexpire && EXPIRE_CHECK(result)) \
272	result = NULL; \
273	return result; \
274	}
275
276	#undef DEFINE_HASH_GET_SCALAR
277	#define DEFINE_HASH_GET_SCALAR(name,type,keyfield,keytype) \
278	HASH_STATIC type *get_##name(keytype what) \
279	{ \
280	type *result; \
281	LIST_SEARCH_SCALAR(hashtable_##name[HASHFUNC(what)], \
282	keyfield, what, result); \
283	if (result && !noexpire && EXPIRE_CHECK(result)) \
284	result = NULL; \
285	return result; \
286	}
287
288	/* Macros to create everything at once for a given type.
289	* name: Name to use in the hash functions (the XXX in add_XXX, etc.)
290	* type: Type of the hash (NickInfo, etc.)
291	* keyfield: Key field in given type
292	*/
293
294	#undef DEFINE_HASH
295	#define DEFINE_HASH(name,type,keyfield) \
296	DEFINE_HASHTABLE(name, type) \
297	DEFINE_HASH_ITER(name, type) \
298	DEFINE_HASH_ADD(name, type, keyfield) \
299	DEFINE_HASH_DEL(name, type, keyfield) \
300	DEFINE_HASH_GET(name, type, keyfield)
301
302	#undef DEFINE_HASH_SCALAR
303	#define DEFINE_HASH_SCALAR(name,type,keyfield,keytype) \
304	DEFINE_HASHTABLE(name, type) \
305	DEFINE_HASH_ITER(name, type) \
306	DEFINE_HASH_ADD_SCALAR(name, type, keyfield) \
307	DEFINE_HASH_DEL(name, type, keyfield) \
308	DEFINE_HASH_GET_SCALAR(name, type, keyfield, keytype)
309
310	/*************************************************************************/
311
312	#endif /* HASH_H */
313
314	/*
315	* Local variables:
316	* c-file-style: "stroustrup"
317	* c-file-offsets: ((case-label . ) (statement-case-intro . ))
318	* indent-tabs-mode: nil
319	* End:
320	*
321	* vim: expandtab shiftwidth=4:
322	*/