-
Notifications
You must be signed in to change notification settings - Fork 0
/
jrb.h
117 lines (89 loc) · 3.68 KB
/
jrb.h
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
/*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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
---------------------------------------------------------------------------
Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
for instruction on how to use this library.
Jim Plank
http://www.cs.utk.edu/~plank
Associate Professor
Department of Computer Science
University of Tennessee
203 Claxton Complex
1122 Volunteer Blvd.
Knoxville, TN 37996-3450
865-974-4397
Fax: 865-974-4404
*/
#ifndef _JRB_H_
#define _JRB_H_
#include "jval.h"
/* Main jrb_node. You only ever use the fields
flink
blink
k.key or k.ikey
v.val
*/
typedef struct jrb_node {
unsigned char red;
unsigned char internal;
unsigned char left;
unsigned char roothead; /* (bit 1 is root, bit 2 is head) */
struct jrb_node *flink;
struct jrb_node *blink;
struct jrb_node *parent;
Jval key;
Jval val;
} *JRB;
extern JRB make_jrb(); /* Creates a new rb-tree */
/* Creates a node with key key and val val and inserts it into the tree.
jrb_insert uses strcmp() as comparison funcion. jrb_inserti uses <>=,
jrb_insertg uses func() */
extern JRB jrb_insert_str(JRB tree, char *key, Jval val);
extern JRB jrb_insert_int(JRB tree, int ikey, Jval val);
extern JRB jrb_insert_dbl(JRB tree, double dkey, Jval val);
extern JRB jrb_insert_gen(JRB tree, Jval key, Jval val, int (*func)(Jval,Jval));
/* returns an external node in t whose value is equal k. Returns NULL if
there is no such node in the tree */
extern JRB jrb_find_str(JRB root, char *key);
extern JRB jrb_find_int(JRB root, int ikey);
extern JRB jrb_find_dbl(JRB root, double dkey);
extern JRB jrb_find_gen(JRB root, Jval, int (*func)(Jval, Jval));
/* returns an external node in t whose value is equal
k or whose value is the smallest value greater than k. Sets found to
1 if the key was found, and 0 otherwise. */
extern JRB jrb_find_gte_str(JRB root, char *key, int *found);
extern JRB jrb_find_gte_int(JRB root, int ikey, int *found);
extern JRB jrb_find_gte_dbl(JRB root, double dkey, int *found);
extern JRB jrb_find_gte_gen(JRB root, Jval key,
int (*func)(Jval, Jval), 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 void jrb_delete_node(JRB node); /* Deletes and frees a node (but
not the key or val) */
extern void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */
extern Jval jrb_val(JRB node); /* Returns node->v.val -- this is to shut
lint up */
extern int jrb_nblack(JRB n); /* returns # of black nodes in path from
n to the root */
int jrb_plength(JRB n); /* returns the # of nodes in path from
n to the root */
#define jrb_first(n) (n->flink)
#define jrb_last(n) (n->blink)
#define jrb_next(n) (n->flink)
#define jrb_prev(n) (n->blink)
#define jrb_empty(t) (t->flink == t)
#ifndef jrb_nil
#define jrb_nil(t) (t)
#endif
#define jrb_traverse(ptr, lst) \
for(ptr = jrb_first(lst); ptr != jrb_nil(lst); ptr = jrb_next(ptr))
#define jrb_rtraverse(ptr, lst) \
for(ptr = jrb_last(lst); ptr != jrb_nil(lst); ptr = jrb_prev(ptr))
#endif