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