]>
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
*rb_n2e(const struct rb_type
*t
, void *node
)
50 unsigned long addr
= (unsigned long)node
;
52 return ((struct rb_entry
*)(addr
+ t
->t_offset
));
55 static inline void *rb_e2n(const struct rb_type
*t
, struct rb_entry
*rbe
)
57 unsigned long addr
= (unsigned long)rbe
;
59 return ((void *)(addr
- t
->t_offset
));
62 #define RBE_LEFT(_rbe) (_rbe)->rbt_left
63 #define RBE_RIGHT(_rbe) (_rbe)->rbt_right
64 #define RBE_PARENT(_rbe) (_rbe)->rbt_parent
65 #define RBE_COLOR(_rbe) (_rbe)->rbt_color
67 #define RBH_ROOT(_rbt) (_rbt)->rbt_root
69 static inline void rbe_set(struct rb_entry
*rbe
, struct rb_entry
*parent
)
71 RBE_PARENT(rbe
) = parent
;
72 RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) = NULL
;
73 RBE_COLOR(rbe
) = RB_RED
;
76 static inline void rbe_set_blackred(struct rb_entry
*black
,
79 RBE_COLOR(black
) = RB_BLACK
;
80 RBE_COLOR(red
) = RB_RED
;
83 static inline void rbe_augment(const struct rb_type
*t
, struct rb_entry
*rbe
)
85 (*t
->t_augment
)(rb_e2n(t
, rbe
));
88 static inline void rbe_if_augment(const struct rb_type
*t
, struct rb_entry
*rbe
)
90 if (t
->t_augment
!= NULL
)
94 static inline void rbe_rotate_left(const struct rb_type
*t
,
95 struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
97 struct rb_entry
*parent
;
100 tmp
= RBE_RIGHT(rbe
);
101 RBE_RIGHT(rbe
) = RBE_LEFT(tmp
);
102 if (RBE_RIGHT(rbe
) != NULL
)
103 RBE_PARENT(RBE_LEFT(tmp
)) = rbe
;
105 parent
= RBE_PARENT(rbe
);
106 RBE_PARENT(tmp
) = parent
;
107 if (parent
!= NULL
) {
108 if (rbe
== RBE_LEFT(parent
))
109 RBE_LEFT(parent
) = tmp
;
111 RBE_RIGHT(parent
) = tmp
;
116 RBE_PARENT(rbe
) = tmp
;
118 if (t
->t_augment
!= NULL
) {
121 parent
= RBE_PARENT(tmp
);
123 rbe_augment(t
, parent
);
127 static inline void rbe_rotate_right(const struct rb_type
*t
,
128 struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
130 struct rb_entry
*parent
;
131 struct rb_entry
*tmp
;
134 RBE_LEFT(rbe
) = RBE_RIGHT(tmp
);
135 if (RBE_LEFT(rbe
) != NULL
)
136 RBE_PARENT(RBE_RIGHT(tmp
)) = rbe
;
138 parent
= RBE_PARENT(rbe
);
139 RBE_PARENT(tmp
) = parent
;
140 if (parent
!= NULL
) {
141 if (rbe
== RBE_LEFT(parent
))
142 RBE_LEFT(parent
) = tmp
;
144 RBE_RIGHT(parent
) = tmp
;
148 RBE_RIGHT(tmp
) = rbe
;
149 RBE_PARENT(rbe
) = tmp
;
151 if (t
->t_augment
!= NULL
) {
154 parent
= RBE_PARENT(tmp
);
156 rbe_augment(t
, parent
);
160 static inline void rbe_insert_color(const struct rb_type
*t
,
161 struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
163 struct rb_entry
*parent
, *gparent
, *tmp
;
165 while ((parent
= RBE_PARENT(rbe
)) != NULL
166 && RBE_COLOR(parent
) == RB_RED
) {
167 gparent
= RBE_PARENT(parent
);
169 if (parent
== RBE_LEFT(gparent
)) {
170 tmp
= RBE_RIGHT(gparent
);
171 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
172 RBE_COLOR(tmp
) = RB_BLACK
;
173 rbe_set_blackred(parent
, gparent
);
178 if (RBE_RIGHT(parent
) == rbe
) {
179 rbe_rotate_left(t
, rbt
, parent
);
185 rbe_set_blackred(parent
, gparent
);
186 rbe_rotate_right(t
, rbt
, gparent
);
188 tmp
= RBE_LEFT(gparent
);
189 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
190 RBE_COLOR(tmp
) = RB_BLACK
;
191 rbe_set_blackred(parent
, gparent
);
196 if (RBE_LEFT(parent
) == rbe
) {
197 rbe_rotate_right(t
, rbt
, parent
);
203 rbe_set_blackred(parent
, gparent
);
204 rbe_rotate_left(t
, rbt
, gparent
);
208 RBE_COLOR(RBH_ROOT(rbt
)) = RB_BLACK
;
211 static inline void rbe_remove_color(const struct rb_type
*t
,
212 struct rbt_tree
*rbt
,
213 struct rb_entry
*parent
,
214 struct rb_entry
*rbe
)
216 struct rb_entry
*tmp
;
218 while ((rbe
== NULL
|| RBE_COLOR(rbe
) == RB_BLACK
)
219 && rbe
!= RBH_ROOT(rbt
) && parent
) {
220 if (RBE_LEFT(parent
) == rbe
) {
221 tmp
= RBE_RIGHT(parent
);
222 if (RBE_COLOR(tmp
) == RB_RED
) {
223 rbe_set_blackred(tmp
, parent
);
224 rbe_rotate_left(t
, rbt
, parent
);
225 tmp
= RBE_RIGHT(parent
);
227 if ((RBE_LEFT(tmp
) == NULL
228 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
)
229 && (RBE_RIGHT(tmp
) == NULL
230 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
231 RBE_COLOR(tmp
) = RB_RED
;
233 parent
= RBE_PARENT(rbe
);
235 if (RBE_RIGHT(tmp
) == NULL
236 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
) {
237 struct rb_entry
*oleft
;
239 oleft
= RBE_LEFT(tmp
);
241 RBE_COLOR(oleft
) = RB_BLACK
;
243 RBE_COLOR(tmp
) = RB_RED
;
244 rbe_rotate_right(t
, rbt
, tmp
);
245 tmp
= RBE_RIGHT(parent
);
248 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
249 RBE_COLOR(parent
) = RB_BLACK
;
251 RBE_COLOR(RBE_RIGHT(tmp
)) = RB_BLACK
;
253 rbe_rotate_left(t
, rbt
, parent
);
258 tmp
= RBE_LEFT(parent
);
259 if (RBE_COLOR(tmp
) == RB_RED
) {
260 rbe_set_blackred(tmp
, parent
);
261 rbe_rotate_right(t
, rbt
, parent
);
262 tmp
= RBE_LEFT(parent
);
265 if ((RBE_LEFT(tmp
) == NULL
266 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
)
267 && (RBE_RIGHT(tmp
) == NULL
268 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
269 RBE_COLOR(tmp
) = RB_RED
;
271 parent
= RBE_PARENT(rbe
);
273 if (RBE_LEFT(tmp
) == NULL
274 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) {
275 struct rb_entry
*oright
;
277 oright
= RBE_RIGHT(tmp
);
279 RBE_COLOR(oright
) = RB_BLACK
;
281 RBE_COLOR(tmp
) = RB_RED
;
282 rbe_rotate_left(t
, rbt
, tmp
);
283 tmp
= RBE_LEFT(parent
);
286 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
287 RBE_COLOR(parent
) = RB_BLACK
;
288 if (RBE_LEFT(tmp
) != NULL
)
289 RBE_COLOR(RBE_LEFT(tmp
)) = RB_BLACK
;
291 rbe_rotate_right(t
, rbt
, parent
);
299 RBE_COLOR(rbe
) = RB_BLACK
;
302 static inline struct rb_entry
*
303 rbe_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
305 struct rb_entry
*child
, *parent
, *old
= rbe
;
308 if (RBE_LEFT(rbe
) == NULL
)
309 child
= RBE_RIGHT(rbe
);
310 else if (RBE_RIGHT(rbe
) == NULL
)
311 child
= RBE_LEFT(rbe
);
313 struct rb_entry
*tmp
;
315 rbe
= RBE_RIGHT(rbe
);
316 while ((tmp
= RBE_LEFT(rbe
)) != NULL
)
319 child
= RBE_RIGHT(rbe
);
320 parent
= RBE_PARENT(rbe
);
321 color
= RBE_COLOR(rbe
);
323 RBE_PARENT(child
) = parent
;
324 if (parent
!= NULL
) {
325 if (RBE_LEFT(parent
) == rbe
)
326 RBE_LEFT(parent
) = child
;
328 RBE_RIGHT(parent
) = child
;
330 rbe_if_augment(t
, parent
);
332 RBH_ROOT(rbt
) = child
;
333 if (RBE_PARENT(rbe
) == old
)
337 tmp
= RBE_PARENT(old
);
339 if (RBE_LEFT(tmp
) == old
)
342 RBE_RIGHT(tmp
) = rbe
;
344 rbe_if_augment(t
, parent
);
348 RBE_PARENT(RBE_LEFT(old
)) = rbe
;
350 RBE_PARENT(RBE_RIGHT(old
)) = rbe
;
352 if (t
->t_augment
!= NULL
&& parent
!= NULL
) {
356 tmp
= RBE_PARENT(tmp
);
357 } while (tmp
!= NULL
);
363 parent
= RBE_PARENT(rbe
);
364 color
= RBE_COLOR(rbe
);
367 RBE_PARENT(child
) = parent
;
368 if (parent
!= NULL
) {
369 if (RBE_LEFT(parent
) == rbe
)
370 RBE_LEFT(parent
) = child
;
372 RBE_RIGHT(parent
) = child
;
374 rbe_if_augment(t
, parent
);
376 RBH_ROOT(rbt
) = child
;
378 if (color
== RB_BLACK
)
379 rbe_remove_color(t
, rbt
, parent
, child
);
384 void *_rb_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
386 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
387 struct rb_entry
*old
;
389 old
= rbe_remove(t
, rbt
, rbe
);
391 return (old
== NULL
? NULL
: rb_e2n(t
, old
));
394 void *_rb_insert(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
396 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
397 struct rb_entry
*tmp
;
398 struct rb_entry
*parent
= NULL
;
403 while (tmp
!= NULL
) {
406 node
= rb_e2n(t
, tmp
);
407 comp
= (*t
->t_compare
)(elm
, node
);
411 tmp
= RBE_RIGHT(tmp
);
416 rbe_set(rbe
, parent
);
418 if (parent
!= NULL
) {
420 RBE_LEFT(parent
) = rbe
;
422 RBE_RIGHT(parent
) = rbe
;
424 rbe_if_augment(t
, parent
);
428 rbe_insert_color(t
, rbt
, rbe
);
433 /* Finds the node with the same key as elm */
434 void *_rb_find(const struct rb_type
*t
, struct rbt_tree
*rbt
, const void *key
)
436 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
440 while (tmp
!= NULL
) {
441 node
= rb_e2n(t
, tmp
);
442 comp
= (*t
->t_compare
)(key
, node
);
446 tmp
= RBE_RIGHT(tmp
);
454 /* Finds the first node greater than or equal to the search key */
455 void *_rb_nfind(const struct rb_type
*t
, struct rbt_tree
*rbt
, const void *key
)
457 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
462 while (tmp
!= NULL
) {
463 node
= rb_e2n(t
, tmp
);
464 comp
= (*t
->t_compare
)(key
, node
);
469 tmp
= RBE_RIGHT(tmp
);
477 void *_rb_next(const struct rb_type
*t
, void *elm
)
479 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
481 if (RBE_RIGHT(rbe
) != NULL
) {
482 rbe
= RBE_RIGHT(rbe
);
483 while (RBE_LEFT(rbe
) != NULL
)
486 if (RBE_PARENT(rbe
) && (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
487 rbe
= RBE_PARENT(rbe
);
489 while (RBE_PARENT(rbe
)
490 && (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
491 rbe
= RBE_PARENT(rbe
);
492 rbe
= RBE_PARENT(rbe
);
496 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
499 void *_rb_prev(const struct rb_type
*t
, void *elm
)
501 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
505 while (RBE_RIGHT(rbe
))
506 rbe
= RBE_RIGHT(rbe
);
508 if (RBE_PARENT(rbe
) && (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
509 rbe
= RBE_PARENT(rbe
);
511 while (RBE_PARENT(rbe
)
512 && (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
513 rbe
= RBE_PARENT(rbe
);
514 rbe
= RBE_PARENT(rbe
);
518 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
521 void *_rb_root(const struct rb_type
*t
, struct rbt_tree
*rbt
)
523 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
525 return (rbe
== NULL
? rbe
: rb_e2n(t
, rbe
));
528 void *_rb_min(const struct rb_type
*t
, struct rbt_tree
*rbt
)
530 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
531 struct rb_entry
*parent
= NULL
;
533 while (rbe
!= NULL
) {
538 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
541 void *_rb_max(const struct rb_type
*t
, struct rbt_tree
*rbt
)
543 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
544 struct rb_entry
*parent
= NULL
;
546 while (rbe
!= NULL
) {
548 rbe
= RBE_RIGHT(rbe
);
551 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
554 void *_rb_left(const struct rb_type
*t
, void *node
)
556 struct rb_entry
*rbe
= rb_n2e(t
, node
);
558 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
561 void *_rb_right(const struct rb_type
*t
, void *node
)
563 struct rb_entry
*rbe
= rb_n2e(t
, node
);
564 rbe
= RBE_RIGHT(rbe
);
565 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
568 void *_rb_parent(const struct rb_type
*t
, void *node
)
570 struct rb_entry
*rbe
= rb_n2e(t
, node
);
571 rbe
= RBE_PARENT(rbe
);
572 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
575 void _rb_set_left(const struct rb_type
*t
, void *node
, void *left
)
577 struct rb_entry
*rbe
= rb_n2e(t
, node
);
578 struct rb_entry
*rbl
= (left
== NULL
) ? NULL
: rb_n2e(t
, left
);
583 void _rb_set_right(const struct rb_type
*t
, void *node
, void *right
)
585 struct rb_entry
*rbe
= rb_n2e(t
, node
);
586 struct rb_entry
*rbr
= (right
== NULL
) ? NULL
: rb_n2e(t
, right
);
588 RBE_RIGHT(rbe
) = rbr
;
591 void _rb_set_parent(const struct rb_type
*t
, void *node
, void *parent
)
593 struct rb_entry
*rbe
= rb_n2e(t
, node
);
594 struct rb_entry
*rbp
= (parent
== NULL
) ? NULL
: rb_n2e(t
, parent
);
596 RBE_PARENT(rbe
) = rbp
;
599 void _rb_poison(const struct rb_type
*t
, void *node
, unsigned long poison
)
601 struct rb_entry
*rbe
= rb_n2e(t
, node
);
603 RBE_PARENT(rbe
) = RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) =
604 (struct rb_entry
*)poison
;
607 int _rb_check(const struct rb_type
*t
, void *node
, unsigned long poison
)
609 struct rb_entry
*rbe
= rb_n2e(t
, node
);
611 return ((unsigned long)RBE_PARENT(rbe
) == poison
612 && (unsigned long)RBE_LEFT(rbe
) == poison
613 && (unsigned long)RBE_RIGHT(rbe
) == poison
);