]>
Commit | Line | Data |
---|---|---|
bfe49944 | 1 | /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ |
cc0583a1 | 2 | /* |
3 | * Copyright 2002 Niels Provos <provos@citi.umich.edu> | |
4 | * All rights reserved. | |
5 | * | |
6 | * Redistribution and use in source and binary forms, with or without | |
7 | * modification, are permitted provided that the following conditions | |
8 | * are met: | |
9 | * 1. Redistributions of source code must retain the above copyright | |
10 | * notice, this list of conditions and the following disclaimer. | |
11 | * 2. Redistributions in binary form must reproduce the above copyright | |
12 | * notice, this list of conditions and the following disclaimer in the | |
13 | * documentation and/or other materials provided with the distribution. | |
14 | * | |
15 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | |
16 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | |
17 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | |
18 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | |
19 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
20 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
21 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
22 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
23 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | |
24 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
25 | */ | |
26 | ||
08822d99 | 27 | /* OPENBSD ORIGINAL: sys/sys/tree.h */ |
28 | ||
cc0583a1 | 29 | #ifndef _SYS_TREE_H_ |
30 | #define _SYS_TREE_H_ | |
31 | ||
32 | /* | |
33 | * This file defines data structures for different types of trees: | |
34 | * splay trees and red-black trees. | |
35 | * | |
36 | * A splay tree is a self-organizing data structure. Every operation | |
37 | * on the tree causes a splay to happen. The splay moves the requested | |
38 | * node to the root of the tree and partly rebalances it. | |
39 | * | |
40 | * This has the benefit that request locality causes faster lookups as | |
41 | * the requested nodes move to the top of the tree. On the other hand, | |
42 | * every lookup causes memory writes. | |
43 | * | |
44 | * The Balance Theorem bounds the total access time for m operations | |
45 | * and n inserts on an initially empty tree as O((m + n)lg n). The | |
46 | * amortized cost for a sequence of m accesses to a splay tree is O(lg n); | |
47 | * | |
48 | * A red-black tree is a binary search tree with the node color as an | |
49 | * extra attribute. It fulfills a set of conditions: | |
50 | * - every search path from the root to a leaf consists of the | |
51 | * same number of black nodes, | |
52 | * - each red node (except for the root) has a black parent, | |
53 | * - each leaf node is black. | |
54 | * | |
55 | * Every operation on a red-black tree is bounded as O(lg n). | |
56 | * The maximum height of a red-black tree is 2lg (n+1). | |
57 | */ | |
58 | ||
59 | #define SPLAY_HEAD(name, type) \ | |
60 | struct name { \ | |
61 | struct type *sph_root; /* root of the tree */ \ | |
62 | } | |
63 | ||
64 | #define SPLAY_INITIALIZER(root) \ | |
65 | { NULL } | |
66 | ||
67 | #define SPLAY_INIT(root) do { \ | |
68 | (root)->sph_root = NULL; \ | |
69 | } while (0) | |
70 | ||
71 | #define SPLAY_ENTRY(type) \ | |
72 | struct { \ | |
73 | struct type *spe_left; /* left element */ \ | |
74 | struct type *spe_right; /* right element */ \ | |
75 | } | |
76 | ||
77 | #define SPLAY_LEFT(elm, field) (elm)->field.spe_left | |
78 | #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right | |
79 | #define SPLAY_ROOT(head) (head)->sph_root | |
80 | #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) | |
81 | ||
82 | /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ | |
83 | #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ | |
84 | SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ | |
85 | SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | |
86 | (head)->sph_root = tmp; \ | |
87 | } while (0) | |
88 | ||
89 | #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ | |
90 | SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ | |
91 | SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | |
92 | (head)->sph_root = tmp; \ | |
93 | } while (0) | |
94 | ||
95 | #define SPLAY_LINKLEFT(head, tmp, field) do { \ | |
96 | SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | |
97 | tmp = (head)->sph_root; \ | |
98 | (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ | |
99 | } while (0) | |
100 | ||
101 | #define SPLAY_LINKRIGHT(head, tmp, field) do { \ | |
102 | SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | |
103 | tmp = (head)->sph_root; \ | |
104 | (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ | |
105 | } while (0) | |
106 | ||
107 | #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ | |
108 | SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ | |
109 | SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ | |
110 | SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ | |
111 | SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ | |
112 | } while (0) | |
113 | ||
114 | /* Generates prototypes and inline functions */ | |
115 | ||
116 | #define SPLAY_PROTOTYPE(name, type, field, cmp) \ | |
117 | void name##_SPLAY(struct name *, struct type *); \ | |
118 | void name##_SPLAY_MINMAX(struct name *, int); \ | |
119 | struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ | |
120 | struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ | |
121 | \ | |
122 | /* Finds the node with the same key as elm */ \ | |
123 | static __inline struct type * \ | |
124 | name##_SPLAY_FIND(struct name *head, struct type *elm) \ | |
125 | { \ | |
126 | if (SPLAY_EMPTY(head)) \ | |
127 | return(NULL); \ | |
128 | name##_SPLAY(head, elm); \ | |
129 | if ((cmp)(elm, (head)->sph_root) == 0) \ | |
130 | return (head->sph_root); \ | |
131 | return (NULL); \ | |
132 | } \ | |
133 | \ | |
134 | static __inline struct type * \ | |
135 | name##_SPLAY_NEXT(struct name *head, struct type *elm) \ | |
136 | { \ | |
137 | name##_SPLAY(head, elm); \ | |
138 | if (SPLAY_RIGHT(elm, field) != NULL) { \ | |
139 | elm = SPLAY_RIGHT(elm, field); \ | |
140 | while (SPLAY_LEFT(elm, field) != NULL) { \ | |
141 | elm = SPLAY_LEFT(elm, field); \ | |
142 | } \ | |
143 | } else \ | |
144 | elm = NULL; \ | |
145 | return (elm); \ | |
146 | } \ | |
147 | \ | |
148 | static __inline struct type * \ | |
149 | name##_SPLAY_MIN_MAX(struct name *head, int val) \ | |
150 | { \ | |
151 | name##_SPLAY_MINMAX(head, val); \ | |
152 | return (SPLAY_ROOT(head)); \ | |
153 | } | |
154 | ||
155 | /* Main splay operation. | |
156 | * Moves node close to the key of elm to top | |
157 | */ | |
158 | #define SPLAY_GENERATE(name, type, field, cmp) \ | |
159 | struct type * \ | |
160 | name##_SPLAY_INSERT(struct name *head, struct type *elm) \ | |
161 | { \ | |
162 | if (SPLAY_EMPTY(head)) { \ | |
163 | SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ | |
164 | } else { \ | |
165 | int __comp; \ | |
166 | name##_SPLAY(head, elm); \ | |
167 | __comp = (cmp)(elm, (head)->sph_root); \ | |
168 | if(__comp < 0) { \ | |
169 | SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ | |
170 | SPLAY_RIGHT(elm, field) = (head)->sph_root; \ | |
171 | SPLAY_LEFT((head)->sph_root, field) = NULL; \ | |
172 | } else if (__comp > 0) { \ | |
173 | SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ | |
174 | SPLAY_LEFT(elm, field) = (head)->sph_root; \ | |
175 | SPLAY_RIGHT((head)->sph_root, field) = NULL; \ | |
176 | } else \ | |
177 | return ((head)->sph_root); \ | |
178 | } \ | |
179 | (head)->sph_root = (elm); \ | |
180 | return (NULL); \ | |
181 | } \ | |
182 | \ | |
183 | struct type * \ | |
184 | name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ | |
185 | { \ | |
186 | struct type *__tmp; \ | |
187 | if (SPLAY_EMPTY(head)) \ | |
188 | return (NULL); \ | |
189 | name##_SPLAY(head, elm); \ | |
190 | if ((cmp)(elm, (head)->sph_root) == 0) { \ | |
191 | if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ | |
192 | (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ | |
193 | } else { \ | |
194 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |
195 | (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ | |
196 | name##_SPLAY(head, elm); \ | |
197 | SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ | |
198 | } \ | |
199 | return (elm); \ | |
200 | } \ | |
201 | return (NULL); \ | |
202 | } \ | |
203 | \ | |
204 | void \ | |
205 | name##_SPLAY(struct name *head, struct type *elm) \ | |
206 | { \ | |
207 | struct type __node, *__left, *__right, *__tmp; \ | |
208 | int __comp; \ | |
209 | \ | |
210 | SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | |
211 | __left = __right = &__node; \ | |
212 | \ | |
213 | while ((__comp = (cmp)(elm, (head)->sph_root))) { \ | |
214 | if (__comp < 0) { \ | |
215 | __tmp = SPLAY_LEFT((head)->sph_root, field); \ | |
216 | if (__tmp == NULL) \ | |
217 | break; \ | |
218 | if ((cmp)(elm, __tmp) < 0){ \ | |
219 | SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | |
220 | if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | |
221 | break; \ | |
222 | } \ | |
223 | SPLAY_LINKLEFT(head, __right, field); \ | |
224 | } else if (__comp > 0) { \ | |
225 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |
226 | if (__tmp == NULL) \ | |
227 | break; \ | |
228 | if ((cmp)(elm, __tmp) > 0){ \ | |
229 | SPLAY_ROTATE_LEFT(head, __tmp, field); \ | |
230 | if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | |
231 | break; \ | |
232 | } \ | |
233 | SPLAY_LINKRIGHT(head, __left, field); \ | |
234 | } \ | |
235 | } \ | |
236 | SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | |
237 | } \ | |
238 | \ | |
239 | /* Splay with either the minimum or the maximum element \ | |
240 | * Used to find minimum or maximum element in tree. \ | |
241 | */ \ | |
242 | void name##_SPLAY_MINMAX(struct name *head, int __comp) \ | |
243 | { \ | |
244 | struct type __node, *__left, *__right, *__tmp; \ | |
245 | \ | |
246 | SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | |
247 | __left = __right = &__node; \ | |
248 | \ | |
249 | while (1) { \ | |
250 | if (__comp < 0) { \ | |
251 | __tmp = SPLAY_LEFT((head)->sph_root, field); \ | |
252 | if (__tmp == NULL) \ | |
253 | break; \ | |
254 | if (__comp < 0){ \ | |
255 | SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | |
256 | if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | |
257 | break; \ | |
258 | } \ | |
259 | SPLAY_LINKLEFT(head, __right, field); \ | |
260 | } else if (__comp > 0) { \ | |
261 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |
262 | if (__tmp == NULL) \ | |
263 | break; \ | |
264 | if (__comp > 0) { \ | |
265 | SPLAY_ROTATE_LEFT(head, __tmp, field); \ | |
266 | if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | |
267 | break; \ | |
268 | } \ | |
269 | SPLAY_LINKRIGHT(head, __left, field); \ | |
270 | } \ | |
271 | } \ | |
272 | SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | |
273 | } | |
274 | ||
275 | #define SPLAY_NEGINF -1 | |
276 | #define SPLAY_INF 1 | |
277 | ||
278 | #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) | |
279 | #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) | |
280 | #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) | |
281 | #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) | |
282 | #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ | |
283 | : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) | |
284 | #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ | |
285 | : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) | |
286 | ||
287 | #define SPLAY_FOREACH(x, name, head) \ | |
288 | for ((x) = SPLAY_MIN(name, head); \ | |
289 | (x) != NULL; \ | |
290 | (x) = SPLAY_NEXT(name, head, x)) | |
291 | ||
292 | /* Macros that define a red-back tree */ | |
293 | #define RB_HEAD(name, type) \ | |
294 | struct name { \ | |
295 | struct type *rbh_root; /* root of the tree */ \ | |
296 | } | |
297 | ||
298 | #define RB_INITIALIZER(root) \ | |
299 | { NULL } | |
300 | ||
301 | #define RB_INIT(root) do { \ | |
302 | (root)->rbh_root = NULL; \ | |
303 | } while (0) | |
304 | ||
305 | #define RB_BLACK 0 | |
306 | #define RB_RED 1 | |
307 | #define RB_ENTRY(type) \ | |
308 | struct { \ | |
309 | struct type *rbe_left; /* left element */ \ | |
310 | struct type *rbe_right; /* right element */ \ | |
311 | struct type *rbe_parent; /* parent element */ \ | |
312 | int rbe_color; /* node color */ \ | |
313 | } | |
314 | ||
315 | #define RB_LEFT(elm, field) (elm)->field.rbe_left | |
316 | #define RB_RIGHT(elm, field) (elm)->field.rbe_right | |
317 | #define RB_PARENT(elm, field) (elm)->field.rbe_parent | |
318 | #define RB_COLOR(elm, field) (elm)->field.rbe_color | |
319 | #define RB_ROOT(head) (head)->rbh_root | |
320 | #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | |
321 | ||
322 | #define RB_SET(elm, parent, field) do { \ | |
323 | RB_PARENT(elm, field) = parent; \ | |
324 | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | |
325 | RB_COLOR(elm, field) = RB_RED; \ | |
326 | } while (0) | |
327 | ||
328 | #define RB_SET_BLACKRED(black, red, field) do { \ | |
329 | RB_COLOR(black, field) = RB_BLACK; \ | |
330 | RB_COLOR(red, field) = RB_RED; \ | |
331 | } while (0) | |
332 | ||
333 | #ifndef RB_AUGMENT | |
334 | #define RB_AUGMENT(x) | |
335 | #endif | |
336 | ||
337 | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | |
338 | (tmp) = RB_RIGHT(elm, field); \ | |
339 | if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ | |
340 | RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ | |
341 | } \ | |
342 | RB_AUGMENT(elm); \ | |
343 | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ | |
344 | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |
345 | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | |
346 | else \ | |
347 | RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |
cc0583a1 | 348 | } else \ |
349 | (head)->rbh_root = (tmp); \ | |
350 | RB_LEFT(tmp, field) = (elm); \ | |
351 | RB_PARENT(elm, field) = (tmp); \ | |
352 | RB_AUGMENT(tmp); \ | |
bfe49944 | 353 | if ((RB_PARENT(tmp, field))) \ |
354 | RB_AUGMENT(RB_PARENT(tmp, field)); \ | |
cc0583a1 | 355 | } while (0) |
356 | ||
357 | #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | |
358 | (tmp) = RB_LEFT(elm, field); \ | |
359 | if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ | |
360 | RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ | |
361 | } \ | |
362 | RB_AUGMENT(elm); \ | |
363 | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ | |
364 | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |
365 | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | |
366 | else \ | |
367 | RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |
cc0583a1 | 368 | } else \ |
369 | (head)->rbh_root = (tmp); \ | |
370 | RB_RIGHT(tmp, field) = (elm); \ | |
371 | RB_PARENT(elm, field) = (tmp); \ | |
372 | RB_AUGMENT(tmp); \ | |
bfe49944 | 373 | if ((RB_PARENT(tmp, field))) \ |
374 | RB_AUGMENT(RB_PARENT(tmp, field)); \ | |
cc0583a1 | 375 | } while (0) |
376 | ||
377 | /* Generates prototypes and inline functions */ | |
378 | #define RB_PROTOTYPE(name, type, field, cmp) \ | |
379 | void name##_RB_INSERT_COLOR(struct name *, struct type *); \ | |
380 | void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ | |
381 | struct type *name##_RB_REMOVE(struct name *, struct type *); \ | |
382 | struct type *name##_RB_INSERT(struct name *, struct type *); \ | |
383 | struct type *name##_RB_FIND(struct name *, struct type *); \ | |
384 | struct type *name##_RB_NEXT(struct name *, struct type *); \ | |
385 | struct type *name##_RB_MINMAX(struct name *, int); \ | |
386 | \ | |
387 | ||
388 | /* Main rb operation. | |
389 | * Moves node close to the key of elm to top | |
390 | */ | |
391 | #define RB_GENERATE(name, type, field, cmp) \ | |
392 | void \ | |
393 | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | |
394 | { \ | |
395 | struct type *parent, *gparent, *tmp; \ | |
396 | while ((parent = RB_PARENT(elm, field)) && \ | |
397 | RB_COLOR(parent, field) == RB_RED) { \ | |
398 | gparent = RB_PARENT(parent, field); \ | |
399 | if (parent == RB_LEFT(gparent, field)) { \ | |
400 | tmp = RB_RIGHT(gparent, field); \ | |
401 | if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | |
402 | RB_COLOR(tmp, field) = RB_BLACK; \ | |
403 | RB_SET_BLACKRED(parent, gparent, field);\ | |
404 | elm = gparent; \ | |
405 | continue; \ | |
406 | } \ | |
407 | if (RB_RIGHT(parent, field) == elm) { \ | |
408 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | |
409 | tmp = parent; \ | |
410 | parent = elm; \ | |
411 | elm = tmp; \ | |
412 | } \ | |
413 | RB_SET_BLACKRED(parent, gparent, field); \ | |
414 | RB_ROTATE_RIGHT(head, gparent, tmp, field); \ | |
415 | } else { \ | |
416 | tmp = RB_LEFT(gparent, field); \ | |
417 | if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | |
418 | RB_COLOR(tmp, field) = RB_BLACK; \ | |
419 | RB_SET_BLACKRED(parent, gparent, field);\ | |
420 | elm = gparent; \ | |
421 | continue; \ | |
422 | } \ | |
423 | if (RB_LEFT(parent, field) == elm) { \ | |
424 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |
425 | tmp = parent; \ | |
426 | parent = elm; \ | |
427 | elm = tmp; \ | |
428 | } \ | |
429 | RB_SET_BLACKRED(parent, gparent, field); \ | |
430 | RB_ROTATE_LEFT(head, gparent, tmp, field); \ | |
431 | } \ | |
432 | } \ | |
433 | RB_COLOR(head->rbh_root, field) = RB_BLACK; \ | |
434 | } \ | |
435 | \ | |
436 | void \ | |
437 | name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ | |
438 | { \ | |
439 | struct type *tmp; \ | |
440 | while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ | |
441 | elm != RB_ROOT(head)) { \ | |
442 | if (RB_LEFT(parent, field) == elm) { \ | |
443 | tmp = RB_RIGHT(parent, field); \ | |
444 | if (RB_COLOR(tmp, field) == RB_RED) { \ | |
445 | RB_SET_BLACKRED(tmp, parent, field); \ | |
446 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | |
447 | tmp = RB_RIGHT(parent, field); \ | |
448 | } \ | |
449 | if ((RB_LEFT(tmp, field) == NULL || \ | |
450 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | |
451 | (RB_RIGHT(tmp, field) == NULL || \ | |
452 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | |
453 | RB_COLOR(tmp, field) = RB_RED; \ | |
454 | elm = parent; \ | |
455 | parent = RB_PARENT(elm, field); \ | |
456 | } else { \ | |
457 | if (RB_RIGHT(tmp, field) == NULL || \ | |
458 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ | |
459 | struct type *oleft; \ | |
460 | if ((oleft = RB_LEFT(tmp, field)))\ | |
461 | RB_COLOR(oleft, field) = RB_BLACK;\ | |
462 | RB_COLOR(tmp, field) = RB_RED; \ | |
463 | RB_ROTATE_RIGHT(head, tmp, oleft, field);\ | |
464 | tmp = RB_RIGHT(parent, field); \ | |
465 | } \ | |
466 | RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | |
467 | RB_COLOR(parent, field) = RB_BLACK; \ | |
468 | if (RB_RIGHT(tmp, field)) \ | |
469 | RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ | |
470 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | |
471 | elm = RB_ROOT(head); \ | |
472 | break; \ | |
473 | } \ | |
474 | } else { \ | |
475 | tmp = RB_LEFT(parent, field); \ | |
476 | if (RB_COLOR(tmp, field) == RB_RED) { \ | |
477 | RB_SET_BLACKRED(tmp, parent, field); \ | |
478 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |
479 | tmp = RB_LEFT(parent, field); \ | |
480 | } \ | |
481 | if ((RB_LEFT(tmp, field) == NULL || \ | |
482 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | |
483 | (RB_RIGHT(tmp, field) == NULL || \ | |
484 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | |
485 | RB_COLOR(tmp, field) = RB_RED; \ | |
486 | elm = parent; \ | |
487 | parent = RB_PARENT(elm, field); \ | |
488 | } else { \ | |
489 | if (RB_LEFT(tmp, field) == NULL || \ | |
490 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ | |
491 | struct type *oright; \ | |
492 | if ((oright = RB_RIGHT(tmp, field)))\ | |
493 | RB_COLOR(oright, field) = RB_BLACK;\ | |
494 | RB_COLOR(tmp, field) = RB_RED; \ | |
495 | RB_ROTATE_LEFT(head, tmp, oright, field);\ | |
496 | tmp = RB_LEFT(parent, field); \ | |
497 | } \ | |
498 | RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | |
499 | RB_COLOR(parent, field) = RB_BLACK; \ | |
500 | if (RB_LEFT(tmp, field)) \ | |
501 | RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ | |
502 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |
503 | elm = RB_ROOT(head); \ | |
504 | break; \ | |
505 | } \ | |
506 | } \ | |
507 | } \ | |
508 | if (elm) \ | |
509 | RB_COLOR(elm, field) = RB_BLACK; \ | |
510 | } \ | |
511 | \ | |
512 | struct type * \ | |
513 | name##_RB_REMOVE(struct name *head, struct type *elm) \ | |
514 | { \ | |
515 | struct type *child, *parent, *old = elm; \ | |
516 | int color; \ | |
517 | if (RB_LEFT(elm, field) == NULL) \ | |
518 | child = RB_RIGHT(elm, field); \ | |
519 | else if (RB_RIGHT(elm, field) == NULL) \ | |
520 | child = RB_LEFT(elm, field); \ | |
521 | else { \ | |
522 | struct type *left; \ | |
523 | elm = RB_RIGHT(elm, field); \ | |
524 | while ((left = RB_LEFT(elm, field))) \ | |
525 | elm = left; \ | |
526 | child = RB_RIGHT(elm, field); \ | |
527 | parent = RB_PARENT(elm, field); \ | |
528 | color = RB_COLOR(elm, field); \ | |
529 | if (child) \ | |
530 | RB_PARENT(child, field) = parent; \ | |
531 | if (parent) { \ | |
532 | if (RB_LEFT(parent, field) == elm) \ | |
533 | RB_LEFT(parent, field) = child; \ | |
534 | else \ | |
535 | RB_RIGHT(parent, field) = child; \ | |
536 | RB_AUGMENT(parent); \ | |
537 | } else \ | |
538 | RB_ROOT(head) = child; \ | |
539 | if (RB_PARENT(elm, field) == old) \ | |
540 | parent = elm; \ | |
541 | (elm)->field = (old)->field; \ | |
542 | if (RB_PARENT(old, field)) { \ | |
543 | if (RB_LEFT(RB_PARENT(old, field), field) == old)\ | |
544 | RB_LEFT(RB_PARENT(old, field), field) = elm;\ | |
545 | else \ | |
546 | RB_RIGHT(RB_PARENT(old, field), field) = elm;\ | |
547 | RB_AUGMENT(RB_PARENT(old, field)); \ | |
548 | } else \ | |
549 | RB_ROOT(head) = elm; \ | |
550 | RB_PARENT(RB_LEFT(old, field), field) = elm; \ | |
551 | if (RB_RIGHT(old, field)) \ | |
552 | RB_PARENT(RB_RIGHT(old, field), field) = elm; \ | |
553 | if (parent) { \ | |
554 | left = parent; \ | |
555 | do { \ | |
556 | RB_AUGMENT(left); \ | |
557 | } while ((left = RB_PARENT(left, field))); \ | |
558 | } \ | |
559 | goto color; \ | |
560 | } \ | |
561 | parent = RB_PARENT(elm, field); \ | |
562 | color = RB_COLOR(elm, field); \ | |
563 | if (child) \ | |
564 | RB_PARENT(child, field) = parent; \ | |
565 | if (parent) { \ | |
566 | if (RB_LEFT(parent, field) == elm) \ | |
567 | RB_LEFT(parent, field) = child; \ | |
568 | else \ | |
569 | RB_RIGHT(parent, field) = child; \ | |
570 | RB_AUGMENT(parent); \ | |
571 | } else \ | |
572 | RB_ROOT(head) = child; \ | |
573 | color: \ | |
574 | if (color == RB_BLACK) \ | |
575 | name##_RB_REMOVE_COLOR(head, parent, child); \ | |
576 | return (old); \ | |
577 | } \ | |
578 | \ | |
579 | /* Inserts a node into the RB tree */ \ | |
580 | struct type * \ | |
581 | name##_RB_INSERT(struct name *head, struct type *elm) \ | |
582 | { \ | |
583 | struct type *tmp; \ | |
584 | struct type *parent = NULL; \ | |
585 | int comp = 0; \ | |
586 | tmp = RB_ROOT(head); \ | |
587 | while (tmp) { \ | |
588 | parent = tmp; \ | |
589 | comp = (cmp)(elm, parent); \ | |
590 | if (comp < 0) \ | |
591 | tmp = RB_LEFT(tmp, field); \ | |
592 | else if (comp > 0) \ | |
593 | tmp = RB_RIGHT(tmp, field); \ | |
594 | else \ | |
595 | return (tmp); \ | |
596 | } \ | |
597 | RB_SET(elm, parent, field); \ | |
598 | if (parent != NULL) { \ | |
599 | if (comp < 0) \ | |
600 | RB_LEFT(parent, field) = elm; \ | |
601 | else \ | |
602 | RB_RIGHT(parent, field) = elm; \ | |
603 | RB_AUGMENT(parent); \ | |
604 | } else \ | |
605 | RB_ROOT(head) = elm; \ | |
606 | name##_RB_INSERT_COLOR(head, elm); \ | |
607 | return (NULL); \ | |
608 | } \ | |
609 | \ | |
610 | /* Finds the node with the same key as elm */ \ | |
611 | struct type * \ | |
612 | name##_RB_FIND(struct name *head, struct type *elm) \ | |
613 | { \ | |
614 | struct type *tmp = RB_ROOT(head); \ | |
615 | int comp; \ | |
616 | while (tmp) { \ | |
617 | comp = cmp(elm, tmp); \ | |
618 | if (comp < 0) \ | |
619 | tmp = RB_LEFT(tmp, field); \ | |
620 | else if (comp > 0) \ | |
621 | tmp = RB_RIGHT(tmp, field); \ | |
622 | else \ | |
623 | return (tmp); \ | |
624 | } \ | |
625 | return (NULL); \ | |
626 | } \ | |
627 | \ | |
628 | struct type * \ | |
629 | name##_RB_NEXT(struct name *head, struct type *elm) \ | |
630 | { \ | |
631 | if (RB_RIGHT(elm, field)) { \ | |
632 | elm = RB_RIGHT(elm, field); \ | |
633 | while (RB_LEFT(elm, field)) \ | |
634 | elm = RB_LEFT(elm, field); \ | |
635 | } else { \ | |
636 | if (RB_PARENT(elm, field) && \ | |
637 | (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ | |
638 | elm = RB_PARENT(elm, field); \ | |
639 | else { \ | |
640 | while (RB_PARENT(elm, field) && \ | |
641 | (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ | |
642 | elm = RB_PARENT(elm, field); \ | |
643 | elm = RB_PARENT(elm, field); \ | |
644 | } \ | |
645 | } \ | |
646 | return (elm); \ | |
647 | } \ | |
648 | \ | |
649 | struct type * \ | |
650 | name##_RB_MINMAX(struct name *head, int val) \ | |
651 | { \ | |
652 | struct type *tmp = RB_ROOT(head); \ | |
653 | struct type *parent = NULL; \ | |
654 | while (tmp) { \ | |
655 | parent = tmp; \ | |
656 | if (val < 0) \ | |
657 | tmp = RB_LEFT(tmp, field); \ | |
658 | else \ | |
659 | tmp = RB_RIGHT(tmp, field); \ | |
660 | } \ | |
661 | return (parent); \ | |
662 | } | |
663 | ||
664 | #define RB_NEGINF -1 | |
665 | #define RB_INF 1 | |
666 | ||
667 | #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | |
668 | #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | |
669 | #define RB_FIND(name, x, y) name##_RB_FIND(x, y) | |
670 | #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y) | |
671 | #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | |
672 | #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | |
673 | ||
674 | #define RB_FOREACH(x, name, head) \ | |
675 | for ((x) = RB_MIN(name, head); \ | |
676 | (x) != NULL; \ | |
677 | (x) = name##_RB_NEXT(head, x)) | |
678 | ||
679 | #endif /* _SYS_TREE_H_ */ |