/src/lldpd/libevent/ht-internal.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright 2002 Christopher Clark */ |
2 | | /* Copyright 2005-2012 Nick Mathewson */ |
3 | | /* Copyright 2009-2012 Niels Provos and Nick Mathewson */ |
4 | | /* See license at end. */ |
5 | | |
6 | | /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ |
7 | | |
8 | | #ifndef HT_INTERNAL_H_INCLUDED_ |
9 | | #define HT_INTERNAL_H_INCLUDED_ |
10 | | |
11 | | #define HT_HEAD(name, type) \ |
12 | | struct name { \ |
13 | | /* The hash table itself. */ \ |
14 | | struct type **hth_table; \ |
15 | | /* How long is the hash table? */ \ |
16 | | unsigned hth_table_length; \ |
17 | | /* How many elements does the table contain? */ \ |
18 | | unsigned hth_n_entries; \ |
19 | | /* How many elements will we allow in the table before resizing it? */ \ |
20 | | unsigned hth_load_limit; \ |
21 | | /* Position of hth_table_length in the primes table. */ \ |
22 | | int hth_prime_idx; \ |
23 | | } |
24 | | |
25 | | #define HT_INITIALIZER() \ |
26 | | { NULL, 0, 0, 0, -1 } |
27 | | |
28 | | #ifdef HT_NO_CACHE_HASH_VALUES |
29 | | #define HT_ENTRY(type) \ |
30 | | struct { \ |
31 | | struct type *hte_next; \ |
32 | | } |
33 | | #else |
34 | | #define HT_ENTRY(type) \ |
35 | | struct { \ |
36 | | struct type *hte_next; \ |
37 | | unsigned hte_hash; \ |
38 | | } |
39 | | #endif |
40 | | |
41 | | #define HT_EMPTY(head) \ |
42 | | ((head)->hth_n_entries == 0) |
43 | | |
44 | | /* How many elements in 'head'? */ |
45 | | #define HT_SIZE(head) \ |
46 | | ((head)->hth_n_entries) |
47 | | |
48 | | /* Return memory usage for a hashtable (not counting the entries themselves) */ |
49 | | #define HT_MEM_USAGE(head) \ |
50 | | (sizeof(*head) + (head)->hth_table_length * sizeof(void*)) |
51 | | |
52 | | #define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) |
53 | | #define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) |
54 | | #define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) |
55 | | #define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) |
56 | | #define HT_START(name, head) name##_HT_START(head) |
57 | | #define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) |
58 | | #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) |
59 | | #define HT_CLEAR(name, head) name##_HT_CLEAR(head) |
60 | | #define HT_INIT(name, head) name##_HT_INIT(head) |
61 | | /* Helper: */ |
62 | | static inline unsigned |
63 | | ht_improve_hash_(unsigned h) |
64 | 0 | { |
65 | 0 | /* Aim to protect against poor hash functions by adding logic here |
66 | 0 | * - logic taken from java 1.4 hashtable source */ |
67 | 0 | h += ~(h << 9); |
68 | 0 | h ^= ((h >> 14) | (h << 18)); /* >>> */ |
69 | 0 | h += (h << 4); |
70 | 0 | h ^= ((h >> 10) | (h << 22)); /* >>> */ |
71 | 0 | return h; |
72 | 0 | } |
73 | | |
74 | | #if 0 |
75 | | /** Basic string hash function, from Java standard String.hashCode(). */ |
76 | | static inline unsigned |
77 | | ht_string_hash_(const char *s) |
78 | | { |
79 | | unsigned h = 0; |
80 | | int m = 1; |
81 | | while (*s) { |
82 | | h += ((signed char)*s++)*m; |
83 | | m = (m<<5)-1; /* m *= 31 */ |
84 | | } |
85 | | return h; |
86 | | } |
87 | | #endif |
88 | | |
89 | | /** Basic string hash function, from Python's str.__hash__() */ |
90 | | static inline unsigned |
91 | | ht_string_hash_(const char *s) |
92 | 0 | { |
93 | 0 | unsigned h; |
94 | 0 | const unsigned char *cp = (const unsigned char *)s; |
95 | 0 | h = *cp << 7; |
96 | 0 | while (*cp) { |
97 | 0 | h = (1000003*h) ^ *cp++; |
98 | 0 | } |
99 | 0 | /* This conversion truncates the length of the string, but that's ok. */ |
100 | 0 | h ^= (unsigned)(cp-(const unsigned char*)s); |
101 | 0 | return h; |
102 | 0 | } |
103 | | |
104 | | #ifndef HT_NO_CACHE_HASH_VALUES |
105 | | #define HT_SET_HASH_(elm, field, hashfn) \ |
106 | | do { (elm)->field.hte_hash = hashfn(elm); } while (0) |
107 | | #define HT_SET_HASHVAL_(elm, field, val) \ |
108 | | do { (elm)->field.hte_hash = (val); } while (0) |
109 | | #define HT_ELT_HASH_(elm, field, hashfn) \ |
110 | | ((elm)->field.hte_hash) |
111 | | #else |
112 | | #define HT_SET_HASH_(elm, field, hashfn) \ |
113 | | ((void)0) |
114 | | #define HT_ELT_HASH_(elm, field, hashfn) \ |
115 | | (hashfn(elm)) |
116 | | #define HT_SET_HASHVAL_(elm, field, val) \ |
117 | | ((void)0) |
118 | | #endif |
119 | | |
120 | | /* Helper: alias for the bucket containing 'elm'. */ |
121 | | #define HT_BUCKET_(head, field, elm, hashfn) \ |
122 | | ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length]) |
123 | | |
124 | | #define HT_FOREACH(x, name, head) \ |
125 | | for ((x) = HT_START(name, head); \ |
126 | | (x) != NULL; \ |
127 | | (x) = HT_NEXT(name, head, x)) |
128 | | |
129 | | #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ |
130 | | int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ |
131 | | void name##_HT_CLEAR(struct name *ht); \ |
132 | | int name##_HT_REP_IS_BAD_(const struct name *ht); \ |
133 | | static inline void \ |
134 | | name##_HT_INIT(struct name *head) { \ |
135 | | head->hth_table_length = 0; \ |
136 | | head->hth_table = NULL; \ |
137 | | head->hth_n_entries = 0; \ |
138 | | head->hth_load_limit = 0; \ |
139 | | head->hth_prime_idx = -1; \ |
140 | | } \ |
141 | | /* Helper: returns a pointer to the right location in the table \ |
142 | | * 'head' to find or insert the element 'elm'. */ \ |
143 | | static inline struct type ** \ |
144 | | name##_HT_FIND_P_(struct name *head, struct type *elm) \ |
145 | | { \ |
146 | | struct type **p; \ |
147 | | if (!head->hth_table) \ |
148 | | return NULL; \ |
149 | | p = &HT_BUCKET_(head, field, elm, hashfn); \ |
150 | | while (*p) { \ |
151 | | if (eqfn(*p, elm)) \ |
152 | | return p; \ |
153 | | p = &(*p)->field.hte_next; \ |
154 | | } \ |
155 | | return p; \ |
156 | | } \ |
157 | | /* Return a pointer to the element in the table 'head' matching 'elm', \ |
158 | | * or NULL if no such element exists */ \ |
159 | | static inline struct type * \ |
160 | | name##_HT_FIND(const struct name *head, struct type *elm) \ |
161 | | { \ |
162 | | struct type **p; \ |
163 | | struct name *h = (struct name *) head; \ |
164 | | HT_SET_HASH_(elm, field, hashfn); \ |
165 | | p = name##_HT_FIND_P_(h, elm); \ |
166 | | return p ? *p : NULL; \ |
167 | | } \ |
168 | | /* Insert the element 'elm' into the table 'head'. Do not call this \ |
169 | | * function if the table might already contain a matching element. */ \ |
170 | | static inline void \ |
171 | | name##_HT_INSERT(struct name *head, struct type *elm) \ |
172 | | { \ |
173 | | struct type **p; \ |
174 | | if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ |
175 | | name##_HT_GROW(head, head->hth_n_entries+1); \ |
176 | | ++head->hth_n_entries; \ |
177 | | HT_SET_HASH_(elm, field, hashfn); \ |
178 | | p = &HT_BUCKET_(head, field, elm, hashfn); \ |
179 | | elm->field.hte_next = *p; \ |
180 | | *p = elm; \ |
181 | | } \ |
182 | | /* Insert the element 'elm' into the table 'head'. If there already \ |
183 | | * a matching element in the table, replace that element and return \ |
184 | | * it. */ \ |
185 | | static inline struct type * \ |
186 | | name##_HT_REPLACE(struct name *head, struct type *elm) \ |
187 | | { \ |
188 | | struct type **p, *r; \ |
189 | | if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ |
190 | | name##_HT_GROW(head, head->hth_n_entries+1); \ |
191 | | HT_SET_HASH_(elm, field, hashfn); \ |
192 | | p = name##_HT_FIND_P_(head, elm); \ |
193 | | r = *p; \ |
194 | | *p = elm; \ |
195 | | if (r && (r!=elm)) { \ |
196 | | elm->field.hte_next = r->field.hte_next; \ |
197 | | r->field.hte_next = NULL; \ |
198 | | return r; \ |
199 | | } else { \ |
200 | | ++head->hth_n_entries; \ |
201 | | return NULL; \ |
202 | | } \ |
203 | | } \ |
204 | | /* Remove any element matching 'elm' from the table 'head'. If such \ |
205 | | * an element is found, return it; otherwise return NULL. */ \ |
206 | | static inline struct type * \ |
207 | | name##_HT_REMOVE(struct name *head, struct type *elm) \ |
208 | | { \ |
209 | | struct type **p, *r; \ |
210 | | HT_SET_HASH_(elm, field, hashfn); \ |
211 | | p = name##_HT_FIND_P_(head,elm); \ |
212 | | if (!p || !*p) \ |
213 | | return NULL; \ |
214 | | r = *p; \ |
215 | | *p = r->field.hte_next; \ |
216 | | r->field.hte_next = NULL; \ |
217 | | --head->hth_n_entries; \ |
218 | | return r; \ |
219 | | } \ |
220 | | /* Invoke the function 'fn' on every element of the table 'head', \ |
221 | | * using 'data' as its second argument. If the function returns \ |
222 | | * nonzero, remove the most recently examined element before invoking \ |
223 | | * the function again. */ \ |
224 | | static inline void \ |
225 | | name##_HT_FOREACH_FN(struct name *head, \ |
226 | | int (*fn)(struct type *, void *), \ |
227 | | void *data) \ |
228 | | { \ |
229 | | unsigned idx; \ |
230 | | struct type **p, **nextp, *next; \ |
231 | | if (!head->hth_table) \ |
232 | | return; \ |
233 | | for (idx=0; idx < head->hth_table_length; ++idx) { \ |
234 | | p = &head->hth_table[idx]; \ |
235 | | while (*p) { \ |
236 | | nextp = &(*p)->field.hte_next; \ |
237 | | next = *nextp; \ |
238 | | if (fn(*p, data)) { \ |
239 | | --head->hth_n_entries; \ |
240 | | *p = next; \ |
241 | | } else { \ |
242 | | p = nextp; \ |
243 | | } \ |
244 | | } \ |
245 | | } \ |
246 | | } \ |
247 | | /* Return a pointer to the first element in the table 'head', under \ |
248 | | * an arbitrary order. This order is stable under remove operations, \ |
249 | | * but not under others. If the table is empty, return NULL. */ \ |
250 | | static inline struct type ** \ |
251 | | name##_HT_START(struct name *head) \ |
252 | | { \ |
253 | | unsigned b = 0; \ |
254 | | while (b < head->hth_table_length) { \ |
255 | | if (head->hth_table[b]) \ |
256 | | return &head->hth_table[b]; \ |
257 | | ++b; \ |
258 | | } \ |
259 | | return NULL; \ |
260 | | } \ |
261 | | /* Return the next element in 'head' after 'elm', under the arbitrary \ |
262 | | * order used by HT_START. If there are no more elements, return \ |
263 | | * NULL. If 'elm' is to be removed from the table, you must call \ |
264 | | * this function for the next value before you remove it. \ |
265 | | */ \ |
266 | | static inline struct type ** \ |
267 | | name##_HT_NEXT(struct name *head, struct type **elm) \ |
268 | | { \ |
269 | | if ((*elm)->field.hte_next) { \ |
270 | | return &(*elm)->field.hte_next; \ |
271 | | } else { \ |
272 | | unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1; \ |
273 | | while (b < head->hth_table_length) { \ |
274 | | if (head->hth_table[b]) \ |
275 | | return &head->hth_table[b]; \ |
276 | | ++b; \ |
277 | | } \ |
278 | | return NULL; \ |
279 | | } \ |
280 | | } \ |
281 | | static inline struct type ** \ |
282 | | name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ |
283 | | { \ |
284 | | unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \ |
285 | | *elm = (*elm)->field.hte_next; \ |
286 | | --head->hth_n_entries; \ |
287 | | if (*elm) { \ |
288 | | return elm; \ |
289 | | } else { \ |
290 | | unsigned b = (h % head->hth_table_length)+1; \ |
291 | | while (b < head->hth_table_length) { \ |
292 | | if (head->hth_table[b]) \ |
293 | | return &head->hth_table[b]; \ |
294 | | ++b; \ |
295 | | } \ |
296 | | return NULL; \ |
297 | | } \ |
298 | | } |
299 | | |
300 | | #define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ |
301 | | reallocfn, freefn) \ |
302 | | static unsigned name##_PRIMES[] = { \ |
303 | | 53, 97, 193, 389, \ |
304 | | 769, 1543, 3079, 6151, \ |
305 | | 12289, 24593, 49157, 98317, \ |
306 | | 196613, 393241, 786433, 1572869, \ |
307 | | 3145739, 6291469, 12582917, 25165843, \ |
308 | | 50331653, 100663319, 201326611, 402653189, \ |
309 | | 805306457, 1610612741 \ |
310 | | }; \ |
311 | | static unsigned name##_N_PRIMES = \ |
312 | | (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \ |
313 | | /* Expand the internal table of 'head' until it is large enough to \ |
314 | | * hold 'size' elements. Return 0 on success, -1 on allocation \ |
315 | | * failure. */ \ |
316 | | int \ |
317 | | name##_HT_GROW(struct name *head, unsigned size) \ |
318 | | { \ |
319 | | unsigned new_len, new_load_limit; \ |
320 | | int prime_idx; \ |
321 | | struct type **new_table; \ |
322 | | if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \ |
323 | | return 0; \ |
324 | | if (head->hth_load_limit > size) \ |
325 | | return 0; \ |
326 | | prime_idx = head->hth_prime_idx; \ |
327 | | do { \ |
328 | | new_len = name##_PRIMES[++prime_idx]; \ |
329 | | new_load_limit = (unsigned)(load*new_len); \ |
330 | | } while (new_load_limit <= size && \ |
331 | | prime_idx < (int)name##_N_PRIMES); \ |
332 | | if ((new_table = mallocfn(new_len*sizeof(struct type*)))) { \ |
333 | | unsigned b; \ |
334 | | memset(new_table, 0, new_len*sizeof(struct type*)); \ |
335 | | for (b = 0; b < head->hth_table_length; ++b) { \ |
336 | | struct type *elm, *next; \ |
337 | | unsigned b2; \ |
338 | | elm = head->hth_table[b]; \ |
339 | | while (elm) { \ |
340 | | next = elm->field.hte_next; \ |
341 | | b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len; \ |
342 | | elm->field.hte_next = new_table[b2]; \ |
343 | | new_table[b2] = elm; \ |
344 | | elm = next; \ |
345 | | } \ |
346 | | } \ |
347 | | if (head->hth_table) \ |
348 | | freefn(head->hth_table); \ |
349 | | head->hth_table = new_table; \ |
350 | | } else { \ |
351 | | unsigned b, b2; \ |
352 | | new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \ |
353 | | if (!new_table) return -1; \ |
354 | | memset(new_table + head->hth_table_length, 0, \ |
355 | | (new_len - head->hth_table_length)*sizeof(struct type*)); \ |
356 | | for (b=0; b < head->hth_table_length; ++b) { \ |
357 | | struct type *e, **pE; \ |
358 | | for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \ |
359 | | b2 = HT_ELT_HASH_(e, field, hashfn) % new_len; \ |
360 | | if (b2 == b) { \ |
361 | | pE = &e->field.hte_next; \ |
362 | | } else { \ |
363 | | *pE = e->field.hte_next; \ |
364 | | e->field.hte_next = new_table[b2]; \ |
365 | | new_table[b2] = e; \ |
366 | | } \ |
367 | | } \ |
368 | | } \ |
369 | | head->hth_table = new_table; \ |
370 | | } \ |
371 | | head->hth_table_length = new_len; \ |
372 | | head->hth_prime_idx = prime_idx; \ |
373 | | head->hth_load_limit = new_load_limit; \ |
374 | | return 0; \ |
375 | | } \ |
376 | | /* Free all storage held by 'head'. Does not free 'head' itself, or \ |
377 | | * individual elements. */ \ |
378 | | void \ |
379 | | name##_HT_CLEAR(struct name *head) \ |
380 | | { \ |
381 | | if (head->hth_table) \ |
382 | | freefn(head->hth_table); \ |
383 | | name##_HT_INIT(head); \ |
384 | | } \ |
385 | | /* Debugging helper: return false iff the representation of 'head' is \ |
386 | | * internally consistent. */ \ |
387 | | int \ |
388 | | name##_HT_REP_IS_BAD_(const struct name *head) \ |
389 | | { \ |
390 | | unsigned n, i; \ |
391 | | struct type *elm; \ |
392 | | if (!head->hth_table_length) { \ |
393 | | if (!head->hth_table && !head->hth_n_entries && \ |
394 | | !head->hth_load_limit && head->hth_prime_idx == -1) \ |
395 | | return 0; \ |
396 | | else \ |
397 | | return 1; \ |
398 | | } \ |
399 | | if (!head->hth_table || head->hth_prime_idx < 0 || \ |
400 | | !head->hth_load_limit) \ |
401 | | return 2; \ |
402 | | if (head->hth_n_entries > head->hth_load_limit) \ |
403 | | return 3; \ |
404 | | if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \ |
405 | | return 4; \ |
406 | | if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \ |
407 | | return 5; \ |
408 | | for (n = i = 0; i < head->hth_table_length; ++i) { \ |
409 | | for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ |
410 | | if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm)) \ |
411 | | return 1000 + i; \ |
412 | | if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \ |
413 | | return 10000 + i; \ |
414 | | ++n; \ |
415 | | } \ |
416 | | } \ |
417 | | if (n != head->hth_n_entries) \ |
418 | | return 6; \ |
419 | | return 0; \ |
420 | | } |
421 | | |
422 | | /** Implements an over-optimized "find and insert if absent" block; |
423 | | * not meant for direct usage by typical code, or usage outside the critical |
424 | | * path.*/ |
425 | | #define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \ |
426 | | { \ |
427 | | struct name *var##_head_ = head; \ |
428 | | struct eltype **var; \ |
429 | | if (!var##_head_->hth_table || \ |
430 | | var##_head_->hth_n_entries >= var##_head_->hth_load_limit) \ |
431 | | name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1); \ |
432 | | HT_SET_HASH_((elm), field, hashfn); \ |
433 | | var = name##_HT_FIND_P_(var##_head_, (elm)); \ |
434 | | if (*var) { \ |
435 | | y; \ |
436 | | } else { \ |
437 | | n; \ |
438 | | } \ |
439 | | } |
440 | | #define HT_FOI_INSERT_(field, head, elm, newent, var) \ |
441 | | { \ |
442 | | HT_SET_HASHVAL_(newent, field, (elm)->field.hte_hash); \ |
443 | | newent->field.hte_next = NULL; \ |
444 | | *var = newent; \ |
445 | | ++((head)->hth_n_entries); \ |
446 | | } |
447 | | |
448 | | /* |
449 | | * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code |
450 | | * by Christopher Clark, retrofit to allow drop-in memory management, and to |
451 | | * use the same interface as Niels Provos's tree.h. This is probably still |
452 | | * a derived work, so the original license below still applies. |
453 | | * |
454 | | * Copyright (c) 2002, Christopher Clark |
455 | | * All rights reserved. |
456 | | * |
457 | | * Redistribution and use in source and binary forms, with or without |
458 | | * modification, are permitted provided that the following conditions |
459 | | * are met: |
460 | | * |
461 | | * * Redistributions of source code must retain the above copyright |
462 | | * notice, this list of conditions and the following disclaimer. |
463 | | * |
464 | | * * Redistributions in binary form must reproduce the above copyright |
465 | | * notice, this list of conditions and the following disclaimer in the |
466 | | * documentation and/or other materials provided with the distribution. |
467 | | * |
468 | | * * Neither the name of the original author; nor the names of any contributors |
469 | | * may be used to endorse or promote products derived from this software |
470 | | * without specific prior written permission. |
471 | | * |
472 | | * |
473 | | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
474 | | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
475 | | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
476 | | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER |
477 | | * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
478 | | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
479 | | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
480 | | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
481 | | * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
482 | | * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
483 | | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
484 | | */ |
485 | | |
486 | | #endif |
487 | | |