[obfsproxy/master] Import container library from Tor. - tor-commits

9 Sep 2011

commit a76f6457e330d14d09d490d2c73f47ac2c7369c6
Author: Zack Weinberg zackw@panix.com
Date:   Tue Jul 19 09:56:07 2011 -0700
Import container library from Tor.
* src/container.c, src/container.h, src/ht.h, src/test/unittest_container.c:
       New files.
     * Makefile.am: Add new files (and some old files that got missed).
     * src/test/unittest.c: Add test group for container library.
* configure.ac: Check size of int.  Check for 'inline'.
     * util.h: Include stdint.h (unconditionally for now).
       (xstrndup, ui64_log2, ascii_isspace, ascii_strstrip, ascii_strlower):
       New functions required by container.c.
     * util.c: Define said new functions.
     * crypt.h, crypt.c (random_int): Another function needed by container.c.
---
 Makefile.am                   |    5 +
 configure.ac                  |   18 +-
 src/container.c               | 1441 +++++++++++++++++++++++++++++++++++++++++
 src/container.h               |  685 ++++++++++++++++++++
 src/crypt.c                   |   24 +
 src/crypt.h                   |    5 +
 src/ht.h                      |  471 ++++++++++++++
 src/test/unittest.c           |    2 +
 src/test/unittest_container.c |  772 ++++++++++++++++++++++
 src/util.c                    |   74 +++
 src/util.h                    |   19 +-
 11 files changed, 3514 insertions(+), 2 deletions(-)

diff --git a/Makefile.am b/Makefile.am
index 521ba24..ff518ad 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -9,6 +9,7 @@ noinst_LIBRARIES = libobfsproxy.a
 noinst_PROGRAMS = unittests
libobfsproxy_a_SOURCES = \
+	src/container.c \
    src/crypt.c \
    src/network.c \
    src/protocol.c \
@@ -26,12 +27,16 @@ obfsproxy_SOURCES = \
 unittests_SOURCES = \
    src/test/tinytest.c \
    src/test/unittest.c \
+	src/test/unittest_container.c \
    src/test/unittest_crypt.c \
    src/test/unittest_obfs2.c \
    src/test/unittest_socks.c
noinst_HEADERS = \
+	src/container.h \
    src/crypt.h \
+	src/ht.h \
+	src/main.h \
    src/network.h \
    src/protocol.h \
    src/sha256.h \
diff --git a/configure.ac b/configure.ac
index 32b7138..fc82507 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1,13 +1,22 @@
 AC_PREREQ([2.61])dnl Possibly earlier will do, but this is what I have
 AC_INIT([obsproxy], [0.0])
 AC_CONFIG_SRCDIR([src/main.c])
-
 AM_INIT_AUTOMAKE([foreign])
+dnl The stock definition of AC_INCLUDES_DEFAULT performs a whole bunch
+dnl of completely unnecessary checks *even if* you override its
+dnl mostly-useless default header list at invocation time.
+dnl Replace it with a version that does nothing unless requested.
+m4_pushdef([AC_INCLUDES_DEFAULT], [$1])
+
+### Programs ###
+
 AC_PROG_CC
 AC_PROG_RANLIB
 PKG_PROG_PKG_CONFIG
+### Libraries ###
+
 PKG_CHECK_MODULES([libevent], [libevent >= 2.0])
 # Presently no need for libssl, only libcrypto.
 PKG_CHECK_MODULES([libcrypto], [libcrypto >= 0.9.7])
@@ -28,6 +37,13 @@ LIBS="$libevent_LIBS $libcrypto_LIBS"
 AX_LIB_WINSOCK2
 LIBS="$save_LIBS"
+### C features ###
+
+AC_C_INLINE
+AC_CHECK_SIZEOF(int)
+
+### Output ###
+
 AC_CONFIG_FILES([Makefile])
 AC_CONFIG_HEADERS([config.h])
 AC_OUTPUT
diff --git a/src/container.c b/src/container.c
new file mode 100644
index 0000000..b66a819
--- /dev/null
+++ b/src/container.c
@@ -0,0 +1,1441 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2011, 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 "util.h"
+#include "container.h"
+#include "crypt.h"
+#include "ht.h"
+
+/** All newly allocated smartlists have this capacity. */
+#define SMARTLIST_DEFAULT_CAPACITY 16
+
+/** Allocate and return an empty smartlist.
+ */
+smartlist_t *
+smartlist_create(void)
+{
+  smartlist_t *sl = xmalloc(sizeof(smartlist_t));
+  sl->num_used = 0;
+  sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
+  sl->list = xmalloc(sizeof(void *) * sl->capacity);
+  return sl;
+}
+
+/** Deallocate a smartlist.  Does not release storage associated with the
+ * list's elements.
+ */
+void
+smartlist_free(smartlist_t *sl)
+{
+  if (!sl)
+    return;
+  free(sl->list);
+  free(sl);
+}
+
+/** Remove all elements from the list.
+ */
+void
+smartlist_clear(smartlist_t *sl)
+{
+  sl->num_used = 0;
+}
+
+/** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
+static inline void
+smartlist_ensure_capacity(smartlist_t *sl, int size)
+{
+  if (size > sl->capacity) {
+    int higher = sl->capacity * 2;
+    while (size > higher)
+      higher *= 2;
+    obfs_assert(higher > 0); /* detect overflow */
+    sl->capacity = higher;
+    sl->list = xrealloc(sl->list, sizeof(void*)*sl->capacity);
+  }
+}
+
+/** Append element to the end of the list. */
+void
+smartlist_add(smartlist_t *sl, void *element)
+{
+  smartlist_ensure_capacity(sl, sl->num_used+1);
+  sl->list[sl->num_used++] = element;
+}
+
+/** Append each element from S2 to the end of S1. */
+void
+smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
+{
+  int new_size = s1->num_used + s2->num_used;
+  obfs_assert(new_size >= s1->num_used); /* check for overflow. */
+  smartlist_ensure_capacity(s1, new_size);
+  memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
+  s1->num_used = new_size;
+}
+
+/** Remove all elements E from sl such that E==element.  Preserve
+ * the order of any elements before E, but elements after E can be
+ * rearranged.
+ */
+void
+smartlist_remove(smartlist_t *sl, const void *element)
+{
+  int i;
+  if (element == NULL)
+    return;
+  for (i=0; i < sl->num_used; i++)
+    if (sl->list[i] == element) {
+      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
+      i--; /* so we process the new i'th element */
+    }
+}
+
+/** If <b>sl</b> is nonempty, remove and return the final element.  Otherwise,
+ * return NULL. */
+void *
+smartlist_pop_last(smartlist_t *sl)
+{
+  obfs_assert(sl);
+  if (sl->num_used)
+    return sl->list[--sl->num_used];
+  else
+    return NULL;
+}
+
+/** Reverse the order of the items in <b>sl</b>. */
+void
+smartlist_reverse(smartlist_t *sl)
+{
+  int i, j;
+  void *tmp;
+  obfs_assert(sl);
+  for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
+    tmp = sl->list[i];
+    sl->list[i] = sl->list[j];
+    sl->list[j] = tmp;
+  }
+}
+
+/** If there are any strings in sl equal to element, remove and free them.
+ * Does not preserve order. */
+void
+smartlist_string_remove(smartlist_t *sl, const char *element)
+{
+  int i;
+  obfs_assert(sl);
+  obfs_assert(element);
+  for (i = 0; i < sl->num_used; ++i) {
+    if (!strcmp(element, sl->list[i])) {
+      free(sl->list[i]);
+      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
+      i--; /* so we process the new i'th element */
+    }
+  }
+}
+
+/** Return true iff some element E of sl has E==element.
+ */
+int
+smartlist_isin(const smartlist_t *sl, const void *element)
+{
+  int i;
+  for (i=0; i < sl->num_used; i++)
+    if (sl->list[i] == element)
+      return 1;
+  return 0;
+}
+
+/** Return true iff <b>sl</b> has some element E such that
+ * !strcmp(E,<b>element</b>)
+ */
+int
+smartlist_string_isin(const smartlist_t *sl, const char *element)
+{
+  int i;
+  if (!sl) return 0;
+  for (i=0; i < sl->num_used; i++)
+    if (strcmp((const char*)sl->list[i],element)==0)
+      return 1;
+  return 0;
+}
+
+/** If <b>element</b> is equal to an element of <b>sl</b>, return that
+ * element's index.  Otherwise, return -1. */
+int
+smartlist_string_pos(const smartlist_t *sl, const char *element)
+{
+  int i;
+  if (!sl) return -1;
+  for (i=0; i < sl->num_used; i++)
+    if (strcmp((const char*)sl->list[i],element)==0)
+      return i;
+  return -1;
+}
+
+/** Return true iff <b>sl</b> has some element E such that
+ * !strcasecmp(E,<b>element</b>)
+ */
+int
+smartlist_string_isin_case(const smartlist_t *sl, const char *element)
+{
+  int i;
+  if (!sl) return 0;
+  for (i=0; i < sl->num_used; i++)
+    if (strcasecmp((const char*)sl->list[i],element)==0)
+      return 1;
+  return 0;
+}
+
+/** Return true iff <b>sl</b> has some element E such that E is equal
+ * to the decimal encoding of <b>num</b>.
+ */
+int
+smartlist_string_num_isin(const smartlist_t *sl, int num)
+{
+  char buf[32]; /* long enough for 64-bit int, and then some. */
+  obfs_snprintf(buf,sizeof(buf),"%d", num);
+  return smartlist_string_isin(sl, buf);
+}
+
+/** Return true iff the two lists contain the same strings in the same
+ * order, or if they are both NULL. */
+int
+smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
+{
+  if (sl1 == NULL)
+    return sl2 == NULL;
+  if (sl2 == NULL)
+    return 0;
+  if (smartlist_len(sl1) != smartlist_len(sl2))
+    return 0;
+  SMARTLIST_FOREACH(sl1, const char *, cp1, {
+      const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
+      if (strcmp(cp1, cp2))
+        return 0;
+    });
+  return 1;
+}
+
+/** Return true iff <b>sl</b> has some element E such that
+ * !memcmp(E,<b>element</b>,SHA256_LENGTH)
+ */
+int
+smartlist_digest_isin(const smartlist_t *sl, const char *element)
+{
+  int i;
+  if (!sl) return 0;
+  for (i=0; i < sl->num_used; i++)
+    if (!memcmp((const char*)sl->list[i],element,SHA256_LENGTH))
+      return 1;
+  return 0;
+}
+
+/** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
+ */
+int
+smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
+{
+  int i;
+  for (i=0; i < sl2->num_used; i++)
+    if (smartlist_isin(sl1, sl2->list[i]))
+      return 1;
+  return 0;
+}
+
+/** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
+ * Does not preserve the order of sl1.
+ */
+void
+smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
+{
+  int i;
+  for (i=0; i < sl1->num_used; i++)
+    if (!smartlist_isin(sl2, sl1->list[i])) {
+      sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
+      i--; /* so we process the new i'th element */
+    }
+}
+
+/** Remove every element E of sl1 such that smartlist_isin(sl2,E).
+ * Does not preserve the order of sl1.
+ */
+void
+smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
+{
+  int i;
+  for (i=0; i < sl2->num_used; i++)
+    smartlist_remove(sl1, sl2->list[i]);
+}
+
+/** Remove the <b>idx</b>th element of sl; if idx is not the last
+ * element, swap the last element of sl into the <b>idx</b>th space.
+ */
+void
+smartlist_del(smartlist_t *sl, int idx)
+{
+  obfs_assert(sl);
+  obfs_assert(idx>=0);
+  obfs_assert(idx < sl->num_used);
+  sl->list[idx] = sl->list[--sl->num_used];
+}
+
+/** Remove the <b>idx</b>th element of sl; if idx is not the last element,
+ * moving all subsequent elements back one space. Return the old value
+ * of the <b>idx</b>th element.
+ */
+void
+smartlist_del_keeporder(smartlist_t *sl, int idx)
+{
+  obfs_assert(sl);
+  obfs_assert(idx>=0);
+  obfs_assert(idx < sl->num_used);
+  --sl->num_used;
+  if (idx < sl->num_used)
+    memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
+}
+
+/** Insert the value <b>val</b> as the new <b>idx</b>th element of
+ * <b>sl</b>, moving all items previously at <b>idx</b> or later
+ * forward one space.
+ */
+void
+smartlist_insert(smartlist_t *sl, int idx, void *val)
+{
+  obfs_assert(sl);
+  obfs_assert(idx>=0);
+  obfs_assert(idx <= sl->num_used);
+  if (idx == sl->num_used) {
+    smartlist_add(sl, val);
+  } else {
+    smartlist_ensure_capacity(sl, sl->num_used+1);
+    /* Move other elements away */
+    if (idx < sl->num_used)
+      memmove(sl->list + idx + 1, sl->list + idx,
+              sizeof(void*)*(sl->num_used-idx));
+    sl->num_used++;
+    sl->list[idx] = val;
+  }
+}
+
+/**
+ * Split a string <b>str</b> along all occurrences of <b>sep</b>,
+ * appending the (newly allocated) split strings, in order, to
+ * <b>sl</b>.  Return the number of strings added to <b>sl</b>.
+ *
+ * If <b>flags</b>&amp;SPLIT_SKIP_SPACE is true, remove initial and
+ * trailing space from each entry.
+ * If <b>flags</b>&amp;SPLIT_IGNORE_BLANK is true, remove any entries
+ * of length 0.
+ * If <b>flags</b>&amp;SPLIT_STRIP_SPACE is true, strip spaces from each
+ * split string.
+ *
+ * If <b>max</b>>0, divide the string into no more than <b>max</b> pieces. If
+ * <b>sep</b> is NULL, split on any sequence of horizontal space.
+ */
+int
+smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
+                       int flags, int max)
+{
+  const char *cp, *end, *next;
+  int n = 0;
+
+  obfs_assert(sl);
+  obfs_assert(str);
+
+  cp = str;
+  while (1) {
+    if (flags&SPLIT_SKIP_SPACE) {
+      while (ascii_isspace(*cp)) ++cp;
+    }
+
+    if (max>0 && n == max-1) {
+      end = strchr(cp,'\0');
+    } else if (sep) {
+      end = strstr(cp,sep);
+      if (!end)
+        end = strchr(cp,'\0');
+    } else {
+      for (end = cp; *end && *end != '\t' && *end != ' '; ++end)
+        ;
+    }
+
+    obfs_assert(end);
+
+    if (!*end) {
+      next = NULL;
+    } else if (sep) {
+      next = end+strlen(sep);
+    } else {
+      next = end+1;
+      while (*next == '\t' || *next == ' ')
+        ++next;
+    }
+
+    if (flags&SPLIT_SKIP_SPACE) {
+      while (end > cp && ascii_isspace(*(end-1)))
+        --end;
+    }
+    if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
+      char *string = xstrndup(cp, end-cp);
+      if (flags&SPLIT_STRIP_SPACE)
+        ascii_strstrip(string, " ");
+      smartlist_add(sl, string);
+      ++n;
+    }
+    if (!next)
+      break;
+    cp = next;
+  }
+
+  return n;
+}
+
+/** Allocate and return a new string containing the concatenation of
+ * the elements of <b>sl</b>, in order, separated by <b>join</b>.  If
+ * <b>terminate</b> is true, also terminate the string with <b>join</b>.
+ * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
+ * the returned string. Requires that every element of <b>sl</b> is
+ * NUL-terminated string.
+ */
+char *
+smartlist_join_strings(smartlist_t *sl, const char *join,
+                       int terminate, size_t *len_out)
+{
+  return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
+}
+
+/** As smartlist_join_strings, but instead of separating/terminated with a
+ * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
+ * at <b>join</b>.  (Useful for generating a sequence of NUL-terminated
+ * strings.)
+ */
+char *
+smartlist_join_strings2(smartlist_t *sl, const char *join,
+                        size_t join_len, int terminate, size_t *len_out)
+{
+  int i;
+  size_t n = 0;
+  char *r = NULL, *dst, *src;
+
+  obfs_assert(sl);
+  obfs_assert(join);
+
+  if (terminate)
+    n = join_len;
+
+  for (i = 0; i < sl->num_used; ++i) {
+    n += strlen(sl->list[i]);
+    if (i+1 < sl->num_used) /* avoid double-counting the last one */
+      n += join_len;
+  }
+  dst = r = xmalloc(n+1);
+  for (i = 0; i < sl->num_used; ) {
+    for (src = sl->list[i]; *src; )
+      *dst++ = *src++;
+    if (++i < sl->num_used) {
+      memcpy(dst, join, join_len);
+      dst += join_len;
+    }
+  }
+  if (terminate) {
+    memcpy(dst, join, join_len);
+    dst += join_len;
+  }
+  *dst = '\0';
+
+  if (len_out)
+    *len_out = dst-r;
+  return r;
+}
+
+/** Sort the members of <b>sl</b> into an order defined by
+ * the ordering function <b>compare</b>, which returns less then 0 if a
+ * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
+ */
+void
+smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
+{
+  if (!sl->num_used)
+    return;
+  qsort(sl->list, sl->num_used, sizeof(void*),
+        (int (*)(const void *,const void*))compare);
+}
+
+/** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
+ * return the most frequent member in the list.  Break ties in favor of
+ * later elements.  If the list is empty, return NULL.
+ */
+void *
+smartlist_get_most_frequent(const smartlist_t *sl,
+                            int (*compare)(const void **a, const void **b))
+{
+  const void *most_frequent = NULL;
+  int most_frequent_count = 0;
+
+  const void *cur = NULL;
+  int i, count=0;
+
+  if (!sl->num_used)
+    return NULL;
+  for (i = 0; i < sl->num_used; ++i) {
+    const void *item = sl->list[i];
+    if (cur && 0 == compare(&cur, &item)) {
+      ++count;
+    } else {
+      if (cur && count >= most_frequent_count) {
+        most_frequent = cur;
+        most_frequent_count = count;
+      }
+      cur = item;
+      count = 1;
+    }
+  }
+  if (cur && count >= most_frequent_count) {
+    most_frequent = cur;
+    most_frequent_count = count;
+  }
+  return (void*)most_frequent;
+}
+
+/** Given a sorted smartlist <b>sl</b> and the comparison function used to
+ * sort it, remove all duplicate members.  If free_fn is provided, calls
+ * free_fn on each duplicate.  Otherwise, just removes them.  Preserves order.
+ */
+void
+smartlist_uniq(smartlist_t *sl,
+               int (*compare)(const void **a, const void **b),
+               void (*free_fn)(void *a))
+{
+  int i;
+  for (i=1; i < sl->num_used; ++i) {
+    if (compare((const void **)&(sl->list[i-1]),
+                (const void **)&(sl->list[i])) == 0) {
+      if (free_fn)
+        free_fn(sl->list[i]);
+      smartlist_del_keeporder(sl, i--);
+    }
+  }
+}
+
+/** Return a randomly chosen element of <b>sl</b>; or NULL if <b>sl</b>
+ * is empty. */
+
+void *
+smartlist_choose(const smartlist_t *sl)
+{
+  int len = smartlist_len(sl);
+  if (len)
+    return smartlist_get(sl, random_int(len));
+  return NULL; /* no elements to choose from */
+}
+
+/** Scramble the elements of <b>sl</b> into a random order. */
+void
+smartlist_shuffle(smartlist_t *sl)
+{
+  int i;
+
+  /* From the end of the list to the front, choose at random from the
+     positions we haven't looked at yet, and swap that position into the
+     current position.  Remember to give "no swap" the same probability as
+     any other swap. */
+  for (i = smartlist_len(sl)-1; i > 0; --i) {
+    int j = random_int(i+1);
+    smartlist_swap(sl, i, j);
+  }
+}
+
+
+/** Assuming the members of <b>sl</b> are in order, return a pointer to the
+ * member that matches <b>key</b>.  Ordering and matching are defined by a
+ * <b>compare</b> function that returns 0 on a match; less than 0 if key is
+ * less than member, and greater than 0 if key is greater then member.
+ */
+void *
+smartlist_bsearch(smartlist_t *sl, const void *key,
+                  int (*compare)(const void *key, const void **member))
+{
+  int found, idx;
+  idx = smartlist_bsearch_idx(sl, key, compare, &found);
+  return found ? smartlist_get(sl, idx) : NULL;
+}
+
+/** Assuming the members of <b>sl</b> are in order, return the index of the
+ * member that matches <b>key</b>.  If no member matches, return the index of
+ * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
+ * is greater than <b>key</b>.  Set <b>found_out</b> to true on a match, to
+ * false otherwise.  Ordering and matching are defined by a <b>compare</b>
+ * function that returns 0 on a match; less than 0 if key is less than member,
+ * and greater than 0 if key is greater then member.
+ */
+int
+smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
+                      int (*compare)(const void *key, const void **member),
+                      int *found_out)
+{
+  int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid;
+
+  while (lo <= hi) {
+    mid = (lo + hi) / 2;
+    cmp = compare(key, (const void**) &(sl->list[mid]));
+    if (cmp>0) { /* key > sl[mid] */
+      lo = mid+1;
+    } else if (cmp<0) { /* key < sl[mid] */
+      hi = mid-1;
+    } else { /* key == sl[mid] */
+      *found_out = 1;
+      return mid;
+    }
+  }
+  /* lo > hi. */
+  {
+    obfs_assert(lo >= 0);
+    if (lo < smartlist_len(sl)) {
+      cmp = compare(key, (const void**) &(sl->list[lo]));
+      obfs_assert(cmp < 0);
+    } else if (smartlist_len(sl)) {
+      cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1]));
+      obfs_assert(cmp > 0);
+    }
+  }
+  *found_out = 0;
+  return lo;
+}
+
+/** Helper: compare two const char **s. */
+static int
+_compare_string_ptrs(const void **_a, const void **_b)
+{
+  return strcmp((const char*)*_a, (const char*)*_b);
+}
+
+/** Sort a smartlist <b>sl</b> containing strings into lexically ascending
+ * order. */
+void
+smartlist_sort_strings(smartlist_t *sl)
+{
+  smartlist_sort(sl, _compare_string_ptrs);
+}
+
+/** Return the most frequent string in the sorted list <b>sl</b> */
+char *
+smartlist_get_most_frequent_string(smartlist_t *sl)
+{
+  return smartlist_get_most_frequent(sl, _compare_string_ptrs);
+}
+
+/** Remove duplicate strings from a sorted list, and free them with free().
+ */
+void
+smartlist_uniq_strings(smartlist_t *sl)
+{
+  smartlist_uniq(sl, _compare_string_ptrs, free);
+}
+
+/* Heap-based priority queue implementation for O(lg N) insert and remove.
+ * Recall that the heap property is that, for every index I, h[I] <
+ * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
+ *
+ * For us to remove items other than the topmost item, each item must store
+ * its own index within the heap.  When calling the pqueue functions, tell
+ * them about the offset of the field that stores the index within the item.
+ *
+ * Example:
+ *
+ *   typedef struct timer_t {
+ *     struct timeval tv;
+ *     int heap_index;
+ *   } timer_t;
+ *
+ *   static int compare(const void *p1, const void *p2) {
+ *     const timer_t *t1 = p1, *t2 = p2;
+ *     if (t1->tv.tv_sec < t2->tv.tv_sec) {
+ *        return -1;
+ *     } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
+ *        return 1;
+ *     } else {
+ *        return t1->tv.tv_usec - t2->tv_usec;
+ *     }
+ *   }
+ *
+ *   void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
+ *      smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index),
+ *         timer);
+ *   }
+ *
+ *   void timer_heap_pop(smartlist_t *heap) {
+ *      return smartlist_pqueue_pop(heap, compare,
+ *         STRUCT_OFFSET(timer_t, heap_index));
+ *   }
+ */
+
+/** @{ */
+/** Functions to manipulate heap indices to find a node's parent and children.
+ *
+ * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
+ *   = 2*x + 1.  But this is C, so we have to adjust a little. */
+//#define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
+//#define RIGHT_CHILD(i) ( ((i)+1)*2 )
+//#define PARENT(i)      ( ((i)+1)/2 - 1)
+#define LEFT_CHILD(i)  ( 2*(i) + 1 )
+#define RIGHT_CHILD(i) ( 2*(i) + 2 )
+#define PARENT(i)      ( ((i)-1) / 2 )
+/** }@ */
+
+/** @{ */
+/** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
+ * set to the offset of an integer index within the heap element structure,
+ * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to
+ * where p's index is stored.  Given additionally a local smartlist <b>sl</b>,
+ * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
+ * value (that is, to <b>i</b>).
+ */
+#define IDXP(p) ((int*)( ((char*)(p)) + idx_field_offset ))
+
+#define UPDATE_IDX(i)  do {                            \
+    void *updated = sl->list[i];                       \
+    *IDXP(updated) = i;                                \
+  } while (0)
+
+#define IDX_OF_ITEM(p) (*IDXP(p))
+/** @} */
+
+/** Helper. <b>sl</b> may have at most one violation of the heap property:
+ * the item at <b>idx</b> may be greater than one or both of its children.
+ * Restore the heap property. */
+static inline void
+smartlist_heapify(smartlist_t *sl,
+                  int (*compare)(const void *a, const void *b),
+                  int idx_field_offset,
+                  int idx)
+{
+  while (1) {
+    int left_idx = LEFT_CHILD(idx);
+    int best_idx;
+
+    if (left_idx >= sl->num_used)
+      return;
+    if (compare(sl->list[idx],sl->list[left_idx]) < 0)
+      best_idx = idx;
+    else
+      best_idx = left_idx;
+    if (left_idx+1 < sl->num_used &&
+        compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
+      best_idx = left_idx + 1;
+
+    if (best_idx == idx) {
+      return;
+    } else {
+      void *tmp = sl->list[idx];
+      sl->list[idx] = sl->list[best_idx];
+      sl->list[best_idx] = tmp;
+      UPDATE_IDX(idx);
+      UPDATE_IDX(best_idx);
+
+      idx = best_idx;
+    }
+  }
+}
+
+/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
+ * determined by <b>compare</b> and the offset of the item in the heap is
+ * stored in an int-typed field at position <b>idx_field_offset</b> within
+ * item.
+ */
+void
+smartlist_pqueue_add(smartlist_t *sl,
+                     int (*compare)(const void *a, const void *b),
+                     int idx_field_offset,
+                     void *item)
+{
+  int idx;
+  smartlist_add(sl,item);
+  UPDATE_IDX(sl->num_used-1);
+
+  for (idx = sl->num_used - 1; idx; ) {
+    int parent = PARENT(idx);
+    if (compare(sl->list[idx], sl->list[parent]) < 0) {
+      void *tmp = sl->list[parent];
+      sl->list[parent] = sl->list[idx];
+      sl->list[idx] = tmp;
+      UPDATE_IDX(parent);
+      UPDATE_IDX(idx);
+      idx = parent;
+    } else {
+      return;
+    }
+  }
+}
+
+/** Remove and return the top-priority item from the heap stored in <b>sl</b>,
+ * where order is determined by <b>compare</b> and the item's position is
+ * stored at position <b>idx_field_offset</b> within the item.  <b>sl</b> must
+ * not be empty. */
+void *
+smartlist_pqueue_pop(smartlist_t *sl,
+                     int (*compare)(const void *a, const void *b),
+                     int idx_field_offset)
+{
+  void *top;
+  obfs_assert(sl->num_used);
+
+  top = sl->list[0];
+  *IDXP(top)=-1;
+  if (--sl->num_used) {
+    sl->list[0] = sl->list[sl->num_used];
+    UPDATE_IDX(0);
+    smartlist_heapify(sl, compare, idx_field_offset, 0);
+  }
+  return top;
+}
+
+/** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
+ * where order is determined by <b>compare</b> and the item's position is
+ * stored at position <b>idx_field_offset</b> within the item.  <b>sl</b> must
+ * not be empty. */
+void
+smartlist_pqueue_remove(smartlist_t *sl,
+                        int (*compare)(const void *a, const void *b),
+                        int idx_field_offset,
+                        void *item)
+{
+  int idx = IDX_OF_ITEM(item);
+  obfs_assert(idx >= 0);
+  obfs_assert(sl->list[idx] == item);
+  --sl->num_used;
+  *IDXP(item) = -1;
+  if (idx == sl->num_used) {
+    return;
+  } else {
+    sl->list[idx] = sl->list[sl->num_used];
+    UPDATE_IDX(idx);
+    smartlist_heapify(sl, compare, idx_field_offset, idx);
+  }
+}
+
+/** Assert that the heap property is correctly maintained by the heap stored
+ * in <b>sl</b>, where order is determined by <b>compare</b>. */
+void
+smartlist_pqueue_assert_ok(smartlist_t *sl,
+                           int (*compare)(const void *a, const void *b),
+                           int idx_field_offset)
+{
+  int i;
+  for (i = sl->num_used - 1; i >= 0; --i) {
+    if (i>0)
+      obfs_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
+    obfs_assert(IDX_OF_ITEM(sl->list[i]) == i);
+  }
+}
+
+/** Helper: compare two SHA256_LENGTH digests. */
+static int
+_compare_digests(const void **_a, const void **_b)
+{
+  return memcmp((const char*)*_a, (const char*)*_b, SHA256_LENGTH);
+}
+
+/** Sort the list of SHA256_LENGTH-byte digests into ascending order. */
+void
+smartlist_sort_digests(smartlist_t *sl)
+{
+  smartlist_sort(sl, _compare_digests);
+}
+
+/** Remove duplicate digests from a sorted list, and free them with free().
+ */
+void
+smartlist_uniq_digests(smartlist_t *sl)
+{
+  smartlist_uniq(sl, _compare_digests, free);
+}
+
+/** 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[SHA256_LENGTH], digestmap_);
+
+/** 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 ht_string_hash(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 !memcmp(a->key, b->key, SHA256_LENGTH);
+}
+
+/** Helper: return a hash value for a digest_map_t. */
+static inline unsigned int
+digestmap_entry_hash(const digestmap_entry_t *a)
+{
+#if SIZEOF_INT != 8
+  const uint32_t *p = (const uint32_t*)a->key;
+  return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
+#else
+  const uint64_t *p = (const uint64_t*)a->key;
+  return p[0] ^ p[1];
+#endif
+}
+
+HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
+             strmap_entries_eq)
+HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
+            strmap_entries_eq, 0.6, malloc, realloc, free)
+
+HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
+             digestmap_entries_eq)
+HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
+            digestmap_entries_eq, 0.6, malloc, realloc, free)
+
+/** Constructor to create a new empty map from strings to void*'s.
+ */
+strmap_t *
+strmap_new(void)
+{
+  strmap_t *result;
+  result = xmalloc(sizeof(strmap_t));
+  HT_INIT(strmap_impl, &result->head);
+  return result;
+}
+
+/** Constructor to create a new empty map from digests to void*'s.
+ */
+digestmap_t *
+digestmap_new(void)
+{
+  digestmap_t *result;
+  result = xmalloc(sizeof(digestmap_t));
+  HT_INIT(digestmap_impl, &result->head);
+  return result;
+}
+
+/** Set the current value for <b>key</b> to <b>val</b>.  Returns the previous
+ * value for <b>key</b> if one was set, or NULL if one was not.
+ *
+ * This function makes a copy of <b>key</b> if necessary, but not of
+ * <b>val</b>.
+ */
+void *
+strmap_set(strmap_t *map, const char *key, void *val)
+{
+  strmap_entry_t *resolve;
+  strmap_entry_t search;
+  void *oldval;
+  obfs_assert(map);
+  obfs_assert(key);
+  obfs_assert(val);
+  search.key = (char*)key;
+  resolve = HT_FIND(strmap_impl, &map->head, &search);
+  if (resolve) {
+    oldval = resolve->val;
+    resolve->val = val;
+    return oldval;
+  } else {
+    resolve = xzalloc(sizeof(strmap_entry_t));
+    resolve->key = xstrdup(key);
+    resolve->val = val;
+    obfs_assert(!HT_FIND(strmap_impl, &map->head, resolve));
+    HT_INSERT(strmap_impl, &map->head, resolve);
+    return NULL;
+  }
+}
+
+#define OPTIMIZED_DIGESTMAP_SET
+
+/** Like strmap_set() above but for digestmaps. */
+void *
+digestmap_set(digestmap_t *map, const char *key, void *val)
+{
+#ifndef OPTIMIZED_DIGESTMAP_SET
+  digestmap_entry_t *resolve;
+#endif
+  digestmap_entry_t search;
+  void *oldval;
+  obfs_assert(map);
+  obfs_assert(key);
+  obfs_assert(val);
+  memcpy(&search.key, key, SHA256_LENGTH);
+#ifndef OPTIMIZED_DIGESTMAP_SET
+  resolve = HT_FIND(digestmap_impl, &map->head, &search);
+  if (resolve) {
+    oldval = resolve->val;
+    resolve->val = val;
+    return oldval;
+  } else {
+    resolve = xzalloc(sizeof(digestmap_entry_t));
+    memcpy(resolve->key, key, SHA256_LENGTH);
+    resolve->val = val;
+    HT_INSERT(digestmap_impl, &map->head, resolve);
+    return NULL;
+  }
+#else
+  /* We spend up to 5% 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 do in the unoptimized code above.  (Each of
+   * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
+   */
+  _HT_FIND_OR_INSERT(digestmap_impl, node, digestmap_entry_hash, &(map->head),
+         digestmap_entry_t, &search, ptr,
+         {
+            /* we found an entry. */
+            oldval = (*ptr)->val;
+            (*ptr)->val = val;
+            return oldval;
+         },
+         {
+           /* We didn't find the entry. */
+           digestmap_entry_t *newent =
+             xzalloc(sizeof(digestmap_entry_t));
+           memcpy(newent->key, key, SHA256_LENGTH);
+           newent->val = val;
+           _HT_FOI_INSERT(node, &(map->head), &search, newent, ptr);
+           return NULL;
+         });
+#endif
+}
+
+/** Return the current value associated with <b>key</b>, or NULL if no
+ * value is set.
+ */
+void *
+strmap_get(const strmap_t *map, const char *key)
+{
+  strmap_entry_t *resolve;
+  strmap_entry_t search;
+  obfs_assert(map);
+  obfs_assert(key);
+  search.key = (char*)key;
+  resolve = HT_FIND(strmap_impl, &map->head, &search);
+  if (resolve) {
+    return resolve->val;
+  } else {
+    return NULL;
+  }
+}
+
+/** Like strmap_get() above but for digestmaps. */
+void *
+digestmap_get(const digestmap_t *map, const char *key)
+{
+  digestmap_entry_t *resolve;
+  digestmap_entry_t search;
+  obfs_assert(map);
+  obfs_assert(key);
+  memcpy(&search.key, key, SHA256_LENGTH);
+  resolve = HT_FIND(digestmap_impl, &map->head, &search);
+  if (resolve) {
+    return resolve->val;
+  } else {
+    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 *
+strmap_remove(strmap_t *map, const char *key)
+{
+  strmap_entry_t *resolve;
+  strmap_entry_t search;
+  void *oldval;
+  obfs_assert(map);
+  obfs_assert(key);
+  search.key = (char*)key;
+  resolve = HT_REMOVE(strmap_impl, &map->head, &search);
+  if (resolve) {
+    oldval = resolve->val;
+    free(resolve->key);
+    free(resolve);
+    return oldval;
+  } else {
+    return NULL;
+  }
+}
+
+/** Like strmap_remove() above but for digestmaps. */
+void *
+digestmap_remove(digestmap_t *map, const char *key)
+{
+  digestmap_entry_t *resolve;
+  digestmap_entry_t search;
+  void *oldval;
+  obfs_assert(map);
+  obfs_assert(key);
+  memcpy(&search.key, key, SHA256_LENGTH);
+  resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
+  if (resolve) {
+    oldval = resolve->val;
+    free(resolve);
+    return oldval;
+  } else {
+    return NULL;
+  }
+}
+
+/** 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 = xstrdup(key);
+  ascii_strlower(lc_key);
+  v = strmap_set(map,lc_key,val);
+  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 = xstrdup(key);
+  ascii_strlower(lc_key);
+  v = strmap_get(map,lc_key);
+  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 = xstrdup(key);
+  ascii_strlower(lc_key);
+  v = strmap_remove(map,lc_key);
+  free(lc_key);
+  return v;
+}
+
+/** 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);
+ *       iter = strmap_iter_next(map,iter);
+ *    }
+ * }
+ * \endcode
+ *
+ */
+strmap_iter_t *
+strmap_iter_init(strmap_t *map)
+{
+  obfs_assert(map);
+  return HT_START(strmap_impl, &map->head);
+}
+
+/** Start iterating through <b>map</b>.  See strmap_iter_init() for example. */
+digestmap_iter_t *
+digestmap_iter_init(digestmap_t *map)
+{
+  obfs_assert(map);
+  return HT_START(digestmap_impl, &map->head);
+}
+
+/** Advance the iterator <b>iter</b> for <b>map</b> a single step to the next
+ * entry, and return its new value. */
+strmap_iter_t *
+strmap_iter_next(strmap_t *map, strmap_iter_t *iter)
+{
+  obfs_assert(map);
+  obfs_assert(iter);
+  return HT_NEXT(strmap_impl, &map->head, iter);
+}
+
+/** Advance the iterator <b>iter</b> for map a single step to the next entry,
+ * and return its new value. */
+digestmap_iter_t *
+digestmap_iter_next(digestmap_t *map, digestmap_iter_t *iter)
+{
+  obfs_assert(map);
+  obfs_assert(iter);
+  return HT_NEXT(digestmap_impl, &map->head, iter);
+}
+
+/** Advance the iterator <b>iter</b> a single step to the next entry, removing
+ * the current entry, and return its new value.
+ */
+strmap_iter_t *
+strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter)
+{
+  strmap_entry_t *rmv;
+  obfs_assert(map);
+  obfs_assert(iter);
+  obfs_assert(*iter);
+  rmv = *iter;
+  iter = HT_NEXT_RMV(strmap_impl, &map->head, iter);
+  free(rmv->key);
+  free(rmv);
+  return iter;
+}
+
+/** Advance the iterator <b>iter</b> a single step to the next entry, removing
+ * the current entry, and return its new value.
+ */
+digestmap_iter_t *
+digestmap_iter_next_rmv(digestmap_t *map, digestmap_iter_t *iter)
+{
+  digestmap_entry_t *rmv;
+  obfs_assert(map);
+  obfs_assert(iter);
+  obfs_assert(*iter);
+  rmv = *iter;
+  iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter);
+  free(rmv);
+  return iter;
+}
+
+/** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
+ * iter. */
+void
+strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp)
+{
+  obfs_assert(iter);
+  obfs_assert(*iter);
+  obfs_assert(keyp);
+  obfs_assert(valp);
+  *keyp = (*iter)->key;
+  *valp = (*iter)->val;
+}
+
+/** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
+ * iter. */
+void
+digestmap_iter_get(digestmap_iter_t *iter, const char **keyp, void **valp)
+{
+  obfs_assert(iter);
+  obfs_assert(*iter);
+  obfs_assert(keyp);
+  obfs_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
+strmap_iter_done(strmap_iter_t *iter)
+{
+  return iter == NULL;
+}
+
+/** Return true iff <b>iter</b> has advanced past the last entry of
+ * <b>map</b>. */
+int
+digestmap_iter_done(digestmap_iter_t *iter)
+{
+  return iter == NULL;
+}
+
+/** Remove all entries from <b>map</b>, and deallocate storage for those
+ * entries.  If free_val is provided, it is invoked on every value in
+ * <b>map</b>.
+ */
+void
+strmap_free(strmap_t *map, void (*free_val)(void*))
+{
+  strmap_entry_t **ent, **next, *this;
+  if (!map)
+    return;
+
+  for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) {
+    this = *ent;
+    next = HT_NEXT_RMV(strmap_impl, &map->head, ent);
+    free(this->key);
+    if (free_val)
+      free_val(this->val);
+    free(this);
+  }
+  obfs_assert(HT_EMPTY(&map->head));
+  HT_CLEAR(strmap_impl, &map->head);
+  free(map);
+}
+
+/** Remove all entries from <b>map</b>, and deallocate storage for those
+ * entries.  If free_val is provided, it is invoked on every value in
+ * <b>map</b>.
+ */
+void
+digestmap_free(digestmap_t *map, void (*free_val)(void*))
+{
+  digestmap_entry_t **ent, **next, *this;
+  if (!map)
+    return;
+  for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) {
+    this = *ent;
+    next = HT_NEXT_RMV(digestmap_impl, &map->head, ent);
+    if (free_val)
+      free_val(this->val);
+    free(this);
+  }
+  obfs_assert(HT_EMPTY(&map->head));
+  HT_CLEAR(digestmap_impl, &map->head);
+  free(map);
+}
+
+/** Fail with an assertion error if anything has gone wrong with the internal
+ * representation of <b>map</b>. */
+void
+strmap_assert_ok(const strmap_t *map)
+{
+  obfs_assert(!_strmap_impl_HT_REP_IS_BAD(&map->head));
+}
+/** Fail with an assertion error if anything has gone wrong with the internal
+ * representation of <b>map</b>. */
+void
+digestmap_assert_ok(const digestmap_t *map)
+{
+  obfs_assert(!_digestmap_impl_HT_REP_IS_BAD(&map->head));
+}
+
+/** Return true iff <b>map</b> has no entries. */
+int
+strmap_isempty(const strmap_t *map)
+{
+  return HT_EMPTY(&map->head);
+}
+
+/** Return true iff <b>map</b> has no entries. */
+int
+digestmap_isempty(const digestmap_t *map)
+{
+  return HT_EMPTY(&map->head);
+}
+
+/** Return the number of items in <b>map</b>. */
+int
+strmap_size(const strmap_t *map)
+{
+  return HT_SIZE(&map->head);
+}
+
+/** Return the number of items in <b>map</b>. */
+int
+digestmap_size(const digestmap_t *map)
+{
+  return HT_SIZE(&map->head);
+}
+
+/** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
+ * function for an array of type <b>elt_t</b>*.
+ *
+ * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding
+ * the kth element of an n-element list can be done in O(n).  Then again, this
+ * implementation is not in critical path, and it is obviously correct. */
+#define IMPLEMENT_ORDER_FUNC(funcname, elt_t)                   \
+  static int                                                    \
+  _cmp_ ## elt_t(const void *_a, const void *_b)                \
+  {                                                             \
+    const elt_t *a = _a, *b = _b;                               \
+    if (*a<*b)                                                  \
+      return -1;                                                \
+    else if (*a>*b)                                             \
+      return 1;                                                 \
+    else                                                        \
+      return 0;                                                 \
+  }                                                             \
+  elt_t                                                         \
+  funcname(elt_t *array, int n_elements, int nth)               \
+  {                                                             \
+    obfs_assert(nth >= 0);                                       \
+    obfs_assert(nth < n_elements);                               \
+    qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t);     \
+    return array[nth];                                          \
+  }
+
+IMPLEMENT_ORDER_FUNC(find_nth_int, int)
+IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
+IMPLEMENT_ORDER_FUNC(find_nth_double, double)
+IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
+IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
+IMPLEMENT_ORDER_FUNC(find_nth_long, long)
+
+/** Return a newly allocated digestset_t, optimized to hold a total of
+ * <b>max_elements</b> digests with a reasonably low false positive weight. */
+digestset_t *
+digestset_new(int max_elements)
+{
+  /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
+   * is the number of hash functions per entry, m is the bits in the array,
+   * and n is the number of elements inserted.  For us, k==4, n<=max_elements,
+   * and m==n_bits= approximately max_elements*32.  This gives
+   *   P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
+   *
+   * It would be more optimal in space vs false positives to get this false
+   * positive rate by going for k==13, and m==18.5n, but we also want to
+   * conserve CPU, and k==13 is pretty big.
+   */
+  int n_bits = 1u << (ui64_log2(max_elements)+5);
+  digestset_t *r = xmalloc(sizeof(digestset_t));
+  r->mask = n_bits - 1;
+  r->ba = bitarray_init_zero(n_bits);
+  return r;
+}
+
+/** Free all storage held in <b>set</b>. */
+void
+digestset_free(digestset_t *set)
+{
+  if (!set)
+    return;
+  bitarray_free(set->ba);
+  free(set);
+}
diff --git a/src/container.h b/src/container.h
new file mode 100644
index 0000000..e1c1a07
--- /dev/null
+++ b/src/container.h
@@ -0,0 +1,685 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2011, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef CONTAINER_H
+#define CONTAINER_H
+
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+/** A resizeable list of pointers, with associated helpful functionality.
+ *
+ * The members of this struct are exposed only so that macros and inlines can
+ * use them; all access to smartlist internals should go through the functions
+ * and macros defined here.
+ **/
+typedef struct smartlist_t {
+  /** @{ */
+  /** <b>list</b> has enough capacity to store exactly <b>capacity</b> elements
+   * before it needs to be resized.  Only the first <b>num_used</b> (<=
+   * capacity) elements point to valid data.
+   */
+  void **list;
+  int num_used;
+  int capacity;
+  /** @} */
+} smartlist_t;
+
+smartlist_t *smartlist_create(void);
+void smartlist_free(smartlist_t *sl);
+void smartlist_clear(smartlist_t *sl);
+void smartlist_add(smartlist_t *sl, void *element);
+void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2);
+void smartlist_remove(smartlist_t *sl, const void *element);
+void *smartlist_pop_last(smartlist_t *sl);
+void smartlist_reverse(smartlist_t *sl);
+void smartlist_string_remove(smartlist_t *sl, const char *element);
+int smartlist_isin(const smartlist_t *sl, const void *element) ATTR_PURE;
+int smartlist_string_isin(const smartlist_t *sl, const char *element)
+  ATTR_PURE;
+int smartlist_string_pos(const smartlist_t *, const char *elt) ATTR_PURE;
+int smartlist_string_isin_case(const smartlist_t *sl, const char *element)
+  ATTR_PURE;
+int smartlist_string_num_isin(const smartlist_t *sl, int num) ATTR_PURE;
+int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
+  ATTR_PURE;
+int smartlist_digest_isin(const smartlist_t *sl, const char *element)
+  ATTR_PURE;
+int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
+  ATTR_PURE;
+void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2);
+void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2);
+
+#ifdef DEBUG_SMARTLIST
+/** Return the number of items in sl.
+ */
+static inline int smartlist_len(const smartlist_t *sl) ATTR_PURE;
+static inline int smartlist_len(const smartlist_t *sl) {
+  tor_assert(sl);
+  return (sl)->num_used;
+}
+/** Return the <b>idx</b>th element of sl.
+ */
+static inline void *smartlist_get(const smartlist_t *sl, int idx) ATTR_PURE;
+static inline void *smartlist_get(const smartlist_t *sl, int idx) {
+  tor_assert(sl);
+  tor_assert(idx>=0);
+  tor_assert(sl->num_used > idx);
+  return sl->list[idx];
+}
+static inline void smartlist_set(smartlist_t *sl, int idx, void *val) {
+  tor_assert(sl);
+  tor_assert(idx>=0);
+  tor_assert(sl->num_used > idx);
+  sl->list[idx] = val;
+}
+#else
+#define smartlist_len(sl) ((sl)->num_used)
+#define smartlist_get(sl, idx) ((sl)->list[idx])
+#define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val))
+#endif
+
+/** Exchange the elements at indices <b>idx1</b> and <b>idx2</b> of the
+ * smartlist <b>sl</b>. */
+static inline void smartlist_swap(smartlist_t *sl, int idx1, int idx2)
+{
+  if (idx1 != idx2) {
+    void *elt = smartlist_get(sl, idx1);
+    smartlist_set(sl, idx1, smartlist_get(sl, idx2));
+    smartlist_set(sl, idx2, elt);
+  }
+}
+
+void smartlist_del(smartlist_t *sl, int idx);
+void smartlist_del_keeporder(smartlist_t *sl, int idx);
+void smartlist_insert(smartlist_t *sl, int idx, void *val);
+void smartlist_sort(smartlist_t *sl,
+                    int (*compare)(const void **a, const void **b));
+void *smartlist_get_most_frequent(const smartlist_t *sl,
+                    int (*compare)(const void **a, const void **b));
+void smartlist_uniq(smartlist_t *sl,
+                    int (*compare)(const void **a, const void **b),
+                    void (*free_fn)(void *elt));
+
+void smartlist_shuffle(smartlist_t *sl);
+void *smartlist_choose(const smartlist_t *sl);
+
+void smartlist_sort_strings(smartlist_t *sl);
+void smartlist_sort_digests(smartlist_t *sl);
+
+char *smartlist_get_most_frequent_string(smartlist_t *sl);
+
+void smartlist_uniq_strings(smartlist_t *sl);
+void smartlist_uniq_digests(smartlist_t *sl);
+void *smartlist_bsearch(smartlist_t *sl, const void *key,
+                        int (*compare)(const void *key, const void **member))
+  ATTR_PURE;
+int smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
+                          int (*compare)(const void *key, const void **member),
+                          int *found_out);
+
+void smartlist_pqueue_add(smartlist_t *sl,
+                          int (*compare)(const void *a, const void *b),
+                          int idx_field_offset,
+                          void *item);
+void *smartlist_pqueue_pop(smartlist_t *sl,
+                           int (*compare)(const void *a, const void *b),
+                           int idx_field_offset);
+void smartlist_pqueue_remove(smartlist_t *sl,
+                             int (*compare)(const void *a, const void *b),
+                             int idx_field_offset,
+                             void *item);
+void smartlist_pqueue_assert_ok(smartlist_t *sl,
+                                int (*compare)(const void *a, const void *b),
+                                int idx_field_offset);
+
+#define SPLIT_SKIP_SPACE   0x01
+#define SPLIT_IGNORE_BLANK 0x02
+#define SPLIT_STRIP_SPACE  0x04
+int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
+                           int flags, int max);
+char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate,
+                             size_t *len_out) ATTR_MALLOC;
+char *smartlist_join_strings2(smartlist_t *sl, const char *join,
+                              size_t join_len, int terminate, size_t *len_out)
+  ATTR_MALLOC;
+
+/** Iterate over the items in a smartlist <b>sl</b>, in order.  For each item,
+ * assign it to a new local variable of type <b>type</b> named <b>var</b>, and
+ * execute the statement <b>cmd</b>.  Inside the loop, the loop index can
+ * be accessed as <b>var</b>_sl_idx and the length of the list can be accessed
+ * as <b>var</b>_sl_len.
+ *
+ * NOTE: Do not change the length of the list while the loop is in progress,
+ * unless you adjust the _sl_len variable correspondingly.  See second example
+ * below.
+ *
+ * Example use:
+ * <pre>
+ *   smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
+ *   SMARTLIST_FOREACH(list, char *, cp,
+ *   {
+ *     printf("%d: %s\n", cp_sl_idx, cp);
+ *     free(cp);
+ *   });
+ *   smartlist_free(list);
+ * </pre>
+ *
+ * Example use (advanced):
+ * <pre>
+ *   SMARTLIST_FOREACH(list, char *, cp,
+ *   {
+ *     if (!strcmp(cp, "junk")) {
+ *       free(cp);
+ *       SMARTLIST_DEL_CURRENT(list, cp);
+ *     }
+ *   });
+ * </pre>
+ */
+/* Note: these macros use token pasting, and reach into smartlist internals.
+ * This can make them a little daunting. Here's the approximate unpacking of
+ * the above examples, for entertainment value:
+ *
+ * <pre>
+ * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
+ * {
+ *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
+ *   char *cp;
+ *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
+ *     cp = smartlist_get(list, cp_sl_idx);
+ *     printf("%d: %s\n", cp_sl_idx, cp);
+ *     free(cp);
+ *   }
+ * }
+ * smartlist_free(list);
+ * </pre>
+ *
+ * <pre>
+ * {
+ *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
+ *   char *cp;
+ *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
+ *     cp = smartlist_get(list, cp_sl_idx);
+ *     if (!strcmp(cp, "junk")) {
+ *       free(cp);
+ *       smartlist_del(list, cp_sl_idx);
+ *       --cp_sl_idx;
+ *       --cp_sl_len;
+ *     }
+ *   }
+ * }
+ * </pre>
+ */
+#define SMARTLIST_FOREACH_BEGIN(sl, type, var)  \
+  do {                                                          \
+    int var ## _sl_idx, var ## _sl_len=(sl)->num_used;          \
+    type var;                                                   \
+    for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len;   \
+         ++var ## _sl_idx) {                                    \
+      var = (sl)->list[var ## _sl_idx];
+
+#define SMARTLIST_FOREACH_END(var)              \
+    var = NULL;                                 \
+  } } while (0)
+
+#define SMARTLIST_FOREACH(sl, type, var, cmd)                   \
+  SMARTLIST_FOREACH_BEGIN(sl,type,var) {                        \
+    cmd;                                                        \
+  } SMARTLIST_FOREACH_END(var)
+
+/** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
+ * with the variable <b>var</b>, remove the current element in a way that
+ * won't confuse the loop. */
+#define SMARTLIST_DEL_CURRENT(sl, var)          \
+  do {                                          \
+    smartlist_del(sl, var ## _sl_idx);          \
+    --var ## _sl_idx;                           \
+    --var ## _sl_len;                           \
+  } while (0)
+
+/** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
+ * with the variable <b>var</b>, replace the current element with <b>val</b>.
+ * Does not deallocate the current value of <b>var</b>.
+ */
+#define SMARTLIST_REPLACE_CURRENT(sl, var, val) \
+  do {                                          \
+    smartlist_set(sl, var ## _sl_idx, val);     \
+  } while (0)
+
+/* Helper: Given two lists of items, possibly of different types, such that
+ * both lists are sorted on some common field (as determined by a comparison
+ * expression <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no
+ * duplicates on the common field, loop through the lists in lockstep, and
+ * execute <b>unmatched_var2</b> on items in var2 that do not appear in
+ * var1.
+ *
+ * WARNING: It isn't safe to add remove elements from either list while the
+ * loop is in progress.
+ *
+ * Example use:
+ *  SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs,
+ *                     routerinfo_list, routerinfo_t *, ri,
+ *                    memcmp(rs->identity_digest, ri->identity_digest, 20),
+ *                     log_info(LD_GENERAL,"No match for %s", ri->nickname)) {
+ *    log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs);
+ * } SMARTLIST_FOREACH_JOIN_END(rs, ri);
+ **/
+/* The example above unpacks (approximately) to:
+ *  int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list);
+ *  int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list);
+ *  int rs_ri_cmp;
+ *  routerstatus_t *rs;
+ *  routerinfo_t *ri;
+ *  for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) {
+ *    ri = smartlist_get(routerinfo_list, ri_sl_idx);
+ *    while (rs_sl_idx < rs_sl_len) {
+ *      rs = smartlist_get(routerstatus_list, rs_sl_idx);
+ *      rs_ri_cmp = memcmp(rs->identity_digest, ri->identity_digest, 20);
+ *      if (rs_ri_cmp > 0) {
+ *        break;
+ *      } else if (rs_ri_cmp == 0) {
+ *        goto matched_ri;
+ *      } else {
+ *        ++rs_sl_idx;
+ *      }
+ *    }
+ *    log_info(LD_GENERAL,"No match for %s", ri->nickname);
+ *    continue;
+ *   matched_ri: {
+ *    log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs);
+ *    }
+ *  }
+ */
+#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2,      \
+                                cmpexpr, unmatched_var2)                \
+  do {                                                                  \
+  int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used;             \
+  int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used;             \
+  int var1 ## _ ## var2 ## _cmp;                                        \
+  type1 var1;                                                           \
+  type2 var2;                                                           \
+  for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) {              \
+    var2 = (sl2)->list[var2##_sl_idx];                                  \
+    while (var1##_sl_idx < var1##_sl_len) {                             \
+      var1 = (sl1)->list[var1##_sl_idx];                                \
+      var1##_##var2##_cmp = (cmpexpr);                                  \
+      if (var1##_##var2##_cmp > 0) {                                    \
+        break;                                                          \
+      } else if (var1##_##var2##_cmp == 0) {                            \
+        goto matched_##var2;                                            \
+      } else {                                                          \
+        ++var1##_sl_idx;                                                \
+      }                                                                 \
+    }                                                                   \
+    /* Ran out of v1, or no match for var2. */                          \
+    unmatched_var2;                                                     \
+    continue;                                                           \
+    matched_##var2: ;                                                   \
+
+#define SMARTLIST_FOREACH_JOIN_END(var1, var2)  \
+  }                                             \
+  } while (0)
+
+#define DECLARE_MAP_FNS(maptype, keytype, prefix)                       \
+  typedef struct maptype maptype;                                       \
+  typedef struct prefix##entry_t *prefix##iter_t;                       \
+  maptype* prefix##new(void);                                           \
+  void* prefix##set(maptype *map, keytype key, void *val);              \
+  void* prefix##get(const maptype *map, keytype key);                   \
+  void* prefix##remove(maptype *map, keytype key);                      \
+  void prefix##free(maptype *map, void (*free_val)(void*));             \
+  int prefix##isempty(const maptype *map);                              \
+  int prefix##size(const maptype *map);                                 \
+  prefix##iter_t *prefix##iter_init(maptype *map);                      \
+  prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \
+  prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \
+  void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \
+  int prefix##iter_done(prefix##iter_t *iter);                          \
+  void prefix##assert_ok(const maptype *map)
+
+/* Map from const char * to void *. Implemented with a hash table. */
+DECLARE_MAP_FNS(strmap_t, const char *, strmap_);
+/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */
+DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_);
+
+#undef DECLARE_MAP_FNS
+
+/** Iterates over the key-value pairs in a map <b>map</b> in order.
+ * <b>prefix</b> is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_).
+ * The map's keys and values are of type keytype and valtype respectively;
+ * each iteration assigns them to keyvar and valvar.
+ *
+ * Example use:
+ *   MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
+ *     // use k and r
+ *   } MAP_FOREACH_END.
+ */
+/* Unpacks to, approximately:
+ * {
+ *   digestmap_iter_t *k_iter;
+ *   for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
+ *        k_iter = digestmap_iter_next(m, k_iter)) {
+ *     const char *k;
+ *     void *r_voidp;
+ *     routerinfo_t *r;
+ *     digestmap_iter_get(k_iter, &k, &r_voidp);
+ *     r = r_voidp;
+ *     // use k and r
+ *   }
+ * }
+ */
+#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar)      \
+  do {                                                                  \
+    prefix##iter_t *keyvar##_iter;                                      \
+    for (keyvar##_iter = prefix##iter_init(map);                        \
+         !prefix##iter_done(keyvar##_iter);                             \
+         keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) {       \
+      keytype keyvar;                                                   \
+      void *valvar##_voidp;                                             \
+      valtype valvar;                                                   \
+      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
+      valvar = valvar##_voidp;
+
+/** As MAP_FOREACH, except allows members to be removed from the map
+ * during the iteration via MAP_DEL_CURRENT.  Example use:
+ *
+ * Example use:
+ *   MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
+ *      if (is_very_old(r))
+ *       MAP_DEL_CURRENT(k);
+ *   } MAP_FOREACH_END.
+ **/
+/* Unpacks to, approximately:
+ * {
+ *   digestmap_iter_t *k_iter;
+ *   int k_del=0;
+ *   for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
+ *        k_iter = k_del ? digestmap_iter_next(m, k_iter)
+ *                       : digestmap_iter_next_rmv(m, k_iter)) {
+ *     const char *k;
+ *     void *r_voidp;
+ *     routerinfo_t *r;
+ *     k_del=0;
+ *     digestmap_iter_get(k_iter, &k, &r_voidp);
+ *     r = r_voidp;
+ *     if (is_very_old(r)) {
+ *       k_del = 1;
+ *     }
+ *   }
+ * }
+ */
+#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \
+  do {                                                                  \
+    prefix##iter_t *keyvar##_iter;                                      \
+    int keyvar##_del=0;                                                 \
+    for (keyvar##_iter = prefix##iter_init(map);                        \
+         !prefix##iter_done(keyvar##_iter);                             \
+         keyvar##_iter = keyvar##_del ?                                 \
+           prefix##iter_next_rmv(map, keyvar##_iter) :                  \
+           prefix##iter_next(map, keyvar##_iter)) {                     \
+      keytype keyvar;                                                   \
+      void *valvar##_voidp;                                             \
+      valtype valvar;                                                   \
+      keyvar##_del=0;                                                   \
+      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
+      valvar = valvar##_voidp;
+
+/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon
+ * member of the map.  */
+#define MAP_DEL_CURRENT(keyvar)                   \
+  do {                                            \
+    keyvar##_del = 1;                             \
+  } while (0)
+
+/** Used to end a MAP_FOREACH() block. */
+#define MAP_FOREACH_END } while (0)
+
+/** As MAP_FOREACH, but does not require declaration of prefix or keytype.
+ * Example use:
+ *   DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) {
+ *     // use k and r
+ *   } DIGESTMAP_FOREACH_END.
+ */
+#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar)                 \
+  MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)
+
+/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or
+ * keytype.
+ * Example use:
+ *   DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) {
+ *      if (is_very_old(r))
+ *       MAP_DEL_CURRENT(k);
+ *   } DIGESTMAP_FOREACH_END.
+ */
+#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)          \
+  MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)
+/** Used to end a DIGESTMAP_FOREACH() block. */
+#define DIGESTMAP_FOREACH_END MAP_FOREACH_END
+
+#define STRMAP_FOREACH(map, keyvar, valtype, valvar)                 \
+  MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar)
+#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)          \
+  MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar)
+#define STRMAP_FOREACH_END MAP_FOREACH_END
+
+void* strmap_set_lc(strmap_t *map, const char *key, void *val);
+void* strmap_get_lc(const strmap_t *map, const char *key);
+void* strmap_remove_lc(strmap_t *map, const char *key);
+
+#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype)           \
+  typedef struct maptype maptype;                                       \
+  typedef struct prefix##iter_t prefix##iter_t;                         \
+  static inline maptype* prefix##new(void)                              \
+  {                                                                     \
+    return (maptype*)digestmap_new();                                   \
+  }                                                                     \
+  static inline digestmap_t* prefix##to_digestmap(maptype *map)         \
+  {                                                                     \
+    return (digestmap_t*)map;                                           \
+  }                                                                     \
+  static inline valtype* prefix##get(maptype *map, const char *key)     \
+  {                                                                     \
+    return (valtype*)digestmap_get((digestmap_t*)map, key);             \
+  }                                                                     \
+  static inline valtype* prefix##set(maptype *map, const char *key,     \
+                                     valtype *val)                      \
+  {                                                                     \
+    return (valtype*)digestmap_set((digestmap_t*)map, key, val);        \
+  }                                                                     \
+  static inline valtype* prefix##remove(maptype *map, const char *key)  \
+  {                                                                     \
+    return (valtype*)digestmap_remove((digestmap_t*)map, key);          \
+  }                                                                     \
+  static inline void prefix##free(maptype *map, void (*free_val)(void*)) \
+  {                                                                     \
+    digestmap_free((digestmap_t*)map, free_val);                        \
+  }                                                                     \
+  static inline int prefix##isempty(maptype *map)                       \
+  {                                                                     \
+    return digestmap_isempty((digestmap_t*)map);                        \
+  }                                                                     \
+  static inline int prefix##size(maptype *map)                          \
+  {                                                                     \
+    return digestmap_size((digestmap_t*)map);                           \
+  }                                                                     \
+  static inline prefix##iter_t *prefix##iter_init(maptype *map)         \
+  {                                                                     \
+    return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map);    \
+  }                                                                     \
+  static inline prefix##iter_t *prefix##iter_next(maptype *map,         \
+                                                  prefix##iter_t *iter) \
+  {                                                                     \
+    return (prefix##iter_t*) digestmap_iter_next(                       \
+                       (digestmap_t*)map, (digestmap_iter_t*)iter);     \
+  }                                                                     \
+  static inline prefix##iter_t *prefix##iter_next_rmv(maptype *map,     \
+                                                  prefix##iter_t *iter) \
+  {                                                                     \
+    return (prefix##iter_t*) digestmap_iter_next_rmv(                   \
+                       (digestmap_t*)map, (digestmap_iter_t*)iter);     \
+  }                                                                     \
+  static inline void prefix##iter_get(prefix##iter_t *iter,             \
+                                      const char **keyp,                \
+                                      valtype **valp)                   \
+  {                                                                     \
+    void *v;                                                            \
+    digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v);             \
+    *valp = v;                                                          \
+  }                                                                     \
+  static inline int prefix##iter_done(prefix##iter_t *iter)             \
+  {                                                                     \
+    return digestmap_iter_done((digestmap_iter_t*)iter);                \
+  }
+
+#if SIZEOF_INT == 4
+#define BITARRAY_SHIFT 5
+#elif SIZEOF_INT == 8
+#define BITARRAY_SHIFT 6
+#else
+#error "int is neither 4 nor 8 bytes. I can't deal with that."
+#endif
+#define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1)
+
+/** A random-access array of one-bit-wide elements. */
+typedef unsigned int bitarray_t;
+/** Create a new bit array that can hold <b>n_bits</b> bits. */
+static inline bitarray_t *
+bitarray_init_zero(unsigned int n_bits)
+{
+  /* round up to the next int. */
+  size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
+  return xzalloc(sz*sizeof(unsigned int));
+}
+/** Expand <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>,
+ * clearing all new bits.  Returns a possibly changed pointer to the
+ * bitarray. */
+static inline bitarray_t *
+bitarray_expand(bitarray_t *ba,
+                unsigned int n_bits_old, unsigned int n_bits_new)
+{
+  size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
+  size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
+  char *ptr;
+  if (sz_new <= sz_old)
+    return ba;
+  ptr = xrealloc(ba, sz_new*sizeof(unsigned int));
+  /* This memset does nothing to the older excess bytes.  But they were
+   * already set to 0 by bitarry_init_zero. */
+  memset(ptr+sz_old*sizeof(unsigned int), 0,
+         (sz_new-sz_old)*sizeof(unsigned int));
+  return (bitarray_t*) ptr;
+}
+/** Free the bit array <b>ba</b>. */
+static inline void
+bitarray_free(bitarray_t *ba)
+{
+  free(ba);
+}
+/** Set the <b>bit</b>th bit in <b>b</b> to 1. */
+static inline void
+bitarray_set(bitarray_t *b, int bit)
+{
+  b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
+}
+/** Set the <b>bit</b>th bit in <b>b</b> to 0. */
+static inline void
+bitarray_clear(bitarray_t *b, int bit)
+{
+  b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
+}
+/** Return true iff <b>bit</b>th bit in <b>b</b> is nonzero.  NOTE: does
+ * not necessarily return 1 on true. */
+static inline unsigned int
+bitarray_is_set(bitarray_t *b, int bit)
+{
+  return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
+}
+
+/** A set of digests, implemented as a Bloom filter. */
+typedef struct {
+  int mask; /**< One less than the number of bits in <b>ba</b>; always one less
+             * than a power of two. */
+  bitarray_t *ba; /**< A bit array to implement the Bloom filter. */
+} digestset_t;
+
+#define BIT(n) ((n) & set->mask)
+/** Add the digest <b>digest</b> to <b>set</b>. */
+static inline void
+digestset_add(digestset_t *set, const char *digest)
+{
+  const uint32_t *p = (const uint32_t *)digest;
+  const uint32_t d1 = p[0] + (p[1]>>16);
+  const uint32_t d2 = p[1] + (p[2]>>16);
+  const uint32_t d3 = p[2] + (p[3]>>16);
+  const uint32_t d4 = p[3] + (p[0]>>16);
+  bitarray_set(set->ba, BIT(d1));
+  bitarray_set(set->ba, BIT(d2));
+  bitarray_set(set->ba, BIT(d3));
+  bitarray_set(set->ba, BIT(d4));
+}
+
+/** If <b>digest</b> is in <b>set</b>, return nonzero.  Otherwise,
+ * <em>probably</em> return zero. */
+static inline int
+digestset_isin(const digestset_t *set, const char *digest)
+{
+  const uint32_t *p = (const uint32_t *)digest;
+  const uint32_t d1 = p[0] + (p[1]>>16);
+  const uint32_t d2 = p[1] + (p[2]>>16);
+  const uint32_t d3 = p[2] + (p[3]>>16);
+  const uint32_t d4 = p[3] + (p[0]>>16);
+  return bitarray_is_set(set->ba, BIT(d1)) &&
+         bitarray_is_set(set->ba, BIT(d2)) &&
+         bitarray_is_set(set->ba, BIT(d3)) &&
+         bitarray_is_set(set->ba, BIT(d4));
+}
+#undef BIT
+
+digestset_t *digestset_new(int max_elements);
+void digestset_free(digestset_t* set);
+
+/* These functions, given an <b>array</b> of <b>n_elements</b>, return the
+ * <b>nth</b> lowest element. <b>nth</b>=0 gives the lowest element;
+ * <b>n_elements</b>-1 gives the highest; and (<b>n_elements</b>-1) / 2 gives
+ * the median.  As a side effect, the elements of <b>array</b> are sorted. */
+int find_nth_int(int *array, int n_elements, int nth);
+time_t find_nth_time(time_t *array, int n_elements, int nth);
+double find_nth_double(double *array, int n_elements, int nth);
+int32_t find_nth_int32(int32_t *array, int n_elements, int nth);
+uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth);
+long find_nth_long(long *array, int n_elements, int nth);
+static inline int
+median_int(int *array, int n_elements)
+{
+  return find_nth_int(array, n_elements, (n_elements-1)/2);
+}
+static inline time_t
+median_time(time_t *array, int n_elements)
+{
+  return find_nth_time(array, n_elements, (n_elements-1)/2);
+}
+static inline double
+median_double(double *array, int n_elements)
+{
+  return find_nth_double(array, n_elements, (n_elements-1)/2);
+}
+static inline uint32_t
+median_uint32(uint32_t *array, int n_elements)
+{
+  return find_nth_uint32(array, n_elements, (n_elements-1)/2);
+}
+static inline int32_t
+median_int32(int32_t *array, int n_elements)
+{
+  return find_nth_int32(array, n_elements, (n_elements-1)/2);
+}
+static inline long
+median_long(long *array, int n_elements)
+{
+  return find_nth_long(array, n_elements, (n_elements-1)/2);
+}
+
+#endif
diff --git a/src/crypt.c b/src/crypt.c
index e28e061..98516e6 100644
--- a/src/crypt.c
+++ b/src/crypt.c
@@ -211,3 +211,27 @@ random_bytes(uchar *buf, size_t buflen)
 {
   return RAND_bytes(buf, buflen) == 1 ? 0 : -1;
 }
+
+
+/** Return a pseudorandom integer, chosen uniformly from the values
+ * between 0 and <b>max</b>-1 inclusive.  <b>max</b> must be between 1 and
+ * INT_MAX+1, inclusive. */
+int
+random_int(unsigned int max)
+{
+  unsigned int val;
+  unsigned int cutoff;
+  obfs_assert(max <= ((unsigned int)INT_MAX)+1);
+  obfs_assert(max > 0); /* don't div by 0 */
+
+  /* We ignore any values that are >= 'cutoff,' to avoid biasing the
+   * distribution with clipping at the upper end of unsigned int's
+   * range.
+   */
+  cutoff = UINT_MAX - (UINT_MAX%max);
+  while (1) {
+    random_bytes((uchar*)&val, sizeof(val));
+    if (val < cutoff)
+      return val % max;
+  }
+}
diff --git a/src/crypt.h b/src/crypt.h
index 3f1e4df..beccda6 100644
--- a/src/crypt.h
+++ b/src/crypt.h
@@ -45,6 +45,11 @@ void crypt_free(crypt_t *);
 /** Set b to contain n random bytes. */
 int random_bytes(uchar *b, size_t n);
+/** Return a random integer in the range [0, max).
+ * 'max' must be between 1 and INT_MAX+1, inclusive.
+ */
+int random_int(unsigned int max);
+
 #ifdef CRYPT_PRIVATE
#include <openssl/aes.h>
diff --git a/src/ht.h b/src/ht.h
new file mode 100644
index 0000000..8c45db1
--- /dev/null
+++ b/src/ht.h
@@ -0,0 +1,471 @@
+/* Copyright (c) 2002, Christopher Clark.
+ * Copyright (c) 2005-2006, Nick Mathewson.
+ * Copyright (c) 2007-2011, The Tor Project, Inc. */
+/* See license at end. */
+
+/* Based on ideas by Christopher Clark and interfaces from Niels Provos. */
+
+#ifndef HT_H
+#define HT_H
+
+#define HT_HEAD(name, type)                                             \
+  struct name {                                                         \
+    /* The hash table itself. */                                        \
+    struct type **hth_table;                                            \
+    /* How long is the hash table? */                                   \
+    unsigned hth_table_length;                                          \
+    /* How many elements does the table contain? */                     \
+    unsigned hth_n_entries;                                             \
+    /* How many elements will we allow in the table before resizing it? */ \
+    unsigned hth_load_limit;                                            \
+    /* Position of hth_table_length in the primes table. */             \
+    int hth_prime_idx;                                                  \
+  }
+
+#define HT_INITIALIZER()                        \
+  { NULL, 0, 0, 0, -1 }
+
+#define HT_ENTRY(type)                          \
+  struct {                                      \
+    struct type *hte_next;                      \
+    unsigned hte_hash;                          \
+  }
+
+#define HT_EMPTY(head)                          \
+  ((head)->hth_n_entries == 0)
+
+/* Helper: alias for the bucket containing 'elm'. */
+#define _HT_BUCKET(head, field, elm)                                    \
+  ((head)->hth_table[elm->field.hte_hash % head->hth_table_length])
+
+/* How many elements in 'head'? */
+#define HT_SIZE(head)                           \
+  ((head)->hth_n_entries)
+
+/* Return memory usage for a hashtable (not counting the entries themselves) */
+#define HT_MEM_USAGE(head)                         \
+  (sizeof(*head) + (head)->hth_table_length * sizeof(void*))
+
+#define HT_FIND(name, head, elm)     name##_HT_FIND((head), (elm))
+#define HT_INSERT(name, head, elm)   name##_HT_INSERT((head), (elm))
+#define HT_REPLACE(name, head, elm)  name##_HT_REPLACE((head), (elm))
+#define HT_REMOVE(name, head, elm)   name##_HT_REMOVE((head), (elm))
+#define HT_START(name, head)         name##_HT_START(head)
+#define HT_NEXT(name, head, elm)     name##_HT_NEXT((head), (elm))
+#define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm))
+#define HT_CLEAR(name, head)         name##_HT_CLEAR(head)
+#define HT_INIT(name, head)          name##_HT_INIT(head)
+/* Helper: */
+static inline unsigned
+ht_improve_hash(unsigned h)
+{
+  /* Aim to protect against poor hash functions by adding logic here
+   * - logic taken from java 1.4 hashtable source */
+  h += ~(h << 9);
+  h ^=  ((h >> 14) | (h << 18)); /* >>> */
+  h +=  (h << 4);
+  h ^=  ((h >> 10) | (h << 22)); /* >>> */
+  return h;
+}
+
+#if 0
+/** Basic string hash function, from Java standard String.hashCode(). */
+static inline unsigned
+ht_string_hash(const char *s)
+{
+  unsigned h = 0;
+  int m = 1;
+  while (*s) {
+    h += ((signed char)*s++)*m;
+    m = (m<<5)-1; /* m *= 31 */
+  }
+  return h;
+}
+#endif
+
+/** Basic string hash function, from Python's str.__hash__() */
+static inline unsigned
+ht_string_hash(const char *s)
+{
+  unsigned h;
+  const unsigned char *cp = (const unsigned char *)s;
+  h = *cp << 7;
+  while (*cp) {
+    h = (1000003*h) ^ *cp++;
+  }
+  /* This conversion truncates the length of the string, but that's ok. */
+  h ^= (unsigned)(cp-(const unsigned char*)s);
+  return h;
+}
+
+#define _HT_SET_HASH(elm, field, hashfn)        \
+    (elm)->field.hte_hash = hashfn(elm)
+
+#define HT_FOREACH(x, name, head)                 \
+  for ((x) = HT_START(name, head);                \
+       (x) != NULL;                               \
+       (x) = HT_NEXT(name, head, x))
+
+#define HT_PROTOTYPE(name, type, field, hashfn, eqfn)                   \
+  int name##_HT_GROW(struct name *ht, unsigned min_capacity);           \
+  void name##_HT_CLEAR(struct name *ht);                                \
+  int _##name##_HT_REP_IS_BAD(const struct name *ht);                   \
+  static inline void                                                    \
+  name##_HT_INIT(struct name *head) {                                   \
+    head->hth_table_length = 0;                                         \
+    head->hth_table = NULL;                                             \
+    head->hth_n_entries = 0;                                            \
+    head->hth_load_limit = 0;                                           \
+    head->hth_prime_idx = -1;                                           \
+  }                                                                     \
+  /* Helper: returns a pointer to the right location in the table       \
+   * 'head' to find or insert the element 'elm'. */                     \
+  static inline struct type **                                          \
+  _##name##_HT_FIND_P(struct name *head, struct type *elm)              \
+  {                                                                     \
+    struct type **p;                                                    \
+    if (!head->hth_table)                                               \
+      return NULL;                                                      \
+    p = &_HT_BUCKET(head, field, elm);                                  \
+    while (*p) {                                                        \
+      if (eqfn(*p, elm))                                                \
+        return p;                                                       \
+      p = &(*p)->field.hte_next;                                        \
+    }                                                                   \
+    return p;                                                           \
+  }                                                                     \
+  /* Return a pointer to the element in the table 'head' matching 'elm', \
+   * or NULL if no such element exists */                               \
+  static inline struct type *                                           \
+  name##_HT_FIND(const struct name *head, struct type *elm)             \
+  {                                                                     \
+    struct type **p;                                                    \
+    struct name *h = (struct name *) head;                              \
+    _HT_SET_HASH(elm, field, hashfn);                                   \
+    p = _##name##_HT_FIND_P(h, elm);                                    \
+    return p ? *p : NULL;                                               \
+  }                                                                     \
+  /* Insert the element 'elm' into the table 'head'.  Do not call this  \
+   * function if the table might already contain a matching element. */ \
+  static inline void                                                    \
+  name##_HT_INSERT(struct name *head, struct type *elm)                 \
+  {                                                                     \
+    struct type **p;                                                    \
+    if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
+      name##_HT_GROW(head, head->hth_n_entries+1);                      \
+    ++head->hth_n_entries;                                              \
+    _HT_SET_HASH(elm, field, hashfn);                                   \
+    p = &_HT_BUCKET(head, field, elm);                                  \
+    elm->field.hte_next = *p;                                           \
+    *p = elm;                                                           \
+  }                                                                     \
+  /* Insert the element 'elm' into the table 'head'. If there already   \
+   * a matching element in the table, replace that element and return   \
+   * it. */                                                             \
+  static inline struct type *                                           \
+  name##_HT_REPLACE(struct name *head, struct type *elm)                \
+  {                                                                     \
+    struct type **p, *r;                                                \
+    if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
+      name##_HT_GROW(head, head->hth_n_entries+1);                      \
+    _HT_SET_HASH(elm, field, hashfn);                                   \
+    p = _##name##_HT_FIND_P(head, elm);                                 \
+    r = *p;                                                             \
+    *p = elm;                                                           \
+    if (r && (r!=elm)) {                                                \
+      elm->field.hte_next = r->field.hte_next;                          \
+      r->field.hte_next = NULL;                                         \
+      return r;                                                         \
+    } else {                                                            \
+      ++head->hth_n_entries;                                            \
+      return NULL;                                                      \
+    }                                                                   \
+  }                                                                     \
+  /* Remove any element matching 'elm' from the table 'head'.  If such  \
+   * an element is found, return it; otherwise return NULL. */          \
+  static inline struct type *                                           \
+  name##_HT_REMOVE(struct name *head, struct type *elm)                 \
+  {                                                                     \
+    struct type **p, *r;                                                \
+    _HT_SET_HASH(elm, field, hashfn);                                   \
+    p = _##name##_HT_FIND_P(head,elm);                                  \
+    if (!p || !*p)                                                      \
+      return NULL;                                                      \
+    r = *p;                                                             \
+    *p = r->field.hte_next;                                             \
+    r->field.hte_next = NULL;                                           \
+    --head->hth_n_entries;                                              \
+    return r;                                                           \
+  }                                                                     \
+  /* Invoke the function 'fn' on every element of the table 'head',     \
+   * using 'data' as its second argument.  If the function returns      \
+   * nonzero, remove the most recently examined element before invoking \
+   * the function again. */                                             \
+  static inline void                                                    \
+  name##_HT_FOREACH_FN(struct name *head,                               \
+                       int (*fn)(struct type *, void *),                \
+                       void *data)                                      \
+  {                                                                     \
+    unsigned idx;                                                       \
+    int remove;                                                         \
+    struct type **p, **nextp, *next;                                    \
+    if (!head->hth_table)                                               \
+      return;                                                           \
+    for (idx=0; idx < head->hth_table_length; ++idx) {                  \
+      p = &head->hth_table[idx];                                        \
+      while (*p) {                                                      \
+        nextp = &(*p)->field.hte_next;                                  \
+        next = *nextp;                                                  \
+        remove = fn(*p, data);                                          \
+        if (remove) {                                                   \
+          --head->hth_n_entries;                                        \
+          *p = next;                                                    \
+        } else {                                                        \
+          p = nextp;                                                    \
+        }                                                               \
+      }                                                                 \
+    }                                                                   \
+  }                                                                     \
+  /* Return a pointer to the first element in the table 'head', under   \
+   * an arbitrary order.  This order is stable under remove operations, \
+   * but not under others. If the table is empty, return NULL. */       \
+  static inline struct type **                                          \
+  name##_HT_START(struct name *head)                                    \
+  {                                                                     \
+    unsigned b = 0;                                                     \
+    while (b < head->hth_table_length) {                                \
+      if (head->hth_table[b])                                           \
+        return &head->hth_table[b];                                     \
+      ++b;                                                              \
+    }                                                                   \
+    return NULL;                                                        \
+  }                                                                     \
+  /* Return the next element in 'head' after 'elm', under the arbitrary \
+   * order used by HT_START.  If there are no more elements, return     \
+   * NULL.  If 'elm' is to be removed from the table, you must call     \
+   * this function for the next value before you remove it.             \
+   */                                                                   \
+  static inline struct type **                                          \
+  name##_HT_NEXT(struct name *head, struct type **elm)                  \
+  {                                                                     \
+    if ((*elm)->field.hte_next) {                                       \
+      return &(*elm)->field.hte_next;                                   \
+    } else {                                                            \
+      unsigned b = ((*elm)->field.hte_hash % head->hth_table_length)+1; \
+      while (b < head->hth_table_length) {                              \
+        if (head->hth_table[b])                                         \
+          return &head->hth_table[b];                                   \
+        ++b;                                                            \
+      }                                                                 \
+      return NULL;                                                      \
+    }                                                                   \
+  }                                                                     \
+  static inline struct type **                                          \
+  name##_HT_NEXT_RMV(struct name *head, struct type **elm)              \
+  {                                                                     \
+    unsigned h = (*elm)->field.hte_hash;                                \
+    *elm = (*elm)->field.hte_next;                                      \
+    --head->hth_n_entries;                                              \
+    if (*elm) {                                                         \
+      return elm;                                                       \
+    } else {                                                            \
+      unsigned b = (h % head->hth_table_length)+1;                      \
+      while (b < head->hth_table_length) {                              \
+        if (head->hth_table[b])                                         \
+          return &head->hth_table[b];                                   \
+        ++b;                                                            \
+      }                                                                 \
+      return NULL;                                                      \
+    }                                                                   \
+  }
+
+#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn,    \
+                    reallocfn, freefn)                                  \
+  static unsigned name##_PRIMES[] = {                                   \
+    53, 97, 193, 389,                                                   \
+    769, 1543, 3079, 6151,                                              \
+    12289, 24593, 49157, 98317,                                         \
+    196613, 393241, 786433, 1572869,                                    \
+    3145739, 6291469, 12582917, 25165843,                               \
+    50331653, 100663319, 201326611, 402653189,                          \
+    805306457, 1610612741                                               \
+  };                                                                    \
+  static unsigned name##_N_PRIMES =                                     \
+    (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0]));         \
+  /* Expand the internal table of 'head' until it is large enough to    \
+   * hold 'size' elements.  Return 0 on success, -1 on allocation       \
+   * failure. */                                                        \
+  int                                                                   \
+  name##_HT_GROW(struct name *head, unsigned size)                      \
+  {                                                                     \
+    unsigned new_len, new_load_limit;                                   \
+    int prime_idx;                                                      \
+    struct type **new_table;                                            \
+    if (head->hth_prime_idx == (int)name##_N_PRIMES - 1)                \
+      return 0;                                                         \
+    if (head->hth_load_limit > size)                                    \
+      return 0;                                                         \
+    prime_idx = head->hth_prime_idx;                                    \
+    do {                                                                \
+      new_len = name##_PRIMES[++prime_idx];                             \
+      new_load_limit = (unsigned)(load*new_len);                        \
+    } while (new_load_limit <= size &&                                  \
+             prime_idx < (int)name##_N_PRIMES);                         \
+    if ((new_table = mallocfn(new_len*sizeof(struct type*)))) {         \
+      unsigned b;                                                       \
+      memset(new_table, 0, new_len*sizeof(struct type*));               \
+      for (b = 0; b < head->hth_table_length; ++b) {                    \
+        struct type *elm, *next;                                        \
+        unsigned b2;                                                    \
+        elm = head->hth_table[b];                                       \
+        while (elm) {                                                   \
+          next = elm->field.hte_next;                                   \
+          b2 = elm->field.hte_hash % new_len;                           \
+          elm->field.hte_next = new_table[b2];                          \
+          new_table[b2] = elm;                                          \
+          elm = next;                                                   \
+        }                                                               \
+      }                                                                 \
+      if (head->hth_table)                                              \
+        freefn(head->hth_table);                                        \
+      head->hth_table = new_table;                                      \
+    } else {                                                            \
+      unsigned b, b2;                                                   \
+      new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \
+      if (!new_table) return -1;                                        \
+      memset(new_table + head->hth_table_length, 0,                     \
+             (new_len - head->hth_table_length)*sizeof(struct type*));  \
+      for (b=0; b < head->hth_table_length; ++b) {                      \
+        struct type *e, **pE;                                           \
+        for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) {         \
+          b2 = e->field.hte_hash % new_len;                             \
+          if (b2 == b) {                                                \
+            pE = &e->field.hte_next;                                    \
+          } else {                                                      \
+            *pE = e->field.hte_next;                                    \
+            e->field.hte_next = new_table[b2];                          \
+            new_table[b2] = e;                                          \
+          }                                                             \
+        }                                                               \
+      }                                                                 \
+      head->hth_table = new_table;                                      \
+    }                                                                   \
+    head->hth_table_length = new_len;                                   \
+    head->hth_prime_idx = prime_idx;                                    \
+    head->hth_load_limit = new_load_limit;                              \
+    return 0;                                                           \
+  }                                                                     \
+  /* Free all storage held by 'head'.  Does not free 'head' itself, or  \
+   * individual elements. */                                            \
+  void                                                                  \
+  name##_HT_CLEAR(struct name *head)                                    \
+  {                                                                     \
+    if (head->hth_table)                                                \
+      freefn(head->hth_table);                                          \
+    head->hth_table_length = 0;                                         \
+    name##_HT_INIT(head);                                               \
+  }                                                                     \
+  /* Debugging helper: return false iff the representation of 'head' is \
+   * internally consistent. */                                          \
+  int                                                                   \
+  _##name##_HT_REP_IS_BAD(const struct name *head)                      \
+  {                                                                     \
+    unsigned n, i;                                                      \
+    struct type *elm;                                                   \
+    if (!head->hth_table_length) {                                      \
+      if (!head->hth_table && !head->hth_n_entries &&                   \
+          !head->hth_load_limit && head->hth_prime_idx == -1)           \
+        return 0;                                                       \
+      else                                                              \
+        return 1;                                                       \
+    }                                                                   \
+    if (!head->hth_table || head->hth_prime_idx < 0 ||                  \
+        !head->hth_load_limit)                                          \
+      return 2;                                                         \
+    if (head->hth_n_entries > head->hth_load_limit)                     \
+      return 3;                                                         \
+    if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx])   \
+      return 4;                                                         \
+    if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
+      return 5;                                                         \
+    for (n = i = 0; i < head->hth_table_length; ++i) {                  \
+      for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) {  \
+        if (elm->field.hte_hash != hashfn(elm))                         \
+          return 1000 + i;                                              \
+        if ((elm->field.hte_hash % head->hth_table_length) != i)        \
+          return 10000 + i;                                             \
+        ++n;                                                            \
+      }                                                                 \
+    }                                                                   \
+    if (n != head->hth_n_entries)                                       \
+      return 6;                                                         \
+    return 0;                                                           \
+  }
+
+/** Implements an over-optimized "find and insert if absent" block;
+ * not meant for direct usage by typical code, or usage outside the critical
+ * path.*/
+#define _HT_FIND_OR_INSERT(name, field, hashfn, head, eltype, elm, var, y, n) \
+  {                                                                     \
+    struct name *_##var##_head = head;                                  \
+    eltype **var;                                                       \
+    if (!_##var##_head->hth_table ||                                    \
+        _##var##_head->hth_n_entries >= _##var##_head->hth_load_limit)  \
+      name##_HT_GROW(_##var##_head, _##var##_head->hth_n_entries+1);     \
+    _HT_SET_HASH((elm), field, hashfn);                                \
+    var = _##name##_HT_FIND_P(_##var##_head, (elm));                    \
+    if (*var) {                                                         \
+      y;                                                                \
+    } else {                                                            \
+      n;                                                                \
+    }                                                                   \
+  }
+#define _HT_FOI_INSERT(field, head, elm, newent, var)       \
+  {                                                         \
+    newent->field.hte_hash = (elm)->field.hte_hash;         \
+    newent->field.hte_next = NULL;                          \
+    *var = newent;                                          \
+    ++((head)->hth_n_entries);                              \
+  }
+
+/*
+ * Copyright 2005, Nick Mathewson.  Implementation logic is adapted from code
+ * by Christopher Clark, retrofit to allow drop-in memory management, and to
+ * use the same interface as Niels Provos's HT_H.  I'm not sure whether this
+ * is a derived work any more, but whether it is or not, the license below
+ * applies.
+ *
+ * Copyright (c) 2002, Christopher Clark
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * * Neither the name of the original author; nor the names of any contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
+ * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#endif
+
diff --git a/src/test/unittest.c b/src/test/unittest.c
index 45757e9..8974c87 100644
--- a/src/test/unittest.c
+++ b/src/test/unittest.c
@@ -5,11 +5,13 @@
 #include "tinytest.h"
 #include "../crypt.h"
+extern struct testcase_t container_tests[];
 extern struct testcase_t crypt_tests[];
 extern struct testcase_t obfs2_tests[];
 extern struct testcase_t socks_tests[];
struct testgroup_t groups[] = {
+  { "container/", container_tests },
   { "crypt/", crypt_tests },
   { "obfs2/", obfs2_tests },
   { "socks/", socks_tests },
diff --git a/src/test/unittest_container.c b/src/test/unittest_container.c
new file mode 100644
index 0000000..4731139
--- /dev/null
+++ b/src/test/unittest_container.c
@@ -0,0 +1,772 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2011, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "../util.h"
+#include "tinytest_macros.h"
+
+#include "../container.h"
+#include "../crypt.h"
+
+/** Helper: return a tristate based on comparing the strings in *<b>a</b> and
+ * *<b>b</b>. */
+static int
+_compare_strs(const void **a, const void **b)
+{
+  const char *s1 = *a, *s2 = *b;
+  return strcmp(s1, s2);
+}
+
+/** Helper: return a tristate based on comparing the strings in *<b>a</b> and
+ * *<b>b</b>, excluding a's first character, and ignoring case. */
+static int
+_compare_without_first_ch(const void *a, const void **b)
+{
+  const char *s1 = a, *s2 = *b;
+  return strcasecmp(s1+1, s2);
+}
+
+/** Run unit tests for basic dynamic-sized array functionality. */
+static void
+test_container_smartlist_basic(void *unused)
+{
+  smartlist_t *sl;
+
+  /* XXXX test sort_digests, uniq_strings, uniq_digests */
+
+  /* Test smartlist add, del_keeporder, insert, get. */
+  sl = smartlist_create();
+  smartlist_add(sl, (void*)1);
+  smartlist_add(sl, (void*)2);
+  smartlist_add(sl, (void*)3);
+  smartlist_add(sl, (void*)4);
+  smartlist_del_keeporder(sl, 1);
+  smartlist_insert(sl, 1, (void*)22);
+  smartlist_insert(sl, 0, (void*)0);
+  smartlist_insert(sl, 5, (void*)555);
+  tt_ptr_op(smartlist_get(sl,0), ==, (void*)0);
+  tt_ptr_op(smartlist_get(sl,1), ==, (void*)1);
+  tt_ptr_op(smartlist_get(sl,2), ==, (void*)22);
+  tt_ptr_op(smartlist_get(sl,3), ==, (void*)3);
+  tt_ptr_op(smartlist_get(sl,4), ==, (void*)4);
+  tt_ptr_op(smartlist_get(sl,5), ==, (void*)555);
+  /* Try deleting in the middle. */
+  smartlist_del(sl, 1);
+  tt_ptr_op(smartlist_get(sl, 1), ==, (void*)555);
+  /* Try deleting at the end. */
+  smartlist_del(sl, 4);
+  tt_int_op(smartlist_len(sl), ==, 4);
+
+  /* test isin. */
+  tt_assert(smartlist_isin(sl, (void*)3));
+  tt_assert(!smartlist_isin(sl, (void*)99));
+
+ end:
+  smartlist_free(sl);
+}
+
+/** Run unit tests for smartlist-of-strings functionality. */
+static void
+test_container_smartlist_strings(void *unused)
+{
+  smartlist_t *sl = smartlist_create();
+  char *cp=NULL, *cp_alloc=NULL;
+  size_t sz;
+
+  /* Test split and join */
+  tt_int_op(smartlist_len(sl), ==, 0);
+  smartlist_split_string(sl, "abc", ":", 0, 0);
+  tt_int_op(smartlist_len(sl), ==, 1);
+  tt_str_op(smartlist_get(sl, 0), ==, "abc");
+  smartlist_split_string(sl, "a::bc::", "::", 0, 0);
+  tt_int_op(smartlist_len(sl), ==, 4);
+  tt_str_op(smartlist_get(sl, 1), ==, "a");
+  tt_str_op(smartlist_get(sl, 2), ==, "bc");
+  tt_str_op(smartlist_get(sl, 3), ==, "");
+  cp_alloc = smartlist_join_strings(sl, "", 0, NULL);
+  tt_str_op(cp_alloc, ==, "abcabc");
+  free(cp_alloc);
+  cp_alloc = smartlist_join_strings(sl, "!", 0, NULL);
+  tt_str_op(cp_alloc, ==, "abc!a!bc!");
+  free(cp_alloc);
+  cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
+  tt_str_op(cp_alloc, ==, "abcXYaXYbcXY");
+  free(cp_alloc);
+  cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
+  tt_str_op(cp_alloc, ==, "abcXYaXYbcXYXY");
+  free(cp_alloc);
+  cp_alloc = smartlist_join_strings(sl, "", 1, NULL);
+  tt_str_op(cp_alloc, ==, "abcabc");
+  free(cp_alloc);
+
+  smartlist_split_string(sl, "/def/  /ghijk", "/", 0, 0);
+  tt_int_op(smartlist_len(sl), ==, 8);
+  tt_str_op(smartlist_get(sl, 4), ==, "");
+  tt_str_op(smartlist_get(sl, 5), ==, "def");
+  tt_str_op(smartlist_get(sl, 6), ==, "  ");
+  tt_str_op(smartlist_get(sl, 7), ==, "ghijk");
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+
+  smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0);
+  tt_int_op(smartlist_len(sl), ==, 3);
+  tt_str_op(smartlist_get(sl,0), ==, "a");
+  tt_str_op(smartlist_get(sl,1), ==, "bbd");
+  tt_str_op(smartlist_get(sl,2), ==, "cdef");
+  smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
+                         SPLIT_SKIP_SPACE, 0);
+  tt_int_op(smartlist_len(sl), ==, 8);
+  tt_str_op(smartlist_get(sl,3), ==, "z");
+  tt_str_op(smartlist_get(sl,4), ==, "zhasd");
+  tt_str_op(smartlist_get(sl,5), ==, "");
+  tt_str_op(smartlist_get(sl,6), ==, "bnud");
+  tt_str_op(smartlist_get(sl,7), ==, "");
+
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+
+  smartlist_split_string(sl, " ab\tc \td ef  ", NULL,
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  tt_int_op(smartlist_len(sl), ==, 4);
+  tt_str_op(smartlist_get(sl,0), ==, "ab");
+  tt_str_op(smartlist_get(sl,1), ==, "c");
+  tt_str_op(smartlist_get(sl,2), ==, "d");
+  tt_str_op(smartlist_get(sl,3), ==, "ef");
+  smartlist_split_string(sl, "ghi\tj", NULL,
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  tt_int_op(smartlist_len(sl), ==, 6);
+  tt_str_op(smartlist_get(sl,4), ==, "ghi");
+  tt_str_op(smartlist_get(sl,5), ==, "j");
+
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+
+  cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
+  tt_str_op(cp_alloc, ==, "");
+  free(cp_alloc);
+  cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
+  tt_str_op(cp_alloc, ==, "XY");
+  free(cp_alloc);
+
+  smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  tt_int_op(smartlist_len(sl), ==, 3);
+  tt_str_op(smartlist_get(sl, 0), ==, "z");
+  tt_str_op(smartlist_get(sl, 1), ==, "zhasd");
+  tt_str_op(smartlist_get(sl, 2), ==, "bnud");
+  smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2);
+  tt_int_op(smartlist_len(sl), ==, 5);
+  tt_str_op(smartlist_get(sl, 3), ==, "z");
+  tt_str_op(smartlist_get(sl, 4), ==, "zhasd <>  <> bnud<>");
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+
+  smartlist_split_string(sl, "abcd\n", "\n",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  tt_int_op(smartlist_len(sl), ==, 1);
+  tt_str_op(smartlist_get(sl, 0), ==, "abcd");
+  smartlist_split_string(sl, "efgh", "\n",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  tt_int_op(smartlist_len(sl), ==, 2);
+  tt_str_op(smartlist_get(sl, 1), ==, "efgh");
+
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+
+  /* Test swapping, shuffling, and sorting. */
+  smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0);
+  tt_int_op(smartlist_len(sl), ==, 7);
+  smartlist_sort(sl, _compare_strs);
+  cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
+  tt_str_op(cp_alloc, ==, "and,arma,by,nickm,onion,router,the");
+  free(cp_alloc);
+  smartlist_swap(sl, 1, 5);
+  cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
+  tt_str_op(cp_alloc, ==, "and,router,by,nickm,onion,arma,the");
+  free(cp_alloc);
+  smartlist_shuffle(sl);
+  tt_int_op(smartlist_len(sl), ==, 7);
+  tt_assert(smartlist_string_isin(sl, "and"));
+  tt_assert(smartlist_string_isin(sl, "router"));
+  tt_assert(smartlist_string_isin(sl, "by"));
+  tt_assert(smartlist_string_isin(sl, "nickm"));
+  tt_assert(smartlist_string_isin(sl, "onion"));
+  tt_assert(smartlist_string_isin(sl, "arma"));
+  tt_assert(smartlist_string_isin(sl, "the"));
+
+  /* Test bsearch. */
+  smartlist_sort(sl, _compare_strs);
+  tt_str_op(smartlist_bsearch(sl, "zNicKM",
+                              _compare_without_first_ch), ==, "nickm");
+  tt_str_op(smartlist_bsearch(sl, " AND", _compare_without_first_ch), ==, "and");
+  tt_ptr_op(smartlist_bsearch(sl, " ANz", _compare_without_first_ch), ==, NULL);
+
+  /* Test bsearch_idx */
+  {
+    int f;
+    tt_int_op(smartlist_bsearch_idx(sl," aaa",_compare_without_first_ch,&f),
+              ==, 0);
+    tt_int_op(f, ==, 0);
+    tt_int_op(smartlist_bsearch_idx(sl," and",_compare_without_first_ch,&f),
+              ==, 0);
+    tt_int_op(f, ==, 1);
+    tt_int_op(smartlist_bsearch_idx(sl," arm",_compare_without_first_ch,&f),
+              ==, 1);
+    tt_int_op(f, ==, 0);
+    tt_int_op(smartlist_bsearch_idx(sl," arma",_compare_without_first_ch,&f),
+              ==, 1);
+    tt_int_op(f, ==, 1);
+    tt_int_op(smartlist_bsearch_idx(sl," armb",_compare_without_first_ch,&f),
+              ==, 2);
+    tt_int_op(f, ==, 0);
+    tt_int_op(smartlist_bsearch_idx(sl," zzzz",_compare_without_first_ch,&f),
+              ==, 7);
+    tt_int_op(f, ==, 0);
+  }
+
+  /* Test reverse() and pop_last() */
+  smartlist_reverse(sl);
+  cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
+  tt_str_op(cp_alloc, ==, "the,router,onion,nickm,by,arma,and");
+  free(cp_alloc);
+  cp_alloc = smartlist_pop_last(sl);
+  tt_str_op(cp_alloc, ==, "and");
+  free(cp_alloc);
+  tt_int_op(smartlist_len(sl), ==, 6);
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+  cp_alloc = smartlist_pop_last(sl);
+  tt_ptr_op(cp_alloc, ==, NULL);
+
+  /* Test uniq() */
+  smartlist_split_string(sl,
+                     "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50",
+                     ",", 0, 0);
+  smartlist_sort(sl, _compare_strs);
+  smartlist_uniq(sl, _compare_strs, free);
+  cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
+  tt_str_op(cp_alloc, ==, "50,a,canal,man,noon,panama,plan,radar");
+  free(cp_alloc);
+
+  /* Test string_isin and isin_case and num_isin */
+  tt_assert(smartlist_string_isin(sl, "noon"));
+  tt_assert(!smartlist_string_isin(sl, "noonoon"));
+  tt_assert(smartlist_string_isin_case(sl, "nOOn"));
+  tt_assert(!smartlist_string_isin_case(sl, "nooNooN"));
+  tt_assert(smartlist_string_num_isin(sl, 50));
+  tt_assert(!smartlist_string_num_isin(sl, 60));
+
+  /* Test smartlist_choose */
+  {
+    int i;
+    int allsame = 1;
+    int allin = 1;
+    void *first = smartlist_choose(sl);
+    tt_assert(smartlist_isin(sl, first));
+    for (i = 0; i < 100; ++i) {
+      void *second = smartlist_choose(sl);
+      if (second != first)
+        allsame = 0;
+      if (!smartlist_isin(sl, second))
+        allin = 0;
+    }
+    tt_assert(!allsame);
+    tt_assert(allin);
+  }
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_clear(sl);
+
+  /* Test string_remove and remove and join_strings2 */
+  smartlist_split_string(sl,
+                    "Some say the Earth will end in ice and some in fire",
+                    " ", 0, 0);
+  cp = smartlist_get(sl, 4);
+  tt_str_op(cp, ==, "will");
+  smartlist_add(sl, cp);
+  smartlist_remove(sl, cp);
+  free(cp);
+  cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
+  tt_str_op(cp_alloc, ==, "Some,say,the,Earth,fire,end,in,ice,and,some,in");
+  free(cp_alloc);
+  smartlist_string_remove(sl, "in");
+  cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz);
+  tt_str_op(cp_alloc, ==, "Some+say+the+Earth+fire+end+some+ice+and");
+  tt_int_op((int)sz, ==, 40);
+
+ end:
+
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_free(sl);
+  free(cp_alloc);
+}
+
+/** Run unit tests for smartlist set manipulation functions. */
+static void
+test_container_smartlist_overlap(void *unused)
+{
+  smartlist_t *sl = smartlist_create();
+  smartlist_t *ints = smartlist_create();
+  smartlist_t *odds = smartlist_create();
+  smartlist_t *evens = smartlist_create();
+  smartlist_t *primes = smartlist_create();
+  int i;
+  for (i=1; i < 10; i += 2)
+    smartlist_add(odds, (void*)(uintptr_t)i);
+  for (i=0; i < 10; i += 2)
+    smartlist_add(evens, (void*)(uintptr_t)i);
+
+  /* add_all */
+  smartlist_add_all(ints, odds);
+  smartlist_add_all(ints, evens);
+  tt_int_op(smartlist_len(ints), ==, 10);
+
+  smartlist_add(primes, (void*)2);
+  smartlist_add(primes, (void*)3);
+  smartlist_add(primes, (void*)5);
+  smartlist_add(primes, (void*)7);
+
+  /* overlap */
+  tt_assert(smartlist_overlap(ints, odds));
+  tt_assert(smartlist_overlap(odds, primes));
+  tt_assert(smartlist_overlap(evens, primes));
+  tt_assert(!smartlist_overlap(odds, evens));
+
+  /* intersect */
+  smartlist_add_all(sl, odds);
+  smartlist_intersect(sl, primes);
+  tt_int_op(smartlist_len(sl), ==, 3);
+  tt_assert(smartlist_isin(sl, (void*)3));
+  tt_assert(smartlist_isin(sl, (void*)5));
+  tt_assert(smartlist_isin(sl, (void*)7));
+
+  /* subtract */
+  smartlist_add_all(sl, primes);
+  smartlist_subtract(sl, odds);
+  tt_int_op(smartlist_len(sl), ==, 1);
+  tt_assert(smartlist_isin(sl, (void*)2));
+
+ end:
+  smartlist_free(odds);
+  smartlist_free(evens);
+  smartlist_free(ints);
+  smartlist_free(primes);
+  smartlist_free(sl);
+}
+
+/** Run unit tests for smartlist-of-digests functions. */
+static void
+test_container_smartlist_digests(void *unused)
+{
+  smartlist_t *sl = smartlist_create();
+
+  /* digest_isin. */
+  smartlist_add(sl, xmemdup("AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH));
+  smartlist_add(sl, xmemdup("\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH));
+  smartlist_add(sl, xmemdup("\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH));
+  tt_int_op(smartlist_digest_isin(NULL, "AAAAAAAAAAAAAAAAAAAA"), ==, 0);
+  tt_assert(smartlist_digest_isin(sl, "AAAAAAAAAAAAAAAAAAAA"));
+  tt_assert(smartlist_digest_isin(sl, "\00090AAB2AAAAaasdAAAAA"));
+  tt_int_op(smartlist_digest_isin(sl, "\00090AAB2AAABaasdAAAAA"), ==, 0);
+
+  /* sort digests */
+  smartlist_sort_digests(sl);
+  tt_mem_op(smartlist_get(sl, 0), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH);
+  tt_mem_op(smartlist_get(sl, 1), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH);
+  tt_mem_op(smartlist_get(sl, 2), ==, "AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH);
+  tt_int_op(smartlist_len(sl), ==, 3);
+
+  /* uniq_digests */
+  smartlist_uniq_digests(sl);
+  tt_int_op(smartlist_len(sl), ==, 2);
+  tt_mem_op(smartlist_get(sl, 0), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH);
+  tt_mem_op(smartlist_get(sl, 1), ==, "AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH);
+
+ end:
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_free(sl);
+}
+
+/** Run unit tests for concatenate-a-smartlist-of-strings functions. */
+static void
+test_container_smartlist_join(void *unused)
+{
+  smartlist_t *sl = smartlist_create();
+  smartlist_t *sl2 = smartlist_create(), *sl3 = smartlist_create(),
+    *sl4 = smartlist_create();
+  char *joined=NULL;
+  /* unique, sorted. */
+  smartlist_split_string(sl,
+                         "Abashments Ambush Anchorman Bacon Banks Borscht "
+                         "Bunks Inhumane Insurance Knish Know Manners "
+                         "Maraschinos Stamina Sunbonnets Unicorns Wombats",
+                         " ", 0, 0);
+  /* non-unique, sorted. */
+  smartlist_split_string(sl2,
+                         "Ambush Anchorman Anchorman Anemias Anemias Bacon "
+                         "Crossbowmen Inhumane Insurance Knish Know Manners "
+                         "Manners Maraschinos Wombats Wombats Work",
+                         " ", 0, 0);
+  SMARTLIST_FOREACH_JOIN(sl, char *, cp1,
+                         sl2, char *, cp2,
+                         strcmp(cp1,cp2),
+                         smartlist_add(sl3, cp2)) {
+    tt_str_op(cp1, ==, cp2);
+    smartlist_add(sl4, cp1);
+  } SMARTLIST_FOREACH_JOIN_END(cp1, cp2);
+
+  SMARTLIST_FOREACH(sl3, const char *, cp,
+                    tt_assert(smartlist_isin(sl2, cp) &&
+                                !smartlist_string_isin(sl, cp)));
+  SMARTLIST_FOREACH(sl4, const char *, cp,
+                    tt_assert(smartlist_isin(sl, cp) &&
+                                smartlist_string_isin(sl2, cp)));
+  joined = smartlist_join_strings(sl3, ",", 0, NULL);
+  tt_str_op(joined, ==, "Anemias,Anemias,Crossbowmen,Work");
+  free(joined);
+  joined = smartlist_join_strings(sl4, ",", 0, NULL);
+  tt_str_op(joined, ==,
+            "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance,"
+            "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats");
+
+ end:
+  smartlist_free(sl4);
+  smartlist_free(sl3);
+  SMARTLIST_FOREACH(sl2, char *, cp, free(cp));
+  smartlist_free(sl2);
+  SMARTLIST_FOREACH(sl, char *, cp, free(cp));
+  smartlist_free(sl);
+  free(joined);
+}
+
+/** Run unit tests for bitarray code */
+static void
+test_container_bitarray(void *unused)
+{
+  bitarray_t *ba = NULL;
+  int i, j;
+
+  ba = bitarray_init_zero(1);
+  tt_assert(ba);
+  tt_assert(! bitarray_is_set(ba, 0));
+  bitarray_set(ba, 0);
+  tt_assert(bitarray_is_set(ba, 0));
+  bitarray_clear(ba, 0);
+  tt_assert(! bitarray_is_set(ba, 0));
+  bitarray_free(ba);
+
+  ba = bitarray_init_zero(1023);
+  for (i = 1; i < 64; ) {
+    for (j = 0; j < 1023; ++j) {
+      if (j % i)
+        bitarray_set(ba, j);
+      else
+        bitarray_clear(ba, j);
+    }
+    for (j = 0; j < 1023; ++j) {
+      tt_bool_op(bitarray_is_set(ba, j), ==, j%i);
+    }
+
+    if (i < 7)
+      ++i;
+    else if (i == 28)
+      i = 32;
+    else
+      i += 7;
+  }
+
+ end:
+  if (ba)
+    bitarray_free(ba);
+}
+
+/** Run unit tests for digest set code (implemented as a hashtable or as a
+ * bloom filter) */
+static void
+test_container_digestset(void *unused)
+{
+  smartlist_t *included = smartlist_create();
+  char d[SHA256_LENGTH];
+  int i;
+  int ok = 1;
+  int false_positives = 0;
+  digestset_t *set = NULL;
+
+  for (i = 0; i < 1000; ++i) {
+    random_bytes((uchar *)d, SHA256_LENGTH);
+    smartlist_add(included, xmemdup(d, SHA256_LENGTH));
+  }
+  set = digestset_new(1000);
+  SMARTLIST_FOREACH(included, const char *, cp,
+                    if (digestset_isin(set, cp))
+                      ok = 0);
+  tt_assert(ok);
+  SMARTLIST_FOREACH(included, const char *, cp,
+                    digestset_add(set, cp));
+  SMARTLIST_FOREACH(included, const char *, cp,
+                    if (!digestset_isin(set, cp))
+                      ok = 0);
+  tt_assert(ok);
+  for (i = 0; i < 1000; ++i) {
+    random_bytes((uchar *)d, SHA256_LENGTH);
+    if (digestset_isin(set, d))
+      ++false_positives;
+  }
+  tt_assert(false_positives < 50); /* Should be far lower. */
+
+ end:
+  if (set)
+    digestset_free(set);
+  SMARTLIST_FOREACH(included, char *, cp, free(cp));
+  smartlist_free(included);
+}
+
+typedef struct pq_entry_t {
+  const char *val;
+  int idx;
+} pq_entry_t;
+
+/** Helper: return a tristate based on comparing two pq_entry_t values. */
+static int
+_compare_strings_for_pqueue(const void *p1, const void *p2)
+{
+  const pq_entry_t *e1=p1, *e2=p2;
+  return strcmp(e1->val, e2->val);
+}
+
+/** Run unit tests for heap-based priority queue functions. */
+static void
+test_container_pqueue(void *unused)
+{
+  smartlist_t *sl = smartlist_create();
+  int (*cmp)(const void *, const void*);
+  const int offset = offsetof(pq_entry_t, idx);
+#define ENTRY(s) pq_entry_t s = { #s, -1 }
+  ENTRY(cows);
+  ENTRY(zebras);
+  ENTRY(fish);
+  ENTRY(frogs);
+  ENTRY(apples);
+  ENTRY(squid);
+  ENTRY(daschunds);
+  ENTRY(eggplants);
+  ENTRY(weissbier);
+  ENTRY(lobsters);
+  ENTRY(roquefort);
+  ENTRY(chinchillas);
+  ENTRY(fireflies);
+
+#define OK() smartlist_pqueue_assert_ok(sl, cmp, offset)
+
+  cmp = _compare_strings_for_pqueue;
+  smartlist_pqueue_add(sl, cmp, offset, &cows);
+  smartlist_pqueue_add(sl, cmp, offset, &zebras);
+  smartlist_pqueue_add(sl, cmp, offset, &fish);
+  smartlist_pqueue_add(sl, cmp, offset, &frogs);
+  smartlist_pqueue_add(sl, cmp, offset, &apples);
+  smartlist_pqueue_add(sl, cmp, offset, &squid);
+  smartlist_pqueue_add(sl, cmp, offset, &daschunds);
+  smartlist_pqueue_add(sl, cmp, offset, &eggplants);
+  smartlist_pqueue_add(sl, cmp, offset, &weissbier);
+  smartlist_pqueue_add(sl, cmp, offset, &lobsters);
+  smartlist_pqueue_add(sl, cmp, offset, &roquefort);
+
+  OK();
+
+  tt_int_op(smartlist_len(sl), ==, 11);
+  tt_ptr_op(smartlist_get(sl, 0), ==, &apples);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &apples);
+  tt_int_op(smartlist_len(sl), ==, 10);
+  OK();
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &cows);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &daschunds);
+  smartlist_pqueue_add(sl, cmp, offset, &chinchillas);
+  OK();
+  smartlist_pqueue_add(sl, cmp, offset, &fireflies);
+  OK();
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &chinchillas);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &eggplants);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fireflies);
+  OK();
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fish);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &frogs);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &lobsters);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &roquefort);
+  OK();
+  tt_int_op(smartlist_len(sl), ==, 3);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &squid);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &weissbier);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &zebras);
+  tt_int_op(smartlist_len(sl), ==, 0);
+  OK();
+
+  /* Now test remove. */
+  smartlist_pqueue_add(sl, cmp, offset, &cows);
+  smartlist_pqueue_add(sl, cmp, offset, &fish);
+  smartlist_pqueue_add(sl, cmp, offset, &frogs);
+  smartlist_pqueue_add(sl, cmp, offset, &apples);
+  smartlist_pqueue_add(sl, cmp, offset, &squid);
+  smartlist_pqueue_add(sl, cmp, offset, &zebras);
+  tt_int_op(smartlist_len(sl), ==, 6);
+  OK();
+  smartlist_pqueue_remove(sl, cmp, offset, &zebras);
+  tt_int_op(smartlist_len(sl), ==, 5);
+  OK();
+  smartlist_pqueue_remove(sl, cmp, offset, &cows);
+  tt_int_op(smartlist_len(sl), ==, 4);
+  OK();
+  smartlist_pqueue_remove(sl, cmp, offset, &apples);
+  tt_int_op(smartlist_len(sl), ==, 3);
+  OK();
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fish);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &frogs);
+  tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &squid);
+  tt_int_op(smartlist_len(sl), ==, 0);
+  OK();
+
+#undef OK
+
+ end:
+
+  smartlist_free(sl);
+}
+
+/** Run unit tests for string-to-void* map functions */
+static void
+test_container_strmap(void *unused)
+{
+  strmap_t *map;
+  strmap_iter_t *iter;
+  const char *k;
+  void *v;
+  char *visited = NULL;
+  smartlist_t *found_keys = NULL;
+
+  map = strmap_new();
+  tt_assert(map);
+  tt_int_op(strmap_size(map), ==, 0);
+  tt_assert(strmap_isempty(map));
+  v = strmap_set(map, "K1", (void*)99);
+  tt_ptr_op(v, ==, NULL);
+  tt_assert(!strmap_isempty(map));
+  v = strmap_set(map, "K2", (void*)101);
+  tt_ptr_op(v, ==, NULL);
+  v = strmap_set(map, "K1", (void*)100);
+  tt_int_op((void*)99, ==, v);
+  tt_ptr_op(strmap_get(map, "K1"), ==, (void*)100);
+  tt_ptr_op(strmap_get(map, "K2"), ==, (void*)101);
+  tt_ptr_op(strmap_get(map, "K-not-there"), ==, NULL);
+  strmap_assert_ok(map);
+
+  v = strmap_remove(map,"K2");
+  strmap_assert_ok(map);
+  tt_ptr_op(v, ==, (void*)101);
+  tt_ptr_op(strmap_get(map, "K2"), ==, NULL);
+  tt_ptr_op(strmap_remove(map, "K2"), ==, NULL);
+
+  strmap_set(map, "K2", (void*)101);
+  strmap_set(map, "K3", (void*)102);
+  strmap_set(map, "K4", (void*)103);
+  tt_int_op(strmap_size(map), ==, 4);
+  strmap_assert_ok(map);
+  strmap_set(map, "K5", (void*)104);
+  strmap_set(map, "K6", (void*)105);
+  strmap_assert_ok(map);
+
+  /* Test iterator. */
+  iter = strmap_iter_init(map);
+  found_keys = smartlist_create();
+  while (!strmap_iter_done(iter)) {
+    strmap_iter_get(iter,&k,&v);
+    smartlist_add(found_keys, xstrdup(k));
+    tt_ptr_op(v, ==, strmap_get(map, k));
+
+    if (!strcmp(k, "K2")) {
+      iter = strmap_iter_next_rmv(map,iter);
+    } else {
+      iter = strmap_iter_next(map,iter);
+    }
+  }
+
+  /* Make sure we removed K2, but not the others. */
+  tt_ptr_op(strmap_get(map, "K2"), ==, NULL);
+  tt_ptr_op(strmap_get(map, "K5"), ==, (void*)104);
+  /* Make sure we visited everyone once */
+  smartlist_sort_strings(found_keys);
+  visited = smartlist_join_strings(found_keys, ":", 0, NULL);
+  tt_str_op(visited, ==, "K1:K2:K3:K4:K5:K6");
+
+  strmap_assert_ok(map);
+  /* Clean up after ourselves. */
+  strmap_free(map, NULL);
+  map = NULL;
+
+  /* Now try some lc functions. */
+  map = strmap_new();
+  strmap_set_lc(map,"Ab.C", (void*)1);
+  tt_ptr_op(strmap_get(map, "ab.c"), ==, (void*)1);
+  strmap_assert_ok(map);
+  tt_ptr_op(strmap_get_lc(map, "AB.C"), ==, (void*)1);
+  tt_ptr_op(strmap_get(map, "AB.C"), ==, NULL);
+  tt_ptr_op(strmap_remove_lc(map, "aB.C"), ==, (void*)1);
+  strmap_assert_ok(map);
+  tt_ptr_op(strmap_get_lc(map, "AB.C"), ==, NULL);
+
+ end:
+  if (map)
+    strmap_free(map,NULL);
+  if (found_keys) {
+    SMARTLIST_FOREACH(found_keys, char *, cp, free(cp));
+    smartlist_free(found_keys);
+  }
+  free(visited);
+}
+
+/** Run unit tests for getting the median of a list. */
+static void
+test_container_order_functions(void *unused)
+{
+  int lst[25], n = 0;
+  //  int a=12,b=24,c=25,d=60,e=77;
+
+#define median() median_int(lst, n)
+
+  lst[n++] = 12;
+  tt_int_op(median(), ==, 12); /* 12 */
+  lst[n++] = 77;
+  //smartlist_shuffle(sl);
+  tt_int_op(median(), ==, 12); /* 12, 77 */
+  lst[n++] = 77;
+  //smartlist_shuffle(sl);
+  tt_int_op(median(), ==, 77); /* 12, 77, 77 */
+  lst[n++] = 24;
+  tt_int_op(median(), ==, 24); /* 12,24,77,77 */
+  lst[n++] = 60;
+  lst[n++] = 12;
+  lst[n++] = 25;
+  //smartlist_shuffle(sl);
+  tt_int_op(median(), ==, 25); /* 12,12,24,25,60,77,77 */
+#undef median
+
+ end:
+  ;
+}
+
+#define T(name)                                          \
+  { #name, test_container_##name, 0, NULL, NULL }
+
+struct testcase_t container_tests[] = {
+  T(smartlist_basic),
+  T(smartlist_strings),
+  T(smartlist_overlap),
+  T(smartlist_digests),
+  T(smartlist_join),
+  T(bitarray),
+  T(digestset),
+  T(strmap),
+  T(pqueue),
+  T(order_functions),
+  END_OF_TESTCASES
+};
+
diff --git a/src/util.c b/src/util.c
index 231c3a8..9b9fa48 100644
--- a/src/util.c
+++ b/src/util.c
@@ -88,6 +88,55 @@ xstrdup(const char *s)
   return xmemdup(s, strlen(s) + 1);
 }
+char *
+xstrndup(const char *s, size_t maxsize)
+{
+  char *copy;
+  size_t size;
+  /* strnlen is not in any standard :-( */
+  for (size = 0; size < maxsize; size++)
+    if (s[size] == '\0')
+      break;
+
+  copy = xmalloc(size + 1);
+  memcpy(copy, s, size);
+  copy[size] = '\0';
+  return copy;
+}
+
+/******************************** Mathematics ********************************/
+
+unsigned int
+ui64_log2(uint64_t u64)
+{
+  unsigned int r = 0;
+  if (u64 >= (((uint64_t)1)<<32)) {
+    u64 >>= 32;
+    r = 32;
+  }
+  if (u64 >= (((uint64_t)1)<<16)) {
+    u64 >>= 16;
+    r += 16;
+  }
+  if (u64 >= (((uint64_t)1)<<8)) {
+    u64 >>= 8;
+    r += 8;
+  }
+  if (u64 >= (((uint64_t)1)<<4)) {
+    u64 >>= 4;
+    r += 4;
+  }
+  if (u64 >= (((uint64_t)1)<<2)) {
+    u64 >>= 2;
+    r += 2;
+  }
+  if (u64 >= (((uint64_t)1)<<1)) {
+    u64 >>= 1;
+    r += 1;
+  }
+  return r;
+}
+
 /************************ Obfsproxy Network Routines *************************/
/**
@@ -206,6 +255,31 @@ obfs_vsnprintf(char *str, size_t size, const char *format, va_list args)
     return -1;
   return r;
 }
+/** Remove from the string <b>s</b> every character which appears in
+ * <b>strip</b>. */
+void
+ascii_strstrip(char *s, const char *strip)
+{
+  char *read = s;
+  while (*read) {
+    if (strchr(strip, *read)) {
+      ++read;
+    } else {
+      *s++ = *read++;
+    }
+  }
+  *s = '\0';
+}
+
+void
+ascii_strlower(char *s)
+{
+  while (*s) {
+    if (*s >= 'A' && *s <= 'Z')
+      *s = *s - 'A' + 'a';
+    ++s;
+  }
+}
/************************ Doubly Linked List (DLL) ******************/
diff --git a/src/util.h b/src/util.h
index d365cbc..e44a711 100644
--- a/src/util.h
+++ b/src/util.h
@@ -8,6 +8,7 @@
 #include "config.h"
 #include <stdarg.h> /* for va_list */
 #include <stddef.h> /* size_t, offsetof, NULL, etc */
+#include <stdint.h> /* intN_t, uintN_t */
#ifndef __GNUC__
 #define __attribute__(x) /* nothing */
@@ -34,6 +35,11 @@ void *xzalloc(size_t size) ATTR_MALLOC; /* clears memory */
 void *xrealloc(void *ptr, size_t size);
 void *xmemdup(const void *ptr, size_t size) ATTR_MALLOC;
 char *xstrdup(const char *s) ATTR_MALLOC;
+char *xstrndup(const char *s, size_t maxsize) ATTR_MALLOC;
+
+/***** Math. *****/
+
+unsigned int ui64_log2(uint64_t u64);
/***** Network functions stuff. *****/
@@ -48,6 +54,18 @@ int init_evdns_base(struct event_base *base);
/***** String functions stuff. *****/
+static inline int ascii_isspace(unsigned char c)
+{
+  return (c == ' ' ||
+          c == '\t' ||
+          c == '\r' ||
+          c == '\n' ||
+          c == '\v' ||
+          c == '\f');
+}
+void ascii_strstrip(char *s, const char *kill);
+void ascii_strlower(char *s);
+
 int obfs_vsnprintf(char *str, size_t size,
                    const char *format, va_list args);
 int obfs_snprintf(char *str, size_t size,
@@ -133,5 +151,4 @@ void log_debug(const char *format, ...)
     log_error("aborted at %s:%d", __FILE__, __LINE__);  \
   } while (0)
-
 #endif

    