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