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 271522 : static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
65 : {
66 271522 : RBE_PARENT(rbe) = parent;
67 271522 : RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
68 271522 : RBE_COLOR(rbe) = RB_RED;
69 : }
70 :
71 241072 : static inline void rbe_set_blackred(struct rb_entry *black,
72 : struct rb_entry *red)
73 : {
74 241072 : RBE_COLOR(black) = RB_BLACK;
75 241072 : RBE_COLOR(red) = RB_RED;
76 : }
77 :
78 82376 : static inline void rbe_rotate_left(struct rbt_tree *rbt, struct rb_entry *rbe)
79 : {
80 82376 : struct rb_entry *parent;
81 82376 : struct rb_entry *tmp;
82 :
83 82376 : tmp = RBE_RIGHT(rbe);
84 82376 : RBE_RIGHT(rbe) = RBE_LEFT(tmp);
85 82376 : if (RBE_RIGHT(rbe) != NULL)
86 21479 : RBE_PARENT(RBE_LEFT(tmp)) = rbe;
87 :
88 82376 : parent = RBE_PARENT(rbe);
89 82376 : RBE_PARENT(tmp) = parent;
90 82376 : if (parent != NULL) {
91 81614 : if (rbe == RBE_LEFT(parent))
92 52360 : RBE_LEFT(parent) = tmp;
93 : else
94 29254 : RBE_RIGHT(parent) = tmp;
95 : } else
96 762 : RBH_ROOT(rbt) = tmp;
97 :
98 82376 : RBE_LEFT(tmp) = rbe;
99 82376 : RBE_PARENT(rbe) = tmp;
100 82376 : }
101 :
102 76107 : static inline void rbe_rotate_right(struct rbt_tree *rbt, struct rb_entry *rbe)
103 : {
104 76107 : struct rb_entry *parent;
105 76107 : struct rb_entry *tmp;
106 :
107 76107 : tmp = RBE_LEFT(rbe);
108 76107 : RBE_LEFT(rbe) = RBE_RIGHT(tmp);
109 76107 : if (RBE_LEFT(rbe) != NULL)
110 19913 : RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
111 :
112 76107 : parent = RBE_PARENT(rbe);
113 76107 : RBE_PARENT(tmp) = parent;
114 76107 : if (parent != NULL) {
115 75908 : if (rbe == RBE_LEFT(parent))
116 22738 : RBE_LEFT(parent) = tmp;
117 : else
118 53170 : RBE_RIGHT(parent) = tmp;
119 : } else
120 199 : RBH_ROOT(rbt) = tmp;
121 :
122 76107 : RBE_RIGHT(tmp) = rbe;
123 76107 : RBE_PARENT(rbe) = tmp;
124 76107 : }
125 :
126 271522 : static inline void rbe_insert_color(struct rbt_tree *rbt, struct rb_entry *rbe)
127 : {
128 271522 : struct rb_entry *parent, *gparent, *tmp;
129 :
130 271522 : rbt->count++;
131 :
132 271522 : while ((parent = RBE_PARENT(rbe)) != NULL
133 512591 : && RBE_COLOR(parent) == RB_RED) {
134 241069 : gparent = RBE_PARENT(parent);
135 :
136 241069 : if (parent == RBE_LEFT(gparent)) {
137 114457 : tmp = RBE_RIGHT(gparent);
138 114457 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
139 68121 : RBE_COLOR(tmp) = RB_BLACK;
140 68121 : rbe_set_blackred(parent, gparent);
141 68121 : rbe = gparent;
142 68121 : continue;
143 : }
144 :
145 46336 : if (RBE_RIGHT(parent) == rbe) {
146 25622 : rbe_rotate_left(rbt, parent);
147 25622 : tmp = parent;
148 25622 : parent = rbe;
149 25622 : rbe = tmp;
150 : }
151 :
152 46336 : rbe_set_blackred(parent, gparent);
153 46336 : rbe_rotate_right(rbt, gparent);
154 : } else {
155 126612 : tmp = RBE_LEFT(gparent);
156 126612 : if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
157 69928 : RBE_COLOR(tmp) = RB_BLACK;
158 69928 : rbe_set_blackred(parent, gparent);
159 69928 : rbe = gparent;
160 69928 : continue;
161 : }
162 :
163 56684 : if (RBE_LEFT(parent) == rbe) {
164 29759 : rbe_rotate_right(rbt, parent);
165 29759 : tmp = parent;
166 29759 : parent = rbe;
167 29759 : rbe = tmp;
168 : }
169 :
170 56684 : rbe_set_blackred(parent, gparent);
171 56684 : rbe_rotate_left(rbt, gparent);
172 : }
173 : }
174 :
175 271522 : RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
176 271522 : }
177 :
178 2152 : static inline void rbe_remove_color(struct rbt_tree *rbt,
179 : struct rb_entry *parent,
180 : struct rb_entry *rbe)
181 : {
182 2152 : struct rb_entry *tmp;
183 :
184 3325 : while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
185 2340 : && rbe != RBH_ROOT(rbt) && parent) {
186 174 : if (RBE_LEFT(parent) == rbe) {
187 113 : tmp = RBE_RIGHT(parent);
188 113 : if (RBE_COLOR(tmp) == RB_RED) {
189 3 : rbe_set_blackred(tmp, parent);
190 3 : rbe_rotate_left(rbt, parent);
191 3 : tmp = RBE_RIGHT(parent);
192 : }
193 113 : if ((RBE_LEFT(tmp) == NULL
194 23 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
195 91 : && (RBE_RIGHT(tmp) == NULL
196 42 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
197 49 : RBE_COLOR(tmp) = RB_RED;
198 49 : rbe = parent;
199 49 : parent = RBE_PARENT(rbe);
200 : } else {
201 64 : if (RBE_RIGHT(tmp) == NULL
202 55 : || 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 64 : RBE_COLOR(tmp) = RBE_COLOR(parent);
215 64 : RBE_COLOR(parent) = RB_BLACK;
216 64 : if (RBE_RIGHT(tmp))
217 64 : RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
218 :
219 64 : rbe_rotate_left(rbt, parent);
220 64 : rbe = RBH_ROOT(rbt);
221 64 : break;
222 : }
223 : } else {
224 61 : tmp = RBE_LEFT(parent);
225 61 : 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 61 : if ((RBE_LEFT(tmp) == NULL
232 2 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
233 61 : && (RBE_RIGHT(tmp) == NULL
234 5 : || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
235 58 : RBE_COLOR(tmp) = RB_RED;
236 58 : rbe = parent;
237 58 : parent = RBE_PARENT(rbe);
238 : } else {
239 3 : if (RBE_LEFT(tmp) == NULL
240 0 : || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
241 3 : struct rb_entry *oright;
242 :
243 3 : oright = RBE_RIGHT(tmp);
244 3 : if (oright != NULL)
245 3 : RBE_COLOR(oright) = RB_BLACK;
246 :
247 3 : RBE_COLOR(tmp) = RB_RED;
248 3 : rbe_rotate_left(rbt, tmp);
249 3 : tmp = RBE_LEFT(parent);
250 : }
251 :
252 3 : RBE_COLOR(tmp) = RBE_COLOR(parent);
253 3 : RBE_COLOR(parent) = RB_BLACK;
254 3 : if (RBE_LEFT(tmp) != NULL)
255 3 : RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
256 :
257 3 : rbe_rotate_right(rbt, parent);
258 3 : rbe = RBH_ROOT(rbt);
259 3 : break;
260 : }
261 : }
262 : }
263 :
264 2152 : if (rbe != NULL)
265 1237 : RBE_COLOR(rbe) = RB_BLACK;
266 2152 : }
267 :
268 : static inline struct rb_entry *
269 2998 : rbe_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
270 : {
271 2998 : struct rb_entry *child, *parent, *old = rbe;
272 2998 : unsigned int color;
273 :
274 2998 : if (RBE_LEFT(rbe) == NULL)
275 2496 : child = RBE_RIGHT(rbe);
276 502 : 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 153 : while ((tmp = RBE_LEFT(rbe)) != NULL)
283 : rbe = tmp;
284 :
285 133 : child = RBE_RIGHT(rbe);
286 133 : parent = RBE_PARENT(rbe);
287 133 : color = RBE_COLOR(rbe);
288 133 : if (child != NULL)
289 16 : RBE_PARENT(child) = parent;
290 133 : if (parent != NULL) {
291 133 : if (RBE_LEFT(parent) == rbe)
292 20 : RBE_LEFT(parent) = child;
293 : else
294 113 : RBE_RIGHT(parent) = child;
295 : } else
296 0 : RBH_ROOT(rbt) = child;
297 133 : if (RBE_PARENT(rbe) == old)
298 113 : parent = rbe;
299 133 : *rbe = *old;
300 :
301 133 : tmp = RBE_PARENT(old);
302 133 : if (tmp != NULL) {
303 56 : if (RBE_LEFT(tmp) == old)
304 3 : RBE_LEFT(tmp) = rbe;
305 : else
306 53 : RBE_RIGHT(tmp) = rbe;
307 : } else
308 77 : RBH_ROOT(rbt) = rbe;
309 :
310 133 : RBE_PARENT(RBE_LEFT(old)) = rbe;
311 133 : if (RBE_RIGHT(old))
312 36 : RBE_PARENT(RBE_RIGHT(old)) = rbe;
313 :
314 133 : goto color;
315 : }
316 :
317 2865 : parent = RBE_PARENT(rbe);
318 2865 : color = RBE_COLOR(rbe);
319 :
320 2865 : if (child != NULL)
321 1050 : RBE_PARENT(child) = parent;
322 2865 : if (parent != NULL) {
323 1032 : if (RBE_LEFT(parent) == rbe)
324 711 : RBE_LEFT(parent) = child;
325 : else
326 321 : RBE_RIGHT(parent) = child;
327 : } else
328 1833 : RBH_ROOT(rbt) = child;
329 2998 : color:
330 2998 : if (color == RB_BLACK)
331 2152 : rbe_remove_color(rbt, parent, child);
332 :
333 2998 : rbt->count--;
334 2998 : memset(old, 0, sizeof(*old));
335 2998 : return (old);
336 : }
337 :
338 2998 : struct typed_rb_entry *typed_rb_remove(struct rbt_tree *rbt,
339 : struct rb_entry *rbe)
340 : {
341 2998 : return rbe_remove(rbt, rbe);
342 : }
343 :
344 332920 : 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 332920 : struct rb_entry *tmp;
350 332920 : struct rb_entry *parent = NULL;
351 332920 : int comp = 0;
352 :
353 332920 : tmp = RBH_ROOT(rbt);
354 3337884 : while (tmp != NULL) {
355 3066362 : parent = tmp;
356 :
357 3066362 : comp = cmpfn(rbe, tmp);
358 3066362 : if (comp < 0)
359 1452379 : tmp = RBE_LEFT(tmp);
360 1613983 : else if (comp > 0)
361 1552585 : tmp = RBE_RIGHT(tmp);
362 : else
363 61398 : return tmp;
364 : }
365 :
366 271522 : rbe_set(rbe, parent);
367 :
368 271522 : if (parent != NULL) {
369 270409 : if (comp < 0)
370 130913 : RBE_LEFT(parent) = rbe;
371 : else
372 139496 : RBE_RIGHT(parent) = rbe;
373 : } else
374 1113 : RBH_ROOT(rbt) = rbe;
375 :
376 271522 : rbe_insert_color(rbt, rbe);
377 :
378 271522 : return NULL;
379 : }
380 :
381 : /* Finds the node with the same key as elm */
382 6596 : 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 6596 : const struct rb_entry *tmp = RBH_ROOT(rbt);
389 6596 : int comp;
390 :
391 9995 : while (tmp != NULL) {
392 8670 : comp = cmpfn(key, tmp);
393 8670 : if (comp < 0)
394 1867 : tmp = RBE_LEFT(tmp);
395 6803 : else if (comp > 0)
396 1532 : tmp = RBE_RIGHT(tmp);
397 : else
398 5271 : 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 655 : struct rb_entry *typed_rb_next(const struct rb_entry *rbe_const)
450 : {
451 655 : struct rb_entry *rbe = (struct rb_entry *)rbe_const;
452 :
453 655 : if (RBE_RIGHT(rbe) != NULL) {
454 : rbe = RBE_RIGHT(rbe);
455 145 : while (RBE_LEFT(rbe) != NULL)
456 : rbe = RBE_LEFT(rbe);
457 : } else {
458 516 : if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
459 : rbe = RBE_PARENT(rbe);
460 : else {
461 590 : while (RBE_PARENT(rbe)
462 590 : && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
463 : rbe = RBE_PARENT(rbe);
464 : rbe = RBE_PARENT(rbe);
465 : }
466 : }
467 :
468 655 : 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 10931 : struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
494 : {
495 10931 : struct rb_entry *rbe = RBH_ROOT(rbt);
496 10931 : struct rb_entry *parent = NULL;
497 :
498 11482 : while (rbe != NULL) {
499 551 : parent = rbe;
500 551 : rbe = RBE_LEFT(rbe);
501 : }
502 :
503 10931 : 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 : }
|
