su 1.12.11devel
Loading...
Searching...
No Matches
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.
 
#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.
 
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.
 

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

◆ RBTREE_BODIES

#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_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.
Definition rbtree.h:647
#define su_inline
Define as suitable declarator static inline functions.
Definition su_configure.h:90

◆ RBTREE_PROTOS

#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);
#define RBTREE_PROTOS(SCOPE, prefix, Type)
Define prototypes for red-black tree functions.
Definition rbtree.h:598

Function Documentation

◆ rbtree_append()

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)

◆ rbtree_first()

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.

◆ rbtree_height()

int rbtree_height ( Type const *  node)

Return height of the tree below node.

Parameters
nodepointer to node
Returns
Height of the tree.

◆ rbtree_insert()

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.

◆ rbtree_last()

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.

◆ rbtree_prec()

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.

◆ rbtree_remove()

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

◆ rbtree_succ()

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.