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.
Typerbtree_succ (Type const *node)
 Return inorder successor of node node.
Typerbtree_prec (Type const *node)
 Return inorder precedessor of node node.
Typerbtree_first (Type const *node)
 Return first node in the tree to which node belongs to.
Typerbtree_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., static 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(static 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., static inline)
prefix function prefix (e.g., rbtree)
Type node type
Example
 RBTREE_PROTOS(static 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.


Sofia-SIP 1.12.4 - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.