/* 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 <stdlib.h>
#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
/*! \def RESTRICT
\brief Defined to the restrict keyword or equivalent if available */
#ifndef RESTRICT
#if __STDC_VERSION__ >= 199901L /* C99 or better */
#define RESTRICT restrict
#else
#if defined(_MSC_VER) && _MSC_VER>=1400
#define RESTRICT __restrict
#endif
#ifdef __GNUC__
#define RESTRICT __restrict
#endif
#endif
#ifndef RESTRICT
#define RESTRICT
#endif
#endif
/*! \def INLINE
\brief Defined to the inline keyword or equivalent if available */
#ifndef INLINE
#if __STDC_VERSION__ >= 199901L /* C99 or better */ || defined(__cplusplus)
#define INLINE inline
#else
#if defined(_MSC_VER)
#define INLINE __inline
#endif
#ifdef __GNUC__
#define INLINE __inline
#endif
#endif
#ifndef INLINE
#define INLINE
#endif
#endif
/*! \def NOINLINE
\brief Defined to whatever compiler magic inhibits inlining if available */
#ifndef NOINLINE
#if defined(__GNUC__)
#define NOINLINE __attribute__ ((noinline))
#elif defined(_MSC_VER)
#define NOINLINE __declspec(noinline)
#else
#define NOINLINE
#endif
#endif
/*! \def DEBUGINLINE
\brief Defined to be INLINE when NDEBUG is defined, NOINLINE when DEBUG is defined, unset otherwise.
*/
#ifndef DEBUGINLINE
#ifdef NDEBUG
#define DEBUGINLINE INLINE
#elif defined(DEBUG)
#define DEBUGINLINE NOINLINE
#else
#define DEBUGINLINE
#endif
#endif
/*! \def NEDTRIEUSEMACROS
\brief Define to 1 to force usage of the macro implementation of nedtries. This is always 1 when
compiling in C, but defaults to 0 when compiling in C++ as a template function implementation offers
much more scope to the optimiser and is much easier to debug.
*/
#ifndef NEDTRIEUSEMACROS
#ifdef __cplusplus
#define NEDTRIEUSEMACROS 0
#else
#define NEDTRIEUSEMACROS 1
#endif
#endif
/*! \def NEDTRIEDEBUG
\brief Define to 1 if you wish a full trie validation to be performed every time you modify the trie.
Requires assert() to work, so disables itself if NDEBUG is defined.
*/
#ifndef NEDTRIEDEBUG
#ifdef DEBUG
#define NEDTRIEDEBUG 1
#else
#define NEDTRIEDEBUG 0
#endif
#endif
#ifdef NDEBUG
#undef NEDTRIEDEBUG
#define NEDTRIEDEBUG 0
#endif
/* Define bit scanning intrinsics */
#ifdef _MSC_VER
#include <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
/* This is a generic 32 and 64 bit compatible branch free bitscan right */
size_t x=value;
const size_t allbits1=~(size_t)0;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
if(8==sizeof(x)) x = x | (x >>32);
x = ~x;
x = x - ((x >> 1) & (allbits1/3));
x = (x & (allbits1/15*3)) + ((x >> 2) & (allbits1/15*3));
x = ((x + (x >> 4)) & (allbits1/255*15)) * (allbits1/255);
x = (8*sizeof(x)-1) - (x >> (8*(sizeof(x)-1)));
return (unsigned) x;
#endif
#endif
}
#ifdef __cplusplus
} /* Anonymous namespace */
#endif
/*! \def NEDTRIE_INDEXBINS
\brief Defines the number of top level bit bins to use. The default based on size_t is usually fine.
*/
#define NEDTRIE_INDEXBINS (8*sizeof(void *))
/*! \def NEDTRIE_HEAD
\brief Substitutes the type used to store the head of the trie.
*/
#define NEDTRIE_HEAD2(name, type) \
struct name { \
size_t count; \
type *triebins[NEDTRIE_INDEXBINS]; /* each containing (1<<x)<=bitscanrev(x)<(1<<(x+1)) */ \
int nobbledir; \
}
#define NEDTRIE_HEAD(name, type) NEDTRIE_HEAD2(name, struct type)
/*! \def NEDTRIE_ENTRY
\brief Substitutes the type used to store the per-node trie information. Occupies 5*sizeof(size_t).
*/
#define NEDTRIE_ENTRY(type) \
struct { \
struct type *trie_parent; /* parent element */ \
struct type *trie_child[2]; /* my children based on whether they are zero or one. */ \
struct type *trie_prev, *trie_next; /* my siblings of identical key to me. */ \
}
#define NEDTRIE_INITIALIZER(root)
/*! \def NEDTRIE_INIT
\brief Initialises a nedtrie for usage.
*/
#define NEDTRIE_INIT(root) do { memset((root), 0, sizeof(*(root))); } while(0)
/*! \def NEDTRIE_EMPTY
\brief Returns whether a nedtrie is empty.
*/
#define NEDTRIE_EMPTY(head) (!(head)->count)
/*! \def NEDTRIE_COUNT
\brief Returns the number of items in a nedtrie.
*/
#define NEDTRIE_COUNT(head) ((head)->count)
/* As macro instantiated code is a royal PITA to debug and even to see what
the hell is going on, we use a templated implementation when in C++. This
aids future debuggability by keeping the template and macro implementations
side by side and hopefully harmonised. */
#ifdef __cplusplus
namespace nedtries {
template<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);
}
/*! \def NEDTRIE_NOBBLEZEROS
\brief A nobble function which preferentially nobbles zeros.
*/
#define NEDTRIE_NOBBLEZEROS(name) nedtries::trienobblezeros<name>
/*! \def NEDTRIE_NOBBLEONES
\brief A nobble function which preferentially nobbles ones.
*/
#define NEDTRIE_NOBBLEONES(name) nedtries::trienobbleones<name>
/*! \def NEDTRIE_NOBBLEEQUALLY
\brief A nobble function which alternates between nobbling zeros and ones.
*/
#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))) 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 */
/*! \def NEDTRIE_GENERATE
\brief Substitutes a set of nedtrie implementation function definitions specialised according to type.
*/
#define NEDTRIE_GENERATE(proto, name, type, field, keyfunct, nobblefunct) \
NEDTRIE_GENERATE_NOBBLES (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_INSERT (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_REMOVE (proto, name, type, field, keyfunct, nobblefunct) \
NEDTRIE_GENERATE_FIND (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_CFIND (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_MINMAX (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_PREV (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_NEXT (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_NFIND (proto, name, type, field, keyfunct) \
proto INLINE struct type * name##_NEDTRIE_PREVLEAF(struct type *r) { return (r)->field.trie_prev; } \
proto INLINE struct type * name##_NEDTRIE_NEXTLEAF(struct type *r) { return (r)->field.trie_next; }
/*! \def NEDTRIE_INSERT
\brief Inserts item y into nedtrie x.
*/
#define NEDTRIE_INSERT(name, x, y) name##_NEDTRIE_INSERT(x, y)
/*! \def NEDTRIE_REMOVE
\brief Removes item y from nedtrie x.
*/
#define NEDTRIE_REMOVE(name, x, y) name##_NEDTRIE_REMOVE(x, y)
/*! \def NEDTRIE_FIND
\brief Finds the item with the same key as y in nedtrie x.
*/
#define NEDTRIE_FIND(name, x, y) name##_NEDTRIE_FIND(x, y)
/*! \def NEDTRIE_EXACTFIND
\brief Returns true if there is an item with the same key and address as y in nedtrie x.
*/
#define NEDTRIE_EXACTFIND(name, x, y) name##_NEDTRIE_EXACTFIND(x, y)
/*! \def NEDTRIE_CFIND
\brief Performs \em rounds number of attempts to find an item with an equal key to y in nedtrie x, and
if none equal then the closest item with a larger key. Always returns a larger key if there is a larger
key in the trie, if there isn't it returns zero. Think of rounds as how closely you want the find to fit
the requested key, so \c INT_MAX means "as close as possible". Note that Cfind does NOT guarantee that
the item returned is the next largest keyed item, use Nfind for that.
*/
#define NEDTRIE_CFIND(name, x, y, rounds) name##_NEDTRIE_CFIND(x, y, rounds)
/*! \def NEDTRIE_NFIND
\brief Finds an item with an equal key to y in nedtrie x, and if none equal then the item with the next
largest key. If the key is not equal, the returned item is guaranteed to be the next largest keyed item.
*/
#define NEDTRIE_NFIND(name, x, y) name##_NEDTRIE_NFIND(x, y)
/*! \def NEDTRIE_PREV
\brief Returns the item preceding y in nedtrie x.
*/
#define NEDTRIE_PREV(name, x, y) name##_NEDTRIE_PREV(x, y)
/*! \def NEDTRIE_NEXT
\brief Returns the item following y in nedtrie x.
*/
#define NEDTRIE_NEXT(name, x, y) name##_NEDTRIE_NEXT(x, y)
/*! \def NEDTRIE_PREVLEAF
\brief Returns the item with an identical key preceding y in nedtrie x.
*/
#define NEDTRIE_PREVLEAF(name, x) name##_NEDTRIE_PREVLEAF(x)
/*! \def NEDTRIE_NEXTLEAF
\brief Returns the item with an identical key following y in nedtrie x.
*/
#define NEDTRIE_NEXTLEAF(name, x) name##_NEDTRIE_NEXTLEAF(x)
/*! \def NEDTRIE_MIN
\brief Returns the lowest item in nedtrie x. This item will approximately have the smallest key.
*/
#define NEDTRIE_MIN(name, x) name##_NEDTRIE_MINMAX(x, 0)
/*! \def NEDTRIE_MAX
\brief Returns the highest item in nedtrie x. This item will approximately have the biggest key.
*/
#define NEDTRIE_MAX(name, x) name##_NEDTRIE_MINMAX(x, 1)
/*! \def NEDTRIE_FOREACH
\brief Substitutes a for loop which forward iterates into x all items in nedtrie head. Order of
items is mostly in key order (enough that a bubble sort is efficient).
*/
#define NEDTRIE_FOREACH(x, name, head) \
for ((x) = NEDTRIE_MIN(name, head); \
(x) != NULL; \
(x) = NEDTRIE_NEXT(name, head, x))
/*! \def NEDTRIE_FOREACH_SAFE
\brief Substitutes a for loop which forward iterates into x all items in
nedtrie head and is safe against removal of x. Order of items is mostly
in key order (enough that a bubble sort is efficient).
*/
#define NEDTRIE_FOREACH_SAFE(x, name, head, y) \
for ((x) = NEDTRIE_MIN(name, head); \
(x) != NULL && ((y) = NEDTRIE_NEXT(name, head, x), 1); \
(x) = (y))
/*! \def NEDTRIE_FOREACH_REVERSE
\brief Substitutes a for loop which reverse iterates into x all items in nedtrie head. Order of
items is mostly inverse to key order (enough that a bubble sort is efficient).
*/
#define NEDTRIE_FOREACH_REVERSE(x, name, head) \
for ((x) = NEDTRIE_MAX(name, head); \
(x) != NULL; \
(x) = NEDTRIE_PREV(name, head, x))
/*! \def NEDTRIE_FOREACH_REVERSE_SAFE
\brief Substitutes a for loop which reverse iterates into x all items in nedtrie head and is
safe against removal of x. Order of items is mostly inverse to key order (enough that a bubble
sort is efficient).
*/
#define NEDTRIE_FOREACH_REVERSE_SAFE(x, name, head, y) \
for ((x) = NEDTRIE_MAX(name, head); \
(x) != NULL && ((y) = NEDTRIE_PREV(name, head, x), 1); \
(x) = (y))
/*! \def NEDTRIE_HASNODEHEADER
\brief Returns true if this item's node header is active. Useful as a quick check for whether a node is in some trie.
*/
#define NEDTRIE_HASNODEHEADER(treevar, node, link) ((node)->link.trie_parent || (node)->link.trie_prev)
#ifdef __cplusplus
#include <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(((((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>=(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 */
}
/*! \def HAVE_CPP0XRVALUEREFS
\ingroup C++
\brief Enables rvalue references
Define to enable the usage of rvalue references which enables move semantics and
other things. Automatically defined if __cplusplus indicates a C++0x compiler,
otherwise you'll need to set it yourself.
*/
#if __cplusplus > 199711L || (defined(_MSC_VER) && _MSC_VER>=1600) || defined(HAVE_CPP0X) /* Do we have C++0x? */
#undef HAVE_CPP0XRVALUEREFS
#define HAVE_CPP0XRVALUEREFS 1
#undef HAVE_CPP0XTYPETRAITS
#define HAVE_CPP0XTYPETRAITS 1
#endif
/*! \brief The policy namespace in which all nedtries policies live. */
namespace nedpolicy
{
/*! \class nobblezeros
\brief A policy nobbling zeros
*/
template<class triemaptype> class nobblezeros
{
protected:
template<class trietype> static int trie_nobblefunction(trietype *)
{
return 0;
}
};
/*! \class nobbleones
\brief A policy nobbling ones
*/
template<class triemaptype> class nobbleones
{
protected:
template<class trietype> static int trie_nobblefunction(trietype *)
{
return 1;
}
};
/*! \class nobbleequally
\brief A policy nobbling zeros and ones equally
*/
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;
/*! \struct trie_keyfunct
\ingroup C++
\brief Calculates the key for a given instance of type
You only really need to use this if you are using trie_multimap or trie_map without the operator[]
override. If using with trie_map, make sure you force the use of trie_keyfunct in its template
parameters as it defaults to an internal thunk type used to indirect access to an embedded key store.
Specialise this as follows for your type:
\code
namespace nedtries {
template<> struct trie_keyfunct<yourtype> : public std::unary_function<yourtype, size_t>
{
size_t operator()(const yourtype *RESTRICT v) const
{
return v->yourtypekeyvalue;
}
};
}
\endcode
*/
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;
/*! \struct trie_maptype
\ingroup C++
\brief Encapsulates the nedtrie metadata with the given type
Note that the nedtrie metadata is kept \em after the typed value - this prevents the nedtrie metadata interfering
with any special data alignment you might be using from a specialised STL allocator.
*/
namespace fake {
template<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
//! Silent const lvalue converter for type
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
//! Silent const lvalue converter for type
operator const type &() const { return trie_value; }
};
/*! \class trie_iterator
\ingroup C++
\brief Iterator for the trie_map and trie_multimap containers
*/
template<class 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);
}
};
}
/*! \class trie_map
\ingroup C++
\brief A STL container wrapper using nedtries to map keys to values.
This class can be used to wrap any arbitrary STL container with nedtrie associativity. For example, if you
had a std::vector<> list of items, you could add nedtrie's fast nearly constant time algorithm for accessing them -
though one would expect that a std::list<> would be the most common combination. There is no strict reason why
one could not wrap std::unordered_map<>, though what one would gain is hard to imagine!
Usage in the simplest sense is like this as the default template parameters use std::list<> as the underlying
container:
\code
trie_map<size_t, Foo> fooMap;
fooMap[5]=Foo();
fooMap.erase(fooMap.find(5));
\endcode
Unlike a proper STL container implementation, this wrapper is very much a hack in the sense that it's a very quick
and dirty way of implementing lots of nedtrie based STL containers at once. In this sense it does require its user
to not be stupid, and to know what they're doing. STL containers go out of their way to enforce correctness - well,
this wrapper most certainly does not. If you want to blow off your own foot, this implementation won't stop you!
For example, despite the protected STL container inheritance, all common STL functions are made public so you
can if you want easily corrupt the internal state. Equally, if you know what you are doing you can pass in the
wrapper as a const version of its underlying STL container by reintrpret_cast<>-ing it. Despite this, the wrapper
is fairly typesafe in that its design won't introduce subtle bugs or cause existing code to magically break itself.
If you would like a more proper bitwise trie STL container class implemented, or would like to be advised on any
algorithmic problems from which your IT project may be suffering, my consulting company <a
href="http://www.nedproductions.biz/">ned Productions Consulting Ltd</a> would be happy to advise. In particular
I would love to see a full bitwise trie implementation submitted to the Boost C++ libraries but I don't have the
unpaid time to devote to such an endeavour sadly.
\warning If you use std::vector<> as the STL container, make SURE you resize() it to its maximum size before use.
Otherwise the iterators trie_map uses to link nedtrie items into the STL items will become invalidated on storage
expansion.
*/
template<class 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 *) ⁢
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;
//! Returns the number of items with the key \em key
size_type count(const key_type &key) const
{
size_type ret=0;
const mapvaluetype *r=triehead_find(key);
if(r)
{
if(r->trie_link.prev) r=r->trie_link.trie_prev;
for(; r; r=r->trie_link.trie_next) ret++;
}
return ret;
}
using stlcontainer::empty;
iterator end() { return iterator(this, stlcontainer::end()); }
const_iterator end() const { return const_iterator(this, stlcontainer::end()); }
//std::pair<iterator, iterator> equal_range(const key_type &key);
//std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const;
//! Removes the item specified by \em it from the container
iterator erase(iterator it)
{
//int (*nobblefunct)(trietype *head)
trieremove<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));
}
//! Removes the items between \em first and \em last from the container
iterator erase(iterator first, iterator last)
{
iterator ret(last); ++ret;
for(iterator it=first; it!=last; ++it)
{
trieremove<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;
}
//! Finds the item with key \em key
iterator find(const key_type &key) { const_iterator it=static_cast<const trie_map *>(this)->find(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
//! Finds the item with key \em key
const_iterator find(const key_type &key) const
{
const mapvaluetype *r=triehead_find(key);
return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator); // type pun safe
}
//! Finds the nearest item with key \em key
iterator nfind(const key_type &key) { const_iterator it=static_cast<const trie_map *>(this)->nfind(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
//! Finds the nearest item with key \em key
const_iterator nfind(const key_type &key) const
{
const mapvaluetype *r=triehead_nfind(key);
return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
}
//! Finds the closest item with key \em key trying up to \em rounds times
iterator cfind(const key_type &key, int rounds=INT_MAX) { const_iterator it=static_cast<const trie_map *>(this)->cfind(key, rounds); void *_it=(void *) ⁢ return *(iterator *)_it; }
//! Finds the closest item with key \em key trying up to \em rounds times
const_iterator cfind(const key_type &key, int rounds=INT_MAX) const
{
const mapvaluetype *r=triehead_cfind(key, rounds);
return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
}
using stlcontainer::get_allocator;
//! Inserts the item \em val
std::pair<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);
}
//! Inserts the item \em val at position \em at
iterator insert(iterator at, const value_type &val)
{
iterator it=stlcontainer::insert(at, val);
it->trie_iterator=from_iterator(it);
trieinsert<trie_map_head, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, &(*it));
return it;
}
//! Inserts the items between \em first and \em last
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;
//! Returns an lvalue reference to the item with key \em key
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);
//! Constructs a trie_map. Has all the typical STL overloads
trie_map() : stlcontainer() { NEDTRIE_INIT(&triehead); }
explicit trie_map(const allocator &a) : stlcontainer(a) { NEDTRIE_INIT(&triehead); }
template<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);
}
/*! \class trie_multimap
\ingroup C++
\brief A STL container wrapper using nedtries to map keys to values.
This class can be used to wrap any arbitrary STL container with nedtrie associativity. For example, if you
had a std::vector<> list of items, you could add nedtrie's fast nearly constant time algorithm for accessing them -
though one would expect that a std::list<> would be the most common combination. There is no strict reason why
one could not wrap std::unordered_map<>, though what one would gain is hard to imagine!
Usage in the simplest sense is like this as the default template parameters use std::list<> as the underlying
container:
\code
trie_multimap<size_t, Foo> fooMap;
fooMap[5]=Foo();
fooMap.erase(fooMap.find(5));
\endcode
Unlike a proper STL container implementation, this wrapper is very much a hack in the sense that it's a very quick
and dirty way of implementing lots of nedtrie based STL containers at once. In this sense it does require its user
to not be stupid, and to know what they're doing. STL containers go out of their way to enforce correctness - well,
this wrapper most certainly does not. If you want to blow off your own foot, this implementation won't stop you!
For example, despite the protected STL container inheritance, all common STL functions are made public so you
can if you want easily corrupt the internal state. Equally, if you know what you are doing you can pass in the
wrapper as a const version of its underlying STL container by reintrpret_cast<>-ing it. Despite this, the wrapper
is fairly typesafe in that its design won't introduce subtle bugs or cause existing code to magically break itself.
If you would like a more proper bitwise trie STL container class implemented, or would like to be advised on any
algorithmic problems from which your IT project may be suffering, my consulting company <a
href="http://www.nedproductions.biz/">ned Productions Consulting Ltd</a> would be happy to advise. In particular
I would love to see a full bitwise trie implementation submitted to the Boost C++ libraries but I don't have the
unpaid time to devote to such an endeavour sadly.
\warning If you use std::vector<> as the STL container, make SURE you resize() it to its maximum size before use.
Otherwise the iterators trie_multimap uses to link nedtrie items into the STL items will become invalidated on storage
expansion.
*/
template<class 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 *) ⁢
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;
//! Returns the number of items with the key \em key
size_type count(const key_type &key) const
{
size_type ret=0;
const mapvaluetype *r=triehead_find(key);
if(r)
{
if(r->trie_link.prev) r=r->trie_link.trie_prev;
for(; r; r=r->trie_link.trie_next) ret++;
}
return ret;
}
using stlcontainer::empty;
iterator end() { return iterator((trie_map<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;
//! Removes the item specified by \em it from the container
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));
}
//! Removes the items between \em first and \em last from the container
iterator erase(iterator first, iterator last)
{
iterator ret(last); ++ret;
for(iterator it=first; it!=last; ++it)
{
trieremove<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;
}
//! Finds the item with key \em key
iterator find(const key_type &key) { const_iterator it=static_cast<const trie_multimap *>(this)->find(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
//! Finds the item with key \em key
const_iterator find(const key_type &key) const
{
const mapvaluetype *r=triehead_find(key);
return !r ? end() : const_iterator((trie_map<keytype, type, keyfunct, allocator, nobblepolicy, stlcontainer> *) this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
}
//! Finds the nearest item with key \em key
iterator nfind(const key_type &key) { const_iterator it=static_cast<const trie_multimap *>(this)->nfind(key); void *_it=(void *) ⁢ return *(iterator *)_it; }
//! Finds the nearest item with key \em key
const_iterator nfind(const key_type &key) const
{
const mapvaluetype *r=triehead_nfind(key);
return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
}
//! Finds the closest item with key \em key trying up to \em rounds times
iterator cfind(const key_type &key, int rounds=INT_MAX) { const_iterator it=static_cast<const trie_multimap *>(this)->cfind(key, rounds); void *_it=(void *) ⁢ return *(iterator *)_it; }
//! Finds the closest item with key \em key trying up to \em rounds times
const_iterator cfind(const key_type &key, int rounds=INT_MAX) const
{
const mapvaluetype *r=triehead_cfind(key, rounds);
return !r ? end() : const_iterator(this, (const typename stlcontainer::const_iterator &) r->trie_iterator);
}
using stlcontainer::get_allocator;
//! Inserts the item \em val
iterator insert(const value_type &val)
{
return triehead_insert(std::move(val));
}
//! Inserts the item \em val at position \em at
iterator insert(iterator at, const value_type &val)
{
iterator it=stlcontainer::insert(at, val);
it->trie_iterator=from_iterator(it);
trieinsert<trie_map_head, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, &(*it));
return it;
}
//! Inserts the items between \em first and \em last
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);
//! Constructs a trie_multimap. Has all the typical STL overloads
trie_multimap() : stlcontainer() { NEDTRIE_INIT(&triehead); }
explicit trie_multimap(const allocator &a) : stlcontainer(a) { NEDTRIE_INIT(&triehead); }
template<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);
}
} /* namespace */
#ifdef _MSC_VER
#pragma warning(pop)
#endif
#endif