GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/gen/tree.c Lines: 0 272 0.0 %
Date: 2017-11-13 Branches: 0 186 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: tree.c,v 1.1 2017/06/19 03:06:26 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, parent);
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);