Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit d3a27c7b9ba1179cd263208c3ee1275f547d43ff created 12 years 22 days ago. By Werner Almesberger, m1r1/dsv/SUPPLEMENT: delete mechanical components; fixed last non-Yageo bad link | |
---|---|
1 | /* |
2 | Libraries for fields, doubly-linked lists and red-black trees. |
3 | Copyright (C) 2001 James S. Plank |
4 | |
5 | This library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | This library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with this library; if not, write to the Free Software |
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
18 | |
19 | --------------------------------------------------------------------------- |
20 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ |
21 | for instruction on how to use this library. |
22 | |
23 | Jim Plank |
24 | plank@cs.utk.edu |
25 | http://www.cs.utk.edu/~plank |
26 | |
27 | Associate Professor |
28 | Department of Computer Science |
29 | University of Tennessee |
30 | 203 Claxton Complex |
31 | 1122 Volunteer Blvd. |
32 | Knoxville, TN 37996-3450 |
33 | |
34 | 865-974-4397 |
35 | Fax: 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 | |
52 | struct 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 | |
65 | struct 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 | |
72 | struct jrb *jrb_insert(struct jrb *tree, void *key, void *val, |
73 | int (*func)(const void *a, const void *b)); |
74 | |
75 | /* If the key already exists, return the node (without altering it). |
76 | Otherwise, insert a new node. */ |
77 | |
78 | struct jrb *jrb_find_or_insert(struct jrb *tree, void *key, void *val, |
79 | int (*func)(const void *a, const void *b)); |
80 | |
81 | /* returns an external node in t whose value is equal k. Returns NULL if |
82 | there is no such node in the tree */ |
83 | |
84 | struct jrb *jrb_find(struct jrb *root, const void *key, |
85 | int (*func)(const void *a, const void *b)); |
86 | |
87 | /* returns an external node in t whose value is equal |
88 | k or whose value is the smallest value greater than k. Sets found to |
89 | 1 if the key was found, and 0 otherwise. */ |
90 | |
91 | struct jrb *jrb_find_gte(struct jrb *root, const void *key, |
92 | int (*func)(const void *a, const void *b), 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 | |
99 | void jrb_delete_node(struct jrb *node); /* Deletes and frees a node (but |
100 | not the key or val) */ |
101 | void jrb_free_tree(struct jrb *root); /* Deletes and frees an entire tree */ |
102 | |
103 | void *jrb_val(struct jrb *node); /* Returns node->v.val -- this is to shut |
104 | lint up */ |
105 | |
106 | int jrb_nblack(struct jrb *n); /* returns # of black nodes in path from |
107 | n to the root */ |
108 | int jrb_plength(struct 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 |
Branches:
master