Permalink
Switch branches/tags
Find file
Fetching contributors…
Cannot retrieve contributors at this time
1673 lines (1610 sloc) 64.9 KB
/* An in-place binary trie implementation for C and C++ aka. the
ridiculously fast way of indexing stuff. (C) 2010 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>
#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) { return 0; } \
static INLINE int name##_nobbleones(struct name *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 */
#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 *trieNfind(const trietype *RESTRICT head, const type *RESTRICT r)
{
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;
for(;;node=childnode)
{
nodelink=(const TrieLink_t<type> *RESTRICT)((size_t) node + fieldoffset);
nodekey=keyfunct(node);
if(nodekey>=rkey && nodekey-rkey<retkey)
{
ret=node;
if(!(retkey=nodekey-rkey)) goto end;
}
keybit>>=1;
keybitset=!!(rkey&keybit);
childnode=nodelink->trie_child[keybitset];
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++;
rkey=0;
continue;
}
} while(!ret);
end:
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_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 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; \
for(;;node=childnode) \
{ \
nodekey=keyfunct(node); \
if(nodekey>=rkey && nodekey-rkey<retkey) \
{ \
ret=node; \
if(!(retkey=nodekey-rkey)) goto end; \
} \
keybit>>=1; \
keybitset=!!(rkey&keybit); \
childnode=node->field.trie_child[keybitset]; \
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++; \
rkey=0; \
continue; \
} \
} while(!ret); \
end: \
return ret->field.trie_next ? ret->field.trie_next : 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 */
#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, 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, 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 *trieprev(const trietype *RESTRICT head, const type *RESTRICT r)
{
const type *RESTRICT node=0, *RESTRICT child;
const TrieLink_t<type> *RESTRICT nodelink, *RESTRICT rlink;
unsigned bitidx;
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];
goto returnbottomofchild;
}
/* If I was already on child[0] or there are no more children, return this node */
goto returnendleaf;
}
/* 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;
returnbottomofchild:
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);
}
returnendleaf:
/* 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_PREV(struct name *RESTRICT head, struct type *RESTRICT r) \
{ \
struct type *RESTRICT node=0, *RESTRICT child; \
unsigned bitidx; \
\
/* 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]; \
goto returnbottomofchild; \
} \
/* If I was already on child[0] or there are no more children, return this node */ \
goto returnendleaf; \
} \
/* 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; \
returnbottomofchild: \
/* Follow child[1] preferentially downwards */ \
while((child=node->field.trie_child[1] ? node->field.trie_child[1] : node->field.trie_child[0])) \
{ \
node=child; \
} \
returnendleaf: \
/* 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 *trienext(const trietype *RESTRICT head, const type *RESTRICT r)
{
const type *RESTRICT node;
const TrieLink_t<type> *RESTRICT nodelink, *RESTRICT rlink;
unsigned bitidx;
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, so on to next 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;
return (type *) node;
}
}
#endif /* __cplusplus */
#if 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) \
{ \
struct type *RESTRICT node; \
unsigned bitidx; \
\
/* 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; \
} \
/* 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 */
/*! \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_NFIND (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) \
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_NFIND
\brief Finds the item with the nearest (larger or equal) key to y in nedtrie x.
*/
#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.
*/
#define NEDTRIE_FOREACH(x, name, head) \
for ((x) = NEDTRIE_MIN(name, head); \
(x) != NULL; \
(x) = NEDTRIE_NEXT(name, head, x))
/*! \def NEDTRIE_FOREACH_REVERSE
\brief Substitutes a for loop which forward iterates into x all items in nedtrie head.
*/
#define NEDTRIE_FOREACH_REVERSE(x, name, head) \
for ((x) = NEDTRIE_MAX(name, head); \
(x) != NULL; \
(x) = NEDTRIE_PREV(name, head, x))
/*! \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
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(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 type, class iteratortype> struct trie_maptype;
template<class type, class iteratortype> size_t trie_maptype_keyfunct(const trie_maptype<type, iteratortype> *);
template<class keytype, class type,
class allocator=std::allocator<trie_maptype<std::pair<keytype, type>, std::list<size_t>::iterator> >,
template<class> class nobblepolicy=nedpolicy::nobblezeros,
class stlcontainer=std::list<trie_maptype<std::pair<keytype, type>, std::list<size_t>::iterator> > > class trie_map;
/*! \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.
*/
template<class type, class iteratortype> struct trie_maptype
{
private:
template<class keytype, class type_, class allocator, template<class> class nobblepolicy, class stlcontainer> friend class trie_map;
template<class type_, class iteratortype_> friend size_t trie_maptype_keyfunct(const trie_maptype<type_, iteratortype_> *);
typedef type trie_value_type;
typedef iteratortype trie_iterator_type;
type trie_value;
iteratortype trie_iterator;
TrieLink_t<type> trie_link;
static const size_t trie_link_offset=sizeof(type)+sizeof(iteratortype); // GCC won't accept offsetof() as a template argument sadly :(
public:
trie_maptype(const type &v) : trie_value(v) { }
template<class otype, class oittype> trie_maptype(const trie_maptype<otype, oittype> &o) : trie_value(o.trie_value) { }
#ifdef HAVE_CPP0XRVALUEREFS
template<class otype, class oittype> trie_maptype(trie_maptype<otype, oittype> &&o) : trie_value(std::move(o.trie_value)) { }
#endif
//! Silent const lvalue converter for type
operator const type &() const { return trie_value; }
};
template<class type, class iteratortype> size_t trie_maptype_keyfunct(const trie_maptype<type, iteratortype> *v)
{
return v->trie_value.first;
}
/*! \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 allocator, template<class> class nobblepolicy, class stlcontainer> class trie_map : protected stlcontainer, protected nobblepolicy<trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> >
{
typedef nobblepolicy<trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> > nobblepolicytype;
typedef typename stlcontainer::value_type mapvaluetype;
static const size_t trie_fieldoffset=mapvaluetype::trie_link_offset;
public:
typedef typename stlcontainer::allocator_type allocator_type;
typedef typename stlcontainer::const_iterator const_iterator;
typedef typename stlcontainer::const_pointer const_pointer;
typedef typename stlcontainer::const_reference const_reference;
typedef typename stlcontainer::const_reverse_iterator const_reverse_iterator;
typedef typename stlcontainer::difference_type difference_type;
typedef typename stlcontainer::iterator iterator;
typedef keytype key_type;
typedef type mapped_type;
typedef typename stlcontainer::pointer pointer;
typedef typename stlcontainer::reference reference;
typedef typename stlcontainer::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 const_iterator &to_iterator(const typename mapvaluetype::trie_iterator_type &it)
{
void *_it=(void *) &it;
return *(const_iterator *)_it;
}
static iterator &to_iterator(typename mapvaluetype::trie_iterator_type &it)
{
void *_it=(void *) &it;
return *(iterator *)_it;
}
static typename mapvaluetype::trie_iterator_type &from_iterator(iterator &it)
{
void *_it=(void *) &it;
return *(typename mapvaluetype::trie_iterator_type *)_it;
}
// Wipes and resets the nedtrie index
void triehead_reindex()
{
NEDTRIE_INIT(&triehead);
for(iterator it=begin(); it!=end(); ++it)
{
trieinsert<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, trie_maptype_keyfunct>(&triehead, &(*it));
it->trie_iterator=it;
}
}
const mapvaluetype *triehead_find(const key_type &key) const
{ // Avoid a value_type construction
char buffer[sizeof(mapvaluetype)];
mapvaluetype *RESTRICT r=(mapvaluetype *RESTRICT) buffer;
r->trie_value.first=key;
return triefind<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, trie_maptype_keyfunct>(&triehead, r);
}
iterator triehead_insert(const value_type &val)
{
iterator it=stlcontainer::insert(end(), std::move(val));
it->trie_iterator=from_iterator(it);
trieinsert<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, trie_maptype_keyfunct>(&triehead, &(*it));
return it;
}
#ifdef HAVE_CPP0XRVALUEREFS
iterator triehead_insert(value_type &&val)
{
iterator it=stlcontainer::insert(end(), std::move(val));
it->trie_iterator=from_iterator(it);
trieinsert<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, trie_maptype_keyfunct>(&triehead, &(*it));
return it;
}
#endif
public:
using 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;
using 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, trie_maptype_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 stlcontainer::erase(it);
}
//! Removes the items between \em first and \em last from the container
iterator erase(iterator first, iterator last)
{
for(iterator it=first; it!=last; ++it)
{
trieremove<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, trie_maptype_keyfunct,
#ifdef _MSC_VER
nobblepolicytype::trie_nobblefunction<trie_map_head<mapvaluetype> >
#else
nobblepolicytype::trie_nobblefunction
#endif
>(&triehead, &(*it));
}
return stlcontainer::erase(first, last);
}
//! 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 *) &it; 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() : to_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(val.trie_value.first));
if(r)
{
r->trie_value=std::move(val.trie_value);
return std::make_pair(to_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, trie_maptype_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, trie_maptype_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;
using stlcontainer::rbegin;
using stlcontainer::rend;
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=r ? to_iterator(r->trie_iterator) : triehead_insert(std::move(value_type(key, std::move(type()))));
return it->trie_value.second;
}
template<class keytype_, class type_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator!=(const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &b);
template<class keytype_, class type_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator<(const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &b);
template<class keytype_, class type_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator<=(const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &b);
template<class keytype_, class type_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator==(const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &b);
template<class keytype_, class type_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator>(const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &b);
template<class keytype_, class type_, class allocator_, template<class> class nobblepolicy_, class stlcontainer_> friend bool operator>=(const trie_map<keytype_, type_, allocator_, nobblepolicy_, stlcontainer_> &a, const trie_map<keytype_, type_, 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 allocator, template<class> class nobblepolicy, class stlcontainer> bool operator!=(const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &b)
{
return static_cast<const stlcontainer &>(a)!=static_cast<const stlcontainer &>(b);
}
template<class keytype, class type, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator<(const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &b)
{
return static_cast<const stlcontainer &>(a)<static_cast<const stlcontainer &>(b);
}
template<class keytype, class type, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator<=(const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &b)
{
return static_cast<const stlcontainer &>(a)<=static_cast<const stlcontainer &>(b);
}
template<class keytype, class type, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator==(const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &b)
{
return static_cast<const stlcontainer &>(a)==static_cast<const stlcontainer &>(b);
}
template<class keytype, class type, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator>(const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &b)
{
return static_cast<const stlcontainer &>(a)>static_cast<const stlcontainer &>(b);
}
template<class keytype, class type, class allocator, template<class> class nobblepolicy, class stlcontainer> bool operator>=(const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &a, const trie_map<keytype, type, allocator, nobblepolicy, stlcontainer> &b)
{
return static_cast<const stlcontainer &>(a)>=static_cast<const stlcontainer &>(b);
}
} /* namespace */
#ifdef _MSC_VER
#pragma warning(pop)
#endif
#endif