su  1.12.11devel
 All Data Structures Files Functions Variables Typedefs Enumerator Macros Groups Pages
Macros | Typedefs | Functions
rbtree.h File Reference

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. More...
 
#define RBTREE_PROTOS(SCOPE, prefix, Type)
 Define prototypes for red-black tree functions. More...
 
#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. More...
 

Typedefs

typedef struct node Type
 Type used for rbtree nodes. More...
 

Functions

int rbtree_insert (Type **tree, Type *node, Type **return_old)
 Insert a node into the tree. More...
 
int rbtree_append (Type **tree, Type *node)
 Append a node into the tree. More...
 
void rbtree_remove (Type **tree, Type *node)
 Remove a node from the tree. More...
 
Typerbtree_succ (Type const *node)
 Return inorder successor of node node. More...
 
Typerbtree_prec (Type const *node)
 Return inorder precedessor of node node. More...
 
Typerbtree_first (Type const *node)
 Return first node in the tree to which node belongs to. More...
 
Typerbtree_last (Type const *node)
 Return last node in the tree to which node belongs to. More...
 
int rbtree_height (Type const *node)
 Return height of the tree below node. More...
 

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.nosp@m..Pes.nosp@m.si@no.nosp@m.kia..nosp@m.com.
Date
Created: Tue Sep 7 19:45:11 EEST 2004 ppessi

Macro Definition 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
SCOPEfunction scope (e.g., su_inline)
prefixfunction prefix (e.g., rbtree)
Typenode type
leftaccessor of left node
rightaccessor of right node
parentaccessor of parent node
IS_REDpredicate testing if node is red
SET_REDsetter marking node as red
IS_BLACKpredicate testing if node is black
SET_BLACKsetter marking node as black
COPY_COLORmethod copying color from node to another
CMPmethod comparing two nodes
INSERTsetter marking node as inserted to the tree
REMOVEmethod 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_H

Defined when <sofia-sip/rbtree.h> has been included.

#define RBTREE_PROTOS (   SCOPE,
  prefix,
  Type 
)

Define prototypes for red-black tree functions.

Parameters
SCOPEfunction scope (e.g., su_inline)
prefixfunction prefix (e.g., rbtree)
Typenode type
Example
RBTREE_PROTOS(su_inline, rbtree, struct node);

Typedef Documentation

typedef struct node Type

Type used for rbtree nodes.

Function Documentation

int rbtree_append ( Type **  tree,
Type node 
)

Append a node into the tree.

Parameters
treepointer to the root of the tree
nodepointer to node to be appended
Return values
0when successful (always)
Type* rbtree_first ( Type const *  node)

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

Parameters
nodepointer to node
Returns
Pointer to first node.
int rbtree_height ( Type const *  node)

Return height of the tree below node.

Parameters
nodepointer to node
Returns
Height of the tree.
int rbtree_insert ( Type **  tree,
Type node,
Type **  return_old 
)

Insert a node into the tree.

Parameters
treepointer to the root of the tree
nodepointer to node to be inserted
return_oldreturn value parameter for matching node already in the tree
Return values
0if node was inserted
-1if 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
nodepointer to node
Returns
Pointer to last node.
Type* rbtree_prec ( Type const *  node)

Return inorder precedessor of node node.

Parameters
nodepointer 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
treepointer to the root of the tree
nodepointer to node to be appended
Type* rbtree_succ ( Type const *  node)

Return inorder successor of node node.

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

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