]>
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.
50 #include <lib/openbsd-tree.h>
52 static inline struct rb_entry
*rb_n2e(const struct rb_type
*t
, void *node
)
54 unsigned long addr
= (unsigned long)node
;
56 return ((struct rb_entry
*)(addr
+ t
->t_offset
));
59 static inline void *rb_e2n(const struct rb_type
*t
, struct rb_entry
*rbe
)
61 unsigned long addr
= (unsigned long)rbe
;
63 return ((void *)(addr
- t
->t_offset
));
66 #define RBE_LEFT(_rbe) (_rbe)->rbt_left
67 #define RBE_RIGHT(_rbe) (_rbe)->rbt_right
68 #define RBE_PARENT(_rbe) (_rbe)->rbt_parent
69 #define RBE_COLOR(_rbe) (_rbe)->rbt_color
71 #define RBH_ROOT(_rbt) (_rbt)->rbt_root
73 static inline void rbe_set(struct rb_entry
*rbe
, struct rb_entry
*parent
)
75 RBE_PARENT(rbe
) = parent
;
76 RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) = NULL
;
77 RBE_COLOR(rbe
) = RB_RED
;
80 static inline void rbe_set_blackred(struct rb_entry
*black
,
83 RBE_COLOR(black
) = RB_BLACK
;
84 RBE_COLOR(red
) = RB_RED
;
87 static inline void rbe_augment(const struct rb_type
*t
, struct rb_entry
*rbe
)
89 (*t
->t_augment
)(rb_e2n(t
, rbe
));
92 static inline void rbe_if_augment(const struct rb_type
*t
, struct rb_entry
*rbe
)
94 if (t
->t_augment
!= NULL
)
98 static inline void rbe_rotate_left(const struct rb_type
*t
,
99 struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
101 struct rb_entry
*parent
;
102 struct rb_entry
*tmp
;
104 tmp
= RBE_RIGHT(rbe
);
105 RBE_RIGHT(rbe
) = RBE_LEFT(tmp
);
106 if (RBE_RIGHT(rbe
) != NULL
)
107 RBE_PARENT(RBE_LEFT(tmp
)) = rbe
;
109 parent
= RBE_PARENT(rbe
);
110 RBE_PARENT(tmp
) = parent
;
111 if (parent
!= NULL
) {
112 if (rbe
== RBE_LEFT(parent
))
113 RBE_LEFT(parent
) = tmp
;
115 RBE_RIGHT(parent
) = tmp
;
120 RBE_PARENT(rbe
) = tmp
;
122 if (t
->t_augment
!= NULL
) {
125 parent
= RBE_PARENT(tmp
);
127 rbe_augment(t
, parent
);
131 static inline void rbe_rotate_right(const struct rb_type
*t
,
132 struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
134 struct rb_entry
*parent
;
135 struct rb_entry
*tmp
;
138 RBE_LEFT(rbe
) = RBE_RIGHT(tmp
);
139 if (RBE_LEFT(rbe
) != NULL
)
140 RBE_PARENT(RBE_RIGHT(tmp
)) = rbe
;
142 parent
= RBE_PARENT(rbe
);
143 RBE_PARENT(tmp
) = parent
;
144 if (parent
!= NULL
) {
145 if (rbe
== RBE_LEFT(parent
))
146 RBE_LEFT(parent
) = tmp
;
148 RBE_RIGHT(parent
) = tmp
;
152 RBE_RIGHT(tmp
) = rbe
;
153 RBE_PARENT(rbe
) = tmp
;
155 if (t
->t_augment
!= NULL
) {
158 parent
= RBE_PARENT(tmp
);
160 rbe_augment(t
, parent
);
164 static inline void rbe_insert_color(const struct rb_type
*t
,
165 struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
167 struct rb_entry
*parent
, *gparent
, *tmp
;
169 while ((parent
= RBE_PARENT(rbe
)) != NULL
170 && RBE_COLOR(parent
) == RB_RED
) {
171 gparent
= RBE_PARENT(parent
);
173 if (parent
== RBE_LEFT(gparent
)) {
174 tmp
= RBE_RIGHT(gparent
);
175 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
176 RBE_COLOR(tmp
) = RB_BLACK
;
177 rbe_set_blackred(parent
, gparent
);
182 if (RBE_RIGHT(parent
) == rbe
) {
183 rbe_rotate_left(t
, rbt
, parent
);
189 rbe_set_blackred(parent
, gparent
);
190 rbe_rotate_right(t
, rbt
, gparent
);
192 tmp
= RBE_LEFT(gparent
);
193 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
194 RBE_COLOR(tmp
) = RB_BLACK
;
195 rbe_set_blackred(parent
, gparent
);
200 if (RBE_LEFT(parent
) == rbe
) {
201 rbe_rotate_right(t
, rbt
, parent
);
207 rbe_set_blackred(parent
, gparent
);
208 rbe_rotate_left(t
, rbt
, gparent
);
212 RBE_COLOR(RBH_ROOT(rbt
)) = RB_BLACK
;
215 static inline void rbe_remove_color(const struct rb_type
*t
,
216 struct rbt_tree
*rbt
,
217 struct rb_entry
*parent
,
218 struct rb_entry
*rbe
)
220 struct rb_entry
*tmp
;
222 while ((rbe
== NULL
|| RBE_COLOR(rbe
) == RB_BLACK
)
223 && rbe
!= RBH_ROOT(rbt
) && parent
) {
224 if (RBE_LEFT(parent
) == rbe
) {
225 tmp
= RBE_RIGHT(parent
);
226 if (RBE_COLOR(tmp
) == RB_RED
) {
227 rbe_set_blackred(tmp
, parent
);
228 rbe_rotate_left(t
, rbt
, parent
);
229 tmp
= RBE_RIGHT(parent
);
231 if ((RBE_LEFT(tmp
) == NULL
232 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
)
233 && (RBE_RIGHT(tmp
) == NULL
234 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
235 RBE_COLOR(tmp
) = RB_RED
;
237 parent
= RBE_PARENT(rbe
);
239 if (RBE_RIGHT(tmp
) == NULL
240 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
) {
241 struct rb_entry
*oleft
;
243 oleft
= RBE_LEFT(tmp
);
245 RBE_COLOR(oleft
) = RB_BLACK
;
247 RBE_COLOR(tmp
) = RB_RED
;
248 rbe_rotate_right(t
, rbt
, tmp
);
249 tmp
= RBE_RIGHT(parent
);
252 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
253 RBE_COLOR(parent
) = RB_BLACK
;
255 RBE_COLOR(RBE_RIGHT(tmp
)) = RB_BLACK
;
257 rbe_rotate_left(t
, rbt
, parent
);
262 tmp
= RBE_LEFT(parent
);
263 if (RBE_COLOR(tmp
) == RB_RED
) {
264 rbe_set_blackred(tmp
, parent
);
265 rbe_rotate_right(t
, rbt
, parent
);
266 tmp
= RBE_LEFT(parent
);
269 if ((RBE_LEFT(tmp
) == NULL
270 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
)
271 && (RBE_RIGHT(tmp
) == NULL
272 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
273 RBE_COLOR(tmp
) = RB_RED
;
275 parent
= RBE_PARENT(rbe
);
277 if (RBE_LEFT(tmp
) == NULL
278 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) {
279 struct rb_entry
*oright
;
281 oright
= RBE_RIGHT(tmp
);
283 RBE_COLOR(oright
) = RB_BLACK
;
285 RBE_COLOR(tmp
) = RB_RED
;
286 rbe_rotate_left(t
, rbt
, tmp
);
287 tmp
= RBE_LEFT(parent
);
290 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
291 RBE_COLOR(parent
) = RB_BLACK
;
292 if (RBE_LEFT(tmp
) != NULL
)
293 RBE_COLOR(RBE_LEFT(tmp
)) = RB_BLACK
;
295 rbe_rotate_right(t
, rbt
, parent
);
303 RBE_COLOR(rbe
) = RB_BLACK
;
306 static inline struct rb_entry
*
307 rbe_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
309 struct rb_entry
*child
, *parent
, *old
= rbe
;
312 if (RBE_LEFT(rbe
) == NULL
)
313 child
= RBE_RIGHT(rbe
);
314 else if (RBE_RIGHT(rbe
) == NULL
)
315 child
= RBE_LEFT(rbe
);
317 struct rb_entry
*tmp
;
319 rbe
= RBE_RIGHT(rbe
);
320 while ((tmp
= RBE_LEFT(rbe
)) != NULL
)
323 child
= RBE_RIGHT(rbe
);
324 parent
= RBE_PARENT(rbe
);
325 color
= RBE_COLOR(rbe
);
327 RBE_PARENT(child
) = parent
;
328 if (parent
!= NULL
) {
329 if (RBE_LEFT(parent
) == rbe
)
330 RBE_LEFT(parent
) = child
;
332 RBE_RIGHT(parent
) = child
;
334 rbe_if_augment(t
, parent
);
336 RBH_ROOT(rbt
) = child
;
337 if (RBE_PARENT(rbe
) == old
)
341 tmp
= RBE_PARENT(old
);
343 if (RBE_LEFT(tmp
) == old
)
346 RBE_RIGHT(tmp
) = rbe
;
348 rbe_if_augment(t
, tmp
);
352 RBE_PARENT(RBE_LEFT(old
)) = rbe
;
354 RBE_PARENT(RBE_RIGHT(old
)) = rbe
;
356 if (t
->t_augment
!= NULL
&& parent
!= NULL
) {
360 tmp
= RBE_PARENT(tmp
);
361 } while (tmp
!= NULL
);
367 parent
= RBE_PARENT(rbe
);
368 color
= RBE_COLOR(rbe
);
371 RBE_PARENT(child
) = parent
;
372 if (parent
!= NULL
) {
373 if (RBE_LEFT(parent
) == rbe
)
374 RBE_LEFT(parent
) = child
;
376 RBE_RIGHT(parent
) = child
;
378 rbe_if_augment(t
, parent
);
380 RBH_ROOT(rbt
) = child
;
382 if (color
== RB_BLACK
)
383 rbe_remove_color(t
, rbt
, parent
, child
);
388 void *_rb_remove(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
390 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
391 struct rb_entry
*old
;
393 old
= rbe_remove(t
, rbt
, rbe
);
395 return (old
== NULL
? NULL
: rb_e2n(t
, old
));
398 void *_rb_insert(const struct rb_type
*t
, struct rbt_tree
*rbt
, void *elm
)
400 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
401 struct rb_entry
*tmp
;
402 struct rb_entry
*parent
= NULL
;
407 while (tmp
!= NULL
) {
410 node
= rb_e2n(t
, tmp
);
411 comp
= (*t
->t_compare
)(elm
, node
);
415 tmp
= RBE_RIGHT(tmp
);
420 rbe_set(rbe
, parent
);
422 if (parent
!= NULL
) {
424 RBE_LEFT(parent
) = rbe
;
426 RBE_RIGHT(parent
) = rbe
;
428 rbe_if_augment(t
, parent
);
432 rbe_insert_color(t
, rbt
, rbe
);
437 /* Finds the node with the same key as elm */
438 void *_rb_find(const struct rb_type
*t
, const struct rbt_tree
*rbt
,
441 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
445 while (tmp
!= NULL
) {
446 node
= rb_e2n(t
, tmp
);
447 comp
= (*t
->t_compare
)(key
, node
);
451 tmp
= RBE_RIGHT(tmp
);
459 /* Finds the first node greater than or equal to the search key */
460 void *_rb_nfind(const struct rb_type
*t
, const struct rbt_tree
*rbt
,
463 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
468 while (tmp
!= NULL
) {
469 node
= rb_e2n(t
, tmp
);
470 comp
= (*t
->t_compare
)(key
, node
);
475 tmp
= RBE_RIGHT(tmp
);
483 void *_rb_next(const struct rb_type
*t
, void *elm
)
485 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
487 if (RBE_RIGHT(rbe
) != NULL
) {
488 rbe
= RBE_RIGHT(rbe
);
489 while (RBE_LEFT(rbe
) != NULL
)
492 if (RBE_PARENT(rbe
) && (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
493 rbe
= RBE_PARENT(rbe
);
495 while (RBE_PARENT(rbe
)
496 && (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
497 rbe
= RBE_PARENT(rbe
);
498 rbe
= RBE_PARENT(rbe
);
502 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
505 void *_rb_prev(const struct rb_type
*t
, void *elm
)
507 struct rb_entry
*rbe
= rb_n2e(t
, elm
);
511 while (RBE_RIGHT(rbe
))
512 rbe
= RBE_RIGHT(rbe
);
514 if (RBE_PARENT(rbe
) && (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
515 rbe
= RBE_PARENT(rbe
);
517 while (RBE_PARENT(rbe
)
518 && (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
519 rbe
= RBE_PARENT(rbe
);
520 rbe
= RBE_PARENT(rbe
);
524 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
527 void *_rb_root(const struct rb_type
*t
, const struct rbt_tree
*rbt
)
529 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
531 return (rbe
== NULL
? rbe
: rb_e2n(t
, rbe
));
534 void *_rb_min(const struct rb_type
*t
, const struct rbt_tree
*rbt
)
536 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
537 struct rb_entry
*parent
= NULL
;
539 while (rbe
!= NULL
) {
544 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
547 void *_rb_max(const struct rb_type
*t
, const struct rbt_tree
*rbt
)
549 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
550 struct rb_entry
*parent
= NULL
;
552 while (rbe
!= NULL
) {
554 rbe
= RBE_RIGHT(rbe
);
557 return (parent
== NULL
? NULL
: rb_e2n(t
, parent
));
560 void *_rb_left(const struct rb_type
*t
, void *node
)
562 struct rb_entry
*rbe
= rb_n2e(t
, node
);
564 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
567 void *_rb_right(const struct rb_type
*t
, void *node
)
569 struct rb_entry
*rbe
= rb_n2e(t
, node
);
570 rbe
= RBE_RIGHT(rbe
);
571 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
574 void *_rb_parent(const struct rb_type
*t
, void *node
)
576 struct rb_entry
*rbe
= rb_n2e(t
, node
);
577 rbe
= RBE_PARENT(rbe
);
578 return (rbe
== NULL
? NULL
: rb_e2n(t
, rbe
));
581 void _rb_set_left(const struct rb_type
*t
, void *node
, void *left
)
583 struct rb_entry
*rbe
= rb_n2e(t
, node
);
584 struct rb_entry
*rbl
= (left
== NULL
) ? NULL
: rb_n2e(t
, left
);
589 void _rb_set_right(const struct rb_type
*t
, void *node
, void *right
)
591 struct rb_entry
*rbe
= rb_n2e(t
, node
);
592 struct rb_entry
*rbr
= (right
== NULL
) ? NULL
: rb_n2e(t
, right
);
594 RBE_RIGHT(rbe
) = rbr
;
597 void _rb_set_parent(const struct rb_type
*t
, void *node
, void *parent
)
599 struct rb_entry
*rbe
= rb_n2e(t
, node
);
600 struct rb_entry
*rbp
= (parent
== NULL
) ? NULL
: rb_n2e(t
, parent
);
602 RBE_PARENT(rbe
) = rbp
;
605 void _rb_poison(const struct rb_type
*t
, void *node
, unsigned long poison
)
607 struct rb_entry
*rbe
= rb_n2e(t
, node
);
609 RBE_PARENT(rbe
) = RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) =
610 (struct rb_entry
*)poison
;
613 int _rb_check(const struct rb_type
*t
, void *node
, unsigned long poison
)
615 struct rb_entry
*rbe
= rb_n2e(t
, node
);
617 return ((unsigned long)RBE_PARENT(rbe
) == poison
618 && (unsigned long)RBE_LEFT(rbe
) == poison
619 && (unsigned long)RBE_RIGHT(rbe
) == poison
);