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