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