Root/qpkg/jrb.h

Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 8 years 10 months ago.
By Werner Almesberger, qpkg: added James S. Plank's red-black trees
1/*
2Libraries for fields, doubly-linked lists and red-black trees.
3Copyright (C) 2001 James S. Plank
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License as published by the Free Software Foundation; either
8version 2.1 of the License, or (at your option) any later version.
9
10This library is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13Lesser General Public License for more details.
14
15You should have received a copy of the GNU Lesser General Public
16License along with this library; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19---------------------------------------------------------------------------
20Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
21for instruction on how to use this library.
22
23Jim Plank
24plank@cs.utk.edu
25http://www.cs.utk.edu/~plank
26
27Associate Professor
28Department of Computer Science
29University of Tennessee
30203 Claxton Complex
311122 Volunteer Blvd.
32Knoxville, TN 37996-3450
33
34     865-974-4397
35Fax: 865-974-4404
36 */
37#ifndef _JRB_H_
38#define _JRB_H_
39
40#include "jval.h"
41
42/* Main jrb_node. You only ever use the fields
43   flink
44   blink
45   k.key or k.ikey
46   v.val
47*/
48
49
50typedef struct jrb_node {
51  unsigned char red;
52  unsigned char internal;
53  unsigned char left;
54  unsigned char roothead; /* (bit 1 is root, bit 2 is head) */
55  struct jrb_node *flink;
56  struct jrb_node *blink;
57  struct jrb_node *parent;
58  Jval key;
59  Jval val;
60} *JRB;
61
62
63extern JRB make_jrb(void); /* Creates a new rb-tree */
64
65
66/* Creates a node with key key and val val and inserts it into the tree.
67   jrb_insert uses strcmp() as comparison funcion. jrb_inserti uses <>=,
68   jrb_insertg uses func() */
69
70extern JRB jrb_insert_str(JRB tree, char *key, Jval val);
71extern JRB jrb_insert_int(JRB tree, int ikey, Jval val);
72extern JRB jrb_insert_dbl(JRB tree, double dkey, Jval val);
73extern JRB jrb_insert_gen(JRB tree, Jval key, Jval val, int (*func)(Jval,Jval));
74
75/* returns an external node in t whose value is equal k. Returns NULL if
76   there is no such node in the tree */
77
78extern JRB jrb_find_str(JRB root, char *key);
79extern JRB jrb_find_int(JRB root, int ikey);
80extern JRB jrb_find_dbl(JRB root, double dkey);
81extern JRB jrb_find_gen(JRB root, Jval, int (*func)(Jval, Jval));
82
83
84/* returns an external node in t whose value is equal
85  k or whose value is the smallest value greater than k. Sets found to
86  1 if the key was found, and 0 otherwise. */
87
88extern JRB jrb_find_gte_str(JRB root, char *key, int *found);
89extern JRB jrb_find_gte_int(JRB root, int ikey, int *found);
90extern JRB jrb_find_gte_dbl(JRB root, double dkey, int *found);
91extern JRB jrb_find_gte_gen(JRB root, Jval key,
92                              int (*func)(Jval, Jval), int *found);
93
94
95/* Creates a node with key key and val val and inserts it into the
96   tree before/after node nd. Does not check to ensure that you are
97   keeping the correct order */
98
99extern void jrb_delete_node(JRB node); /* Deletes and frees a node (but
100                                              not the key or val) */
101extern void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */
102
103extern Jval jrb_val(JRB node); /* Returns node->v.val -- this is to shut
104                                       lint up */
105
106extern int jrb_nblack(JRB n); /* returns # of black nodes in path from
107                                    n to the root */
108int jrb_plength(JRB n); /* returns the # of nodes in path from
109                    n to the root */
110 
111#define jrb_first(n) ((n)->flink)
112#define jrb_last(n) ((n)->blink)
113#define jrb_next(n) ((n)->flink)
114#define jrb_prev(n) ((n)->blink)
115#define jrb_empty(t) ((t)->flink == (t))
116#ifndef jrb_nil
117#define jrb_nil(t) (t)
118#endif
119 
120#define jrb_traverse(ptr, lst) \
121  for(ptr = jrb_first(lst); ptr != jrb_nil(lst); ptr = jrb_next(ptr))
122 
123#define jrb_rtraverse(ptr, lst) \
124  for(ptr = jrb_last(lst); ptr != jrb_nil(lst); ptr = jrb_prev(ptr))
125 
126#endif
127

Archive Download this file

Branches:
master



interactive