Graphviz  2.41.20170921.2350
red_black_tree.h
Go to the documentation of this file.
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
12 extern "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 
40 typedef struct rb_red_blk_node {
41  void* key;
42  void* info;
43  int red; /* if red=0 then the node is black */
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 */
52 typedef 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 */
67 
68 rb_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*));
73 rb_red_blk_node * RBTreeInsert(rb_red_blk_tree*, void* key, void* info);
80 stk_stack * RBEnumerate(rb_red_blk_tree* tree,void* low, void* high);
81 void NullFunction(void*);
82 
83 #ifdef __cplusplus
84 }
85 #endif
86 
87 #endif
void(* DestroyKey)(void *a)
struct rb_red_blk_node * parent
rb_red_blk_node * nil
rb_red_blk_node * RBTreeInsert(rb_red_blk_tree *tree, void *key, void *info)
struct rb_red_blk_node rb_red_blk_node
void(* PrintKey)(const void *a)
rb_red_blk_node * TreeSuccessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
int
Definition: grammar.c:1264
int(* Compare)(const void *a, const void *b)
void RBDelete(rb_red_blk_tree *tree, rb_red_blk_node *z)
void(* DestroyInfo)(void *a)
stk_stack * RBEnumerate(rb_red_blk_tree *tree, void *low, void *high)
void NullFunction(void *junk)
Definition: misc.c:72
rb_red_blk_tree * RBTreeCreate(int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *), void(*InfoDestFunc)(void *), void(*PrintFunc)(const void *), void(*PrintInfo)(void *))
void RBTreePrint(rb_red_blk_tree *tree)
rb_red_blk_node * TreePredecessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
void(* PrintInfo)(void *a)
void RBTreeDestroy(rb_red_blk_tree *tree)
struct rb_red_blk_tree rb_red_blk_tree
rb_red_blk_node * RBExactQuery(rb_red_blk_tree *tree, void *q)
struct rb_red_blk_node * right
struct rb_red_blk_node * left
rb_red_blk_node * root