trie.c

Go to the documentation of this file.

/*
 *   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: 344a24564536764b47335f1d1158506b1711c981 $")
 
#include <freeradius-devel/util/dict.h>
#include <freeradius-devel/util/misc.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)) - 1);
                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) 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 false;
 
        if (uctx->get_key(&key, &keylen, data) < 0) return false;
 
        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 false;
 
        if (uctx->get_key(&key, &keylen, data) < 0) return false;
 
        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 },
        { NULL, NULL, 0, 0}
};
 
#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