]>
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 while ((rbe
== NULL
|| RBE_COLOR(rbe
) == RB_BLACK
) &&
226 rbe
!= RBH_ROOT(rbt
) && parent
) {
227 if (RBE_LEFT(parent
) == rbe
) {
228 tmp
= RBE_RIGHT(parent
);
229 if (RBE_COLOR(tmp
) == RB_RED
) {
230 rbe_set_blackred(tmp
, parent
);
231 rbe_rotate_left(t
, rbt
, parent
);
232 tmp
= RBE_RIGHT(parent
);
234 if ((RBE_LEFT(tmp
) == NULL
||
235 RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) &&
236 (RBE_RIGHT(tmp
) == NULL
||
237 RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
238 RBE_COLOR(tmp
) = RB_RED
;
240 parent
= RBE_PARENT(rbe
);
242 if (RBE_RIGHT(tmp
) == NULL
||
243 RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
) {
244 struct rb_entry
*oleft
;
246 oleft
= RBE_LEFT(tmp
);
248 RBE_COLOR(oleft
) = RB_BLACK
;
250 RBE_COLOR(tmp
) = RB_RED
;
251 rbe_rotate_right(t
, rbt
, tmp
);
252 tmp
= RBE_RIGHT(parent
);
255 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
256 RBE_COLOR(parent
) = RB_BLACK
;
258 RBE_COLOR(RBE_RIGHT(tmp
)) = RB_BLACK
;
260 rbe_rotate_left(t
, rbt
, parent
);
265 tmp
= RBE_LEFT(parent
);
266 if (RBE_COLOR(tmp
) == RB_RED
) {
267 rbe_set_blackred(tmp
, parent
);
268 rbe_rotate_right(t
, rbt
, parent
);
269 tmp
= RBE_LEFT(parent
);
272 if ((RBE_LEFT(tmp
) == NULL
||
273 RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) &&
274 (RBE_RIGHT(tmp
) == NULL
||
275 RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
276 RBE_COLOR(tmp
) = RB_RED
;
278 parent
= RBE_PARENT(rbe
);
280 if (RBE_LEFT(tmp
) == NULL
||
281 RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) {
282 struct rb_entry
*oright
;
284 oright
= RBE_RIGHT(tmp
);
286 RBE_COLOR(oright
) = RB_BLACK
;
288 RBE_COLOR(tmp
) = RB_RED
;
289 rbe_rotate_left(t
, rbt
, tmp
);
290 tmp
= RBE_LEFT(parent
);
293 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
294 RBE_COLOR(parent
) = RB_BLACK
;
295 if (RBE_LEFT(tmp
) != NULL
)
296 RBE_COLOR(RBE_LEFT(tmp
)) = RB_BLACK
;
298 rbe_rotate_right(t
, rbt
, parent
);
306 RBE_COLOR(rbe
) = RB_BLACK
;
309 static inline struct rb_entry
*
310 rbe_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
312 struct rb_entry
*child
, *parent
, *old
= rbe
;
315 if (RBE_LEFT(rbe
) == NULL
)
316 child
= RBE_RIGHT(rbe
);
317 else if (RBE_RIGHT(rbe
) == NULL
)
318 child
= RBE_LEFT(rbe
);
320 struct rb_entry
*tmp
;
322 rbe
= RBE_RIGHT(rbe
);
323 while ((tmp
= RBE_LEFT(rbe
)) != NULL
)
326 child
= RBE_RIGHT(rbe
);
327 parent
= RBE_PARENT(rbe
);
328 color
= RBE_COLOR(rbe
);
330 RBE_PARENT(child
) = parent
;
331 if (parent
!= NULL
) {
332 if (RBE_LEFT(parent
) == rbe
)
333 RBE_LEFT(parent
) = child
;
335 RBE_RIGHT(parent
) = child
;
337 rbe_if_augment(t
, parent
);
339 RBH_ROOT(rbt
) = child
;
340 if (RBE_PARENT(rbe
) == old
)
344 tmp
= RBE_PARENT(old
);
346 if (RBE_LEFT(tmp
) == old
)
349 RBE_RIGHT(tmp
) = rbe
;
351 rbe_if_augment(t
, parent
);
355 RBE_PARENT(RBE_LEFT(old
)) = rbe
;
357 RBE_PARENT(RBE_RIGHT(old
)) = rbe
;
359 if (t
->t_augment
!= NULL
&& parent
!= NULL
) {
363 tmp
= RBE_PARENT(tmp
);
364 } while (tmp
!= NULL
);
370 parent
= RBE_PARENT(rbe
);
371 color
= RBE_COLOR(rbe
);
374 RBE_PARENT(child
) = parent
;
375 if (parent
!= NULL
) {
376 if (RBE_LEFT(parent
) == rbe
)
377 RBE_LEFT(parent
) = child
;
379 RBE_RIGHT(parent
) = child
;
381 rbe_if_augment(t
, parent
);
383 RBH_ROOT(rbt
) = child
;
385 if (color
== RB_BLACK
)
386 rbe_remove_color(t
, rbt
, parent
, child
);
392 _rb_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
394 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
395 struct rb_entry
*old
;
397 old
= rbe_remove(t
, rbt
, rbe
);
399 return (old
== NULL
? NULL
: rb_e2n(t
, old
));
403 _rb_insert(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
405 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
406 struct rb_entry
*tmp
;
407 struct rb_entry
*parent
= NULL
;
412 while (tmp
!= NULL
) {
415 node
= rb_e2n(t
, tmp
);
416 comp
= (*t
->t_compare
)(elm
, node
);
420 tmp
= RBE_RIGHT(tmp
);
425 rbe_set(rbe
, parent
);
427 if (parent
!= NULL
) {
429 RBE_LEFT(parent
) = rbe
;
431 RBE_RIGHT(parent
) = rbe
;
433 rbe_if_augment(t
, parent
);
437 rbe_insert_color(t
, rbt
, rbe
);
442 /* Finds the node with the same key as elm */
444 _rb_find(const struct rb_type
*t
, struct rbt_tree
*rbt
, const void *key
)
446 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
450 while (tmp
!= NULL
) {
451 node
= rb_e2n(t
, tmp
);
452 comp
= (*t
->t_compare
)(key
, node
);
456 tmp
= RBE_RIGHT(tmp
);
464 /* Finds the first node greater than or equal to the search key */
466 _rb_nfind(const struct rb_type
*t
, struct rbt_tree
*rbt
, const void *key
)
468 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
473 while (tmp
!= NULL
) {
474 node
= rb_e2n(t
, tmp
);
475 comp
= (*t
->t_compare
)(key
, node
);
480 tmp
= RBE_RIGHT(tmp
);
489 _rb_next(const struct rb_type
*t
, void *elm
)
491 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
493 if (RBE_RIGHT(rbe
) != NULL
) {
494 rbe
= RBE_RIGHT(rbe
);
495 while (RBE_LEFT(rbe
) != NULL
)
498 if (RBE_PARENT(rbe
) &&
499 (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
500 rbe
= RBE_PARENT(rbe
);
502 while (RBE_PARENT(rbe
) &&
503 (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
504 rbe
= RBE_PARENT(rbe
);
505 rbe
= RBE_PARENT(rbe
);
509 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
513 _rb_prev(const struct rb_type
*t
, void *elm
)
515 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
519 while (RBE_RIGHT(rbe
))
520 rbe
= RBE_RIGHT(rbe
);
522 if (RBE_PARENT(rbe
) &&
523 (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
524 rbe
= RBE_PARENT(rbe
);
526 while (RBE_PARENT(rbe
) &&
527 (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
528 rbe
= RBE_PARENT(rbe
);
529 rbe
= RBE_PARENT(rbe
);
533 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
537 _rb_root(const struct rb_type
*t
, struct rbt_tree
*rbt
)
539 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
541 return (rbe
== NULL
? rbe
: rb_e2n(t
, rbe
));
545 _rb_min(const struct rb_type
*t
, struct rbt_tree
*rbt
)
547 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
548 struct rb_entry
*parent
= NULL
;
550 while (rbe
!= NULL
) {
555 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
559 _rb_max(const struct rb_type
*t
, struct rbt_tree
*rbt
)
561 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
562 struct rb_entry
*parent
= NULL
;
564 while (rbe
!= NULL
) {
566 rbe
= RBE_RIGHT(rbe
);
569 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
573 _rb_left(const struct rb_type
*t
, void *node
)
575 struct rb_entry
*rbe
= rb_n2e(t
, node
);
577 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
581 _rb_right(const struct rb_type
*t
, void *node
)
583 struct rb_entry
*rbe
= rb_n2e(t
, node
);
584 rbe
= RBE_RIGHT(rbe
);
585 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
589 _rb_parent(const struct rb_type
*t
, void *node
)
591 struct rb_entry
*rbe
= rb_n2e(t
, node
);
592 rbe
= RBE_PARENT(rbe
);
593 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
597 _rb_set_left(const struct rb_type
*t
, void *node
, void *left
)
599 struct rb_entry
*rbe
= rb_n2e(t
, node
);
600 struct rb_entry
*rbl
= (left
== NULL
) ? NULL
: rb_n2e(t
, left
);
606 _rb_set_right(const struct rb_type
*t
, void *node
, void *right
)
608 struct rb_entry
*rbe
= rb_n2e(t
, node
);
609 struct rb_entry
*rbr
= (right
== NULL
) ? NULL
: rb_n2e(t
, right
);
611 RBE_RIGHT(rbe
) = rbr
;
615 _rb_set_parent(const struct rb_type
*t
, void *node
, void *parent
)
617 struct rb_entry
*rbe
= rb_n2e(t
, node
);
618 struct rb_entry
*rbp
= (parent
== NULL
) ? NULL
: rb_n2e(t
, parent
);
620 RBE_PARENT(rbe
) = rbp
;
624 _rb_poison(const struct rb_type
*t
, void *node
, unsigned long poison
)
626 struct rb_entry
*rbe
= rb_n2e(t
, node
);
628 RBE_PARENT(rbe
) = RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) =
629 (struct rb_entry
*)poison
;
633 _rb_check(const struct rb_type
*t
, void *node
, unsigned long poison
)
635 struct rb_entry
*rbe
= rb_n2e(t
, node
);
637 return ((unsigned long)RBE_PARENT(rbe
) == poison
&&
638 (unsigned long)RBE_LEFT(rbe
) == poison
&&
639 (unsigned long)RBE_RIGHT(rbe
) == poison
);