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