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