nedtries  v1.03 trunk (?)
nedtrie.h File Reference
#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <list>
#include <functional>

Go to the source code of this file.

Classes

struct  nedtries::TrieLink_t< type >
 
struct  nedtries::testtrielinksize::foo1
 
struct  nedtries::testtrielinksize::foo2
 
struct  nedtries::TrieValidityState_t
 

Namespaces

 nedtries
 
 nedtries::testtrielinksize
 

Macros

#define RESTRICT
 Defined to the restrict keyword or equivalent if available. More...
 
#define INLINE   inline
 Defined to the inline keyword or equivalent if available. More...
 
#define NOINLINE
 Defined to whatever compiler magic inhibits inlining if available. More...
 
#define DEBUGINLINE
 Defined to be INLINE when NDEBUG is defined, NOINLINE when DEBUG is defined, unset otherwise. More...
 
#define NEDTRIEUSEMACROS   0
 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. More...
 
#define NEDTRIEDEBUG   0
 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. More...
 
#define NEDTRIE_INDEXBINS   (8*sizeof(void *))
 Defines the number of top level bit bins to use. The default based on size_t is usually fine. More...
 
#define NEDTRIE_HEAD2(name, type)
 
#define NEDTRIE_HEAD(name, type)   NEDTRIE_HEAD2(name, struct type)
 Substitutes the type used to store the head of the trie. More...
 
#define NEDTRIE_ENTRY(type)
 Substitutes the type used to store the per-node trie information. Occupies 5*sizeof(size_t). More...
 
#define NEDTRIE_INITIALIZER(root)
 
#define NEDTRIE_INIT(root)   do { memset((root), 0, sizeof(*(root))); } while(0)
 Initialises a nedtrie for usage. More...
 
#define NEDTRIE_EMPTY(head)   (!(head)->count)
 Returns whether a nedtrie is empty. More...
 
#define NEDTRIE_COUNT(head)   ((head)->count)
 Returns the number of items in a nedtrie. More...
 
#define NEDTRIE_NOBBLEZEROS(name)    nedtries::trienobblezeros<name>
 A nobble function which preferentially nobbles zeros. More...
 
#define NEDTRIE_NOBBLEONES(name)    nedtries::trienobbleones<name>
 A nobble function which preferentially nobbles ones. More...
 
#define NEDTRIE_NOBBLEEQUALLY(name)   nedtries::trienobbleequally<name>
 A nobble function which alternates between nobbling zeros and ones. More...
 
#define NEDTRIE_GENERATE_NOBBLES(proto, name, type, field, keyfunct)
 
#define NEDTRIEFIELDOFFSET2(type, field)   ((size_t) &(((type *)0)->field))
 
#define NEDTRIEFIELDOFFSET(type, field)   NEDTRIEFIELDOFFSET2(struct type, field)
 
#define NEDTRIE_GENERATE_INSERT(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_REMOVE(proto, name, type, field, keyfunct, nobblefunct)
 
#define NEDTRIE_GENERATE_FIND(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_CFIND(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_MINMAX(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_PREV(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_NEXT(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE_NFIND(proto, name, type, field, keyfunct)
 
#define NEDTRIE_GENERATE(proto, name, type, field, keyfunct, nobblefunct)
 Substitutes a set of nedtrie implementation function definitions specialised according to type. More...
 
#define NEDTRIE_INSERT(name, x, y)    name##_NEDTRIE_INSERT(x, y)
 Inserts item y into nedtrie x. More...
 
#define NEDTRIE_REMOVE(name, x, y)    name##_NEDTRIE_REMOVE(x, y)
 Removes item y from nedtrie x. More...
 
#define NEDTRIE_FIND(name, x, y)    name##_NEDTRIE_FIND(x, y)
 Finds the item with the same key as y in nedtrie x. More...
 
#define NEDTRIE_EXACTFIND(name, x, y)    name##_NEDTRIE_EXACTFIND(x, y)
 Returns true if there is an item with the same key and address as y in nedtrie x. More...
 
#define NEDTRIE_CFIND(name, x, y, rounds)   name##_NEDTRIE_CFIND(x, y, rounds)
 Performs 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 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. More...
 
#define NEDTRIE_NFIND(name, x, y)    name##_NEDTRIE_NFIND(x, y)
 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. More...
 
#define NEDTRIE_PREV(name, x, y)    name##_NEDTRIE_PREV(x, y)
 Returns the item preceding y in nedtrie x. More...
 
#define NEDTRIE_NEXT(name, x, y)    name##_NEDTRIE_NEXT(x, y)
 Returns the item following y in nedtrie x. More...
 
#define NEDTRIE_PREVLEAF(name, x)    name##_NEDTRIE_PREVLEAF(x)
 Returns the item with an identical key preceding y in nedtrie x. More...
 
#define NEDTRIE_NEXTLEAF(name, x)    name##_NEDTRIE_NEXTLEAF(x)
 Returns the item with an identical key following y in nedtrie x. More...
 
#define NEDTRIE_MIN(name, x)    name##_NEDTRIE_MINMAX(x, 0)
 Returns the lowest item in nedtrie x. This item will approximately have the smallest key. More...
 
#define NEDTRIE_MAX(name, x)    name##_NEDTRIE_MINMAX(x, 1)
 Returns the highest item in nedtrie x. This item will approximately have the biggest key. More...
 
#define NEDTRIE_FOREACH(x, name, head)
 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). More...
 
#define NEDTRIE_FOREACH_SAFE(x, name, head, y)
 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). More...
 
#define NEDTRIE_FOREACH_REVERSE(x, name, head)
 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). More...
 
#define NEDTRIE_FOREACH_REVERSE_SAFE(x, name, head, y)
 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). More...
 
#define NEDTRIE_HASNODEHEADER(treevar, node, link)   ((node)->link.trie_parent || (node)->link.trie_prev)
 Returns true if this item's node header is active. Useful as a quick check for whether a node is in some trie. More...
 

Typedefs

typedef struct nedtries::TrieValidityState_t nedtries::TrieValidityState
 

Functions

template<class trietype >
int nedtries::trienobblezeros (trietype *)
 
template<class trietype >
int nedtries::trienobbleones (trietype *)
 
template<class trietype >
int nedtries::trienobbleequally (trietype *head)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
void nedtries::triecheckvalidity (trietype *head)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
void nedtries::trieinsert (trietype *head, type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct, int(*)(trietype *head) nobblefunct>
void nedtries::trieremove (trietype *head, type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::triefind (const trietype *head, const type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
int nedtries::trieexactfind (const trietype *head, const type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::trieCfind (const trietype *head, const type *r, int rounds)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::trieminmax (const trietype *head, const unsigned dir)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::triebranchprev (const type *r, const TrieLink_t< type > **rlinkaddr)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::trieprev (const trietype *head, const type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::triebranchnext (const type *r, const TrieLink_t< type > **rlinkaddr)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::trienext (const trietype *head, const type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
type * nedtries::trieNfind (const trietype *head, const type *r)
 
template<class trietype , class type , size_t fieldoffset, size_t(*)(const type *) keyfunct>
void nedtries::triecheckvaliditybranch (trietype *head, type *node, unsigned bitidx, TrieValidityState &state)
 

Macro Definition Documentation

#define RESTRICT

Defined to the restrict keyword or equivalent if available.

#define INLINE   inline

Defined to the inline keyword or equivalent if available.

#define NOINLINE

Defined to whatever compiler magic inhibits inlining if available.

#define DEBUGINLINE

Defined to be INLINE when NDEBUG is defined, NOINLINE when DEBUG is defined, unset otherwise.

#define NEDTRIEUSEMACROS   0

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.

#define NEDTRIEDEBUG   0

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.

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

Defines the number of top level bit bins to use. The default based on size_t is usually fine.

#define NEDTRIE_HEAD2 (   name,
  type 
)
Value:
struct name { \
size_t count; \
type *triebins[NEDTRIE_INDEXBINS]; /* each containing (1<<x)<=bitscanrev(x)<(1<<(x+1)) */ \
int nobbledir; \
}
#define NEDTRIE_INDEXBINS
Defines the number of top level bit bins to use. The default based on size_t is usually fine...
Definition: nedtrie.h:217
#define NEDTRIE_HEAD (   name,
  type 
)    NEDTRIE_HEAD2(name, struct type)

Substitutes the type used to store the head of the trie.

#define NEDTRIE_ENTRY (   type)
Value:
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. */ \
}

Substitutes the type used to store the per-node trie information. Occupies 5*sizeof(size_t).

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

Initialises a nedtrie for usage.

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

Returns whether a nedtrie is empty.

#define NEDTRIE_COUNT (   head)    ((head)->count)

Returns the number of items in a nedtrie.

#define NEDTRIE_NOBBLEZEROS (   name)    nedtries::trienobblezeros<name>

A nobble function which preferentially nobbles zeros.

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

A nobble function which preferentially nobbles ones.

#define NEDTRIE_NOBBLEEQUALLY (   name)    nedtries::trienobbleequally<name>

A nobble function which alternates between nobbling zeros and ones.

#define NEDTRIE_GENERATE_NOBBLES (   proto,
  name,
  type,
  field,
  keyfunct 
)
#define NEDTRIEFIELDOFFSET2 (   type,
  field 
)    ((size_t) &(((type *)0)->field))
#define NEDTRIEFIELDOFFSET (   type,
  field 
)    NEDTRIEFIELDOFFSET2(struct type, field)
#define NEDTRIE_GENERATE_INSERT (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_REMOVE (   proto,
  name,
  type,
  field,
  keyfunct,
  nobblefunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_FIND (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_EXACTFIND (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_CFIND (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_MINMAX (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_PREV (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_NEXT (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE_NFIND (   proto,
  name,
  type,
  field,
  keyfunct 
)
Value:
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); \
}
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define RESTRICT
Defined to the restrict keyword or equivalent if available.
Definition: nedtrie.h:59
#define NEDTRIE_GENERATE (   proto,
  name,
  type,
  field,
  keyfunct,
  nobblefunct 
)
Value:
NEDTRIE_GENERATE_NOBBLES (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_INSERT (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_REMOVE (proto, name, type, field, keyfunct, nobblefunct) \
NEDTRIE_GENERATE_FIND (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_CFIND (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_MINMAX (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_PREV (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_NEXT (proto, name, type, field, keyfunct) \
NEDTRIE_GENERATE_NFIND (proto, name, type, field, keyfunct) \
proto INLINE struct type * name##_NEDTRIE_PREVLEAF(struct type *r) { return (r)->field.trie_prev; } \
proto INLINE struct type * name##_NEDTRIE_NEXTLEAF(struct type *r) { return (r)->field.trie_next; }
#define NEDTRIE_GENERATE_REMOVE(proto, name, type, field, keyfunct, nobblefunct)
Definition: nedtrie.h:599
#define NEDTRIE_GENERATE_CFIND(proto, name, type, field, keyfunct)
Definition: nedtrie.h:884
#define NEDTRIE_GENERATE_FIND(proto, name, type, field, keyfunct)
Definition: nedtrie.h:674
#define NEDTRIE_GENERATE_INSERT(proto, name, type, field, keyfunct)
Definition: nedtrie.h:417
#define INLINE
Defined to the inline keyword or equivalent if available.
Definition: nedtrie.h:67
#define NEDTRIE_GENERATE_PREV(proto, name, type, field, keyfunct)
Definition: nedtrie.h:1094
#define NEDTRIE_GENERATE_MINMAX(proto, name, type, field, keyfunct)
Definition: nedtrie.h:952
#define NEDTRIE_GENERATE_NOBBLES(proto, name, type, field, keyfunct)
Definition: nedtrie.h:282
#define NEDTRIE_GENERATE_NFIND(proto, name, type, field, keyfunct)
Definition: nedtrie.h:1269
#define NEDTRIE_GENERATE_EXACTFIND(proto, name, type, field, keyfunct)
Definition: nedtrie.h:719
#define NEDTRIE_GENERATE_NEXT(proto, name, type, field, keyfunct)
Definition: nedtrie.h:1203

Substitutes a set of nedtrie implementation function definitions specialised according to type.

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

Inserts item y into nedtrie x.

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

Removes item y from nedtrie x.

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

Finds the item with the same key as y in nedtrie x.

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

Returns true if there is an item with the same key and address as y in nedtrie x.

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

Performs 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 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_NFIND (   name,
  x,
 
)    name##_NEDTRIE_NFIND(x, y)

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_PREV (   name,
  x,
 
)    name##_NEDTRIE_PREV(x, y)

Returns the item preceding y in nedtrie x.

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

Returns the item following y in nedtrie x.

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

Returns the item with an identical key preceding y in nedtrie x.

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

Returns the item with an identical key following y in nedtrie x.

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

Returns the lowest item in nedtrie x. This item will approximately have the smallest key.

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

Returns the highest item in nedtrie x. This item will approximately have the biggest key.

#define NEDTRIE_FOREACH (   x,
  name,
  head 
)
Value:
for ((x) = NEDTRIE_MIN(name, head); \
(x) != NULL; \
(x) = NEDTRIE_NEXT(name, head, x))
#define NEDTRIE_NEXT(name, x, y)
Returns the item following y in nedtrie x.
Definition: nedtrie.h:1330
#define NEDTRIE_MIN(name, x)
Returns the lowest item in nedtrie x. This item will approximately have the smallest key...
Definition: nedtrie.h:1342

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_SAFE (   x,
  name,
  head,
 
)
Value:
for ((x) = NEDTRIE_MIN(name, head); \
(x) != NULL && ((y) = NEDTRIE_NEXT(name, head, x), 1); \
(x) = (y))
#define NEDTRIE_NEXT(name, x, y)
Returns the item following y in nedtrie x.
Definition: nedtrie.h:1330
#define NEDTRIE_MIN(name, x)
Returns the lowest item in nedtrie x. This item will approximately have the smallest key...
Definition: nedtrie.h:1342

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_REVERSE (   x,
  name,
  head 
)
Value:
for ((x) = NEDTRIE_MAX(name, head); \
(x) != NULL; \
(x) = NEDTRIE_PREV(name, head, x))
#define NEDTRIE_MAX(name, x)
Returns the highest item in nedtrie x. This item will approximately have the biggest key...
Definition: nedtrie.h:1346
#define NEDTRIE_PREV(name, x, y)
Returns the item preceding y in nedtrie x.
Definition: nedtrie.h:1326

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_SAFE (   x,
  name,
  head,
 
)
Value:
for ((x) = NEDTRIE_MAX(name, head); \
(x) != NULL && ((y) = NEDTRIE_PREV(name, head, x), 1); \
(x) = (y))
#define NEDTRIE_MAX(name, x)
Returns the highest item in nedtrie x. This item will approximately have the biggest key...
Definition: nedtrie.h:1346
#define NEDTRIE_PREV(name, x, y)
Returns the item preceding y in nedtrie x.
Definition: nedtrie.h:1326

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_HASNODEHEADER (   treevar,
  node,
  link 
)    ((node)->link.trie_parent || (node)->link.trie_prev)

Returns true if this item's node header is active. Useful as a quick check for whether a node is in some trie.