Line data Source code
1 : /* RB-tree */
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 : #ifdef HAVE_CONFIG_H
45 : #include "config.h"
46 : #endif
47 :
48 : #include <string.h>
49 : #include "typerb.h"
50 :
51 : #define RB_BLACK 0
52 : #define RB_RED 1
53 :
54 : #define rb_entry typed_rb_entry
55 : #define rbt_tree typed_rb_root
56 :
57 : #define RBE_LEFT(_rbe) (_rbe)->rbt_left
58 : #define RBE_RIGHT(_rbe) (_rbe)->rbt_right
59 : #define RBE_PARENT(_rbe) (_rbe)->rbt_parent
60 : #define RBE_COLOR(_rbe) (_rbe)->rbt_color
61 :
62 : #define RBH_ROOT(_rbt) (_rbt)->rbt_root
63 :
64 321204 : static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
65 : {
66 321204 : RBE_PARENT(rbe) = parent;
67 321204 : RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
68 321204 : RBE_COLOR(rbe) = RB_RED;
69 : }
70 :
71 285465 : static inline void rbe_set_blackred(struct rb_entry *black,
72 : struct rb_entry *red)
73 : {
74 285465 : RBE_COLOR(black) = RB_BLACK;
75 285465 : RBE_COLOR(red) = RB_RED;
76 : }
77 :
78 97306 : static inline void rbe_rotate_left(struct rbt_tree *rbt, struct rb_entry *rbe)
79 : {
80 97306 : struct rb_entry *parent;
81 97306 : struct rb_entry *tmp;
82 :
83 97306 : tmp = RBE_RIGHT(rbe);
84 97306 : RBE_RIGHT(rbe) = RBE_LEFT(tmp);
85 97306 : if (RBE_RIGHT(rbe) != NULL)
86 25294 : RBE_PARENT(RBE_LEFT(tmp)) = rbe;
87 :
88 97306 : parent = RBE_PARENT(rbe);
89 97306 : RBE_PARENT(tmp) = parent;
90 97306 : if (parent != NULL) {
91 96420 : if (rbe == RBE_LEFT(parent))
92 61906 : RBE_LEFT(parent) = tmp;
93 : else
94 34514 : RBE_RIGHT(parent) = tmp;
95 : } else
96 886 : RBH_ROOT(rbt) = tmp;
97 :
98 97306 : RBE_LEFT(tmp) = rbe;
99 97306 : RBE_PARENT(rbe) = tmp;
100 97306 : }
101 :
102 89852 : static inline void rbe_rotate_right(struct rbt_tree *rbt, struct rb_entry *rbe)
103 : {
104 89852 : struct rb_entry *parent;
105 89852 : struct rb_entry *tmp;
106 :
107 89852 : tmp = RBE_LEFT(rbe);
108 89852 : RBE_LEFT(rbe) = RBE_RIGHT(tmp);
109 89852 : if (RBE_LEFT(rbe) != NULL)
110 23581 : RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
111 :
112 89852 : parent = RBE_PARENT(rbe);
113 89852 : RBE_PARENT(tmp) = parent;
114 89852 : if (parent != NULL) {
115 89625 : if (rbe == RBE_LEFT(parent))
116 26895 : RBE_LEFT(parent) = tmp;
117 : else
118 62730 : RBE_RIGHT(parent) = tmp;
119 : } else
120 227 : RBH_ROOT(rbt) = tmp;
121 :
122 89852 : RBE_RIGHT(tmp) = rbe;
123 89852 : RBE_PARENT(rbe) = tmp;
124 89852 : }
125 :
126 321204 : static inline void rbe_insert_color(struct rbt_tree *rbt, struct rb_entry *rbe)
127 : {
128 321204 : struct rb_entry *parent, *gparent, *tmp;
129 :
130 321204 : rbt->count++;
131 :
132 321204 : while ((parent = RBE_PARENT(rbe)) != NULL
133 606667 : && RBE_COLOR(parent) == RB_RED) {
134 285463 : gparent = RBE_PARENT(parent);
135 :
136 285463 : if (parent == RBE_LEFT(gparent)) {
137 135723 : tmp = RBE_RIGHT(gparent);
138 135723 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
139 80889 : RBE_COLOR(tmp) = RB_BLACK;
140 80889 : rbe_set_blackred(parent, gparent);
141 80889 : rbe = gparent;
142 80889 : continue;
143 : }
144 :
145 54834 : if (RBE_RIGHT(parent) == rbe) {
146 30242 : rbe_rotate_left(rbt, parent);
147 30242 : tmp = parent;
148 30242 : parent = rbe;
149 30242 : rbe = tmp;
150 : }
151 :
152 54834 : rbe_set_blackred(parent, gparent);
153 54834 : rbe_rotate_right(rbt, gparent);
154 : } else {
155 149740 : tmp = RBE_LEFT(gparent);
156 149740 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
157 82740 : RBE_COLOR(tmp) = RB_BLACK;
158 82740 : rbe_set_blackred(parent, gparent);
159 82740 : rbe = gparent;
160 82740 : continue;
161 : }
162 :
163 67000 : if (RBE_LEFT(parent) == rbe) {
164 35008 : rbe_rotate_right(rbt, parent);
165 35008 : tmp = parent;
166 35008 : parent = rbe;
167 35008 : rbe = tmp;
168 : }
169 :
170 67000 : rbe_set_blackred(parent, gparent);
171 67000 : rbe_rotate_left(rbt, gparent);
172 : }
173 : }
174 :
175 321204 : RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
176 321204 : }
177 :
178 2145 : static inline void rbe_remove_color(struct rbt_tree *rbt,
179 : struct rb_entry *parent,
180 : struct rb_entry *rbe)
181 : {
182 2145 : struct rb_entry *tmp;
183 :
184 3286 : while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
185 2335 : && rbe != RBH_ROOT(rbt) && parent) {
186 171 : if (RBE_LEFT(parent) == rbe) {
187 104 : tmp = RBE_RIGHT(parent);
188 104 : if (RBE_COLOR(tmp) == RB_RED) {
189 2 : rbe_set_blackred(tmp, parent);
190 2 : rbe_rotate_left(rbt, parent);
191 2 : tmp = RBE_RIGHT(parent);
192 : }
193 104 : if ((RBE_LEFT(tmp) == NULL
194 17 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
195 89 : && (RBE_RIGHT(tmp) == NULL
196 46 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
197 43 : RBE_COLOR(tmp) = RB_RED;
198 43 : rbe = parent;
199 43 : parent = RBE_PARENT(rbe);
200 : } else {
201 61 : if (RBE_RIGHT(tmp) == NULL
202 52 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
203 9 : struct rb_entry *oleft;
204 :
205 9 : oleft = RBE_LEFT(tmp);
206 9 : if (oleft != NULL)
207 9 : RBE_COLOR(oleft) = RB_BLACK;
208 :
209 9 : RBE_COLOR(tmp) = RB_RED;
210 9 : rbe_rotate_right(rbt, tmp);
211 9 : tmp = RBE_RIGHT(parent);
212 : }
213 :
214 61 : RBE_COLOR(tmp) = RBE_COLOR(parent);
215 61 : RBE_COLOR(parent) = RB_BLACK;
216 61 : if (RBE_RIGHT(tmp))
217 61 : RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
218 :
219 61 : rbe_rotate_left(rbt, parent);
220 61 : rbe = RBH_ROOT(rbt);
221 61 : break;
222 : }
223 : } else {
224 67 : tmp = RBE_LEFT(parent);
225 67 : if (RBE_COLOR(tmp) == RB_RED) {
226 0 : rbe_set_blackred(tmp, parent);
227 0 : rbe_rotate_right(rbt, parent);
228 0 : tmp = RBE_LEFT(parent);
229 : }
230 :
231 67 : if ((RBE_LEFT(tmp) == NULL
232 3 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
233 67 : && (RBE_RIGHT(tmp) == NULL
234 4 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
235 66 : RBE_COLOR(tmp) = RB_RED;
236 66 : rbe = parent;
237 66 : parent = RBE_PARENT(rbe);
238 : } else {
239 1 : if (RBE_LEFT(tmp) == NULL
240 0 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
241 1 : struct rb_entry *oright;
242 :
243 1 : oright = RBE_RIGHT(tmp);
244 1 : if (oright != NULL)
245 1 : RBE_COLOR(oright) = RB_BLACK;
246 :
247 1 : RBE_COLOR(tmp) = RB_RED;
248 1 : rbe_rotate_left(rbt, tmp);
249 1 : tmp = RBE_LEFT(parent);
250 : }
251 :
252 1 : RBE_COLOR(tmp) = RBE_COLOR(parent);
253 1 : RBE_COLOR(parent) = RB_BLACK;
254 1 : if (RBE_LEFT(tmp) != NULL)
255 1 : RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
256 :
257 1 : rbe_rotate_right(rbt, parent);
258 1 : rbe = RBH_ROOT(rbt);
259 1 : break;
260 : }
261 : }
262 : }
263 :
264 2145 : if (rbe != NULL)
265 1198 : RBE_COLOR(rbe) = RB_BLACK;
266 2145 : }
267 :
268 : static inline struct rb_entry *
269 3120 : rbe_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
270 : {
271 3120 : struct rb_entry *child, *parent, *old = rbe;
272 3120 : unsigned int color;
273 :
274 3120 : if (RBE_LEFT(rbe) == NULL)
275 2637 : child = RBE_RIGHT(rbe);
276 483 : else if (RBE_RIGHT(rbe) == NULL)
277 : child = RBE_LEFT(rbe);
278 : else {
279 : struct rb_entry *tmp;
280 :
281 : rbe = RBE_RIGHT(rbe);
282 168 : while ((tmp = RBE_LEFT(rbe)) != NULL)
283 : rbe = tmp;
284 :
285 145 : child = RBE_RIGHT(rbe);
286 145 : parent = RBE_PARENT(rbe);
287 145 : color = RBE_COLOR(rbe);
288 145 : if (child != NULL)
289 27 : RBE_PARENT(child) = parent;
290 145 : if (parent != NULL) {
291 145 : if (RBE_LEFT(parent) == rbe)
292 23 : RBE_LEFT(parent) = child;
293 : else
294 122 : RBE_RIGHT(parent) = child;
295 : } else
296 0 : RBH_ROOT(rbt) = child;
297 145 : if (RBE_PARENT(rbe) == old)
298 122 : parent = rbe;
299 145 : *rbe = *old;
300 :
301 145 : tmp = RBE_PARENT(old);
302 145 : if (tmp != NULL) {
303 61 : if (RBE_LEFT(tmp) == old)
304 2 : RBE_LEFT(tmp) = rbe;
305 : else
306 59 : RBE_RIGHT(tmp) = rbe;
307 : } else
308 84 : RBH_ROOT(rbt) = rbe;
309 :
310 145 : RBE_PARENT(RBE_LEFT(old)) = rbe;
311 145 : if (RBE_RIGHT(old))
312 50 : RBE_PARENT(RBE_RIGHT(old)) = rbe;
313 :
314 145 : goto color;
315 : }
316 :
317 2975 : parent = RBE_PARENT(rbe);
318 2975 : color = RBE_COLOR(rbe);
319 :
320 2975 : if (child != NULL)
321 1005 : RBE_PARENT(child) = parent;
322 2975 : if (parent != NULL) {
323 1145 : if (RBE_LEFT(parent) == rbe)
324 795 : RBE_LEFT(parent) = child;
325 : else
326 350 : RBE_RIGHT(parent) = child;
327 : } else
328 1830 : RBH_ROOT(rbt) = child;
329 3120 : color:
330 3120 : if (color == RB_BLACK)
331 2145 : rbe_remove_color(rbt, parent, child);
332 :
333 3120 : rbt->count--;
334 3120 : memset(old, 0, sizeof(*old));
335 3120 : return (old);
336 : }
337 :
338 3120 : struct typed_rb_entry *typed_rb_remove(struct rbt_tree *rbt,
339 : struct rb_entry *rbe)
340 : {
341 3120 : return rbe_remove(rbt, rbe);
342 : }
343 :
344 393046 : struct typed_rb_entry *typed_rb_insert(struct rbt_tree *rbt,
345 : struct rb_entry *rbe, int (*cmpfn)(
346 : const struct typed_rb_entry *a,
347 : const struct typed_rb_entry *b))
348 : {
349 393046 : struct rb_entry *tmp;
350 393046 : struct rb_entry *parent = NULL;
351 393046 : int comp = 0;
352 :
353 393046 : tmp = RBH_ROOT(rbt);
354 3961730 : while (tmp != NULL) {
355 3640526 : parent = tmp;
356 :
357 3640526 : comp = cmpfn(rbe, tmp);
358 3640526 : if (comp < 0)
359 1728096 : tmp = RBE_LEFT(tmp);
360 1912430 : else if (comp > 0)
361 1840588 : tmp = RBE_RIGHT(tmp);
362 : else
363 71842 : return tmp;
364 : }
365 :
366 321204 : rbe_set(rbe, parent);
367 :
368 321204 : if (parent != NULL) {
369 320031 : if (comp < 0)
370 154882 : RBE_LEFT(parent) = rbe;
371 : else
372 165149 : RBE_RIGHT(parent) = rbe;
373 : } else
374 1173 : RBH_ROOT(rbt) = rbe;
375 :
376 321204 : rbe_insert_color(rbt, rbe);
377 :
378 321204 : return NULL;
379 : }
380 :
381 : /* Finds the node with the same key as elm */
382 6906 : const struct rb_entry *typed_rb_find(const struct rbt_tree *rbt,
383 : const struct rb_entry *key,
384 : int (*cmpfn)(
385 : const struct typed_rb_entry *a,
386 : const struct typed_rb_entry *b))
387 : {
388 6906 : const struct rb_entry *tmp = RBH_ROOT(rbt);
389 6906 : int comp;
390 :
391 10297 : while (tmp != NULL) {
392 8632 : comp = cmpfn(key, tmp);
393 8632 : if (comp < 0)
394 1858 : tmp = RBE_LEFT(tmp);
395 6774 : else if (comp > 0)
396 1533 : tmp = RBE_RIGHT(tmp);
397 : else
398 5241 : return tmp;
399 : }
400 :
401 : return NULL;
402 : }
403 :
404 0 : const struct rb_entry *typed_rb_find_gteq(const struct rbt_tree *rbt,
405 : const struct rb_entry *key,
406 : int (*cmpfn)(
407 : const struct typed_rb_entry *a,
408 : const struct typed_rb_entry *b))
409 : {
410 0 : const struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
411 0 : int comp;
412 :
413 0 : while (tmp != NULL) {
414 0 : comp = cmpfn(key, tmp);
415 0 : if (comp < 0) {
416 0 : best = tmp;
417 0 : tmp = RBE_LEFT(tmp);
418 0 : } else if (comp > 0)
419 0 : tmp = RBE_RIGHT(tmp);
420 : else
421 0 : return tmp;
422 : }
423 :
424 : return best;
425 : }
426 :
427 0 : const struct rb_entry *typed_rb_find_lt(const struct rbt_tree *rbt,
428 : const struct rb_entry *key,
429 : int (*cmpfn)(
430 : const struct typed_rb_entry *a,
431 : const struct typed_rb_entry *b))
432 : {
433 0 : const struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
434 0 : int comp;
435 :
436 0 : while (tmp != NULL) {
437 0 : comp = cmpfn(key, tmp);
438 0 : if (comp <= 0)
439 0 : tmp = RBE_LEFT(tmp);
440 : else {
441 0 : best = tmp;
442 0 : tmp = RBE_RIGHT(tmp);
443 : }
444 : }
445 :
446 0 : return best;
447 : }
448 :
449 749 : struct rb_entry *typed_rb_next(const struct rb_entry *rbe_const)
450 : {
451 749 : struct rb_entry *rbe = (struct rb_entry *)rbe_const;
452 :
453 749 : if (RBE_RIGHT(rbe) != NULL) {
454 : rbe = RBE_RIGHT(rbe);
455 167 : while (RBE_LEFT(rbe) != NULL)
456 : rbe = RBE_LEFT(rbe);
457 : } else {
458 588 : if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
459 : rbe = RBE_PARENT(rbe);
460 : else {
461 678 : while (RBE_PARENT(rbe)
462 678 : && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
463 : rbe = RBE_PARENT(rbe);
464 : rbe = RBE_PARENT(rbe);
465 : }
466 : }
467 :
468 749 : return rbe;
469 : }
470 :
471 0 : struct rb_entry *typed_rb_prev(const struct rb_entry *rbe_const)
472 : {
473 0 : struct rb_entry *rbe = (struct rb_entry *)rbe_const;
474 :
475 0 : if (RBE_LEFT(rbe)) {
476 : rbe = RBE_LEFT(rbe);
477 0 : while (RBE_RIGHT(rbe))
478 : rbe = RBE_RIGHT(rbe);
479 : } else {
480 0 : if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
481 : rbe = RBE_PARENT(rbe);
482 : else {
483 0 : while (RBE_PARENT(rbe)
484 0 : && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
485 : rbe = RBE_PARENT(rbe);
486 : rbe = RBE_PARENT(rbe);
487 : }
488 : }
489 :
490 0 : return rbe;
491 : }
492 :
493 12657 : struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
494 : {
495 12657 : struct rb_entry *rbe = RBH_ROOT(rbt);
496 12657 : struct rb_entry *parent = NULL;
497 :
498 13280 : while (rbe != NULL) {
499 623 : parent = rbe;
500 623 : rbe = RBE_LEFT(rbe);
501 : }
502 :
503 12657 : return parent;
504 : }
505 :
506 0 : struct rb_entry *typed_rb_max(const struct rbt_tree *rbt)
507 : {
508 0 : struct rb_entry *rbe = RBH_ROOT(rbt);
509 0 : struct rb_entry *parent = NULL;
510 :
511 0 : while (rbe != NULL) {
512 0 : parent = rbe;
513 0 : rbe = RBE_RIGHT(rbe);
514 : }
515 :
516 0 : return parent;
517 : }
518 :
519 0 : bool typed_rb_member(const struct typed_rb_root *rbt,
520 : const struct typed_rb_entry *rbe)
521 : {
522 0 : while (rbe->rbt_parent)
523 : rbe = rbe->rbt_parent;
524 0 : return rbe == rbt->rbt_root;
525 : }
|
