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