Line data Source code
1 : /* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
2 :
3 : /*
4 : * Copyright 2002 Niels Provos <provos@citi.umich.edu>
5 : * All rights reserved.
6 : *
7 : * Redistribution and use in source and binary forms, with or without
8 : * modification, are permitted provided that the following conditions
9 : * are met:
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.
15 : *
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.
26 : */
27 :
28 : /*
29 : * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
30 : *
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.
34 : *
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.
42 : */
43 :
44 : #ifdef HAVE_CONFIG_H
45 : #include "config.h"
46 : #endif
47 :
48 : #include <stdlib.h>
49 :
50 : #include <lib/openbsd-tree.h>
51 :
52 22777 : static inline struct rb_entry *rb_n2e(const struct rb_type *t, void *node)
53 : {
54 22777 : unsigned long addr = (unsigned long)node;
55 :
56 22777 : return ((struct rb_entry *)(addr + t->t_offset));
57 : }
58 :
59 101808 : static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
60 : {
61 101808 : unsigned long addr = (unsigned long)rbe;
62 :
63 101808 : return ((void *)(addr - t->t_offset));
64 : }
65 :
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
70 :
71 : #define RBH_ROOT(_rbt) (_rbt)->rbt_root
72 :
73 4224 : static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
74 : {
75 4224 : RBE_PARENT(rbe) = parent;
76 4224 : RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
77 4224 : RBE_COLOR(rbe) = RB_RED;
78 : }
79 :
80 1269 : static inline void rbe_set_blackred(struct rb_entry *black,
81 : struct rb_entry *red)
82 : {
83 1269 : RBE_COLOR(black) = RB_BLACK;
84 1269 : RBE_COLOR(red) = RB_RED;
85 : }
86 :
87 0 : static inline void rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
88 : {
89 0 : (*t->t_augment)(rb_e2n(t, rbe));
90 0 : }
91 :
92 4684 : static inline void rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
93 : {
94 4684 : if (t->t_augment != NULL)
95 0 : rbe_augment(t, rbe);
96 : }
97 :
98 1024 : static inline void rbe_rotate_left(const struct rb_type *t,
99 : struct rbt_tree *rbt, struct rb_entry *rbe)
100 : {
101 1024 : struct rb_entry *parent;
102 1024 : struct rb_entry *tmp;
103 :
104 1024 : tmp = RBE_RIGHT(rbe);
105 1024 : RBE_RIGHT(rbe) = RBE_LEFT(tmp);
106 1024 : if (RBE_RIGHT(rbe) != NULL)
107 6 : RBE_PARENT(RBE_LEFT(tmp)) = rbe;
108 :
109 1024 : parent = RBE_PARENT(rbe);
110 1024 : RBE_PARENT(tmp) = parent;
111 1024 : if (parent != NULL) {
112 398 : if (rbe == RBE_LEFT(parent))
113 106 : RBE_LEFT(parent) = tmp;
114 : else
115 292 : RBE_RIGHT(parent) = tmp;
116 : } else
117 626 : RBH_ROOT(rbt) = tmp;
118 :
119 1024 : RBE_LEFT(tmp) = rbe;
120 1024 : RBE_PARENT(rbe) = tmp;
121 :
122 1024 : if (t->t_augment != NULL) {
123 0 : rbe_augment(t, rbe);
124 0 : rbe_augment(t, tmp);
125 0 : parent = RBE_PARENT(tmp);
126 0 : if (parent != NULL)
127 0 : rbe_augment(t, parent);
128 : }
129 1024 : }
130 :
131 378 : static inline void rbe_rotate_right(const struct rb_type *t,
132 : struct rbt_tree *rbt, struct rb_entry *rbe)
133 : {
134 378 : struct rb_entry *parent;
135 378 : struct rb_entry *tmp;
136 :
137 378 : tmp = RBE_LEFT(rbe);
138 378 : RBE_LEFT(rbe) = RBE_RIGHT(tmp);
139 378 : if (RBE_LEFT(rbe) != NULL)
140 5 : RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
141 :
142 378 : parent = RBE_PARENT(rbe);
143 378 : RBE_PARENT(tmp) = parent;
144 378 : if (parent != NULL) {
145 212 : if (rbe == RBE_LEFT(parent))
146 26 : RBE_LEFT(parent) = tmp;
147 : else
148 186 : RBE_RIGHT(parent) = tmp;
149 : } else
150 166 : RBH_ROOT(rbt) = tmp;
151 :
152 378 : RBE_RIGHT(tmp) = rbe;
153 378 : RBE_PARENT(rbe) = tmp;
154 :
155 378 : if (t->t_augment != NULL) {
156 0 : rbe_augment(t, rbe);
157 0 : rbe_augment(t, tmp);
158 0 : parent = RBE_PARENT(tmp);
159 0 : if (parent != NULL)
160 0 : rbe_augment(t, parent);
161 : }
162 378 : }
163 :
164 4224 : static inline void rbe_insert_color(const struct rb_type *t,
165 : struct rbt_tree *rbt, struct rb_entry *rbe)
166 : {
167 4224 : struct rb_entry *parent, *gparent, *tmp;
168 :
169 4224 : while ((parent = RBE_PARENT(rbe)) != NULL
170 5490 : && RBE_COLOR(parent) == RB_RED) {
171 1266 : gparent = RBE_PARENT(parent);
172 :
173 1266 : if (parent == RBE_LEFT(gparent)) {
174 207 : tmp = RBE_RIGHT(gparent);
175 207 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
176 147 : RBE_COLOR(tmp) = RB_BLACK;
177 147 : rbe_set_blackred(parent, gparent);
178 147 : rbe = gparent;
179 147 : continue;
180 : }
181 :
182 60 : if (RBE_RIGHT(parent) == rbe) {
183 50 : rbe_rotate_left(t, rbt, parent);
184 50 : tmp = parent;
185 50 : parent = rbe;
186 50 : rbe = tmp;
187 : }
188 :
189 60 : rbe_set_blackred(parent, gparent);
190 60 : rbe_rotate_right(t, rbt, gparent);
191 : } else {
192 1059 : tmp = RBE_LEFT(gparent);
193 1059 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
194 381 : RBE_COLOR(tmp) = RB_BLACK;
195 381 : rbe_set_blackred(parent, gparent);
196 381 : rbe = gparent;
197 381 : continue;
198 : }
199 :
200 678 : if (RBE_LEFT(parent) == rbe) {
201 164 : rbe_rotate_right(t, rbt, parent);
202 164 : tmp = parent;
203 164 : parent = rbe;
204 164 : rbe = tmp;
205 : }
206 :
207 678 : rbe_set_blackred(parent, gparent);
208 678 : rbe_rotate_left(t, rbt, gparent);
209 : }
210 : }
211 :
212 4224 : RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
213 4224 : }
214 :
215 4926 : 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)
219 : {
220 4926 : struct rb_entry *tmp;
221 :
222 7514 : while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
223 6346 : && rbe != RBH_ROOT(rbt) && parent) {
224 1229 : if (RBE_LEFT(parent) == rbe) {
225 575 : tmp = RBE_RIGHT(parent);
226 575 : if (RBE_COLOR(tmp) == RB_RED) {
227 1 : rbe_set_blackred(tmp, parent);
228 1 : rbe_rotate_left(t, rbt, parent);
229 1 : tmp = RBE_RIGHT(parent);
230 : }
231 575 : if ((RBE_LEFT(tmp) == NULL
232 2 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
233 573 : && (RBE_RIGHT(tmp) == NULL
234 240 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
235 333 : RBE_COLOR(tmp) = RB_RED;
236 333 : rbe = parent;
237 333 : parent = RBE_PARENT(rbe);
238 : } else {
239 242 : if (RBE_RIGHT(tmp) == NULL
240 240 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
241 2 : struct rb_entry *oleft;
242 :
243 2 : oleft = RBE_LEFT(tmp);
244 2 : if (oleft != NULL)
245 2 : RBE_COLOR(oleft) = RB_BLACK;
246 :
247 2 : RBE_COLOR(tmp) = RB_RED;
248 2 : rbe_rotate_right(t, rbt, tmp);
249 2 : tmp = RBE_RIGHT(parent);
250 : }
251 :
252 242 : RBE_COLOR(tmp) = RBE_COLOR(parent);
253 242 : RBE_COLOR(parent) = RB_BLACK;
254 242 : if (RBE_RIGHT(tmp))
255 242 : RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
256 :
257 242 : rbe_rotate_left(t, rbt, parent);
258 242 : rbe = RBH_ROOT(rbt);
259 242 : break;
260 : }
261 : } else {
262 654 : tmp = RBE_LEFT(parent);
263 654 : if (RBE_COLOR(tmp) == RB_RED) {
264 2 : rbe_set_blackred(tmp, parent);
265 2 : rbe_rotate_right(t, rbt, parent);
266 2 : tmp = RBE_LEFT(parent);
267 : }
268 :
269 654 : if ((RBE_LEFT(tmp) == NULL
270 97 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
271 557 : && (RBE_RIGHT(tmp) == NULL
272 53 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
273 504 : RBE_COLOR(tmp) = RB_RED;
274 504 : rbe = parent;
275 504 : parent = RBE_PARENT(rbe);
276 : } else {
277 150 : if (RBE_LEFT(tmp) == NULL
278 97 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
279 53 : struct rb_entry *oright;
280 :
281 53 : oright = RBE_RIGHT(tmp);
282 53 : if (oright != NULL)
283 53 : RBE_COLOR(oright) = RB_BLACK;
284 :
285 53 : RBE_COLOR(tmp) = RB_RED;
286 53 : rbe_rotate_left(t, rbt, tmp);
287 53 : tmp = RBE_LEFT(parent);
288 : }
289 :
290 150 : RBE_COLOR(tmp) = RBE_COLOR(parent);
291 150 : RBE_COLOR(parent) = RB_BLACK;
292 150 : if (RBE_LEFT(tmp) != NULL)
293 150 : RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
294 :
295 150 : rbe_rotate_right(t, rbt, parent);
296 150 : rbe = RBH_ROOT(rbt);
297 150 : break;
298 : }
299 : }
300 : }
301 :
302 4926 : if (rbe != NULL)
303 2980 : RBE_COLOR(rbe) = RB_BLACK;
304 4926 : }
305 :
306 : static inline struct rb_entry *
307 5305 : rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
308 : {
309 5305 : struct rb_entry *child, *parent, *old = rbe;
310 5305 : unsigned int color;
311 :
312 5305 : if (RBE_LEFT(rbe) == NULL)
313 2646 : child = RBE_RIGHT(rbe);
314 2659 : else if (RBE_RIGHT(rbe) == NULL)
315 : child = RBE_LEFT(rbe);
316 : else {
317 : struct rb_entry *tmp;
318 :
319 : rbe = RBE_RIGHT(rbe);
320 2812 : while ((tmp = RBE_LEFT(rbe)) != NULL)
321 : rbe = tmp;
322 :
323 1982 : child = RBE_RIGHT(rbe);
324 1982 : parent = RBE_PARENT(rbe);
325 1982 : color = RBE_COLOR(rbe);
326 1982 : if (child != NULL)
327 690 : RBE_PARENT(child) = parent;
328 1982 : if (parent != NULL) {
329 1982 : if (RBE_LEFT(parent) == rbe)
330 778 : RBE_LEFT(parent) = child;
331 : else
332 1204 : RBE_RIGHT(parent) = child;
333 :
334 1982 : rbe_if_augment(t, parent);
335 : } else
336 0 : RBH_ROOT(rbt) = child;
337 1982 : if (RBE_PARENT(rbe) == old)
338 1204 : parent = rbe;
339 1982 : *rbe = *old;
340 :
341 1982 : tmp = RBE_PARENT(old);
342 1982 : if (tmp != NULL) {
343 5 : if (RBE_LEFT(tmp) == old)
344 5 : RBE_LEFT(tmp) = rbe;
345 : else
346 0 : RBE_RIGHT(tmp) = rbe;
347 :
348 5 : rbe_if_augment(t, tmp);
349 : } else
350 1977 : RBH_ROOT(rbt) = rbe;
351 :
352 1982 : RBE_PARENT(RBE_LEFT(old)) = rbe;
353 1982 : if (RBE_RIGHT(old))
354 1224 : RBE_PARENT(RBE_RIGHT(old)) = rbe;
355 :
356 1982 : if (t->t_augment != NULL && parent != NULL) {
357 : tmp = parent;
358 0 : do {
359 0 : rbe_augment(t, tmp);
360 0 : tmp = RBE_PARENT(tmp);
361 0 : } while (tmp != NULL);
362 : }
363 :
364 1982 : goto color;
365 : }
366 :
367 3323 : parent = RBE_PARENT(rbe);
368 3323 : color = RBE_COLOR(rbe);
369 :
370 3323 : if (child != NULL)
371 1061 : RBE_PARENT(child) = parent;
372 3323 : if (parent != NULL) {
373 324 : if (RBE_LEFT(parent) == rbe)
374 189 : RBE_LEFT(parent) = child;
375 : else
376 135 : RBE_RIGHT(parent) = child;
377 :
378 324 : rbe_if_augment(t, parent);
379 : } else
380 2999 : RBH_ROOT(rbt) = child;
381 5305 : color:
382 5305 : if (color == RB_BLACK)
383 4926 : rbe_remove_color(t, rbt, parent, child);
384 :
385 5305 : return (old);
386 : }
387 :
388 5305 : void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
389 : {
390 5305 : struct rb_entry *rbe = rb_n2e(t, elm);
391 5305 : struct rb_entry *old;
392 :
393 5305 : old = rbe_remove(t, rbt, rbe);
394 :
395 5305 : return (old == NULL ? NULL : rb_e2n(t, old));
396 : }
397 :
398 4224 : void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
399 : {
400 4224 : struct rb_entry *rbe = rb_n2e(t, elm);
401 4224 : struct rb_entry *tmp;
402 4224 : struct rb_entry *parent = NULL;
403 4224 : void *node;
404 4224 : int comp = 0;
405 :
406 4224 : tmp = RBH_ROOT(rbt);
407 8483 : while (tmp != NULL) {
408 4259 : parent = tmp;
409 :
410 4259 : node = rb_e2n(t, tmp);
411 4259 : comp = (*t->t_compare)(elm, node);
412 4259 : if (comp < 0)
413 693 : tmp = RBE_LEFT(tmp);
414 3566 : else if (comp > 0)
415 3566 : tmp = RBE_RIGHT(tmp);
416 : else
417 0 : return (node);
418 : }
419 :
420 4224 : rbe_set(rbe, parent);
421 :
422 4224 : if (parent != NULL) {
423 2373 : if (comp < 0)
424 363 : RBE_LEFT(parent) = rbe;
425 : else
426 2010 : RBE_RIGHT(parent) = rbe;
427 :
428 2373 : rbe_if_augment(t, parent);
429 : } else
430 1851 : RBH_ROOT(rbt) = rbe;
431 :
432 4224 : rbe_insert_color(t, rbt, rbe);
433 :
434 4224 : return NULL;
435 : }
436 :
437 : /* Finds the node with the same key as elm */
438 59057 : void *_rb_find(const struct rb_type *t, const struct rbt_tree *rbt,
439 : const void *key)
440 : {
441 59057 : struct rb_entry *tmp = RBH_ROOT(rbt);
442 59057 : void *node;
443 59057 : int comp;
444 :
445 67881 : while (tmp != NULL) {
446 65213 : node = rb_e2n(t, tmp);
447 65213 : comp = (*t->t_compare)(key, node);
448 65213 : if (comp < 0)
449 1510 : tmp = RBE_LEFT(tmp);
450 63703 : else if (comp > 0)
451 7314 : tmp = RBE_RIGHT(tmp);
452 : else
453 56389 : return (node);
454 : }
455 :
456 : return NULL;
457 : }
458 :
459 : /* Finds the first node greater than or equal to the search key */
460 0 : void *_rb_nfind(const struct rb_type *t, const struct rbt_tree *rbt,
461 : const void *key)
462 : {
463 0 : struct rb_entry *tmp = RBH_ROOT(rbt);
464 0 : void *node;
465 0 : void *res = NULL;
466 0 : int comp;
467 :
468 0 : while (tmp != NULL) {
469 0 : node = rb_e2n(t, tmp);
470 0 : comp = (*t->t_compare)(key, node);
471 0 : if (comp < 0) {
472 0 : res = node;
473 0 : tmp = RBE_LEFT(tmp);
474 0 : } else if (comp > 0)
475 0 : tmp = RBE_RIGHT(tmp);
476 : else
477 0 : return (node);
478 : }
479 :
480 : return (res);
481 : }
482 :
483 13248 : void *_rb_next(const struct rb_type *t, void *elm)
484 : {
485 13248 : struct rb_entry *rbe = rb_n2e(t, elm);
486 :
487 13248 : if (RBE_RIGHT(rbe) != NULL) {
488 : rbe = RBE_RIGHT(rbe);
489 3791 : while (RBE_LEFT(rbe) != NULL)
490 : rbe = RBE_LEFT(rbe);
491 : } else {
492 9662 : if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
493 : rbe = RBE_PARENT(rbe);
494 : else {
495 10577 : while (RBE_PARENT(rbe)
496 10577 : && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
497 : rbe = RBE_PARENT(rbe);
498 : rbe = RBE_PARENT(rbe);
499 : }
500 : }
501 :
502 13248 : return (rbe == NULL ? NULL : rb_e2n(t, rbe));
503 : }
504 :
505 0 : void *_rb_prev(const struct rb_type *t, void *elm)
506 : {
507 0 : struct rb_entry *rbe = rb_n2e(t, elm);
508 :
509 0 : if (RBE_LEFT(rbe)) {
510 : rbe = RBE_LEFT(rbe);
511 0 : while (RBE_RIGHT(rbe))
512 : rbe = RBE_RIGHT(rbe);
513 : } else {
514 0 : if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
515 : rbe = RBE_PARENT(rbe);
516 : else {
517 0 : while (RBE_PARENT(rbe)
518 0 : && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
519 : rbe = RBE_PARENT(rbe);
520 : rbe = RBE_PARENT(rbe);
521 : }
522 : }
523 :
524 0 : return (rbe == NULL ? NULL : rb_e2n(t, rbe));
525 : }
526 :
527 3826 : void *_rb_root(const struct rb_type *t, const struct rbt_tree *rbt)
528 : {
529 3826 : struct rb_entry *rbe = RBH_ROOT(rbt);
530 :
531 3826 : return (rbe == NULL ? rbe : rb_e2n(t, rbe));
532 : }
533 :
534 22031 : void *_rb_min(const struct rb_type *t, const struct rbt_tree *rbt)
535 : {
536 22031 : struct rb_entry *rbe = RBH_ROOT(rbt);
537 22031 : struct rb_entry *parent = NULL;
538 :
539 41498 : while (rbe != NULL) {
540 19467 : parent = rbe;
541 19467 : rbe = RBE_LEFT(rbe);
542 : }
543 :
544 22031 : return (parent == NULL ? NULL : rb_e2n(t, parent));
545 : }
546 :
547 0 : void *_rb_max(const struct rb_type *t, const struct rbt_tree *rbt)
548 : {
549 0 : struct rb_entry *rbe = RBH_ROOT(rbt);
550 0 : struct rb_entry *parent = NULL;
551 :
552 0 : while (rbe != NULL) {
553 0 : parent = rbe;
554 0 : rbe = RBE_RIGHT(rbe);
555 : }
556 :
557 0 : return (parent == NULL ? NULL : rb_e2n(t, parent));
558 : }
559 :
560 0 : void *_rb_left(const struct rb_type *t, void *node)
561 : {
562 0 : struct rb_entry *rbe = rb_n2e(t, node);
563 0 : rbe = RBE_LEFT(rbe);
564 0 : return (rbe == NULL ? NULL : rb_e2n(t, rbe));
565 : }
566 :
567 0 : void *_rb_right(const struct rb_type *t, void *node)
568 : {
569 0 : struct rb_entry *rbe = rb_n2e(t, node);
570 0 : rbe = RBE_RIGHT(rbe);
571 0 : return (rbe == NULL ? NULL : rb_e2n(t, rbe));
572 : }
573 :
574 0 : void *_rb_parent(const struct rb_type *t, void *node)
575 : {
576 0 : struct rb_entry *rbe = rb_n2e(t, node);
577 0 : rbe = RBE_PARENT(rbe);
578 0 : return (rbe == NULL ? NULL : rb_e2n(t, rbe));
579 : }
580 :
581 0 : void _rb_set_left(const struct rb_type *t, void *node, void *left)
582 : {
583 0 : struct rb_entry *rbe = rb_n2e(t, node);
584 0 : struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
585 :
586 0 : RBE_LEFT(rbe) = rbl;
587 0 : }
588 :
589 0 : void _rb_set_right(const struct rb_type *t, void *node, void *right)
590 : {
591 0 : struct rb_entry *rbe = rb_n2e(t, node);
592 0 : struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
593 :
594 0 : RBE_RIGHT(rbe) = rbr;
595 0 : }
596 :
597 0 : void _rb_set_parent(const struct rb_type *t, void *node, void *parent)
598 : {
599 0 : struct rb_entry *rbe = rb_n2e(t, node);
600 0 : struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
601 :
602 0 : RBE_PARENT(rbe) = rbp;
603 0 : }
604 :
605 0 : void _rb_poison(const struct rb_type *t, void *node, unsigned long poison)
606 : {
607 0 : struct rb_entry *rbe = rb_n2e(t, node);
608 :
609 0 : RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
610 0 : (struct rb_entry *)poison;
611 0 : }
612 :
613 0 : int _rb_check(const struct rb_type *t, void *node, unsigned long poison)
614 : {
615 0 : struct rb_entry *rbe = rb_n2e(t, node);
616 :
617 0 : return ((unsigned long)RBE_PARENT(rbe) == poison
618 0 : && (unsigned long)RBE_LEFT(rbe) == poison
619 0 : && (unsigned long)RBE_RIGHT(rbe) == poison);
620 : }
|