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