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