1 /*========================================================================
2 //
3 // rbtree.c
4 //
5 // Red Black tree implementation
6 //
7 //========================================================================
8 // ####ECOSGPLCOPYRIGHTBEGIN####
9 // -------------------------------------------
10 // This file is part of eCos, the Embedded Configurable Operating System.
11 // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
12 //
13 // eCos is free software; you can redistribute it and/or modify it under
14 // the terms of the GNU General Public License as published by the Free
15 // Software Foundation; either version 2 or (at your option) any later
16 // version.
17 //
18 // eCos is distributed in the hope that it will be useful, but WITHOUT
19 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
20 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 // for more details.
22 //
23 // You should have received a copy of the GNU General Public License
24 // along with eCos; if not, write to the Free Software Foundation, Inc.,
25 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
26 //
27 // As a special exception, if other files instantiate templates or use
28 // macros or inline functions from this file, or you compile this file
29 // and link it with other works to produce a work based on this file,
30 // this file does not by itself cause the resulting work to be covered by
31 // the GNU General Public License. However the source code for this file
32 // must still be made available in accordance with section (3) of the GNU
33 // General Public License v2.
34 //
35 // This exception does not invalidate any other reasons why a work based
36 // on this file might be covered by the GNU General Public License.
37 // -------------------------------------------
38 // ####ECOSGPLCOPYRIGHTEND####
39 //========================================================================
40 //#####DESCRIPTIONBEGIN####
41 //
42 // Author(s): Niels Provos/OpenBSD
43 // Contributors: dwmw2
44 // Date: 2003-01-21
45 // Purpose: This file provides an implementation of red-black trees.
46 // Description: Derived from OpenBSD src/sys/sys/tree.h
47 // Usage:
48 //
49 //####DESCRIPTIONEND####
50 //
51 //======================================================================
52 */
53
54 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
55 /*
56 * Copyright 2002 Niels Provos <[email protected]>
57 * All rights reserved.
58 *
59 * Redistribution and use in source and binary forms, with or without
60 * modification, are permitted provided that the following conditions
61 * are met:
62 * 1. Redistributions of source code must retain the above copyright
63 * notice, this list of conditions and the following disclaimer.
64 * 2. Redistributions in binary form must reproduce the above copyright
65 * notice, this list of conditions and the following disclaimer in the
66 * documentation and/or other materials provided with the distribution.
67 *
68 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
69 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
70 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
71 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
72 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
73 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
74 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
75 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
76 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
77 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
78 */
79
80 /* Fields renamed to match Linux ones. */
81 #include <linux/rbtree.h>
82
83
84 #define RB_HEAD(head) (head)->rb_node
85 #define RB_LEFT(elm) (elm)->rb_left
86 #define RB_RIGHT(elm) (elm)->rb_right
87 #define RB_PARENT(elm) (elm)->rb_parent
88 #define RB_COLOR(elm) (elm)->rb_color
89
90
91 #define RB_SET(elm, parent) do { \
92 RB_PARENT(elm) = parent; \
93 RB_LEFT(elm) = RB_RIGHT(elm) = NULL; \
94 RB_COLOR(elm) = RB_RED; \
95 } while (0)
96
97 #define RB_SET_BLACKRED(black, red) do { \
98 RB_COLOR(black) = RB_BLACK; \
99 RB_COLOR(red) = RB_RED; \
100 } while (0)
101
102 #ifndef RB_AUGMENT
103 #define RB_AUGMENT(x)
104 #endif
105
106 #define RB_ROTATE_LEFT(head, elm, tmp) do { \
107 (tmp) = RB_RIGHT(elm); \
108 if ((RB_RIGHT(elm) = RB_LEFT(tmp))) { \
109 RB_PARENT(RB_LEFT(tmp)) = (elm); \
110 } \
111 RB_AUGMENT(elm); \
112 if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \
113 if ((elm) == RB_LEFT(RB_PARENT(elm))) \
114 RB_LEFT(RB_PARENT(elm)) = (tmp); \
115 else \
116 RB_RIGHT(RB_PARENT(elm)) = (tmp); \
117 } else \
118 (head)->rb_node = (tmp); \
119 RB_LEFT(tmp) = (elm); \
120 RB_PARENT(elm) = (tmp); \
121 RB_AUGMENT(tmp); \
122 if ((RB_PARENT(tmp))) \
123 RB_AUGMENT(RB_PARENT(tmp)); \
124 } while (0)
125
126 #define RB_ROTATE_RIGHT(head, elm, tmp) do { \
127 (tmp) = RB_LEFT(elm); \
128 if ((RB_LEFT(elm) = RB_RIGHT(tmp))) { \
129 RB_PARENT(RB_RIGHT(tmp)) = (elm); \
130 } \
131 RB_AUGMENT(elm); \
132 if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \
133 if ((elm) == RB_LEFT(RB_PARENT(elm))) \
134 RB_LEFT(RB_PARENT(elm)) = (tmp); \
135 else \
136 RB_RIGHT(RB_PARENT(elm)) = (tmp); \
137 } else \
138 (head)->rb_node = (tmp); \
139 RB_RIGHT(tmp) = (elm); \
140 RB_PARENT(elm) = (tmp); \
141 RB_AUGMENT(tmp); \
142 if ((RB_PARENT(tmp))) \
143 RB_AUGMENT(RB_PARENT(tmp)); \
144 } while(0)
145
146 /* Note args swapped to match Linux */
rb_insert_color(struct rb_node * elm,struct rb_root * head)147 void rb_insert_color(struct rb_node *elm, struct rb_root *head)
148 {
149 struct rb_node *parent, *gparent, *tmp;
150 while ((parent = RB_PARENT(elm)) &&
151 RB_COLOR(parent) == RB_RED) {
152 gparent = RB_PARENT(parent);
153 if (parent == RB_LEFT(gparent)) {
154 tmp = RB_RIGHT(gparent);
155 if (tmp && RB_COLOR(tmp) == RB_RED) {
156 RB_COLOR(tmp) = RB_BLACK;
157 RB_SET_BLACKRED(parent, gparent);
158 elm = gparent;
159 continue;
160 }
161 if (RB_RIGHT(parent) == elm) {
162 RB_ROTATE_LEFT(head, parent, tmp);
163 tmp = parent;
164 parent = elm;
165 elm = tmp;
166 }
167 RB_SET_BLACKRED(parent, gparent);
168 RB_ROTATE_RIGHT(head, gparent, tmp);
169 } else {
170 tmp = RB_LEFT(gparent);
171 if (tmp && RB_COLOR(tmp) == RB_RED) {
172 RB_COLOR(tmp) = RB_BLACK;
173 RB_SET_BLACKRED(parent, gparent);
174 elm = gparent;
175 continue;
176 }
177 if (RB_LEFT(parent) == elm) {
178 RB_ROTATE_RIGHT(head, parent, tmp);
179 tmp = parent;
180 parent = elm;
181 elm = tmp;
182 }
183 RB_SET_BLACKRED(parent, gparent);
184 RB_ROTATE_LEFT(head, gparent, tmp);
185 }
186 }
187 RB_COLOR(head->rb_node) = RB_BLACK;
188 }
189
190
rb_remove_color(struct rb_root * head,struct rb_node * parent,struct rb_node * elm)191 static void rb_remove_color(struct rb_root *head, struct rb_node *parent,
192 struct rb_node *elm)
193 {
194 struct rb_node *tmp;
195 while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
196 elm != RB_HEAD(head)) {
197 if (RB_LEFT(parent) == elm) {
198 tmp = RB_RIGHT(parent);
199 if (RB_COLOR(tmp) == RB_RED) {
200 RB_SET_BLACKRED(tmp, parent);
201 RB_ROTATE_LEFT(head, parent, tmp);
202 tmp = RB_RIGHT(parent);
203 }
204 if ((RB_LEFT(tmp) == NULL ||
205 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
206 (RB_RIGHT(tmp) == NULL ||
207 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
208 RB_COLOR(tmp) = RB_RED;
209 elm = parent;
210 parent = RB_PARENT(elm);
211 } else {
212 if (RB_RIGHT(tmp) == NULL ||
213 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
214 struct rb_node *oleft;
215 if ((oleft = RB_LEFT(tmp)))
216 RB_COLOR(oleft) = RB_BLACK;
217 RB_COLOR(tmp) = RB_RED;
218 RB_ROTATE_RIGHT(head, tmp, oleft);
219 tmp = RB_RIGHT(parent);
220 }
221 RB_COLOR(tmp) = RB_COLOR(parent);
222 RB_COLOR(parent) = RB_BLACK;
223 if (RB_RIGHT(tmp))
224 RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
225 RB_ROTATE_LEFT(head, parent, tmp);
226 elm = RB_HEAD(head);
227 break;
228 }
229 } else {
230 tmp = RB_LEFT(parent);
231 if (RB_COLOR(tmp) == RB_RED) {
232 RB_SET_BLACKRED(tmp, parent);
233 RB_ROTATE_RIGHT(head, parent, tmp);
234 tmp = RB_LEFT(parent);
235 }
236 if ((RB_LEFT(tmp) == NULL ||
237 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
238 (RB_RIGHT(tmp) == NULL ||
239 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
240 RB_COLOR(tmp) = RB_RED;
241 elm = parent;
242 parent = RB_PARENT(elm);
243 } else {
244 if (RB_LEFT(tmp) == NULL ||
245 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
246 struct rb_node *oright;
247 if ((oright = RB_RIGHT(tmp)))
248 RB_COLOR(oright) = RB_BLACK;
249 RB_COLOR(tmp) = RB_RED;
250 RB_ROTATE_LEFT(head, tmp, oright);
251 tmp = RB_LEFT(parent);
252 }
253 RB_COLOR(tmp) = RB_COLOR(parent);
254 RB_COLOR(parent) = RB_BLACK;
255 if (RB_LEFT(tmp))
256 RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
257 RB_ROTATE_RIGHT(head, parent, tmp);
258 elm = RB_HEAD(head);
259 break;
260 }
261 }
262 }
263 if (elm)
264 RB_COLOR(elm) = RB_BLACK;
265 }
266
267 /* Note name changed. Guess why :) */
rb_erase(struct rb_node * elm,struct rb_root * head)268 void rb_erase(struct rb_node *elm, struct rb_root *head)
269 {
270 struct rb_node *child, *parent, *old = elm;
271 int color;
272 if (RB_LEFT(elm) == NULL)
273 child = RB_RIGHT(elm);
274 else if (RB_RIGHT(elm) == NULL)
275 child = RB_LEFT(elm);
276 else {
277 struct rb_node *left;
278 elm = RB_RIGHT(elm);
279 while ((left = RB_LEFT(elm)))
280 elm = left;
281 child = RB_RIGHT(elm);
282 parent = RB_PARENT(elm);
283 color = RB_COLOR(elm);
284 if (child)
285 RB_PARENT(child) = parent;
286 if (parent) {
287 if (RB_LEFT(parent) == elm)
288 RB_LEFT(parent) = child;
289 else
290 RB_RIGHT(parent) = child;
291 RB_AUGMENT(parent);
292 } else
293 RB_HEAD(head) = child;
294 if (RB_PARENT(elm) == old)
295 parent = elm;
296 *(elm) = *(old);
297 if (RB_PARENT(old)) {
298 if (RB_LEFT(RB_PARENT(old)) == old)
299 RB_LEFT(RB_PARENT(old)) = elm;
300 else
301 RB_RIGHT(RB_PARENT(old)) = elm;
302 RB_AUGMENT(RB_PARENT(old));
303 } else
304 RB_HEAD(head) = elm;
305 RB_PARENT(RB_LEFT(old)) = elm;
306 if (RB_RIGHT(old))
307 RB_PARENT(RB_RIGHT(old)) = elm;
308 if (parent) {
309 left = parent;
310 do {
311 RB_AUGMENT(left);
312 } while ((left = RB_PARENT(left)));
313 }
314 goto color;
315 }
316 parent = RB_PARENT(elm);
317 color = RB_COLOR(elm);
318 if (child)
319 RB_PARENT(child) = parent;
320 if (parent) {
321 if (RB_LEFT(parent) == elm)
322 RB_LEFT(parent) = child;
323 else
324 RB_RIGHT(parent) = child;
325 RB_AUGMENT(parent);
326 } else
327 RB_HEAD(head) = child;
328 color:
329 if (color == RB_BLACK)
330 rb_remove_color(head, parent, child);
331 }
332
rb_next(struct rb_node * elm)333 struct rb_node *rb_next(struct rb_node *elm)
334 {
335 if (RB_RIGHT(elm)) {
336 elm = RB_RIGHT(elm);
337 while (RB_LEFT(elm))
338 elm = RB_LEFT(elm);
339 } else {
340 if (RB_PARENT(elm) &&
341 (elm == RB_LEFT(RB_PARENT(elm))))
342 elm = RB_PARENT(elm);
343 else {
344 while (RB_PARENT(elm) &&
345 (elm == RB_RIGHT(RB_PARENT(elm))))
346 elm = RB_PARENT(elm);
347 elm = RB_PARENT(elm);
348 }
349 }
350 return (elm);
351 }
352
rb_prev(struct rb_node * elm)353 struct rb_node *rb_prev(struct rb_node *elm)
354 {
355 if (RB_LEFT(elm)) {
356 elm = RB_LEFT(elm);
357 while (RB_RIGHT(elm))
358 elm = RB_RIGHT(elm);
359 } else {
360 if (RB_PARENT(elm) &&
361 (elm == RB_RIGHT(RB_PARENT(elm))))
362 elm = RB_PARENT(elm);
363 else {
364 while (RB_PARENT(elm) &&
365 (elm == RB_LEFT(RB_PARENT(elm))))
366 elm = RB_PARENT(elm);
367 elm = RB_PARENT(elm);
368 }
369 }
370 return (elm);
371 }
372
373 /* These ones are lifted from Linux -- but that's OK because I
374 wrote them. dwmw2. */
rb_first(struct rb_root * root)375 struct rb_node *rb_first(struct rb_root *root)
376 {
377 struct rb_node *n;
378
379 n = root->rb_node;
380 if (!n)
381 return 0;
382 while (n->rb_left)
383 n = n->rb_left;
384 return n;
385 }
386
rb_replace_node(struct rb_node * victim,struct rb_node * new,struct rb_root * root)387 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
388 struct rb_root *root)
389 {
390 struct rb_node *parent = victim->rb_parent;
391
392 /* Set the surrounding nodes to point to the replacement */
393 if (parent) {
394 if (victim == parent->rb_left)
395 parent->rb_left = new;
396 else
397 parent->rb_right = new;
398 } else {
399 root->rb_node = new;
400 }
401 if (victim->rb_left)
402 victim->rb_left->rb_parent = new;
403 if (victim->rb_right)
404 victim->rb_right->rb_parent = new;
405
406 /* Copy the pointers/colour from the victim to the replacement */
407 *new = *victim;
408 }
409