Red-black tree. More...
Go to the source code of this file.
Defines | |
| #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 LEFT(node) ((node)->left) #define RIGHT(node) ((node)->right) #define PARENT(node) ((node)->parent) #define SET_RED(node) ((node)->black = 0) #define SET_BLACK(node) ((node)->black = 1) #define CMP(a, b) ((a)->value - (b)->value) #define IS_RED(node) ((node) && (node)->black == 0) #define IS_BLACK(node) (!(node) || (node)->black == 1) #define COPY_COLOR(dst, src) ((dst)->black = (src)->black) #define INSERT(node) ((node)->inserted = 1) #define REMOVE(node) ((node)->left = (node)->right = (node)->parent = NULL, \ (node)->inserted = 0) RBTREE_BODIES(su_inline, rbtree, struct node, LEFT, RIGHT, PARENT, IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, CMP, INSERT, REMOVE);
| #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.
| SCOPE | function scope (e.g., su_inline) | |
| prefix | function prefix (e.g., rbtree) | |
| Type | node type |
RBTREE_PROTOS(su_inline, rbtree, struct node);
| typedef struct node Type |
Type used for rbtree nodes.
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 |
