TABLE OF CONTENTS

trish2/patricia_node [ Modules ]

[ Top ] [ Modules ]

NAME

patricia_node

SYNOPSIS

 #include <patricia_node.h>

DESCRIPTION

EXAMPLE

SEE ALSO

bunch, patricia, pnode_t, PNODE_SPECIAL_START, PNODE_SPECIAL_END, pnode_new, pnode_lookup, pnode_insert, pnode_string

trish2/pnode_t [ Structures ]

[ Top ] [ Structures ]

NAME

pnode_t

SYNOPSIS

 #include <patricia_node.h>
 typedef struct {
   wchar_t wc;
   wchar_t *tail;
   pnode_t *next;
   pnode_t *left;
   pnode_t *right;
   pnode_t *parent;
   void *data;
 } pnode_t;

DESCRIPTION

A PATRICIA tree node consists of a leading character, a tail string and its children. Sibling nodes are organized in a BST, so don't confuse the PATRICIA tree and the BST of children nodes.

ATTRIBUTES

SEE ALSO

patricia_node, PNODE_SPECIAL_START, PNODE_SPECIAL_END, pnode_new

trish2/PNODE_SPECIAL_START, trish2/PNODE_SPECIAL_END [ Definitions ]

[ Top ] [ Definitions ]

NAME

PNODE_SPECIAL_START, PNODE_SPECIAL_END

SYNOPSIS

 #include <patricia_node.h>
 #define PNODE_SPECIAL_START 0xFDD0
 #define PNODE_SPECIAL_END   0xFDD1

DESCRIPTION

These are special values for the PATRICIA tree node leading character indicating respectively the start and the end of a PATRICIA entry. The unicode standard defines noncharacters U+FDD0..U+FDEF for application use: PNODE_SPECIAL_START and PNODE_SPECIAL_END are guaranteed to belong to this segment.

SEE ALSO

patricia_node, pnode_t

trish2/pnode_new [ Functions ]

[ Top ] [ Functions ]

NAME

pnode_new

SYNOPSIS

 #include <patricia_node.h>
 pnode_t *pnode_new(bunch_t *b, pnode_t *parent, wchar_t wc);

FUNCTION

pnode_new claims a new pnode_t structure from the bunch b, with parent node parent and leading character wc. b must be a bunch created with bunch_new with an element size of sizeof(pnode_t). If parent is NULL then the new node has no parent. The new node will be inserted in the parent's children BST.

INPUTS

RETURN VALUE

A pointer to the new PATRICIA tree node.

SEE ALSO

patricia_node, pnode_t, bunch_claim

trish2/pnode_lookup [ Functions ]

[ Top ] [ Functions ]

NAME

pnode_lookup

SYNOPSIS

 #include <patricia_node.h>
 pnode_t *pnode_lookup(pnode_t *ref, wchar_t wc);

FUNCTION

pnode_lookup searches for a node amongst children of ref with leading character equals to wc.

INPUTS

RETURN VALUE

A pointer to the node found. NULL if no node was found.

SEE ALSO

patricia_node, pnode_t, PNODE_SPECIAL_START, PNODE_SPECIAL_END, pnode_new, pnode_insert

trish2/pnode_insert [ Functions ]

[ Top ] [ Functions ]

NAME

pnode_insert

SYNOPSIS

 #include <patricia_node.h>
 int pnode_insert(bunch_t *b, pnode_t *ref, wchar_t wc, pnode_t **new);

FUNCTION

pnode_insert searches for a node amongst children of ref with leading character equals to wc. If none is found, then it inserts a new one claimed from bunch b and with wc as leading character. The new address is assigned to the children node with leading character wc, whether it was found or inserted.

INPUTS

RETURN VALUE

Zero if *new was found, non zero if *new was inserted.

SEE ALSO

patricia_node, pnode_t, PNODE_SPECIAL_START, PNODE_SPECIAL_END, pnode_new, pnode_lookup

trish2/pnode_string [ Functions ]

[ Top ] [ Functions ]

NAME

pnode_string

SYNOPSIS

 #include <patricia_node.h>
 wchar_t *pnode_string(pnode_t *pn, int n, bunch_t *b);

FUNCTION

pnode_string builds a wide character that is the concatenation of leading characters and tail strings of the n ancestors of pn to pn. If n is lower than the depth of pn from the tree root, the the string will be truncated of its prefix. If n is higher than the depth of pn, then the behaviour is undefined. If b is not NULL, then the string will be claimed from the bunch pointed by b. If b is NULL, then it will be allocated with calloc.

INPUTS

RETURN VALUE

A freshly claimed or allocated wide character string.

SEE ALSO

patricia_node, pnode_t, bunch_claim