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