ht.h 31 KB

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