tor/src/lib/container/map.c

/* Copyright (c) 2003-2004, Roger Dingledine
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
 * Copyright (c) 2007-2018, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
 * \file container.c
 * \brief Implements a smartlist (a resizable array) along
 * with helper functions to use smartlists.  Also includes
 * hash table implementations of a string-to-void* map, and of
 * a digest-to-void* map.
 **/

#include "lib/container/map.h"
#include "lib/ctime/di_ops.h"
#include "lib/defs/digest_sizes.h"
#include "lib/string/util_string.h"
#include "lib/malloc/util_malloc.h"

#include "common/util_bug.h"

#include <stdlib.h>
#include <string.h>

#include "ht.h"

/** Helper: Declare an entry type and a map type to implement a mapping using
 * ht.h.  The map type will be called <b>maptype</b>.  The key part of each
 * entry is declared using the C declaration <b>keydecl</b>.  All functions
 * and types associated with the map get prefixed with <b>prefix</b> */
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
  typedef struct prefix ## entry_t {                      \
    HT_ENTRY(prefix ## entry_t) node;                     \
    void *val;                                            \
    keydecl;                                              \
  } prefix ## entry_t;                                    \
  struct maptype {                                        \
    HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
  }

DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_);

/** Helper: compare strmap_entry_t objects by key value. */
static inline int
strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
{
  return !strcmp(a->key, b->key);
}

/** Helper: return a hash value for a strmap_entry_t. */
static inline unsigned int
strmap_entry_hash(const strmap_entry_t *a)
{
  return (unsigned) siphash24g(a->key, strlen(a->key));
}

/** Helper: compare digestmap_entry_t objects by key value. */
static inline int
digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
{
  return tor_memeq(a->key, b->key, DIGEST_LEN);
}

/** Helper: return a hash value for a digest_map_t. */
static inline unsigned int
digestmap_entry_hash(const digestmap_entry_t *a)
{
  return (unsigned) siphash24g(a->key, DIGEST_LEN);
}

/** Helper: compare digestmap_entry_t objects by key value. */
static inline int
digest256map_entries_eq(const digest256map_entry_t *a,
                        const digest256map_entry_t *b)
{
  return tor_memeq(a->key, b->key, DIGEST256_LEN);
}

/** Helper: return a hash value for a digest_map_t. */
static inline unsigned int
digest256map_entry_hash(const digest256map_entry_t *a)
{
  return (unsigned) siphash24g(a->key, DIGEST256_LEN);
}

HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
             strmap_entries_eq)
HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
             strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)

HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
             digestmap_entries_eq)
HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
             digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)

HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
             digest256map_entry_hash,
             digest256map_entries_eq)
HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
             digest256map_entry_hash,
             digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_)

#define strmap_entry_free(ent) \
  FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent))
#define digestmap_entry_free(ent) \
  FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent))
#define digest256map_entry_free(ent) \
  FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent))

static inline void
strmap_entry_free_(strmap_entry_t *ent)
{
  tor_free(ent->key);
  tor_free(ent);
}
static inline void
digestmap_entry_free_(digestmap_entry_t *ent)
{
  tor_free(ent);
}
static inline void
digest256map_entry_free_(digest256map_entry_t *ent)
{
  tor_free(ent);
}

static inline void
strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
{
  ent->key = (char*)key;
}
static inline void
digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
{
  memcpy(ent->key, key, DIGEST_LEN);
}
static inline void
digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
{
  memcpy(ent->key, key, DIGEST256_LEN);
}
static inline void
strmap_assign_key(strmap_entry_t *ent, const char *key)
{
  ent->key = tor_strdup(key);
}
static inline void
digestmap_assign_key(digestmap_entry_t *ent, const char *key)
{
  memcpy(ent->key, key, DIGEST_LEN);
}
static inline void
digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key)
{
  memcpy(ent->key, key, DIGEST256_LEN);
}

/**
 * Macro: implement all the functions for a map that are declared in
 * map.h by the DECLARE_MAP_FNS() macro.  You must additionally define a
 * prefix_entry_free_() function to free entries (and their keys), a
 * prefix_assign_tmp_key() function to temporarily set a stack-allocated
 * entry to hold a key, and a prefix_assign_key() function to set a
 * heap-allocated entry to hold a key.
 */
#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix)                     \
  /** Create and return a new empty map. */                             \
  MOCK_IMPL(maptype *,                                                  \
  prefix##_new,(void))                                                  \
  {                                                                     \
    maptype *result;                                                    \
    result = tor_malloc(sizeof(maptype));                               \
    HT_INIT(prefix##_impl, &result->head);                              \
    return result;                                                      \
  }                                                                     \
                                                                        \
  /** Return the item from <b>map</b> whose key matches <b>key</b>, or  \
   * NULL if no such value exists. */                                   \
  void *                                                                \
  prefix##_get(const maptype *map, const keytype key)                   \
  {                                                                     \
    prefix ##_entry_t *resolve;                                         \
    prefix ##_entry_t search;                                           \
    tor_assert(map);                                                    \
    tor_assert(key);                                                    \
    prefix ##_assign_tmp_key(&search, key);                             \
    resolve = HT_FIND(prefix ##_impl, &map->head, &search);             \
    if (resolve) {                                                      \
      return resolve->val;                                              \
    } else {                                                            \
      return NULL;                                                      \
    }                                                                   \
  }                                                                     \
                                                                        \
  /** Add an entry to <b>map</b> mapping <b>key</b> to <b>val</b>;      \
   * return the previous value, or NULL if no such value existed. */     \
  void *                                                                \
  prefix##_set(maptype *map, const keytype key, void *val)              \
  {                                                                     \
    prefix##_entry_t search;                                            \
    void *oldval;                                                       \
    tor_assert(map);                                                    \
    tor_assert(key);                                                    \
    tor_assert(val);                                                    \
    prefix##_assign_tmp_key(&search, key);                              \
    /* We a lot of our time in this function, so the code below is */   \
    /* meant to optimize the check/alloc/set cycle by avoiding the two */\
    /* trips to the hash table that we would do in the unoptimized */   \
    /* version of this code. (Each of HT_INSERT and HT_FIND calls */     \
    /* HT_SET_HASH and HT_FIND_P.) */                                   \
    HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash,        \
                       &(map->head),                                    \
                       prefix##_entry_t, &search, ptr,                  \
                       {                                                \
                         /* we found an entry. */                       \
                         oldval = (*ptr)->val;                          \
                         (*ptr)->val = val;                             \
                         return oldval;                                 \
                       },                                               \
                       {                                                \
                         /* We didn't find the entry. */                \
                         prefix##_entry_t *newent =                     \
                           tor_malloc_zero(sizeof(prefix##_entry_t));   \
                         prefix##_assign_key(newent, key);              \
                         newent->val = val;                             \
                         HT_FOI_INSERT_(node, &(map->head),             \
                            &search, newent, ptr);                      \
                         return NULL;                                   \
    });                                                                 \
  }                                                                     \
                                                                        \
  /** Remove the value currently associated with <b>key</b> from the map. \
   * Return the value if one was set, or NULL if there was no entry for \
   * <b>key</b>.                                                        \
   *                                                                    \
   * Note: you must free any storage associated with the returned value. \
   */                                                                   \
  void *                                                                \
  prefix##_remove(maptype *map, const keytype key)                      \
  {                                                                     \
    prefix##_entry_t *resolve;                                          \
    prefix##_entry_t search;                                            \
    void *oldval;                                                       \
    tor_assert(map);                                                    \
    tor_assert(key);                                                    \
    prefix##_assign_tmp_key(&search, key);                              \
    resolve = HT_REMOVE(prefix##_impl, &map->head, &search);            \
    if (resolve) {                                                      \
      oldval = resolve->val;                                            \
      prefix##_entry_free(resolve);                                     \
      return oldval;                                                    \
    } else {                                                            \
      return NULL;                                                      \
    }                                                                   \
  }                                                                     \
                                                                        \
  /** Return the number of elements in <b>map</b>. */                   \
  int                                                                   \
  prefix##_size(const maptype *map)                                     \
  {                                                                     \
    return HT_SIZE(&map->head);                                         \
  }                                                                     \
                                                                        \
  /** Return true iff <b>map</b> has no entries. */                     \
  int                                                                   \
  prefix##_isempty(const maptype *map)                                  \
  {                                                                     \
    return HT_EMPTY(&map->head);                                        \
  }                                                                     \
                                                                        \
  /** Assert that <b>map</b> is not corrupt. */                         \
  void                                                                  \
  prefix##_assert_ok(const maptype *map)                                \
  {                                                                     \
    tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head));              \
  }                                                                     \
                                                                        \
  /** Remove all entries from <b>map</b>, and deallocate storage for    \
   * those entries.  If free_val is provided, invoked it every value in \
   * <b>map</b>. */                                                     \
  MOCK_IMPL(void,                                                       \
  prefix##_free_, (maptype *map, void (*free_val)(void*)))              \
  {                                                                     \
    prefix##_entry_t **ent, **next, *this;                              \
    if (!map)                                                           \
      return;                                                           \
    for (ent = HT_START(prefix##_impl, &map->head); ent != NULL;        \
         ent = next) {                                                  \
      this = *ent;                                                      \
      next = HT_NEXT_RMV(prefix##_impl, &map->head, ent);               \
      if (free_val)                                                     \
        free_val(this->val);                                            \
      prefix##_entry_free(this);                                        \
    }                                                                   \
    tor_assert(HT_EMPTY(&map->head));                                   \
    HT_CLEAR(prefix##_impl, &map->head);                                \
    tor_free(map);                                                      \
  }                                                                     \
                                                                        \
  /** return an <b>iterator</b> pointer to the front of a map.          \
   *                                                                    \
   * Iterator example:                                                  \
   *                                                                    \
   * \code                                                              \
   * // uppercase values in "map", removing empty values.               \
   *                                                                    \
   * strmap_iter_t *iter;                                               \
   * const char *key;                                                   \
   * void *val;                                                         \
   * char *cp;                                                          \
   *                                                                    \
   * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {    \
   *    strmap_iter_get(iter, &key, &val);                              \
   *    cp = (char*)val;                                                \
   *    if (!*cp) {                                                     \
   *       iter = strmap_iter_next_rmv(map,iter);                       \
   *       free(val);                                                   \
   *    } else {                                                        \
   *       for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);                      \
   */                                                                   \
  prefix##_iter_t *                                                     \
  prefix##_iter_init(maptype *map)                                      \
  {                                                                     \
    tor_assert(map);                                                    \
    return HT_START(prefix##_impl, &map->head);                         \
  }                                                                     \
                                                                        \
  /** Advance <b>iter</b> a single step to the next entry, and return   \
   * its new value. */                                                  \
  prefix##_iter_t *                                                     \
  prefix##_iter_next(maptype *map, prefix##_iter_t *iter)               \
  {                                                                     \
    tor_assert(map);                                                    \
    tor_assert(iter);                                                   \
    return HT_NEXT(prefix##_impl, &map->head, iter);                    \
  }                                                                     \
  /** Advance <b>iter</b> a single step to the next entry, removing the \
   * current entry, and return its new value. */                        \
  prefix##_iter_t *                                                     \
  prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter)           \
  {                                                                     \
    prefix##_entry_t *rmv;                                              \
    tor_assert(map);                                                    \
    tor_assert(iter);                                                   \
    tor_assert(*iter);                                                  \
    rmv = *iter;                                                        \
    iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter);                \
    prefix##_entry_free(rmv);                                           \
    return iter;                                                        \
  }                                                                     \
  /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed    \
   * to by iter. */                                                     \
  void                                                                  \
  prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp,         \
                    void **valp)                                        \
  {                                                                     \
    tor_assert(iter);                                                   \
    tor_assert(*iter);                                                  \
    tor_assert(keyp);                                                   \
    tor_assert(valp);                                                   \
    *keyp = (*iter)->key;                                               \
    *valp = (*iter)->val;                                               \
  }                                                                     \
  /** Return true iff <b>iter</b> has advanced past the last entry of   \
   * <b>map</b>. */                                                     \
  int                                                                   \
  prefix##_iter_done(prefix##_iter_t *iter)                             \
  {                                                                     \
    return iter == NULL;                                                \
  }

IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map)

/** Same as strmap_set, but first converts <b>key</b> to lowercase. */
void *
strmap_set_lc(strmap_t *map, const char *key, void *val)
{
  /* We could be a little faster by using strcasecmp instead, and a separate
   * type, but I don't think it matters. */
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_set(map,lc_key,val);
  tor_free(lc_key);
  return v;
}

/** Same as strmap_get, but first converts <b>key</b> to lowercase. */
void *
strmap_get_lc(const strmap_t *map, const char *key)
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_get(map,lc_key);
  tor_free(lc_key);
  return v;
}

/** Same as strmap_remove, but first converts <b>key</b> to lowercase */
void *
strmap_remove_lc(strmap_t *map, const char *key)
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_remove(map,lc_key);
  tor_free(lc_key);
  return v;
}