src/or/fp_pair.c

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