su 1.12.11devel
|
Red-black tree. More...
Go to the source code of this file.
Macros | |
#define | RBTREE_H |
Defined when <sofia-sip/rbtree.h> has been included. | |
#define | RBTREE_PROTOS(SCOPE, prefix, Type) |
Define prototypes for red-black tree functions. | |
#define | RBTREE_BODIES(SCOPE, prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, CMP, INSERT, REMOVE) |
Define bodies for red-black tree functions. | |
Typedefs | |
typedef struct node | Type |
Type used for rbtree nodes. | |
Functions | |
int | rbtree_insert (Type **tree, Type *node, Type **return_old) |
Insert a node into the tree. | |
int | rbtree_append (Type **tree, Type *node) |
Append a node into the tree. | |
void | rbtree_remove (Type **tree, Type *node) |
Remove a node from the tree. | |
Type * | rbtree_succ (Type const *node) |
Return inorder successor of node node. | |
Type * | rbtree_prec (Type const *node) |
Return inorder precedessor of node node. | |
Type * | rbtree_first (Type const *node) |
Return first node in the tree to which node belongs to. | |
Type * | rbtree_last (Type const *node) |
Return last node in the tree to which node belongs to. | |
int | rbtree_height (Type const *node) |
Return height of the tree below node. | |
Red-black tree.
This file contain a red-black-tree template for C. The red-black-tree is a balanced binary tree containing structures as nodes.
The prototypes for red-black-tree functions are declared with macro RBTREE_PROTOS(). The implementation is instantiated with macro RBTREE_BODIES().
When a entry with new identical key is added to the tree, it can be either inserted (replacing other node with same key value) or appended.
Example code can be found from <rbtree_test.c>.
#define RBTREE_BODIES | ( | SCOPE, | |
prefix, | |||
Type, | |||
left, | |||
right, | |||
parent, | |||
IS_RED, | |||
SET_RED, | |||
IS_BLACK, | |||
SET_BLACK, | |||
COPY_COLOR, | |||
CMP, | |||
INSERT, | |||
REMOVE | |||
) |
Define bodies for red-black tree functions.
SCOPE | function scope (e.g., su_inline) |
prefix | function prefix (e.g., rbtree) |
Type | node type |
left | accessor of left node |
right | accessor of right node |
parent | accessor of parent node |
IS_RED | predicate testing if node is red |
SET_RED | setter marking node as red |
IS_BLACK | predicate testing if node is black |
SET_BLACK | setter marking node as black |
COPY_COLOR | method copying color from node to another |
CMP | method comparing two nodes |
INSERT | setter marking node as inserted to the tree |
REMOVE | method marking node as removed and possibly deleting node |
#define RBTREE_PROTOS | ( | SCOPE, | |
prefix, | |||
Type | |||
) |
Define prototypes for red-black tree functions.
SCOPE | function scope (e.g., su_inline) |
prefix | function prefix (e.g., rbtree) |
Type | node type |
Append a node into the tree.
tree | pointer to the root of the tree |
node | pointer to node to be appended |
0 | when successful (always) |
Return first node in the tree to which node belongs to.
node | pointer to node |
int rbtree_height | ( | Type const * | node | ) |
Return height of the tree below node.
node | pointer to node |
Insert a node into the tree.
tree | pointer to the root of the tree |
node | pointer to node to be inserted |
return_old | return value parameter for matching node already in the tree |
0 | if node was inserted |
-1 | if there already was an matching node and return_old is NULL. |
Return last node in the tree to which node belongs to.
node | pointer to node |
Return inorder precedessor of node node.
node | pointer to node |
Remove a node from the tree.
tree | pointer to the root of the tree |
node | pointer to node to be appended |