ht.h 34 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620
  1. /* Copyright (c) 2002, Christopher Clark.
  2. * Copyright (c) 2005-2006, Nick Mathewson.
  3. * Copyright (c) 2007-2017, The Tor Project, Inc. */
  4. /* See license at end. */
  5. /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */
  6. /*
  7. These macros provide an intrustive implementation for a typesafe chaining
  8. hash table, loosely based on the BSD tree.h and queue.h macros. Here's
  9. how to use them.
  10. First, pick a the structure that you'll be storing in the hashtable. Let's
  11. say that's "struct dinosaur". To this structure, you add an HT_ENTRY()
  12. member, as such:
  13. struct dinosaur {
  14. HT_ENTRY(dinosaur) node; // The name inside the () must match the
  15. // struct.
  16. // These are just fields from the dinosaur structure...
  17. long dinosaur_id;
  18. char *name;
  19. long age;
  20. int is_ornithischian;
  21. int is_herbivorous;
  22. };
  23. You can declare the hashtable itself as:
  24. HT_HEAD(dinosaur_ht, dinosaur);
  25. This declares a new 'struct dinosaur_ht' type.
  26. Now you need to declare two functions to help implement the hashtable: one
  27. compares two dinosaurs for equality, and one computes the hash of a
  28. dinosaur. Let's say that two dinosaurs are equal if they have the same ID
  29. and name.
  30. int
  31. dinosaurs_equal(const struct dinosaur *d1, const struct dinosaur *d2)
  32. {
  33. return d1->dinosaur_id == d2->dinosaur_id &&
  34. 0 == strcmp(d1->name, d2->name);
  35. }
  36. unsigned
  37. dinosaur_hash(const struct dinosaur *d)
  38. {
  39. // This is a very bad hash function. Use siphash24g instead.
  40. return (d->dinosaur_id + d->name[0] ) * 1337 + d->name[1] * 1337;
  41. }
  42. Now you'll need to declare the functions that manipulate the hash table.
  43. To do this, you put this declaration either in a header file, or inside
  44. a regular module, depending on what visibility you want.
  45. HT_PROTOTYPE(dinosaur_ht, // The name of the hashtable struct
  46. dinosaur, // The name of the element struct,
  47. node, // The name of HT_ENTRY member
  48. dinosaur_hash, dinosaurs_equal);
  49. Later, inside a C function, you use this macro to declare the hashtable
  50. functions.
  51. HT_GENERATE2(dinosaur_ht, dinosaur, node, dinosaur_hash, dinosaurs_equal,
  52. 0.6, tor_reallocarray, tor_free_);
  53. Note the use of tor_free_, not tor_free. The 0.6 is magic.
  54. Now you can use the hashtable! You can initialize one with
  55. struct dinosaur_ht my_dinos = HT_INITIALIZER();
  56. Or create one in core with
  57. struct dinosaur_ht *dinos = tor_malloc(sizeof(dinosaur_ht));
  58. HT_INIT(dinosaur_ht, dinos);
  59. To the hashtable, you use the HT_FOO(dinosaur_ht, ...) macros. For
  60. example, to put new_dino into dinos, you say:
  61. HT_REPLACE(dinosaur_ht, dinos, new_dino);
  62. If you're searching for an element, you need to use a dummy 'key' element in
  63. the search. For example.
  64. struct dinosaur dino_key;
  65. dino_key.dinosaur_id = 12345;
  66. dino_key.name = tor_strdup("Atrociraptor");
  67. struct dinosaur *found = HT_FIND(dinosaurs_ht, dinos, &dino_key);
  68. Have fun with your hash table!
  69. */
  70. #ifndef HT_H_INCLUDED_
  71. #define HT_H_INCLUDED_
  72. #define HT_HEAD(name, type) \
  73. struct name { \
  74. /* The hash table itself. */ \
  75. struct type **hth_table; \
  76. /* How long is the hash table? */ \
  77. unsigned hth_table_length; \
  78. /* How many elements does the table contain? */ \
  79. unsigned hth_n_entries; \
  80. /* How many elements will we allow in the table before resizing it? */ \
  81. unsigned hth_load_limit; \
  82. /* Position of hth_table_length in the primes table. */ \
  83. int hth_prime_idx; \
  84. }
  85. #define HT_INITIALIZER() \
  86. { NULL, 0, 0, 0, -1 }
  87. #ifdef HT_NO_CACHE_HASH_VALUES
  88. #define HT_ENTRY(type) \
  89. struct { \
  90. struct type *hte_next; \
  91. }
  92. #else
  93. #define HT_ENTRY(type) \
  94. struct { \
  95. struct type *hte_next; \
  96. unsigned hte_hash; \
  97. }
  98. #endif
  99. /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */
  100. #define HT_EMPTY(head) \
  101. (((head)->hth_n_entries == 0) || 0)
  102. /* How many elements in 'head'? */
  103. #define HT_SIZE(head) \
  104. ((head)->hth_n_entries)
  105. /* Return memory usage for a hashtable (not counting the entries themselves) */
  106. #define HT_MEM_USAGE(head) \
  107. (sizeof(*head) + (head)->hth_table_length * sizeof(void*))
  108. #define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm))
  109. #define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm))
  110. #define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm))
  111. #define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm))
  112. #define HT_START(name, head) name##_HT_START(head)
  113. #define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm))
  114. #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm))
  115. #define HT_CLEAR(name, head) name##_HT_CLEAR(head)
  116. #define HT_INIT(name, head) name##_HT_INIT(head)
  117. #define HT_REP_IS_BAD_(name, head) name##_HT_REP_IS_BAD_(head)
  118. #define HT_FOREACH_FN(name, head, fn, data) \
  119. name##_HT_FOREACH_FN((head), (fn), (data))
  120. /* Helper: */
  121. static inline unsigned
  122. ht_improve_hash(unsigned h)
  123. {
  124. /* Aim to protect against poor hash functions by adding logic here
  125. * - logic taken from java 1.4 hashtable source */
  126. h += ~(h << 9);
  127. h ^= ((h >> 14) | (h << 18)); /* >>> */
  128. h += (h << 4);
  129. h ^= ((h >> 10) | (h << 22)); /* >>> */
  130. return h;
  131. }
  132. #if 0
  133. /** Basic string hash function, from Java standard String.hashCode(). */
  134. static inline unsigned
  135. ht_string_hash(const char *s)
  136. {
  137. unsigned h = 0;
  138. int m = 1;
  139. while (*s) {
  140. h += ((signed char)*s++)*m;
  141. m = (m<<5)-1; /* m *= 31 */
  142. }
  143. return h;
  144. }
  145. #endif
  146. #if 0
  147. /** Basic string hash function, from Python's str.__hash__() */
  148. static inline unsigned
  149. ht_string_hash(const char *s)
  150. {
  151. unsigned h;
  152. const unsigned char *cp = (const unsigned char *)s;
  153. h = *cp << 7;
  154. while (*cp) {
  155. h = (1000003*h) ^ *cp++;
  156. }
  157. /* This conversion truncates the length of the string, but that's ok. */
  158. h ^= (unsigned)(cp-(const unsigned char*)s);
  159. return h;
  160. }
  161. #endif
  162. #ifndef HT_NO_CACHE_HASH_VALUES
  163. #define HT_SET_HASH_(elm, field, hashfn) \
  164. do { (elm)->field.hte_hash = hashfn(elm); } while (0)
  165. #define HT_SET_HASHVAL_(elm, field, val) \
  166. do { (elm)->field.hte_hash = (val); } while (0)
  167. #define HT_ELT_HASH_(elm, field, hashfn) \
  168. ((elm)->field.hte_hash)
  169. #else
  170. #define HT_SET_HASH_(elm, field, hashfn) \
  171. ((void)0)
  172. #define HT_ELT_HASH_(elm, field, hashfn) \
  173. (hashfn(elm))
  174. #define HT_SET_HASHVAL_(elm, field, val) \
  175. ((void)0)
  176. #endif
  177. #define HT_BUCKET_NUM_(head, field, elm, hashfn) \
  178. (HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length)
  179. /* Helper: alias for the bucket containing 'elm'. */
  180. #define HT_BUCKET_(head, field, elm, hashfn) \
  181. ((head)->hth_table[HT_BUCKET_NUM_(head, field, elm, hashfn)])
  182. #define HT_FOREACH(x, name, head) \
  183. for ((x) = HT_START(name, head); \
  184. (x) != NULL; \
  185. (x) = HT_NEXT(name, head, x))
  186. #ifndef HT_NDEBUG
  187. #define HT_ASSERT_(x) tor_assert(x)
  188. #else
  189. #define HT_ASSERT_(x) (void)0
  190. #endif
  191. #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \
  192. int name##_HT_GROW(struct name *ht, unsigned min_capacity); \
  193. void name##_HT_CLEAR(struct name *ht); \
  194. int name##_HT_REP_IS_BAD_(const struct name *ht); \
  195. static inline void \
  196. name##_HT_INIT(struct name *head) { \
  197. head->hth_table_length = 0; \
  198. head->hth_table = NULL; \
  199. head->hth_n_entries = 0; \
  200. head->hth_load_limit = 0; \
  201. head->hth_prime_idx = -1; \
  202. } \
  203. /* Helper: returns a pointer to the right location in the table \
  204. * 'head' to find or insert the element 'elm'. */ \
  205. static inline struct type ** \
  206. name##_HT_FIND_P_(struct name *head, struct type *elm) \
  207. { \
  208. struct type **p; \
  209. if (!head->hth_table) \
  210. return NULL; \
  211. p = &HT_BUCKET_(head, field, elm, hashfn); \
  212. while (*p) { \
  213. if (eqfn(*p, elm)) \
  214. return p; \
  215. p = &(*p)->field.hte_next; \
  216. } \
  217. return p; \
  218. } \
  219. /* Return a pointer to the element in the table 'head' matching 'elm', \
  220. * or NULL if no such element exists */ \
  221. ATTR_UNUSED static inline struct type * \
  222. name##_HT_FIND(const struct name *head, struct type *elm) \
  223. { \
  224. struct type **p; \
  225. struct name *h = (struct name *) head; \
  226. HT_SET_HASH_(elm, field, hashfn); \
  227. p = name##_HT_FIND_P_(h, elm); \
  228. return p ? *p : NULL; \
  229. } \
  230. /* Insert the element 'elm' into the table 'head'. Do not call this \
  231. * function if the table might already contain a matching element. */ \
  232. ATTR_UNUSED static inline void \
  233. name##_HT_INSERT(struct name *head, struct type *elm) \
  234. { \
  235. struct type **p; \
  236. if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
  237. name##_HT_GROW(head, head->hth_n_entries+1); \
  238. ++head->hth_n_entries; \
  239. HT_SET_HASH_(elm, field, hashfn); \
  240. p = &HT_BUCKET_(head, field, elm, hashfn); \
  241. elm->field.hte_next = *p; \
  242. *p = elm; \
  243. } \
  244. /* Insert the element 'elm' into the table 'head'. If there already \
  245. * a matching element in the table, replace that element and return \
  246. * it. */ \
  247. ATTR_UNUSED static inline struct type * \
  248. name##_HT_REPLACE(struct name *head, struct type *elm) \
  249. { \
  250. struct type **p, *r; \
  251. if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
  252. name##_HT_GROW(head, head->hth_n_entries+1); \
  253. HT_SET_HASH_(elm, field, hashfn); \
  254. p = name##_HT_FIND_P_(head, elm); \
  255. HT_ASSERT_(p != NULL); /* this holds because we called HT_GROW */ \
  256. r = *p; \
  257. *p = elm; \
  258. if (r && (r!=elm)) { \
  259. elm->field.hte_next = r->field.hte_next; \
  260. r->field.hte_next = NULL; \
  261. return r; \
  262. } else { \
  263. ++head->hth_n_entries; \
  264. return NULL; \
  265. } \
  266. } \
  267. /* Remove any element matching 'elm' from the table 'head'. If such \
  268. * an element is found, return it; otherwise return NULL. */ \
  269. ATTR_UNUSED static inline struct type * \
  270. name##_HT_REMOVE(struct name *head, struct type *elm) \
  271. { \
  272. struct type **p, *r; \
  273. HT_SET_HASH_(elm, field, hashfn); \
  274. p = name##_HT_FIND_P_(head,elm); \
  275. if (!p || !*p) \
  276. return NULL; \
  277. r = *p; \
  278. *p = r->field.hte_next; \
  279. r->field.hte_next = NULL; \
  280. --head->hth_n_entries; \
  281. return r; \
  282. } \
  283. /* Invoke the function 'fn' on every element of the table 'head', \
  284. * using 'data' as its second argument. If the function returns \
  285. * nonzero, remove the most recently examined element before invoking \
  286. * the function again. */ \
  287. ATTR_UNUSED static inline void \
  288. name##_HT_FOREACH_FN(struct name *head, \
  289. int (*fn)(struct type *, void *), \
  290. void *data) \
  291. { \
  292. unsigned idx; \
  293. struct type **p, **nextp, *next; \
  294. if (!head->hth_table) \
  295. return; \
  296. for (idx=0; idx < head->hth_table_length; ++idx) { \
  297. p = &head->hth_table[idx]; \
  298. while (*p) { \
  299. nextp = &(*p)->field.hte_next; \
  300. next = *nextp; \
  301. if (fn(*p, data)) { \
  302. --head->hth_n_entries; \
  303. *p = next; \
  304. } else { \
  305. p = nextp; \
  306. } \
  307. } \
  308. } \
  309. } \
  310. /* Return a pointer to the first element in the table 'head', under \
  311. * an arbitrary order. This order is stable under remove operations, \
  312. * but not under others. If the table is empty, return NULL. */ \
  313. ATTR_UNUSED static inline struct type ** \
  314. name##_HT_START(struct name *head) \
  315. { \
  316. unsigned b = 0; \
  317. while (b < head->hth_table_length) { \
  318. if (head->hth_table[b]) { \
  319. HT_ASSERT_(b == \
  320. HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \
  321. return &head->hth_table[b]; \
  322. } \
  323. ++b; \
  324. } \
  325. return NULL; \
  326. } \
  327. /* Return the next element in 'head' after 'elm', under the arbitrary \
  328. * order used by HT_START. If there are no more elements, return \
  329. * NULL. If 'elm' is to be removed from the table, you must call \
  330. * this function for the next value before you remove it. \
  331. */ \
  332. ATTR_UNUSED static inline struct type ** \
  333. name##_HT_NEXT(struct name *head, struct type **elm) \
  334. { \
  335. if ((*elm)->field.hte_next) { \
  336. HT_ASSERT_(HT_BUCKET_NUM_(head,field,*elm,hashfn) == \
  337. HT_BUCKET_NUM_(head,field,(*elm)->field.hte_next,hashfn)); \
  338. return &(*elm)->field.hte_next; \
  339. } else { \
  340. unsigned b = HT_BUCKET_NUM_(head,field,*elm,hashfn)+1; \
  341. while (b < head->hth_table_length) { \
  342. if (head->hth_table[b]) { \
  343. HT_ASSERT_(b == \
  344. HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \
  345. return &head->hth_table[b]; \
  346. } \
  347. ++b; \
  348. } \
  349. return NULL; \
  350. } \
  351. } \
  352. ATTR_UNUSED static inline struct type ** \
  353. name##_HT_NEXT_RMV(struct name *head, struct type **elm) \
  354. { \
  355. unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \
  356. *elm = (*elm)->field.hte_next; \
  357. --head->hth_n_entries; \
  358. if (*elm) { \
  359. return elm; \
  360. } else { \
  361. unsigned b = (h % head->hth_table_length)+1; \
  362. while (b < head->hth_table_length) { \
  363. if (head->hth_table[b]) \
  364. return &head->hth_table[b]; \
  365. ++b; \
  366. } \
  367. return NULL; \
  368. } \
  369. }
  370. #define HT_GENERATE2(name, type, field, hashfn, eqfn, load, reallocarrayfn, \
  371. freefn) \
  372. /* Primes that aren't too far from powers of two. We stop at */ \
  373. /* P=402653189 because P*sizeof(void*) is less than SSIZE_MAX */ \
  374. /* even on a 32-bit platform. */ \
  375. static unsigned name##_PRIMES[] = { \
  376. 53, 97, 193, 389, \
  377. 769, 1543, 3079, 6151, \
  378. 12289, 24593, 49157, 98317, \
  379. 196613, 393241, 786433, 1572869, \
  380. 3145739, 6291469, 12582917, 25165843, \
  381. 50331653, 100663319, 201326611, 402653189 \
  382. }; \
  383. static unsigned name##_N_PRIMES = \
  384. (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \
  385. /* Expand the internal table of 'head' until it is large enough to \
  386. * hold 'size' elements. Return 0 on success, -1 on allocation \
  387. * failure. */ \
  388. int \
  389. name##_HT_GROW(struct name *head, unsigned size) \
  390. { \
  391. unsigned new_len, new_load_limit; \
  392. int prime_idx; \
  393. struct type **new_table; \
  394. if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \
  395. return 0; \
  396. if (head->hth_load_limit > size) \
  397. return 0; \
  398. prime_idx = head->hth_prime_idx; \
  399. do { \
  400. new_len = name##_PRIMES[++prime_idx]; \
  401. new_load_limit = (unsigned)(load*new_len); \
  402. } while (new_load_limit <= size && \
  403. prime_idx < (int)name##_N_PRIMES); \
  404. if ((new_table = reallocarrayfn(NULL, new_len, sizeof(struct type*)))) { \
  405. unsigned b; \
  406. memset(new_table, 0, new_len*sizeof(struct type*)); \
  407. for (b = 0; b < head->hth_table_length; ++b) { \
  408. struct type *elm, *next; \
  409. unsigned b2; \
  410. elm = head->hth_table[b]; \
  411. while (elm) { \
  412. next = elm->field.hte_next; \
  413. b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len; \
  414. elm->field.hte_next = new_table[b2]; \
  415. new_table[b2] = elm; \
  416. elm = next; \
  417. } \
  418. } \
  419. if (head->hth_table) \
  420. freefn(head->hth_table); \
  421. head->hth_table = new_table; \
  422. } else { \
  423. unsigned b, b2; \
  424. new_table = reallocarrayfn(head->hth_table, new_len, sizeof(struct type*)); \
  425. if (!new_table) return -1; \
  426. memset(new_table + head->hth_table_length, 0, \
  427. (new_len - head->hth_table_length)*sizeof(struct type*)); \
  428. for (b=0; b < head->hth_table_length; ++b) { \
  429. struct type *e, **pE; \
  430. for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \
  431. b2 = HT_ELT_HASH_(e, field, hashfn) % new_len; \
  432. if (b2 == b) { \
  433. pE = &e->field.hte_next; \
  434. } else { \
  435. *pE = e->field.hte_next; \
  436. e->field.hte_next = new_table[b2]; \
  437. new_table[b2] = e; \
  438. } \
  439. } \
  440. } \
  441. head->hth_table = new_table; \
  442. } \
  443. head->hth_table_length = new_len; \
  444. head->hth_prime_idx = prime_idx; \
  445. head->hth_load_limit = new_load_limit; \
  446. return 0; \
  447. } \
  448. /* Free all storage held by 'head'. Does not free 'head' itself, or \
  449. * individual elements. */ \
  450. void \
  451. name##_HT_CLEAR(struct name *head) \
  452. { \
  453. if (head->hth_table) \
  454. freefn(head->hth_table); \
  455. head->hth_table_length = 0; \
  456. name##_HT_INIT(head); \
  457. } \
  458. /* Debugging helper: return false iff the representation of 'head' is \
  459. * internally consistent. */ \
  460. int \
  461. name##_HT_REP_IS_BAD_(const struct name *head) \
  462. { \
  463. unsigned n, i; \
  464. struct type *elm; \
  465. if (!head->hth_table_length) { \
  466. if (!head->hth_table && !head->hth_n_entries && \
  467. !head->hth_load_limit && head->hth_prime_idx == -1) \
  468. return 0; \
  469. else \
  470. return 1; \
  471. } \
  472. if (!head->hth_table || head->hth_prime_idx < 0 || \
  473. !head->hth_load_limit) \
  474. return 2; \
  475. if (head->hth_n_entries > head->hth_load_limit) \
  476. return 3; \
  477. if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \
  478. return 4; \
  479. if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
  480. return 5; \
  481. for (n = i = 0; i < head->hth_table_length; ++i) { \
  482. for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \
  483. if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm)) \
  484. return 1000 + i; \
  485. if (HT_BUCKET_NUM_(head,field,elm,hashfn) != i) \
  486. return 10000 + i; \
  487. ++n; \
  488. } \
  489. } \
  490. if (n != head->hth_n_entries) \
  491. return 6; \
  492. return 0; \
  493. }
  494. #define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \
  495. reallocfn, freefn) \
  496. static void * \
  497. name##_reallocarray(void *arg, size_t a, size_t b) \
  498. { \
  499. if ((b) && (a) > SIZE_MAX / (b)) \
  500. return NULL; \
  501. if (arg) \
  502. return reallocfn((arg),(a)*(b)); \
  503. else \
  504. return mallocfn((a)*(b)); \
  505. } \
  506. HT_GENERATE2(name, type, field, hashfn, eqfn, load, \
  507. name##_reallocarray, freefn)
  508. /** Implements an over-optimized "find and insert if absent" block;
  509. * not meant for direct usage by typical code, or usage outside the critical
  510. * path.*/
  511. #define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \
  512. { \
  513. struct name *var##_head_ = head; \
  514. struct eltype **var; \
  515. if (!var##_head_->hth_table || \
  516. var##_head_->hth_n_entries >= var##_head_->hth_load_limit) \
  517. name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1); \
  518. HT_SET_HASH_((elm), field, hashfn); \
  519. var = name##_HT_FIND_P_(var##_head_, (elm)); \
  520. HT_ASSERT_(var); /* Holds because we called HT_GROW */ \
  521. if (*var) { \
  522. y; \
  523. } else { \
  524. n; \
  525. } \
  526. }
  527. #define HT_FOI_INSERT_(field, head, elm, newent, var) \
  528. { \
  529. HT_SET_HASHVAL_(newent, field, (elm)->field.hte_hash); \
  530. newent->field.hte_next = NULL; \
  531. *var = newent; \
  532. ++((head)->hth_n_entries); \
  533. }
  534. /*
  535. * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code
  536. * by Christopher Clark, retrofit to allow drop-in memory management, and to
  537. * use the same interface as Niels Provos's tree.h. This is probably still
  538. * a derived work, so the original license below still applies.
  539. *
  540. * Copyright (c) 2002, Christopher Clark
  541. * All rights reserved.
  542. *
  543. * Redistribution and use in source and binary forms, with or without
  544. * modification, are permitted provided that the following conditions
  545. * are met:
  546. *
  547. * * Redistributions of source code must retain the above copyright
  548. * notice, this list of conditions and the following disclaimer.
  549. *
  550. * * Redistributions in binary form must reproduce the above copyright
  551. * notice, this list of conditions and the following disclaimer in the
  552. * documentation and/or other materials provided with the distribution.
  553. *
  554. * * Neither the name of the original author; nor the names of any contributors
  555. * may be used to endorse or promote products derived from this software
  556. * without specific prior written permission.
  557. *
  558. *
  559. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  560. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  561. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  562. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
  563. * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  564. * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  565. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  566. * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  567. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  568. * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  569. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  570. */
  571. #endif