ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/vendor/ircservices-5.1.24/hash.h
Revision: 3389
Committed: Fri Apr 25 14:12:15 2014 UTC (9 years, 11 months ago) by michael
Content type: text/x-chdr
File size: 14538 byte(s)
Log Message:
- Imported ircservices-5.1.24

File Contents

# 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 = (hash*31 + __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 */