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