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