treetrie-2015/route.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <stdarg.h>
#include <errno.h>
#include <assert.h>

#include "treetrie.h"
#include "critbit.h"
#include "route.h"

static inline tt_node_ptr_t rseq(tt_arena_t *a, tt_atom_t s, tt_node_ptr_t r) {
  if (TT_EMPTY_P(r)) {
    return TT_EMPTY;
  }
  assert(s != TT_WILD);
  return tt_cons_branch(a, TT_EMPTY, RET_IF_NO_PTR(tt_dict_singleton(a, s, r)));
}

static inline tt_node_ptr_t rwild(tt_arena_t *a, tt_node_ptr_t r) {
  if (TT_EMPTY_P(r)) {
    return TT_EMPTY;
  }
  return tt_cons_branch(a, r, TT_EMPTY_DICT);
}

static inline tt_node_ptr_t rbranch(tt_arena_t *a,
				    tt_node_ptr_t wild, /* trie */
				    tt_node_ptr_t others) /* dict */
{
  if (TT_EMPTY_DICT_P(others)) {
    if (TT_EMPTY_P(wild)) {
      return TT_EMPTY;
    } else if (tt_ptr_tag(wild) == TT_TAG_TAIL) {
      return wild;
    }
  }
  return tt_cons_branch(a, wild, others);
}

static inline tt_node_ptr_t rwildseq(tt_arena_t *a, tt_node_ptr_t r) {
  if (TT_EMPTY_P(r)) {
    return TT_EMPTY;
  }
  return tt_cons_tail(a, r);
}

static inline tt_node_ptr_t runwildseq(tt_arena_t *a, tt_node_ptr_t r) {
  if (tt_ptr_tag(r) == TT_TAG_TAIL) {
    return TT_TAIL_TRIE(a,r);
  } else {
    return TT_EMPTY;
  }
}

static inline tt_node_ptr_t rlookup_dict(tt_arena_t *a,
					 tt_node_ptr_t wild,
					 tt_node_ptr_t others,
					 tt_atom_t key)
{
  tt_node_ptr_t result;
  result = tt_dict_get(a, others, key);
  if (!TT_NO_PTR_P(result)) {
    return result;
  }
  result = wild;
  switch (key) {
    case TT_BOS: return rwildseq(a, result);
    case TT_EOS: return runwildseq(a, result);
    default:     return result;
  }
}

static inline tt_node_ptr_t rlookup(tt_arena_t *a,
				    tt_node_ptr_t r,
				    tt_atom_t key)
{
  assert(tt_ptr_tag(r) == TT_TAG_BRANCH);
  return rlookup_dict(a, TT_BRANCH_WILDCARD(a,r), TT_BRANCH_OTHERS(a,r), key);
}

static inline tt_node_ptr_t rupdate_dict(tt_arena_t *a,
					 tt_node_ptr_t old_wild, /* trie */
					 tt_node_ptr_t old_others, /* dict */
					 tt_atom_t key,
					 tt_node_ptr_t k) /* trie */
{
  assert(key != TT_WILD);
  assert(TT_EMPTY_DICT_P(old_others) || tt_ptr_tag(old_others) == TT_TAG_DICT);
  /* printf("rupdate_dict key %d k %u/%u old_wild %u/%u old_others %u/%u\n", */
  /* 	 key, */
  /* 	 tt_ptr_idx(k), */
  /* 	 tt_ptr_tag(k), */
  /* 	 tt_ptr_idx(old_wild), */
  /* 	 tt_ptr_tag(old_wild), */
  /* 	 tt_ptr_idx(old_others), */
  /* 	 tt_ptr_tag(old_others)); */

#define OTHERS_SANS_KEY() (tt_dict_remove(a, old_others, key))
#define OTHERS_WITH_KEY() (tt_dict_set(a, old_others, key, k))

  switch (key) {
    case TT_BOS:
      if (tt_ptr_tag(k) == TT_TAG_TAIL) {
	return (TT_TAIL_TRIE(a,k) == old_wild) ? OTHERS_SANS_KEY() : OTHERS_WITH_KEY();
      } else {
	return TT_EMPTY_P(k) ? OTHERS_SANS_KEY() : OTHERS_WITH_KEY();
      }
    case TT_EOS:
      if (tt_ptr_tag(old_wild) == TT_TAG_TAIL) {
	return (TT_TAIL_TRIE(a,old_wild) == k) ? OTHERS_SANS_KEY() : OTHERS_WITH_KEY();
      } else {
	return TT_EMPTY_P(k) ? OTHERS_SANS_KEY() : OTHERS_WITH_KEY();
      }
    default:
      return (k == old_wild) ? OTHERS_SANS_KEY() : OTHERS_WITH_KEY();
  }

#undef OTHERS_SANS_KEY
#undef OTHERS_WITH_KEY
}

/* static inline tt_node_ptr_t rupdate(tt_arena_t *a, */
/* 				    tt_node_ptr_t r0, /\* branch *\/ */
/* 				    tt_atom_t key, */
/* 				    tt_node_ptr_t k) /\* trie *\/ */
/* { */
/*   assert(key != TT_WILD); */
/*   if (TT_EMPTY_P(r0)) { */
/*     return rseq(a, key, k); */
/*   } else { */
/*     tt_node_ptr_t new_others; */
/*     assert(tt_ptr_tag(r0) == TT_TAG_BRANCH); */
/*     new_others = rupdate_dict(a, TT_BRANCH_WILDCARD(a,r0), TT_BRANCH_OTHERS(a,r0), key, k); */
/*     return rbranch(a, TT_BRANCH_WILDCARD(a,r0), RET_IF_NO_PTR(new_others)); */
/*   } */
/* } */

static inline tt_node_ptr_t expand(tt_arena_t *a, tt_node_ptr_t tailnode) {
  tt_node_ptr_t others = RET_IF_NO_PTR(tt_dict_singleton(a, TT_EOS, TT_TAIL_TRIE(a,tailnode)));
  return rbranch(a, tailnode, others);
}

static inline tt_node_ptr_t collapse(tt_arena_t *a, tt_node_ptr_t n) {
  /* This is a hand-inlined version of rupdate followed by rlookup of
     TT_EOS, effectively undoing expand(). */
  if (tt_ptr_tag(n) == TT_TAG_BRANCH) {
    tt_node_ptr_t o = TT_BRANCH_OTHERS(a,n);
    if (tt_ptr_tag(o) == TT_TAG_DICT) {
      tt_node_ptr_t eos_trie = tt_dict_get(a, o, TT_EOS);
      if (!TT_NO_PTR_P(eos_trie)) {
	tt_node_ptr_t w = TT_BRANCH_WILDCARD(a,n);
	if (tt_ptr_tag(w) == TT_TAG_TAIL && eos_trie == TT_TAIL_TRIE(a,w)) {
	  return rbranch(a, w, RET_IF_NO_PTR(tt_dict_remove(a, o, TT_EOS)));
	}
      }
    }
  }
  return n;
}

struct tt_trie_combine_context {
  tt_arena_t *a;
  int left_empty_keep;
  int right_empty_keep;
  int left_base_keep;
  int right_base_keep;
  void *f_context;
  /* Should return a tt_grab'd result. */
  tt_node_ptr_t (*f)(void *f_context, tt_node_ptr_t r1, tt_node_ptr_t r2);
};

struct tt_trie_combine_examine_key_context {
  struct tt_trie_combine_context *c;
  tt_arena_t *a; /* the same as from tt_trie_combine_context */
  tt_node_ptr_t w1;
  tt_node_ptr_t w2;
  tt_node_ptr_t dict1;
  tt_node_ptr_t dict2;
  tt_node_ptr_t result_wild; /* grab'd */
  tt_node_ptr_t result_others; /* grab'd */
};

/* Forward declaration (mutual recursion) */
static tt_node_ptr_t tt_trie_combine_g(struct tt_trie_combine_context *c,
				       tt_node_ptr_t r1,
				       tt_node_ptr_t r2);

static int tt_trie_combine_examine_key(void *examine_key_context,
				       tt_atom_t key,
				       tt_node_ptr_t ignored_trie)
{
  struct tt_trie_combine_examine_key_context *c =
    (struct tt_trie_combine_examine_key_context *) examine_key_context;
  tt_arena_t *a = c->a;
  tt_node_ptr_t trie1, trie2; /* Looked up in r1 and r2 */
  tt_node_ptr_t new_trie; /* Combination of trie1 and trie2 */
  tt_node_ptr_t new_result_others; /* Updated dictionary with key---new_trie association */

  trie1 = tt_grab(a, rlookup_dict(a, c->w1, c->dict1, key));
  if (TT_NO_PTR_P(trie1)) return 0;
  trie2 = tt_grab(a, rlookup_dict(a, c->w2, c->dict2, key));
  if (TT_NO_PTR_P(trie2)) {
    tt_drop(a, trie1);
    return 0;
  }
  /* printf("descending into key %d, trie1 %u/%u trie2 %u/%u\n", */
  /*        key, */
  /*        tt_ptr_idx(trie1), */
  /*        tt_ptr_tag(trie1), */
  /*        tt_ptr_idx(trie2), */
  /*        tt_ptr_tag(trie2)); */
  new_trie = tt_trie_combine_g(c->c, trie1, trie2); /* already grabbed */
  tt_drop(a, trie1);
  tt_drop(a, trie2);
  if (TT_NO_PTR_P(new_trie)) return 0;
  new_result_others = tt_grab(a, rupdate_dict(a, c->result_wild, c->result_others, key, new_trie));
  tt_drop(a, new_trie);
  if (TT_NO_PTR_P(new_result_others)) return 0;
  tt_drop(a, c->result_others);
  c->result_others = new_result_others;
  /* printf("after update key %d, result_others %u/%u\n", */
  /*        key, */
  /*        tt_ptr_idx(c->result_others), */
  /*        tt_ptr_tag(c->result_others)); */
  return 1;
}

/* N.B. Returns a tt_grab'd result. */
static tt_node_ptr_t tt_trie_combine_g(struct tt_trie_combine_context *c,
				       tt_node_ptr_t r1,
				       tt_node_ptr_t r2)
{
  tt_arena_t *a = c->a;
  tt_tag_t t1, t2;

  if (TT_EMPTY_P(r1)) {
    return c->left_empty_keep ? tt_grab(a, r2) : TT_EMPTY;
  }
  if (TT_EMPTY_P(r2)) {
    return c->right_empty_keep ? tt_grab(a, r1) : TT_EMPTY;
  }

  t1 = tt_ptr_tag(r1);
  t2 = tt_ptr_tag(r2);

  if (t1 == TT_TAG_BRANCH && t2 == TT_TAG_BRANCH) {
    tt_node_ptr_t result = TT_NO_PTR; /* grab'd */
    struct tt_trie_combine_examine_key_context ekc;
    int ok = 1;

    ekc.c = c;
    ekc.a = a;
    ekc.w1 = TT_BRANCH_WILDCARD(a,r1);
    ekc.w2 = TT_BRANCH_WILDCARD(a,r2);
    ekc.dict1 = TT_BRANCH_OTHERS(a,r1);
    ekc.dict2 = TT_BRANCH_OTHERS(a,r2);
    ekc.result_wild = TT_EMPTY; /* grab'd */
    ekc.result_others = TT_EMPTY_DICT; /* grab'd */

    /* printf("{{{ combining %u/%u with %u/%u\n", */
    /* 	     tt_ptr_idx(r1), */
    /* 	     tt_ptr_tag(r1), */
    /* 	     tt_ptr_idx(r2), */
    /* 	     tt_ptr_tag(r2)); */
    if (!TT_EMPTY_P(ekc.w1) && !TT_EMPTY_P(ekc.w2)) {
      /* Two wildcards - worst case. Must loop over both dictionaries. */
      ekc.result_wild = tt_trie_combine_g(c, ekc.w1, ekc.w2);
      ok = !TT_NO_PTR_P(ekc.result_wild);
      ok = ok && tt_dict_foreach(a, ekc.dict1, &ekc, tt_trie_combine_examine_key);
      ok = ok && tt_dict_foreach(a, ekc.dict2, &ekc, tt_trie_combine_examine_key);
    } else if ((!TT_EMPTY_P(ekc.w1)) ||
	       (TT_EMPTY_P(ekc.w2) &&
		(tt_dict_size(a, ekc.dict1) >= tt_dict_size(a, ekc.dict2)))) {
      /* Either a wildcard on the left, or no wildcard at all but the left is larger */
      if (c->left_base_keep) {
	ekc.result_wild = tt_grab(a, ekc.w1);
	ekc.result_others = tt_grab(a, ekc.dict1);
      }
      ok = ok && tt_dict_foreach(a, ekc.dict2, &ekc, tt_trie_combine_examine_key);
    } else {
      /* Either a wildcard on the right, or no wildcard at all but the right is larger */
      if (c->right_base_keep) {
	ekc.result_wild = tt_grab(a, ekc.w2);
	ekc.result_others = tt_grab(a, ekc.dict2);
      }
      ok = ok && tt_dict_foreach(a, ekc.dict1, &ekc, tt_trie_combine_examine_key);
    }

    if (ok) {
      result = tt_grab(a, rbranch(a, ekc.result_wild, ekc.result_others));
      if (!TT_NO_PTR_P(result)) {
	tt_node_ptr_t collapsed = tt_grab(a, collapse(a, result));
	tt_drop(a, result);
	result = collapsed;
      }
    }
    /* printf("}}} result %u/%u\n", */
    /* 	     tt_ptr_idx(result), */
    /* 	     tt_ptr_tag(result)); */

    tt_drop(a, ekc.result_wild);
    tt_drop(a, ekc.result_others);
    return result;
  }

  if (t1 == TT_TAG_TAIL) {
    if (t2 == TT_TAG_TAIL) {
      tt_node_ptr_t combined =
	RET_IF_NO_PTR(tt_trie_combine_g(c, TT_TAIL_TRIE(a,r1), TT_TAIL_TRIE(a,r2)));
      tt_node_ptr_t result = tt_grab(a, rwildseq(a, combined));
      tt_drop(a, combined);
      return result;
    } else {
      tt_node_ptr_t r1_expanded = tt_grab(a, RET_IF_NO_PTR(expand(a, r1)));
      tt_node_ptr_t result = tt_trie_combine_g(c, r1_expanded, r2);
      tt_drop(a, r1_expanded);
      return result;
    }
  } else if (t2 == TT_TAG_TAIL) {
    tt_node_ptr_t r2_expanded = tt_grab(a, RET_IF_NO_PTR(expand(a, r2)));
    tt_node_ptr_t result = tt_trie_combine_g(c, r1, r2_expanded);
    tt_drop(a, r2_expanded);
    return result;
  }

  if (t1 == TT_TAG_OK || t2 == TT_TAG_OK) {
    return c->f(c->f_context, r1, r2);
  }

  /* There is no legitimate combination of tags that should let us get here. */
  assert(0);
}

/* N.B. Returns a tt_grab'd result. */
tt_node_ptr_t tt_trie_combine(tt_arena_t *a,
			      tt_node_ptr_t r1,
			      tt_node_ptr_t r2,
			      int left_empty_keep,
			      int right_empty_keep,
			      int left_base_keep,
			      int right_base_keep,
			      void *f_context,
			      /* Should return a tt_grab'd result. */
			      tt_node_ptr_t (*f)(void *f_context,
						 tt_node_ptr_t r1,
						 tt_node_ptr_t r2))
{
  struct tt_trie_combine_context context;
  context.a = a;
  context.left_empty_keep = left_empty_keep;
  context.right_empty_keep = right_empty_keep;
  context.left_base_keep = left_base_keep;
  context.right_base_keep = right_base_keep;
  context.f_context = f_context;
  context.f = f;
  /* No need for tt_grab here - tt_trie_combine_g has already done that for us */
  return tt_trie_combine_g(&context, r1, r2);
}

static tt_node_ptr_t f_union_map(void *f_context, tt_node_ptr_t r1, tt_node_ptr_t r2) {
  tt_arena_t *a = (tt_arena_t *) f_context;
  tt_tag_t t1 = tt_ptr_tag(r1);
  tt_tag_t t2 = tt_ptr_tag(r2);
  if (t1 != TT_TAG_OK) {
    /* t2 must be ok. */
    return tt_grab(a, r2);
  } else if (t2 != TT_TAG_OK) {
    return tt_grab(a, r1);
  } else {
    tt_node_ptr_t s = RET_IF_NO_PTR(tt_dictset_union(a, TT_OK_DICT(a,r1), TT_OK_DICT(a,r2)));
    tt_node_ptr_t result = tt_cons_ok(a, s);
    tt_drop(a, s);
    return tt_grab(a, result);
  }
}

tt_node_ptr_t tt_trie_union_map(tt_arena_t *a, tt_node_ptr_t r1, tt_node_ptr_t r2) {
  return tt_trie_combine(a, r1, r2, 1, 1, 1, 1, a, f_union_map);
}

struct f_union_set_context {
  tt_arena_t *a;
  tt_node_ptr_t emptyset;
};

static tt_node_ptr_t f_union_set(void *f_context, tt_node_ptr_t r1, tt_node_ptr_t r2) {
  struct f_union_set_context *c = (struct f_union_set_context *) f_context;
  return tt_grab(c->a, c->emptyset);
}

tt_node_ptr_t tt_trie_union_set(tt_arena_t *a, tt_node_ptr_t r1, tt_node_ptr_t r2) {
  struct f_union_set_context context;
  tt_node_ptr_t result;
  context.a = a;
  context.emptyset = tt_grab(a, RET_IF_NO_PTR(tt_cons_ok(a, TT_EMPTY_DICT)));
  result = tt_trie_combine(a, r1, r2, 1, 1, 1, 1, &context, f_union_set);
  tt_drop(a, context.emptyset);
  return result;
}

static tt_node_ptr_t f_subtract_set(void *f_context, tt_node_ptr_t r1, tt_node_ptr_t r2) {
  return TT_EMPTY;
}

tt_node_ptr_t tt_trie_subtract_set(tt_arena_t *a, tt_node_ptr_t r1, tt_node_ptr_t r2) {
  return tt_trie_combine(a, r1, r2, 0, 1, 1, 0, NULL, f_subtract_set);
}

tt_node_ptr_t tt_trie_step(tt_arena_t *a, tt_node_ptr_t r, tt_atom_t key) {
  if (TT_EMPTY_P(r)) {
    return r;
  }

  switch (tt_ptr_tag(r)) {
    case TT_TAG_OK:
      return TT_EMPTY;

    case TT_TAG_TAIL:
      return (key == TT_EOS) ? TT_TAIL_TRIE(a,r) : r;

    case TT_TAG_BRANCH:
      return rlookup(a, r, key);

    default:
      assert(0);
  }
}

struct tt_trie_relabel_visit_edge_context {
  tt_arena_t *a;
  void *f_context;
  tt_node_ptr_t (*f)(void *f_context, tt_node_ptr_t oldlabel);
  tt_node_ptr_t wild;
  tt_node_ptr_t others;
};

static int tt_trie_relabel_visit_edge(void *context, tt_atom_t key, tt_node_ptr_t trie) {
  struct tt_trie_relabel_visit_edge_context *c =
    (struct tt_trie_relabel_visit_edge_context *) context;
  tt_arena_t *a = c->a;
  tt_node_ptr_t new_trie = tt_grab(a, tt_trie_relabel(a, trie, c->f_context, c->f));
  tt_node_ptr_t new_others;
  if (TT_NO_PTR_P(new_trie)) return 0;
  new_others = tt_grab(a, rupdate_dict(a, c->wild, c->others, key, new_trie));
  tt_drop(a, new_trie);
  if (TT_NO_PTR_P(new_others)) return 0;
  tt_drop(a, c->others);
  c->others = new_others;
  return 1;
}

tt_node_ptr_t tt_trie_relabel(tt_arena_t *a,
			      tt_node_ptr_t r,
			      void *f_context,
			      tt_node_ptr_t (*f)(void *f_context,
						 tt_node_ptr_t oldlabel))
{
  if (TT_EMPTY_P(r)) {
    return r;
  }

  switch (tt_ptr_tag(r)) {
    case TT_TAG_OK:
      return tt_cons_ok(a, RET_IF_NO_PTR(f(f_context, TT_OK_DICT(a, r))));

    case TT_TAG_TAIL:
      return tt_cons_tail(a, RET_IF_NO_PTR(tt_trie_relabel(a, TT_TAIL_TRIE(a, r), f_context, f)));

    case TT_TAG_BRANCH: {
      struct tt_trie_relabel_visit_edge_context context;
      context.a = a;
      context.f_context = f_context;
      context.f = f;
      context.wild =
	tt_grab(a, RET_IF_NO_PTR(tt_trie_relabel(a, TT_BRANCH_WILDCARD(a, r), f_context, f)));
      context.others = TT_EMPTY_DICT; /* grab'd */
      tt_node_ptr_t result = TT_NO_PTR;
      if (tt_dict_foreach(a, TT_BRANCH_OTHERS(a, r), &context, tt_trie_relabel_visit_edge)) {
	result = rbranch(a, context.wild, context.others);
      }
      tt_drop(a, context.wild);
      tt_drop(a, context.others);
      return result;
    }

    default:
      assert(0);
  }
}

static tt_node_ptr_t relabel_to_const(void *context, tt_node_ptr_t oldlabel) {
  return *((tt_node_ptr_t *) context);
}

tt_node_ptr_t tt_trie_relabel_const(tt_arena_t *a, tt_node_ptr_t r, tt_node_ptr_t newlabel) {
  return tt_trie_relabel(a, r, &newlabel, relabel_to_const);
}

tt_node_ptr_t tt_begin_path(tt_arena_t *a, tt_node_ptr_t ok_dict) {
  return tt_cons_ok(a, ok_dict);
}

tt_node_ptr_t tt_prepend_path(tt_arena_t *a, tt_atom_t tok, tt_node_ptr_t tail) {
  if (tok == TT_WILD) {
    return rwild(a, tail);
  } else {
    return rseq(a, tok, tail);
  }
}

void print_indent(int spaces) {
  while (spaces--) {
    putchar(' ');
  }
}

static size_t gross_approximate_utf8_strlen(char const *c) {
  size_t count = 0;
  while (*c) {
    unsigned char b = *c;
    if (b < 0x80 || b >= 0xc0) {
      count++;
    }
    c++;
  }
  return count;
}

static int tt_dump_routingtable_pkey(void *context, tt_atom_t key, tt_node_ptr_t ignored_trie) {
  int *need_space = (int *) context;
  if (*need_space) {
    putchar(' ');
  } else {
    *need_space = 1;
  }
  printf("%d", key);
  return 1;
}

/* Forward declaration (mutual recursion) */
static void tt_dump_routingtable_walk(tt_arena_t *a, tt_node_ptr_t r, int indent);

struct tt_dump_routingtable_pedge_context {
  tt_arena_t *a;
  int indent;
  int need_sep;
};

static int tt_dump_routingtable_pedge(void *context, tt_atom_t key, tt_node_ptr_t node) {
  struct tt_dump_routingtable_pedge_context *c =
    (struct tt_dump_routingtable_pedge_context *) context;
  char keystr[256]; /* not very tight */
  if (c->need_sep) {
    putchar('\n');
    print_indent(c->indent);
  } else {
    c->need_sep = 1;
  }
  keystr[sizeof(keystr) - 1] = '\0';
  switch (key) {
    case TT_WILD: snprintf(keystr, sizeof(keystr) - 1, " ★"); break;
    case TT_BOS: snprintf(keystr, sizeof(keystr) - 1, " <"); break;
    case TT_EOS: snprintf(keystr, sizeof(keystr) - 1, " >"); break;
    case TT_BOC: snprintf(keystr, sizeof(keystr) - 1, " {"); break;
    case TT_EOC: snprintf(keystr, sizeof(keystr) - 1, " }"); break;
    default:
      snprintf(keystr, sizeof(keystr) - 1, " %d", key);
  }
  fputs(keystr, stdout);
  tt_dump_routingtable_walk(c->a, node, c->indent + gross_approximate_utf8_strlen(keystr));
  return 1;
}

static void tt_dump_routingtable_walk(tt_arena_t *a, tt_node_ptr_t r, int indent) {
  switch (tt_ptr_tag(r)) {
    case TT_TAG_TAIL:
      printf(" ...>");
      tt_dump_routingtable_walk(a, TT_TAIL_TRIE(a, r), indent + 5);
      break;
    case TT_TAG_OK: {
      int need_space = 0;
      fputs(" {", stdout);
      tt_dict_foreach(a, TT_OK_DICT(a, r), &need_space, tt_dump_routingtable_pkey);
      putchar('}');
      break;
    }
    case TT_TAG_BRANCH: {
      struct tt_dump_routingtable_pedge_context context;
      context.a = a;
      context.indent = indent;
      context.need_sep = 0;
      if (!TT_EMPTY_P(TT_BRANCH_WILDCARD(a, r))) {
	tt_dump_routingtable_pedge(&context, TT_WILD, TT_BRANCH_WILDCARD(a, r));
      }
      tt_dict_foreach(a, TT_BRANCH_OTHERS(a, r), &context, tt_dump_routingtable_pedge);
      if (!context.need_sep) {
	printf(" ::: no edges!");
      }
      break;
    }
    case TT_TAG_SPECIAL:
      if (TT_EMPTY_P(r)) {
	printf(" ::: nothing");
	break;
      }
      /* fall through */
    default:
      printf("?!?!?! %x", (unsigned int) r);
      break;
  }
}

void tt_dump_routingtable(tt_arena_t *a, tt_node_ptr_t r, int initial_indent) {
  tt_dump_routingtable_walk(a, r, initial_indent);
  putchar('\n');
}