1 /* $Id$ */
2
3 /*
4 *
5 * Copyright (C) 1998 David Mazieres (dm@uun.org)
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation; either version 2, or (at
10 * your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
20 * USA
21 *
22 */
23
24
25 #include "itree.h"
26
27 #define oc __opaquecontainer_pointer
28 #define itree_entry __itree_entry_private
29
30 /* Define some gross macros to avoid a lot of typing. These asssume a
31 * local variable 'os' contains the offset of the itree_entry
32 * structure in the opaque container structure. */
33 static inline struct itree_entry *oc2rb (oc, const int)
34 __attribute__ ((const));
35 static inline struct itree_entry *
oc2rb(oc o,const int os)36 oc2rb (oc o, const int os)
37 {
38 return (struct itree_entry *) ((char *) o + os);
39 }
40 #define up(n) oc2rb (n, os)->rbe_up
41 #define left(n) oc2rb (n, os)->rbe_left
42 #define right(n) oc2rb (n, os)->rbe_right
43 #define color(n) ((n) ? oc2rb (n, os)->rbe_color : BLACK)
44 #define lcolor(n) oc2rb (n, os)->rbe_color
45
46 static void
itree_left_rotate(oc * r,oc x,const int os)47 itree_left_rotate (oc *r, oc x, const int os)
48 {
49 oc y = right (x);
50 if ((right (x) = left (y)))
51 up (left (y)) = x;
52 up (y) = up (x);
53 if (!up (x))
54 *r = y;
55 else if (x == left (up (x)))
56 left (up (x)) = y;
57 else
58 right (up (x)) = y;
59 left (y) = x;
60 up (x) = y;
61 }
62
63 static void
itree_right_rotate(oc * r,oc y,const int os)64 itree_right_rotate (oc *r, oc y, const int os)
65 {
66 oc x = left (y);
67 if ((left (y) = right (x)))
68 up (right (x)) = y;
69 up (x) = up (y);
70 if (!up (y))
71 *r = x;
72 else if (y == right (up (y)))
73 right (up (y)) = x;
74 else
75 left (up (y)) = x;
76 right (x) = y;
77 up (y) = x;
78 }
79
80 /* Turn any newly inserted node red. Then fix things up if the new
81 * node's parent is also red. Note that this routine assumes the root
82 * of the tree is black. */
83 static inline void
itree_insert_fix(oc * r,oc x,const int os)84 itree_insert_fix (oc *r, oc x, const int os)
85 {
86 oc y;
87
88 lcolor (x) = RED;
89 while (color (up (x)) == RED) {
90 oc gp = up (up (x));
91 if (up (x) == left (gp)) {
92 y = right (gp);
93 if (color (y) == RED) {
94 lcolor (up (x)) = BLACK;
95 lcolor (y) = BLACK;
96 lcolor (gp) = RED;
97 x = gp;
98 }
99 else {
100 if (x == right (up (x))) {
101 x = up (x);
102 itree_left_rotate (r, x, os);
103 }
104 lcolor (up (x)) = BLACK;
105 lcolor (up (up (x))) = RED;
106 itree_right_rotate (r, up (up (x)), os);
107 }
108 }
109 else {
110 y = left (gp);
111 if (color (y) == RED) {
112 lcolor (up (x)) = BLACK;
113 lcolor (y) = BLACK;
114 lcolor (gp) = RED;
115 x = gp;
116 }
117 else {
118 if (x == left (up (x))) {
119 x = up (x);
120 itree_right_rotate (r, x, os);
121 }
122 lcolor (up (x)) = BLACK;
123 lcolor (up (up (x))) = RED;
124 itree_left_rotate (r, up (up (x)), os);
125 }
126 }
127 }
128 lcolor (*r) = BLACK;
129 }
130
131 void
itree_insert(oc * r,oc z,const int os,int (* cmpfn)(void *,oc,oc),void * cmparg)132 itree_insert (oc *r, oc z, const int os,
133 int (*cmpfn) (void *, oc, oc), void *cmparg)
134 {
135 oc y, x;
136 int cmpres = 0;
137
138 left (z) = right (z) = y = NULL;
139 for (x = *r; x; x = cmpres < 0 ? left (x) : right (x)) {
140 y = x;
141 cmpres = cmpfn (cmparg, z, x);
142 }
143 up (z) = y;
144 if (!y)
145 *r = z;
146 else if (cmpres < 0)
147 left (y) = z;
148 else
149 right (y) = z;
150 itree_insert_fix (r, z, os);
151 }
152
153 static inline oc
itree_minimum(oc x,const int os)154 itree_minimum (oc x, const int os)
155 {
156 oc y;
157 while ((y = left (x)))
158 x = y;
159 return x;
160 }
161
162 oc
itree_successor(oc x,const int os)163 itree_successor (oc x, const int os)
164 {
165 oc y;
166 if ((y = right (x)))
167 return itree_minimum (y, os);
168 for (y = up (x); y && x == right (y); y = up (y))
169 x = y;
170 return y;
171 }
172
173 static inline oc
itree_maximum(oc x,const int os)174 itree_maximum (oc x, const int os)
175 {
176 oc y;
177 while ((y = right (x)))
178 x = y;
179 return x;
180 }
181
182 oc
itree_predecessor(oc x,const int os)183 itree_predecessor (oc x, const int os)
184 {
185 oc y;
186 if ((y = left (x)))
187 return itree_maximum (y, os);
188 for (y = up (x); y && x == left (y); y = up (y))
189 x = y;
190 return y;
191 }
192
193 static inline void
itree_delete_fixup(oc * r,oc x,oc p,const int os)194 itree_delete_fixup (oc *r, oc x, oc p, const int os)
195 {
196 oc w;
197
198 assert (!x || up (x) == p);
199 while (x != *r && color (x) == BLACK) {
200 if (x)
201 p = up (x);
202 if (x == left (p)) {
203 w = right (p);
204 if (color (w) == RED) {
205 lcolor (w) = BLACK;
206 lcolor (p) = RED;
207 itree_left_rotate (r, p, os);
208 w = right (p);
209 }
210 if (color (left (w)) == BLACK && color (right (w)) == BLACK) {
211 lcolor (w) = RED;
212 x = p;
213 }
214 else {
215 if (color (right (w)) == BLACK) {
216 lcolor (left (w)) = BLACK;
217 lcolor (w) = RED;
218 itree_right_rotate (r, w, os);
219 w = right (p);
220 }
221 lcolor (w) = color (p);
222 lcolor (p) = BLACK;
223 lcolor (right (w)) = BLACK;
224 itree_left_rotate (r, p, os);
225 x = *r;
226 }
227 }
228 else {
229 w = left (p);
230 if (color (w) == RED) {
231 lcolor (w) = BLACK;
232 lcolor (p) = RED;
233 itree_right_rotate (r, p, os);
234 w = left (p);
235 }
236 if (color (right (w)) == BLACK && color (left (w)) == BLACK) {
237 lcolor (w) = RED;
238 x = p;
239 }
240 else {
241 if (color (left (w)) == BLACK) {
242 lcolor (right (w)) = BLACK;
243 lcolor (w) = RED;
244 itree_left_rotate (r, w, os);
245 w = left (p);
246 }
247 lcolor (w) = color (p);
248 lcolor (p) = BLACK;
249 lcolor (left (w)) = BLACK;
250 itree_right_rotate (r, p, os);
251 x = *r;
252 }
253 }
254 }
255 if (x)
256 lcolor (x) = BLACK;
257 }
258
259 void
itree_delete(oc * r,oc z,const int os)260 itree_delete (oc *r, oc z, const int os)
261 {
262 oc x, y, p;
263 enum itree_color c;
264
265 y = left (z) && right (z) ? itree_successor (z, os) : z;
266 p = up (y);
267 if ((x = left (y)) || (x = right (y)))
268 up (x) = p;
269 if (!p)
270 *r = x;
271 else if (y == left (p))
272 left (p) = x;
273 else
274 right (p) = x;
275 c = color (y);
276
277 if (y != z) {
278 oc pz = up (z);
279 if (pz) {
280 if (z == left (pz))
281 left (pz) = y;
282 else
283 right (pz) = y;
284 }
285 else
286 *r = y;
287 if ((pz = left (z)))
288 up (pz) = y;
289 if ((pz = right (z)))
290 up (pz) = y;
291 *oc2rb (y, os) = *oc2rb (z, os);
292 if (p == z)
293 p = y;
294 }
295
296 if (c == BLACK)
297 itree_delete_fixup (r, x, p, os);
298 }
299
300 static void
itree_check_node(oc x,oc low,oc high,int bd,const int lbd,const int os,int (* cmpfn)(void *,oc,oc),void * cmparg)301 itree_check_node (oc x, oc low, oc high, int bd, const int lbd,
302 const int os,
303 int (*cmpfn) (void *, oc, oc), void *cmparg)
304 {
305 /* These variables are primarily to make it easier to look at values
306 * when debugging, hence the volatile and usused. */
307 volatile oc l, r, p;
308 volatile enum itree_color cx, cl, cr, cp __attribute__((unused));
309
310 if (color (x) == BLACK)
311 bd++;
312 if (!x) {
313 assert (bd == lbd);
314 return;
315 }
316
317 cx = color (x);
318 p = up (x);
319 cp = color (p);
320 l = left (x);
321 cl = color (l);
322 r = right (x);
323 cr = color (r);
324
325 assert (!l || up (l) == x);
326 assert (!r || up (r) == x);
327 assert (cx == BLACK || cx == RED);
328 assert (cx == BLACK || (cl == BLACK && cr == BLACK));
329 assert (!low || cmpfn (cmparg, low, x) <= 0);
330 assert (!high || cmpfn (cmparg, x, high) <= 0);
331
332 itree_check_node (l, low, x, bd, lbd, os, cmpfn, cmparg);
333 itree_check_node (r, x, high, bd, lbd, os, cmpfn, cmparg);
334 }
335
336 void
__itree_check(oc * r,const int os,int (* cmpfn)(void *,oc,oc),void * cmparg)337 __itree_check (oc *r, const int os,
338 int (*cmpfn) (void *, oc, oc), void *cmparg)
339 {
340 oc x;
341 int lbd = 0;
342
343 assert (color (*r) == BLACK);
344 for (x = *r; x;) {
345 x = left (x);
346 if (color (x) == BLACK)
347 lbd++;
348 }
349
350 assert (!*r || !up (*r));
351 itree_check_node (*r, NULL, NULL, -1, lbd, os, cmpfn, cmparg);
352 }
353