xref: /openbsd/lib/libc/gen/tree.c (revision 76d0caae) 
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 *
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 *
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
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
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
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
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
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
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
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
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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
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
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
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
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
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