File Coverage

nedtrie.h

Criterion	Covered	Total	%
statement	3	3	100.0
branch	1	2	50.0
condition			n/a
subroutine			n/a
pod			n/a
total	4	5	80.0

/* An in-place binary trie implementation for C and C++ aka. the
ridiculously fast way of indexing stuff. (C) 2010-2012 Niall Douglas.


Boost Software License - Version 1.0 - August 17th, 2003

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/

#include
#include
#include
#include  /* for memset */
#include  /* For INT_MAX */

#ifdef _MSC_VER
/* Disable stupid warnings */
#pragma warning(push)
#pragma warning(disable: 4702) /* unreachable code */
#pragma warning(disable: 4706) /* assignment within conditional expression */
#pragma warning(disable: 4127) /* conditional expression is constant */
#pragma warning(disable: 4133) /* incompatible types */
#endif

/*! \def RESTRICT
\brief Defined to the restrict keyword or equivalent if available */
#ifndef RESTRICT
#if __STDC_VERSION__ >= 199901L		/* C99 or better */
 #define RESTRICT restrict
#else
 #if defined(_MSC_VER) && _MSC_VER>=1400
  #define RESTRICT __restrict
 #endif
 #ifdef __GNUC__
  #define RESTRICT __restrict
 #endif
#endif
#ifndef RESTRICT
 #define RESTRICT
#endif
#endif

/*! \def INLINE
\brief Defined to the inline keyword or equivalent if available */
#ifndef INLINE
#if __STDC_VERSION__ >= 199901L		/* C99 or better */ || defined(__cplusplus)
 #define INLINE inline
#else
 #if defined(_MSC_VER)
  #define INLINE __inline
 #endif
 #ifdef __GNUC__
  #define INLINE __inline
 #endif
#endif
#ifndef INLINE
 #define INLINE
#endif
#endif

/*! \def NOINLINE
\brief Defined to whatever compiler magic inhibits inlining if available */
#ifndef NOINLINE
  #if defined(__GNUC__)
    #define NOINLINE __attribute__ ((noinline))
  #elif defined(_MSC_VER)
    #define NOINLINE __declspec(noinline)
  #else
    #define NOINLINE
  #endif
#endif

/*! \def DEBUGINLINE
\brief Defined to be INLINE when NDEBUG is defined, NOINLINE when DEBUG is defined, unset otherwise.
*/
#ifndef DEBUGINLINE
#ifdef NDEBUG
#define DEBUGINLINE INLINE
#elif defined(DEBUG)
#define DEBUGINLINE NOINLINE
#else
#define DEBUGINLINE
#endif
#endif

/*! \def NEDTRIEUSEMACROS
\brief Define to 1 to force usage of the macro implementation of nedtries. This is always 1 when
compiling in C, but defaults to 0 when compiling in C++ as a template function implementation offers
much more scope to the optimiser and is much easier to debug.
*/
#ifndef NEDTRIEUSEMACROS
#ifdef __cplusplus
#define NEDTRIEUSEMACROS 0
#else
#define NEDTRIEUSEMACROS 1
#endif
#endif

/*! \def NEDTRIEDEBUG
\brief Define to 1 if you wish a full trie validation to be performed every time you modify the trie.
Requires assert() to work, so disables itself if NDEBUG is defined.
*/
#ifndef NEDTRIEDEBUG
#ifdef DEBUG
#define NEDTRIEDEBUG 1
#else
#define NEDTRIEDEBUG 0
#endif
#endif
#ifdef NDEBUG
#undef NEDTRIEDEBUG
#define NEDTRIEDEBUG 0
#endif

/* Define bit scanning intrinsics */
#ifdef _MSC_VER
#include
#endif

#ifdef __cplusplus
#include
#if (defined(_MSC_VER) && _MSC_VER<=1500) || (defined(__GNUC__) && !defined(HAVE_CPP0X))
// Doesn't have std::move<> by default, so define
namespace std
{
  template T &move(T &a) { return a; }
  template T &move(const T &a) { return const_cast(a); }
  template T &forward(A &a) { return a; }
}
#endif
namespace {
#endif
static INLINE unsigned nedtriebitscanr(size_t value)
{
  if(!value) return 0;
#if defined(_MSC_VER) && !defined(__cplusplus_cli)
  {
    unsigned long bitpos;
#if defined(_M_IA64) || defined(_M_X64) || defined(WIN64)
    assert(8==sizeof(size_t));
    _BitScanReverse64(&bitpos, value);
#else
    assert(4==sizeof(size_t));
    _BitScanReverse(&bitpos, value);
#endif
    return (unsigned) bitpos;
  }
#elif defined(__GNUC__)
  return sizeof(value)*CHAR_BIT - 1 - (unsigned) __builtin_clzl(value);
#else
  /* The following code is illegal C, but it almost certainly will work.
  If not use the legal implementation below */
#if !defined(__cplusplus_cli)
	union {
		unsigned asInt[2];
		double asDouble;
	};
	int n;

	asDouble = (double)value + 0.5;
	n = (asInt[0 /*Use 1 if your CPU is big endian!*/] >> 20) - 1023;
#ifdef _MSC_VER
#pragma message(__FILE__ ": WARNING: Make sure you change the line above me if your CPU is big endian!")
#else
#warning Make sure you change the line above me if your CPU is big endian!
#endif
	return (unsigned) n;
#else
#if CHAR_BIT != 8
#error CHAR_BIT is not eight, and therefore this generic bitscan routine will need adjusting!
#endif
  /* This is a generic 32 and 64 bit compatible branch free bitscan right */
  size_t x=value;
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  if(16 < sizeof(x)*CHAR_BIT) x = x | (x >>16);
  if(32 < sizeof(x)*CHAR_BIT) x = x | (x >>32);
  x = ~x;
  x = x - ((x >> 1) & (SIZE_MAX/3));
  x = (x & (SIZE_MAX/15*3)) + ((x >> 2) & (SIZE_MAX/15*3));
  x = ((x + (x >> 4)) & (SIZE_MAX/UCHAR_MAX*15)) * (SIZE_MAX/UCHAR_MAX);
  x = (CHAR_BIT*sizeof(x)-1) - (x >> (CHAR_BIT*(sizeof(x)-1)));
  return (unsigned) x;
#endif
#endif
}

#ifdef __cplusplus
} /* Anonymous namespace */
#endif

/*! \def NEDTRIE_INDEXBINS
\brief Defines the number of top level bit bins to use. The default based on size_t is usually fine.
*/
#define NEDTRIE_INDEXBINS (8*sizeof(void *))
/*! \def NEDTRIE_HEAD
\brief Substitutes the type used to store the head of the trie.
*/
#define NEDTRIE_HEAD2(name, type) \
struct name {                    \
  size_t count;                  \
  type *triebins[NEDTRIE_INDEXBINS]; /* each containing (1<
  int nobbledir;                 \
}
#define NEDTRIE_HEAD(name, type) NEDTRIE_HEAD2(name, struct type)
/*! \def NEDTRIE_ENTRY
\brief Substitutes the type used to store the per-node trie information. Occupies 5*sizeof(size_t).
*/
#define NEDTRIE_ENTRY(type) \
struct {                   \
  struct type *trie_parent;           /* parent element */		\
  struct type *trie_child[2];         /* my children based on whether they are zero or one. */		\
  struct type *trie_prev, *trie_next; /* my siblings of identical key to me. */    \
}
#define NEDTRIE_INITIALIZER(root)
/*! \def NEDTRIE_INIT
\brief Initialises a nedtrie for usage.
*/
#define NEDTRIE_INIT(root) do { memset((root), 0, sizeof(*(root))); } while(0)
/*! \def NEDTRIE_EMPTY
\brief Returns whether a nedtrie is empty.
*/
#define NEDTRIE_EMPTY(head) (!(head)->count)
/*! \def NEDTRIE_COUNT
\brief Returns the number of items in a nedtrie.
*/
#define NEDTRIE_COUNT(head) ((head)->count)

/* As macro instantiated code is a royal PITA to debug and even to see what
the hell is going on, we use a templated implementation when in C++. This
aids future debuggability by keeping the template and macro implementations
side by side and hopefully harmonised. */
#ifdef __cplusplus
namespace nedtries {

  template int trienobblezeros(trietype *)
  {
    return 0;
  }
  template int trienobbleones(trietype *)
  {
    return 1;
  }
  template int trienobbleequally(trietype *head)
  {
    return (head->nobbledir=!head->nobbledir);
  }
/*! \def NEDTRIE_NOBBLEZEROS
\brief A nobble function which preferentially nobbles zeros.
*/
#define NEDTRIE_NOBBLEZEROS(name)   nedtries::trienobblezeros
/*! \def NEDTRIE_NOBBLEONES
\brief A nobble function which preferentially nobbles ones.
*/
#define NEDTRIE_NOBBLEONES(name)    nedtries::trienobbleones
/*! \def NEDTRIE_NOBBLEEQUALLY
\brief A nobble function which alternates between nobbling zeros and ones.
*/
#define NEDTRIE_NOBBLEEQUALLY(name) nedtries::trienobbleequally
#define NEDTRIE_GENERATE_NOBBLES(proto, name, type, field, keyfunct)
#else
#define NEDTRIE_NOBBLEZEROS(name)   name##_nobblezeros
#define NEDTRIE_NOBBLEONES(name)    name##_nobbleones
#define NEDTRIE_NOBBLEEQUALLY(name) name##_nobbleequally
#define NEDTRIE_GENERATE_NOBBLES(proto, name, type, field, keyfunct) \
  static INLINE int name##_nobblezeros(struct name *head) { (void) head; return 0; } \
  static INLINE int name##_nobbleones(struct name *head) { (void) head; return 1; } \
  static INLINE int name##_nobbleequally(struct name *head) { return (head->nobbledir=!head->nobbledir); }
#endif /* __cplusplus */

#ifdef __cplusplus
  template struct TrieLink_t {
    type *trie_parent;	          /* parent element */
    type *trie_child[2];		      /* my children based on whether they are zero or one. */
    type *trie_prev, *trie_next;  /* my siblings of identical key to me. */
  };
  template DEBUGINLINE void triecheckvalidity(trietype *head);
  namespace testtrielinksize {
    struct foo1; struct foo2;
    struct foo1 { NEDTRIE_ENTRY(foo1) link; size_t n; };
    struct foo2 { TrieLink_t link; size_t n; };
    static char test_sizeof_trielink_t_equal[sizeof(foo1)==sizeof(foo2)];
  }

} /* namespace */
#endif

/* GCC recently has started puking if you use operators -> and & in template parameters :( */
#ifdef __GNUC__
#define NEDTRIEFIELDOFFSET2(type, field) __builtin_offsetof(type, field)
#else
#define NEDTRIEFIELDOFFSET2(type, field) ((size_t) &(((type *)0)->field))
#endif
#define NEDTRIEFIELDOFFSET(type, field) NEDTRIEFIELDOFFSET2(struct type, field)

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE void trieinsert(trietype *RESTRICT head, type *RESTRICT r)
  {
    type *RESTRICT node, *RESTRICT childnode;
    TrieLink_t *RESTRICT nodelink, *RESTRICT rlink;
    size_t rkey=keyfunct(r), keybit, nodekey;
    unsigned bitidx;
    int keybitset;

    rlink=(TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    memset(rlink, 0, sizeof(TrieLink_t));
    bitidx=nedtriebitscanr(rkey);
    assert(bitidx
    if(!(node=head->triebins[bitidx]))
    { /* Bottom two bits set indicates a node hanging off of head */
      rlink->trie_parent=(type *RESTRICT)(size_t)(3|(bitidx<<2));
      head->triebins[bitidx]=r;
      goto end;
    }
    /* Avoid variable bit shifts where possible, their performance can suck */
    keybit=(size_t) 1<
    for(;;node=childnode)
    {
      nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      nodekey=keyfunct(node);
      if(nodekey==rkey)
      { /* Insert into ring list */
        rlink->trie_parent=0;
        rlink->trie_prev=node;
        rlink->trie_next=nodelink->trie_next;
        nodelink->trie_next=r;
        if(rlink->trie_next) ((TrieLink_t *RESTRICT)((size_t) rlink->trie_next + fieldoffset))->trie_prev=r;
        break;
      }
      keybit>>=1;
      keybitset=!!(rkey&keybit);
      childnode=nodelink->trie_child[keybitset];
      if(!childnode)
      { /* Insert here */
        rlink->trie_parent=node;
        nodelink->trie_child[keybitset]=r;
        break;
      }
    }
end:
    head->count++;
#if NEDTRIEDEBUG
    triecheckvalidity(head);
#endif
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_INSERT(proto, name, type, field, keyfunct) \
  proto INLINE void name##_NEDTRIE_INSERT(struct name *RESTRICT head, struct type *RESTRICT r) \
  { \
    struct type *RESTRICT node, *RESTRICT childnode; \
    size_t rkey=keyfunct(r), keybit, nodekey; \
    unsigned bitidx; \
    int keybitset; \
\
    memset(&r->field, 0, sizeof(r->field)); \
    bitidx=nedtriebitscanr(rkey); \
    assert(bitidx
    if(!(node=head->triebins[bitidx])) \
    { /* Bottom two bits set indicates a node hanging off of head */ \
      r->field.trie_parent=(struct type *RESTRICT)(size_t)(3|(bitidx<<2)); \
      head->triebins[bitidx]=r; \
      goto end; \
    } \
    /* Avoid variable bit shifts where possible, their performance can suck */ \
    keybit=(size_t) 1<
    for(;;node=childnode) \
    { \
      nodekey=keyfunct(node); \
      if(nodekey==rkey) \
      { /* Insert into ring list */ \
        r->field.trie_parent=0; \
        r->field.trie_prev=node; \
        r->field.trie_next=node->field.trie_next; \
        node->field.trie_next=r; \
        if(r->field.trie_next) r->field.trie_next->field.trie_prev=r; \
        break; \
      } \
      keybit>>=1; \
      keybitset=!!(rkey&keybit); \
      childnode=node->field.trie_child[keybitset]; \
      if(!childnode) \
      { /* Insert here */ \
        r->field.trie_parent=node; \
        node->field.trie_child[keybitset]=r; \
        break; \
      } \
    } \
end: \
    head->count++; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_INSERT(proto, name, type, field, keyfunct) \
  proto INLINE void name##_NEDTRIE_INSERT(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  nedtries::trieinsert(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE void trieremove(trietype *RESTRICT head, type *RESTRICT r)
  {
    type *RESTRICT node, **myaddrinparent=0;
    TrieLink_t *RESTRICT nodelink, *RESTRICT childlink, *RESTRICT rlink;
    unsigned bitidx;

    rlink=(TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    /* Am I a leaf off the tree? */
    if(rlink->trie_prev)
    { /* Remove from linked list */
      assert(!rlink->trie_parent);
      node=rlink->trie_prev;
      nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      nodelink->trie_next=rlink->trie_next;
      if(rlink->trie_next)
      {
        nodelink=(TrieLink_t *RESTRICT)((size_t) rlink->trie_next + fieldoffset);
        nodelink->trie_prev=node;
      }
      goto functexit;
    }
    /* I must therefore be part of the tree */
    assert(rlink->trie_parent);
    assert(!rlink->trie_prev);
    /* Am I at the top of the tree? */
    if(((size_t) rlink->trie_parent & 3)==3)
    { /* Extract my bitidx */
      bitidx=(unsigned)(((size_t) rlink->trie_parent)>>2);
      assert(head->triebins[bitidx]==r);
      /* Set the node addr to be modified */
      myaddrinparent=&head->triebins[bitidx];
    }
    else
    { /* Otherwise I am one of my parent's children */
      node=rlink->trie_parent;
      nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      myaddrinparent=(nodelink->trie_child[0]==r) ? &nodelink->trie_child[0] : &nodelink->trie_child[1];
    }
    assert(*myaddrinparent==r);
    node=0;
    /* Can I replace me with a sibling? */
    if(rlink->trie_next)
    {
      node=rlink->trie_next;
      nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      assert(nodelink->trie_prev==r);
      nodelink->trie_prev=0;
      goto end;
    }
    /* Can I simply remove myself from my parent? */
    if(!rlink->trie_child[0] && !rlink->trie_child[1])
      goto end;
    /* I need someone to replace me in the trie, so simply find any
       grandchild of mine (who has the right bits to be here) which has no children.
    */
    {
      type *RESTRICT *RESTRICT childaddrinparent=myaddrinparent, *RESTRICT *RESTRICT newchildaddrinparent;
      int nobbledir=nobblefunct(head);
      while(*(newchildaddrinparent=&(((TrieLink_t *RESTRICT)((size_t) *childaddrinparent + fieldoffset))->trie_child[nobbledir]))
         || *(newchildaddrinparent=&(((TrieLink_t *RESTRICT)((size_t) *childaddrinparent + fieldoffset))->trie_child[!nobbledir])))
        childaddrinparent=newchildaddrinparent;
      node=*childaddrinparent;
      *childaddrinparent=0;
    }
  end:
    if(node)
    {
      nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      assert(!nodelink->trie_child[0] && !nodelink->trie_child[1]);
      nodelink->trie_parent=rlink->trie_parent;
      nodelink->trie_child[0]=rlink->trie_child[0];
      nodelink->trie_child[1]=rlink->trie_child[1];
      if(nodelink->trie_child[0])
      {
        childlink=(TrieLink_t *RESTRICT)((size_t) nodelink->trie_child[0] + fieldoffset);
        childlink->trie_parent=node;
      }
      if(nodelink->trie_child[1])
      {
        childlink=(TrieLink_t *RESTRICT)((size_t) nodelink->trie_child[1] + fieldoffset);
        childlink->trie_parent=node;
      }
    }
    *myaddrinparent=node;
  functexit:
    head->count--;
#if NEDTRIEDEBUG
    triecheckvalidity(head);
#endif
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_REMOVE(proto, name, type, field, keyfunct, nobblefunct) \
  proto INLINE void name##_NEDTRIE_REMOVE(struct name *RESTRICT head, struct type *RESTRICT r)		\
  { \
    struct type *RESTRICT node, **myaddrinparent=0; \
    unsigned bitidx; \
\
    /* Am I a leaf off the tree? */ \
    if(r->field.trie_prev) \
    { /* Remove from linked list */ \
      assert(!r->field.trie_parent); \
      node=r->field.trie_prev; \
      node->field.trie_next=r->field.trie_next; \
      if(r->field.trie_next) \
      { \
        r->field.trie_next->field.trie_prev=node; \
      } \
      goto functexit; \
    } \
    /* I must therefore be part of the tree */ \
    assert(r->field.trie_parent); \
    assert(!r->field.trie_prev); \
    /* Am I at the top of the tree? */ \
    if(((size_t) r->field.trie_parent & 3)==3) \
    { /* Extract my bitidx */ \
      bitidx=(unsigned)(((size_t) r->field.trie_parent)>>2); \
      assert(head->triebins[bitidx]==r); \
      /* Set the node addr to be modified */ \
      myaddrinparent=&head->triebins[bitidx]; \
    } \
    else \
    { /* Otherwise I am one of my parent's children */ \
      node=r->field.trie_parent; \
      myaddrinparent=(node->field.trie_child[0]==r) ? &node->field.trie_child[0] : &node->field.trie_child[1]; \
    } \
    assert(*myaddrinparent==r); \
    node=0; \
    /* Can I replace me with a sibling? */ \
    if(r->field.trie_next) \
    { \
      node=r->field.trie_next; \
      assert(node->field.trie_prev==r); \
      node->field.trie_prev=0; \
      goto end; \
    } \
    /* Can I simply remove myself from my parent? */ \
    if(!r->field.trie_child[0] && !r->field.trie_child[1]) \
      goto end; \
    /* I need someone to replace me in the trie, so simply find any \
       grandchild of mine (who has the right bits to be here) which has no children. \
    */ \
    { \
      struct type *RESTRICT *RESTRICT childaddrinparent=myaddrinparent, *RESTRICT *RESTRICT newchildaddrinparent; \
      int nobbledir=nobblefunct(head); \
      while(*(newchildaddrinparent=&(*childaddrinparent)->field.trie_child[nobbledir]) \
         || *(newchildaddrinparent=&(*childaddrinparent)->field.trie_child[!nobbledir])) \
        childaddrinparent=newchildaddrinparent; \
      node=*childaddrinparent; \
      *childaddrinparent=0; \
    } \
  end: \
    if(node) \
    { \
      assert(!node->field.trie_child[0] && !node->field.trie_child[1]); \
      node->field.trie_parent=r->field.trie_parent; \
      node->field.trie_child[0]=r->field.trie_child[0]; \
      node->field.trie_child[1]=r->field.trie_child[1]; \
      if(node->field.trie_child[0]) \
      { \
        node->field.trie_child[0]->field.trie_parent=node; \
      } \
      if(node->field.trie_child[1]) \
      { \
        node->field.trie_child[1]->field.trie_parent=node; \
      } \
    } \
    *myaddrinparent=node; \
  functexit: \
    head->count--; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_REMOVE(proto, name, type, field, keyfunct, nobblefunct) \
  proto INLINE void name##_NEDTRIE_REMOVE(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  nedtries::trieremove(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE type *triefind(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node, *RESTRICT childnode;
    const TrieLink_t *RESTRICT nodelink, *RESTRICT rlink;
    size_t rkey=keyfunct(r), keybit, nodekey;
    unsigned bitidx;
    int keybitset;

    if(!head->count) return 0;
    rlink=(const TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    bitidx=nedtriebitscanr(rkey);
    assert(bitidx
    if(!(node=head->triebins[bitidx]))
      return 0;
    /* Avoid variable bit shifts where possible, their performance can suck */
    keybit=(size_t) 1<
    for(;;node=childnode)
    {
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      nodekey=keyfunct(node);
      if(nodekey==rkey)
        goto end;
      keybit>>=1;
      keybitset=!!(rkey&keybit);
      childnode=nodelink->trie_child[keybitset];
      if(!childnode)
        return 0;
    }
    return 0;
  end:
    return nodelink->trie_next ? nodelink->trie_next : (type *) node;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_FIND(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_FIND(struct name *RESTRICT head, struct type *RESTRICT r)		\
  { \
    struct type *RESTRICT node, *RESTRICT childnode; \
    size_t rkey=keyfunct(r), keybit, nodekey; \
    unsigned bitidx; \
    int keybitset; \
\
    if(!head->count) return 0; \
    bitidx=nedtriebitscanr(rkey); \
    assert(bitidx
    if(!(node=head->triebins[bitidx])) \
      return 0; \
    /* Avoid variable bit shifts where possible, their performance can suck */ \
    keybit=(size_t) 1<
    for(;;node=childnode) \
    { \
      nodekey=keyfunct(node); \
      if(nodekey==rkey) \
        goto end; \
      keybit>>=1; \
      keybitset=!!(rkey&keybit); \
      childnode=node->field.trie_child[keybitset]; \
      if(!childnode) \
        return 0; \
    } \
    return 0; \
  end: \
    return node->field.trie_next ? node->field.trie_next : node; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_FIND(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_FIND(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  return nedtries::triefind(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE int trieexactfind(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node;
    const TrieLink_t *RESTRICT nodelink;

    if(!head->count) return 0;
    if(!(node=triefind(head, r))) return 0;
    nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    if(nodelink->trie_prev) node=nodelink->trie_prev;
    do
    {
      if(node==r) return 1;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      node=nodelink->trie_next;
    } while(node);
    return 0;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct) \
  proto INLINE int name##_NEDTRIE_EXACTFIND(struct name *RESTRICT head, struct type *RESTRICT r)		\
  { \
    struct type *RESTRICT node; \
\
    if(!head->count) return 0; \
    if(!(node=name##_NEDTRIE_FIND(head, r))) return 0; \
    if(node->field.trie_prev) node=node->field.trie_prev; \
    do \
    { \
      if(node==r) return 1; \
      node=node->field.trie_next; \
    } while(node); \
    return 0; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct) \
  proto INLINE int name##_NEDTRIE_EXACTFIND(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  return nedtries::trieexactfind(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE type *trieCfind(const trietype *RESTRICT head, const type *RESTRICT r, int rounds)
  {
    const type *RESTRICT node=0, *RESTRICT childnode, *RESTRICT ret=0;
    const TrieLink_t *RESTRICT nodelink, *RESTRICT rlink;
    size_t rkey=keyfunct(r), keybit, nodekey;
    unsigned binbitidx;
    int keybitset;

    if(!head->count) return 0;
    rlink=(const TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    binbitidx=nedtriebitscanr(rkey);
    assert(binbitidx
    do
    {
      size_t retkey=(size_t)-1;
      unsigned bitidx;
      /* Keeping raising the bin until we find a larger key */
      while(binbitidxtriebins[binbitidx]))
        binbitidx++;
      if(binbitidx>=NEDTRIE_INDEXBINS)
        return 0;
      bitidx=binbitidx;
      /* Avoid variable bit shifts where possible, their performance can suck */
      keybit=(size_t) 1<
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      nodekey=keyfunct(node);
      /* If nodekey is a closer fit to search key, mark as best result so far */
      if(nodekey>=rkey && nodekey-rkey
      {
        ret=node;
        retkey=nodekey-rkey;
      }
      if(rounds--<=0 && ret) return (type *) ret;
      for(;;node=childnode)
      {
        nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
        /* If a child is a closer fit to search key, mark as best result so far */
        if(nodelink->trie_child[0])
        {
          nodekey=keyfunct(nodelink->trie_child[0]);
          if(nodekey>=rkey && nodekey-rkey
          {
            ret=nodelink->trie_child[0];
            retkey=nodekey-rkey;
          }
        }
        if(nodelink->trie_child[1])
        {
          nodekey=keyfunct(nodelink->trie_child[1]);
          if(nodekey>=rkey && nodekey-rkey
          {
            ret=nodelink->trie_child[1];
            retkey=nodekey-rkey;
          }
        }
        if(rounds--<=0 && ret) return (type *) ret;
        /* Which child branch should we check? */
        keybit>>=1;
        keybitset=!!(rkey&keybit);
        childnode=nodelink->trie_child[keybitset];
        /* If no child and we were checking lowest, check highest */
        if(!childnode && !keybitset)
          childnode=nodelink->trie_child[1];
        if(!childnode) break;
      }
      if(!ret)
      { /* If we didn't find any node bigger than rkey, bump up a bin
           and look for the smallest possible key in that */
        binbitidx++;
        /* From now on, always match lowest */
        retkey+=rkey;
        rkey=0;
        continue;
      }
    } while(!ret);
    nodelink=(const TrieLink_t *RESTRICT)((size_t) ret + fieldoffset);
    return nodelink->trie_next ? nodelink->trie_next : (type *) ret;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_CFIND(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_CFIND(struct name *RESTRICT head, struct type *RESTRICT r, int rounds)		\
  { \
    struct type *RESTRICT node=0, *RESTRICT childnode, *RESTRICT ret=0; \
    size_t rkey=keyfunct(r), keybit, nodekey; \
    unsigned binbitidx; \
    int keybitset; \
 \
    if(!head->count) return 0; \
    binbitidx=nedtriebitscanr(rkey); \
    assert(binbitidx
    do \
    { \
      size_t retkey=(size_t)-1; \
      unsigned bitidx; \
      /* Keeping raising the bin until we find a larger key */ \
      while(binbitidxtriebins[binbitidx])) \
        binbitidx++; \
      if(binbitidx>=NEDTRIE_INDEXBINS) \
        return 0; \
      bitidx=binbitidx; \
      /* Avoid variable bit shifts where possible, their performance can suck */ \
      keybit=(size_t) 1<
      nodekey=keyfunct(node); \
      /* If nodekey is a closer fit to search key, mark as best result so far */ \
      if(nodekey>=rkey && nodekey-rkey
      { \
        ret=node; \
        retkey=nodekey-rkey; \
      } \
      if(rounds--<=0 && ret) return ret; \
      for(;;node=childnode) \
      { \
        /* If a child is a closer fit to search key, mark as best result so far */ \
        if(node->field.trie_child[0]) \
        { \
          nodekey=keyfunct(node->field.trie_child[0]); \
          if(nodekey>=rkey && nodekey-rkey
          { \
            ret=node->field.trie_child[0]; \
            retkey=nodekey-rkey; \
          } \
        } \
        if(node->field.trie_child[1]) \
        { \
          nodekey=keyfunct(node->field.trie_child[1]); \
          if(nodekey>=rkey && nodekey-rkey
          { \
            ret=node->field.trie_child[1]; \
            retkey=nodekey-rkey; \
          } \
        } \
        if(rounds--<=0 && ret) return ret; \
        /* Which child branch should we check? */ \
        keybit>>=1; \
        keybitset=!!(rkey&keybit); \
        childnode=node->field.trie_child[keybitset]; \
        /* If no child and we were checking lowest, check highest */ \
        if(!childnode && !keybitset) \
          childnode=node->field.trie_child[1]; \
        if(!childnode) break; \
      } \
      if(!ret) \
      { /* If we didn't find any node bigger than rkey, bump up a bin \
           and look for the smallest possible key in that */ \
        binbitidx++; \
        /* From now on, always match lowest */ \
        retkey+=rkey; \
        rkey=0; \
        continue; \
      } \
    } while(!ret); \
    return ret->field.trie_next ? ret->field.trie_next : ret; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_CFIND(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_CFIND(struct name *RESTRICT head, struct type *RESTRICT r, int rounds)		\
{ \
  return nedtries::trieCfind(head, r, rounds); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE type *trieminmax(const trietype *RESTRICT head, const unsigned dir)
  {
    const type *RESTRICT node=0, *RESTRICT child;
    const TrieLink_t *RESTRICT nodelink;
    unsigned bitidx;
    if(!head->count) return 0;
    if(!dir)
    { /* He wants min */
      for(bitidx=0; bitidxtriebins[bitidx]); bitidx++);
      assert(node);
      return (type *) node;
    }
    /* He wants max */
    for(bitidx=NEDTRIE_INDEXBINS-1; bitidxtriebins[bitidx]); bitidx--);
    assert(node);
    nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    while((child=nodelink->trie_child[1] ? nodelink->trie_child[1] : nodelink->trie_child[0]))
    {
      node=child;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    }
    /* Now go to end leaf */
    while(nodelink->trie_next)
    {
      node=nodelink->trie_next;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    }
    return (type *) node;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_MINMAX(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_MINMAX(struct name *RESTRICT head, const unsigned dir)		\
  { \
    struct type *RESTRICT node=0, *RESTRICT child; \
    unsigned bitidx; \
    if(!head->count) return 0; \
    if(!dir) \
    { /* He wants min */ \
      for(bitidx=0; bitidxtriebins[bitidx]); bitidx++); \
      assert(node); \
      return node; \
    } \
    /* He wants max */ \
    for(bitidx=NEDTRIE_INDEXBINS-1; bitidxtriebins[bitidx]); bitidx--); \
    assert(node); \
    while((child=node->field.trie_child[1] ? node->field.trie_child[1] : node->field.trie_child[0])) \
    { \
      node=child; \
    } \
    /* Now go to end leaf */ \
    while(node->field.trie_next) \
    { \
      node=node->field.trie_next; \
    } \
    return node; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_MINMAX(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_MINMAX(struct name *RESTRICT head, unsigned dir)		\
{ \
  return nedtries::trieminmax(head, dir); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE type *triebranchprev(const type *RESTRICT r, const TrieLink_t *RESTRICT *rlinkaddr)
  {
    const type *RESTRICT node=0, *RESTRICT child;
    const TrieLink_t *RESTRICT nodelink, *RESTRICT rlink;

    rlink=(TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    /* Am I a leaf off the tree? */
    if(rlink->trie_prev)
    {
      assert(!rlink->trie_parent);
      return rlink->trie_prev;
    }
    /* Trace up my parents to prev branch */
    while(((size_t) rlink->trie_parent & 3)!=3)
    {
      node=rlink->trie_parent;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      /* If I was on child[1] and there is a child[0], go to bottom of child[0] */
      if(nodelink->trie_child[1]==r && nodelink->trie_child[0])
      {
        node=nodelink->trie_child[0];
        nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
        /* Follow child[1] preferentially downwards */
        while((child=nodelink->trie_child[1] ? nodelink->trie_child[1] : nodelink->trie_child[0]))
        {
          node=child;
          nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
        }
      }
      /* If I was already on child[0] or there are no more children, return this node */
      /* Now go to end leaf */
      while(nodelink->trie_next)
      {
        node=nodelink->trie_next;
        nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      }
      return (type *) node;
    }
    /* I have reached the top of my trie, no more on this branch */
    if(rlinkaddr) *rlinkaddr=rlink;
    return 0;
  }

  template DEBUGINLINE type *trieprev(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node=0, *RESTRICT child;
    const TrieLink_t *RESTRICT nodelink, *RESTRICT rlink=0;
    unsigned bitidx;

    if((node=triebranchprev(r, &rlink)) || !rlink) return (type *) node;
    /* I have reached the top of my trie, so on to prev bin */
    bitidx=(unsigned)(((size_t) rlink->trie_parent)>>2);
    assert(head->triebins[bitidx]==r);
    for(bitidx--; bitidxtriebins[bitidx]); bitidx--);
    if(bitidx>=NEDTRIE_INDEXBINS) return 0;
    nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    /* Follow child[1] preferentially downwards */
    while((child=nodelink->trie_child[1] ? nodelink->trie_child[1] : nodelink->trie_child[0]))
    {
      node=child;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    }
    /* Now go to end leaf */
    while(nodelink->trie_next)
    {
      node=nodelink->trie_next;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    }
    return (type *) node;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_PREV(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_BRANCHPREV(struct type *RESTRICT *RESTRICT r)		\
  { \
    struct type *RESTRICT node=0, *RESTRICT child; \
\
    /* Am I a leaf off the tree? */ \
    if((*r)->field.trie_prev) \
    { \
      assert(!(*r)->field.trie_parent); \
      return (*r)->field.trie_prev; \
    } \
    /* Trace up my parents to prev branch */ \
    while(((size_t) (*r)->field.trie_parent & 3)!=3) \
    { \
      node=(*r)->field.trie_parent; \
      /* If I was on child[1] and there is a child[0], go to bottom of child[0] */ \
      if(node->field.trie_child[1]==(*r) && node->field.trie_child[0]) \
      { \
        node=node->field.trie_child[0]; \
        /* Follow child[1] preferentially downwards */ \
        while((child=node->field.trie_child[1] ? node->field.trie_child[1] : node->field.trie_child[0])) \
        { \
          node=child; \
        } \
      } \
      /* If I was already on child[0] or there are no more children, return this node */ \
      /* Now go to end leaf */ \
      while(node->field.trie_next) \
      { \
        node=node->field.trie_next; \
      } \
      return node; \
    } \
    /* I have reached the top of my trie, no more on this branch */ \
    return 0; \
  } \
  proto INLINE struct type * name##_NEDTRIE_PREV(struct name *RESTRICT head, struct type *RESTRICT r)		\
  { \
    struct type *RESTRICT node=0, *RESTRICT child; \
    unsigned bitidx; \
\
    if((node=name##_NEDTRIE_BRANCHPREV(&r))) return node; \
    /* I have reached the top of my trie, so on to prev bin */ \
    bitidx=(unsigned)(((size_t) r->field.trie_parent)>>2); \
    assert(head->triebins[bitidx]==r); \
    for(bitidx--; bitidxtriebins[bitidx]); bitidx--); \
    if(bitidx>=NEDTRIE_INDEXBINS) return 0; \
    /* Follow child[1] preferentially downwards */ \
    while((child=node->field.trie_child[1] ? node->field.trie_child[1] : node->field.trie_child[0])) \
    { \
      node=child; \
    } \
    /* Now go to end leaf */ \
    while(node->field.trie_next) \
    { \
      node=node->field.trie_next; \
    } \
    return node; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_PREV(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_PREV(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  return nedtries::trieprev(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE type *triebranchnext(const type *RESTRICT r, const TrieLink_t *RESTRICT *rlinkaddr)
  {
    const type *RESTRICT node;
    const TrieLink_t *RESTRICT nodelink, *RESTRICT rlink;

    rlink=(const TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    /* Am I a leaf off the tree? */
    if(rlink->trie_next)
      return rlink->trie_next;
    /* If I am the end leaf off a tree, put me back at my tree node */
    while(!rlink->trie_parent)
    {
      r=rlink->trie_prev;
      rlink=(const TrieLink_t *RESTRICT)((size_t) r + fieldoffset);
    }
    /* Follow my children, preferring child[0] */
    if((node=rlink->trie_child[0] ? rlink->trie_child[0] : rlink->trie_child[1]))
    {
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      assert(nodelink->trie_parent==r);
      return (type *) node;
    }
    /* Trace up my parents to next branch */
    while(((size_t) rlink->trie_parent & 3)!=3)
    {
      node=rlink->trie_parent;
      nodelink=(const TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
      if(nodelink->trie_child[0]==r && nodelink->trie_child[1])
      {
        return nodelink->trie_child[1];
      }
      r=node;
      rlink=nodelink;
    }
    /* I have reached the top of my trie, no more on this branch */
    if(rlinkaddr) *rlinkaddr=rlink;
    return 0;
  }

  template DEBUGINLINE type *trienext(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node;
    const TrieLink_t *RESTRICT rlink=0;
    unsigned bitidx;

    if((node=triebranchnext(r, &rlink))) return (type *) node;
    /* I have reached the top of my trie, so on to next bin */
    bitidx=(unsigned)(((size_t) rlink->trie_parent)>>2);
    for(bitidx++; bitidxtriebins[bitidx]); bitidx++);
    if(bitidx>=NEDTRIE_INDEXBINS) return 0;
    return (type *) node;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_NEXT(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_BRANCHNEXT(struct type *RESTRICT *RESTRICT r)		\
  { \
    struct type *RESTRICT node; \
\
    /* Am I a leaf off the tree? */ \
    if((*r)->field.trie_next) \
      return (*r)->field.trie_next; \
    /* If I am the end leaf off a tree, put me back at my tree node */ \
    while(!(*r)->field.trie_parent) \
    { \
      (*r)=(*r)->field.trie_prev; \
    } \
    /* Follow my children, preferring child[0] */ \
    if((node=(*r)->field.trie_child[0] ? (*r)->field.trie_child[0] : (*r)->field.trie_child[1])) \
    { \
      assert(node->field.trie_parent==(*r)); \
      return node; \
    } \
    /* Trace up my parents to next branch */ \
    while(((size_t) (*r)->field.trie_parent & 3)!=3) \
    { \
      node=(*r)->field.trie_parent; \
      if(node->field.trie_child[0]==(*r) && node->field.trie_child[1]) \
      { \
        return node->field.trie_child[1]; \
      } \
      (*r)=node; \
    } \
    return 0; \
  } \
  proto INLINE struct type * name##_NEDTRIE_NEXT(struct name *RESTRICT head, struct type *RESTRICT r)		\
  { \
    struct type *RESTRICT node; \
    unsigned bitidx; \
\
    if((node=name##_NEDTRIE_BRANCHNEXT(&r))) return node; \
    /* I have reached the top of my trie, so on to next bin */ \
    bitidx=(unsigned)(((size_t) r->field.trie_parent)>>2); \
    assert(head->triebins[bitidx]==r); \
    for(bitidx++; bitidxtriebins[bitidx]); bitidx++); \
    if(bitidx>=NEDTRIE_INDEXBINS) return 0; \
    return node; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_NEXT(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_NEXT(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  return nedtries::trienext(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template DEBUGINLINE type *trieNfind(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node=0, *RESTRICT ret=trieCfind(head, r, INT_MAX), *RESTRICT stop;
    const TrieLink_t *RESTRICT rlink;
    size_t rkey=keyfunct(r), retkey, nodekey;

    if(!ret) return 0;
    if(!(retkey=keyfunct(ret)-rkey)) return (type *) ret;
    /* Cfind basically does a find but if it doesn't find an exact match it early outs
    with the closest result it found during the find. As nodes with children have a key
    which is only guaranteed to be correct under its parent's constraints and has nothing
    to do with its children, there may be a closer key in any of the children of the node
    returned. Hence we iterate the local subbranch, looking for closer fits. */
    rlink=(const TrieLink_t *RESTRICT)((size_t) ret + fieldoffset);
    stop=rlink->trie_parent;
    for(node=triebranchnext(ret, 0); node && node!=stop; node=triebranchnext(node, 0))
    {
      nodekey=keyfunct(node);
      /* If nodekey is a closer fit to search key, mark as best result so far */
      if(nodekey>=rkey && nodekey-rkey
      {
        ret=node;
        retkey=nodekey-rkey;
      }
    }
    return (type *) ret;
  }
}
#endif /* __cplusplus */
#if NEDTRIEUSEMACROS
#define NEDTRIE_GENERATE_NFIND(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_NFIND(struct name *RESTRICT head, struct type *RESTRICT r)		\
  { \
    struct type *RESTRICT node=0, *RESTRICT ret=name##_NEDTRIE_CFIND(head, r, INT_MAX), *RESTRICT stop; \
    size_t rkey=keyfunct(r), retkey, nodekey; \
    \
    if(!ret) return 0; \
    if(!(retkey=keyfunct(ret)-rkey)) return ret; \
    /* Cfind basically does a find but if it doesn't find an exact match it early outs    \
    with the closest result it found during the find. As nodes with children have a key   \
    which is only guaranteed to be correct under its parent's constraints and has nothing \
    to do with its children, there may be a closer key in any of the children of the node \
    returned. Hence we iterate the local subbranch, looking for closer fits. */           \
    stop=r->field.trie_parent; \
    for(node=ret, node=name##_NEDTRIE_BRANCHNEXT(&node); node && node!=stop; node=name##_NEDTRIE_BRANCHNEXT(&node)) \
    { \
      nodekey=keyfunct(node); \
      /* If nodekey is a closer fit to search key, mark as best result so far */ \
      if(nodekey>=rkey && nodekey-rkey
      { \
        ret=node; \
        retkey=nodekey-rkey; \
      } \
    } \
    return ret; \
  }
#else /* NEDTRIEUSEMACROS */
#define NEDTRIE_GENERATE_NFIND(proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_NFIND(struct name *RESTRICT head, struct type *RESTRICT r)		\
{ \
  return nedtries::trieNfind(head, r); \
}
#endif /* NEDTRIEUSEMACROS */


/*! \def NEDTRIE_GENERATE
\brief Substitutes a set of nedtrie implementation function definitions specialised according to type.
*/
#define NEDTRIE_GENERATE(proto, name, type, field, keyfunct, nobblefunct) \
  NEDTRIE_GENERATE_NOBBLES  (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_INSERT   (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_REMOVE   (proto, name, type, field, keyfunct, nobblefunct) \
  NEDTRIE_GENERATE_FIND     (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_CFIND    (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_MINMAX   (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_PREV     (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_NEXT     (proto, name, type, field, keyfunct) \
  NEDTRIE_GENERATE_NFIND    (proto, name, type, field, keyfunct) \
  proto INLINE struct type * name##_NEDTRIE_PREVLEAF(struct type *r) { return (r)->field.trie_prev; } \
  proto INLINE struct type * name##_NEDTRIE_NEXTLEAF(struct type *r) { return (r)->field.trie_next; }

/*! \def NEDTRIE_INSERT
\brief Inserts item y into nedtrie x.
*/
#define NEDTRIE_INSERT(name, x, y)       name##_NEDTRIE_INSERT(x, y)
/*! \def NEDTRIE_REMOVE
\brief Removes item y from nedtrie x.
*/
#define NEDTRIE_REMOVE(name, x, y)       name##_NEDTRIE_REMOVE(x, y)
/*! \def NEDTRIE_FIND
\brief Finds the item with the same key as y in nedtrie x.
*/
#define NEDTRIE_FIND(name, x, y)         name##_NEDTRIE_FIND(x, y)
/*! \def NEDTRIE_EXACTFIND
\brief Returns true if there is an item with the same key and address as y in nedtrie x.
*/
#define NEDTRIE_EXACTFIND(name, x, y)    name##_NEDTRIE_EXACTFIND(x, y)
/*! \def NEDTRIE_CFIND
\brief Performs \em rounds number of attempts to find an item with an equal key to y in nedtrie x, and
if none equal then the closest item with a larger key. Always returns a larger key if there is a larger
key in the trie, if there isn't it returns zero. Think of rounds as how closely you want the find to fit
the requested key, so \c INT_MAX means "as close as possible". Note that Cfind does NOT guarantee that
the item returned is the next largest keyed item, use Nfind for that.
*/
#define NEDTRIE_CFIND(name, x, y, rounds) name##_NEDTRIE_CFIND(x, y, rounds)
/*! \def NEDTRIE_NFIND
\brief Finds an item with an equal key to y in nedtrie x, and if none equal then the item with the next
largest key. If the key is not equal, the returned item is guaranteed to be the next largest keyed item.
*/
#define NEDTRIE_NFIND(name, x, y)        name##_NEDTRIE_NFIND(x, y)
/*! \def NEDTRIE_PREV
\brief Returns the item preceding y in nedtrie x.
*/
#define NEDTRIE_PREV(name, x, y)         name##_NEDTRIE_PREV(x, y)
/*! \def NEDTRIE_NEXT
\brief Returns the item following y in nedtrie x.
*/
#define NEDTRIE_NEXT(name, x, y)         name##_NEDTRIE_NEXT(x, y)
/*! \def NEDTRIE_PREVLEAF
\brief Returns the item with an identical key preceding y in nedtrie x.
*/
#define NEDTRIE_PREVLEAF(name, x)        name##_NEDTRIE_PREVLEAF(x)
/*! \def NEDTRIE_NEXTLEAF
\brief Returns the item with an identical key following y in nedtrie x.
*/
#define NEDTRIE_NEXTLEAF(name, x)        name##_NEDTRIE_NEXTLEAF(x)
/*! \def NEDTRIE_MIN
\brief Returns the lowest item in nedtrie x. This item will approximately have the smallest key.
*/
#define NEDTRIE_MIN(name, x)             name##_NEDTRIE_MINMAX(x, 0)
/*! \def NEDTRIE_MAX
\brief Returns the highest item in nedtrie x. This item will approximately have the biggest key.
*/
#define NEDTRIE_MAX(name, x)             name##_NEDTRIE_MINMAX(x, 1)

/*! \def NEDTRIE_FOREACH
\brief Substitutes a for loop which forward iterates into x all items in nedtrie head. Order of
items is mostly in key order (enough that a bubble sort is efficient).
*/
#define NEDTRIE_FOREACH(x, name, head)          \
	for ((x) = NEDTRIE_MIN(name, head);           \
	     (x) != NULL;                             \
	     (x) = NEDTRIE_NEXT(name, head, x))

/*! \def NEDTRIE_FOREACH_SAFE
\brief Substitutes a for loop which forward iterates into x all items in
nedtrie head and is safe against removal of x. Order of items is mostly
in key order (enough that a bubble sort is efficient).
*/
#define NEDTRIE_FOREACH_SAFE(x, name, head, y)  \
	for ((x) = NEDTRIE_MIN(name, head);           \
	     (x) != NULL && ((y) = NEDTRIE_NEXT(name, head, x), 1); \
	     (x) = (y))

/*! \def NEDTRIE_FOREACH_REVERSE
\brief Substitutes a for loop which reverse iterates into x all items in nedtrie head. Order of
items is mostly inverse to key order (enough that a bubble sort is efficient).
*/
#define NEDTRIE_FOREACH_REVERSE(x, name, head)  \
	for ((x) = NEDTRIE_MAX(name, head);           \
	     (x) != NULL;                             \
	     (x) = NEDTRIE_PREV(name, head, x))

/*! \def NEDTRIE_FOREACH_REVERSE_SAFE
\brief Substitutes a for loop which reverse iterates into x all items in nedtrie head and is
safe against removal of x. Order of items is mostly inverse to key order (enough that a bubble
sort is efficient).
*/
#define NEDTRIE_FOREACH_REVERSE_SAFE(x, name, head, y)  \
	for ((x) = NEDTRIE_MAX(name, head);           \
	     (x) != NULL && ((y) = NEDTRIE_PREV(name, head, x), 1); \
	     (x) = (y))

/*! \def NEDTRIE_HASNODEHEADER
\brief Returns true if this item's node header is active. Useful as a quick check for whether a node is in some trie.
*/
#define NEDTRIE_HASNODEHEADER(treevar, node, link)  ((node)->link.trie_parent || (node)->link.trie_prev)

#ifdef __cplusplus
#include
namespace nedtries {

#ifndef NDEBUG
  typedef struct TrieValidityState_t
  {
    size_t count, smallestkey, largestkey, tops, lefts, rights, leafs;
  } TrieValidityState;

  template DEBUGINLINE
           void triecheckvaliditybranch(trietype *head, type *RESTRICT node, unsigned bitidx, TrieValidityState &state)
  {
    type *RESTRICT child;
    TrieLink_t *RESTRICT nodelink, *RESTRICT childlink;
    size_t nodekey=keyfunct(node);

    if(nodekey
    if(nodekey>state.largestkey) state.largestkey=nodekey;
    nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    assert(nodelink->trie_parent);
    child=nodelink->trie_parent;
    childlink=(TrieLink_t *RESTRICT)((size_t) child + fieldoffset);
    assert(childlink->trie_child[0]==node || childlink->trie_child[1]==node);
    assert(node==childlink->trie_child[!!(nodekey & ((size_t) 1<
    assert(!nodelink->trie_prev);
    while((child=nodelink->trie_next))
    {
      state.leafs++;
      childlink=(TrieLink_t *RESTRICT)((size_t) child + fieldoffset);
      assert(!childlink->trie_parent);
      assert(!childlink->trie_child[0]);
      assert(!childlink->trie_child[1]);
      assert(childlink->trie_prev);
      assert(!childlink->trie_next || child==((TrieLink_t *RESTRICT)((size_t) childlink->trie_next + fieldoffset))->trie_prev);
      nodelink=childlink;
      state.count++;
    }
    nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
    state.count++;
    if(nodelink->trie_child[0])
    {
      state.lefts++;
      triecheckvaliditybranch(head, nodelink->trie_child[0], bitidx-1, state);
    }
    if(nodelink->trie_child[1])
    {
      state.rights++;
      triecheckvaliditybranch(head, nodelink->trie_child[1], bitidx-1, state);
    }
  }
#endif
  template DEBUGINLINE void triecheckvalidity(trietype *head)
  {
#ifndef NDEBUG
    type *RESTRICT node, *RESTRICT child;
    TrieLink_t *RESTRICT nodelink, *RESTRICT childlink;
    unsigned n, bitidx;
    TrieValidityState state={0};
    for(n=0; n
    {
      if((node=head->triebins[n]))
      {
        size_t nodekey=keyfunct(node);
        state.tops++;
        nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
        bitidx=(unsigned)(((size_t) nodelink->trie_parent)>>2);
        assert(bitidx==n);
        assert(head->triebins[bitidx]==node);
        assert(!nodekey || ((((size_t)-1)<
        assert(!nodelink->trie_prev);
        while((child=nodelink->trie_next))
        {
          state.leafs++;
          childlink=(TrieLink_t *RESTRICT)((size_t) child + fieldoffset);
          assert(!childlink->trie_parent);
          assert(!childlink->trie_child[0]);
          assert(!childlink->trie_child[1]);
          assert(childlink->trie_prev);
          assert(!childlink->trie_next || child==((TrieLink_t *RESTRICT)((size_t) childlink->trie_next + fieldoffset))->trie_prev);
          nodelink=childlink;
          state.count++;
        }
        nodelink=(TrieLink_t *RESTRICT)((size_t) node + fieldoffset);
        state.count++;
        if(nodelink->trie_child[0])
        {
          state.lefts++;
          state.smallestkey=(size_t)-1;
          state.largestkey=0;
          triecheckvaliditybranch(head, nodelink->trie_child[0], bitidx-1, state);
          assert(!state.smallestkey || state.smallestkey>=(size_t)1<
          assert(state.largestkey<(size_t)1<<(bitidx+1));
        }
        if(nodelink->trie_child[1])
        {
          state.rights++;
          state.smallestkey=(size_t)-1;
          state.largestkey=0;
          triecheckvaliditybranch(head, nodelink->trie_child[1], bitidx-1, state);
          assert(state.smallestkey>=(size_t)1<
          assert(state.largestkey<(size_t)1<<(bitidx+1));
        }
      }
    }
    assert(state.count==head->count);
    for(state.count=0, node=trieminmax(head, 0); node; (node=trienext(head, node)), state.count++)
#if 0
      printf("%p\n", node)
#endif
      ;
    if(state.count!=head->count)
    {
      assert(state.count==head->count);
    }
#if 0
    printf("\n");
#endif
    for(state.count=0, node=trieminmax(head, 1); node; (node=trieprev(head, node)), state.count++)
#if 0
      printf("%p\n", node)
#endif
      ;
    if(state.count!=head->count)
    {
      assert(state.count==head->count);
    }
#if 0
    printf("\n");
#endif
#if !defined(NDEBUG) && 0
    if(count>50)
      printf("Of count %u, tops %.2lf%%, lefts %.2lf%%, rights %.2lf%%, leafs %.2lf%%\n", count, 100.0*tops/count, 100.0*lefts/count, 100.0*rights/count, 100.0*leafs/count);
#endif
#endif /* !NDEBUG */
  }

#if NEDTRIE_ENABLE_STL_CONTAINERS
  /*! \def HAVE_CPP0XRVALUEREFS
  \ingroup C++
  \brief Enables rvalue references

  Define to enable the usage of rvalue references which enables move semantics and
  other things. Automatically defined if __cplusplus indicates a C++0x compiler,
  otherwise you'll need to set it yourself.
  */
#if __cplusplus > 199711L || (defined(_MSC_VER) && _MSC_VER>=1600) || defined(HAVE_CPP0X) /* Do we have C++0x? */
#undef HAVE_CPP0XRVALUEREFS
#define HAVE_CPP0XRVALUEREFS 1
#undef HAVE_CPP0XTYPETRAITS
#define HAVE_CPP0XTYPETRAITS 1
#endif

/*! \brief The policy namespace in which all nedtries policies live. */
  namespace nedpolicy
  {
    /*! \class nobblezeros
    \brief A policy nobbling zeros
    */
    template class nobblezeros
    {
    protected:
      template static int trie_nobblefunction(trietype *)
      {
        return 0;
      }
    };
    /*! \class nobbleones
    \brief A policy nobbling ones
    */
    template class nobbleones
    {
    protected:
      template static int trie_nobblefunction(trietype *)
      {
        return 1;
      }
    };
    /*! \class nobbleequally
    \brief A policy nobbling zeros and ones equally
    */
    template class nobbleequally
    {
    protected:
      template static int trie_nobblefunction(trietype *head)
      {
        return (head->nobbledir=!head->nobbledir);
      }
    };
  } // namspace
  template NEDTRIE_HEAD2(trie_map_head, type);
  template struct trie_maptype;
  /*! \struct trie_keyfunct
  \ingroup C++
  \brief Calculates the key for a given instance of type

  You only really need to use this if you are using trie_multimap or trie_map without the operator[]
  override. If using with trie_map, make sure you force the use of trie_keyfunct in its template
  parameters as it defaults to an internal thunk type used to indirect access to an embedded key store.

  Specialise this as follows for your type:
  \code
  namespace nedtries {
    template<> struct trie_keyfunct : public std::unary_function
    {
      size_t operator()(const yourtype *RESTRICT v) const
      {
        return v->yourtypekeyvalue;
      }
    };
  }
  \endcode
  */
  template struct trie_keyfunct : public std::unary_function
  {
#ifdef HAVE_CPP0XRVALUEREFS
	  keytype operator()(const type &v) const
	  {
		  static_assert(typeid(type)==typeid(type), "trie_keyfunct has not been specialised for this type");
	  }
#else
  private:
	  keytype operator()(const type &) const;
#endif
  };
  template struct trie_maptype_keyfunct : public std::unary_function
  {
	  template keytype operator()(const maptype &v) const
	  {
	    return v.trie_keyvalue;
	  }
  };
  namespace intern {
    template struct noconstiteratortype : public type { };
    template size_t to_Ckeyfunct(const mapvaluetype *RESTRICT v)
    {
      return keyfunct_()(*v);
    }
  }
  template class nobblepolicy, class stlcontainer,
    class iteratortype, int dir, class mapvaluetype, class constiteratortype=intern::noconstiteratortype > class trie_iterator;
  template,
    class allocator=std::allocator::iterator> >,
    template class nobblepolicy=nedpolicy::nobblezeros,
    class stlcontainer=std::list::iterator>, allocator> > class trie_map;
  template,
    class allocator=std::allocator::iterator> >,
    template class nobblepolicy=nedpolicy::nobblezeros,
    class stlcontainer=std::list::iterator>, allocator> > class trie_multimap;
  /*! \struct trie_maptype
  \ingroup C++
  \brief Encapsulates the nedtrie metadata with the given type

  Note that the nedtrie metadata is kept \em after the typed value - this prevents the nedtrie metadata interfering
  with any special data alignment you might be using from a specialised STL allocator.
  */
  namespace fake {
    template struct trie_maptype
    {
      template friend struct trie_keyfunct;
      template class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
      template class nobblepolicy, class stlcontainer> friend class trie_map;
      template class nobblepolicy, class stlcontainer> friend class trie_multimap;
      typedef keytype trie_key_type;
      typedef type trie_value_type;
      typedef keyfunct trie_keyfunct_type;
      typedef iteratortype trie_iterator_type;
      type trie_value;
      iteratortype trie_iterator;
      TrieLink_t trie_link;
    };
  }
  template struct trie_maptype
  {
  private: // ENSURE the fake type above mirrors this one
    template friend struct trie_keyfunct;
    template class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
    template class nobblepolicy, class stlcontainer> friend class trie_map;
    template class nobblepolicy, class stlcontainer> friend class trie_multimap;
    typedef keytype trie_key_type;
    typedef type trie_value_type;
    typedef keyfunct trie_keyfunct_type;
    typedef iteratortype trie_iterator_type;
    typedef fake::trie_maptype fakemirrorofme_type;
    type trie_value;
    iteratortype trie_iterator;
    TrieLink_t trie_link;
    static const size_t trie_link_offset=NEDTRIEFIELDOFFSET2(fakemirrorofme_type, trie_link);
  public:
    trie_maptype(const type &v) : trie_value(v)
    { // Prevent that memory corruption bug ever happening again
      static char ensure_trie_link_offset_is_bounded[trie_link_offset+sizeof(trie_link)<=sizeof(*this)];
    }
    template trie_maptype(const trie_maptype &o) : trie_value(o.trie_value) { }
#ifdef HAVE_CPP0XRVALUEREFS
    template trie_maptype(trie_maptype &&o) : trie_value(std::move(o.trie_value)) { }
#endif
    //! Silent const lvalue converter for type
    operator const type &() const { return trie_value; }
  };
  namespace fake {
    template struct trie_maptype2
    {
      template friend struct trie_keyfunct;
      template class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
      template class nobblepolicy, class stlcontainer> friend class trie_map;
      template class nobblepolicy, class stlcontainer> friend class trie_multimap;
      template friend struct trie_maptype_keyfunct;
      typedef keytype trie_key_type;
      typedef type trie_value_type;
      typedef trie_maptype_keyfunct trie_keyfunct_type;
      typedef iteratortype trie_iterator_type;
      type trie_value;
      keytype trie_keyvalue; // For when key is overriden using trie_map::operator[]
      iteratortype trie_iterator;
      TrieLink_t trie_link;
    };
  }
  template struct trie_maptype, iteratortype>
  {
  private: // ENSURE the fake type above mirrors this one
    template friend struct trie_keyfunct;
    template class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
    template class nobblepolicy, class stlcontainer> friend class trie_map;
    template class nobblepolicy, class stlcontainer> friend class trie_multimap;
    template friend struct trie_maptype_keyfunct;
    typedef keytype trie_key_type;
    typedef type trie_value_type;
    typedef trie_maptype_keyfunct trie_keyfunct_type;
    typedef iteratortype trie_iterator_type;
    typedef fake::trie_maptype2 fakemirrorofme_type;
    type trie_value;
    keytype trie_keyvalue; // For when key is overriden using trie_map::operator[]
    iteratortype trie_iterator;
    TrieLink_t trie_link;
    static const size_t trie_link_offset=NEDTRIEFIELDOFFSET2(fakemirrorofme_type, trie_link);
  public:
    trie_maptype(const type &v) : trie_value(v)
    { // Prevent that memory corruption bug ever happening again
      static char ensure_trie_link_offset_is_bounded[trie_link_offset+sizeof(trie_link)<=sizeof(*this)];
    }
    template trie_maptype(const trie_maptype, iteratortype_> &o) : trie_value(o.trie_value), trie_keyvalue(o.trie_keyvalue) { }
#ifdef HAVE_CPP0XRVALUEREFS
    template trie_maptype(trie_maptype, iteratortype_> &&o) : trie_value(std::move(o.trie_value)), trie_keyvalue(std::move(o.trie_keyvalue)) { }
#endif
    //! Silent const lvalue converter for type
    operator const type &() const { return trie_value; }
  };

  /*! \class trie_iterator
  \ingroup C++
  \brief Iterator for the trie_map and trie_multimap containers
  */
  template class nobblepolicy, class stlcontainer, class iteratortype, int dir, class mapvaluetype, class constiteratortype> class trie_iterator : protected iteratortype
  {
    trie_map *parent;
  public:
    typedef typename iteratortype::value_type::trie_value_type value_type;
    typedef typename iteratortype::difference_type difference_type;
    typedef typename iteratortype::pointer pointer;
    typedef typename iteratortype::reference reference;
    typedef typename iteratortype::iterator_category iterator_category;

    operator constiteratortype () const { return constiteratortype(parent, static_cast(*this)); }

    trie_iterator() : parent(0) { }
    trie_iterator(const trie_map *parent_, const iteratortype &o) : iteratortype(o), parent(const_cast *>(parent_)) { }
    trie_iterator(const trie_iterator &o) : iteratortype(o), parent(o.parent) { }
#ifdef HAVE_CPP0XRVALUEREFS
    trie_iterator(trie_iterator &&o) : iteratortype(std::move(o)), parent(o.parent) { }
#endif
    trie_iterator &operator=(const trie_iterator &o)
    {
      return *new(this) trie_iterator(o);
    }
#ifdef HAVE_CPP0XRVALUEREFS
    trie_iterator &operator=(trie_iterator &&o)
    {
      return *new(this) trie_iterator(std::move(o));
    }
#endif
    trie_iterator &operator++()
    {
      mapvaluetype *r=dir>0 ?
        trienext, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct >(&parent->triehead, (mapvaluetype *)(&**this)) :
        trieprev, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct >(&parent->triehead, (mapvaluetype *)(&**this));
      if(r)
        new(this) iteratortype((iteratortype &) r->trie_iterator); // type pun safe
      else
        *this=parent->end();
      return *this;
    }
    trie_iterator &operator++(int) { trie_iterator tmp(*this); operator++(); return tmp; }
    trie_iterator &operator--()
    {
      mapvaluetype *r=dir<0 ?
        trienext, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct >(&parent->triehead, (mapvaluetype *)(&**this)) :
        trieprev, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct >(&parent->triehead, (mapvaluetype *)(&**this));
      if(r)
        new(this) iteratortype((iteratortype &) r->trie_iterator);
      else
        *this=parent->end();
      return *this;
    }
    trie_iterator &operator--(int) { trie_iterator tmp(*this); operator--(); return tmp; }
    bool operator==(const trie_iterator &o) const { return static_cast(*this)==static_cast(o); }
    bool operator!=(const trie_iterator &o) const { return static_cast(*this)!=static_cast(o); }
    const mapvaluetype &operator *() const { return (const mapvaluetype &) iteratortype::operator *(); }
    mapvaluetype &operator *() { return (mapvaluetype &) iteratortype::operator *(); }
    const mapvaluetype *operator ->() const { return (const mapvaluetype *) iteratortype::operator->(); }
    mapvaluetype *operator ->() { return (mapvaluetype *) iteratortype::operator->(); }
  };

  namespace intern
  {
      template struct keystore_t { size_t magic; const key_type &key; keystore_t(size_t magic_, const key_type &key_) : magic(magic_), key(key_) { } private: keystore_t &operator=(const keystore_t &); };
      template struct findkeyfunct_t : public std::unary_function
      {
        size_t operator()(const mapvaluetype &v) const
        {
          keystore_t *r=(keystore_t *)(void *)(&v);
	  // NOTE: This line triggers a "conditional jump or move depends on unintialized value(s)" in valgrind if
	  // sizeof(type)
          if(r->magic==*(size_t *)"TRIEFINDKEYSTORE")
            return r->key;
          return keyfunct()(v);
        }
      };
  }

  /*! \class trie_map
  \ingroup C++
  \brief A STL container wrapper using nedtries to map keys to values.

  \note Enable this by defining `NEDTRIE_ENABLE_STL_CONTAINERS`.

  This class can be used to wrap any arbitrary STL container with nedtrie associativity. For example, if you
  had a std::vector<> list of items, you could add nedtrie's fast nearly constant time algorithm for accessing them -
  though one would expect that a std::list<> would be the most common combination. There is no strict reason why
  one could not wrap std::unordered_map<>, though what one would gain is hard to imagine!

  Usage in the simplest sense is like this as the default template parameters use std::list<> as the underlying
  container:
  \code
  trie_map fooMap;
  fooMap[5]=Foo();
  fooMap.erase(fooMap.find(5));
  \endcode

  Unlike a proper STL container implementation, this wrapper is very much a hack in the sense that it's a very quick
  and dirty way of implementing lots of nedtrie based STL containers at once. In this sense it does require its user
  to not be stupid, and to know what they're doing. STL containers go out of their way to enforce correctness - well,
  this wrapper most certainly does not. If you want to blow off your own foot, this implementation won't stop you!

  For example, despite the protected STL container inheritance, all common STL functions are made public so you
  can if you want easily corrupt the internal state. Equally, if you know what you are doing you can pass in the
  wrapper as a const version of its underlying STL container by reintrpret_cast<>-ing it. Despite this, the wrapper
  is fairly typesafe in that its design won't introduce subtle bugs or cause existing code to magically break itself.

  If you would like a more proper bitwise trie STL container class implemented, or would like to be advised on any
  algorithmic problems from which your IT project may be suffering, my consulting company
  href="http://www.nedproductions.biz/">ned Productions Consulting Ltd would be happy to advise. In particular
  I would love to see a full bitwise trie implementation submitted to the Boost C++ libraries but I don't have the
  unpaid time to devote to such an endeavour sadly.

  \warning If you use std::vector<> as the STL container, make SURE you resize() it to its maximum size before use.
  Otherwise the iterators trie_map uses to link nedtrie items into the STL items will become invalidated on storage
  expansion.
  */
  template class nobblepolicy, class stlcontainer> class trie_map : protected stlcontainer, protected nobblepolicy >
  {
    typedef nobblepolicy > nobblepolicytype;
    typedef typename stlcontainer::value_type mapvaluetype;
    static const size_t trie_fieldoffset=mapvaluetype::trie_link_offset;
    template class nobblepolicy_, class stlcontainer_, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
  public:
    typedef typename stlcontainer::allocator_type allocator_type;
    typedef trie_iterator const_iterator;
    typedef typename stlcontainer::const_pointer const_pointer;
    typedef typename stlcontainer::const_reference const_reference;
    typedef trie_iterator const_reverse_iterator;
    typedef typename stlcontainer::difference_type difference_type;
    typedef trie_iterator iterator;
    typedef keytype key_type;
    typedef type mapped_type;
    typedef typename stlcontainer::pointer pointer;
    typedef typename stlcontainer::reference reference;
    typedef trie_iterator reverse_iterator;
    typedef typename stlcontainer::size_type size_type;
    typedef typename stlcontainer::value_type::trie_value_type value_type;
  private:
    trie_map_head triehead;
    static typename mapvaluetype::trie_iterator_type &from_iterator(iterator &it)
    {
      void *_it=(void *) ⁢
      return *(typename mapvaluetype::trie_iterator_type *)_it;
    }
    // Wipes and resets the nedtrie index
    void triehead_reindex()
    {
      NEDTRIE_INIT(&triehead);
      for(iterator it=begin(); it!=end(); ++it)
      {
        trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, &(*it));
        it->trie_iterator=it;
      }
    }
    const mapvaluetype *triehead_find(const key_type &key) const
    { // Avoid a value_type construction using pure unmitigated evil
      char buffer[sizeof(mapvaluetype)];
      new(buffer) intern::keystore_t(*(size_t *)"TRIEFINDKEYSTORE", key);
      return triefind, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct > >(&triehead, (mapvaluetype *) buffer);
    }
    const mapvaluetype *triehead_nfind(const key_type &key) const
    { // Avoid a value_type construction using pure unmitigated evil
      char buffer[sizeof(mapvaluetype)];
      new(buffer) intern::keystore_t(*(size_t *)"TRIEFINDKEYSTORE", key);
      return trieNfind, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct > >(&triehead, (mapvaluetype *) buffer);
    }
    const mapvaluetype *triehead_cfind(const key_type &key, int rounds) const
    { // Avoid a value_type construction using pure unmitigated evil
      char buffer[sizeof(mapvaluetype)];
      new(buffer) intern::keystore_t(*(size_t *)"TRIEFINDKEYSTORE", key);
      return trieCfind, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct > >(&triehead, (mapvaluetype *) buffer, rounds);
    }
    iterator triehead_insert(const value_type &val)
    {
      iterator it=iterator(this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, const_cast(&(*it)));
      return it;
    }
#ifdef HAVE_CPP0XRVALUEREFS
    iterator triehead_insert(value_type &&val)
    {
      iterator it=iterator(this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, const_cast(&(*it)));
      return it;
    }
#endif
    iterator triehead_insert(const keytype &key, const value_type &val)
    {
      iterator it=iterator(this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      it->trie_keyvalue=key;
      trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, const_cast(&(*it)));
      return it;
    }
#ifdef HAVE_CPP0XRVALUEREFS
    iterator triehead_insert(const keytype &key, value_type &&val)
    {
      iterator it=iterator(this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      it->trie_keyvalue=key;
      trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, const_cast(&(*it)));
      return it;
    }
#endif
  public:
    iterator begin() { return iterator(this, stlcontainer::begin()); }
    const_iterator begin() const { return const_iterator(this, stlcontainer::begin()); }
    using stlcontainer::clear;
    //! Returns the number of items with the key \em key
    size_type count(const key_type &key) const
    {
      size_type ret=0;
      const mapvaluetype *r=triehead_find(key);
      if(r)
      {
        if(r->trie_link.prev) r=r->trie_link.trie_prev;
        for(; r; r=r->trie_link.trie_next) ret++;
      }
      return ret;
    }
    using stlcontainer::empty;
    iterator end() { return iterator(this, stlcontainer::end()); }
    const_iterator end() const { return const_iterator(this, stlcontainer::end()); }
    //std::pair equal_range(const key_type &key);
    //std::pair equal_range(const key_type &key) const;
    //! Removes the item specified by \em it from the container
    iterator erase(iterator it)
    {
      //int (*nobblefunct)(trietype *head)
      trieremove, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct,
        // Need to give MSVC a little bit of help
#ifdef _MSC_VER
        nobblepolicytype::trie_nobblefunction >
#else
        nobblepolicytype::trie_nobblefunction
#endif
      >(&triehead, &(*it));
      return iterator(this, stlcontainer::erase((typename stlcontainer::iterator &) it));
    }
    //! Removes the items between \em first and \em last from the container
    iterator erase(iterator first, iterator last)
    {
      iterator ret(last); ++ret;
      for(iterator it=first; it!=last; ++it)
      {
        trieremove, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct,
#ifdef _MSC_VER
          nobblepolicytype::trie_nobblefunction >
#else
          nobblepolicytype::trie_nobblefunction
#endif
        >(&triehead, &(*it));
        stlcontainer::erase((typename stlcontainer::iterator &) it);
      }
      return ret;
    }
    //! Finds the item with key \em key
    iterator find(const key_type &key) { const_iterator it=static_cast(this)->find(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
    //! Finds the item with key \em key
    const_iterator find(const key_type &key) const
    {
      const mapvaluetype *r=triehead_find(key);
      return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator); // type pun safe
    }
    //! Finds the nearest item with key \em key
    iterator nfind(const key_type &key) { const_iterator it=static_cast(this)->nfind(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
    //! Finds the nearest item with key \em key
    const_iterator nfind(const key_type &key) const
    {
      const mapvaluetype *r=triehead_nfind(key);
      return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
    }
    //! Finds the closest item with key \em key trying up to \em rounds times
    iterator cfind(const key_type &key, int rounds=INT_MAX) { const_iterator it=static_cast(this)->cfind(key, rounds); void *_it=(void *) ⁢ return *(iterator *)_it; }
    //! Finds the closest item with key \em key trying up to \em rounds times
    const_iterator cfind(const key_type &key, int rounds=INT_MAX) const
    {
      const mapvaluetype *r=triehead_cfind(key, rounds);
      return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
    }
    using stlcontainer::get_allocator;
    //! Inserts the item \em val
    std::pair insert(const value_type &val)
    {
      mapvaluetype *r=const_cast(triehead_find(keyfunct()(val)));
      if(r)
      {
        r->trie_value=std::move(val);
        return std::make_pair(iterator(this, (typename stlcontainer::iterator &) r->trie_iterator), false);
      }
      return std::make_pair(triehead_insert(std::move(val)), true);
    }
    //! Inserts the item \em val at position \em at
    iterator insert(iterator at, const value_type &val)
    {
      iterator it=stlcontainer::insert(at, val);
      it->trie_iterator=from_iterator(it);
      trieinsert >(&triehead, &(*it));
      return it;
    }
    //! Inserts the items between \em first and \em last
    template void insert(inputiterator first, inputiterator last)
    {
      iterator it=--end();
      stlcontainer::insert(first, last);
      for(; it!=end(); ++it)
      {
        it->trie_iterator=from_iterator(it);
        trieinsert >(&triehead, &(*it));
      }
    }
    //key_compare key_comp() const;
    //iterator lower_bound(const key_type &key);
    //const_iterator lower_bound(const key_type &key) const;
    using stlcontainer::max_size;
    reverse_iterator rbegin() { return reverse_iterator(this, stlcontainer::begin()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator(this, stlcontainer::begin()); }
    reverse_iterator rend() { return reverse_iterator(this, stlcontainer::end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(this, stlcontainer::end()); }
    using stlcontainer::size;
    using stlcontainer::swap;
    //iterator upper_bound(const key_type &key);
    //const_iterator upper_bound(const key_type &key) const;
    //value_compare value_comp() const;
    //! Returns an lvalue reference to the item with key \em key
    mapped_type &operator[](const keytype &key)
    {
      mapvaluetype *r=const_cast(triehead_find(key));
      iterator it;
      if(r)
        it=iterator(this, (typename stlcontainer::iterator &) r->trie_iterator); // type pun safe
      else
      {
        it=triehead_insert(key, std::move(type()));
      }
      return it->trie_value;
    }

    template class nobblepolicy_, class stlcontainer_> friend bool operator!=(const trie_map &a, const trie_map &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator<(const trie_map &a, const trie_map &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator<=(const trie_map &a, const trie_map &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator==(const trie_map &a, const trie_map &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator>(const trie_map &a, const trie_map &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator>=(const trie_map &a, const trie_map &b);

    //! Constructs a trie_map. Has all the typical STL overloads
    trie_map() : stlcontainer() { NEDTRIE_INIT(&triehead); }
    explicit trie_map(const allocator &a) : stlcontainer(a) { NEDTRIE_INIT(&triehead); }
    template trie_map(const trie_map &o) : stlcontainer(o) { triehead_reindex(); }
    template trie_map &operator=(const trie_map &o) { *static_cast(this)=static_cast(o); triehead_reindex(); return *this; }
#ifdef HAVE_CPP0XRVALUEREFS
	  template trie_map(trie_map &&o) : stlcontainer(std::move(o))
    {
      memcpy(&triehead, &o.triehead, sizeof(triehead));
    }
    template trie_map &operator=(trie_map &&o)
    {
      *static_cast(this)=std::move(static_cast(o));
      memcpy(&triehead, &o.triehead, sizeof(triehead));
      return *this;
    }
#endif
    template trie_map(inputiterator s, inputiterator e) : stlcontainer(s, e) { triehead_reindex(); }
    template trie_map(inputiterator s, inputiterator e, const allocator &a) : stlcontainer(s, e, a) { triehead_reindex(); }
  };
  template class nobblepolicy, class stlcontainer> bool operator!=(const trie_map &a, const trie_map &b)
  {
    return static_cast(a)!=static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator<(const trie_map &a, const trie_map &b)
  {
    return static_cast(a)(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator<=(const trie_map &a, const trie_map &b)
  {
    return static_cast(a)<=static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator==(const trie_map &a, const trie_map &b)
  {
    return static_cast(a)==static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator>(const trie_map &a, const trie_map &b)
  {
    return static_cast(a)>static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator>=(const trie_map &a, const trie_map &b)
  {
    return static_cast(a)>=static_cast(b);
  }

  /*! \class trie_multimap
  \ingroup C++
  \brief A STL container wrapper using nedtries to map keys to values.

  \note Enable this by defining `NEDTRIE_ENABLE_STL_CONTAINERS`.

  This class can be used to wrap any arbitrary STL container with nedtrie associativity. For example, if you
  had a std::vector<> list of items, you could add nedtrie's fast nearly constant time algorithm for accessing them -
  though one would expect that a std::list<> would be the most common combination. There is no strict reason why
  one could not wrap std::unordered_map<>, though what one would gain is hard to imagine!

  Usage in the simplest sense is like this as the default template parameters use std::list<> as the underlying
  container:
  \code
  trie_multimap fooMap;
  fooMap[5]=Foo();
  fooMap.erase(fooMap.find(5));
  \endcode

  Unlike a proper STL container implementation, this wrapper is very much a hack in the sense that it's a very quick
  and dirty way of implementing lots of nedtrie based STL containers at once. In this sense it does require its user
  to not be stupid, and to know what they're doing. STL containers go out of their way to enforce correctness - well,
  this wrapper most certainly does not. If you want to blow off your own foot, this implementation won't stop you!

  For example, despite the protected STL container inheritance, all common STL functions are made public so you
  can if you want easily corrupt the internal state. Equally, if you know what you are doing you can pass in the
  wrapper as a const version of its underlying STL container by reintrpret_cast<>-ing it. Despite this, the wrapper
  is fairly typesafe in that its design won't introduce subtle bugs or cause existing code to magically break itself.

  If you would like a more proper bitwise trie STL container class implemented, or would like to be advised on any
  algorithmic problems from which your IT project may be suffering, my consulting company
  href="http://www.nedproductions.biz/">ned Productions Consulting Ltd would be happy to advise. In particular
  I would love to see a full bitwise trie implementation submitted to the Boost C++ libraries but I don't have the
  unpaid time to devote to such an endeavour sadly.

  \warning If you use std::vector<> as the STL container, make SURE you resize() it to its maximum size before use.
  Otherwise the iterators trie_multimap uses to link nedtrie items into the STL items will become invalidated on storage
  expansion.
  */
  template class nobblepolicy, class stlcontainer> class trie_multimap : protected stlcontainer, protected nobblepolicy >
  {
    typedef nobblepolicy > nobblepolicytype;
    typedef typename stlcontainer::value_type mapvaluetype;
    static const size_t trie_fieldoffset=mapvaluetype::trie_link_offset;
    template class nobblepolicy_, class stlcontainer_, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
  public:
    typedef typename stlcontainer::allocator_type allocator_type;
    typedef trie_iterator const_iterator;
    typedef typename stlcontainer::const_pointer const_pointer;
    typedef typename stlcontainer::const_reference const_reference;
    typedef trie_iterator const_reverse_iterator;
    typedef typename stlcontainer::difference_type difference_type;
    typedef trie_iterator iterator;
    typedef keytype key_type;
    typedef type mapped_type;
    typedef typename stlcontainer::pointer pointer;
    typedef typename stlcontainer::reference reference;
    typedef trie_iterator reverse_iterator;
    typedef typename stlcontainer::size_type size_type;
    typedef typename stlcontainer::value_type::trie_value_type value_type;
  private:
    trie_map_head triehead;
    static typename mapvaluetype::trie_iterator_type &from_iterator(iterator &it)
    {
      void *_it=(void *) ⁢
      return *(typename mapvaluetype::trie_iterator_type *)_it;
    }
    // Wipes and resets the nedtrie index
    void triehead_reindex()
    {
      NEDTRIE_INIT(&triehead);
      for(iterator it=begin(); it!=end(); ++it)
      {
        trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, &(*it));
        it->trie_iterator=it;
      }
    }
    const mapvaluetype *triehead_find(const key_type &key) const
    { // Avoid a value_type construction using pure unmitigated evil
      char buffer[sizeof(mapvaluetype)];
      new(buffer) intern::keystore_t(*(size_t *)"TRIEFINDKEYSTORE", key);
      return triefind, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct > >(&triehead, (mapvaluetype *) buffer);
    }
    iterator triehead_insert(const value_type &val)
    {
      iterator it=iterator((trie_map *) this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, const_cast(&(*it)));
      return it;
    }
#ifdef HAVE_CPP0XRVALUEREFS
    iterator triehead_insert(value_type &&val)
    {
      iterator it=iterator((trie_map *) this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      trieinsert, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct >(&triehead, const_cast(&(*it)));
      return it;
    }
#endif
  public:
    iterator begin() { return iterator((trie_map *) this, stlcontainer::begin()); }
    const_iterator begin() const { return const_iterator((trie_map *) this, stlcontainer::begin()); }
    using stlcontainer::clear;
    //! Returns the number of items with the key \em key
    size_type count(const key_type &key) const
    {
      size_type ret=0;
      const mapvaluetype *r=triehead_find(key);
      if(r)
      {
        if(r->trie_link.prev) r=r->trie_link.trie_prev;
        for(; r; r=r->trie_link.trie_next) ret++;
      }
      return ret;
    }
    using stlcontainer::empty;
    iterator end() { return iterator((trie_map *) this, stlcontainer::end()); }
    const_iterator end() const { return const_iterator((trie_map *) this, stlcontainer::end()); }
    //std::pair equal_range(const key_type &key);
    //std::pair equal_range(const key_type &key) const;
    //! Removes the item specified by \em it from the container
    iterator erase(iterator it)
    {
      //int (*nobblefunct)(trietype *head)
      trieremove, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct,
        // Need to give MSVC a little bit of help
#ifdef _MSC_VER
        nobblepolicytype::trie_nobblefunction >
#else
        nobblepolicytype::trie_nobblefunction
#endif
      >(&triehead, &(*it));
      return iterator((trie_map *) this, stlcontainer::erase((typename stlcontainer::iterator &) it));
    }
    //! Removes the items between \em first and \em last from the container
    iterator erase(iterator first, iterator last)
    {
      iterator ret(last); ++ret;
      for(iterator it=first; it!=last; ++it)
      {
        trieremove, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct,
#ifdef _MSC_VER
          nobblepolicytype::trie_nobblefunction >
#else
          nobblepolicytype::trie_nobblefunction
#endif
        >(&triehead, &(*it));
        stlcontainer::erase((typename stlcontainer::iterator &) it);
      }
      return ret;
    }
    //! Finds the item with key \em key
    iterator find(const key_type &key) { const_iterator it=static_cast(this)->find(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
    //! Finds the item with key \em key
    const_iterator find(const key_type &key) const
    {
      const mapvaluetype *r=triehead_find(key);
      return !r ? end() : const_iterator((trie_map *) this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
    }
    //! Finds the nearest item with key \em key
    iterator nfind(const key_type &key) { const_iterator it=static_cast(this)->nfind(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
    //! Finds the nearest item with key \em key
    const_iterator nfind(const key_type &key) const
    {
      const mapvaluetype *r=triehead_nfind(key);
      return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
    }
    //! Finds the closest item with key \em key trying up to \em rounds times
    iterator cfind(const key_type &key, int rounds=INT_MAX) { const_iterator it=static_cast(this)->cfind(key, rounds); void *_it=(void *) ⁢ return *(iterator *)_it; }
    //! Finds the closest item with key \em key trying up to \em rounds times
    const_iterator cfind(const key_type &key, int rounds=INT_MAX) const
    {
      const mapvaluetype *r=triehead_cfind(key, rounds);
      return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
    }
    using stlcontainer::get_allocator;
    //! Inserts the item \em val
    iterator insert(const value_type &val)
    {
      return triehead_insert(std::move(val));
    }
    //! Inserts the item \em val at position \em at
    iterator insert(iterator at, const value_type &val)
    {
      iterator it=stlcontainer::insert(at, val);
      it->trie_iterator=from_iterator(it);
      trieinsert >(&triehead, &(*it));
      return it;
    }
    //! Inserts the items between \em first and \em last
    template void insert(inputiterator first, inputiterator last)
    {
      iterator it=--end();
      stlcontainer::insert(first, last);
      for(; it!=end(); ++it)
      {
        it->trie_iterator=from_iterator(it);
        trieinsert >(&triehead, &(*it));
      }
    }
    //key_compare key_comp() const;
    //iterator lower_bound(const key_type &key);
    //const_iterator lower_bound(const key_type &key) const;
    using stlcontainer::max_size;
    reverse_iterator rbegin() { return reverse_iterator((trie_map *) this, stlcontainer::begin()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator((trie_map *) this, stlcontainer::begin()); }
    reverse_iterator rend() { return reverse_iterator((trie_map *) this, stlcontainer::end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator((trie_map *) this, stlcontainer::end()); }
    using stlcontainer::size;
    using stlcontainer::swap;
    //iterator upper_bound(const key_type &key);
    //const_iterator upper_bound(const key_type &key) const;
    //value_compare value_comp() const;

    template class nobblepolicy_, class stlcontainer_> friend bool operator!=(const trie_multimap &a, const trie_multimap &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator<(const trie_multimap &a, const trie_multimap &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator<=(const trie_multimap &a, const trie_multimap &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator==(const trie_multimap &a, const trie_multimap &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator>(const trie_multimap &a, const trie_multimap &b);
    template class nobblepolicy_, class stlcontainer_> friend bool operator>=(const trie_multimap &a, const trie_multimap &b);

    //! Constructs a trie_multimap. Has all the typical STL overloads
    trie_multimap() : stlcontainer() { NEDTRIE_INIT(&triehead); }
    explicit trie_multimap(const allocator &a) : stlcontainer(a) { NEDTRIE_INIT(&triehead); }
    template trie_multimap(const trie_multimap &o) : stlcontainer(o) { triehead_reindex(); }
    template trie_multimap &operator=(const trie_multimap &o) { *static_cast(this)=static_cast(o); triehead_reindex(); return *this; }
#ifdef HAVE_CPP0XRVALUEREFS
	  template trie_multimap(trie_multimap &&o) : stlcontainer(std::move(o))
    {
      memcpy(&triehead, &o.triehead, sizeof(triehead));
    }
    template trie_multimap &operator=(trie_multimap &&o)
    {
      *static_cast(this)=std::move(static_cast(o));
      memcpy(&triehead, &o.triehead, sizeof(triehead));
      return *this;
    }
#endif
    template trie_multimap(inputiterator s, inputiterator e) : stlcontainer(s, e) { triehead_reindex(); }
    template trie_multimap(inputiterator s, inputiterator e, const allocator &a) : stlcontainer(s, e, a) { triehead_reindex(); }
  };
  template class nobblepolicy, class stlcontainer> bool operator!=(const trie_multimap &a, const trie_multimap &b)
  {
    return static_cast(a)!=static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator<(const trie_multimap &a, const trie_multimap &b)
  {
    return static_cast(a)(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator<=(const trie_multimap &a, const trie_multimap &b)
  {
    return static_cast(a)<=static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator==(const trie_multimap &a, const trie_multimap &b)
  {
    return static_cast(a)==static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator>(const trie_multimap &a, const trie_multimap &b)
  {
    return static_cast(a)>static_cast(b);
  }
  template class nobblepolicy, class stlcontainer> bool operator>=(const trie_multimap &a, const trie_multimap &b)
  {
    return static_cast(a)>=static_cast(b);
  }

#endif

} /* namespace */

#ifdef _MSC_VER
#pragma warning(pop)
#endif
#endif