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