1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/**********************************************************
5* See the LICENSE file for copyright infomation. *
6**********************************************************/
7
8#ifndef RED_BLACK_TREE_H
9#define RED_BLACK_TREE_H
10
11#ifdef __cplusplus
12extern "C" {
13#endif
14
15#ifdef DMALLOC
16#include <dmalloc.h>
17#endif
18#include "misc.h"
19#include "stack.h"
20
21/* CONVENTIONS: All data structures for red-black trees have the prefix */
22/* "rb_" to prevent name conflicts. */
23/* */
24/* Function names: Each word in a function name begins with */
25/* a capital letter. An example funcntion name is */
26/* CreateRedTree(a,b,c). Furthermore, each function name */
27/* should begin with a capital letter to easily distinguish */
28/* them from variables. */
29/* */
30/* Variable names: Each word in a variable name begins with */
31/* a capital letter EXCEPT the first letter of the variable */
32/* name. For example, int newLongInt. Global variables have */
33/* names beginning with "g". An example of a global */
34/* variable name is gNewtonsConstant. */
35
36/* comment out the line below to remove all the debugging assertion */
37/* checks from the compiled code. */
38/* #define DEBUG_ASSERT 1 */
39
40typedef struct rb_red_blk_node {
41 void* key;
42 void* info;
43 int red; /* if red=0 then the node is black */
44 struct rb_red_blk_node* left;
45 struct rb_red_blk_node* right;
46 struct rb_red_blk_node* parent;
47} rb_red_blk_node;
48
49
50/* Compare(a,b) should return 1 if *a > *b, -1 if *a < *b, and 0 otherwise */
51/* Destroy(a) takes a pointer to whatever key might be and frees it accordingly */
52typedef struct rb_red_blk_tree {
53 int (*Compare)(const void* a, const void* b);
54 void (*DestroyKey)(void* a);
55 void (*DestroyInfo)(void* a);
56 void (*PrintKey)(const void* a);
57 void (*PrintInfo)(void* a);
58 /* A sentinel is used for root and for nil. These sentinels are */
59 /* created when RBTreeCreate is caled. root->left should always */
60 /* point to the node which is the root of the tree. nil points to a */
61 /* node which should always be black but has aribtrary children and */
62 /* parent and no key or info. The point of using these sentinels is so */
63 /* that the root and nil nodes do not require special cases in the code */
64 rb_red_blk_node* root;
65 rb_red_blk_node* nil;
66} rb_red_blk_tree;
67
68rb_red_blk_tree* RBTreeCreate(int (*CompFunc)(const void*, const void*),
69 void (*DestFunc)(void*),
70 void (*InfoDestFunc)(void*),
71 void (*PrintFunc)(const void*),
72 void (*PrintInfo)(void*));
73rb_red_blk_node * RBTreeInsert(rb_red_blk_tree*, void* key, void* info);
74void RBTreePrint(rb_red_blk_tree*);
75void RBDelete(rb_red_blk_tree* , rb_red_blk_node* );
76void RBTreeDestroy(rb_red_blk_tree*);
77rb_red_blk_node* TreePredecessor(rb_red_blk_tree*,rb_red_blk_node*);
78rb_red_blk_node* TreeSuccessor(rb_red_blk_tree*,rb_red_blk_node*);
79rb_red_blk_node* RBExactQuery(rb_red_blk_tree*, void*);
80stk_stack * RBEnumerate(rb_red_blk_tree* tree,void* low, void* high);
81void NullFunction(void*);
82
83#ifdef __cplusplus
84}
85#endif
86
87#endif
88