sofia-sip/rbtree.h File Reference

Detailed Description

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

Author:: Pekka Pessi <Pekka.Pessi@nokia-email.address.hidden>.

Date:: Created: Tue Sep 7 19:45:11 EEST 2004 ppessi

Go to the source code of this file.

Defines

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

Define Documentation

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

Parameters:

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

Example

#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_PROTOS ( SCOPE,
prefix,
Type )

Define prototypes for red-black tree functions.

Parameters:

SCOPE function scope (e.g., su_inline)

prefix function prefix (e.g., rbtree)

Type node type

Example
RBTREE_PROTOS(su_inline, rbtree, struct node);

Function Documentation

int rbtree_append ( Type ** tree,

Type * node

)

Append a node into the tree.

Parameters:

tree pointer to the root of the tree

node pointer to node to be appended

Return values:

0 when successful (always)

Type* rbtree_first ( Type const * node )

Return first node in the tree to which node belongs to.

Parameters:

node pointer to node

Returns:
Pointer to first node.

int rbtree_height ( Type const * node )

Return height of the tree below node.

Parameters:

node pointer to node

Returns:
Height of the tree.

int rbtree_insert ( Type ** tree,

Type * node,

Type ** return_old

)

Insert a node into the tree.

Parameters:

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

Return values:

0 if node was inserted

-1 if there already was an matching node and return_old is NULL.

Type* rbtree_last ( Type const * node )

Return last node in the tree to which node belongs to.

Parameters:

node pointer to node

Returns:
Pointer to last node.

Type* rbtree_prec ( Type const * node )

Return inorder precedessor of node node.

Parameters:

node pointer to node

Returns:
Pointer to precedessor, or NULL if node was first.

void rbtree_remove ( Type ** tree,

Type * node

)

Remove a node from the tree.

Parameters:

tree pointer to the root of the tree

node pointer to node to be appended

Type* rbtree_succ ( Type const * node )

Return inorder successor of node node.

Parameters:

node pointer to node

Returns:
Pointer to successor, or NULL if node was last.


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