/src/freeradius-server/src/lib/util/trie.c

Source
/*
 *   This library is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU Lesser General Public
 *   License as published by the Free Software Foundation; either
 *   version 2.1 of the License, or (at your option) any later version.
 *
 *   This library is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *   Lesser General Public License for more details.
 *
 *   You should have received a copy of the GNU Lesser General Public
 *   License along with this library; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/** Path-compressed prefix tries
 *
 * @file src/lib/util/trie.c
 *
 * @copyright 2017 Alan DeKok (aland@freeradius.org)
 */
RCSID("$Id: 0c2e975b6d8169f07c309a70593953b7f3bcd440 $")

#include <freeradius-devel/util/dict.h>
#include <freeradius-devel/util/skip.h>
#include <freeradius-devel/util/syserror.h>
#include <freeradius-devel/util/trie.h>


/*
 *  This file implements path-compressed, level-compressed
 *  patricia tries.  The original research paper is:
 *
 *  https://www.nada.kth.se/~snilsson/publications/Dynamic-trie-compression-implementation/
 *
 *  The functionality has been extended to include intermediate
 *  nodes which consume 0 bits, but which hold user context data.
 *  These intermediate nodes allow for "longest prefix" matching.
 *  For example, in networking, you can have a routing table entry
 *  with 0/0 leading to one destination, and 10/8 leading to a
 *  different one.  Looking up an address in the 10/8 network will
 *  return the 10/8 destination.  Looking up any other address
 *  will return the default destination.
 *
 *  In addition, we desire the ability to add and delete nodes
 *  dynamically.  In the example given above, this means that
 *  after deleting 10/8, the trie should contain only the 0/0
 *  network and associated destination.
 *
 *  As of yet, it does not do level compression.  This can be
 *  added without (hopefully) too much work.  That would require
 *  an additional step to "normalize" the trie.
 *
 *  This code could be extended to do packet matching, through the
 *  inclusion of "don't care" paths.  e.g. parsing an IP header,
 *  where the src/dst IP addresses are 32-bit "don't care" fields.
 *
 *  It could also be extended via "count" paths, where the path
 *  holds a count that is used in another part of the trie.  For
 *  example, in RADIUS.  The attribute encoding is one byte
 *  attribute, one byte length, followed by "length - 2" bytes of
 *  data.  At that point though, you might as well just use Ragel.
 */

/** Enable path compression (or not)
 *
 *  With path compression, long sequences of bits are stored as a
 *  path, e.g. "abcdef".  Without path compression, we would have to
 *  create a large number of intermediate 2^N-way nodes, all of which
 *  would have only one edge.
 */
#if !defined(NO_PATH_COMPRESSION) && !defined(WITH_PATH_COMPRESSION)
#define WITH_PATH_COMPRESSION
#endif

//#define WITH_NODE_COMPRESSION

#ifdef WITH_NODE_COMPRESSION
#ifndef WITH_PATH_COMPRESSION
#define WITH_PATH_COMPRESSION
#endif

#ifndef MAX_COMP_BITS
#define MAX_COMP_BITS (8)
#endif

#ifndef MAX_COMP_EDGES
#define MAX_COMP_EDGES (4)
#endif

#endif  /* WITH_NODE_COMPRESSION */

#define MAX_KEY_BYTES (256)
#define MAX_KEY_BITS (MAX_KEY_BYTES * 8)

#ifndef MAX_NODE_BITS
#define MAX_NODE_BITS (4)
#endif

/**  Internal sanity checks for debugging.
 *
 *  Tries are complex.  So we have verification routines for every
 *  type of node.  These routines are called from within the trie
 *  manipulation functions.  If the trie manipulation has a bug, the
 *  verification routines are likely to catch some of the more
 *  egregious issues.
 */
DIAG_OFF(unused-macros)
#ifdef TESTING
#define WITH_TRIE_VERIFY (1)
#  define MPRINT(...) fprintf(stderr, ## __VA_ARGS__)

   /* define this to be MPRINT for additional debugging */
#  define MPRINT2(...)
#  define MPRINT3(...)
static void trie_sprint(fr_trie_t *trie, uint8_t const *key, int start_bit, int lineno);
#else
#  define MPRINT(...)
#  define MPRINT2(...)
#  define MPRINT3(...)
#define trie_sprint(_trie, _key, _start_bit, _lineno)
#endif

#ifdef WITH_TRIE_VERIFY
static int trie_verify(fr_trie_t *trie);
//#define VERIFY(_x) fr_cond_assert(trie_verify((fr_trie_t *) _x) == 0)
#define VERIFY(_x) if (trie_verify((fr_trie_t *) _x) < 0) do { fprintf(stderr, "FAIL VERIFY at %d - %s\n", __LINE__, fr_strerror()); fr_cond_assert(0); } while (0)
#else
#define VERIFY(_x)
#endif

/*
 *  Macros to swap one for the other.
 */
#define BITSOF(_x)  ((_x) * 8)
#define BYTEOF(_x)  ((_x) >> 3)
#define BYTES(_x) (((_x) + 0x07) >> 3)
DIAG_ON(unused-macros)


// @todo - do level compression
// stop merging nodes if a key ends at the top of the level
// otherwise merge so we have at least 2^4 way fan-out, but no more than 2^8
// that should be a decent trade-off between memory and speed

// @todo - generalized function to normalize the trie.


static uint8_t start_bit_mask[8] = {
  0xff, 0x7f, 0x3f, 0x1f,
  0x0f, 0x07, 0x03, 0x01
};

static uint8_t used_bit_mask[8] = {
  0x80, 0xc0, 0xe0, 0xf0,
  0xf8, 0xfc, 0xfe, 0xff,
};

#if 0
/*
 *  For testing and debugging.
 */
static char const *spaces = "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ";
#endif


#if defined(WITH_PATH_COMPRESSION) || defined(TESTING)
/*
 *  Table of how many leading bits there are in KEY1^KEY2.
 */
static uint8_t xor2lcp[256] = {
  8, 7, 6, 6,
  5, 5, 5, 5,   /* 4x 5 */
  4, 4, 4, 4,   /* 8x 4 */
  4, 4, 4, 4,
  3, 3, 3, 3,   /* 16x 3 */
  3, 3, 3, 3,
  3, 3, 3, 3,
  3, 3, 3, 3,
  2, 2, 2, 2,   /* 32x 2 */
  2, 2, 2, 2,
  2, 2, 2, 2,
  2, 2, 2, 2,
  2, 2, 2, 2,
  2, 2, 2, 2,
  2, 2, 2, 2,
  2, 2, 2, 2,
  1, 1, 1, 1,   /* 64x 1 */
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  1, 1, 1, 1,
  0, 0, 0, 0,   /* 128x 0 */
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
  0, 0, 0, 0,
};


/** Get the longest prefix of the two keys.
 *
 */
static int fr_trie_key_lcp(uint8_t const *key1, int keylen1, uint8_t const *key2, int keylen2, int start_bit)
{
  int lcp, end_bit;

  if (!keylen1 || !keylen2) return 0;
  fr_cond_assert((start_bit & 0x07) == start_bit);

  end_bit = keylen1;
  if (end_bit > keylen2) end_bit = keylen2;
  end_bit += start_bit;

  MPRINT2("%.*sLCP %02x%02x %02x%02x start %d length %d, %d\n",
    start_bit, spaces, key1[0], key1[1], key2[0], key2[1], start_bit, keylen1, keylen2);

  lcp = 0;

  while (end_bit > 0) {
    int num_bits;
    uint8_t cmp1, cmp2, xor;

    MPRINT2("END %d\n", end_bit);

    /*
     *  Default to grabbing the whole byte.
     */
    cmp1 = key1[0];
    cmp2 = key2[0];
    num_bits = 8;

    /*
     *  The LCP ends in this byte.  Mask off the
     *  trailing bits so that they don't affect the
     *  result.
     */
    if (end_bit < 8) {
      cmp1 &= used_bit_mask[end_bit - 1];
      cmp2 &= used_bit_mask[end_bit - 1];
      num_bits = end_bit;
    }

    /*
     *  The key doesn't start on the leading bit.
     *  Shift the data left until it does start there.
     */
    if ((start_bit & 0x07) != 0) {
      cmp1 <<= start_bit;
      cmp2 <<= start_bit;
      num_bits -= start_bit;
      end_bit -= start_bit;

      /*
       *  For subsequent bytes we start on a
       *  byte boundary.
       */
      start_bit = 0;
    }

    xor = cmp1 ^ cmp2;

    /*
     *  A table lookup is faster than looping through
     *  the bits.  If the LCP is smaller than the
     *  number of bits we're looking up, we can stop.
     *
     *  On the other hand, if it returns the same or
     *  too many bits, just do another round through
     *  the loop, so that we can update the pointers
     *  and check the exit conditions.
     */
    if (xor2lcp[xor] < num_bits) {
      MPRINT2("RETURN %d + %d\n", lcp, xor2lcp[xor]);
      return lcp + xor2lcp[xor];
    }

    /*
     *  The LCP may be longer than num_bits if we're
     *  checking the first byte, which has only
     *  "start_bit" things we care about.  Ignore that
     *  case, and just keep going.
     */

    lcp += num_bits;
    end_bit -= num_bits;
    key1++;
    key2++;
  }

  return lcp;
}
#endif

//#define HEX_DUMP

#ifdef HEX_DUMP
static void hex_dump(FILE *fp, char const *msg, uint8_t const *key, int start_bit, int end_bit)
{
  int i;

  fprintf(fp, "%s\ts=%zd e=%zd\t\t", msg, start_bit, end_bit);

  for (i = 0; i < BYTES(end_bit); i++) {
    fprintf(fp, "%02x ", key[i]);
  }
  fprintf(fp, "\n");
}
#endif

/** Return a chunk of a key (in the low bits) for use in 2^N node de-indexing
 *
 */
static CC_HINT(nonnull) uint16_t get_chunk(uint8_t const *key, uint32_t start_bit, uint32_t num_bits)
{
  uint16_t chunk;
  int end_bit;

  fr_cond_assert(num_bits > 0);
  fr_cond_assert(num_bits <= 16);

  /*
   *  Normalize it so that the caller doesn't have to.
   */
  if (start_bit > 7) {
    key += BYTEOF(start_bit);
    start_bit &= 0x07;
  }

  /*
   *  Special-case 1-bit lookups.
   */
  if (num_bits == 1) {
    chunk = key[0] >> (7 - start_bit);
    chunk &= 0x01;
    return chunk;
  }

  /*
   *  Catch some simple use-cases.
   */
  if (start_bit == 0) {
    if (num_bits < 7) return key[0] >> (8 - num_bits);
    if (num_bits == 8) return key[0];

    chunk = (key[0] << 8) | key[1];
    if (num_bits < 16) chunk >>= (16 - num_bits);
    fr_cond_assert(chunk < (1 << num_bits));
    return chunk;
  }

  /*
   *  Load the first byte and mask off the bits we don't
   *  want.
   */
  chunk = key[0] & start_bit_mask[start_bit & 0x07];

  fr_cond_assert(BYTEOF(start_bit + num_bits - 1) <= 1);

  if (BYTEOF(start_bit + num_bits - 1) != 0) {
    chunk <<= 8;
    chunk |= key[1];
  }

  /*
   *  The bits we want are now all in the higher bits
   *  of "chunk".  But we only want some of them.
   *
   *  Shift the chunk so that the bits we want are now in
   *  the low bits.
   */
  end_bit = (start_bit + num_bits) & 0x07;
  if (end_bit != 0) chunk >>= 8 - end_bit;

  fr_cond_assert(chunk < (1 << num_bits));

  return chunk;
}


static void write_chunk(uint8_t *out, int start_bit, int num_bits, uint16_t chunk) CC_HINT(nonnull);

/** Write a chunk to an output buffer
 *
 */
static void write_chunk(uint8_t *out, int start_bit, int num_bits, uint16_t chunk)
{
  fr_cond_assert(chunk < (1 << num_bits));

  /*
   *  Normalize it so that the caller doesn't have to.
   */
  if (start_bit > 7) {
    out += BYTEOF(start_bit);
    start_bit &= 0x07;
  }

  /*
   *  Special-case 1-bit writes.
   */
  if (num_bits == 1) {
    out[0] &= ~(1 << (7 - start_bit));
    out[0] |= chunk << (7 - start_bit);
    return;
  }

  /*
   *  Ensure that we don't write to more than 2 octets at
   *  the same time.
   */
  fr_cond_assert((start_bit + num_bits) <= 16);

  /*
   *  Shift the chunk to the high bits, but leave room for
   *  start_bit
   */
  if ((start_bit + num_bits) < 16) chunk <<= (16 - (start_bit + num_bits));

  /*
   *  Mask off the first bits that are already in the
   *  output.  Then OR in the relevant bits of "chunk".
   */
  out[0] &= (used_bit_mask[start_bit] << 1);
  out[0] |= chunk >> 8;

  if ((start_bit + num_bits) > 8) {
    out[1] = chunk & 0xff;
  }
}

typedef enum fr_trie_type_t {
  FR_TRIE_INVALID = 0,
  FR_TRIE_USER,
#ifdef WITH_PATH_COMPRESSION
  FR_TRIE_PATH,
#endif
#ifdef WITH_NODE_COMPRESSION
  FR_TRIE_COMP,   /* 4-way, N bits deep */
#endif
  FR_TRIE_NODE,
} fr_trie_type_t;

#define FR_TRIE_MAX (FR_TRIE_NODE + 1)

#ifdef TESTING
static int trie_number = 0;

#define TRIE_HEADER uint8_t type; uint8_t bits; int number
#define TRIE_TYPE_CHECK(_x, _r) do { if ((trie->type == FR_TRIE_INVALID) || \
           (trie->type >= FR_TRIE_MAX) || \
           !trie_ ## _x ##_table [trie->type]) { \
            fr_strerror_printf("unknown trie type %d", trie->type); \
            return _r; \
             } } while (0)

#else
#define TRIE_HEADER uint8_t type; uint8_t bits
#define TRIE_TYPE_CHECK(_x, _r)
#endif

struct fr_trie_s {
  TRIE_HEADER;

  fr_trie_t *trie;  /* for USER and PATH nodes*/
};

typedef struct {
  TRIE_HEADER;

  int   used;
  fr_trie_t *trie[];
} fr_trie_node_t;

typedef struct {
  TRIE_HEADER;

  fr_trie_t *trie;
  void      *data;
} fr_trie_user_t;

#ifdef WITH_PATH_COMPRESSION
typedef struct {
  TRIE_HEADER;

  fr_trie_t *trie;

  uint16_t  chunk;
  uint8_t   key[2];
} fr_trie_path_t;
#endif

#ifdef WITH_NODE_COMPRESSION
typedef struct {
  TRIE_HEADER;

  int   used;   //!< number of used entries
  uint8_t   index[MAX_COMP_EDGES];
  fr_trie_t *trie[MAX_COMP_EDGES];
} fr_trie_comp_t;
#endif


/* ALLOC FUNCTIONS */

static fr_trie_node_t *trie_node_alloc(TALLOC_CTX *ctx, int bits)
{
  fr_trie_node_t *node;
  int size;

  if ((bits <= 0) || (bits > 8)) {
    fr_strerror_printf("Invalid bit size %d passed to node alloc", bits);
    return NULL;
  }

  size = 1 << bits;

  node = (fr_trie_node_t *) talloc_zero_array(ctx, uint8_t, sizeof(fr_trie_node_t) + sizeof(node->trie[0]) * size);
  if (!node) {
    fr_strerror_const("failed allocating node trie");
    return NULL;
  }

  talloc_set_name_const(node, "fr_trie_node_t");
  node->type = FR_TRIE_NODE;
  node->bits = bits;

#ifdef TESTING
  node->number = trie_number++;
#endif
  return node;
}

/** Free a fr_trie_t
 *
 *  We can't use talloc_free(), because we can't talloc_parent the
 *  nodes from each other, as talloc_steal() is O(N).  So, we just
 *  recurse manually.
 */
static void trie_free(fr_trie_t *trie)
{
  if (!trie) return;

  if (trie->type == FR_TRIE_USER) {
    fr_trie_user_t *user = (fr_trie_user_t *) trie;

    trie_free(user->trie);
    talloc_free(user);
    return;
  }

  if (trie->type == FR_TRIE_NODE) {
    fr_trie_node_t *node = (fr_trie_node_t *) trie;
    int i;

    for (i = 0; i < (1 << node->bits); i++) {
      if (!node->trie[i]) continue; /* save a function call in the common case */

      trie_free(node->trie[i]);
    }

    talloc_free(node);
    return;
  }

#ifdef WITH_PATH_COMPRESSION
  if (trie->type == FR_TRIE_PATH) {
    fr_trie_path_t *path = (fr_trie_path_t *) trie;

    trie_free(path->trie);
    talloc_free(path);
    return;
  }
#endif

#ifdef WITH_NODE_COMPRESSION
  if (trie->type == FR_TRIE_COMP) {
    fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
    int i;

    for (i = 0; i < comp->used; i++) {
      trie_free(comp->trie[i]);
    }

    talloc_free(comp);
    return;
  }
#endif
}

static CC_HINT(nonnull(2)) fr_trie_user_t *fr_trie_user_alloc(TALLOC_CTX *ctx, void const *data)
{
  fr_trie_user_t *user;

  user = talloc_zero(ctx, fr_trie_user_t);
  if (!user) {
    fr_strerror_const("failed allocating user trie");
    return NULL;
  }

  user->type = FR_TRIE_USER;
  user->data = UNCONST(void *, data);

#ifdef TESTING
  user->number = trie_number++;
#endif

  return user;
}

#ifdef WITH_PATH_COMPRESSION
static CC_HINT(nonnull(2)) fr_trie_path_t *fr_trie_path_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit)
{
  fr_trie_path_t *path;

  if (end_bit <= start_bit) {
    fr_strerror_printf("path asked for start >= end, %d >= %d", start_bit, end_bit);
    return NULL;
  }

  /*
   *  Normalize it so that the caller doesn't have to.
   */
  if (start_bit > 7) {
    key += (start_bit >> 3);
    end_bit -= 8 * (start_bit >> 3);
    start_bit -= 8 * (start_bit >> 3);
  }

  if ((end_bit - start_bit) > 16) {
    fr_strerror_printf("path asked for too many bits (%d)", end_bit - start_bit);
    return NULL;
  }

  /*
   *  The "end_bit" is the bit we're not using, so it's
   *  allowed to point past the end of path->key.
   */
  if ((BYTEOF(start_bit) - BYTEOF(end_bit - 1)) > 1) {
    fr_strerror_printf("path asked for too many bits / bytes (%d)", end_bit - start_bit);
    return NULL;
  }

  path = talloc_zero(ctx, fr_trie_path_t);
  if (!path) {
    fr_strerror_const("failed allocating path trie");
    return NULL;
  }

  path->type = FR_TRIE_PATH;
  path->bits = end_bit - start_bit;
  path->chunk = get_chunk(key, start_bit, path->bits);

  /*
   *  Write the chunk back to the key.
   */
  write_chunk(&path->key[0], start_bit, path->bits, path->chunk);

#if 0
  fprintf(stderr, "PATH ALLOC key %02x%02x start %d end %d bits %d == chunk %04x key %02x%02x\n",
    key[0], key[1],
    start_bit, end_bit, path->bits,
    path->chunk, path->key[0], path->key[1]);
#endif

#ifdef TESTING
  path->number = trie_number++;
#endif

  return path;
}
#endif  /* WITH_PATH_COMPRESSION */

#ifdef WITH_NODE_COMPRESSION
static fr_trie_comp_t *fr_trie_comp_alloc(TALLOC_CTX *ctx, int bits)
{
  fr_trie_comp_t *comp;

  /*
   *  For 1 && 2 bits, just allocate fr_trie_node_t.
   */
  if ((bits <= 2) || (bits > MAX_COMP_BITS)) {
    fr_strerror_printf("Invalid bit size %d passed to comp alloc", bits);
    return NULL;
  }

  comp = talloc_zero(ctx, fr_trie_comp_t);
  if (!comp) {
    fr_strerror_const("failed allocating comp trie");
    return NULL;
  }

  comp->type = FR_TRIE_COMP;
  comp->bits = bits;
  comp->used = 0;

#ifdef TESTING
  comp->number = trie_number++;
#endif
  return comp;
}
#endif  /* WITH_NODE_COMPRESSION */

typedef struct {
  uint8_t   buffer[16]; /* for get_key callbacks */
  fr_trie_key_t get_key;
  fr_free_t free_data;
} fr_trie_ctx_t;

/** Allocate a trie
 *
 * @param ctx   The talloc ctx.
 * @param get_key The "get key from object" function.
 * @param free_data Callback to free data.
 * @return
 *  - NULL on error
 *  - fr_trie_node_t on success
 */
fr_trie_t *fr_trie_alloc(TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
{
  fr_trie_user_t *user;
  fr_trie_ctx_t *uctx;

  /*
   *  The trie itself is just a user node with user data
   *  that is the get_key function.
   */
  user = (fr_trie_user_t *) fr_trie_user_alloc(ctx, "");
  if (!user) return NULL;

  /*
   *  Only the top-level node here can have 'user->data == NULL'
   */
  user->data = uctx = talloc_zero(user, fr_trie_ctx_t);
  if (!user->data) {
    talloc_free(user);
    return NULL;
  }

  uctx->get_key = get_key;
  uctx->free_data = free_data;

  return (fr_trie_t *) user;
}

/* SPLIT FUNCTIONS */

/** Split a node at bits
 *
 */
static CC_HINT(nonnull(2)) fr_trie_node_t *trie_node_split(TALLOC_CTX *ctx, fr_trie_node_t *node, int bits)
{
  fr_trie_node_t *split;
  int i, remaining_bits;

  /*
   *  Can't split zero bits, more bits than the node has, or
   *  a node which has 1 bit.
   */
  if ((bits == 0) || (bits >= node->bits) || (node->bits == 1)) {
    fr_strerror_printf("invalid value for node split (%d / %d)", bits, node->bits);
    return NULL;
  }

  split = trie_node_alloc(ctx, bits);
  if (!split) return NULL;

  remaining_bits = node->bits - bits;

  /*
   *  Allocate the children.  For now, just brute-force all
   *  of the children.  We take a later pass at optimizing this.
   */
  for (i = 0; i < (1 << bits); i++) {
    int j;
    fr_trie_node_t *child;

    child = trie_node_alloc(ctx, remaining_bits);
    if (!child) {
      trie_free((fr_trie_t *) split);
      return NULL;
    }

    for (j = 0; j < (1 << remaining_bits); j++) {
      if (!node->trie[(i << remaining_bits) + j]) continue;

      child->trie[j] = node->trie[(i << remaining_bits) + j];
      node->trie[(i << remaining_bits) + j] = NULL; /* so we don't free it when freeing 'node' */
      child->used++;
    }

    if (!child->used) {
      talloc_free(child); /* no children, so no need to recurse */
      continue;
    }

    split->trie[i] = (fr_trie_t *) child;
    split->used++;
  }

  /*
   *  Note that we do NOT free "node".  The caller still
   *  needs it for some activities.
   */
  return split;
}

#ifdef WITH_PATH_COMPRESSION
static CC_HINT(nonnull(2)) fr_trie_path_t *trie_path_split(TALLOC_CTX *ctx, fr_trie_path_t *path, int start_bit, int lcp)
{
  fr_trie_path_t *split, *child;
#ifdef TESTING
  uint8_t key[2] = { 0, 0 };
#endif

  if ((lcp <= 0) || (lcp > path->bits) || (start_bit < 0)) {
    fr_strerror_printf("invalid parameter %d %d to path split", lcp, start_bit);
    return NULL;
  }

  MPRINT3("%.*sSPLIT start %d\n", start_bit, spaces, start_bit);
  start_bit &= 0x07;

  split = fr_trie_path_alloc(ctx, &path->key[0], start_bit, start_bit + lcp);
  if (!split) return NULL;

  child = fr_trie_path_alloc(ctx, &path->key[0], start_bit + lcp, start_bit + path->bits);
  if (!child) {
    talloc_free(split);
    return NULL;
  }

  split->trie = (fr_trie_t *) child;
  child->trie = (fr_trie_t *) path->trie;

  /*
   *  Don't free "path" until we've successfully inserted
   *  the new key.
   */

#ifdef TESTING
  /*
   *  Check that the two chunks add up to the parent chunk.
   */
  fr_cond_assert(path->chunk == ((split->chunk << (path->bits - lcp)) | child->chunk));

  /*
   *  Check that the two keys match the parent key.
   */

  write_chunk(&key[0], start_bit, split->bits, split->chunk);
  write_chunk(&key[0], start_bit + split->bits, child->bits, child->chunk);

  fr_cond_assert(key[0] == path->key[0]);
  fr_cond_assert(key[1] == path->key[1]);

  MPRINT3("%.*ssplit %02x%02x start %d split %d -> %02x%02x %02x%02x\n",
    start_bit, spaces,
    path->key[0], path->key[1],
    start_bit, split->bits,
    split->key[0], split->key[1],
    child->key[0], child->key[1]);
#endif

  return split;
}

static CC_HINT(nonnull(2)) fr_trie_t *trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  fr_trie_path_t *path;
  int next_bit;

  if (start_bit == end_bit) return (fr_trie_t *) fr_trie_user_alloc(ctx, data);

  if (start_bit > end_bit) {
    fr_strerror_printf("key_alloc asked for start >= end, %d >= %d", start_bit, end_bit);
    return NULL;
  }

  /*
   *  Grab some more bits.  Try to grab 16 bits at a time.
   */
  next_bit = start_bit + 16 - (start_bit & 0x07);

  if (next_bit >= end_bit) {
    path = fr_trie_path_alloc(ctx, key, start_bit, end_bit);
    if (!path) return NULL;

    path->trie = (fr_trie_t *) fr_trie_user_alloc(ctx, data);
    return (fr_trie_t *) path;
  }


  path = fr_trie_path_alloc(ctx,  key, start_bit, next_bit);
  if (!path) return NULL;

  path->trie = (fr_trie_t *) trie_key_alloc(ctx, key, next_bit, end_bit, data);
  if (!path->trie) {
    talloc_free(path); /* no children */
    return NULL;
  }

  return (fr_trie_t *) path;
}
#else  /* WITH_PATH_COMPRESSION */
static CC_HINT(nonnull(2)) fr_trie_t *trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  fr_trie_node_t *node;
  uint16_t chunk;
  int bits = MAX_NODE_BITS;

  if (start_bit == end_bit) {
    return (fr_trie_t *) fr_trie_user_alloc(ctx, data);
  }

  bits = end_bit - start_bit;
  if (bits > MAX_NODE_BITS) bits = MAX_NODE_BITS;

  /*
   *  We only want one edge here.
   */
  node = trie_node_alloc(ctx, bits);
  if (!node) return NULL;

  chunk = get_chunk(key, start_bit, node->bits);
  node->trie[chunk] = trie_key_alloc(ctx, key, start_bit + node->bits, end_bit, data);
  if (!node->trie[chunk]) {
    talloc_free(node); /* no children */
    return NULL;
  }
  node->used++;

  return (fr_trie_t *) node;
}
#endif


#if 0
/** Split a compressed at bits
 *
 */
#ifdef WITH_NODE_COMPRESSION
static fr_trie_t *trie_comp_split(TALLOC_CTX *ctx, fr_trie_comp_t *comp, int start_bit, int bits)
{
  int i;
  fr_trie_comp_t *split;

  /*
   *  Can't split zero bits, more bits than the node has, or
   *  a node which has 1 bit.
   */
  if ((bits == 0) || (bits >= comp->bits)) {
    fr_strerror_printf("invalid value for comp split (%d / %d)", bits, comp->bits);
    return NULL;
  }

  split = fr_trie_comp_alloc(ctx, bits);
  if (!split) return NULL;

  if (start_bit > 7) start_bit &= 0x07;

  // walk over the edges, seeing how many edges have the same before bits
  //
  // if all have the same bits, then split by creating a path
  // node, and then a child split node.

  /*
   *  Walk over each edge, inserting the first chunk into
   *  the new node, and the split node...
   */
  for (i = 0; i < comp->used; i++) {
    int j, where;
    uint16_t before, after;
    uint8_t key[2];
    fr_trie_path_t *path;

    before = i >> (comp->bits - bits);
    after = i & ((1 << bits) - 1);

    write_chunk(&key[0], start_bit, comp->bits, i);

    // see if "before" was already used in the newly created node.

    where = 0;

    for (j = 0; j < split->used; j++) {
      if (before == split->index[j]) {
        where = j;
        break;
      }
    }

    if (split->index[where]) {
      // the children MUST be different
      // create another compressed node as a child, and go from there.

    } else {
      split->index[split->used] = before;
      path = fr_trie_path_alloc(ctx, &key[0], start_bit, start_bit + bits);
      if (!path) goto fail;

      split->trie[split->used++] = (fr_trie_t *) path;
      path->trie = comp->trie[i];
    }
  }

  return (fr_trie_t *) split;

fail:
  for (i = 0; i < split->used; i++) {
    talloc_free(split->trie[i]);
  }
  talloc_free(split);
  return NULL;
}
#endif  /* WITH_NODE_COMPRESSION */
#endif

/* ADD EDGES */

#ifdef WITH_PATH_COMPRESSION
/** Add an edge to a node.
 *
 *  This function is so that we can abstract 2^N-way nodes, or
 *  compressed edge nodes.
 */
static int trie_add_edge(fr_trie_t *trie, uint16_t chunk, fr_trie_t *child)
{
  fr_trie_node_t *node;

#ifdef WITH_NODE_COMPRESSION
  if (trie->type == FR_TRIE_COMP) {
    fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
    int i, edge;

    if (chunk >= (1 << comp->bits)) return -1;

    if (comp->used >= MAX_COMP_EDGES) return -1;

    edge = comp->used;
    for (i = 0; i < comp->used; i++) {
      if (comp->index[i] < chunk) continue;

      if (comp->index[edge] == chunk) return -1;

      edge = i;
      break;
    }

    if (edge == MAX_COMP_EDGES) return -1;

    /*
     *  Move the nodes up so that we have room for the
     *  new edge.
     */
    for (i = edge; i < comp->used; i++) {
      comp->index[i + 1] = comp->index[i];
      comp->trie[i + 1] = comp->trie[i];
    }

    comp->index[edge] = chunk;
    comp->trie[edge] = child;

    comp->used++;
    VERIFY(comp);
    return 0;
  }
#endif

  if (trie->type != FR_TRIE_NODE) return -1;

  node = (fr_trie_node_t *) trie;

  if (chunk >= (1 << node->bits)) return -1;

  if (node->trie[chunk] != NULL) return -1;

  node->used++;
  node->trie[chunk] = child;

  return 0;
}
#endif

/* MATCH FUNCTIONS */

typedef void *(*trie_key_match_t)(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact);

static void *trie_key_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact);

static void *trie_user_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
{
  fr_trie_user_t *user = (fr_trie_user_t *) trie;
  void *data;

  /*
   *  We've matched the input exactly.  Return the
   *  user data.
   */
  if (start_bit == end_bit) return user->data;

  /*
   *  We're not at the end of the input.  Go find a
   *  deeper match.  If a match is found, return
   *  that.
   */
  data = trie_key_match(user->trie, key, start_bit, end_bit, exact);
  if (data) return data;

  /*
   *  We didn't find anything deeper in the trie,
   *  AND we require an exact match.  That's a
   *  failure.
   */
  if (exact) {
    MPRINT2("no exact match at %d\n", __LINE__);
    return NULL;
  }

  /*
   *  Return the closest (i.e. inexact) match.
   */
  return user->data;
}

static void *trie_node_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
{
  uint16_t chunk;
  fr_trie_node_t *node = (fr_trie_node_t *) trie;

  chunk = get_chunk(key, start_bit, node->bits);
  if (!node->trie[chunk]) {
    MPRINT2("no match for node chunk %02x at %d\n", chunk, __LINE__);
    return NULL;
  }

  return trie_key_match(node->trie[chunk], key, start_bit + node->bits, end_bit, exact);
}

#ifdef WITH_PATH_COMPRESSION
static void *trie_path_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
{
  uint16_t chunk;
  fr_trie_path_t *path = (fr_trie_path_t *) trie;

  chunk = get_chunk(key, start_bit, path->bits);
  if (chunk != path->chunk) return NULL;

  return trie_key_match(path->trie, key, start_bit + path->bits, end_bit, exact);
}
#endif

#ifdef WITH_NODE_COMPRESSION
static void *trie_comp_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
{
  int i;
  uint16_t chunk;
  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;

  chunk = get_chunk(key, start_bit, comp->bits);

  for (i = 0; i < comp->used; i++) {
    if (comp->index[i] < chunk) continue;

    if (comp->index[i] == chunk) {
      return trie_key_match(comp->trie[i], key, start_bit + comp->bits, end_bit, exact);
    }

    /*
     *  The edges are ordered smallest to largest.  So
     *  if the edge is larger than the chunk, NO edge
     *  will match the chunk.
     */
    return NULL;
  }

  return NULL;
}
#endif

static trie_key_match_t trie_match_table[FR_TRIE_MAX] = {
  [ FR_TRIE_USER ] = trie_user_match,
  [ FR_TRIE_NODE ] = trie_node_match,
#ifdef WITH_PATH_COMPRESSION
  [ FR_TRIE_PATH ] = trie_path_match,
#endif
#ifdef WITH_NODE_COMPRESSION
  [ FR_TRIE_COMP ] = trie_comp_match,
#endif
};


/** Match a key in a trie and return user ctx, if any
 *
 *  The key may be LONGER than entries in the trie.  In which case the
 *  closest match is returned.
 *
 * @param trie    the trie
 * @param key   the key
 * @param start_bit the start bit
 * @param end_bit the end bit
 * @param exact   do we return an exact match, or the shortest one.
 * @return
 *  - NULL on not found
 *  - void* user ctx on found
 */
static void *trie_key_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
{
  if (!trie) return NULL;

  /*
   *  We've run out of trie, so it's not a match.
   */
  if ((start_bit + trie->bits) > end_bit) {
    MPRINT2("%d + %d = %d > %d\n",
           start_bit, trie->bits, start_bit + trie->bits, end_bit);
#ifdef TESTING
    MPRINT2("no match for key too short for trie NODE-%d at %d\n", trie->number, __LINE__);
#endif
    return NULL;
  }

  TRIE_TYPE_CHECK(match, NULL);

  /*
   *  Recursively match each type.
   */
  return trie_match_table[trie->type](trie, key, start_bit, end_bit, exact);
}

/** Lookup a key in a trie and return user ctx, if any
 *
 *  The key may be LONGER than entries in the trie.  In which case the
 *  closest match is returned.
 *
 * @param ft   the trie
 * @param key  the key bytes
 * @param keylen length in bits of the key
 * @return
 *  - NULL on not found
 *  - void* user ctx on found
 */
void *fr_trie_lookup_by_key(fr_trie_t const *ft, void const *key, size_t keylen)
{
  fr_trie_user_t *user;

  if (keylen > MAX_KEY_BITS) return NULL;

  if (!ft->trie) return NULL;

  user = UNCONST(fr_trie_user_t *, ft);

  return trie_key_match(user->trie, key, 0, keylen, false);
}

/** Match a key and length in a trie and return user ctx, if any
 *
 * Only the exact match is returned.
 *
 * @param ft   the trie
 * @param key  the key bytes
 * @param keylen length in bits of the key
 * @return
 *  - NULL on not found
 *  - void* user ctx on found
 */
void *fr_trie_match_by_key(fr_trie_t const *ft, void const *key, size_t keylen)
{
  fr_trie_user_t *user;

  if (keylen > MAX_KEY_BITS) return NULL;

  if (!ft->trie) return NULL;

  user = UNCONST(fr_trie_user_t *, ft);

  return trie_key_match(user->trie, key, 0, keylen, true);
}

/* INSERT FUNCTIONS */

#ifdef TESTING
static void trie_check(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, void *data, int lineno)
{
  void *answer;

  trie_sprint(trie, key, start_bit, lineno);

  answer = trie_key_match(trie, key, start_bit, end_bit, true);
  if (!answer) {
    fr_strerror_printf("Failed trie check answer at %d", lineno);

    // print out the current trie!
    MPRINT3("%.*sFailed to find user data %s from start %d end %d at %d\n", start_bit, spaces, data,
      start_bit, end_bit, lineno);
    fr_cond_assert(0);
  }

  if (answer != data) {
    fr_strerror_printf("Failed trie check answer == data at %d", lineno);

    MPRINT3("%.*sFound wrong user data %s != %s, from start %d end %d at %d\n", start_bit, spaces,
      answer, data, start_bit, end_bit, lineno);
    fr_cond_assert(0);
  }
}
#else
#define trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)
#endif

static int trie_key_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data) CC_HINT(nonnull(2,3,6));

typedef int (*trie_key_insert_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data);

static int trie_user_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  fr_trie_t *trie = *trie_p;
  fr_trie_user_t *user = (fr_trie_user_t *) trie;

  MPRINT3("user insert to start %d end %d with data %s\n", start_bit, end_bit, (char *) data);

  /*
   *  Just insert the key into user->trie.
   */
  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
  return trie_key_insert(ctx, &user->trie, key, start_bit, end_bit, data);
}

static int trie_node_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  fr_trie_t *trie = *trie_p;
  fr_trie_node_t *node = (fr_trie_node_t *) trie;
  fr_trie_t *trie_to_free = NULL;
  uint32_t chunk;

  MPRINT3("%.*snode insert end %d with data %s\n",
    start_bit, spaces, end_bit, (char *) data);

  /*
   *  The current node is longer than the input bits
   *  for the key.  Split the node into a smaller
   *  N-way node, and insert the key into the (now
   *  fitting) node.
   */
  if ((start_bit + node->bits) > end_bit) {
    fr_trie_node_t *split;

    MPRINT3("%.*snode insert splitting %d at %d start %d end %d with data %s\n",
      start_bit, spaces,
      node->bits, start_bit - end_bit,
      start_bit, end_bit, (char *) data);

    split = trie_node_split(ctx, node, end_bit - start_bit);
    if (!split) {
      fr_strerror_printf("Failed splitting node at %d\n", __LINE__);
      return -1;
    }

    trie_to_free = (fr_trie_t *) node;
    node = split;
  }

  chunk = get_chunk(key, start_bit, node->bits);

  /*
   *  No existing trie, create a brand new trie from
   *  the key.
   */
  if (!node->trie[chunk]) {
    node->trie[chunk] = trie_key_alloc(ctx, key, start_bit + node->bits, end_bit, data);
    if (!node->trie[chunk]) {
      fr_strerror_printf("Failed key_alloc at %d\n", __LINE__);
      if (trie_to_free) trie_free(trie_to_free);
      return -1;
    }
    node->used++;

  } else {
    /*
     *  Recurse in order to insert the key
     *  into the current node.
     */
    MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
    if (trie_key_insert(ctx, &node->trie[chunk], key, start_bit + node->bits, end_bit, data) < 0) {
      MPRINT("Failed recursing at %d\n", __LINE__);
      if (trie_to_free) trie_free(trie_to_free);
      return -1;
    }
  }

  trie_check((fr_trie_t *) node, key, start_bit, end_bit, data, __LINE__);

  MPRINT3("%.*snode insert returning at %d\n",
    start_bit, spaces, __LINE__);

  if (trie_to_free) trie_free(trie_to_free);
  *trie_p = (fr_trie_t *) node;
  VERIFY(node);
  return 0;
}

#ifdef WITH_PATH_COMPRESSION
static CC_HINT(nonnull(2,3,6)) int trie_path_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  fr_trie_t *trie = *trie_p;
  fr_trie_path_t *path = (fr_trie_path_t *) trie;
  uint32_t chunk;
  int lcp, bits;
  uint8_t const *key2;
  int start_bit2;
  fr_trie_t *node;
  fr_trie_t *child;

  MPRINT3("%.*spath insert start %d end %d with key %02x%02x data %s\n",
    start_bit, spaces, start_bit, end_bit, key[0], key[1], (char *) data);

  VERIFY(path);
  trie_sprint((fr_trie_t *) path, key, start_bit, __LINE__);

  /*
   *  The key exactly matches the path.  Recurse.
   */
  if (start_bit + path->bits <= end_bit) {
    chunk = get_chunk(key, start_bit, path->bits);

    /*
     *  The chunk matches exactly.  Recurse to
     *  insert the key into the child trie.
     */
    if (chunk == path->chunk) {
      MPRINT3("%.*spath chunk matches %04x bits of %d\n",
        start_bit, spaces, chunk, path->bits);
      MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
      if (trie_key_insert(ctx, &path->trie, key, start_bit + path->bits, end_bit, data) < 0) {
        return -1;
      }

      trie_check((fr_trie_t *) path, key, start_bit, end_bit, data, __LINE__);

      MPRINT3("%.*spath returning at %d\n", start_bit, spaces, __LINE__);
      VERIFY(path);
      return 0;
    }

    bits = path->bits;
    MPRINT3("%.*spath using %d\n", start_bit, spaces, path->bits);

  } else {
    /*
     *  Limit the number of bits we check to
     *  the number of bits left in the key.
     */
    bits = end_bit - start_bit;
    MPRINT3("%.*spath limiting %d to %d\n", start_bit, spaces, path->bits, bits);
  }

  /*
   *  Figure out what part of the key we need to
   *  look at for LCP.
   */
  key2 = key;
  start_bit2 = start_bit;
  if (start_bit2 > 7) {
    key2 += (start_bit2 >> 3);
    start_bit2 -= 8 * (start_bit2 >> 3);
  }

  /*
   *  Get the LCP.  If we have one, split the path
   *  node at the LCP.  Replace the parent with the
   *  first half of the path, and build an N-way
   *  node for the second half.
   */
  lcp = fr_trie_key_lcp(&path->key[0], bits, key2, bits, start_bit2);
  MPRINT3("%.*spath lcp %d\n", start_bit, spaces, lcp);

  /*
   *  This should have been caught above.
   */
  if (lcp == path->bits) {
    fr_strerror_const("found lcp which should have been previously found");
    return -1;
  }

  if (lcp > 0) {
    fr_trie_path_t *split;

    /*
     *  Note that "path" is still valid after this
     *  call.  We will rewrite things on the way back
     *  up the stack.
     */
    MPRINT3("%.*spath split depth %d bits %d at lcp %d with data %s\n",
      start_bit, spaces, start_bit, path->bits, lcp, (char *) data);

    MPRINT3("%.*spath key %02x%02x input key %02x%02x, offset %d\n",
      start_bit, spaces,
      path->key[0],path->key[1],
      key[0], key[1],
      start_bit2);

    split = trie_path_split(ctx, path, start_bit2, lcp);
    if (!split) {
      fr_strerror_printf("failed path split at %d\n", __LINE__);
      return -1;
    }

    trie_sprint((fr_trie_t *) path, key, start_bit, __LINE__);
    trie_sprint((fr_trie_t *) split, key, start_bit, __LINE__);
    trie_sprint((fr_trie_t *) split->trie, key, start_bit + split->bits, __LINE__);

    /*
     *  Recurse to insert the key into the child node.
     *  Note that if "bits > MAX_NODE_BITS", we will
     *  have to split "path" again.
     */
    MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
    if (trie_key_insert(ctx, &split->trie, key, start_bit + split->bits, end_bit, data) < 0) {
      talloc_free(split->trie);
      talloc_free(split);
      return -1;
    }

    /*
     *  We can't have two LCPs in a row here, as we
     *  SHOULD have found the LCP above!
     */
    fr_cond_assert(split->type == FR_TRIE_PATH);
    fr_cond_assert(split->trie->type != FR_TRIE_PATH);

    trie_check((fr_trie_t *) split, key, start_bit, end_bit, data, __LINE__);

    MPRINT3("%.*spath returning at %d\n", start_bit, spaces, __LINE__);
    talloc_free(path);
    *trie_p = (fr_trie_t *) split;
    VERIFY(split);
    return 0;
  }

  /*
   *  Else there's no common prefix.  Just create an
   *  fanout node.
   */
  /*
   *  We only want two edges here. Try to create a
   *  compressed N-way node if possible.
   */
#ifdef WITH_NODE_COMPRESSION
  if (bits > 2) {
    if (bits > MAX_COMP_BITS) bits = MAX_COMP_BITS;

    MPRINT3("%.*sFanout to comp %d at depth %d data %s\n", start_bit, spaces, bits, start_bit, (char *) data);
    node = (fr_trie_t *) fr_trie_comp_alloc(ctx, bits);
  } else
#endif
  {
    /*
     *  Without path compression create no more than a
     *  16-way node.
     */
    if (bits > MAX_NODE_BITS) bits = MAX_NODE_BITS;

    MPRINT3("%.*sFanout to node %d at depth %d data %s\n", start_bit, spaces, bits, start_bit, (char *) data);
    node = (fr_trie_t *) trie_node_alloc(ctx, bits);
  }
  if (!node) return -1;

  /*
   *  Get the chunk from the path, and insert the child trie
   *  into the node at that chunk.
   */
  chunk = get_chunk(&path->key[0], start_bit2, node->bits);

  if (node->bits == path->bits) {
    child = path->trie;

  } else {
    /*
     *  Skip the common prefix.
     */
    child = (fr_trie_t *) fr_trie_path_alloc(ctx, &path->key[0], start_bit2 + node->bits, start_bit2 + path->bits);
    if (!child) {
      fr_strerror_printf("failed allocating path child at %d", __LINE__);
      return -1;
    }

    /*
     *  Patch in the child trie.
     */
    ((fr_trie_path_t *)child)->trie = path->trie;

    VERIFY(child);
  }

  trie = NULL;

  /*
   *  Recurse to insert the key into the second edge.  If
   *  this fails, then we haven't changed anything.  So just
   *  free memory and return.
   *
   *  Note that if "bits > DEFAULT_BITS", we will have to
   *  split "path" again.
   */
  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
  if (trie_key_insert(ctx, &trie, key, start_bit + node->bits, end_bit, data) < 0) {
    talloc_free(node);
    if (child != path->trie) talloc_free(child);
    return -1;
  }

  /*
   *  Copy the first edge over to the first chunk.
   */
  if (trie_add_edge(node, chunk, child) < 0) {
    fr_strerror_printf("chunk failure in insert node %d at %d", node->bits, __LINE__);
    talloc_free(node);
    if (child != path->trie) talloc_free(child);
    return -1;
  }

  /*
   *  Copy the second edge from the new chunk.
   */
  chunk = get_chunk(key, start_bit, node->bits);
  if (trie_add_edge(node, chunk, trie) < 0) {
    fr_strerror_printf("chunk failure in insert node %d at %d", node->bits, __LINE__);
    talloc_free(node);
    trie_free(trie);
    return -1;
  }

  trie_check((fr_trie_t *) node, key, start_bit, end_bit, data, __LINE__);

  MPRINT3("%.*spath returning at %d\n", start_bit, spaces, __LINE__);

  /*
   *  Only update the answer if the insert succeeded.
   */
  *trie_p = node;
  talloc_free(path);
  VERIFY(node);
  return 0;
}
#endif

#ifdef WITH_NODE_COMPRESSION
static CC_HINT(nonnull(2,3,6)) int trie_comp_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  int i, bits;
  fr_trie_t *trie = *trie_p;
  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
  fr_trie_node_t *node;
  uint16_t chunk;

  MPRINT3("%.*scomp insert start %d end %d with key %02x%02x data %s\n",
    start_bit, spaces, start_bit, end_bit, key[0], key[1], (char *) data);

  if ((end_bit - start_bit) < comp->bits) {
    fr_strerror_printf("Not implemented at %d", __LINE__);
    return -1;
  }

  chunk = get_chunk(key, start_bit, comp->bits);

  /*
   *  Search for a matching edge.  If found, recurse and
   *  insert the key there.
   */
  for (i = 0; i < comp->used; i++) {
    if (comp->index[i] < chunk) continue;

    /*
     *  We've found a matching chunk, recurse.
     */
    if (comp->index[i] == chunk) {
      MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
      if (trie_key_insert(ctx, &comp->trie[i], key, start_bit + comp->bits, end_bit, data) < 0) {
        MPRINT3("%.*scomp failed recursing at %d", start_bit, spaces, __LINE__);
        return -1;
      }

      trie_check((fr_trie_t *) comp, key, start_bit, end_bit, data, __LINE__);

      MPRINT3("%.*scomp returning at %d", start_bit, spaces, __LINE__);
      VERIFY(comp);
      return 0;
    }

    /*
     *  The chunk is larger than the current edge,
     *  stop.
     */
    break;
  }

  /*
   *  No edge matches the chunk from the key.  Insert the
   *  child trie into a place-holder entry, so that we don't
   *  modify the current node on failure.
   */
  if (comp->used < MAX_COMP_EDGES) {
    MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
    trie = NULL;
    if (trie_key_insert(ctx, &trie, key, start_bit + comp->bits, end_bit, data) < 0) {
      MPRINT3("%.*scomp failed recursing at %d", start_bit, spaces, __LINE__);
      return -1;
    }
    fr_cond_assert(trie != NULL);

    if (trie_add_edge((fr_trie_t *) comp, chunk, trie) < 0) {
      talloc_free(trie); // @todo - there may be multiple nodes here?
      return -1;
    }

    trie_check((fr_trie_t *) comp, key, start_bit, end_bit, data, __LINE__);

    VERIFY(comp);
    return 0;
  }

  /*
   *  All edges are used.  Create an N-way node.
   */

  /*
   *  @todo - limit bits by calling
   *  trie_comp_split()?
   */
  bits = comp->bits;

  MPRINT3("%.*scomp swapping to node bits %d at %d\n", start_bit, spaces, bits, __LINE__);

  node = trie_node_alloc(ctx, bits);
  if (!node) return -1;

  for (i = 0; i < comp->used; i++) {
    fr_cond_assert(node->trie[comp->index[i]] == NULL);
    node->trie[comp->index[i]] = comp->trie[i];
  }
  node->used = comp->used;
  node->used += (node->trie[chunk] == NULL); /* will get set if the recursive insert succeeds */

  /*
   *  Insert the new chunk, which may or may not overlap
   *  with an existing one.
   */
  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
  if (trie_key_insert(ctx, &node->trie[chunk], key, start_bit + node->bits, end_bit, data) < 0) {
    MPRINT3("%.*scomp failed recursing at %d", start_bit, spaces, __LINE__);
    talloc_free(node);
    return -1;
  }

  trie_check((fr_trie_t *) node, key, start_bit, end_bit, data, __LINE__);

  MPRINT3("%.*scomp returning at %d", start_bit, spaces, __LINE__);

  talloc_free(comp);
  *trie_p = (fr_trie_t *) node;
  VERIFY(node);
  return 0;
}
#endif

static trie_key_insert_t trie_insert_table[FR_TRIE_MAX] = {
  [ FR_TRIE_USER ] = trie_user_insert,
  [ FR_TRIE_NODE ] = trie_node_insert,
#ifdef WITH_PATH_COMPRESSION
  [ FR_TRIE_PATH ] = trie_path_insert,
#endif
#ifdef WITH_NODE_COMPRESSION
  [ FR_TRIE_COMP ] = trie_comp_insert,
#endif
};

/** Insert a binary key into the trie
 *
 *  The key must have at least ((start_bit + keylen) >> 3) bytes
 *
 * @param ctx   the talloc ctx
 * @param[in,out] trie_p the trie where things are inserted
 * @param key   the binary key
 * @param start_bit the start bit
 * @param end_bit the end bit
 * @param data    user data to insert
 * @return
 *  - <0 on error
 *  - 0 on success
 */
static int trie_key_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
{
  fr_trie_t *trie = *trie_p;

  /*
   *  We've reached the end of the trie, but may still have
   *  key bits to insert.
   */
  if (!trie) {
    *trie_p = trie_key_alloc(ctx, key, start_bit, end_bit, data);
    if (!*trie_p) return -1;
    return 0;
  }

  MPRINT3("%.*sIN recurse at %d\n", start_bit, spaces, __LINE__);
  trie_sprint(trie, key, start_bit, __LINE__);

  /*
   *  We've reached the end of the key.  Insert a user node
   *  here, and push the remaining bits of the trie to after
   *  the user node.
   */
  if (start_bit == end_bit) {
    fr_trie_user_t *user;

    if (trie->type == FR_TRIE_USER) {
      fr_strerror_printf("already has a user node at %d\n", __LINE__);
      return -1;
    }

    user = fr_trie_user_alloc(ctx, data);
    if (!user) return -1;

    user->trie = trie;
    *trie_p = (fr_trie_t *) user;
    return 0;
  }

  TRIE_TYPE_CHECK(insert, -1);

#ifndef TESTING
  return trie_insert_table[trie->type](ctx, trie_p, key, start_bit, end_bit, data);
#else
  MPRINT3("%.*srecurse at start %d end %d with data %s\n", start_bit, spaces, start_bit, end_bit, (char *) data);

  if (trie_insert_table[trie->type](ctx, trie_p, key, start_bit, end_bit, data) < 0) {
    return -1;
  }

  trie_check(*trie_p, key, start_bit, end_bit, data, __LINE__);

  return 0;
#endif
}

/** Insert a key and user ctx into a trie
 *
 * @param ft   the trie
 * @param key  the key
 * @param keylen key length in bits
 * @param data   user ctx information to associated with the key
 * @return
 *  - <0 on error
 *  - 0 on success
 */
int fr_trie_insert_by_key(fr_trie_t *ft, void const *key, size_t keylen, void const *data)
{
  void *my_data;
  fr_trie_user_t *user;

  if (keylen > MAX_KEY_BITS) {
    fr_strerror_printf("keylen too long (%u > %d)", (unsigned int) keylen, MAX_KEY_BITS);
    return -1;
  }

  user = (fr_trie_user_t *) ft;

  /*
   *  Do a lookup before insertion.  If we tried to insert
   *  the key with new nodes and then discovered a conflict,
   *  we would not be able to undo the process.  This check
   *  ensures that the insertion can modify the trie in
   *  place without worry.
   */
  if (trie_key_match(user->trie, key, 0, keylen, true) != NULL) {
    fr_strerror_const("Cannot insert due to pre-existing key");
    return -1;
  }

  my_data = UNCONST(void *, data);
  MPRINT2("No match for data, inserting...\n");

  MPRINT3("%.*srecurse STARTS at %d with %.*s=%s\n", 0, spaces, __LINE__,
    (int) keylen, key, my_data);
  return trie_key_insert(user->data, &user->trie, key, 0, keylen, my_data);
}

/* REMOVE FUNCTIONS */
static void *trie_key_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit);

typedef void *(*trie_key_remove_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit);

static void *trie_user_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
{
  fr_trie_t *trie = *trie_p;
  fr_trie_user_t *user = (fr_trie_user_t *) trie;

  /*
   *  We're at the end of the key, return the data
   *  given here, and free the node that we're
   *  removing.
   */
  if (start_bit == end_bit) {
    void *data = user->data;

    *trie_p = user->trie;
    talloc_free(user);

    return data;
  }

  return trie_key_remove(ctx, &user->trie, key, start_bit, end_bit);
}

static void *trie_node_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
{
  fr_trie_t *trie = *trie_p;
  fr_trie_node_t *node = (fr_trie_node_t *) trie;
  uint32_t chunk;
  void *data;

  chunk = get_chunk(key, start_bit, node->bits);
  if (!node->trie[chunk]) return NULL;

  data = trie_key_remove(ctx, &node->trie[chunk], key, start_bit + node->bits, end_bit);
  if (!data) return NULL;

  /*
   *  The trie still has a subtrie.  Just return the data.
   */
  if (node->trie[chunk]) return data;

  /*
   *  One less used edge.
   */
  node->used--;
  if (node->used > 0) return data;

  /*
   *  @todo - if we have path compression, and
   *  node->used==1, then create a fr_trie_path_t from the
   *  chunk, and concatenate it (if necessary) to any
   *  trailing path compression node.
   */

  /*
   *  Our entire node is empty.  Delete it as we walk back up the trie.
   */
  *trie_p = NULL;
  talloc_free(node); /* no children */
  return data;
}

#ifdef WITH_PATH_COMPRESSION
static void *trie_path_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
{
  fr_trie_t *trie = *trie_p;
  fr_trie_path_t *path = (fr_trie_path_t *) trie;
  uint32_t chunk;
  void *data;

  chunk = get_chunk(key, start_bit, path->bits);

  /*
   *  No match, can't remove it.
   */
  if (path->chunk != chunk) return NULL;

  data = trie_key_remove(ctx, &path->trie, key, start_bit + path->bits, end_bit);
  if (!data) return NULL;

  /*
   *  The trie still has a subtrie.  Just return the data.
   */
  if (path->trie) return data;

  /*
   *  Our entire path is empty.  Delete it as we walk back up the trie.
   */
  *trie_p = NULL;
  talloc_free(path); /* no children */
  return data;
}
#endif

#ifdef WITH_NODE_COMPRESSION
static void *trie_comp_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
{
  int i, j;
  uint16_t chunk;
  void *data;
  fr_trie_comp_t *comp = *(fr_trie_comp_t **) trie_p;
  fr_trie_path_t *path;

  chunk = get_chunk(key, start_bit, comp->bits);

  MPRINT3("%.*sremove at %d\n", start_bit, spaces, __LINE__);
  trie_sprint(*trie_p, key, start_bit, __LINE__);

  for (i = 0; i < comp->used; i++) {
    if (comp->index[i] < chunk) continue;

    if (comp->index[i] == chunk) {
      break;
    }

    /*
     *  The edges are ordered smallest to largest.  So
     *  if the edge is larger than the chunk, NO edge
     *  will match the chunk.
     */
    if (comp->index[i] > chunk) return NULL;
  }

  /*
   *  Didn't find it, fail.
   */
  if (i >= comp->used) return NULL;

  fr_cond_assert(chunk == comp->index[i]);

  data = trie_key_remove(ctx, &comp->trie[i], key, start_bit + comp->bits, end_bit);
  if (!data) return NULL;

  /*
   *  The trie still has a subtrie.  Just return the data.
   */
  if (comp->trie[i]) {
    MPRINT3("%.*sremove at %d\n", start_bit, spaces, __LINE__);
    trie_sprint((fr_trie_t *) comp, key, start_bit, __LINE__);
    VERIFY(comp);
    return data;
  }

  /*
   *  Shrinking at the end is easy, we don't need to do
   *  anything.  For shrinking in the middle, we just copy
   *  the entries down.
   */
  for (j = i; j < comp->used - 1; j++) {
    comp->index[j] = comp->index[j + 1];
    comp->trie[j] = comp->trie[j + 1];
  }
  comp->used--;

  if (comp->used >= 2) {
    VERIFY(comp);
    return data;
  }

  /*
   *  Our entire path is empty.  Delete it as we walk back
   *  up the trie.  We hope that this doesn't happen.
   */
  if (!comp->used) {
    *trie_p = NULL;
    talloc_free(comp); /* no children */
    MPRINT3("%.*sremove at %d\n", start_bit, spaces, __LINE__);
    return data;
  }

  /*
   *  Only one edge.  Turn it back into a path node.  Note
   *  that we pass "key" here, which is wrong... that's the
   *  key we're removing, not the key left in the node.  But
   *  we fix that later.
   *
   *  @todo - check the child. If it's also a path node, try
   *  to concatenate the nodes together.
   */
  path = fr_trie_path_alloc(ctx, key, start_bit, start_bit + comp->bits);
  if (!path) return data;

  /*
   *  Tie the new node in.
   */
  path->trie = comp->trie[0];

  /*
   *  Fix up the chunk and key to be the one left in the
   *  trie, not the one which was removed.
   */
  path->chunk = comp->index[0];
  write_chunk(&path->key[0], start_bit & 0x07, path->bits, path->chunk);

  *trie_p = (fr_trie_t *) path;
  talloc_free(comp);
  VERIFY(path);
  return data;
}
#endif

static trie_key_remove_t trie_remove_table[FR_TRIE_MAX] = {
  [ FR_TRIE_USER ] = trie_user_remove,
  [ FR_TRIE_NODE ] = trie_node_remove,
#ifdef WITH_PATH_COMPRESSION
  [ FR_TRIE_PATH ] = trie_path_remove,
#endif
#ifdef WITH_NODE_COMPRESSION
  [ FR_TRIE_COMP ] = trie_comp_remove,
#endif
};

/** Remove a key from a trie, and return the user data.
 *
 */
static void *trie_key_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
{
  fr_trie_t *trie = *trie_p;

  if (!trie) return NULL;

  /*
   *  We can't remove a key which is shorter than the
   *  current trie.
   */
  if ((start_bit + trie->bits) > end_bit) return NULL;

  TRIE_TYPE_CHECK(remove, NULL);

  return trie_remove_table[trie->type](ctx, trie_p, key, start_bit, end_bit);
}

/** Remove a key and return the associated user ctx
 *
 *  The key must match EXACTLY.  This is not a prefix match.
 *
 * @param ft   the trie
 * @param key  the key
 * @param keylen key length in bits
 * @return
 *  - NULL on not found
 *  - user ctx data on success
 */
void *fr_trie_remove_by_key(fr_trie_t *ft, void const *key, size_t keylen)
{
  fr_trie_user_t *user;

  if (keylen > MAX_KEY_BITS) return NULL;

  if (!ft->trie) return NULL;

  user = (fr_trie_user_t *) ft;

  /*
   *  Remove the user trie, not ft->trie.
   */
  return trie_key_remove(user->data, &user->trie, key, 0, (int) keylen);
}

/* WALK FUNCTIONS */

typedef struct fr_trie_callback_s fr_trie_callback_t;

typedef int (*fr_trie_key_walk_t)(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more);

static int trie_key_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more);

struct fr_trie_callback_s {
  uint8_t     *start;
  uint8_t const   *end;

  void      *ctx;

  fr_trie_key_walk_t  callback;
  fr_trie_walk_t    user_callback;
};

static int trie_user_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
{
  fr_trie_user_t *user = (fr_trie_user_t *) trie;

  if (!user->trie) return 0;

  return trie_key_walk(user->trie, cb, depth, more);
}

static int trie_node_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
{
  int i, used;
  fr_trie_node_t *node = (fr_trie_node_t *) trie;

  used = 0;
  for (i = 0; i < (1 << node->bits); i++) {
    if (!node->trie[i]) continue;

    write_chunk(cb->start, depth, node->bits, (uint16_t) i);
    used++;

    if (trie_key_walk(node->trie[i], cb, depth + node->bits,
             more || (used < node->used)) < 0) {
      return -1;
    }
  }

  return 0;
}

#ifdef WITH_PATH_COMPRESSION
static int trie_path_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
{
  fr_trie_path_t *path = (fr_trie_path_t *) trie;

  write_chunk(cb->start, depth, path->bits, path->chunk);

  fr_cond_assert(path->trie != NULL);
  return trie_key_walk(path->trie, cb, depth + path->bits, more);
}
#endif

#ifdef WITH_NODE_COMPRESSION
static int trie_comp_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
{
  int i, used;
  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;

  used = 0;
  for (i = 0; i < comp->used; i++) {
    write_chunk(cb->start, depth, comp->bits, comp->index[i]);

    fr_cond_assert(comp->trie[i] != NULL);

    used++;
    if (trie_key_walk(comp->trie[i], cb, depth + comp->bits,
             more || (used < comp->used)) < 0) {
      return -1;
    }
  }

  return 0;
}
#endif

static fr_trie_key_walk_t trie_walk_table[FR_TRIE_MAX] = {
  [ FR_TRIE_USER ] = trie_user_walk,
  [ FR_TRIE_NODE ] = trie_node_walk,
#ifdef WITH_PATH_COMPRESSION
  [ FR_TRIE_PATH ] = trie_path_walk,
#endif
#ifdef WITH_NODE_COMPRESSION
  [ FR_TRIE_COMP ] = trie_comp_walk,
#endif
};

static int trie_key_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
{
  /*
   *  Do the callback before anything else.
   */
  if (cb->callback(trie, cb, depth, more) < 0) return -1;

  if (!trie) {
    fr_cond_assert(depth == 0);
    return 0;
  }

  TRIE_TYPE_CHECK(walk, -1);

  /*
   *  No more buffer space, stop.
   */
  if ((cb->start + BYTEOF(depth + trie->bits + 8)) >= cb->end) return 0;

  return trie_walk_table[trie->type](trie, cb, depth, more);
}

#ifdef WITH_TRIE_VERIFY
/* VERIFY FUNCTIONS */

typedef int (*trie_verify_t)(fr_trie_t *trie);

static int trie_user_verify(fr_trie_t *trie)
{
  fr_trie_user_t *user = (fr_trie_user_t *) trie;

  if (!user->data) {
    fr_strerror_const("user node has no user data");
    return -1;
  }

  if (!user->trie) return 0;

  return trie_verify(user->trie);
}

static int trie_node_verify(fr_trie_t *trie)
{
  fr_trie_node_t *node = (fr_trie_node_t *) trie;
  int i, used;

  if ((node->bits == 0) || (node->bits > MAX_NODE_BITS)) {
    fr_strerror_printf("N-way node has invalid bits %d",
           node->bits);
    return -1;
  }

  if ((node->used == 0) || (node->used > (1 << node->bits))) {
    fr_strerror_printf("N-way node has invalid used %d for bits %d",
           node->used, node->bits);
    return -1;
  }

  used = 0;
  for (i = 0; i < (1 << node->bits); i++) {
    if (!node->trie[i]) continue;

    if (trie_verify(node->trie[i]) < 0) return -1;

    used++;
  }

  if (used != node->used) {
    fr_strerror_printf("N-way node has incorrect used %d when actually used %d",
           node->used, used);
    return -1;
  }

  return 0;
}

#ifdef WITH_PATH_COMPRESSION
static int trie_path_verify(fr_trie_t *trie)
{
  fr_trie_path_t *path = (fr_trie_path_t *) trie;

  if ((path->bits == 0) || (path->bits > 16)) {
    fr_strerror_printf("path node has invalid bits %d",
           path->bits);
    return -1;
  }

  if (!path->trie) {
    fr_strerror_const("path node has no child trie");
    return -1;
  }

  return trie_verify(path->trie);
}
#endif

#ifdef WITH_NODE_COMPRESSION
static int trie_comp_verify(fr_trie_t *trie)
{
  int i, used;
  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;

  if ((comp->bits == 0) || (comp->bits > MAX_COMP_BITS)) {
    fr_strerror_printf("comp node has invalid bits %d",
           comp->bits);
    return -1;
  }

  used = 0;
  for (i = 0; i < comp->used; i++) {
    if (!comp->trie[i]) {
      fr_strerror_printf("comp node has no child trie at %d", i);
      return -1;
    }

    if ((i + 1) < comp->used) {
      if (comp->index[i] >= comp->index[i + 1]) {
        fr_strerror_printf("comp node has inverted edges at %d (%04x >= %04x)",
               i, comp->index[i], comp->index[i + 1]);
        return -1;
      }
    }

    if (trie_verify(comp->trie[i]) < 0) return -1;
    used++;
  }

  if (used != comp->used) {
    fr_strerror_printf("Compressed node has incorrect used %d when actually used %d",
           comp->used, used);
    return -1;
  }

  return 0;
}
#endif

static trie_verify_t trie_verify_table[FR_TRIE_MAX] = {
  [ FR_TRIE_USER ] = trie_user_verify,
  [ FR_TRIE_NODE ] = trie_node_verify,
#ifdef WITH_PATH_COMPRESSION
  [ FR_TRIE_PATH ] = trie_path_verify,
#endif
#ifdef WITH_NODE_COMPRESSION
  [ FR_TRIE_COMP ] = trie_comp_verify,
#endif
};


/**  Verify the trie nodes
 *
 */
static int trie_verify(fr_trie_t *trie)
{
  if (!trie) return 0;

  TRIE_TYPE_CHECK(verify, -1);

  return trie_verify_table[trie->type](trie);
}
#endif  /* WITH_TRIE_VERIFY */

/* MISCELLANEOUS FUNCTIONS */

#ifdef TESTING
/** Dump a trie edge in canonical form.
 *
 */
static void trie_dump_edge(FILE *fp, fr_trie_t *trie)
{
  fr_cond_assert(trie != NULL);

  fprintf(fp, "NODE-%d\n", trie->number);
  return;
}


typedef void (*fr_trie_dump_t)(FILE *fp, fr_trie_t *trie, char const *key, int keylen);

static void trie_user_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
{
  fr_trie_user_t *user = (fr_trie_user_t *) trie;
  int bytes = BYTES(keylen);

  fprintf(fp, "{ NODE-%d\n", user->number);
  fprintf(fp, "\ttype\tUSER\n");
  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);

  fprintf(fp, "\tdata\t\"%s\"\n", (char const *) user->data);
  if (!user->trie) {
    fprintf(fp, "}\n\n");
    return;
  }

  fprintf(fp, "\tnext\t");
  trie_dump_edge(fp, user->trie);
  fprintf(fp, "}\n\n");
}

static void trie_node_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
{
  fr_trie_node_t *node = (fr_trie_node_t *) trie;
  int i;
  int bytes = BYTES(keylen);

  fprintf(fp, "{ NODE-%d\n", node->number);
  fprintf(fp, "\ttype\tNODE\n");
  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);

  fprintf(fp, "\tbits\t%d\n", node->bits);
  fprintf(fp, "\tused\t%d\n", node->used);

  for (i = 0; i < (1 << node->bits); i++) {
    if (!node->trie[i]) continue;

    fprintf(fp, "\t%02x\t", (int) i);
    trie_dump_edge(fp, node->trie[i]);
  }
  fprintf(fp, "}\n\n");
}

#ifdef WITH_PATH_COMPRESSION
static void trie_path_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
{
  fr_trie_path_t *path = (fr_trie_path_t *) trie;
  int bytes = BYTES(keylen);

  fprintf(fp, "{ NODE-%d\n", path->number);
  fprintf(fp, "\ttype\tPATH\n");
  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);

  fprintf(fp, "\tbits\t%d\n", (int) path->bits);
  fprintf(fp, "\tpath\t");

  fprintf(fp, "%02x %02x", path->key[0], path->key[1]);

  fprintf(fp, "\n");

  fprintf(fp, "\tnext\t");
  trie_dump_edge(fp, path->trie);

  fprintf(fp, "}\n\n");
}
#endif

#ifdef WITH_NODE_COMPRESSION
static void trie_comp_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
{
  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
  int i;
  int bytes = BYTES(keylen);

  fprintf(fp, "{ NODE-%d\n", comp->number);
  fprintf(fp, "\ttype\tCOMP\n");
  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);

  fprintf(fp, "\tbits\t%d\n", comp->bits);
  fprintf(fp, "\tused\t%d\n", comp->used);

  for (i = 0; i < comp->used; i++) {
    fprintf(fp, "\t%d = %02x\t", i, comp->index[i]);
    trie_dump_edge(fp, comp->trie[i]);
  }
  fprintf(fp, "}\n\n");
}

#endif

static fr_trie_dump_t trie_dump_table[FR_TRIE_MAX] = {
  [ FR_TRIE_USER ] = trie_user_dump,
  [ FR_TRIE_NODE ] = trie_node_dump,
#ifdef WITH_PATH_COMPRESSION
  [ FR_TRIE_PATH ] = trie_path_dump,
#endif
#ifdef WITH_NODE_COMPRESSION
  [ FR_TRIE_COMP ] = trie_comp_dump,
#endif
};


/**  Dump the trie nodes
 *
 */
static int _trie_dump_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
{
  FILE *fp = cb->ctx;

  if (!trie) return 0;

  TRIE_TYPE_CHECK(dump, -1);

  trie_dump_table[trie->type](fp, trie, (char const *) cb->start, keylen);
  return 0;
}

/**  Print the strings accepted by a trie to a file
 *
 */
static int _trie_print_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
{
  int bytes;
  FILE *fp = cb->ctx;
  fr_trie_user_t *user;

  if (!trie || (trie->type != FR_TRIE_USER)) {
    return 0;
  }

  bytes = BYTES(keylen);
  user = (fr_trie_user_t *) trie;

  if ((keylen & 0x07) != 0) {
    fprintf(fp, "{%d}%.*s\t%s\n", keylen, bytes, cb->start, (char const *) user->data);
  } else {
    fprintf(fp, "%.*s\t%s\n", bytes, cb->start, (char const *) user->data);
  }

  return 0;
}
#endif  /* TESTING */


/**  Implement the user-visible side of the walk callback.
 *
 */
static int _trie_user_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
{
  fr_trie_user_t *user;

  if (!trie || (trie->type != FR_TRIE_USER)) return 0;

  user = (fr_trie_user_t *) trie;

  /*
   *  Call the user function with the key, key length, and data.
   */
  if (cb->user_callback(cb->start, keylen, UNCONST(void *, user->data), cb->ctx) < 0) {
    return -1;
  }

  return 0;
}

int fr_trie_walk(fr_trie_t *ft, void *ctx, fr_trie_walk_t callback)
{
  uint8_t buffer[MAX_KEY_BYTES + 1];
  fr_trie_callback_t my_cb = {
    .start = buffer,
    .end = buffer + sizeof(buffer),
    .callback = _trie_user_cb,
    .user_callback = callback,
    .ctx = ctx
  };

  memset(buffer, 0, sizeof(buffer));

  /*
   *  Call the internal walk function to do the work.
   */
  return trie_key_walk(ft->trie, &my_cb, 0, false);
}


/**********************************************************************/

/*
 *  Object API.
 */

/** Find an element in the trie, returning the data.
 *
 * @param[in] ft to search in.
 * @param[in] data to find.
 * @return
 *  - User data matching the data passed in.
 *  - NULL if nothing matched passed data.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
void *fr_trie_find(fr_trie_t *ft, void const *data)
{
  fr_trie_user_t *user = (fr_trie_user_t *) ft;
  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
  uint8_t *key;
  size_t keylen;

  key = &uctx->buffer[0];
  keylen = sizeof(uctx->buffer) * 8;

  if (!uctx->get_key) return NULL;

  if (uctx->get_key(&key, &keylen, data) < 0) return NULL;

  return fr_trie_lookup_by_key(ft, key, keylen);
}

/** Match an element exactly in the trie, returning the data.
 *
 * @param[in] ft to search in.
 * @param[in] data to find.
 * @return
 *  - User data matching the data passed in.
 *  - NULL if nothing matched passed data.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
void *fr_trie_match(fr_trie_t *ft, void const *data)
{
  fr_trie_user_t *user = (fr_trie_user_t *) ft;
  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
  uint8_t *key;
  size_t keylen;

  key = &uctx->buffer[0];
  keylen = sizeof(uctx->buffer) * 8;

  if (!uctx->get_key) return NULL;

  if (uctx->get_key(&key, &keylen, data) < 0) return NULL;

  return fr_trie_match_by_key(ft, key, keylen);
}

/** Insert data into a trie
 *
 * @param[in] ft  to insert data into.
 * @param[in] data  to insert.
 * @return
 *  - true if data was inserted.
 *  - false if data already existed and was not inserted.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
bool fr_trie_insert(fr_trie_t *ft, void const *data)
{
  fr_trie_user_t *user = (fr_trie_user_t *) ft;
  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
  uint8_t *key;
  size_t keylen;

  key = &uctx->buffer[0];
  keylen = sizeof(uctx->buffer) * 8;

  if (!uctx->get_key) return false;

  if (uctx->get_key(&key, &keylen, data) < 0) return false;

  if (fr_trie_insert_by_key(ft, key, keylen, data) < 0) return false;

  return true;
}

/** Replace old data with new data, OR insert if there is no old
 *
 * @param[out] old  data that was replaced.  If this argument
 *      is not NULL, then the old data will not
 *      be freed, even if a free function is
 *      configured.
 * @param[in] ft  to insert data into.
 * @param[in] data  to replace.
 * @return
 *  - 1 if data was replaced.
 *      - 0 if data was inserted.
 *      - -1 if we failed to replace data
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
int fr_trie_replace(void **old, fr_trie_t *ft, void const *data)
{
  fr_trie_user_t  *user = (fr_trie_user_t *) ft;
  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
  uint8_t   *key;
  size_t    keylen;
  void    *found;

  key = &uctx->buffer[0];
  keylen = sizeof(uctx->buffer) * 8;

  if (!uctx->get_key) return -1;

  if (uctx->get_key(&key, &keylen, data) < 0) return -1;

  found = trie_key_match(ft, key, 0, keylen, true); /* do exact match */
  if (found) {
    if (old) *old = found;
    if (fr_trie_remove_by_key(ft, key, keylen) != found) return -1;
  } else {
    if (old) *old = NULL;
  }

  /*
   *  Insert the new key.
   */
  if (fr_trie_insert_by_key(ft, key, keylen, data) < 0) return -1;

  return found ? 1 : 0;
}

/** Remove an entry, without freeing the data
 *
 * @param[in] ft  to remove data from.
 * @param[in] data  to remove.
 * @return
 *      - The user data we removed.
 *  - NULL if we couldn't find any matching data.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
void *fr_trie_remove(fr_trie_t *ft, void const *data)
{
  fr_trie_user_t *user = (fr_trie_user_t *) ft;
  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
  uint8_t *key;
  size_t keylen;

  key = &uctx->buffer[0];
  keylen = sizeof(uctx->buffer) * 8;

  if (!uctx->get_key) return NULL;

  if (uctx->get_key(&key, &keylen, data) < 0) return NULL;

  return fr_trie_remove_by_key(ft, key, keylen);
}

/** Remove node and free data (if a free function was specified)
 *
 * @param[in] ft  to remove data from.
 * @param[in] data  to remove/free.
 * @return
 *  - true if we removed data.
 *      - false if we couldn't find any matching data.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
bool fr_trie_delete(fr_trie_t *ft, void const *data)
{
  fr_trie_user_t *user = (fr_trie_user_t *) ft;
  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
  uint8_t *key;
  size_t keylen;
  void *found;

  key = &uctx->buffer[0];
  keylen = sizeof(uctx->buffer) * 8;

  if (!uctx->get_key) return false;

  if (uctx->get_key(&key, &keylen, data) < 0) return false;

  found = fr_trie_remove_by_key(ft, key, keylen);
  if (!found) return false;

  if (!uctx->free_data) return true;

  uctx->free_data(found);
  return true;
}

/** Return how many nodes there are in a trie
 *
 * @param[in] ft  to return node count for.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
unsigned int fr_trie_num_elements(UNUSED fr_trie_t *ft)
{
  return 0;
}

#ifdef TESTING
static bool print_lineno = false;

typedef struct {
  char  *start;
  char  *buffer;
  size_t  buflen;
} trie_sprint_ctx_t;


/**  Print the strings accepted by a trie to one line
 */
static int _trie_sprint_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, bool more)
{
  int bytes, len;
  trie_sprint_ctx_t *ctx;
  fr_trie_user_t *user;

  ctx = cb->ctx;

  if (!trie) {
    len = snprintf(ctx->buffer, ctx->buflen, "{}");
    goto done;
  }

  if (trie->type != FR_TRIE_USER) return 0;

  bytes = BYTES(keylen);
  user = (fr_trie_user_t *) trie;

  if (!user->trie && !more) {
    len = snprintf(ctx->buffer, ctx->buflen, "%.*s=%s",
        bytes, cb->start, (char const *) user->data);
  } else {
    len = snprintf(ctx->buffer, ctx->buflen, "%.*s=%s,",
             bytes, cb->start, (char const *) user->data);
  }

done:
  ctx->buffer += len;
  ctx->buflen -= len;

  return 0;
}


static void trie_sprint(fr_trie_t *trie, uint8_t const *key, int start_bit, UNUSED int lineno)
{
  fr_trie_callback_t my_cb;
  trie_sprint_ctx_t my_sprint;
  uint8_t buffer[MAX_KEY_BYTES + 1];
  char out[8192];

  /*
   *  Initialize the buffer
   */
  memset(buffer, 0, sizeof(buffer));
  memset(out, 0, sizeof(out));
  if (key) {
    memcpy(buffer, key, BYTES(start_bit) + 1);
  }

  /*
   *  Where the output data goes.
   */
  my_sprint.start = out;
  my_sprint.buffer = out;
  my_sprint.buflen = sizeof(out);

  /*
   *  Where the keys are built.
   */
  my_cb.start = buffer;
  my_cb.end = buffer + sizeof(buffer);
  my_cb.callback = _trie_sprint_cb;
  my_cb.user_callback = NULL;
  my_cb.ctx = &my_sprint;

  /*
   *  Call the internal walk function to do the work.
   */
  (void) trie_key_walk(trie, &my_cb, start_bit, false);

  MPRINT3("%.*s%s at %d\n", start_bit, spaces, out, lineno);
}


/**  Parse a string into bits + key
 *
 *  The format is one of:
 *
 *  - string such as "abcdef"
 *  - string prefixed with a bit length, {4}a
 */
static int arg2key(char *arg, char **key, int *length)
{
  char *p;
  int bits, size;

  if (*arg != '{') {
    *key = arg;
    *length = BITSOF(strlen(arg));
    return 0;
  }

  p = strchr(arg, '}');
  if (!p) {
    MPRINT("Failed to find end '}' for {bits}\n");
    return -1;
  }

  bits = BITSOF(strlen(p + 1));
  if (!bits) {
    MPRINT("No key found in in '%s'\n", arg);
    return -1;
  }

  size = atoi(arg + 1); /* ignore end character... */
  if (size > bits) {
    MPRINT("Length '%d' is longer than bits in key %s",
      size, p + 1);
  }

  *key = p + 1;
  *length = size;

  return 0;
}

/**  Our TALLOC_CTX for the data we put into the trie.
 *
 *  Most people don't need to do this, they can just insert their own
 *  data.
 */
static void *data_ctx = NULL;

/**  Insert a key + data into a trie.
 *
 */
static int command_insert(fr_trie_t *ft, UNUSED int argc, char **argv, UNUSED char *out, UNUSED size_t outlen)
{
  int bits;
  void *data;
  char *key;

  if (arg2key(argv[0], &key, &bits) < 0) {
    return -1;
  }

  /*
   *  This has to stick around in between command
   *  invocations.
   */
  data = talloc_strdup(data_ctx, argv[1]);
  if (!data) {
    MPRINT("OOM\n");
    return -1;
  }

  if (fr_trie_insert_by_key(ft, key, bits, data) < 0) {
    MPRINT("Failed inserting key %s=%s - %s\n", key, argv[1], fr_strerror());
    return -1;
  }

  return 0;
}

/**  Verify a trie recursively
 *
 *  For sanity reasons, this command runs but doesn't do anything if
 *  the code is built with no trie verification.
 */
static int command_verify(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen)
{
  fr_cond_assert(ft != NULL);

  /*
   *  The top-level node may have a NULL talloc ctx, which
   *  is OK.  So we skip that.
   */
  if (ft->type != FR_TRIE_USER) {
    fprintf(stderr, "Verify failed: trie is malformed\n");
    return -1;
  }

  if (trie_verify(ft->trie) < 0) {
    fprintf(stderr, "Verify failed: %s\n", fr_strerror());
    return -1;
  }

  return 0;
}

/** Print the keys accepted by a trie
 *
 *  The strings are printed to stdout.
 *
 *  @todo - allow printing to a file.
 */
static int command_keys(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen)
{
  fr_trie_callback_t my_cb;

  my_cb.start = (uint8_t *) out;
  my_cb.end = (uint8_t *) (out + outlen);
  my_cb.callback = _trie_print_cb;
  my_cb.user_callback = NULL;
  my_cb.ctx = stdout;

  /*
   *  Call the internal walk function to do the work.
   */
  return trie_key_walk(ft->trie, &my_cb, 0, false);
}


/** Dump the trie in internal format
 *
 *  The information is printed to stdout.
 *
 *  For sanity reasons, this command runs but doesn't do anything if
 *  the code is built with no trie dumping.
 *
 *  @todo - allow printing to a file.
 */
static int command_dump(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen)
{
  fr_trie_callback_t my_cb;

  my_cb.start = (uint8_t *) out;
  my_cb.end = (uint8_t *) (out + outlen);
  my_cb.callback = _trie_dump_cb;
  my_cb.user_callback = NULL;
  my_cb.ctx = stdout;

  /*
   *  Call the internal walk function to do the work.
   */
  return trie_key_walk(ft->trie, &my_cb, 0, false);
}


/**  Clear the entire trie without caring what's in it.
 *
 */
static int command_clear(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen)
{
  if (!ft->trie) return 0;

  trie_free(ft->trie);
  ft->trie = NULL;

  /*
   *  Clean up our internal data ctx, too.
   */
  talloc_free(data_ctx);
  data_ctx = talloc_init_const("data_ctx");

  return 0;
}


/**  Turn on line number debugging.
 *
 *  @todo - add general "debug" functionality.
 */
static int command_lineno(UNUSED fr_trie_t *ft, UNUSED int argc, char **argv, UNUSED char *out, UNUSED size_t outlen)
{
  if (strcmp(argv[0], "true") == 0) {
    print_lineno = true;
  } else {
    print_lineno = false;
  }

  return 0;
}


/**  Match an exact key + length
 *
 *  Normally, the "lookup" returns the longest prefix match, so that
 *  *long* key lookups can return *short* matches.
 *
 *  In some cases, we want to know if an exact key is in the trie.
 *  For those cases, we use this function.
 */
static int command_match(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
{
  int bits;
  void *answer;
  char *key;

  if (arg2key(argv[0], &key, &bits) < 0) {
    return -1;
  }

  answer = trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true);
  if (!answer) {
    strlcpy(out, "{}", outlen);
    return 0;
  }

  strlcpy(out, answer, outlen);

  return 0;
}


/**  Look up a key and return user ctx data.
 *
 *  This is done by longest prefix match, not exact match.
 */
static int command_lookup(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
{
  int bits;
  void *answer;
  char *key;

  if (arg2key(argv[0], &key, &bits) < 0) {
    return -1;
  }

  answer = fr_trie_lookup_by_key(ft, key, bits);
  if (!answer) {
    strlcpy(out, "{}", outlen);
    return 0;
  }

  strlcpy(out, answer, outlen);

  return 0;
}


/**  Remove a key from the trie.
 *
 *  The key has to match exactly.
 */
static int command_remove(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
{
  int bits;
  void *answer;
  char *key;

  if (arg2key(argv[0], &key, &bits) < 0) {
    return -1;
  }

  answer = fr_trie_remove_by_key(ft, key, bits);
  if (!answer) {
    MPRINT("Could not remove key %s\n", key);
    return -1;
  }

  strlcpy(out, answer, outlen);

  talloc_free(answer);

  /*
   *  We now try to find an exact match.  i.e. we don't want
   *  to find a shorter prefix.
   */
  answer = trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true);
  if (answer) {
    MPRINT("Still in trie after 'remove' for key %s, found data %s\n", key, (char const *) answer);
    return -1;
  }

  return 0;
}


/**  Remove a key from the trie.
 *
 *  Try to remove a key, but don't error if we can't.
 */
static int command_try_to_remove(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
{
  int bits;
  void *answer;
  char *key;

  if (arg2key(argv[0], &key, &bits) < 0) {
    return -1;
  }

  answer = fr_trie_remove_by_key(ft, key, bits);
  if (!answer) {
    strlcpy(out, ".", outlen);
    return 0;
  }

  strlcpy(out, answer, outlen);

  talloc_free(answer);

  /*
   *  We now try to find an exact match.  i.e. we don't want
   *  to find a shorter prefix.
   */
  answer = trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true);
  if (answer) {
    MPRINT("Still in trie after 'remove' for key %s, found data %s\n", key, (char const *) answer);
    return -1;
  }

  return 0;
}


/** Print a trie to a string
 *
 *  The trie is printed one one line.  If the trie contains keys which
 *  are not on a byte boundary, well... too bad.  It gets printed
 *  terribly.
 */
static int command_print(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen)
{
  fr_trie_callback_t my_cb;
  trie_sprint_ctx_t my_sprint;
  uint8_t buffer[MAX_KEY_BYTES + 1];

  /*
   *  Where the output data goes.
   */
  my_sprint.start = out;
  my_sprint.buffer = out;
  my_sprint.buflen = outlen;

  /*
   *  Where the keys are built.
   */
  my_cb.start = buffer;
  my_cb.end = buffer + sizeof(buffer);
  my_cb.callback = _trie_sprint_cb;
  my_cb.user_callback = NULL;
  my_cb.ctx = &my_sprint;

  memset(buffer, 0, sizeof(buffer));

  /*
   *  Call the internal walk function to do the work.
   */
  return trie_key_walk(ft->trie, &my_cb, 0, false);
}


/**  Do insert / lookup / remove all at once.
 *
 *  Sometimes it's more useful to do insert / lookup / remove for
 *  simple keys.
 */
static int command_path(fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen)
{
  void *data;
  void *answer;

  data = talloc_strdup(ft, argv[1]); /* has to be malloc'd data, sorry */
  if (!data) {
    MPRINT("OOM\n");
    return -1;
  }

  if (fr_trie_insert_by_key(ft, argv[0], BITSOF(strlen(argv[0])), data) < 0) {
    MPRINT("Could not insert key %s=%s - %s\n", argv[0], argv[1], fr_strerror());
    return -1;
  }

  answer = fr_trie_lookup_by_key(ft, argv[0], BITSOF(strlen(argv[0])));
  if (!answer) {
    MPRINT("Could not look up key %s\n", argv[0]);
    return -1;
  }

  if (answer != data) {
    MPRINT("Expected to find %s, got %s\n", argv[1], (char const *) answer);
    return -1;
  }

  /*
   *  Call the command 'print' to print out the key.
   */
  (void) command_print(ft, argc, argv, out, outlen);

  answer = fr_trie_remove_by_key(ft, (uint8_t const *) argv[0], BITSOF(strlen(argv[0])));
  if (!answer) {
    MPRINT("Could not remove key %s\n", argv[0]);
    return -1;
  }

  if (answer != data) {
    MPRINT("Expected to remove %s, got %s\n", argv[1], (char const *) answer);
    return -1;
  }

  talloc_free(answer);

  return 0;
}


/**  Return the longest common prefix of two bit strings.
 *
 */
static int command_lcp(UNUSED fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen)
{
  int lcp;
  int keylen1, keylen2;
  int start_bit;
  uint8_t const *key1, *key2;

  if (argc == 2) {
    key1 = (uint8_t const *) argv[0];
    keylen1 = BITSOF(strlen(argv[0]));

    key2 = (uint8_t const *) argv[1];
    keylen2 = BITSOF(strlen(argv[1]));
    start_bit = 0;

  } else if (argc == 5) {
    key1 = (uint8_t const *) argv[0];
    keylen1 = atoi(argv[1]);
    if ((keylen1 < 0) || (keylen1 > (int) BITSOF(strlen(argv[0])))) {
      MPRINT("length of key1 %s is larger than string length %ld\n",
        argv[1], BITSOF(strlen(argv[0])));
      return -1;
    }

    key2 = (uint8_t const *) argv[2];
    keylen2 = atoi(argv[3]);
    if ((keylen2 < 0) || (keylen2 > (int) BITSOF(strlen(argv[2])))) {
      MPRINT("length of key2 %s is larger than string length %ld\n",
        argv[3], BITSOF(strlen(argv[2])));
      return -1;
    }

    start_bit = atoi(argv[4]);
    if ((start_bit < 0) || (start_bit > 7)) {
      MPRINT("start_bit has invalid value %s\n", argv[4]);
      return -1;
    }

  } else {
    MPRINT("Invalid number of arguments\n");
    return -1;
  }

  lcp = fr_trie_key_lcp(key1, keylen1, key2, keylen2, start_bit);

  snprintf(out, outlen, "%d", lcp);
  return 0;
}

/** Get chunks from raw data
 *
 */
static int command_chunk(UNUSED fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
{
  int start_bit, num_bits;
  uint16_t chunk;

  start_bit = atoi(argv[1]);
  num_bits = atoi(argv[2]);

  chunk = get_chunk((uint8_t const *) argv[0], start_bit, num_bits);

  snprintf(out, outlen, "%04x", chunk);
  return 0;
}

/**  A function to parse a trie command line.
 *
 */
typedef int (*fr_trie_function_t)(fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen);

/**  Data structure which holds the trie command name, function, etc.
 *
 */
typedef struct {
  char const    *name;
  fr_trie_function_t  function;
  int     min_argc;
  int     max_argc;
  bool      output;
} fr_trie_command_t;


/**  The trie commands for debugging.
 *
 */
static fr_trie_command_t commands[] = {
  { "lcp",  command_lcp,  2, 5, true },
  { "chunk",  command_chunk,  3, 3, true },
  { "path", command_path, 2, 2, true },
  { "insert", command_insert, 2, 2, false },
  { "match",  command_match,  1, 1, true },
  { "lookup", command_lookup, 1, 1, true },
  { "remove", command_remove, 1, 1, true },
  { "-remove",  command_try_to_remove, 1, 1, true },
  { "print",  command_print,  0, 0, true },
  { "dump", command_dump, 0, 0, false },
  { "keys", command_keys, 0, 0, false },
  { "verify", command_verify, 0, 0, false },
  { "lineno", command_lineno, 1, 1, false },
  { "clear",  command_clear,  0, 0, false },
  { .name = NULL }
};

#define MAX_ARGC (16)
int main(int argc, char **argv)
{
  int lineno = 0;
  int ret = 0;
  fr_trie_t *ft;
  FILE *fp;
  int my_argc;
  char *my_argv[MAX_ARGC];
  char buffer[8192];
  char output[8192];

  if (argc < 2) {
    fprintf(stderr, "Please specify filename\n");
    fr_exit_now(EXIT_SUCCESS);
  }

  fp = fopen(argv[1], "r");
  if (!fp) {
    fprintf(stderr, "Failed opening %s: %s\n", argv[1], fr_syserror(errno));
    fr_exit_now(1);
  }

  /*
   *  Tell us if we leaked memory.
   */
  talloc_enable_null_tracking();

  data_ctx = talloc_init_const("data_ctx");

  ft = fr_trie_alloc(NULL, NULL, NULL);
  if (!ft) {
    fprintf(stderr, "Failed creating trie\n");
    fr_exit_now(1);
  }

  while (fgets(buffer, sizeof(buffer), fp) != NULL) {
    int i, cmd;
    char *p;

    lineno++;

    /*
     *  Remove comments.
     */
    for (p = buffer; *p != '\0'; p++) {
      if (*p == '#') {
        *p = '\0';
        break;
      }
    }

    /*
     *  Skip leading whitespace.
     */
    p = buffer;
    fr_skip_whitespace(p);

    /*
     *  Skip (now) blank lines.
     */
    if (!*p) continue;

    my_argc = fr_dict_str_to_argv(p, my_argv, MAX_ARGC);

    cmd = -1;
    for (i = 0; commands[i].name != NULL; i++) {
      if (strcmp(my_argv[0], commands[i].name) != 0) continue;

      cmd = i;
      break;
    }

    if (cmd < 0) {
      fprintf(stderr, "Unknown command '%s' at line %d\n",
        my_argv[0], lineno);
      ret = 1;
      break;
    }

    /*
     *  argv[0] is the command.
     *  argv[argc-1] is the output.
     */
    if (((commands[cmd].min_argc + 1 + commands[cmd].output) > my_argc) ||
        ((commands[cmd].max_argc + 1 + commands[cmd].output) < my_argc)) {
      fprintf(stderr, "Invalid number of arguments to %s at line %d.  Expected %d, got %d\n",
        my_argv[0], lineno, commands[cmd].min_argc + 1, my_argc - 1);
      fr_exit_now(1);
    }

    if (print_lineno) {
      printf("%d ", lineno);
      fflush(stdout);
    }

    MPRINT3("[%d] %s\n", lineno, my_argv[0]);
    if (commands[cmd].function(ft, my_argc - 1 - commands[cmd].output, &my_argv[1], output, sizeof(output)) < 0) {
      fprintf(stderr, "Failed running %s at line %d\n",
        my_argv[0], lineno);
      fr_exit_now(1);
    }

    if (!commands[cmd].output) continue;

    if (strcmp(output, my_argv[my_argc - 1]) != 0) {
      fprintf(stderr, "Failed running %s at line %d: Expected '%s' got '%s'\n",
        my_argv[0], lineno, my_argv[my_argc - 1], output);
      fr_exit_now(1);
    }
  }

  fclose(fp);

  trie_free(ft);
  talloc_free(data_ctx);

  talloc_report_full(NULL, stdout); /* Print details of any leaked memory */
  talloc_disable_null_tracking();   /* Cleanup talloc null tracking context */

  return ret;
}
#endif

Coverage Report

Created: 2026-05-11 06:44