]>
git.proxmox.com Git - mirror_frr.git/blob - lib/typerb.c
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.
49 #define rb_entry typed_rb_entry
50 #define rbt_tree typed_rb_root
52 #define RBE_LEFT(_rbe) (_rbe)->rbt_left
53 #define RBE_RIGHT(_rbe) (_rbe)->rbt_right
54 #define RBE_PARENT(_rbe) (_rbe)->rbt_parent
55 #define RBE_COLOR(_rbe) (_rbe)->rbt_color
57 #define RBH_ROOT(_rbt) (_rbt)->rbt_root
59 static inline void rbe_set(struct rb_entry
*rbe
, struct rb_entry
*parent
)
61 RBE_PARENT(rbe
) = parent
;
62 RBE_LEFT(rbe
) = RBE_RIGHT(rbe
) = NULL
;
63 RBE_COLOR(rbe
) = RB_RED
;
66 static inline void rbe_set_blackred(struct rb_entry
*black
,
69 RBE_COLOR(black
) = RB_BLACK
;
70 RBE_COLOR(red
) = RB_RED
;
73 static inline void rbe_rotate_left(struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
75 struct rb_entry
*parent
;
79 RBE_RIGHT(rbe
) = RBE_LEFT(tmp
);
80 if (RBE_RIGHT(rbe
) != NULL
)
81 RBE_PARENT(RBE_LEFT(tmp
)) = rbe
;
83 parent
= RBE_PARENT(rbe
);
84 RBE_PARENT(tmp
) = parent
;
86 if (rbe
== RBE_LEFT(parent
))
87 RBE_LEFT(parent
) = tmp
;
89 RBE_RIGHT(parent
) = tmp
;
94 RBE_PARENT(rbe
) = tmp
;
97 static inline void rbe_rotate_right(struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
99 struct rb_entry
*parent
;
100 struct rb_entry
*tmp
;
103 RBE_LEFT(rbe
) = RBE_RIGHT(tmp
);
104 if (RBE_LEFT(rbe
) != NULL
)
105 RBE_PARENT(RBE_RIGHT(tmp
)) = rbe
;
107 parent
= RBE_PARENT(rbe
);
108 RBE_PARENT(tmp
) = parent
;
109 if (parent
!= NULL
) {
110 if (rbe
== RBE_LEFT(parent
))
111 RBE_LEFT(parent
) = tmp
;
113 RBE_RIGHT(parent
) = tmp
;
117 RBE_RIGHT(tmp
) = rbe
;
118 RBE_PARENT(rbe
) = tmp
;
121 static inline void rbe_insert_color(struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
123 struct rb_entry
*parent
, *gparent
, *tmp
;
127 while ((parent
= RBE_PARENT(rbe
)) != NULL
128 && RBE_COLOR(parent
) == RB_RED
) {
129 gparent
= RBE_PARENT(parent
);
131 if (parent
== RBE_LEFT(gparent
)) {
132 tmp
= RBE_RIGHT(gparent
);
133 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
134 RBE_COLOR(tmp
) = RB_BLACK
;
135 rbe_set_blackred(parent
, gparent
);
140 if (RBE_RIGHT(parent
) == rbe
) {
141 rbe_rotate_left(rbt
, parent
);
147 rbe_set_blackred(parent
, gparent
);
148 rbe_rotate_right(rbt
, gparent
);
150 tmp
= RBE_LEFT(gparent
);
151 if (tmp
!= NULL
&& RBE_COLOR(tmp
) == RB_RED
) {
152 RBE_COLOR(tmp
) = RB_BLACK
;
153 rbe_set_blackred(parent
, gparent
);
158 if (RBE_LEFT(parent
) == rbe
) {
159 rbe_rotate_right(rbt
, parent
);
165 rbe_set_blackred(parent
, gparent
);
166 rbe_rotate_left(rbt
, gparent
);
170 RBE_COLOR(RBH_ROOT(rbt
)) = RB_BLACK
;
173 static inline void rbe_remove_color(struct rbt_tree
*rbt
,
174 struct rb_entry
*parent
,
175 struct rb_entry
*rbe
)
177 struct rb_entry
*tmp
;
179 while ((rbe
== NULL
|| RBE_COLOR(rbe
) == RB_BLACK
)
180 && rbe
!= RBH_ROOT(rbt
) && parent
) {
181 if (RBE_LEFT(parent
) == rbe
) {
182 tmp
= RBE_RIGHT(parent
);
183 if (RBE_COLOR(tmp
) == RB_RED
) {
184 rbe_set_blackred(tmp
, parent
);
185 rbe_rotate_left(rbt
, parent
);
186 tmp
= RBE_RIGHT(parent
);
188 if ((RBE_LEFT(tmp
) == NULL
189 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
)
190 && (RBE_RIGHT(tmp
) == NULL
191 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
192 RBE_COLOR(tmp
) = RB_RED
;
194 parent
= RBE_PARENT(rbe
);
196 if (RBE_RIGHT(tmp
) == NULL
197 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
) {
198 struct rb_entry
*oleft
;
200 oleft
= RBE_LEFT(tmp
);
202 RBE_COLOR(oleft
) = RB_BLACK
;
204 RBE_COLOR(tmp
) = RB_RED
;
205 rbe_rotate_right(rbt
, tmp
);
206 tmp
= RBE_RIGHT(parent
);
209 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
210 RBE_COLOR(parent
) = RB_BLACK
;
212 RBE_COLOR(RBE_RIGHT(tmp
)) = RB_BLACK
;
214 rbe_rotate_left(rbt
, parent
);
219 tmp
= RBE_LEFT(parent
);
220 if (RBE_COLOR(tmp
) == RB_RED
) {
221 rbe_set_blackred(tmp
, parent
);
222 rbe_rotate_right(rbt
, parent
);
223 tmp
= RBE_LEFT(parent
);
226 if ((RBE_LEFT(tmp
) == NULL
227 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
)
228 && (RBE_RIGHT(tmp
) == NULL
229 || RBE_COLOR(RBE_RIGHT(tmp
)) == RB_BLACK
)) {
230 RBE_COLOR(tmp
) = RB_RED
;
232 parent
= RBE_PARENT(rbe
);
234 if (RBE_LEFT(tmp
) == NULL
235 || RBE_COLOR(RBE_LEFT(tmp
)) == RB_BLACK
) {
236 struct rb_entry
*oright
;
238 oright
= RBE_RIGHT(tmp
);
240 RBE_COLOR(oright
) = RB_BLACK
;
242 RBE_COLOR(tmp
) = RB_RED
;
243 rbe_rotate_left(rbt
, tmp
);
244 tmp
= RBE_LEFT(parent
);
247 RBE_COLOR(tmp
) = RBE_COLOR(parent
);
248 RBE_COLOR(parent
) = RB_BLACK
;
249 if (RBE_LEFT(tmp
) != NULL
)
250 RBE_COLOR(RBE_LEFT(tmp
)) = RB_BLACK
;
252 rbe_rotate_right(rbt
, parent
);
260 RBE_COLOR(rbe
) = RB_BLACK
;
263 static inline struct rb_entry
*
264 rbe_remove(struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
266 struct rb_entry
*child
, *parent
, *old
= rbe
;
269 if (RBE_LEFT(rbe
) == NULL
)
270 child
= RBE_RIGHT(rbe
);
271 else if (RBE_RIGHT(rbe
) == NULL
)
272 child
= RBE_LEFT(rbe
);
274 struct rb_entry
*tmp
;
276 rbe
= RBE_RIGHT(rbe
);
277 while ((tmp
= RBE_LEFT(rbe
)) != NULL
)
280 child
= RBE_RIGHT(rbe
);
281 parent
= RBE_PARENT(rbe
);
282 color
= RBE_COLOR(rbe
);
284 RBE_PARENT(child
) = parent
;
285 if (parent
!= NULL
) {
286 if (RBE_LEFT(parent
) == rbe
)
287 RBE_LEFT(parent
) = child
;
289 RBE_RIGHT(parent
) = child
;
291 RBH_ROOT(rbt
) = child
;
292 if (RBE_PARENT(rbe
) == old
)
296 tmp
= RBE_PARENT(old
);
298 if (RBE_LEFT(tmp
) == old
)
301 RBE_RIGHT(tmp
) = rbe
;
305 RBE_PARENT(RBE_LEFT(old
)) = rbe
;
307 RBE_PARENT(RBE_RIGHT(old
)) = rbe
;
312 parent
= RBE_PARENT(rbe
);
313 color
= RBE_COLOR(rbe
);
316 RBE_PARENT(child
) = parent
;
317 if (parent
!= NULL
) {
318 if (RBE_LEFT(parent
) == rbe
)
319 RBE_LEFT(parent
) = child
;
321 RBE_RIGHT(parent
) = child
;
323 RBH_ROOT(rbt
) = child
;
325 if (color
== RB_BLACK
)
326 rbe_remove_color(rbt
, parent
, child
);
332 void typed_rb_remove(struct rbt_tree
*rbt
, struct rb_entry
*rbe
)
334 rbe_remove(rbt
, rbe
);
337 struct typed_rb_entry
*typed_rb_insert(struct rbt_tree
*rbt
,
338 struct rb_entry
*rbe
, int (*cmpfn
)(
339 const struct typed_rb_entry
*a
,
340 const struct typed_rb_entry
*b
))
342 struct rb_entry
*tmp
;
343 struct rb_entry
*parent
= NULL
;
347 while (tmp
!= NULL
) {
350 comp
= cmpfn(rbe
, tmp
);
354 tmp
= RBE_RIGHT(tmp
);
359 rbe_set(rbe
, parent
);
361 if (parent
!= NULL
) {
363 RBE_LEFT(parent
) = rbe
;
365 RBE_RIGHT(parent
) = rbe
;
369 rbe_insert_color(rbt
, rbe
);
374 /* Finds the node with the same key as elm */
375 struct rb_entry
*typed_rb_find(struct rbt_tree
*rbt
, const struct rb_entry
*key
,
377 const struct typed_rb_entry
*a
,
378 const struct typed_rb_entry
*b
))
380 struct rb_entry
*tmp
= RBH_ROOT(rbt
);
383 while (tmp
!= NULL
) {
384 comp
= cmpfn(key
, tmp
);
388 tmp
= RBE_RIGHT(tmp
);
396 struct rb_entry
*typed_rb_find_gteq(struct rbt_tree
*rbt
,
397 const struct rb_entry
*key
,
399 const struct typed_rb_entry
*a
,
400 const struct typed_rb_entry
*b
))
402 struct rb_entry
*tmp
= RBH_ROOT(rbt
), *best
= NULL
;
405 while (tmp
!= NULL
) {
406 comp
= cmpfn(key
, tmp
);
411 tmp
= RBE_RIGHT(tmp
);
419 struct rb_entry
*typed_rb_find_lt(struct rbt_tree
*rbt
,
420 const struct rb_entry
*key
,
422 const struct typed_rb_entry
*a
,
423 const struct typed_rb_entry
*b
))
425 struct rb_entry
*tmp
= RBH_ROOT(rbt
), *best
= NULL
;
428 while (tmp
!= NULL
) {
429 comp
= cmpfn(key
, tmp
);
434 tmp
= RBE_RIGHT(tmp
);
441 struct rb_entry
*typed_rb_next(struct rb_entry
*rbe
)
443 if (RBE_RIGHT(rbe
) != NULL
) {
444 rbe
= RBE_RIGHT(rbe
);
445 while (RBE_LEFT(rbe
) != NULL
)
448 if (RBE_PARENT(rbe
) && (rbe
== RBE_LEFT(RBE_PARENT(rbe
))))
449 rbe
= RBE_PARENT(rbe
);
451 while (RBE_PARENT(rbe
)
452 && (rbe
== RBE_RIGHT(RBE_PARENT(rbe
))))
453 rbe
= RBE_PARENT(rbe
);
454 rbe
= RBE_PARENT(rbe
);
461 struct rb_entry
*typed_rb_min(struct rbt_tree
*rbt
)
463 struct rb_entry
*rbe
= RBH_ROOT(rbt
);
464 struct rb_entry
*parent
= NULL
;
466 while (rbe
!= NULL
) {