]>
git.proxmox.com Git - mirror_frr.git/blob - lib/openbsd-tree.c
1 /* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
4 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
31 * Permission to use, copy, modify, and distribute this software for any
32 * purpose with or without fee is hereby granted, provided that the above
33 * copyright notice and this permission notice appear in all copies.
35 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
36 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
37 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
38 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
39 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
40 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
41 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
46 #include <lib/openbsd-tree.h>
48 static inline struct rb_entry
*
49 rb_n2e(const struct rb_type
*t
, void *node
)
51 unsigned long addr
= (unsigned long)node
;
53 return ((struct rb_entry
*)(addr
+ t
->t_offset
));
57 rb_e2n(const struct rb_type
*t
, struct rb_entry
*rbe
)
59 unsigned long addr
= (unsigned long)rbe
;
61 return ((void *)(addr
- t
->t_offset
));
64 #define RBE_LEFT(_rbe) (_rbe)->rbt_left
65 #define RBE_RIGHT(_rbe) (_rbe)->rbt_right
66 #define RBE_PARENT(_rbe) (_rbe)->rbt_parent
67 #define RBE_COLOR(_rbe) (_rbe)->rbt_color
69 #define RBH_ROOT(_rbt) (_rbt)->rbt_root
72 rbe_set(struct rb_entry
*rbe
, struct rb_entry
*parent
)
74 RBE_PARENT(rbe
) = parent
;
75 RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) = NULL
;
76 RBE_COLOR(rbe
) = RB_RED
;
80 rbe_set_blackred(struct rb_entry
*black
, struct rb_entry
*red
)
82 RBE_COLOR(black
) = RB_BLACK
;
83 RBE_COLOR(red
) = RB_RED
;
87 rbe_augment(const struct rb_type
*t
, struct rb_entry
*rbe
)
89 (*t
->t_augment
)(rb_e2n(t
, rbe
));
93 rbe_if_augment(const struct rb_type
*t
, struct rb_entry
*rbe
)
95 if (t
->t_augment
!= NULL
)
100 rbe_rotate_left(const struct rb_type
*t
, struct rbt_tree
*rbt
,
101 struct rb_entry
*rbe
)
103 struct rb_entry
*parent
;
104 struct rb_entry
*tmp
;
106 tmp
= RBE_RIGHT(rbe
);
107 RBE_RIGHT(rbe
) = RBE_LEFT(tmp
);
108 if (RBE_RIGHT(rbe
) != NULL
)
109 RBE_PARENT(RBE_LEFT(tmp
)) = rbe
;
111 parent
= RBE_PARENT(rbe
);
112 RBE_PARENT(tmp
) = parent
;
113 if (parent
!= NULL
) {
114 if (rbe
== RBE_LEFT(parent
))
115 RBE_LEFT(parent
) = tmp
;
117 RBE_RIGHT(parent
) = tmp
;
122 RBE_PARENT(rbe
) = tmp
;
124 if (t
->t_augment
!= NULL
) {
127 parent
= RBE_PARENT(tmp
);
129 rbe_augment(t
, parent
);
134 rbe_rotate_right(const struct rb_type
*t
, struct rbt_tree
*rbt
,
135 struct rb_entry
*rbe
)
137 struct rb_entry
*parent
;
138 struct rb_entry
*tmp
;
141 RBE_LEFT(rbe
) = RBE_RIGHT(tmp
);
142 if (RBE_LEFT(rbe
) != NULL
)
143 RBE_PARENT(RBE_RIGHT(tmp
)) = rbe
;
145 parent
= RBE_PARENT(rbe
);
146 RBE_PARENT(tmp
) = parent
;
147 if (parent
!= NULL
) {
148 if (rbe
== RBE_LEFT(parent
))
149 RBE_LEFT(parent
) = tmp
;
151 RBE_RIGHT(parent
) = tmp
;
155 RBE_RIGHT(tmp
) = rbe
;
156 RBE_PARENT(rbe
) = tmp
;
158 if (t
->t_augment
!= NULL
) {
161 parent
= RBE_PARENT(tmp
);
163 rbe_augment(t
, parent
);
168 rbe_insert_color(const struct rb_type
*t
, struct rbt_tree
*rbt
,
169 struct rb_entry
*rbe
)
171 struct rb_entry
*parent
, *gparent
, *tmp
;
173 while ((parent
= RBE_PARENT(rbe
)) != NULL
&&
174 RBE_COLOR(parent
) == RB_RED
) {
175 gparent
= RBE_PARENT(parent
);
177 if (parent
== RBE_LEFT(gparent
)) {
178 tmp
= RBE_RIGHT(gparent
);
179 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
180 RBE_COLOR(tmp
) = RB_BLACK
;
181 rbe_set_blackred(parent
, gparent
);
186 if (RBE_RIGHT(parent
) == rbe
) {
187 rbe_rotate_left(t
, rbt
, parent
);
193 rbe_set_blackred(parent
, gparent
);
194 rbe_rotate_right(t
, rbt
, gparent
);
196 tmp
= RBE_LEFT(gparent
);
197 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
198 RBE_COLOR(tmp
) = RB_BLACK
;
199 rbe_set_blackred(parent
, gparent
);
204 if (RBE_LEFT(parent
) == rbe
) {
205 rbe_rotate_right(t
, rbt
, parent
);
211 rbe_set_blackred(parent
, gparent
);
212 rbe_rotate_left(t
, rbt
, gparent
);
216 RBE_COLOR(RBH_ROOT(rbt
)) = RB_BLACK
;
220 rbe_remove_color(const struct rb_type
*t
, struct rbt_tree
*rbt
,
221 struct rb_entry
*parent
, struct rb_entry
*rbe
)
223 struct rb_entry
*tmp
;
225 /* Silence clang possible NULL deference warning. */
229 while ((rbe
== NULL
|| RBE_COLOR(rbe
) == RB_BLACK
) &&
230 rbe
!= RBH_ROOT(rbt
)) {
231 if (RBE_LEFT(parent
) == rbe
) {
232 tmp
= RBE_RIGHT(parent
);
233 if (RBE_COLOR(tmp
) == RB_RED
) {
234 rbe_set_blackred(tmp
, parent
);
235 rbe_rotate_left(t
, rbt
, parent
);
236 tmp
= RBE_RIGHT(parent
);
238 if ((RBE_LEFT(tmp
) == NULL
||
239 RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) &&
240 (RBE_RIGHT(tmp
) == NULL
||
241 RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
242 RBE_COLOR(tmp
) = RB_RED
;
244 parent
= RBE_PARENT(rbe
);
246 if (RBE_RIGHT(tmp
) == NULL
||
247 RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
) {
248 struct rb_entry
*oleft
;
250 oleft
= RBE_LEFT(tmp
);
252 RBE_COLOR(oleft
) = RB_BLACK
;
254 RBE_COLOR(tmp
) = RB_RED
;
255 rbe_rotate_right(t
, rbt
, tmp
);
256 tmp
= RBE_RIGHT(parent
);
259 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
260 RBE_COLOR(parent
) = RB_BLACK
;
262 RBE_COLOR(RBE_RIGHT(tmp
)) = RB_BLACK
;
264 rbe_rotate_left(t
, rbt
, parent
);
269 tmp
= RBE_LEFT(parent
);
270 if (RBE_COLOR(tmp
) == RB_RED
) {
271 rbe_set_blackred(tmp
, parent
);
272 rbe_rotate_right(t
, rbt
, parent
);
273 tmp
= RBE_LEFT(parent
);
276 if ((RBE_LEFT(tmp
) == NULL
||
277 RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) &&
278 (RBE_RIGHT(tmp
) == NULL
||
279 RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
280 RBE_COLOR(tmp
) = RB_RED
;
282 parent
= RBE_PARENT(rbe
);
284 if (RBE_LEFT(tmp
) == NULL
||
285 RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) {
286 struct rb_entry
*oright
;
288 oright
= RBE_RIGHT(tmp
);
290 RBE_COLOR(oright
) = RB_BLACK
;
292 RBE_COLOR(tmp
) = RB_RED
;
293 rbe_rotate_left(t
, rbt
, tmp
);
294 tmp
= RBE_LEFT(parent
);
297 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
298 RBE_COLOR(parent
) = RB_BLACK
;
299 if (RBE_LEFT(tmp
) != NULL
)
300 RBE_COLOR(RBE_LEFT(tmp
)) = RB_BLACK
;
302 rbe_rotate_right(t
, rbt
, parent
);
310 RBE_COLOR(rbe
) = RB_BLACK
;
313 static inline struct rb_entry
*
314 rbe_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
316 struct rb_entry
*child
, *parent
, *old
= rbe
;
319 if (RBE_LEFT(rbe
) == NULL
)
320 child
= RBE_RIGHT(rbe
);
321 else if (RBE_RIGHT(rbe
) == NULL
)
322 child
= RBE_LEFT(rbe
);
324 struct rb_entry
*tmp
;
326 rbe
= RBE_RIGHT(rbe
);
327 while ((tmp
= RBE_LEFT(rbe
)) != NULL
)
330 child
= RBE_RIGHT(rbe
);
331 parent
= RBE_PARENT(rbe
);
332 color
= RBE_COLOR(rbe
);
334 RBE_PARENT(child
) = parent
;
335 if (parent
!= NULL
) {
336 if (RBE_LEFT(parent
) == rbe
)
337 RBE_LEFT(parent
) = child
;
339 RBE_RIGHT(parent
) = child
;
341 rbe_if_augment(t
, parent
);
343 RBH_ROOT(rbt
) = child
;
344 if (RBE_PARENT(rbe
) == old
)
348 tmp
= RBE_PARENT(old
);
350 if (RBE_LEFT(tmp
) == old
)
353 RBE_RIGHT(tmp
) = rbe
;
355 rbe_if_augment(t
, parent
);
359 RBE_PARENT(RBE_LEFT(old
)) = rbe
;
361 RBE_PARENT(RBE_RIGHT(old
)) = rbe
;
363 if (t
->t_augment
!= NULL
&& parent
!= NULL
) {
367 tmp
= RBE_PARENT(tmp
);
368 } while (tmp
!= NULL
);
374 parent
= RBE_PARENT(rbe
);
375 color
= RBE_COLOR(rbe
);
378 RBE_PARENT(child
) = parent
;
379 if (parent
!= NULL
) {
380 if (RBE_LEFT(parent
) == rbe
)
381 RBE_LEFT(parent
) = child
;
383 RBE_RIGHT(parent
) = child
;
385 rbe_if_augment(t
, parent
);
387 RBH_ROOT(rbt
) = child
;
389 if (color
== RB_BLACK
)
390 rbe_remove_color(t
, rbt
, parent
, child
);
396 _rb_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
398 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
399 struct rb_entry
*old
;
401 old
= rbe_remove(t
, rbt
, rbe
);
403 return (old
== NULL
? NULL
: rb_e2n(t
, old
));
407 _rb_insert(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
409 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
410 struct rb_entry
*tmp
;
411 struct rb_entry
*parent
= NULL
;
416 while (tmp
!= NULL
) {
419 node
= rb_e2n(t
, tmp
);
420 comp
= (*t
->t_compare
)(elm
, node
);
424 tmp
= RBE_RIGHT(tmp
);
429 rbe_set(rbe
, parent
);
431 if (parent
!= NULL
) {
433 RBE_LEFT(parent
) = rbe
;
435 RBE_RIGHT(parent
) = rbe
;
437 rbe_if_augment(t
, parent
);
441 rbe_insert_color(t
, rbt
, rbe
);
446 /* Finds the node with the same key as elm */
448 _rb_find(const struct rb_type
*t
, struct rbt_tree
*rbt
, const void *key
)
450 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
454 while (tmp
!= NULL
) {
455 node
= rb_e2n(t
, tmp
);
456 comp
= (*t
->t_compare
)(key
, node
);
460 tmp
= RBE_RIGHT(tmp
);
468 /* Finds the first node greater than or equal to the search key */
470 _rb_nfind(const struct rb_type
*t
, struct rbt_tree
*rbt
, const void *key
)
472 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
477 while (tmp
!= NULL
) {
478 node
= rb_e2n(t
, tmp
);
479 comp
= (*t
->t_compare
)(key
, node
);
484 tmp
= RBE_RIGHT(tmp
);
493 _rb_next(const struct rb_type
*t
, void *elm
)
495 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
497 if (RBE_RIGHT(rbe
) != NULL
) {
498 rbe
= RBE_RIGHT(rbe
);
499 while (RBE_LEFT(rbe
) != NULL
)
502 if (RBE_PARENT(rbe
) &&
503 (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
504 rbe
= RBE_PARENT(rbe
);
506 while (RBE_PARENT(rbe
) &&
507 (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
508 rbe
= RBE_PARENT(rbe
);
509 rbe
= RBE_PARENT(rbe
);
513 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
517 _rb_prev(const struct rb_type
*t
, void *elm
)
519 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
523 while (RBE_RIGHT(rbe
))
524 rbe
= RBE_RIGHT(rbe
);
526 if (RBE_PARENT(rbe
) &&
527 (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
528 rbe
= RBE_PARENT(rbe
);
530 while (RBE_PARENT(rbe
) &&
531 (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
532 rbe
= RBE_PARENT(rbe
);
533 rbe
= RBE_PARENT(rbe
);
537 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
541 _rb_root(const struct rb_type
*t
, struct rbt_tree
*rbt
)
543 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
545 return (rbe
== NULL
? rbe
: rb_e2n(t
, rbe
));
549 _rb_min(const struct rb_type
*t
, struct rbt_tree
*rbt
)
551 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
552 struct rb_entry
*parent
= NULL
;
554 while (rbe
!= NULL
) {
559 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
563 _rb_max(const struct rb_type
*t
, struct rbt_tree
*rbt
)
565 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
566 struct rb_entry
*parent
= NULL
;
568 while (rbe
!= NULL
) {
570 rbe
= RBE_RIGHT(rbe
);
573 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
577 _rb_left(const struct rb_type
*t
, void *node
)
579 struct rb_entry
*rbe
= rb_n2e(t
, node
);
581 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
585 _rb_right(const struct rb_type
*t
, void *node
)
587 struct rb_entry
*rbe
= rb_n2e(t
, node
);
588 rbe
= RBE_RIGHT(rbe
);
589 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
593 _rb_parent(const struct rb_type
*t
, void *node
)
595 struct rb_entry
*rbe
= rb_n2e(t
, node
);
596 rbe
= RBE_PARENT(rbe
);
597 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
601 _rb_set_left(const struct rb_type
*t
, void *node
, void *left
)
603 struct rb_entry
*rbe
= rb_n2e(t
, node
);
604 struct rb_entry
*rbl
= (left
== NULL
) ? NULL
: rb_n2e(t
, left
);
610 _rb_set_right(const struct rb_type
*t
, void *node
, void *right
)
612 struct rb_entry
*rbe
= rb_n2e(t
, node
);
613 struct rb_entry
*rbr
= (right
== NULL
) ? NULL
: rb_n2e(t
, right
);
615 RBE_RIGHT(rbe
) = rbr
;
619 _rb_set_parent(const struct rb_type
*t
, void *node
, void *parent
)
621 struct rb_entry
*rbe
= rb_n2e(t
, node
);
622 struct rb_entry
*rbp
= (parent
== NULL
) ? NULL
: rb_n2e(t
, parent
);
624 RBE_PARENT(rbe
) = rbp
;
628 _rb_poison(const struct rb_type
*t
, void *node
, unsigned long poison
)
630 struct rb_entry
*rbe
= rb_n2e(t
, node
);
632 RBE_PARENT(rbe
) = RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) =
633 (struct rb_entry
*)poison
;
637 _rb_check(const struct rb_type
*t
, void *node
, unsigned long poison
)
639 struct rb_entry
*rbe
= rb_n2e(t
, node
);
641 return ((unsigned long)RBE_PARENT(rbe
) == poison
&&
642 (unsigned long)RBE_LEFT(rbe
) == poison
&&
643 (unsigned long)RBE_RIGHT(rbe
) == poison
);