Trie impl

Implements Trie.

Summary

Trie impl	Implements Trie.
Copyright	This program is free software.
Files
C-kern/api/ds/inmem/trie.h	Header file Trie.
C-kern/ds/inmem/trie.c	Implementation file Trie impl.
header_t	Stores bit values of type header_e.
types
header_e	Bitvalues which encodes the optional data members of trie_node_t.
constants
MAXSIZE
query
size_header	Returns the size in bytes of the header size field.
trie_subnode_t	Points to 256 childs of type trie_nodedata_t.
struct fields
child	An array of 256 pointer to trie_nodedata_t.
lifetime
delete_triesubnode	Frees allocated memory of subnode.
new_triesubnode	Allocates a single subnode.
query
child_triesubnode	Returns child pointer for digit.
change
setchild_triesubnode	Sets child as pointer to child node for digit.
trie_nodedata_t	Describes a flexible structure of trie node data stored in memory.
struct fields
header	Flags which describes content of trie_nodedata_t.
nrchild	Nr of childs stored in optional child[] array or trie_subnode_t.
keylen	Start of byte-aligned data.
uservalue	Start of ptr-aligned data.
constants
PTRALIGN	Alignment of trie_nodedata_t.uservalue.
MAXCHILD	The maximum nr of child pointer which could be stored in a trie_nodedata_t of size header_t.MAXSIZE.
trie_node_t	Stores decoded information about a trie node in memory.
struct fields
data	Points to data in memory.
query-helper
alignoffset_trienode	Aligns offset to architecture specific pointer alignment.
change-helper
adduservalue_trienode
deluservalue_trienode
addsubnode_trienode	Moves all pointers in child[] array to subnode.
delsubnode_trienode	Moves all pointers from subnode into child[] array.
splitkey_trienode
query
ischild_header	Return true in case child and digit array are encoded in trie_node_t.
ischildorsubnode_header	Return true in case ischild_header or issubnode_header returns true.
issubnode_header	Return true in case child array points to trie_subnode_t.
isuservalue_header	Return true in case node contains member uservalue.
sizenode_header	Return size in bytes of node.
change
clear_header	Clears flags in header.
trie_subnode2_t	Points to up to 8 trie_node_ts.
lifetime
new_triesubnode2	Allocates subnode and sets all child pointer to 0.
delete_triesubnode2	Frees memory of subnode and sets it to 0.
query
trie_subnode_t	Points to up to 32 trie_subnode2_ts.
lifetime
delete_triesubnode	Frees memory of subnode and of all referenced trie_subnode2_t.
new_triesubnode	Allocates new subnode and additional trie_subnode2_t.
query
trie_nodeoffsets_t	Stores offsets of every possible member of trie_node_t.
constants
SIZE1NODE	Size of trie_node_t if header_t contains <header_SIZE1NODE>.
SIZE2NODE	Size of trie_node_t if header_t contains <header_SIZE2NODE>.
SIZE3NODE	Size of trie_node_t if header_t contains <header_SIZE3NODE>.
SIZE4NODE	Size of trie_node_t if header_t contains <header_SIZE4NODE>.
SIZE5NODE	Size of trie_node_t if header_t contains <header_SIZE5NODE>.
SIZEMAXNODE	Same as SIZE5NODE.
HEADERSIZE	Offset to first data byte in trie_node_t.
LENCHILDMAX	The maximum length of child array in a trie_node_t.
helper
lifetime
init_trienodeoffsets	Initializes offsets from prefixlen, optional uservalue, and number of child pointers nrchild.
initdecode_trienodeoffsets	Init offsets from decoded information stored in header.
query
isexpandable_trienodeoffsets	Returns true if the nodesize is lower than maximum size.
lenprefix_trienodeoffsets	Returns the number of bytes the encoded prefix uses.
lenuservalue_trienodeoffsets	Returns sizeof(void*) if uservalue is available else 0.
uservalue_trienodeoffsets	Returns address of uservalue member.
subnode_trienodeoffsets	Returns address of subnode member.
sizefree_trienodeoffsets	Calculates unused bytes in node which corresponds to offset.
sizegrowprefix_trienodeoffsets	Calculates size the prefix could grow without growing the node size.
change
convert2subnode_trienodeoffsets	Switch header flags from <header_CHILD> to <header_SUBNODE>.
shrinkprefix_trienodeoffsets	Adapts offsets to newprefixlen.
changesize_trienodeoffsets	Sets header and nodesize of offset to smaller or bigger size.
growprefix_trienodesoffsets	Adds increment to length of prefix.
adduservalue_trienodeoffsets	Add header_USERVALUE to offsets->header and adapts offsets.
trie_node_t	Describes a node in the trie.
query-helper
child_trienode	Returns ptr to child array.
child_trienode	Returns ptr to child array.
digit_trienode	Returns ptr to digit array.
isfreechild_trienode	Uses node to check if last child entry is empty.
prefix_trienode	Returns ptr to digit array.
helper
newnode_trienode	Allocates new trie_node_t of size nodesize and returns pointer in node.
shrinksize_trienode	Resize node to a smaller size.
expand_trienode	Doubles the size of the node.
shrinkprefixkeeptail_trienode	Keeps last newprefixlen bytes of the key prefix.
shrinkprefixkeephead_trienode	Keeps first newprefixlen bytes of the key prefix.
tryextendprefix_trienode	Extends prefix with new head prefix1[len-1] + prefix2.
adduservalue_trienode	Add uservalue to node and adapt offset.
lifetime
delete_trienode	Frees memory of node and all of its child nodes.
new_trienode	Allocate new trie_node_t with optional prefix, optional usernode and optional childs.
newsplit_trienode	The prefix of splitnode is split.
change
convertchild2sub_trienode	TODO: describe TODO: remove shrinknode
insertchild_trienode	Inserts child into node.
lifetime
query
findnode_trie	Finds node in trie who matches the given key fully or partially.
update
trie_t
static variables
s_trie_errtimer	Simulates an error in different functions.
Functions
test
compare_expectnode	Compares expect with node.

Copyright

This program is free software. You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

Author

Files

C-kern/api/ds/inmem/trie.h

Header file Trie.

C-kern/ds/inmem/trie.c

Implementation file Trie impl.

header_t

typedef uint8_t header_t

Stores bit values of type header_e.

Summary

types
header_e	Bitvalues which encodes the optional data members of trie_node_t.
constants
MAXSIZE
query
size_header	Returns the size in bytes of the header size field.

types

header_e

Bitvalues which encodes the optional data members of trie_node_t. These values are stored in a data field of type header_t.

header_KEYMASK	Mask to determine the value of the following KEY configurations.
header_KEYLEN0	No key[] member available
header_KEYLEN1	trie_nodedata_t.key[0] == binary key digit
header_KEYLEN2	trie_nodedata_t.key[0..1] == binary key digits
header_KEYLEN3	trie_nodedata_t.key[0..2] == binary key digits
header_KEYLEN4	trie_nodedata_t.key[0..3] == binary key digits
header_KEYLEN5	trie_nodedata_t.key[0..4] == binary key digits
header_KEYLEN6	trie_nodedata_t.key[0..5] == binary key digits
header_KEYLEN	trie_nodedata_t.keylen == contains key length trie_nodedata_t.key[0..keylen-1] == binary key digits
header_USERVALUE	If set indicates that uservalue member is available.
header_CHILD	Child and digit array available. digit[x] contains next digit and child[x] points to next trie_node_t.
header_SUBNODE	Subnode pointer is avialable and digit[0] counts the number of valid pointers to trie_node_t not null. If a pointer in trie_subnode_t or trie_subnode2_t is null there is no entry with such a key. The number of stored pointers is (digit[0]+1), i.e. it at least one pointer must be valid.
header_SIZEMASK	Mask to determine the value of one of the following 4 size configurations.
header_SIZE1	The size of the node is 2 * sizeof(void*)
header_SIZE2	The size of the node is 4 * sizeof(void*)
header_SIZE3	The size of the node is 8 * sizeof(void*)
header_SIZE4	The size of the node is 16 * sizeof(void*)
header_SIZE5	The size of the node is 32 * sizeof(void*)
header_SIZE6	The size of the node is 64 * sizeof(void*)

constants

MAXSIZE

#define MAXSIZE ( 64*sizeof(void*) )

TODO

query

size_header

static uint_fast16_t size_header( unsigned headersize )

Returns the size in bytes of the header size field. If you want to know the size of a node call this function with parameter (trie_nodedata_t.header & header_SIZEMASK).

trie_subnode_t

struct trie_subnode_t

Points to 256 childs of type trie_nodedata_t. If child[i] is 0 it means there is no child for 8-bit binary digit i at a certain offset in the search key.

Summary

struct fields
child	An array of 256 pointer to trie_nodedata_t.
lifetime
delete_triesubnode	Frees allocated memory of subnode.
new_triesubnode	Allocates a single subnode.
query
child_triesubnode	Returns child pointer for digit.
change
setchild_triesubnode	Sets child as pointer to child node for digit.

struct fields

child

trie_nodedata_t * child[256]

An array of 256 pointer to trie_nodedata_t. If there is no child at a given key digit the pointer is set to 0.

lifetime

delete_triesubnode

static int delete_triesubnode( trie_subnode_t ** subnode )

Frees allocated memory of subnode. Referenced childs are not freed.

new_triesubnode

static int new_triesubnode( /*out*/trie_subnode_t ** subnode )

Allocates a single subnode. All 256 pointer to child nodes are set to 0.

query

child_triesubnode

static inline trie_nodedata_t * child_triesubnode( trie_subnode_t * subnode,
uint8_t digit )

Returns child pointer for digit.

change

setchild_triesubnode

static inline void setchild_triesubnode( trie_subnode_t * subnode,
uint8_t digit,
trie_nodedata_t * child )

Sets child as pointer to child node for digit.

trie_nodedata_t

struct trie_nodedata_t

Describes a flexible structure of trie node data stored in memory. Two fields header and nrchild are followed by optional data fields. The optional fields are a part of the key (prefix/subkey), a user pointer, and optional digit and child arrays. Instead of digit and child arrays a single pointer to a trie_subnode_t could be stored.

The size of the structure is flexible. It can use up to header_t.MAXSIZE bytes.

Summary

struct fields
header	Flags which describes content of trie_nodedata_t.
nrchild	Nr of childs stored in optional child[] array or trie_subnode_t.
keylen	Start of byte-aligned data.
uservalue	Start of ptr-aligned data.
constants
PTRALIGN	Alignment of trie_nodedata_t.uservalue.
MAXCHILD	The maximum nr of child pointer which could be stored in a trie_nodedata_t of size header_t.MAXSIZE.

struct fields

header

header_t header

Flags which describes content of trie_nodedata_t. See header_t.

nrchild

uint8_t nrchild

Nr of childs stored in optional child[] array or trie_subnode_t. The subnode can store up to 256 childs and the number of childs in a subnode is always >= 1. In the subnode case the stored value is one less than the real number of child to be able to count up to 256.

keylen

uint8_t keylen

Start of byte-aligned data. Contains optional byte size of key.

uservalue

void * uservalue

Start of ptr-aligned data. Contains an optional user value.

constants

PTRALIGN

#define PTRALIGN ( offsetof(trie_nodedata_t, uservalue) )

Alignment of trie_nodedata_t.uservalue. The first byte in trie_node_t which encodes the availability of the optional members is followed by byte aligned data which is in turn followed by pointer aligned data. This value is the alignment necessary for a pointer on this architecture. This value must be a power of two.

MAXCHILD

#define MAXCHILD (
(MAXSIZE-offsetof(trie_nodedata_t, keylen)-sizeof(((trie_nodedata_t*)0)->uservalue)) / (sizeof(void*)+sizeof(uint8_t))
)

The maximum nr of child pointer which could be stored in a trie_nodedata_t of size header_t.MAXSIZE.

trie_node_t

struct trie_node_t

Stores decoded information about a trie node in memory. A pointer to the encoded information (trie_nodedata_t) is stored in the data field.

TODO: describe

Summary

struct fields
data	Points to data in memory.
query-helper
alignoffset_trienode	Aligns offset to architecture specific pointer alignment.
change-helper
adduservalue_trienode
deluservalue_trienode
addsubnode_trienode	Moves all pointers in child[] array to subnode.
delsubnode_trienode	Moves all pointers from subnode into child[] array.
splitkey_trienode
query
ischild_header	Return true in case child and digit array are encoded in trie_node_t.
ischildorsubnode_header	Return true in case ischild_header or issubnode_header returns true.
issubnode_header	Return true in case child array points to trie_subnode_t.
isuservalue_header	Return true in case node contains member uservalue.
sizenode_header	Return size in bytes of node.
change
clear_header	Clears flags in header.

struct fields

data

trie_nodedata_t * data

Points to data in memory.

query-helper

alignoffset_trienode

static inline unsigned alignoffset_trienode( unsigned offset )

Aligns offset to architecture specific pointer alignment.

change-helper

adduservalue_trienode

Unchecked Precondition

The node has no uservalue (<off4_uservalue_trienode>() == <off5_child_trienode>())
The node layout has at least sizeof(void*) free aligned bytes at its end (higher address). The child array must not occupy the whole node.

deluservalue_trienode

Unchecked Precondition

The node has a uservalue (<off4_uservalue_trienode>() == <off5_child_trienode>()-sizeof(void*))

addsubnode_trienode

Moves all pointers in child[] array to subnode. A new subnode is created. For every pointer in child[] if no subnode2 exists it is created and added to subnode. The pointer is inserted in subnode2. Then all pointers in child[] are removed and a single pointer to subnode is stored in child[0]. The digit[] array is also removed from node.

Unchecked Precondition

The node contains digit[] and child[] arrays with more than MAXCHILD entries.

delsubnode_trienode

Moves all pointers from subnode into child[] array. Subnode and all referenced subnode2 are deleted afterwards. Also a digit[] array is added to the node.

Unchecked Precondition

The node contains a subnode with less than MAXCHILD entries.
The node is big enough to hold all digit[] and child[] entries.

splitkey_trienode

Unchecked Precondition

query

ischild_header

static inline int ischild_header( const header_t header )

Return true in case child and digit array are encoded in trie_node_t.

ischildorsubnode_header

static inline int ischildorsubnode_header( const header_t header )

Return true in case ischild_header or issubnode_header returns true.

issubnode_header

static inline int issubnode_header( const header_t header )

Return true in case child array points to trie_subnode_t.

isuservalue_header

static inline int isuservalue_header( const header_t header )

Return true in case node contains member uservalue.

sizenode_header

static inline uint16_t sizenode_header( const header_t header )

Return size in bytes of node.

change

clear_header

static inline header_t clear_header( const header_t header,
header_e flags )

Clears flags in header.

trie_subnode2_t

struct trie_subnode2_t

Points to up to 8 trie_node_ts.

unchecked Invariant

At least one pointer != 0 in child[].

Summary

lifetime
new_triesubnode2	Allocates subnode and sets all child pointer to 0.
delete_triesubnode2	Frees memory of subnode and sets it to 0.
query

lifetime

new_triesubnode2

static int new_triesubnode2( /*out*/trie_subnode2_t ** subnode )

Allocates subnode and sets all child pointer to 0.

delete_triesubnode2

static int delete_triesubnode2( trie_subnode2_t ** subnode )

Frees memory of subnode and sets it to 0. Nodes referenced from child array are not deleted.

query

trie_subnode_t

struct trie_subnode_t

Points to up to 32 trie_subnode2_ts. Exactly one trie_subnode_t is referenced from trie_node_t.

unchecked Invariant

At least one pointer != 0 in child[].

Summary

lifetime
delete_triesubnode	Frees memory of subnode and of all referenced trie_subnode2_t.
new_triesubnode	Allocates new subnode and additional trie_subnode2_t.
query

lifetime

delete_triesubnode

static int delete_triesubnode( trie_subnode_t ** subnode )

Frees memory of subnode and of all referenced trie_subnode2_t. Subnode is set to 0. Nodes referenced from any trie_subnode2_t are not deleted.

new_triesubnode

static int new_triesubnode( /*out*/trie_subnode_t ** subnode,
uint16_t nrchild,
const uint8_t digit[nrchild],
trie_nodedata_t * const child[nrchild] )

Allocates new subnode and additional trie_subnode2_t. Every pointer in child is stored into the corresponding child entry in the referenced trie_subnode2_t. The correct place to store pointer child[x] is calculated from digit[x].

Unchecked Precondition

nrchild <= 256
digit array sorted in ascending order
Forall 0 <= x < nrchild: child[x] != 0

query

trie_nodeoffsets_t

struct trie_nodeoffsets_t

Stores offsets of every possible member of trie_node_t. Offsets point to valid data only if the following offset is greater. nodesize gives the size of the whole node. lenchild is no offset but gives the length of the child array. In case of (1 == issubnode_header(offsets->header)) lenchild is 1 and child[0] contains a single pointer to trie_subnode_t. header is a bitmask which encodes the offset and size information.

Summary

constants
SIZE1NODE	Size of trie_node_t if header_t contains <header_SIZE1NODE>.
SIZE2NODE	Size of trie_node_t if header_t contains <header_SIZE2NODE>.
SIZE3NODE	Size of trie_node_t if header_t contains <header_SIZE3NODE>.
SIZE4NODE	Size of trie_node_t if header_t contains <header_SIZE4NODE>.
SIZE5NODE	Size of trie_node_t if header_t contains <header_SIZE5NODE>.
SIZEMAXNODE	Same as SIZE5NODE.
HEADERSIZE	Offset to first data byte in trie_node_t.
LENCHILDMAX	The maximum length of child array in a trie_node_t.
helper
lifetime
init_trienodeoffsets	Initializes offsets from prefixlen, optional uservalue, and number of child pointers nrchild.
initdecode_trienodeoffsets	Init offsets from decoded information stored in header.
query
isexpandable_trienodeoffsets	Returns true if the nodesize is lower than maximum size.
lenprefix_trienodeoffsets	Returns the number of bytes the encoded prefix uses.
lenuservalue_trienodeoffsets	Returns sizeof(void*) if uservalue is available else 0.
uservalue_trienodeoffsets	Returns address of uservalue member.
subnode_trienodeoffsets	Returns address of subnode member.
sizefree_trienodeoffsets	Calculates unused bytes in node which corresponds to offset.
sizegrowprefix_trienodeoffsets	Calculates size the prefix could grow without growing the node size.
change
convert2subnode_trienodeoffsets	Switch header flags from <header_CHILD> to <header_SUBNODE>.
shrinkprefix_trienodeoffsets	Adapts offsets to newprefixlen.
changesize_trienodeoffsets	Sets header and nodesize of offset to smaller or bigger size.
growprefix_trienodesoffsets	Adds increment to length of prefix.
adduservalue_trienodeoffsets	Add header_USERVALUE to offsets->header and adapts offsets.

constants

SIZE1NODE

#define SIZE1NODE ( 2*sizeof(trie_node_t*) )

Size of trie_node_t if header_t contains <header_SIZE1NODE>.

SIZE2NODE

#define SIZE2NODE ( 4*sizeof(trie_node_t*) )

Size of trie_node_t if header_t contains <header_SIZE2NODE>.

SIZE3NODE

#define SIZE3NODE ( 8*sizeof(trie_node_t*) )

Size of trie_node_t if header_t contains <header_SIZE3NODE>.

SIZE4NODE

#define SIZE4NODE ( 16*sizeof(trie_node_t*) )

Size of trie_node_t if header_t contains <header_SIZE4NODE>.

SIZE5NODE

#define SIZE5NODE ( 32*sizeof(trie_node_t*) )

Size of trie_node_t if header_t contains <header_SIZE5NODE>.

SIZEMAXNODE

#define SIZEMAXNODE SIZE5NODE

Same as SIZE5NODE.

HEADERSIZE

#define HEADERSIZE ( sizeof(header_t) )

Offset to first data byte in trie_node_t.

LENCHILDMAX

#define LENCHILDMAX (
(SIZEMAXNODE-sizeof(void*)/*uservalue*/-HEADERSIZE-2/*prefix*/)/(sizeof(trie_node_t*)+1)
)

The maximum length of child array in a trie_node_t. If more than LENCHILDMAX pointers have to be stored then a single pointer to a trie_subnode_t is stored in trie_node_t.

helper

lifetime

init_trienodeoffsets

static void init_trienodeoffsets( /*out*/trie_nodeoffsets_t * offsets,
uint16_t prefixlen,
bool isuservalue,
const uint16_t nrchild )

Initializes offsets from prefixlen, optional uservalue, and number of child pointers nrchild.

initdecode_trienodeoffsets

static int initdecode_trienodeoffsets( /*out*/trie_nodeoffsets_t * offsets,
const trie_nodedata_t * data )

Init offsets from decoded information stored in header. A single byte in trienode is needed for the prefixlen if header contains value <header_PREFIX_LEN>.

query

isexpandable_trienodeoffsets

static inline int isexpandable_trienodeoffsets(
const trie_nodeoffsets_t * offsets
)

Returns true if the nodesize is lower than maximum size.

lenprefix_trienodeoffsets

static inline uint8_t lenprefix_trienodeoffsets(
const trie_nodeoffsets_t * offsets
)

Returns the number of bytes the encoded prefix uses.

lenuservalue_trienodeoffsets

static inline uint8_t lenuservalue_trienodeoffsets(
const trie_nodeoffsets_t * offsets
)

Returns sizeof(void*) if uservalue is available else 0.

uservalue_trienodeoffsets

static inline void ** uservalue_trienodeoffsets(
const trie_nodeoffsets_t * offsets,
trie_nodedata_t * data
)

Returns address of uservalue member.

subnode_trienodeoffsets

static inline trie_subnode_t ** subnode_trienodeoffsets(
const trie_nodeoffsets_t * offsets,
trie_nodedata_t * data
)

Returns address of subnode member.

sizefree_trienodeoffsets

static uint8_t sizefree_trienodeoffsets( const trie_nodeoffsets_t * offsets )

Calculates unused bytes in node which corresponds to offset.

sizegrowprefix_trienodeoffsets

static uint8_t sizegrowprefix_trienodeoffsets(
const trie_nodeoffsets_t * offsets
)

Calculates size the prefix could grow without growing the node size.

change

convert2subnode_trienodeoffsets

static void convert2subnode_trienodeoffsets( trie_nodeoffsets_t * offsets )

Switch header flags from <header_CHILD> to <header_SUBNODE>. The function returns the number of bytes in use after conversion. Values in offsets are adapted and members in node are moved if necessary. The header in node is changed and the subnode pointer is set.

Unchecked Precondition

true == ischild_header(offsets->header)

shrinkprefix_trienodeoffsets

static void shrinkprefix_trienodeoffsets( trie_nodeoffsets_t * offsets,
uint8_t newprefixlen )

Adapts offsets to newprefixlen.

Unchecked Precondition

newprefixlen < lenprefix_trienodeoffsets(offsets)

changesize_trienodeoffsets

static void changesize_trienodeoffsets( trie_nodeoffsets_t * offsets,
header_t headersize )

Sets header and nodesize of offset to smaller or bigger size. Also offsets members lenchild, uservalue and child are recalculated in case of ischild_header(offsets->header) returns true.

Unchecked Precondition

0 == (headersize & ~header_SIZENODE_MASK)
sizenode_header(headersize) <= SIZEMAXNODE
//”either growing or offsets->child fits in smaller size” offsets.nodesize <= sizenode_header(headersize)

| offsets->child < sizenode_header(headersize)
| (offsets->child == sizenode_header(headersize) && !ischildorsubnode_header(offsets->header))

growprefix_trienodesoffsets

static void growprefix_trienodesoffsets( trie_nodeoffsets_t * offsets,
uint8_t increment,
bool usefreechild )

Adds increment to length of prefix.

Unchecked Precondition

sizegrowprefix_trienodeoffsets(offsets) >= increment || (usefreechild && sizegrowprefix_trienodeoffsets(offsets)+sizeof(trie_node_t*) >= increment)
lenprefix_trienodeoffsets(offsets) + increment <= 255 // is valid cause SIZEMAXNODE-HEADERSIZE <= 255 !
! usefreechild || offsets.lenchild >= 2

adduservalue_trienodeoffsets

static void adduservalue_trienodeoffsets( trie_nodeoffsets_t * offsets )

Add header_USERVALUE to offsets->header and adapts offsets.

Unchecked Preconditions

(node points to trie_node_t* which corresponds to offset)

! isuservalue_header(offsets->header)
sizeof(void*) <= sizefree_trienodeoffsets(offsets)

| offsets.lenchild >= 2 && "last child in node is 0"

trie_node_t

struct trie_node_t

Describes a node in the trie. It is a flexible data structure which can hold an optional string prefix, an optional user pointer, and an optional array of pointers to child nodes or instead a pointer to a trie_subnode_t. The subnode and child members exclude each other.

A trie_node_t can use 2*sizeof(trie_node_t*) up to 32*sizeof(trie_node_t*) bytes.

Summary

query-helper
child_trienode	Returns ptr to child array.
child_trienode	Returns ptr to child array.
digit_trienode	Returns ptr to digit array.
isfreechild_trienode	Uses node to check if last child entry is empty.
prefix_trienode	Returns ptr to digit array.
helper
newnode_trienode	Allocates new trie_node_t of size nodesize and returns pointer in node.
shrinksize_trienode	Resize node to a smaller size.
expand_trienode	Doubles the size of the node.
shrinkprefixkeeptail_trienode	Keeps last newprefixlen bytes of the key prefix.
shrinkprefixkeephead_trienode	Keeps first newprefixlen bytes of the key prefix.
tryextendprefix_trienode	Extends prefix with new head prefix1[len-1] + prefix2.
adduservalue_trienode	Add uservalue to node and adapt offset.
lifetime
delete_trienode	Frees memory of node and all of its child nodes.
new_trienode	Allocate new trie_node_t with optional prefix, optional usernode and optional childs.
newsplit_trienode	The prefix of splitnode is split.
change
convertchild2sub_trienode	TODO: describe TODO: remove shrinknode
insertchild_trienode	Inserts child into node.
lifetime
query
findnode_trie	Finds node in trie who matches the given key fully or partially.
update

query-helper

child_trienode

Returns ptr to child array.

child_trienode

static inline void ** child_trienode( trie_node_t * node )

Returns ptr to child array.

digit_trienode

static inline uint8_t * digit_trienode( trie_node_t * node )

Returns ptr to digit array.

isfreechild_trienode

static inline bool isfreechild_trienode( trie_node_t * node )

Uses node to check if last child entry is empty.

prefix_trienode

static inline uint8_t * prefix_trienode( trie_node_t * node )

Returns ptr to digit array.

helper

newnode_trienode

static int newnode_trienode( /*out*/trie_nodedata_t ** node,
uint16_t nodesize )

Allocates new trie_node_t of size nodesize and returns pointer in node.

shrinksize_trienode

static int shrinksize_trienode( trie_node_t * node )

Resize node to a smaller size. The header of node and offsets are adapted and also lenchild, digit, uservalue and child array of node. A smallest value for nodesize is chosen for which offsets->child <= nodesize and all childs zero at offset nodsize.

expand_trienode

static int expand_trienode( trie_node_t * node )

Doubles the size of the node. The header of node and offsets are adapted. offsets->nodesize is also adapted.

TODO: add functionality to increase lenchild !

Unchecked Precondition

1 == isexpandable_trienodeoffsets(offsets)

shrinkprefixkeeptail_trienode

static void shrinkprefixkeeptail_trienode( trie_node_t * node,
uint8_t newprefixlen )

Keeps last newprefixlen bytes of the key prefix.

Unchecked Precondition

newprefixlen < prefixlen

shrinkprefixkeephead_trienode

static void shrinkprefixkeephead_trienode( trie_node_t * node,
uint8_t newprefixlen )

Keeps first newprefixlen bytes of the key prefix.

Unchecked Precondition

newprefixlen < prefixlen

tryextendprefix_trienode

static int tryextendprefix_trienode( trie_node_t * node,
uint8_t len,
uint8_t prefix1[len-1],
uint8_t prefix2/*single digit*/ )

Extends prefix with new head prefix1[len-1] + prefix2. The new prefix is prefix1[len-1] + prefix2 + oldprefix. Returns ENOMEM if node has not enough free space.

Unchecked Preconditions

len > 0 && len <= sizeof(trie_node_t*)

adduservalue_trienode

static void adduservalue_trienode( trie_node_t * node,
void * uservalue )

Add uservalue to node and adapt offset.

Unchecked Preconditions

! isuservalue_header(node->header)
sizeof(void*) <= sizefree_trienodeoffsets(offsets) || isfreechild_trienode(node, offsets) o

lifetime

delete_trienode

static int delete_trienode( trie_nodedata_t ** node )

Frees memory of node and all of its child nodes. The tree is traversed in depth first order. During traversal a special delete header is written to the node.

new_trienode

static int new_trienode( /*out*/trie_node_t * node,
uint16_t prefixlen,
const uint8_t prefix[prefixlen],
void * const * uservalue,
uint16_t nrchild,
const uint8_t digit[nrchild],
trie_nodedata_t * const child[nrchild] )

Allocate new trie_node_t with optional prefix, optional usernode and optional childs. If the prefix does not fit into a single trie_node_t a chain of trie_nodes is created.

TODO: add size optimization for long prefix (two nodes instead of one, if two nodes occupy less space)

unchecked Precondition

nrchild <= 256
digit array is sorted in ascending order
Every pointer in child != 0

newsplit_trienode

static int newsplit_trienode( /*out*/trie_node_t * node,
trie_node_t * splitnode,
uint8_t splitlen,
void * uservalue,
uint8_t digit,
trie_nodedata_t * child )

The prefix of splitnode is split. A new node is created which contains the first splitlen bytes of prefix in splitnode. The prefix in splitnode is shrunk to the last lenprefix_trienodeoffsets(splitnodeoffsets)-splitlen-1 bytes.

Merge Case

In case lenprefix_trienodeoffsets(splitnodeoffsets)-splitlen <= sizeof(trie_node_t*) it is possible that the last part of the prefix of splitnode is merged into its child (if exactly one child and no uservalue). In this case node is not allocated but the prefix in splitnode is adapted to new size splitlen and splitnode is returned in node.

Attention

Do not use splitnode after return. It may be resized and therefore points to invalid memory.

Unchecked Preconditions

child != 0 ==> uservalue not used (must be invalid)
child == 0 ==> uservalue used (must be valid)
child == 0 || digit != prefix_trienode(splitnode, splitnodeoffsets)[splitlen]
splitlen < prefixlen

change

convertchild2sub_trienode

static int convertchild2sub_trienode( trie_node_t * node )

TODO: describe TODO: remove shrinknode

insertchild_trienode

static int insertchild_trienode( trie_node_t * node,
uint8_t digit,
trie_nodedata_t * child,
uint8_t childindex )

Inserts child into node. offsets must be the corresponding trie_nodeoffsets_t of node. childindex is considered only valid if ischild_header(offsets->header) returns true. digit is a single digit associated with key. After the prefix of node matched every child pointer in node is associated with a unique digit to determine the child node to follow.

Unchecked Preconditions

! ischild_header(offsets->header)

| ( forall(i < childindex): digit_trienode(*node, offsets)[i] < digit

&& forall(i >= childindex && i < offsets.lenchild): digit_trienode(*node, offsets)[i] > digit)

! ischild_header(offsets->header) || child_trienode(*node, offsets)[0] != 0
! ischild_header(offsets->header) || childindex == 0 || child_trienode(*node, offsets)[childindex-1] != 0
! ischild_header(offsets->header) || (0 <= childindex && childindex <= offsets.lenchild)

lifetime

query

findnode_trie

static int findnode_trie( trie_t * trie,
uint16_t keylen,
const uint8_t key[keylen],
/*out*/trie_findresult_t * result )

Finds node in trie who matches the given key fully or partially. The returned result contains information if a node was found which matched full or at least partially.

update

trie_t

Summary

static variables
s_trie_errtimer	Simulates an error in different functions.

static variables

s_trie_errtimer

static test_errortimer_t s_trie_errtimer

Simulates an error in different functions.

Functions

Summary

test
compare_expectnode	Compares expect with node.

test

compare_expectnode

static int compare_expectnode( expect_node_t * expect,
trie_node_t * node,
trie_nodeoffsets_t * nodeoffsets/*could be 0*/,
uint8_t cmpnodesize,
uint8_t cmpsubnodesize )

Compares expect with node. If nodeoffsets != 0 then node and nodeoffsets must match. If cmpnodesize == 0 then the nodesize of node must be the minimum size. If cmpnodesize == 1 then the nodesize of node must be the minimum size or double in size (needed for splitting). If cmpnodesize == 2 then the nodesize of node must be >= the minimum size. The value cmpsubnodesize is inheritedas cmpnodesize for childs.