nedtrie.h

Go to the documentation of this file.

/* 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 <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h> /* for memset */
#include <limits.h> /* 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

#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

#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

#ifndef NOINLINE
  #if defined(__GNUC__)
    #define NOINLINE __attribute__ ((noinline))
  #elif defined(_MSC_VER)
    #define NOINLINE __declspec(noinline)
  #else
    #define NOINLINE
  #endif
#endif

#ifndef DEBUGINLINE
#ifdef NDEBUG
#define DEBUGINLINE INLINE
#elif defined(DEBUG)
#define DEBUGINLINE NOINLINE
#else
#define DEBUGINLINE
#endif
#endif

#ifndef NEDTRIEUSEMACROS
#ifdef __cplusplus
#define NEDTRIEUSEMACROS 0
#else
#define NEDTRIEUSEMACROS 1
#endif
#endif

#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 <intrin.h>
#endif

#ifdef __cplusplus
#include <list>
#if (defined(_MSC_VER) && _MSC_VER<=1500) || (defined(__GNUC__) && !defined(HAVE_CPP0X))
// Doesn't have std::move<> by default, so define
namespace std
{
  template<class T> T &move(T &a) { return a; }
  template<class T> T &move(const T &a) { return const_cast<T &>(a); }
  template<class T, class A> 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

#define NEDTRIE_INDEXBINS (8*sizeof(void *))

#define NEDTRIE_HEAD2(name, type) \
struct name {                    \
  size_t count;                  \
  type *triebins[NEDTRIE_INDEXBINS]; /* each containing (1<<x)<=bitscanrev(x)<(1<<(x+1)) */ \
  int nobbledir;                 \
}
#define NEDTRIE_HEAD(name, type) NEDTRIE_HEAD2(name, struct type)

#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)

#define NEDTRIE_INIT(root) do { memset((root), 0, sizeof(*(root))); } while(0)

#define NEDTRIE_EMPTY(head) (!(head)->count)

#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<class trietype> int trienobblezeros(trietype *)
  {
    return 0;
  }
  template<class trietype> int trienobbleones(trietype *)
  {
    return 1;
  }
  template<class trietype> int trienobbleequally(trietype *head)
  {
    return (head->nobbledir=!head->nobbledir);
  }
#define NEDTRIE_NOBBLEZEROS(name)   nedtries::trienobblezeros<name>

#define NEDTRIE_NOBBLEONES(name)    nedtries::trienobbleones<name>

#define NEDTRIE_NOBBLEEQUALLY(name) nedtries::trienobbleequally<name>
#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<class type> 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<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE void triecheckvalidity(trietype *head);
  namespace testtrielinksize {
    struct foo1; struct foo2;
    struct foo1 { NEDTRIE_ENTRY(foo1) link; size_t n; };
    struct foo2 { TrieLink_t<foo2> 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<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE void trieinsert(trietype *RESTRICT head, type *RESTRICT r)
  {
    type *RESTRICT node, *RESTRICT childnode;
    TrieLink_t<type> *RESTRICT nodelink, *RESTRICT rlink;
    size_t rkey=keyfunct(r), keybit, nodekey;
    unsigned bitidx;
    int keybitset;

    rlink=(TrieLink_t<type> *RESTRICT)((size_t) r + fieldoffset);
    memset(rlink, 0, sizeof(TrieLink_t<type>));
    bitidx=nedtriebitscanr(rkey);
    assert(bitidx<NEDTRIE_INDEXBINS);
    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<<bitidx;
    for(;;node=childnode)
    {
      nodelink=(TrieLink_t<type> *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<type> *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<trietype, type, fieldoffset, keyfunct>(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<NEDTRIE_INDEXBINS); \
    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<<bitidx; \
    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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT), int (*nobblefunct)(trietype *head)> DEBUGINLINE void trieremove(trietype *RESTRICT head, type *RESTRICT r)
  {
    type *RESTRICT node, **myaddrinparent=0;
    TrieLink_t<type> *RESTRICT nodelink, *RESTRICT childlink, *RESTRICT rlink;
    unsigned bitidx;

    rlink=(TrieLink_t<type> *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<type> *RESTRICT)((size_t) node + fieldoffset);
      nodelink->trie_next=rlink->trie_next;
      if(rlink->trie_next)
      {
        nodelink=(TrieLink_t<type> *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<type> *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<type> *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<type> *RESTRICT)((size_t) *childaddrinparent + fieldoffset))->trie_child[nobbledir]))
         || *(newchildaddrinparent=&(((TrieLink_t<type> *RESTRICT)((size_t) *childaddrinparent + fieldoffset))->trie_child[!nobbledir])))
        childaddrinparent=newchildaddrinparent;
      node=*childaddrinparent;
      *childaddrinparent=0;
    }
  end:
    if(node)
    {
      nodelink=(TrieLink_t<type> *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<type> *RESTRICT)((size_t) nodelink->trie_child[0] + fieldoffset);
        childlink->trie_parent=node;
      }
      if(nodelink->trie_child[1])
      {
        childlink=(TrieLink_t<type> *RESTRICT)((size_t) nodelink->trie_child[1] + fieldoffset);
        childlink->trie_parent=node;
      }
    }
    *myaddrinparent=node;
  functexit:
    head->count--;
#if NEDTRIEDEBUG
    triecheckvalidity<trietype, type, fieldoffset, keyfunct>(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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct, nobblefunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

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

    if(!head->count) return 0;
    rlink=(const TrieLink_t<type> *RESTRICT)((size_t) r + fieldoffset);
    bitidx=nedtriebitscanr(rkey);
    assert(bitidx<NEDTRIE_INDEXBINS);
    if(!(node=head->triebins[bitidx]))
      return 0;
    /* Avoid variable bit shifts where possible, their performance can suck */
    keybit=(size_t) 1<<bitidx;
    for(;;node=childnode)
    {
      nodelink=(const TrieLink_t<type> *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<NEDTRIE_INDEXBINS); \
    if(!(node=head->triebins[bitidx])) \
      return 0; \
    /* Avoid variable bit shifts where possible, their performance can suck */ \
    keybit=(size_t) 1<<bitidx; \
    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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

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

    if(!head->count) return 0;
    if(!(node=triefind<trietype, type, fieldoffset, keyfunct>(head, r))) return 0;
    nodelink=(const TrieLink_t<type> *RESTRICT)((size_t) node + fieldoffset);
    if(nodelink->trie_prev) node=nodelink->trie_prev;
    do
    {
      if(node==r) return 1;
      nodelink=(const TrieLink_t<type> *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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> 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<type> *RESTRICT nodelink, *RESTRICT rlink;
    size_t rkey=keyfunct(r), keybit, nodekey;
    unsigned binbitidx;
    int keybitset;

    if(!head->count) return 0;
    rlink=(const TrieLink_t<type> *RESTRICT)((size_t) r + fieldoffset);
    binbitidx=nedtriebitscanr(rkey);
    assert(binbitidx<NEDTRIE_INDEXBINS);
    do
    {
      size_t retkey=(size_t)-1;
      unsigned bitidx;
      /* Keeping raising the bin until we find a larger key */
      while(binbitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[binbitidx]))
        binbitidx++;
      if(binbitidx>=NEDTRIE_INDEXBINS)
        return 0;
      bitidx=binbitidx;
      /* Avoid variable bit shifts where possible, their performance can suck */
      keybit=(size_t) 1<<bitidx;
      nodelink=(const TrieLink_t<type> *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<retkey)
      {
        ret=node;
        retkey=nodekey-rkey;
      }
      if(rounds--<=0 && ret) return (type *) ret;
      for(;;node=childnode)
      {
        nodelink=(const TrieLink_t<type> *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<retkey)
          {
            ret=nodelink->trie_child[0];
            retkey=nodekey-rkey;
          }
        }
        if(nodelink->trie_child[1])
        {
          nodekey=keyfunct(nodelink->trie_child[1]);
          if(nodekey>=rkey && nodekey-rkey<retkey)
          {
            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<type> *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<NEDTRIE_INDEXBINS); \
    do \
    { \
      size_t retkey=(size_t)-1; \
      unsigned bitidx; \
      /* Keeping raising the bin until we find a larger key */ \
      while(binbitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[binbitidx])) \
        binbitidx++; \
      if(binbitidx>=NEDTRIE_INDEXBINS) \
        return 0; \
      bitidx=binbitidx; \
      /* Avoid variable bit shifts where possible, their performance can suck */ \
      keybit=(size_t) 1<<bitidx; \
      nodekey=keyfunct(node); \
      /* If nodekey is a closer fit to search key, mark as best result so far */ \
      if(nodekey>=rkey && nodekey-rkey<retkey) \
      { \
        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<retkey) \
          { \
            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<retkey) \
          { \
            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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r, rounds); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *trieminmax(const trietype *RESTRICT head, const unsigned dir)
  {
    const type *RESTRICT node=0, *RESTRICT child;
    const TrieLink_t<type> *RESTRICT nodelink;
    unsigned bitidx;
    if(!head->count) return 0;
    if(!dir)
    { /* He wants min */
      for(bitidx=0; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[bitidx]); bitidx++);
      assert(node);
      return (type *) node;
    }
    /* He wants max */
    for(bitidx=NEDTRIE_INDEXBINS-1; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[bitidx]); bitidx--);
    assert(node);
    nodelink=(const TrieLink_t<type> *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<type> *RESTRICT)((size_t) node + fieldoffset);
    }
    /* Now go to end leaf */
    while(nodelink->trie_next)
    {
      node=nodelink->trie_next;
      nodelink=(const TrieLink_t<type> *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; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[bitidx]); bitidx++); \
      assert(node); \
      return node; \
    } \
    /* He wants max */ \
    for(bitidx=NEDTRIE_INDEXBINS-1; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, dir); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *triebranchprev(const type *RESTRICT r, const TrieLink_t<type> *RESTRICT *rlinkaddr)
  {
    const type *RESTRICT node=0, *RESTRICT child;
    const TrieLink_t<type> *RESTRICT nodelink, *RESTRICT rlink;

    rlink=(TrieLink_t<type> *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<type> *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<type> *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<type> *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<type> *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<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *trieprev(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node=0, *RESTRICT child;
    const TrieLink_t<type> *RESTRICT nodelink, *RESTRICT rlink=0;
    unsigned bitidx;

    if((node=triebranchprev<trietype, type, fieldoffset, keyfunct>(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--; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[bitidx]); bitidx--);
    if(bitidx>=NEDTRIE_INDEXBINS) return 0;
    nodelink=(const TrieLink_t<type> *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<type> *RESTRICT)((size_t) node + fieldoffset);
    }
    /* Now go to end leaf */
    while(nodelink->trie_next)
    {
      node=nodelink->trie_next;
      nodelink=(const TrieLink_t<type> *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--; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *triebranchnext(const type *RESTRICT r, const TrieLink_t<type> *RESTRICT *rlinkaddr)
  {
    const type *RESTRICT node;
    const TrieLink_t<type> *RESTRICT nodelink, *RESTRICT rlink;

    rlink=(const TrieLink_t<type> *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<type> *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<type> *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<type> *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<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *trienext(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node;
    const TrieLink_t<type> *RESTRICT rlink=0;
    unsigned bitidx;

    if((node=triebranchnext<trietype, type, fieldoffset, keyfunct>(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++; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[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++; bitidx<NEDTRIE_INDEXBINS && !(node=head->triebins[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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */

#ifdef __cplusplus
namespace nedtries {
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *trieNfind(const trietype *RESTRICT head, const type *RESTRICT r)
  {
    const type *RESTRICT node=0, *RESTRICT ret=trieCfind<trietype, type, fieldoffset, keyfunct>(head, r, INT_MAX), *RESTRICT stop;
    const TrieLink_t<type> *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<type> *RESTRICT)((size_t) ret + fieldoffset);
    stop=rlink->trie_parent;
    for(node=triebranchnext<trietype, type, fieldoffset, keyfunct>(ret, 0); node && node!=stop; node=triebranchnext<trietype, type, fieldoffset, keyfunct>(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<retkey)
      {
        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<retkey) \
      { \
        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<struct name, struct type, NEDTRIEFIELDOFFSET(type, field), keyfunct>(head, r); \
}
#endif /* NEDTRIEUSEMACROS */


#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; }

#define NEDTRIE_INSERT(name, x, y)       name##_NEDTRIE_INSERT(x, y)

#define NEDTRIE_REMOVE(name, x, y)       name##_NEDTRIE_REMOVE(x, y)

#define NEDTRIE_FIND(name, x, y)         name##_NEDTRIE_FIND(x, y)

#define NEDTRIE_EXACTFIND(name, x, y)    name##_NEDTRIE_EXACTFIND(x, y)

#define NEDTRIE_CFIND(name, x, y, rounds) name##_NEDTRIE_CFIND(x, y, rounds)

#define NEDTRIE_NFIND(name, x, y)        name##_NEDTRIE_NFIND(x, y)

#define NEDTRIE_PREV(name, x, y)         name##_NEDTRIE_PREV(x, y)

#define NEDTRIE_NEXT(name, x, y)         name##_NEDTRIE_NEXT(x, y)

#define NEDTRIE_PREVLEAF(name, x)        name##_NEDTRIE_PREVLEAF(x)

#define NEDTRIE_NEXTLEAF(name, x)        name##_NEDTRIE_NEXTLEAF(x)

#define NEDTRIE_MIN(name, x)             name##_NEDTRIE_MINMAX(x, 0)

#define NEDTRIE_MAX(name, x)             name##_NEDTRIE_MINMAX(x, 1)

#define NEDTRIE_FOREACH(x, name, head)          \
    for ((x) = NEDTRIE_MIN(name, head);           \
         (x) != NULL;                             \
         (x) = NEDTRIE_NEXT(name, head, x))

#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))

#define NEDTRIE_FOREACH_REVERSE(x, name, head)  \
    for ((x) = NEDTRIE_MAX(name, head);           \
         (x) != NULL;                             \
         (x) = NEDTRIE_PREV(name, head, x))

#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))

#define NEDTRIE_HASNODEHEADER(treevar, node, link)  ((node)->link.trie_parent || (node)->link.trie_prev)

#ifdef __cplusplus
#include <functional>
namespace nedtries {

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

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

    if(nodekey<state.smallestkey) state.smallestkey=nodekey;
    if(nodekey>state.largestkey) state.largestkey=nodekey;
    nodelink=(TrieLink_t<type> *RESTRICT)((size_t) node + fieldoffset);
    assert(nodelink->trie_parent);
    child=nodelink->trie_parent;
    childlink=(TrieLink_t<type> *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<<bitidx))]);
    assert(!nodelink->trie_prev);
    while((child=nodelink->trie_next))
    {
      state.leafs++;
      childlink=(TrieLink_t<type> *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<type> *RESTRICT)((size_t) childlink->trie_next + fieldoffset))->trie_prev);
      nodelink=childlink;
      state.count++;
    }
    nodelink=(TrieLink_t<type> *RESTRICT)((size_t) node + fieldoffset);
    state.count++;
    if(nodelink->trie_child[0])
    {
      state.lefts++;
      triecheckvaliditybranch<trietype, type, fieldoffset, keyfunct>(head, nodelink->trie_child[0], bitidx-1, state);
    }
    if(nodelink->trie_child[1])
    {
      state.rights++;
      triecheckvaliditybranch<trietype, type, fieldoffset, keyfunct>(head, nodelink->trie_child[1], bitidx-1, state);
    }
  }
#endif
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE void triecheckvalidity(trietype *head)
  {
#ifndef NDEBUG
    type *RESTRICT node, *RESTRICT child;
    TrieLink_t<type> *RESTRICT nodelink, *RESTRICT childlink;
    unsigned n, bitidx;
    TrieValidityState state={0};
    for(n=0; n<NEDTRIE_INDEXBINS; n++)
    {
      if((node=head->triebins[n]))
      {
        size_t nodekey=keyfunct(node);
        state.tops++;
        nodelink=(TrieLink_t<type> *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)<<bitidx) & nodekey)==((size_t) 1<<bitidx));
        assert(!nodelink->trie_prev);
        while((child=nodelink->trie_next))
        {
          state.leafs++;
          childlink=(TrieLink_t<type> *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<type> *RESTRICT)((size_t) childlink->trie_next + fieldoffset))->trie_prev);
          nodelink=childlink;
          state.count++;
        }
        nodelink=(TrieLink_t<type> *RESTRICT)((size_t) node + fieldoffset);
        state.count++;
        if(nodelink->trie_child[0])
        {
          state.lefts++;
          state.smallestkey=(size_t)-1;
          state.largestkey=0;
          triecheckvaliditybranch<trietype, type, fieldoffset, keyfunct>(head, nodelink->trie_child[0], bitidx-1, state);
          assert(!state.smallestkey || state.smallestkey>=(size_t)1<<bitidx);
          assert(state.largestkey<(size_t)1<<(bitidx+1));
        }
        if(nodelink->trie_child[1])
        {
          state.rights++;
          state.smallestkey=(size_t)-1;
          state.largestkey=0;
          triecheckvaliditybranch<trietype, type, fieldoffset, keyfunct>(head, nodelink->trie_child[1], bitidx-1, state);
          assert(state.smallestkey>=(size_t)1<<bitidx);
          assert(state.largestkey<(size_t)1<<(bitidx+1));
        }
      }
    }
    assert(state.count==head->count);
    for(state.count=0, node=trieminmax<trietype, type, fieldoffset, keyfunct>(head, 0); node; (node=trienext<trietype, type, fieldoffset, keyfunct>(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<trietype, type, fieldoffset, keyfunct>(head, 1); node; (node=trieprev<trietype, type, fieldoffset, keyfunct>(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

#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

  namespace nedpolicy
  {
    template<class triemaptype> class nobblezeros
    {
    protected:
      template<class trietype> static int trie_nobblefunction(trietype *)
      {
        return 0;
      }
    };
    template<class triemaptype> class nobbleones
    {
    protected:
      template<class trietype> static int trie_nobblefunction(trietype *)
      {
        return 1;
      }
    };
    template<class triemaptype> class nobbleequally
    {
    protected:
      template<class trietype> static int trie_nobblefunction(trietype *head)
      {
        return (head->nobbledir=!head->nobbledir);
      }
    };
  } // namspace
  template<class type> NEDTRIE_HEAD2(trie_map_head, type);
  template<class keytype, class type, class keyfunct, class iteratortype> struct trie_maptype;
  template<class keytype, class type> struct trie_keyfunct : public std::unary_function<type, keytype>
  {
#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<class keytype, class type> struct trie_maptype_keyfunct : public std::unary_function<type, keytype>
  {
      template<class maptype> keytype operator()(const maptype &v) const
      {
        return v.trie_keyvalue;
      }
  };
  namespace intern {
    template<class type> struct noconstiteratortype : public type { };
    template<class keyfunct_, class mapvaluetype> size_t to_Ckeyfunct(const mapvaluetype *RESTRICT v)
    {
      return keyfunct_()(*v);
    }
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer,
    class iteratortype, int dir, class mapvaluetype, class constiteratortype=intern::noconstiteratortype<iteratortype> > class trie_iterator;
  template<class keytype, class type, class keyfunct=trie_maptype_keyfunct<keytype, type>,
    class allocator=std::allocator<trie_maptype<keytype, type, keyfunct, std::list<size_t>::iterator> >,
    template<class> class nobblepolicy=nedpolicy::nobblezeros, 
    class stlcontainer=std::list<trie_maptype<keytype, type, keyfunct, std::list<size_t>::iterator>, allocator> > class trie_map;
  template<class keytype, class type, class keyfunct=trie_keyfunct<keytype, type>, 
    class allocator=std::allocator<trie_maptype<keytype, type, keyfunct, std::list<size_t>::iterator> >,
    template<class> class nobblepolicy=nedpolicy::nobblezeros, 
    class stlcontainer=std::list<trie_maptype<keytype, type, keyfunct, std::list<size_t>::iterator>, allocator> > class trie_multimap;
  namespace fake {
    template<class keytype, class type, class keyfunct, class iteratortype> struct trie_maptype
    {
      template<class keytype_, class type_> friend struct trie_keyfunct;
      template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
      template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_map;
      template<class keytype_, class type_, class keyfunct_, class allocator, template<class> 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<type> trie_link;
    };
  }
  template<class keytype, class type, class keyfunct, class iteratortype> struct trie_maptype
  {
  private: // ENSURE the fake type above mirrors this one
    template<class keytype_, class type_> friend struct trie_keyfunct;
    template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
    template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_map;
    template<class keytype_, class type_, class keyfunct_, class allocator, template<class> 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<keytype, type, keyfunct, iteratortype> fakemirrorofme_type;
    type trie_value;
    iteratortype trie_iterator;
    TrieLink_t<type> 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<class keytype_, class type_, class keyfunct_, class iteratortype_> trie_maptype(const trie_maptype<keytype_, type_, keyfunct_, iteratortype_> &o) : trie_value(o.trie_value) { }
#ifdef HAVE_CPP0XRVALUEREFS
    template<class keytype_, class type_, class keyfunct_, class iteratortype_> trie_maptype(trie_maptype<keytype_, type_, keyfunct_, iteratortype_> &&o) : trie_value(std::move(o.trie_value)) { }
#endif
    operator const type &() const { return trie_value; }
  };
  namespace fake {
    template<class keytype, class type, class iteratortype> struct trie_maptype2
    {
      template<class keytype_, class type_> friend struct trie_keyfunct;
      template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
      template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_map;
      template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_multimap;
      template<class keytype_, class type_> friend struct trie_maptype_keyfunct;
      typedef keytype trie_key_type;
      typedef type trie_value_type;
      typedef trie_maptype_keyfunct<keytype, type> 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<type> trie_link;
    };
  }
  template<class keytype, class type, class iteratortype> struct trie_maptype<keytype, type, trie_maptype_keyfunct<keytype, type>, iteratortype>
  {
  private: // ENSURE the fake type above mirrors this one
    template<class keytype_, class type_> friend struct trie_keyfunct;
    template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer, class iteratortype_, int dir, class mapvaluetype, class constiteratortype> friend class trie_iterator;
    template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_map;
    template<class keytype_, class type_, class keyfunct_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_multimap;
    template<class keytype_, class type_> friend struct trie_maptype_keyfunct;
    typedef keytype trie_key_type;
    typedef type trie_value_type;
    typedef trie_maptype_keyfunct<keytype, type> trie_keyfunct_type;
    typedef iteratortype trie_iterator_type;
    typedef fake::trie_maptype2<keytype, type, iteratortype> fakemirrorofme_type;
    type trie_value;
    keytype trie_keyvalue; // For when key is overriden using trie_map::operator[]
    iteratortype trie_iterator;
    TrieLink_t<type> 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<class keytype_, class type_, class iteratortype_> trie_maptype(const trie_maptype<keytype_, type_, trie_maptype_keyfunct<keytype_, type_>, iteratortype_> &o) : trie_value(o.trie_value), trie_keyvalue(o.trie_keyvalue) { }
#ifdef HAVE_CPP0XRVALUEREFS
    template<class keytype_, class type_, class iteratortype_> trie_maptype(trie_maptype<keytype_, type_, trie_maptype_keyfunct<keytype_, type_>, iteratortype_> &&o) : trie_value(std::move(o.trie_value)), trie_keyvalue(std::move(o.trie_keyvalue)) { }
#endif
    operator const type &() const { return trie_value; }
  };

  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer, class iteratortype, int dir, class mapvaluetype, class constiteratortype> class trie_iterator : protected iteratortype
  {
    trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *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<const iteratortype &>(*this)); }

    trie_iterator() : parent(0) { }
    trie_iterator(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *parent_, const iteratortype &o) : iteratortype(o), parent(const_cast<trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *>(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<trie_map_head<mapvaluetype>, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct<typename mapvaluetype::trie_keyfunct_type> >(&parent->triehead, (mapvaluetype *)(&**this)) :
        trieprev<trie_map_head<mapvaluetype>, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct<typename mapvaluetype::trie_keyfunct_type> >(&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<trie_map_head<mapvaluetype>, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct<typename mapvaluetype::trie_keyfunct_type> >(&parent->triehead, (mapvaluetype *)(&**this)) :
        trieprev<trie_map_head<mapvaluetype>, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct<typename mapvaluetype::trie_keyfunct_type> >(&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<const iteratortype &>(*this)==static_cast<const iteratortype &>(o); }
    bool operator!=(const trie_iterator &o) const { return static_cast<const iteratortype &>(*this)!=static_cast<const iteratortype &>(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<class key_type> 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<class keytype, class type, class mapvaluetype, class keyfunct> struct findkeyfunct_t : public std::unary_function<type, keytype>
      {
        size_t operator()(const mapvaluetype &v) const
        {
          keystore_t<keytype> *r=(keystore_t<keytype> *)(void *)(&v);
      // NOTE: This line triggers a "conditional jump or move depends on unintialized value(s)" in valgrind if
      // sizeof(type)<sizeof(size_t). This is unavoidable.
          if(r->magic==*(size_t *)"TRIEFINDKEYSTORE")
            return r->key;
          return keyfunct()(v);
        }
      };
  }

  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> class trie_map : protected stlcontainer, protected nobblepolicy<trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> >
  {
    typedef nobblepolicy<trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> > nobblepolicytype;
    typedef typename stlcontainer::value_type mapvaluetype;
    static const size_t trie_fieldoffset=mapvaluetype::trie_link_offset;
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> 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<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::const_iterator, 1, mapvaluetype> const_iterator;
    typedef typename stlcontainer::const_pointer const_pointer;
    typedef typename stlcontainer::const_reference const_reference;
    typedef trie_iterator<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::const_reverse_iterator, -1, mapvaluetype> const_reverse_iterator;
    typedef typename stlcontainer::difference_type difference_type;
    typedef trie_iterator<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::iterator, 1, mapvaluetype, const_iterator> iterator;
    typedef keytype key_type;
    typedef type mapped_type;
    typedef typename stlcontainer::pointer pointer;
    typedef typename stlcontainer::reference reference;
    typedef trie_iterator<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::reverse_iterator, -1, mapvaluetype, const_reverse_iterator> reverse_iterator;
    typedef typename stlcontainer::size_type size_type;
    typedef typename stlcontainer::value_type::trie_value_type value_type;
  private:
    trie_map_head<mapvaluetype> triehead;
    static typename mapvaluetype::trie_iterator_type &from_iterator(iterator &it)
    {
      void *_it=(void *) &it;
      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<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&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<key_type>(*(size_t *)"TRIEFINDKEYSTORE", key);
      return triefind<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<intern::findkeyfunct_t<keytype, type, mapvaluetype, keyfunct> > >(&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<key_type>(*(size_t *)"TRIEFINDKEYSTORE", key);
      return trieNfind<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<intern::findkeyfunct_t<keytype, type, mapvaluetype, keyfunct> > >(&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<key_type>(*(size_t *)"TRIEFINDKEYSTORE", key);
      return trieCfind<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<intern::findkeyfunct_t<keytype, type, mapvaluetype, keyfunct> > >(&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<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*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<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*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<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*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<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*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;
    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<iterator, iterator> equal_range(const key_type &key);
    //std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const;
    iterator erase(iterator it)
    {
      //int (*nobblefunct)(trietype *head)
      trieremove<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct>,
        // Need to give MSVC a little bit of help
#ifdef _MSC_VER
        nobblepolicytype::trie_nobblefunction<trie_map_head<mapvaluetype> >
#else
        nobblepolicytype::trie_nobblefunction
#endif
      >(&triehead, &(*it));
      return iterator(this, stlcontainer::erase((typename stlcontainer::iterator &) it));
    }
    iterator erase(iterator first, iterator last)
    {
      iterator ret(last); ++ret;
      for(iterator it=first; it!=last; ++it)
      {
        trieremove<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct>,
#ifdef _MSC_VER
          nobblepolicytype::trie_nobblefunction<trie_map_head<mapvaluetype> >
#else
          nobblepolicytype::trie_nobblefunction
#endif
        >(&triehead, &(*it));
        stlcontainer::erase((typename stlcontainer::iterator &) it);
      }
      return ret;
    }
    iterator find(const key_type &key) { const_iterator it=static_cast<const trie_map *>(this)->find(key); void *_it=(void *) &it; return *(iterator *)_it; }
    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
    }
    iterator nfind(const key_type &key) { const_iterator it=static_cast<const trie_map *>(this)->nfind(key); void *_it=(void *) &it; return *(iterator *)_it; }
    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);
    }
    iterator cfind(const key_type &key, int rounds=INT_MAX) { const_iterator it=static_cast<const trie_map *>(this)->cfind(key, rounds); void *_it=(void *) &it; return *(iterator *)_it; }
    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;
    std::pair<iterator, bool> insert(const value_type &val)
    {
      mapvaluetype *r=const_cast<mapvaluetype *>(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);
    }
    iterator insert(iterator at, const value_type &val)
    {
      iterator it=stlcontainer::insert(at, val);
      it->trie_iterator=from_iterator(it);
      trieinsert<trie_map_head, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, &(*it));
      return it;
    }
    template<class inputiterator> void insert(inputiterator first, inputiterator last)
    {
      iterator it=--end();
      stlcontainer::insert(first, last);
      for(; it!=end(); ++it)
      {
        it->trie_iterator=from_iterator(it);
        trieinsert<trie_map_head, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&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;
    mapped_type &operator[](const keytype &key)
    {
      mapvaluetype *r=const_cast<mapvaluetype *>(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 keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator!=(const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator<(const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator<=(const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator==(const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator>(const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator>=(const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);

    trie_map() : stlcontainer() { NEDTRIE_INIT(&triehead); }
    explicit trie_map(const allocator &a) : stlcontainer(a) { NEDTRIE_INIT(&triehead); }
    template<class okeytype, class otype, class oallocator> trie_map(const trie_map<okeytype, otype, oallocator> &o) : stlcontainer(o) { triehead_reindex(); }
    template<class okeytype, class otype, class oallocator> trie_map &operator=(const trie_map<okeytype, otype, oallocator> &o) { *static_cast<stlcontainer *>(this)=static_cast<const stlcontainer &>(o); triehead_reindex(); return *this; }
#ifdef HAVE_CPP0XRVALUEREFS
      template<class okeytype, class otype, class oallocator> trie_map(trie_map<okeytype, otype, oallocator> &&o) : stlcontainer(std::move(o))
    {
      memcpy(&triehead, &o.triehead, sizeof(triehead));
    }
    template<class okeytype, class otype, class oallocator> trie_map &operator=(trie_map<okeytype, otype, oallocator> &&o)
    {
      *static_cast<stlcontainer *>(this)=std::move(static_cast<stlcontainer &&>(o));
      memcpy(&triehead, &o.triehead, sizeof(triehead));
      return *this;
    }
#endif
    template<class inputiterator> trie_map(inputiterator s, inputiterator e) : stlcontainer(s, e) { triehead_reindex(); }
    template<class inputiterator> trie_map(inputiterator s, inputiterator e, const allocator &a) : stlcontainer(s, e, a) { triehead_reindex(); }
  };
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator!=(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)!=static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator<(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)<static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator<=(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)<=static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator==(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)==static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator>(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)>static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator>=(const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)>=static_cast<const stlcontainer &>(b);
  }

  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> class trie_multimap : protected stlcontainer, protected nobblepolicy<trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> >
  {
    typedef nobblepolicy<trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> > nobblepolicytype;
    typedef typename stlcontainer::value_type mapvaluetype;
    static const size_t trie_fieldoffset=mapvaluetype::trie_link_offset;
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> 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<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::const_iterator, 1, mapvaluetype> const_iterator;
    typedef typename stlcontainer::const_pointer const_pointer;
    typedef typename stlcontainer::const_reference const_reference;
    typedef trie_iterator<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::const_reverse_iterator, -1, mapvaluetype> const_reverse_iterator;
    typedef typename stlcontainer::difference_type difference_type;
    typedef trie_iterator<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::iterator, 1, mapvaluetype, const_iterator> iterator;
    typedef keytype key_type;
    typedef type mapped_type;
    typedef typename stlcontainer::pointer pointer;
    typedef typename stlcontainer::reference reference;
    typedef trie_iterator<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer, typename stlcontainer::reverse_iterator, -1, mapvaluetype, const_reverse_iterator> reverse_iterator;
    typedef typename stlcontainer::size_type size_type;
    typedef typename stlcontainer::value_type::trie_value_type value_type;
  private:
    trie_map_head<mapvaluetype> triehead;
    static typename mapvaluetype::trie_iterator_type &from_iterator(iterator &it)
    {
      void *_it=(void *) &it;
      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<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&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<key_type>(*(size_t *)"TRIEFINDKEYSTORE", key);
      return triefind<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<intern::findkeyfunct_t<keytype, type, mapvaluetype, keyfunct> > >(&triehead, (mapvaluetype *) buffer);
    }
    iterator triehead_insert(const value_type &val)
    {
      iterator it=iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      trieinsert<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*it)));
      return it;
    }
#ifdef HAVE_CPP0XRVALUEREFS
    iterator triehead_insert(value_type &&val)
    {
      iterator it=iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
      it->trie_iterator=from_iterator(it);
      trieinsert<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*it)));
      return it;
    }
#endif
  public:
    iterator begin() { return iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::begin()); }
    const_iterator begin() const { return const_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::begin()); }
    using stlcontainer::clear;
    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<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::end()); }
    const_iterator end() const { return const_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::end()); }
    //std::pair<iterator, iterator> equal_range(const key_type &key);
    //std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const;
    iterator erase(iterator it)
    {
      //int (*nobblefunct)(trietype *head)
      trieremove<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct>,
        // Need to give MSVC a little bit of help
#ifdef _MSC_VER
        nobblepolicytype::trie_nobblefunction<trie_map_head<mapvaluetype> >
#else
        nobblepolicytype::trie_nobblefunction
#endif
      >(&triehead, &(*it));
      return iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::erase((typename stlcontainer::iterator &) it));
    }
    iterator erase(iterator first, iterator last)
    {
      iterator ret(last); ++ret;
      for(iterator it=first; it!=last; ++it)
      {
        trieremove<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct>,
#ifdef _MSC_VER
          nobblepolicytype::trie_nobblefunction<trie_map_head<mapvaluetype> >
#else
          nobblepolicytype::trie_nobblefunction
#endif
        >(&triehead, &(*it));
        stlcontainer::erase((typename stlcontainer::iterator &) it);
      }
      return ret;
    }
    iterator find(const key_type &key) { const_iterator it=static_cast<const trie_multimap *>(this)->find(key); void *_it=(void *) &it; return *(iterator *)_it; }
    const_iterator find(const key_type &key) const
    {
      const mapvaluetype *r=triehead_find(key);
      return !r ? end() : const_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
    }
    iterator nfind(const key_type &key) { const_iterator it=static_cast<const trie_multimap *>(this)->nfind(key); void *_it=(void *) &it; return *(iterator *)_it; }
    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);
    }
    iterator cfind(const key_type &key, int rounds=INT_MAX) { const_iterator it=static_cast<const trie_multimap *>(this)->cfind(key, rounds); void *_it=(void *) &it; return *(iterator *)_it; }
    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;
    iterator insert(const value_type &val)
    {
      return triehead_insert(std::move(val));
    }
    iterator insert(iterator at, const value_type &val)
    {
      iterator it=stlcontainer::insert(at, val);
      it->trie_iterator=from_iterator(it);
      trieinsert<trie_map_head, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, &(*it));
      return it;
    }
    template<class inputiterator> void insert(inputiterator first, inputiterator last)
    {
      iterator it=--end();
      stlcontainer::insert(first, last);
      for(; it!=end(); ++it)
      {
        it->trie_iterator=from_iterator(it);
        trieinsert<trie_map_head, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&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<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::begin()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::begin()); }
    reverse_iterator rend() { return reverse_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, stlcontainer::end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) 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 keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator!=(const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator<(const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator<=(const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator==(const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator>(const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);
    template<class keytype_, class type_, class keyfunct_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator>=(const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_multimap<keytype_, type_, keyfunct_, allocator_, nobblepolicy_, stlcontainer_> &b);

    trie_multimap() : stlcontainer() { NEDTRIE_INIT(&triehead); }
    explicit trie_multimap(const allocator &a) : stlcontainer(a) { NEDTRIE_INIT(&triehead); }
    template<class okeytype, class otype, class oallocator> trie_multimap(const trie_multimap<okeytype, otype, oallocator> &o) : stlcontainer(o) { triehead_reindex(); }
    template<class okeytype, class otype, class oallocator> trie_multimap &operator=(const trie_multimap<okeytype, otype, oallocator> &o) { *static_cast<stlcontainer *>(this)=static_cast<const stlcontainer &>(o); triehead_reindex(); return *this; }
#ifdef HAVE_CPP0XRVALUEREFS
      template<class okeytype, class otype, class oallocator> trie_multimap(trie_multimap<okeytype, otype, oallocator> &&o) : stlcontainer(std::move(o))
    {
      memcpy(&triehead, &o.triehead, sizeof(triehead));
    }
    template<class okeytype, class otype, class oallocator> trie_multimap &operator=(trie_multimap<okeytype, otype, oallocator> &&o)
    {
      *static_cast<stlcontainer *>(this)=std::move(static_cast<stlcontainer &&>(o));
      memcpy(&triehead, &o.triehead, sizeof(triehead));
      return *this;
    }
#endif
    template<class inputiterator> trie_multimap(inputiterator s, inputiterator e) : stlcontainer(s, e) { triehead_reindex(); }
    template<class inputiterator> trie_multimap(inputiterator s, inputiterator e, const allocator &a) : stlcontainer(s, e, a) { triehead_reindex(); }
  };
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator!=(const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_multimap<keytype, type, allocator, keyfunct, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)!=static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator<(const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_multimap<keytype, type, allocator, keyfunct, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)<static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator<=(const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_multimap<keytype, type, allocator, keyfunct, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)<=static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator==(const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_multimap<keytype, type, allocator, keyfunct, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)==static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator>(const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_multimap<keytype, type, allocator, keyfunct, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)>static_cast<const stlcontainer &>(b);
  }
  template<class keytype, class type, class keyfunct, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator>=(const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &a, const trie_multimap<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> &b)
  {
    return static_cast<const stlcontainer &>(a)>=static_cast<const stlcontainer &>(b);
  }

#endif

} /* namespace */

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