xref: /freebsd/contrib/ntp/sntp/libevent/ht-internal.h (revision bdd1243df58e60e85101c09001d9812a789b6bc4)
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 {
65   /* Aim to protect against poor hash functions by adding logic here
66    * - logic taken from java 1.4 hashtable source */
67   h += ~(h << 9);
68   h ^=  ((h >> 14) | (h << 18)); /* >>> */
69   h +=  (h << 4);
70   h ^=  ((h >> 10) | (h << 22)); /* >>> */
71   return h;
72 }
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 {
93   unsigned h;
94   const unsigned char *cp = (const unsigned char *)s;
95   h = *cp << 7;
96   while (*cp) {
97     h = (1000003*h) ^ *cp++;
98   }
99   /* This conversion truncates the length of the string, but that's ok. */
100   h ^= (unsigned)(cp-(const unsigned char*)s);
101   return h;
102 }
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 
488