fp_pair.c 6.7 KB

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