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