Loading...
Searching...
No Matches
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.
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.

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

  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);
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.
Definition rbtree.h:647
su_inline
#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

  SCOPE | function scope (e.g., su_inline)
  prefix | function prefix (e.g., rbtree)
  Type | node type

Example
  RBTREE_PROTOS(su_inline, rbtree, struct node);
  RBTREE_PROTOS
  #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

  tree | pointer to the root of the tree
  node | pointer to node to be appended

Return values

  0 | when successful (always)

## rbtree_first()

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.

## rbtree_height()

int rbtree_height | ( | Type const * | node | ) |

Return height of the tree below node.

Parameters

  node | pointer 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

  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.

## rbtree_last()

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.

## rbtree_prec()

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.

## rbtree_remove()

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

## rbtree_succ()

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.11devel - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.