Split the routerset code out of routerlist.c

14 files changed, 486 insertions, 445 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index e9d010ee30..d4969239cb 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -33,6 +33,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 #include "statefile.h"
 #include "crypto.h"
 #undef log
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 7ed942c8fe..d9b74bd4c2 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -26,6 +26,7 @@
 #include "rendcommon.h"
 #include "rephist.h"
 #include "routerlist.h"
+#include "routerset.h"
 #include "ht.h"
 
 /********* START VARIABLES **********/
diff --git a/src/or/config.c b/src/or/config.c
index 3536db6d07..99903775b0 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -36,6 +36,7 @@
 #include "router.h"
 #include "util.h"
 #include "routerlist.h"
+#include "routerset.h"
 #include "statefile.h"
 #include "transports.h"
 #ifdef _WIN32
diff --git a/src/or/confparse.c b/src/or/confparse.c
index 203395d081..67cf43fe8c 100644
--- a/src/or/confparse.c
+++ b/src/or/confparse.c
@@ -6,7 +6,7 @@
 
 #include "or.h"
 #include "confparse.h"
-#include "routerlist.h"
+#include "routerset.h"
 
 static uint64_t config_parse_memunit(const char *s, int *ok);
 static int config_parse_msec_interval(const char *s, int *ok);
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index 1592033c54..ade3b48df2 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -33,6 +33,7 @@
 #include "rephist.h"
 #include "router.h"
 #include "routerlist.h"
+#include "routerset.h"
 
 #ifdef HAVE_LINUX_TYPES_H
 #include <linux/types.h>
diff --git a/src/or/directory.c b/src/or/directory.c
index effccc5856..7df91fb57e 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -25,6 +25,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 
 #if defined(EXPORTMALLINFO) && defined(HAVE_MALLOC_H) && defined(HAVE_MALLINFO)
 #ifndef OPENBSD
diff --git a/src/or/include.am b/src/or/include.am
index 5c93e3e598..e9811ec962 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -53,6 +53,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/router.c					\
 	src/or/routerlist.c				\
 	src/or/routerparse.c				\
+	src/or/routerset.c				\
 	src/or/statefile.c				\
 	src/or/status.c					\
 	$(evdns_source)					\
@@ -124,6 +125,7 @@ ORHEADERS = \
 	src/or/replaycache.h				\
 	src/or/router.h					\
 	src/or/routerlist.h				\
+	src/or/routerset.h				\
 	src/or/routerparse.h				\
 	src/or/statefile.h				\
 	src/or/status.h
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 0b6d82bdf4..73e1c41d7b 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -23,6 +23,7 @@
 #include "rephist.h"
 #include "router.h"
 #include "routerlist.h"
+#include "routerset.h"
 
 static extend_info_t *rend_client_get_random_intro_impl(
                           const rend_cache_entry_t *rend_query,
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 394831f857..0bfa17d108 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -26,6 +26,7 @@
 #include "replaycache.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 
 static origin_circuit_t *find_intro_circuit(rend_intro_point_t *intro,
                                             const char *pk_digest);
diff --git a/src/or/router.c b/src/or/router.c
index 91209eef04..052ed38074 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -29,6 +29,7 @@
 #include "routerparse.h"
 #include "statefile.h"
 #include "transports.h"
+#include "routerset.h"
 
 /**
  * \file router.c
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 214c086448..c6f24bf929 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -34,6 +34,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 
 // #define DEBUG_ROUTERLIST
 
@@ -5409,149 +5410,6 @@ routers_sort_by_identity(smartlist_t *routers)
   smartlist_sort(routers, _compare_routerinfo_by_id_digest);
 }
 
-/** A routerset specifies constraints on a set of possible routerinfos, based
- * on their names, identities, or addresses.  It is optimized for determining
- * whether a router is a member or not, in O(1+P) time, where P is the number
- * of address policy constraints. */
-struct routerset_t {
-  /** A list of strings for the elements of the policy.  Each string is either
-   * a nickname, a hexadecimal identity fingerprint, or an address policy.  A
-   * router belongs to the set if its nickname OR its identity OR its address
-   * matches an entry here. */
-  smartlist_t *list;
-  /** A map from lowercase nicknames of routers in the set to (void*)1 */
-  strmap_t *names;
-  /** A map from identity digests routers in the set to (void*)1 */
-  digestmap_t *digests;
-  /** An address policy for routers in the set.  For implementation reasons,
-   * a router belongs to the set if it is _rejected_ by this policy. */
-  smartlist_t *policies;
-
-  /** A human-readable description of what this routerset is for.  Used in
-   * log messages. */
-  char *description;
-
-  /** A list of the country codes in this set. */
-  smartlist_t *country_names;
-  /** Total number of countries we knew about when we built <b>countries</b>.*/
-  int n_countries;
-  /** Bit array mapping the return value of geoip_get_country() to 1 iff the
-   * country is a member of this routerset.  Note that we MUST call
-   * routerset_refresh_countries() whenever the geoip country list is
-   * reloaded. */
-  bitarray_t *countries;
-};
-
-/** Return a new empty routerset. */
-routerset_t *
-routerset_new(void)
-{
-  routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
-  result->list = smartlist_new();
-  result->names = strmap_new();
-  result->digests = digestmap_new();
-  result->policies = smartlist_new();
-  result->country_names = smartlist_new();
-  return result;
-}
-
-/** If <b>c</b> is a country code in the form {cc}, return a newly allocated
- * string holding the "cc" part.  Else, return NULL. */
-static char *
-routerset_get_countryname(const char *c)
-{
-  char *country;
-
-  if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
-    return NULL;
-
-  country = tor_strndup(c+1, 2);
-  tor_strlower(country);
-  return country;
-}
-
-/** Update the routerset's <b>countries</b> bitarray_t. Called whenever
- * the GeoIP database is reloaded.
- */
-void
-routerset_refresh_countries(routerset_t *target)
-{
-  int cc;
-  bitarray_free(target->countries);
-
-  if (!geoip_is_loaded()) {
-    target->countries = NULL;
-    target->n_countries = 0;
-    return;
-  }
-  target->n_countries = geoip_get_n_countries();
-  target->countries = bitarray_init_zero(target->n_countries);
-  SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
-    cc = geoip_get_country(country);
-    if (cc >= 0) {
-      tor_assert(cc < target->n_countries);
-      bitarray_set(target->countries, cc);
-    } else {
-      log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.",
-          country);
-    }
-  } SMARTLIST_FOREACH_END(country);
-}
-
-/** Parse the string <b>s</b> to create a set of routerset entries, and add
- * them to <b>target</b>.  In log messages, refer to the string as
- * <b>description</b>.  Return 0 on success, -1 on failure.
- *
- * Three kinds of elements are allowed in routersets: nicknames, IP address
- * patterns, and fingerprints.  They may be surrounded by optional space, and
- * must be separated by commas.
- */
-int
-routerset_parse(routerset_t *target, const char *s, const char *description)
-{
-  int r = 0;
-  int added_countries = 0;
-  char *countryname;
-  smartlist_t *list = smartlist_new();
-  smartlist_split_string(list, s, ",",
-                         SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
-  SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
-      addr_policy_t *p;
-      if (is_legal_hexdigest(nick)) {
-        char d[DIGEST_LEN];
-        if (*nick == '$')
-          ++nick;
-        log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
-        base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
-        digestmap_set(target->digests, d, (void*)1);
-      } else if (is_legal_nickname(nick)) {
-        log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
-        strmap_set_lc(target->names, nick, (void*)1);
-      } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
-        log_debug(LD_CONFIG, "Adding country %s to %s", nick,
-                  description);
-        smartlist_add(target->country_names, countryname);
-        added_countries = 1;
-      } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
-                 (p = router_parse_addr_policy_item_from_string(
-                                     nick, ADDR_POLICY_REJECT))) {
-        log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
-        smartlist_add(target->policies, p);
-      } else {
-        log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick,
-                 description);
-        r = -1;
-        tor_free(nick);
-        SMARTLIST_DEL_CURRENT(list, nick);
-      }
-  } SMARTLIST_FOREACH_END(nick);
-  smartlist_add_all(target->list, list);
-  smartlist_free(list);
-  if (added_countries)
-    routerset_refresh_countries(target);
-  return r;
-}
-
 /** Called when we change a node set, or when we reload the geoip list:
  * recompute all country info in all configuration node sets and in the
  * routerlist. */
@@ -5574,275 +5432,6 @@ refresh_all_country_info(void)
   nodelist_refresh_countries();
 }
 
-/** Add all members of the set <b>source</b> to <b>target</b>. */
-void
-routerset_union(routerset_t *target, const routerset_t *source)
-{
-  char *s;
-  tor_assert(target);
-  if (!source || !source->list)
-    return;
-  s = routerset_to_string(source);
-  routerset_parse(target, s, "other routerset");
-  tor_free(s);
-}
-
-/** Return true iff <b>set</b> lists only nicknames and digests, and includes
- * no IP ranges or countries. */
-int
-routerset_is_list(const routerset_t *set)
-{
-  return smartlist_len(set->country_names) == 0 &&
-    smartlist_len(set->policies) == 0;
-}
-
-/** Return true iff we need a GeoIP IP-to-country database to make sense of
- * <b>set</b>. */
-int
-routerset_needs_geoip(const routerset_t *set)
-{
-  return set && smartlist_len(set->country_names);
-}
-
-/** Return true iff there are no entries in <b>set</b>. */
-int
-routerset_is_empty(const routerset_t *set)
-{
-  return !set || smartlist_len(set->list) == 0;
-}
-
-/** Helper.  Return true iff <b>set</b> contains a router based on the other
- * provided fields.  Return higher values for more specific subentries: a
- * single router is more specific than an address range of routers, which is
- * more specific in turn than a country code.
- *
- * (If country is -1, then we take the country
- * from addr.) */
-static int
-routerset_contains(const routerset_t *set, const tor_addr_t *addr,
-                   uint16_t orport,
-                   const char *nickname, const char *id_digest,
-                   country_t country)
-{
-  if (!set || !set->list)
-    return 0;
-  if (nickname && strmap_get_lc(set->names, nickname))
-    return 4;
-  if (id_digest && digestmap_get(set->digests, id_digest))
-    return 4;
-  if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
-      == ADDR_POLICY_REJECTED)
-    return 3;
-  if (set->countries) {
-    if (country < 0 && addr)
-      country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr));
-
-    if (country >= 0 && country < set->n_countries &&
-        bitarray_is_set(set->countries, country))
-      return 2;
-  }
-  return 0;
-}
-
-/** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */
-int
-routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
-{
-  return routerset_contains(set,
-                            &ei->addr,
-                            ei->port,
-                            ei->nickname,
-                            ei->identity_digest,
-                            -1 /*country*/);
-}
-
-/** Return true iff <b>ri</b> is in <b>set</b>.  If country is <b>-1</b>, we
- * look up the country. */
-int
-routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
-                          country_t country)
-{
-  tor_addr_t addr;
-  tor_addr_from_ipv4h(&addr, ri->addr);
-  return routerset_contains(set,
-                            &addr,
-                            ri->or_port,
-                            ri->nickname,
-                            ri->cache_info.identity_digest,
-                            country);
-}
-
-/** Return true iff <b>rs</b> is in <b>set</b>.  If country is <b>-1</b>, we
- * look up the country. */
-int
-routerset_contains_routerstatus(const routerset_t *set,
-                                const routerstatus_t *rs,
-                                country_t country)
-{
-  tor_addr_t addr;
-  tor_addr_from_ipv4h(&addr, rs->addr);
-  return routerset_contains(set,
-                            &addr,
-                            rs->or_port,
-                            rs->nickname,
-                            rs->identity_digest,
-                            country);
-}
-
-/** Return true iff <b>node</b> is in <b>set</b>. */
-int
-routerset_contains_node(const routerset_t *set, const node_t *node)
-{
-  if (node->rs)
-    return routerset_contains_routerstatus(set, node->rs, node->country);
-  else if (node->ri)
-    return routerset_contains_router(set, node->ri, node->country);
-  else
-    return 0;
-}
-
-/** Add every known node_t that is a member of <b>routerset</b> to
- * <b>out</b>, but never add any that are part of <b>excludeset</b>.
- * If <b>running_only</b>, only add the running ones. */
-void
-routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
-                        const routerset_t *excludeset, int running_only)
-{ /* XXXX MOVE */
-  tor_assert(out);
-  if (!routerset || !routerset->list)
-    return;
-
-  if (routerset_is_list(routerset)) {
-    /* No routers are specified by type; all are given by name or digest.
-     * we can do a lookup in O(len(routerset)). */
-    SMARTLIST_FOREACH(routerset->list, const char *, name, {
-        const node_t *node = node_get_by_nickname(name, 1);
-        if (node) {
-          if (!running_only || node->is_running)
-            if (!routerset_contains_node(excludeset, node))
-              smartlist_add(out, (void*)node);
-        }
-    });
-  } else {
-    /* We need to iterate over the routerlist to get all the ones of the
-     * right kind. */
-    smartlist_t *nodes = nodelist_get_list();
-    SMARTLIST_FOREACH(nodes, const node_t *, node, {
-        if (running_only && !node->is_running)
-          continue;
-        if (routerset_contains_node(routerset, node) &&
-            !routerset_contains_node(excludeset, node))
-          smartlist_add(out, (void*)node);
-    });
-  }
-}
-
-#if 0
-/** Add to <b>target</b> every node_t from <b>source</b> except:
- *
- * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in
- * <b>include</b>; and
- * 2) Don't add it if <b>exclude</b> is non-empty and the relay is
- * excluded in a more specific fashion by <b>exclude</b>.
- * 3) If <b>running_only</b>, don't add non-running routers.
- */
-void
-routersets_get_node_disjunction(smartlist_t *target,
-                           const smartlist_t *source,
-                           const routerset_t *include,
-                           const routerset_t *exclude, int running_only)
-{
-  SMARTLIST_FOREACH(source, const node_t *, node, {
-    int include_result;
-    if (running_only && !node->is_running)
-      continue;
-    if (!routerset_is_empty(include))
-      include_result = routerset_contains_node(include, node);
-    else
-      include_result = 1;
-
-    if (include_result) {
-      int exclude_result = routerset_contains_node(exclude, node);
-      if (include_result >= exclude_result)
-        smartlist_add(target, (void*)node);
-    }
-  });
-}
-#endif
-
-/** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */
-void
-routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
-{ /*XXXX MOVE ? */
-  tor_assert(lst);
-  if (!routerset)
-    return;
-  SMARTLIST_FOREACH(lst, const node_t *, node, {
-      if (routerset_contains_node(routerset, node)) {
-        //log_debug(LD_DIR, "Subtracting %s",r->nickname);
-        SMARTLIST_DEL_CURRENT(lst, node);
-      }
-    });
-}
-
-/** Return a new string that when parsed by routerset_parse_string() will
- * yield <b>set</b>. */
-char *
-routerset_to_string(const routerset_t *set)
-{
-  if (!set || !set->list)
-    return tor_strdup("");
-  return smartlist_join_strings(set->list, ",", 0, NULL);
-}
-
-/** Helper: return true iff old and new are both NULL, or both non-NULL
- * equal routersets. */
-int
-routerset_equal(const routerset_t *old, const routerset_t *new)
-{
-  if (routerset_is_empty(old) && routerset_is_empty(new)) {
-    /* Two empty sets are equal */
-    return 1;
-  } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
-    /* An empty set is equal to nothing else. */
-    return 0;
-  }
-  tor_assert(old != NULL);
-  tor_assert(new != NULL);
-
-  if (smartlist_len(old->list) != smartlist_len(new->list))
-    return 0;
-
-  SMARTLIST_FOREACH(old->list, const char *, cp1, {
-    const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
-    if (strcmp(cp1, cp2))
-      return 0;
-  });
-
-  return 1;
-}
-
-/** Free all storage held in <b>routerset</b>. */
-void
-routerset_free(routerset_t *routerset)
-{
-  if (!routerset)
-    return;
-
-  SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
-  smartlist_free(routerset->list);
-  SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
-                    addr_policy_free(p));
-  smartlist_free(routerset->policies);
-  SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
-  smartlist_free(routerset->country_names);
-
-  strmap_free(routerset->names, NULL);
-  digestmap_free(routerset->digests, NULL);
-  bitarray_free(routerset->countries);
-  tor_free(routerset);
-}
-
 /** Refresh the country code of <b>ri</b>.  This function MUST be called on
  * each router when the GeoIP database is reloaded, and on all new routers. */
 void
diff --git a/src/or/routerlist.h b/src/or/routerlist.h
index ab58b9ee5a..28856109b7 100644
--- a/src/or/routerlist.h
+++ b/src/or/routerlist.h
@@ -166,38 +166,6 @@ void routerlist_assert_ok(const routerlist_t *rl);
 const char *esc_router_info(const routerinfo_t *router);
 void routers_sort_by_identity(smartlist_t *routers);
 
-routerset_t *routerset_new(void);
-void routerset_refresh_countries(routerset_t *rs);
-int routerset_parse(routerset_t *target, const char *s,
-                    const char *description);
-void routerset_union(routerset_t *target, const routerset_t *source);
-int routerset_is_list(const routerset_t *set);
-int routerset_needs_geoip(const routerset_t *set);
-int routerset_is_empty(const routerset_t *set);
-int routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
-                              country_t country);
-int routerset_contains_routerstatus(const routerset_t *set,
-                                    const routerstatus_t *rs,
-                                    country_t country);
-int routerset_contains_extendinfo(const routerset_t *set,
-                                  const extend_info_t *ei);
-
-int routerset_contains_node(const routerset_t *set, const node_t *node);
-void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
-                             const routerset_t *excludeset,
-                             int running_only);
-#if 0
-void routersets_get_node_disjunction(smartlist_t *target,
-                                const smartlist_t *source,
-                                const routerset_t *include,
-                                const routerset_t *exclude, int running_only);
-#endif
-void routerset_subtract_nodes(smartlist_t *out,
-                                const routerset_t *routerset);
-
-char *routerset_to_string(const routerset_t *routerset);
-int routerset_equal(const routerset_t *old, const routerset_t *new);
-void routerset_free(routerset_t *routerset);
 void refresh_all_country_info(void);
 
 int hid_serv_get_responsible_directories(smartlist_t *responsible_dirs,
diff --git a/src/or/routerset.c b/src/or/routerset.c
new file mode 100644
index 0000000000..263cf79d70
--- /dev/null
+++ b/src/or/routerset.c
@@ -0,0 +1,426 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or.h"
+#include "geoip.h"
+#include "nodelist.h"
+#include "policies.h"
+#include "router.h"
+#include "routerparse.h"
+#include "routerset.h"
+
+/** A routerset specifies constraints on a set of possible routerinfos, based
+ * on their names, identities, or addresses.  It is optimized for determining
+ * whether a router is a member or not, in O(1+P) time, where P is the number
+ * of address policy constraints. */
+struct routerset_t {
+  /** A list of strings for the elements of the policy.  Each string is either
+   * a nickname, a hexadecimal identity fingerprint, or an address policy.  A
+   * router belongs to the set if its nickname OR its identity OR its address
+   * matches an entry here. */
+  smartlist_t *list;
+  /** A map from lowercase nicknames of routers in the set to (void*)1 */
+  strmap_t *names;
+  /** A map from identity digests routers in the set to (void*)1 */
+  digestmap_t *digests;
+  /** An address policy for routers in the set.  For implementation reasons,
+   * a router belongs to the set if it is _rejected_ by this policy. */
+  smartlist_t *policies;
+
+  /** A human-readable description of what this routerset is for.  Used in
+   * log messages. */
+  char *description;
+
+  /** A list of the country codes in this set. */
+  smartlist_t *country_names;
+  /** Total number of countries we knew about when we built <b>countries</b>.*/
+  int n_countries;
+  /** Bit array mapping the return value of geoip_get_country() to 1 iff the
+   * country is a member of this routerset.  Note that we MUST call
+   * routerset_refresh_countries() whenever the geoip country list is
+   * reloaded. */
+  bitarray_t *countries;
+};
+
+/** Return a new empty routerset. */
+routerset_t *
+routerset_new(void)
+{
+  routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
+  result->list = smartlist_new();
+  result->names = strmap_new();
+  result->digests = digestmap_new();
+  result->policies = smartlist_new();
+  result->country_names = smartlist_new();
+  return result;
+}
+
+/** If <b>c</b> is a country code in the form {cc}, return a newly allocated
+ * string holding the "cc" part.  Else, return NULL. */
+static char *
+routerset_get_countryname(const char *c)
+{
+  char *country;
+
+  if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
+    return NULL;
+
+  country = tor_strndup(c+1, 2);
+  tor_strlower(country);
+  return country;
+}
+
+/** Update the routerset's <b>countries</b> bitarray_t. Called whenever
+ * the GeoIP database is reloaded.
+ */
+void
+routerset_refresh_countries(routerset_t *target)
+{
+  int cc;
+  bitarray_free(target->countries);
+
+  if (!geoip_is_loaded()) {
+    target->countries = NULL;
+    target->n_countries = 0;
+    return;
+  }
+  target->n_countries = geoip_get_n_countries();
+  target->countries = bitarray_init_zero(target->n_countries);
+  SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
+    cc = geoip_get_country(country);
+    if (cc >= 0) {
+      tor_assert(cc < target->n_countries);
+      bitarray_set(target->countries, cc);
+    } else {
+      log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.",
+          country);
+    }
+  } SMARTLIST_FOREACH_END(country);
+}
+
+/** Parse the string <b>s</b> to create a set of routerset entries, and add
+ * them to <b>target</b>.  In log messages, refer to the string as
+ * <b>description</b>.  Return 0 on success, -1 on failure.
+ *
+ * Three kinds of elements are allowed in routersets: nicknames, IP address
+ * patterns, and fingerprints.  They may be surrounded by optional space, and
+ * must be separated by commas.
+ */
+int
+routerset_parse(routerset_t *target, const char *s, const char *description)
+{
+  int r = 0;
+  int added_countries = 0;
+  char *countryname;
+  smartlist_t *list = smartlist_new();
+  smartlist_split_string(list, s, ",",
+                         SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
+  SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
+      addr_policy_t *p;
+      if (is_legal_hexdigest(nick)) {
+        char d[DIGEST_LEN];
+        if (*nick == '$')
+          ++nick;
+        log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
+        base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
+        digestmap_set(target->digests, d, (void*)1);
+      } else if (is_legal_nickname(nick)) {
+        log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
+        strmap_set_lc(target->names, nick, (void*)1);
+      } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
+        log_debug(LD_CONFIG, "Adding country %s to %s", nick,
+                  description);
+        smartlist_add(target->country_names, countryname);
+        added_countries = 1;
+      } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
+                 (p = router_parse_addr_policy_item_from_string(
+                                     nick, ADDR_POLICY_REJECT))) {
+        log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
+        smartlist_add(target->policies, p);
+      } else {
+        log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick,
+                 description);
+        r = -1;
+        tor_free(nick);
+        SMARTLIST_DEL_CURRENT(list, nick);
+      }
+  } SMARTLIST_FOREACH_END(nick);
+  smartlist_add_all(target->list, list);
+  smartlist_free(list);
+  if (added_countries)
+    routerset_refresh_countries(target);
+  return r;
+}
+
+/** Add all members of the set <b>source</b> to <b>target</b>. */
+void
+routerset_union(routerset_t *target, const routerset_t *source)
+{
+  char *s;
+  tor_assert(target);
+  if (!source || !source->list)
+    return;
+  s = routerset_to_string(source);
+  routerset_parse(target, s, "other routerset");
+  tor_free(s);
+}
+
+/** Return true iff <b>set</b> lists only nicknames and digests, and includes
+ * no IP ranges or countries. */
+int
+routerset_is_list(const routerset_t *set)
+{
+  return smartlist_len(set->country_names) == 0 &&
+    smartlist_len(set->policies) == 0;
+}
+
+/** Return true iff we need a GeoIP IP-to-country database to make sense of
+ * <b>set</b>. */
+int
+routerset_needs_geoip(const routerset_t *set)
+{
+  return set && smartlist_len(set->country_names);
+}
+
+/** Return true iff there are no entries in <b>set</b>. */
+int
+routerset_is_empty(const routerset_t *set)
+{
+  return !set || smartlist_len(set->list) == 0;
+}
+
+/** Helper.  Return true iff <b>set</b> contains a router based on the other
+ * provided fields.  Return higher values for more specific subentries: a
+ * single router is more specific than an address range of routers, which is
+ * more specific in turn than a country code.
+ *
+ * (If country is -1, then we take the country
+ * from addr.) */
+static int
+routerset_contains(const routerset_t *set, const tor_addr_t *addr,
+                   uint16_t orport,
+                   const char *nickname, const char *id_digest,
+                   country_t country)
+{
+  if (!set || !set->list)
+    return 0;
+  if (nickname && strmap_get_lc(set->names, nickname))
+    return 4;
+  if (id_digest && digestmap_get(set->digests, id_digest))
+    return 4;
+  if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
+      == ADDR_POLICY_REJECTED)
+    return 3;
+  if (set->countries) {
+    if (country < 0 && addr)
+      country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr));
+
+    if (country >= 0 && country < set->n_countries &&
+        bitarray_is_set(set->countries, country))
+      return 2;
+  }
+  return 0;
+}
+
+/** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */
+int
+routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
+{
+  return routerset_contains(set,
+                            &ei->addr,
+                            ei->port,
+                            ei->nickname,
+                            ei->identity_digest,
+                            -1 /*country*/);
+}
+
+/** Return true iff <b>ri</b> is in <b>set</b>.  If country is <b>-1</b>, we
+ * look up the country. */
+int
+routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
+                          country_t country)
+{
+  tor_addr_t addr;
+  tor_addr_from_ipv4h(&addr, ri->addr);
+  return routerset_contains(set,
+                            &addr,
+                            ri->or_port,
+                            ri->nickname,
+                            ri->cache_info.identity_digest,
+                            country);
+}
+
+/** Return true iff <b>rs</b> is in <b>set</b>.  If country is <b>-1</b>, we
+ * look up the country. */
+int
+routerset_contains_routerstatus(const routerset_t *set,
+                                const routerstatus_t *rs,
+                                country_t country)
+{
+  tor_addr_t addr;
+  tor_addr_from_ipv4h(&addr, rs->addr);
+  return routerset_contains(set,
+                            &addr,
+                            rs->or_port,
+                            rs->nickname,
+                            rs->identity_digest,
+                            country);
+}
+
+/** Return true iff <b>node</b> is in <b>set</b>. */
+int
+routerset_contains_node(const routerset_t *set, const node_t *node)
+{
+  if (node->rs)
+    return routerset_contains_routerstatus(set, node->rs, node->country);
+  else if (node->ri)
+    return routerset_contains_router(set, node->ri, node->country);
+  else
+    return 0;
+}
+
+/** Add every known node_t that is a member of <b>routerset</b> to
+ * <b>out</b>, but never add any that are part of <b>excludeset</b>.
+ * If <b>running_only</b>, only add the running ones. */
+void
+routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
+                        const routerset_t *excludeset, int running_only)
+{
+  tor_assert(out);
+  if (!routerset || !routerset->list)
+    return;
+
+  if (routerset_is_list(routerset)) {
+    /* No routers are specified by type; all are given by name or digest.
+     * we can do a lookup in O(len(routerset)). */
+    SMARTLIST_FOREACH(routerset->list, const char *, name, {
+        const node_t *node = node_get_by_nickname(name, 1);
+        if (node) {
+          if (!running_only || node->is_running)
+            if (!routerset_contains_node(excludeset, node))
+              smartlist_add(out, (void*)node);
+        }
+    });
+  } else {
+    /* We need to iterate over the routerlist to get all the ones of the
+     * right kind. */
+    smartlist_t *nodes = nodelist_get_list();
+    SMARTLIST_FOREACH(nodes, const node_t *, node, {
+        if (running_only && !node->is_running)
+          continue;
+        if (routerset_contains_node(routerset, node) &&
+            !routerset_contains_node(excludeset, node))
+          smartlist_add(out, (void*)node);
+    });
+  }
+}
+
+#if 0
+/** Add to <b>target</b> every node_t from <b>source</b> except:
+ *
+ * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in
+ * <b>include</b>; and
+ * 2) Don't add it if <b>exclude</b> is non-empty and the relay is
+ * excluded in a more specific fashion by <b>exclude</b>.
+ * 3) If <b>running_only</b>, don't add non-running routers.
+ */
+void
+routersets_get_node_disjunction(smartlist_t *target,
+                           const smartlist_t *source,
+                           const routerset_t *include,
+                           const routerset_t *exclude, int running_only)
+{
+  SMARTLIST_FOREACH(source, const node_t *, node, {
+    int include_result;
+    if (running_only && !node->is_running)
+      continue;
+    if (!routerset_is_empty(include))
+      include_result = routerset_contains_node(include, node);
+    else
+      include_result = 1;
+
+    if (include_result) {
+      int exclude_result = routerset_contains_node(exclude, node);
+      if (include_result >= exclude_result)
+        smartlist_add(target, (void*)node);
+    }
+  });
+}
+#endif
+
+/** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */
+void
+routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
+{
+  tor_assert(lst);
+  if (!routerset)
+    return;
+  SMARTLIST_FOREACH(lst, const node_t *, node, {
+      if (routerset_contains_node(routerset, node)) {
+        //log_debug(LD_DIR, "Subtracting %s",r->nickname);
+        SMARTLIST_DEL_CURRENT(lst, node);
+      }
+    });
+}
+
+/** Return a new string that when parsed by routerset_parse_string() will
+ * yield <b>set</b>. */
+char *
+routerset_to_string(const routerset_t *set)
+{
+  if (!set || !set->list)
+    return tor_strdup("");
+  return smartlist_join_strings(set->list, ",", 0, NULL);
+}
+
+/** Helper: return true iff old and new are both NULL, or both non-NULL
+ * equal routersets. */
+int
+routerset_equal(const routerset_t *old, const routerset_t *new)
+{
+  if (routerset_is_empty(old) && routerset_is_empty(new)) {
+    /* Two empty sets are equal */
+    return 1;
+  } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
+    /* An empty set is equal to nothing else. */
+    return 0;
+  }
+  tor_assert(old != NULL);
+  tor_assert(new != NULL);
+
+  if (smartlist_len(old->list) != smartlist_len(new->list))
+    return 0;
+
+  SMARTLIST_FOREACH(old->list, const char *, cp1, {
+    const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
+    if (strcmp(cp1, cp2))
+      return 0;
+  });
+
+  return 1;
+}
+
+/** Free all storage held in <b>routerset</b>. */
+void
+routerset_free(routerset_t *routerset)
+{
+  if (!routerset)
+    return;
+
+  SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
+  smartlist_free(routerset->list);
+  SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
+                    addr_policy_free(p));
+  smartlist_free(routerset->policies);
+  SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
+  smartlist_free(routerset->country_names);
+
+  strmap_free(routerset->names, NULL);
+  digestmap_free(routerset->digests, NULL);
+  bitarray_free(routerset->countries);
+  tor_free(routerset);
+}
+
diff --git a/src/or/routerset.h b/src/or/routerset.h
new file mode 100644
index 0000000000..ad0832e4df
--- /dev/null
+++ b/src/or/routerset.h
@@ -0,0 +1,48 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file routerlist.h
+ * \brief Header file for routerset.c
+ **/
+
+#ifndef TOR_ROUTERSET_H
+#define TOR_ROUTERSET_H
+
+routerset_t *routerset_new(void);
+void routerset_refresh_countries(routerset_t *rs);
+int routerset_parse(routerset_t *target, const char *s,
+                    const char *description);
+void routerset_union(routerset_t *target, const routerset_t *source);
+int routerset_is_list(const routerset_t *set);
+int routerset_needs_geoip(const routerset_t *set);
+int routerset_is_empty(const routerset_t *set);
+int routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
+                              country_t country);
+int routerset_contains_routerstatus(const routerset_t *set,
+                                    const routerstatus_t *rs,
+                                    country_t country);
+int routerset_contains_extendinfo(const routerset_t *set,
+                                  const extend_info_t *ei);
+
+int routerset_contains_node(const routerset_t *set, const node_t *node);
+void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
+                             const routerset_t *excludeset,
+                             int running_only);
+#if 0
+void routersets_get_node_disjunction(smartlist_t *target,
+                                const smartlist_t *source,
+                                const routerset_t *include,
+                                const routerset_t *exclude, int running_only);
+#endif
+void routerset_subtract_nodes(smartlist_t *out,
+                                const routerset_t *routerset);
+
+char *routerset_to_string(const routerset_t *routerset);
+int routerset_equal(const routerset_t *old, const routerset_t *new);
+void routerset_free(routerset_t *routerset);
+
+#endif
+