1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
/*
Generic C code for red-black trees.
Copyright (C) 2000 James S. Plank,
2004 Tuomo Valkonen.
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA
*/
/* Revision 1.2. Jim Plank */
/* Original code by Jim Plank (plank@cs.utk.edu) */
/* modified for THINK C 6.0 for Macintosh by Chris Bartley */
#ifndef LIBTU_RB_H
#define LIBTU_RB_H
typedef struct rb_status {
unsigned red : 1 ;
unsigned internal : 1 ;
unsigned left : 1 ;
unsigned root : 1 ;
unsigned head : 1 ;
} Rb_status;
/* Main rb_node. You only ever use the fields
c.list.flink
c.list.blink
k.key or k.ikey
v.val
*/
typedef struct rb_node {
union {
struct {
struct rb_node *flink;
struct rb_node *blink;
} list;
struct {
struct rb_node *left;
struct rb_node *right;
} child;
} c;
union {
struct rb_node *parent;
struct rb_node *root;
} p;
Rb_status s;
union {
int ikey;
const void *key;
struct rb_node *lext;
} k;
union {
int ival;
void *val;
struct rb_node *rext;
} v;
} *Rb_node;
typedef int Rb_compfn(const void *, const void *);
extern Rb_node make_rb(); /* Creates a new rb-tree */
/* Creates a node with key key and val val and inserts it into the tree.
rb_insert uses strcmp() as comparison funcion. rb_inserti uses <>=,
rb_insertg uses func() */
extern Rb_node rb_insert(Rb_node tree, const char *key, void *val);
extern Rb_node rb_inserti(Rb_node tree, int ikey, void *val);
extern Rb_node rb_insertp(Rb_node tree, const void *key, void *val);
extern Rb_node rb_insertg(Rb_node tree, const void *key, void *val,
Rb_compfn *func);
/* returns an external node in t whose value is equal
k or whose value is the smallest value greater than k. */
extern Rb_node rb_find_key(Rb_node root, const char *key);
extern Rb_node rb_find_ikey(Rb_node root, int ikey);
extern Rb_node rb_find_pkey(Rb_node root, const void *key);
extern Rb_node rb_find_gkey(Rb_node root, const void *key, Rb_compfn *func);
/* Works just like the find_key versions only it returns whether or not
it found the key in the integer variable found */
extern Rb_node rb_find_key_n(Rb_node root, const char *key, int *found);
extern Rb_node rb_find_ikey_n(Rb_node root, int ikey, int *found);
extern Rb_node rb_find_pkey_n(Rb_node root, const void *key, int *found);
extern Rb_node rb_find_gkey_n(Rb_node root, const void *key,
Rb_compfn *func, int *found);
/* Creates a node with key key and val val and inserts it into the
tree before/after node nd. Does not check to ensure that you are
keeping the correct order */
extern Rb_node rb_insert_b(Rb_node nd, const void *key, void *val);
extern Rb_node rb_insert_a(Rb_node nd, const void *key, void *val);
extern void rb_delete_node(Rb_node node); /* Deletes and frees a node (but
not the key or val) */
extern void rb_free_tree(Rb_node root); /* Deletes and frees an entire tree */
extern void *rb_val(Rb_node node); /* Returns node->v.val -- this is to shut
lint up */
extern int rb_nblack(Rb_node n); /* returns # of black nodes in path from
n to the root */
int rb_plength(Rb_node n); /* returns the # of nodes in path from
n to the root */
#define rb_first(n) (n->c.list.flink)
#define rb_last(n) (n->c.list.blink)
#define rb_next(n) (n->c.list.flink)
#define rb_prev(n) (n->c.list.blink)
#define rb_empty(t) (t->c.list.flink == t)
#ifndef rb_nil
#define rb_nil(t) (t)
#endif
#define rb_traverse(ptr, lst) \
for(ptr = rb_first(lst); ptr != rb_nil(lst); ptr = rb_next(ptr))
#endif /* LIBTU_RB_H */
|
