Root/qpkg/jrb.h

Source at commit a9f12d56661a8e6def5a2b32519c3efd55e38d31 created 8 years 11 months ago.
By Werner Almesberger, qpkg: converted ID comparison from "struct id *" to "void *"
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
38/* Heavily edited and reformatted to K&R style 2010 by Werner Almesberger */
39
40
41#ifndef _JRB_H_
42#define _JRB_H_
43
44/* Main jrb_node. You only ever use the fields
45   flink
46   blink
47   k.key or k.ikey
48   v.val
49*/
50
51
52struct jrb {
53    unsigned char red;
54    unsigned char internal;
55    unsigned char left;
56    unsigned char roothead; /* (bit 1 is root, bit 2 is head) */
57    struct jrb *flink;
58    struct jrb *blink;
59    struct jrb *parent;
60    void *key;
61    void *val;
62};
63
64
65struct jrb *make_jrb(void); /* Creates a new rb-tree */
66
67
68/* Creates a node with key key and val val and inserts it into the tree.
69   jrb_insert uses strcmp() as comparison funcion. jrb_inserti uses <>=,
70   jrb_insertg uses func() */
71
72struct jrb *jrb_insert(struct jrb *tree, void *key, void *val,
73    int (*func)(const void *a, const void *b));
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
78struct jrb *jrb_find(struct jrb *root, const void *key,
79    int (*func)(const void *a, const void *b));
80
81/* returns an external node in t whose value is equal
82  k or whose value is the smallest value greater than k. Sets found to
83  1 if the key was found, and 0 otherwise. */
84
85struct jrb *jrb_find_gte(struct jrb *root, const void *key,
86    int (*func)(const void *a, const void *b), int *found);
87
88
89/* Creates a node with key key and val val and inserts it into the
90   tree before/after node nd. Does not check to ensure that you are
91   keeping the correct order */
92
93void jrb_delete_node(struct jrb *node); /* Deletes and frees a node (but
94                                            not the key or val) */
95void jrb_free_tree(struct jrb *root); /* Deletes and frees an entire tree */
96
97void *jrb_val(struct jrb *node); /* Returns node->v.val -- this is to shut
98                                     lint up */
99
100int jrb_nblack(struct jrb *n); /* returns # of black nodes in path from
101                                  n to the root */
102int jrb_plength(struct jrb *n); /* returns the # of nodes in path from
103                   n to the root */
104
105#define jrb_first(n) ((n)->flink)
106#define jrb_last(n) ((n)->blink)
107#define jrb_next(n) ((n)->flink)
108#define jrb_prev(n) ((n)->blink)
109#define jrb_empty(t) ((t)->flink == (t))
110#ifndef jrb_nil
111#define jrb_nil(t) (t)
112#endif
113
114#define jrb_traverse(ptr, lst) \
115    for (ptr = jrb_first(lst); ptr != jrb_nil(lst); ptr = jrb_next(ptr))
116
117#define jrb_rtraverse(ptr, lst) \
118    for (ptr = jrb_last(lst); ptr != jrb_nil(lst); ptr = jrb_prev(ptr))
119
120#endif
121

Archive Download this file

Branches:
master



interactive