src/or/fp_pair.c

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