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