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 445 : static inline struct rb_entry *rb_n2e(const struct rb_type *t, void *node)
53 : {
54 445 : unsigned long addr = (unsigned long)node;
55 :
56 445 : return ((struct rb_entry *)(addr + t->t_offset));
57 : }
58 :
59 2397 : static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
60 : {
61 2397 : unsigned long addr = (unsigned long)rbe;
62 :
63 2397 : 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 98 : static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
74 : {
75 98 : RBE_PARENT(rbe) = parent;
76 98 : RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
77 98 : RBE_COLOR(rbe) = RB_RED;
78 : }
79 :
80 51 : static inline void rbe_set_blackred(struct rb_entry *black,
81 : struct rb_entry *red)
82 : {
83 51 : RBE_COLOR(black) = RB_BLACK;
84 51 : 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 124 : static inline void rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
93 : {
94 124 : if (t->t_augment != NULL)
95 0 : rbe_augment(t, rbe);
96 : }
97 :
98 33 : static inline void rbe_rotate_left(const struct rb_type *t,
99 : struct rbt_tree *rbt, struct rb_entry *rbe)
100 : {
101 33 : struct rb_entry *parent;
102 33 : struct rb_entry *tmp;
103 :
104 33 : tmp = RBE_RIGHT(rbe);
105 33 : RBE_RIGHT(rbe) = RBE_LEFT(tmp);
106 33 : if (RBE_RIGHT(rbe) != NULL)
107 5 : RBE_PARENT(RBE_LEFT(tmp)) = rbe;
108 :
109 33 : parent = RBE_PARENT(rbe);
110 33 : RBE_PARENT(tmp) = parent;
111 33 : if (parent != NULL) {
112 19 : if (rbe == RBE_LEFT(parent))
113 5 : RBE_LEFT(parent) = tmp;
114 : else
115 14 : RBE_RIGHT(parent) = tmp;
116 : } else
117 14 : RBH_ROOT(rbt) = tmp;
118 :
119 33 : RBE_LEFT(tmp) = rbe;
120 33 : RBE_PARENT(rbe) = tmp;
121 :
122 33 : 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 33 : }
130 :
131 8 : static inline void rbe_rotate_right(const struct rb_type *t,
132 : struct rbt_tree *rbt, struct rb_entry *rbe)
133 : {
134 8 : struct rb_entry *parent;
135 8 : struct rb_entry *tmp;
136 :
137 8 : tmp = RBE_LEFT(rbe);
138 8 : RBE_LEFT(rbe) = RBE_RIGHT(tmp);
139 8 : if (RBE_LEFT(rbe) != NULL)
140 5 : RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
141 :
142 8 : parent = RBE_PARENT(rbe);
143 8 : RBE_PARENT(tmp) = parent;
144 8 : if (parent != NULL) {
145 1 : if (rbe == RBE_LEFT(parent))
146 0 : RBE_LEFT(parent) = tmp;
147 : else
148 1 : RBE_RIGHT(parent) = tmp;
149 : } else
150 7 : RBH_ROOT(rbt) = tmp;
151 :
152 8 : RBE_RIGHT(tmp) = rbe;
153 8 : RBE_PARENT(rbe) = tmp;
154 :
155 8 : 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 8 : }
163 :
164 98 : static inline void rbe_insert_color(const struct rb_type *t,
165 : struct rbt_tree *rbt, struct rb_entry *rbe)
166 : {
167 98 : struct rb_entry *parent, *gparent, *tmp;
168 :
169 98 : while ((parent = RBE_PARENT(rbe)) != NULL
170 147 : && RBE_COLOR(parent) == RB_RED) {
171 49 : gparent = RBE_PARENT(parent);
172 :
173 49 : if (parent == RBE_LEFT(gparent)) {
174 8 : tmp = RBE_RIGHT(gparent);
175 8 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
176 6 : RBE_COLOR(tmp) = RB_BLACK;
177 6 : rbe_set_blackred(parent, gparent);
178 6 : rbe = gparent;
179 6 : continue;
180 : }
181 :
182 2 : if (RBE_RIGHT(parent) == rbe) {
183 2 : rbe_rotate_left(t, rbt, parent);
184 2 : tmp = parent;
185 2 : parent = rbe;
186 2 : rbe = tmp;
187 : }
188 :
189 2 : rbe_set_blackred(parent, gparent);
190 2 : rbe_rotate_right(t, rbt, gparent);
191 : } else {
192 41 : tmp = RBE_LEFT(gparent);
193 41 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
194 16 : RBE_COLOR(tmp) = RB_BLACK;
195 16 : rbe_set_blackred(parent, gparent);
196 16 : rbe = gparent;
197 16 : continue;
198 : }
199 :
200 25 : if (RBE_LEFT(parent) == rbe) {
201 1 : rbe_rotate_right(t, rbt, parent);
202 1 : tmp = parent;
203 1 : parent = rbe;
204 1 : rbe = tmp;
205 : }
206 :
207 25 : rbe_set_blackred(parent, gparent);
208 25 : rbe_rotate_left(t, rbt, gparent);
209 : }
210 : }
211 :
212 98 : RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
213 98 : }
214 :
215 107 : 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 107 : struct rb_entry *tmp;
221 :
222 164 : while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
223 146 : && rbe != RBH_ROOT(rbt) && parent) {
224 35 : if (RBE_LEFT(parent) == rbe) {
225 15 : tmp = RBE_RIGHT(parent);
226 15 : if (RBE_COLOR(tmp) == RB_RED) {
227 0 : rbe_set_blackred(tmp, parent);
228 0 : rbe_rotate_left(t, rbt, parent);
229 0 : tmp = RBE_RIGHT(parent);
230 : }
231 15 : if ((RBE_LEFT(tmp) == NULL
232 0 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
233 15 : && (RBE_RIGHT(tmp) == NULL
234 6 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
235 9 : RBE_COLOR(tmp) = RB_RED;
236 9 : rbe = parent;
237 9 : parent = RBE_PARENT(rbe);
238 : } else {
239 6 : if (RBE_RIGHT(tmp) == NULL
240 6 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
241 0 : struct rb_entry *oleft;
242 :
243 0 : oleft = RBE_LEFT(tmp);
244 0 : if (oleft != NULL)
245 0 : RBE_COLOR(oleft) = RB_BLACK;
246 :
247 0 : RBE_COLOR(tmp) = RB_RED;
248 0 : rbe_rotate_right(t, rbt, tmp);
249 0 : tmp = RBE_RIGHT(parent);
250 : }
251 :
252 6 : RBE_COLOR(tmp) = RBE_COLOR(parent);
253 6 : RBE_COLOR(parent) = RB_BLACK;
254 6 : if (RBE_RIGHT(tmp))
255 6 : RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
256 :
257 6 : rbe_rotate_left(t, rbt, parent);
258 6 : rbe = RBH_ROOT(rbt);
259 6 : break;
260 : }
261 : } else {
262 20 : tmp = RBE_LEFT(parent);
263 20 : 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 20 : if ((RBE_LEFT(tmp) == NULL
270 3 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
271 17 : && (RBE_RIGHT(tmp) == NULL
272 0 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
273 17 : RBE_COLOR(tmp) = RB_RED;
274 17 : rbe = parent;
275 17 : parent = RBE_PARENT(rbe);
276 : } else {
277 3 : if (RBE_LEFT(tmp) == NULL
278 3 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
279 0 : struct rb_entry *oright;
280 :
281 0 : oright = RBE_RIGHT(tmp);
282 0 : if (oright != NULL)
283 0 : RBE_COLOR(oright) = RB_BLACK;
284 :
285 0 : RBE_COLOR(tmp) = RB_RED;
286 0 : rbe_rotate_left(t, rbt, tmp);
287 0 : tmp = RBE_LEFT(parent);
288 : }
289 :
290 3 : RBE_COLOR(tmp) = RBE_COLOR(parent);
291 3 : RBE_COLOR(parent) = RB_BLACK;
292 3 : if (RBE_LEFT(tmp) != NULL)
293 3 : RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
294 :
295 3 : rbe_rotate_right(t, rbt, parent);
296 3 : rbe = RBH_ROOT(rbt);
297 3 : break;
298 : }
299 : }
300 : }
301 :
302 107 : if (rbe != NULL)
303 66 : RBE_COLOR(rbe) = RB_BLACK;
304 107 : }
305 :
306 : static inline struct rb_entry *
307 114 : rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
308 : {
309 114 : struct rb_entry *child, *parent, *old = rbe;
310 114 : unsigned int color;
311 :
312 114 : if (RBE_LEFT(rbe) == NULL)
313 50 : child = RBE_RIGHT(rbe);
314 64 : 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 72 : while ((tmp = RBE_LEFT(rbe)) != NULL)
321 : rbe = tmp;
322 :
323 51 : child = RBE_RIGHT(rbe);
324 51 : parent = RBE_PARENT(rbe);
325 51 : color = RBE_COLOR(rbe);
326 51 : if (child != NULL)
327 16 : RBE_PARENT(child) = parent;
328 51 : if (parent != NULL) {
329 51 : if (RBE_LEFT(parent) == rbe)
330 21 : RBE_LEFT(parent) = child;
331 : else
332 30 : RBE_RIGHT(parent) = child;
333 :
334 51 : rbe_if_augment(t, parent);
335 : } else
336 0 : RBH_ROOT(rbt) = child;
337 51 : if (RBE_PARENT(rbe) == old)
338 30 : parent = rbe;
339 51 : *rbe = *old;
340 :
341 51 : tmp = RBE_PARENT(old);
342 51 : 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 46 : RBH_ROOT(rbt) = rbe;
351 :
352 51 : RBE_PARENT(RBE_LEFT(old)) = rbe;
353 51 : if (RBE_RIGHT(old))
354 34 : RBE_PARENT(RBE_RIGHT(old)) = rbe;
355 :
356 51 : 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 51 : goto color;
365 : }
366 :
367 63 : parent = RBE_PARENT(rbe);
368 63 : color = RBE_COLOR(rbe);
369 :
370 63 : if (child != NULL)
371 15 : RBE_PARENT(child) = parent;
372 63 : if (parent != NULL) {
373 9 : if (RBE_LEFT(parent) == rbe)
374 5 : RBE_LEFT(parent) = child;
375 : else
376 4 : RBE_RIGHT(parent) = child;
377 :
378 9 : rbe_if_augment(t, parent);
379 : } else
380 54 : RBH_ROOT(rbt) = child;
381 114 : color:
382 114 : if (color == RB_BLACK)
383 107 : rbe_remove_color(t, rbt, parent, child);
384 :
385 114 : return (old);
386 : }
387 :
388 114 : void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
389 : {
390 114 : struct rb_entry *rbe = rb_n2e(t, elm);
391 114 : struct rb_entry *old;
392 :
393 114 : old = rbe_remove(t, rbt, rbe);
394 :
395 114 : return (old == NULL ? NULL : rb_e2n(t, old));
396 : }
397 :
398 98 : void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
399 : {
400 98 : struct rb_entry *rbe = rb_n2e(t, elm);
401 98 : struct rb_entry *tmp;
402 98 : struct rb_entry *parent = NULL;
403 98 : void *node;
404 98 : int comp = 0;
405 :
406 98 : tmp = RBH_ROOT(rbt);
407 241 : while (tmp != NULL) {
408 143 : parent = tmp;
409 :
410 143 : node = rb_e2n(t, tmp);
411 143 : comp = (*t->t_compare)(elm, node);
412 143 : if (comp < 0)
413 20 : tmp = RBE_LEFT(tmp);
414 123 : else if (comp > 0)
415 123 : tmp = RBE_RIGHT(tmp);
416 : else
417 0 : return (node);
418 : }
419 :
420 98 : rbe_set(rbe, parent);
421 :
422 98 : if (parent != NULL) {
423 59 : if (comp < 0)
424 4 : RBE_LEFT(parent) = rbe;
425 : else
426 55 : RBE_RIGHT(parent) = rbe;
427 :
428 59 : rbe_if_augment(t, parent);
429 : } else
430 39 : RBH_ROOT(rbt) = rbe;
431 :
432 98 : rbe_insert_color(t, rbt, rbe);
433 :
434 98 : return NULL;
435 : }
436 :
437 : /* Finds the node with the same key as elm */
438 1135 : void *_rb_find(const struct rb_type *t, const struct rbt_tree *rbt,
439 : const void *key)
440 : {
441 1135 : struct rb_entry *tmp = RBH_ROOT(rbt);
442 1135 : void *node;
443 1135 : int comp;
444 :
445 1655 : while (tmp != NULL) {
446 1593 : node = rb_e2n(t, tmp);
447 1593 : comp = (*t->t_compare)(key, node);
448 1593 : if (comp < 0)
449 179 : tmp = RBE_LEFT(tmp);
450 1414 : else if (comp > 0)
451 341 : tmp = RBE_RIGHT(tmp);
452 : else
453 1073 : 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 233 : void *_rb_next(const struct rb_type *t, void *elm)
484 : {
485 233 : struct rb_entry *rbe = rb_n2e(t, elm);
486 :
487 233 : if (RBE_RIGHT(rbe) != NULL) {
488 : rbe = RBE_RIGHT(rbe);
489 67 : while (RBE_LEFT(rbe) != NULL)
490 : rbe = RBE_LEFT(rbe);
491 : } else {
492 180 : if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
493 : rbe = RBE_PARENT(rbe);
494 : else {
495 211 : while (RBE_PARENT(rbe)
496 211 : && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
497 : rbe = RBE_PARENT(rbe);
498 : rbe = RBE_PARENT(rbe);
499 : }
500 : }
501 :
502 233 : 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 78 : void *_rb_root(const struct rb_type *t, const struct rbt_tree *rbt)
528 : {
529 78 : struct rb_entry *rbe = RBH_ROOT(rbt);
530 :
531 78 : return (rbe == NULL ? rbe : rb_e2n(t, rbe));
532 : }
533 :
534 472 : void *_rb_min(const struct rb_type *t, const struct rbt_tree *rbt)
535 : {
536 472 : struct rb_entry *rbe = RBH_ROOT(rbt);
537 472 : struct rb_entry *parent = NULL;
538 :
539 874 : while (rbe != NULL) {
540 402 : parent = rbe;
541 402 : rbe = RBE_LEFT(rbe);
542 : }
543 :
544 472 : 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 : }
|
