fp_pair.c 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299
  1. /* Copyright (c) 2013, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. #include "or.h"
  4. #include "fp_pair.h"
  5. /* Define fp_pair_map_t structures */
  6. struct fp_pair_map_entry_s {
  7. HT_ENTRY(fp_pair_map_entry_s) node;
  8. void *val;
  9. fp_pair_t key;
  10. };
  11. struct fp_pair_map_s {
  12. HT_HEAD(fp_pair_map_impl, fp_pair_map_entry_s) head;
  13. };
  14. /*
  15. * Hash function and equality checker for fp_pair_map_t
  16. */
  17. /** Compare fp_pair_entry_t objects by key value. */
  18. static INLINE int
  19. fp_pair_map_entries_eq(const fp_pair_map_entry_t *a,
  20. const fp_pair_map_entry_t *b)
  21. {
  22. return tor_memeq(&(a->key), &(b->key), sizeof(fp_pair_t));
  23. }
  24. /** Return a hash value for an fp_pair_entry_t. */
  25. static INLINE unsigned int
  26. fp_pair_map_entry_hash(const fp_pair_map_entry_t *a)
  27. {
  28. tor_assert(sizeof(a->key) == DIGEST_LEN*2);
  29. return (unsigned) siphash24g(&a->key, DIGEST_LEN*2);
  30. }
  31. /*
  32. * Hash table functions for fp_pair_map_t
  33. */
  34. HT_PROTOTYPE(fp_pair_map_impl, fp_pair_map_entry_s, node,
  35. fp_pair_map_entry_hash, fp_pair_map_entries_eq)
  36. HT_GENERATE2(fp_pair_map_impl, fp_pair_map_entry_s, node,
  37. fp_pair_map_entry_hash, fp_pair_map_entries_eq,
  38. 0.6, tor_reallocarray_, tor_free_)
  39. /** Constructor to create a new empty map from fp_pair_t to void *
  40. */
  41. fp_pair_map_t *
  42. fp_pair_map_new(void)
  43. {
  44. fp_pair_map_t *result;
  45. result = tor_malloc(sizeof(fp_pair_map_t));
  46. HT_INIT(fp_pair_map_impl, &result->head);
  47. return result;
  48. }
  49. /** Set the current value for key to val; returns the previous
  50. * value for key if one was set, or NULL if one was not.
  51. */
  52. void *
  53. fp_pair_map_set(fp_pair_map_t *map, const fp_pair_t *key, void *val)
  54. {
  55. fp_pair_map_entry_t *resolve;
  56. fp_pair_map_entry_t search;
  57. void *oldval;
  58. tor_assert(map);
  59. tor_assert(key);
  60. tor_assert(val);
  61. memcpy(&(search.key), key, sizeof(*key));
  62. resolve = HT_FIND(fp_pair_map_impl, &(map->head), &search);
  63. if (resolve) {
  64. oldval = resolve->val;
  65. resolve->val = val;
  66. } else {
  67. resolve = tor_malloc_zero(sizeof(fp_pair_map_entry_t));
  68. memcpy(&(resolve->key), key, sizeof(*key));
  69. resolve->val = val;
  70. HT_INSERT(fp_pair_map_impl, &(map->head), resolve);
  71. oldval = NULL;
  72. }
  73. return oldval;
  74. }
  75. /** Set the current value for the key (first, second) to val; returns
  76. * the previous value for key if one was set, or NULL if one was not.
  77. */
  78. void *
  79. fp_pair_map_set_by_digests(fp_pair_map_t *map,
  80. const char *first, const char *second,
  81. void *val)
  82. {
  83. fp_pair_t k;
  84. tor_assert(first);
  85. tor_assert(second);
  86. memcpy(k.first, first, DIGEST_LEN);
  87. memcpy(k.second, second, DIGEST_LEN);
  88. return fp_pair_map_set(map, &k, val);
  89. }
  90. /** Return the current value associated with key, or NULL if no value is set.
  91. */
  92. void *
  93. fp_pair_map_get(const fp_pair_map_t *map, const fp_pair_t *key)
  94. {
  95. fp_pair_map_entry_t *resolve;
  96. fp_pair_map_entry_t search;
  97. void *val = NULL;
  98. tor_assert(map);
  99. tor_assert(key);
  100. memcpy(&(search.key), key, sizeof(*key));
  101. resolve = HT_FIND(fp_pair_map_impl, &(map->head), &search);
  102. if (resolve) val = resolve->val;
  103. return val;
  104. }
  105. /** Return the current value associated the key (first, second), or
  106. * NULL if no value is set.
  107. */
  108. void *
  109. fp_pair_map_get_by_digests(const fp_pair_map_t *map,
  110. const char *first, const char *second)
  111. {
  112. fp_pair_t k;
  113. tor_assert(first);
  114. tor_assert(second);
  115. memcpy(k.first, first, DIGEST_LEN);
  116. memcpy(k.second, second, DIGEST_LEN);
  117. return fp_pair_map_get(map, &k);
  118. }
  119. /** Remove the value currently associated with key from the map.
  120. * Return the value if one was set, or NULL if there was no entry for
  121. * key. The caller must free any storage associated with the
  122. * returned value.
  123. */
  124. void *
  125. fp_pair_map_remove(fp_pair_map_t *map, const fp_pair_t *key)
  126. {
  127. fp_pair_map_entry_t *resolve;
  128. fp_pair_map_entry_t search;
  129. void *val = NULL;
  130. tor_assert(map);
  131. tor_assert(key);
  132. memcpy(&(search.key), key, sizeof(*key));
  133. resolve = HT_REMOVE(fp_pair_map_impl, &(map->head), &search);
  134. if (resolve) {
  135. val = resolve->val;
  136. tor_free(resolve);
  137. }
  138. return val;
  139. }
  140. /** Remove all entries from map, and deallocate storage for those entries.
  141. * If free_val is provided, it is invoked on every value in map.
  142. */
  143. void
  144. fp_pair_map_free(fp_pair_map_t *map, void (*free_val)(void*))
  145. {
  146. fp_pair_map_entry_t **ent, **next, *this;
  147. if (map) {
  148. for (ent = HT_START(fp_pair_map_impl, &(map->head));
  149. ent != NULL; ent = next) {
  150. this = *ent;
  151. next = HT_NEXT_RMV(fp_pair_map_impl, &(map->head), ent);
  152. if (free_val) free_val(this->val);
  153. tor_free(this);
  154. }
  155. tor_assert(HT_EMPTY(&(map->head)));
  156. HT_CLEAR(fp_pair_map_impl, &(map->head));
  157. tor_free(map);
  158. }
  159. }
  160. /** Return true iff map has no entries.
  161. */
  162. int
  163. fp_pair_map_isempty(const fp_pair_map_t *map)
  164. {
  165. tor_assert(map);
  166. return HT_EMPTY(&(map->head));
  167. }
  168. /** Return the number of items in map.
  169. */
  170. int
  171. fp_pair_map_size(const fp_pair_map_t *map)
  172. {
  173. tor_assert(map);
  174. return HT_SIZE(&(map->head));
  175. }
  176. /** return an iterator pointing to the start of map.
  177. */
  178. fp_pair_map_iter_t *
  179. fp_pair_map_iter_init(fp_pair_map_t *map)
  180. {
  181. tor_assert(map);
  182. return HT_START(fp_pair_map_impl, &(map->head));
  183. }
  184. /** Advance iter a single step to the next entry of map, and return
  185. * its new value.
  186. */
  187. fp_pair_map_iter_t *
  188. fp_pair_map_iter_next(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
  189. {
  190. tor_assert(map);
  191. tor_assert(iter);
  192. return HT_NEXT(fp_pair_map_impl, &(map->head), iter);
  193. }
  194. /** Advance iter a single step to the next entry of map, removing the current
  195. * entry, and return its new value.
  196. */
  197. fp_pair_map_iter_t *
  198. fp_pair_map_iter_next_rmv(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
  199. {
  200. fp_pair_map_entry_t *rmv;
  201. tor_assert(map);
  202. tor_assert(iter);
  203. tor_assert(*iter);
  204. rmv = *iter;
  205. iter = HT_NEXT_RMV(fp_pair_map_impl, &(map->head), iter);
  206. tor_free(rmv);
  207. return iter;
  208. }
  209. /** Set *key_out and *val_out to the current entry pointed to by iter.
  210. */
  211. void
  212. fp_pair_map_iter_get(fp_pair_map_iter_t *iter,
  213. fp_pair_t *key_out, void **val_out)
  214. {
  215. tor_assert(iter);
  216. tor_assert(*iter);
  217. if (key_out) memcpy(key_out, &((*iter)->key), sizeof(fp_pair_t));
  218. if (val_out) *val_out = (*iter)->val;
  219. }
  220. /** Return true iff iter has advanced past the last entry of its map.
  221. */
  222. int
  223. fp_pair_map_iter_done(fp_pair_map_iter_t *iter)
  224. {
  225. return (iter == NULL);
  226. }
  227. /** Assert if anything has gone wrong with the internal
  228. * representation of map.
  229. */
  230. void
  231. fp_pair_map_assert_ok(const fp_pair_map_t *map)
  232. {
  233. tor_assert(!fp_pair_map_impl_HT_REP_IS_BAD_(&(map->head)));
  234. }