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

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

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

Inserts item y into nedtrie x.

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

Removes item y from nedtrie x.

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

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

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

#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,
			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.

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

Returns the item preceding y in nedtrie x.

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

Returns the item following y in nedtrie x.

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

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

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

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

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

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

#define NEDTRIE_FOREACH	(		x,
			name,
			head
	)

Value:

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

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,
			y
	)

Value:

for ((x) = NEDTRIE_MIN(name, head);           \
         (x) != NULL && ((y) = NEDTRIE_NEXT(name, head, x), 1); \
         (x) = (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).

#define NEDTRIE_FOREACH_REVERSE	(		x,
			name,
			head
	)

Value:

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

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,
			y
	)

Value:

for ((x) = NEDTRIE_MAX(name, head);           \
         (x) != NULL && ((y) = NEDTRIE_PREV(name, head, x), 1); \
         (x) = (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).

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