]>
Commit | Line | Data |
---|---|---|
8429abe0 RW |
1 | /* $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt Exp $ */ |
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 | ||
27 | #ifndef _SYS_TREE_H_ | |
28 | #define _SYS_TREE_H_ | |
29 | ||
30 | /* | |
31 | * This file defines data structures for different types of trees: | |
32 | * splay trees and red-black trees. | |
33 | * | |
34 | * A splay tree is a self-organizing data structure. Every operation | |
35 | * on the tree causes a splay to happen. The splay moves the requested | |
36 | * node to the root of the tree and partly rebalances it. | |
37 | * | |
38 | * This has the benefit that request locality causes faster lookups as | |
39 | * the requested nodes move to the top of the tree. On the other hand, | |
40 | * every lookup causes memory writes. | |
41 | * | |
42 | * The Balance Theorem bounds the total access time for m operations | |
43 | * and n inserts on an initially empty tree as O((m + n)lg n). The | |
44 | * amortized cost for a sequence of m accesses to a splay tree is O(lg n); | |
45 | * | |
46 | * A red-black tree is a binary search tree with the node color as an | |
47 | * extra attribute. It fulfills a set of conditions: | |
48 | * - every search path from the root to a leaf consists of the | |
49 | * same number of black nodes, | |
50 | * - each red node (except for the root) has a black parent, | |
51 | * - each leaf node is black. | |
52 | * | |
53 | * Every operation on a red-black tree is bounded as O(lg n). | |
54 | * The maximum height of a red-black tree is 2lg (n+1). | |
55 | */ | |
56 | ||
57 | #define SPLAY_HEAD(name, type) \ | |
58 | struct name { \ | |
59 | struct type *sph_root; /* root of the tree */ \ | |
60 | } | |
61 | ||
62 | #define SPLAY_INITIALIZER(root) \ | |
63 | { NULL } | |
64 | ||
65 | #define SPLAY_INIT(root) do { \ | |
66 | (root)->sph_root = NULL; \ | |
67 | } while (0) | |
68 | ||
69 | #define SPLAY_ENTRY(type) \ | |
70 | struct { \ | |
71 | struct type *spe_left; /* left element */ \ | |
72 | struct type *spe_right; /* right element */ \ | |
73 | } | |
74 | ||
75 | #define SPLAY_LEFT(elm, field) (elm)->field.spe_left | |
76 | #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right | |
77 | #define SPLAY_ROOT(head) (head)->sph_root | |
78 | #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) | |
79 | ||
80 | /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ | |
81 | #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ | |
82 | SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ | |
83 | SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | |
84 | (head)->sph_root = tmp; \ | |
85 | } while (0) | |
86 | ||
87 | #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ | |
88 | SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ | |
89 | SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | |
90 | (head)->sph_root = tmp; \ | |
91 | } while (0) | |
92 | ||
93 | #define SPLAY_LINKLEFT(head, tmp, field) do { \ | |
94 | SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | |
95 | tmp = (head)->sph_root; \ | |
96 | (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ | |
97 | } while (0) | |
98 | ||
99 | #define SPLAY_LINKRIGHT(head, tmp, field) do { \ | |
100 | SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | |
101 | tmp = (head)->sph_root; \ | |
102 | (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ | |
103 | } while (0) | |
104 | ||
105 | #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ | |
106 | SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ | |
107 | SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ | |
108 | SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ | |
109 | SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ | |
110 | } while (0) | |
111 | ||
112 | /* Generates prototypes and inline functions */ | |
113 | ||
114 | #define SPLAY_PROTOTYPE(name, type, field, cmp) \ | |
115 | void name##_SPLAY(struct name *, struct type *); \ | |
116 | void name##_SPLAY_MINMAX(struct name *, int); \ | |
117 | struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ | |
118 | struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ | |
119 | \ | |
120 | /* Finds the node with the same key as elm */ \ | |
121 | static __inline struct type * \ | |
122 | name##_SPLAY_FIND(struct name *head, struct type *elm) \ | |
123 | { \ | |
124 | if (SPLAY_EMPTY(head)) \ | |
125 | return(NULL); \ | |
126 | name##_SPLAY(head, elm); \ | |
127 | if ((cmp)(elm, (head)->sph_root) == 0) \ | |
128 | return (head->sph_root); \ | |
129 | return (NULL); \ | |
130 | } \ | |
131 | \ | |
132 | static __inline struct type * \ | |
133 | name##_SPLAY_NEXT(struct name *head, struct type *elm) \ | |
134 | { \ | |
135 | name##_SPLAY(head, elm); \ | |
136 | if (SPLAY_RIGHT(elm, field) != NULL) { \ | |
137 | elm = SPLAY_RIGHT(elm, field); \ | |
138 | while (SPLAY_LEFT(elm, field) != NULL) { \ | |
139 | elm = SPLAY_LEFT(elm, field); \ | |
140 | } \ | |
141 | } else \ | |
142 | elm = NULL; \ | |
143 | return (elm); \ | |
144 | } \ | |
145 | \ | |
146 | static __inline struct type * \ | |
147 | name##_SPLAY_MIN_MAX(struct name *head, int val) \ | |
148 | { \ | |
149 | name##_SPLAY_MINMAX(head, val); \ | |
150 | return (SPLAY_ROOT(head)); \ | |
151 | } | |
152 | ||
153 | /* Main splay operation. | |
154 | * Moves node close to the key of elm to top | |
155 | */ | |
156 | #define SPLAY_GENERATE(name, type, field, cmp) \ | |
157 | struct type * \ | |
158 | name##_SPLAY_INSERT(struct name *head, struct type *elm) \ | |
159 | { \ | |
160 | if (SPLAY_EMPTY(head)) { \ | |
161 | SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ | |
162 | } else { \ | |
163 | int __comp; \ | |
164 | name##_SPLAY(head, elm); \ | |
165 | __comp = (cmp)(elm, (head)->sph_root); \ | |
166 | if(__comp < 0) { \ | |
167 | SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ | |
168 | SPLAY_RIGHT(elm, field) = (head)->sph_root; \ | |
169 | SPLAY_LEFT((head)->sph_root, field) = NULL; \ | |
170 | } else if (__comp > 0) { \ | |
171 | SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ | |
172 | SPLAY_LEFT(elm, field) = (head)->sph_root; \ | |
173 | SPLAY_RIGHT((head)->sph_root, field) = NULL; \ | |
174 | } else \ | |
175 | return ((head)->sph_root); \ | |
176 | } \ | |
177 | (head)->sph_root = (elm); \ | |
178 | return (NULL); \ | |
179 | } \ | |
180 | \ | |
181 | struct type * \ | |
182 | name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ | |
183 | { \ | |
184 | struct type *__tmp; \ | |
185 | if (SPLAY_EMPTY(head)) \ | |
186 | return (NULL); \ | |
187 | name##_SPLAY(head, elm); \ | |
188 | if ((cmp)(elm, (head)->sph_root) == 0) { \ | |
189 | if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ | |
190 | (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ | |
191 | } else { \ | |
192 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |
193 | (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ | |
194 | name##_SPLAY(head, elm); \ | |
195 | SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ | |
196 | } \ | |
197 | return (elm); \ | |
198 | } \ | |
199 | return (NULL); \ | |
200 | } \ | |
201 | \ | |
202 | void \ | |
203 | name##_SPLAY(struct name *head, struct type *elm) \ | |
204 | { \ | |
205 | struct type __node, *__left, *__right, *__tmp; \ | |
206 | int __comp; \ | |
207 | \ | |
208 | SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | |
209 | __left = __right = &__node; \ | |
210 | \ | |
211 | while ((__comp = (cmp)(elm, (head)->sph_root))) { \ | |
212 | if (__comp < 0) { \ | |
213 | __tmp = SPLAY_LEFT((head)->sph_root, field); \ | |
214 | if (__tmp == NULL) \ | |
215 | break; \ | |
216 | if ((cmp)(elm, __tmp) < 0){ \ | |
217 | SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | |
218 | if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | |
219 | break; \ | |
220 | } \ | |
221 | SPLAY_LINKLEFT(head, __right, field); \ | |
222 | } else if (__comp > 0) { \ | |
223 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |
224 | if (__tmp == NULL) \ | |
225 | break; \ | |
226 | if ((cmp)(elm, __tmp) > 0){ \ | |
227 | SPLAY_ROTATE_LEFT(head, __tmp, field); \ | |
228 | if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | |
229 | break; \ | |
230 | } \ | |
231 | SPLAY_LINKRIGHT(head, __left, field); \ | |
232 | } \ | |
233 | } \ | |
234 | SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | |
235 | } \ | |
236 | \ | |
237 | /* Splay with either the minimum or the maximum element \ | |
238 | * Used to find minimum or maximum element in tree. \ | |
239 | */ \ | |
240 | void name##_SPLAY_MINMAX(struct name *head, int __comp) \ | |
241 | { \ | |
242 | struct type __node, *__left, *__right, *__tmp; \ | |
243 | \ | |
244 | SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | |
245 | __left = __right = &__node; \ | |
246 | \ | |
247 | while (1) { \ | |
248 | if (__comp < 0) { \ | |
249 | __tmp = SPLAY_LEFT((head)->sph_root, field); \ | |
250 | if (__tmp == NULL) \ | |
251 | break; \ | |
252 | if (__comp < 0){ \ | |
253 | SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | |
254 | if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | |
255 | break; \ | |
256 | } \ | |
257 | SPLAY_LINKLEFT(head, __right, field); \ | |
258 | } else if (__comp > 0) { \ | |
259 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |
260 | if (__tmp == NULL) \ | |
261 | break; \ | |
262 | if (__comp > 0) { \ | |
263 | SPLAY_ROTATE_LEFT(head, __tmp, field); \ | |
264 | if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | |
265 | break; \ | |
266 | } \ | |
267 | SPLAY_LINKRIGHT(head, __left, field); \ | |
268 | } \ | |
269 | } \ | |
270 | SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | |
271 | } | |
272 | ||
273 | #define SPLAY_NEGINF -1 | |
274 | #define SPLAY_INF 1 | |
275 | ||
276 | #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) | |
277 | #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) | |
278 | #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) | |
279 | #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) | |
280 | #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ | |
281 | : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) | |
282 | #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ | |
283 | : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) | |
284 | ||
285 | #define SPLAY_FOREACH(x, name, head) \ | |
286 | for ((x) = SPLAY_MIN(name, head); \ | |
287 | (x) != NULL; \ | |
288 | (x) = SPLAY_NEXT(name, head, x)) | |
289 | ||
290 | /* Macros that define a red-black tree */ | |
291 | #define RB_HEAD(name, type) \ | |
292 | struct name { \ | |
293 | struct type *rbh_root; /* root of the tree */ \ | |
294 | } | |
295 | ||
296 | #define RB_INITIALIZER(root) \ | |
297 | { NULL } | |
298 | ||
299 | #define RB_INIT(root) do { \ | |
300 | (root)->rbh_root = NULL; \ | |
301 | } while (0) | |
302 | ||
303 | #define RB_BLACK 0 | |
304 | #define RB_RED 1 | |
305 | #define RB_ENTRY(type) \ | |
306 | struct { \ | |
307 | struct type *rbe_left; /* left element */ \ | |
308 | struct type *rbe_right; /* right element */ \ | |
309 | struct type *rbe_parent; /* parent element */ \ | |
310 | int rbe_color; /* node color */ \ | |
311 | } | |
312 | ||
313 | #define RB_LEFT(elm, field) (elm)->field.rbe_left | |
314 | #define RB_RIGHT(elm, field) (elm)->field.rbe_right | |
315 | #define RB_PARENT(elm, field) (elm)->field.rbe_parent | |
316 | #define RB_COLOR(elm, field) (elm)->field.rbe_color | |
317 | #define RB_ROOT(head) (head)->rbh_root | |
318 | #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | |
319 | ||
320 | #define RB_SET(elm, parent, field) do { \ | |
321 | RB_PARENT(elm, field) = parent; \ | |
322 | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | |
323 | RB_COLOR(elm, field) = RB_RED; \ | |
324 | } while (0) | |
325 | ||
326 | #define RB_SET_BLACKRED(black, red, field) do { \ | |
327 | RB_COLOR(black, field) = RB_BLACK; \ | |
328 | RB_COLOR(red, field) = RB_RED; \ | |
329 | } while (0) | |
330 | ||
331 | #ifndef RB_AUGMENT | |
332 | #define RB_AUGMENT(x) do {} while (0) | |
333 | #endif | |
334 | ||
335 | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | |
336 | (tmp) = RB_RIGHT(elm, field); \ | |
337 | if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ | |
338 | RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ | |
339 | } \ | |
340 | RB_AUGMENT(elm); \ | |
341 | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ | |
342 | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |
343 | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | |
344 | else \ | |
345 | RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |
346 | } else \ | |
347 | (head)->rbh_root = (tmp); \ | |
348 | RB_LEFT(tmp, field) = (elm); \ | |
349 | RB_PARENT(elm, field) = (tmp); \ | |
350 | RB_AUGMENT(tmp); \ | |
351 | if ((RB_PARENT(tmp, field))) \ | |
352 | RB_AUGMENT(RB_PARENT(tmp, field)); \ | |
353 | } while (0) | |
354 | ||
355 | #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | |
356 | (tmp) = RB_LEFT(elm, field); \ | |
357 | if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ | |
358 | RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ | |
359 | } \ | |
360 | RB_AUGMENT(elm); \ | |
361 | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ | |
362 | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |
363 | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | |
364 | else \ | |
365 | RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |
366 | } else \ | |
367 | (head)->rbh_root = (tmp); \ | |
368 | RB_RIGHT(tmp, field) = (elm); \ | |
369 | RB_PARENT(elm, field) = (tmp); \ | |
370 | RB_AUGMENT(tmp); \ | |
371 | if ((RB_PARENT(tmp, field))) \ | |
372 | RB_AUGMENT(RB_PARENT(tmp, field)); \ | |
373 | } while (0) | |
374 | ||
375 | /* Generates prototypes and inline functions */ | |
376 | #define RB_PROTOTYPE(name, type, field, cmp) \ | |
377 | RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) | |
378 | #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ | |
379 | RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) | |
380 | #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ | |
381 | attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ | |
382 | attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ | |
383 | attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ | |
384 | attr struct type *name##_RB_INSERT(struct name *, struct type *); \ | |
385 | attr struct type *name##_RB_FIND(struct name *, struct type *); \ | |
386 | attr struct type *name##_RB_NFIND(struct name *, struct type *); \ | |
387 | attr struct type *name##_RB_NEXT(struct type *); \ | |
388 | attr struct type *name##_RB_PREV(struct type *); \ | |
389 | attr struct type *name##_RB_MINMAX(struct name *, int); \ | |
390 | \ | |
391 | ||
392 | /* Main rb operation. | |
393 | * Moves node close to the key of elm to top | |
394 | */ | |
395 | #define RB_GENERATE(name, type, field, cmp) \ | |
396 | RB_GENERATE_INTERNAL(name, type, field, cmp,) | |
397 | #define RB_GENERATE_STATIC(name, type, field, cmp) \ | |
398 | RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) | |
399 | #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | |
400 | attr void \ | |
401 | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | |
402 | { \ | |
403 | struct type *parent, *gparent, *tmp; \ | |
404 | while ((parent = RB_PARENT(elm, field)) && \ | |
405 | RB_COLOR(parent, field) == RB_RED) { \ | |
406 | gparent = RB_PARENT(parent, field); \ | |
407 | if (parent == RB_LEFT(gparent, field)) { \ | |
408 | tmp = RB_RIGHT(gparent, field); \ | |
409 | if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | |
410 | RB_COLOR(tmp, field) = RB_BLACK; \ | |
411 | RB_SET_BLACKRED(parent, gparent, field);\ | |
412 | elm = gparent; \ | |
413 | continue; \ | |
414 | } \ | |
415 | if (RB_RIGHT(parent, field) == elm) { \ | |
416 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | |
417 | tmp = parent; \ | |
418 | parent = elm; \ | |
419 | elm = tmp; \ | |
420 | } \ | |
421 | RB_SET_BLACKRED(parent, gparent, field); \ | |
422 | RB_ROTATE_RIGHT(head, gparent, tmp, field); \ | |
423 | } else { \ | |
424 | tmp = RB_LEFT(gparent, field); \ | |
425 | if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | |
426 | RB_COLOR(tmp, field) = RB_BLACK; \ | |
427 | RB_SET_BLACKRED(parent, gparent, field);\ | |
428 | elm = gparent; \ | |
429 | continue; \ | |
430 | } \ | |
431 | if (RB_LEFT(parent, field) == elm) { \ | |
432 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |
433 | tmp = parent; \ | |
434 | parent = elm; \ | |
435 | elm = tmp; \ | |
436 | } \ | |
437 | RB_SET_BLACKRED(parent, gparent, field); \ | |
438 | RB_ROTATE_LEFT(head, gparent, tmp, field); \ | |
439 | } \ | |
440 | } \ | |
441 | RB_COLOR(head->rbh_root, field) = RB_BLACK; \ | |
442 | } \ | |
443 | \ | |
444 | attr void \ | |
445 | name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ | |
446 | { \ | |
447 | struct type *tmp; \ | |
448 | while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ | |
449 | elm != RB_ROOT(head)) { \ | |
450 | if (RB_LEFT(parent, field) == elm) { \ | |
451 | tmp = RB_RIGHT(parent, field); \ | |
452 | if (RB_COLOR(tmp, field) == RB_RED) { \ | |
453 | RB_SET_BLACKRED(tmp, parent, field); \ | |
454 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | |
455 | tmp = RB_RIGHT(parent, field); \ | |
456 | } \ | |
457 | if ((RB_LEFT(tmp, field) == NULL || \ | |
458 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | |
459 | (RB_RIGHT(tmp, field) == NULL || \ | |
460 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | |
461 | RB_COLOR(tmp, field) = RB_RED; \ | |
462 | elm = parent; \ | |
463 | parent = RB_PARENT(elm, field); \ | |
464 | } else { \ | |
465 | if (RB_RIGHT(tmp, field) == NULL || \ | |
466 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ | |
467 | struct type *oleft; \ | |
468 | if ((oleft = RB_LEFT(tmp, field)))\ | |
469 | RB_COLOR(oleft, field) = RB_BLACK;\ | |
470 | RB_COLOR(tmp, field) = RB_RED; \ | |
471 | RB_ROTATE_RIGHT(head, tmp, oleft, field);\ | |
472 | tmp = RB_RIGHT(parent, field); \ | |
473 | } \ | |
474 | RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | |
475 | RB_COLOR(parent, field) = RB_BLACK; \ | |
476 | if (RB_RIGHT(tmp, field)) \ | |
477 | RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ | |
478 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | |
479 | elm = RB_ROOT(head); \ | |
480 | break; \ | |
481 | } \ | |
482 | } else { \ | |
483 | tmp = RB_LEFT(parent, field); \ | |
484 | if (RB_COLOR(tmp, field) == RB_RED) { \ | |
485 | RB_SET_BLACKRED(tmp, parent, field); \ | |
486 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |
487 | tmp = RB_LEFT(parent, field); \ | |
488 | } \ | |
489 | if ((RB_LEFT(tmp, field) == NULL || \ | |
490 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | |
491 | (RB_RIGHT(tmp, field) == NULL || \ | |
492 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | |
493 | RB_COLOR(tmp, field) = RB_RED; \ | |
494 | elm = parent; \ | |
495 | parent = RB_PARENT(elm, field); \ | |
496 | } else { \ | |
497 | if (RB_LEFT(tmp, field) == NULL || \ | |
498 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ | |
499 | struct type *oright; \ | |
500 | if ((oright = RB_RIGHT(tmp, field)))\ | |
501 | RB_COLOR(oright, field) = RB_BLACK;\ | |
502 | RB_COLOR(tmp, field) = RB_RED; \ | |
503 | RB_ROTATE_LEFT(head, tmp, oright, field);\ | |
504 | tmp = RB_LEFT(parent, field); \ | |
505 | } \ | |
506 | RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | |
507 | RB_COLOR(parent, field) = RB_BLACK; \ | |
508 | if (RB_LEFT(tmp, field)) \ | |
509 | RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ | |
510 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |
511 | elm = RB_ROOT(head); \ | |
512 | break; \ | |
513 | } \ | |
514 | } \ | |
515 | } \ | |
516 | if (elm) \ | |
517 | RB_COLOR(elm, field) = RB_BLACK; \ | |
518 | } \ | |
519 | \ | |
520 | attr struct type * \ | |
521 | name##_RB_REMOVE(struct name *head, struct type *elm) \ | |
522 | { \ | |
523 | struct type *child, *parent, *old = elm; \ | |
524 | int color; \ | |
525 | if (RB_LEFT(elm, field) == NULL) \ | |
526 | child = RB_RIGHT(elm, field); \ | |
527 | else if (RB_RIGHT(elm, field) == NULL) \ | |
528 | child = RB_LEFT(elm, field); \ | |
529 | else { \ | |
530 | struct type *left; \ | |
531 | elm = RB_RIGHT(elm, field); \ | |
532 | while ((left = RB_LEFT(elm, field))) \ | |
533 | elm = left; \ | |
534 | child = RB_RIGHT(elm, field); \ | |
535 | parent = RB_PARENT(elm, field); \ | |
536 | color = RB_COLOR(elm, field); \ | |
537 | if (child) \ | |
538 | RB_PARENT(child, field) = parent; \ | |
539 | if (parent) { \ | |
540 | if (RB_LEFT(parent, field) == elm) \ | |
541 | RB_LEFT(parent, field) = child; \ | |
542 | else \ | |
543 | RB_RIGHT(parent, field) = child; \ | |
544 | RB_AUGMENT(parent); \ | |
545 | } else \ | |
546 | RB_ROOT(head) = child; \ | |
547 | if (RB_PARENT(elm, field) == old) \ | |
548 | parent = elm; \ | |
549 | (elm)->field = (old)->field; \ | |
550 | if (RB_PARENT(old, field)) { \ | |
551 | if (RB_LEFT(RB_PARENT(old, field), field) == old)\ | |
552 | RB_LEFT(RB_PARENT(old, field), field) = elm;\ | |
553 | else \ | |
554 | RB_RIGHT(RB_PARENT(old, field), field) = elm;\ | |
555 | RB_AUGMENT(RB_PARENT(old, field)); \ | |
556 | } else \ | |
557 | RB_ROOT(head) = elm; \ | |
558 | RB_PARENT(RB_LEFT(old, field), field) = elm; \ | |
559 | if (RB_RIGHT(old, field)) \ | |
560 | RB_PARENT(RB_RIGHT(old, field), field) = elm; \ | |
561 | if (parent) { \ | |
562 | left = parent; \ | |
563 | do { \ | |
564 | RB_AUGMENT(left); \ | |
565 | } while ((left = RB_PARENT(left, field))); \ | |
566 | } \ | |
567 | goto color; \ | |
568 | } \ | |
569 | parent = RB_PARENT(elm, field); \ | |
570 | color = RB_COLOR(elm, field); \ | |
571 | if (child) \ | |
572 | RB_PARENT(child, field) = parent; \ | |
573 | if (parent) { \ | |
574 | if (RB_LEFT(parent, field) == elm) \ | |
575 | RB_LEFT(parent, field) = child; \ | |
576 | else \ | |
577 | RB_RIGHT(parent, field) = child; \ | |
578 | RB_AUGMENT(parent); \ | |
579 | } else \ | |
580 | RB_ROOT(head) = child; \ | |
581 | color: \ | |
582 | if (color == RB_BLACK) \ | |
583 | name##_RB_REMOVE_COLOR(head, parent, child); \ | |
584 | return (old); \ | |
585 | } \ | |
586 | \ | |
587 | /* Inserts a node into the RB tree */ \ | |
588 | attr struct type * \ | |
589 | name##_RB_INSERT(struct name *head, struct type *elm) \ | |
590 | { \ | |
591 | struct type *tmp; \ | |
592 | struct type *parent = NULL; \ | |
593 | int comp = 0; \ | |
594 | tmp = RB_ROOT(head); \ | |
595 | while (tmp) { \ | |
596 | parent = tmp; \ | |
597 | comp = (cmp)(elm, parent); \ | |
598 | if (comp < 0) \ | |
599 | tmp = RB_LEFT(tmp, field); \ | |
600 | else if (comp > 0) \ | |
601 | tmp = RB_RIGHT(tmp, field); \ | |
602 | else \ | |
603 | return (tmp); \ | |
604 | } \ | |
605 | RB_SET(elm, parent, field); \ | |
606 | if (parent != NULL) { \ | |
607 | if (comp < 0) \ | |
608 | RB_LEFT(parent, field) = elm; \ | |
609 | else \ | |
610 | RB_RIGHT(parent, field) = elm; \ | |
611 | RB_AUGMENT(parent); \ | |
612 | } else \ | |
613 | RB_ROOT(head) = elm; \ | |
614 | name##_RB_INSERT_COLOR(head, elm); \ | |
615 | return (NULL); \ | |
616 | } \ | |
617 | \ | |
618 | /* Finds the node with the same key as elm */ \ | |
619 | attr struct type * \ | |
620 | name##_RB_FIND(struct name *head, struct type *elm) \ | |
621 | { \ | |
622 | struct type *tmp = RB_ROOT(head); \ | |
623 | int comp; \ | |
624 | while (tmp) { \ | |
625 | comp = cmp(elm, tmp); \ | |
626 | if (comp < 0) \ | |
627 | tmp = RB_LEFT(tmp, field); \ | |
628 | else if (comp > 0) \ | |
629 | tmp = RB_RIGHT(tmp, field); \ | |
630 | else \ | |
631 | return (tmp); \ | |
632 | } \ | |
633 | return (NULL); \ | |
634 | } \ | |
635 | \ | |
636 | /* Finds the first node greater than or equal to the search key */ \ | |
637 | attr struct type * \ | |
638 | name##_RB_NFIND(struct name *head, struct type *elm) \ | |
639 | { \ | |
640 | struct type *tmp = RB_ROOT(head); \ | |
641 | struct type *res = NULL; \ | |
642 | int comp; \ | |
643 | while (tmp) { \ | |
644 | comp = cmp(elm, tmp); \ | |
645 | if (comp < 0) { \ | |
646 | res = tmp; \ | |
647 | tmp = RB_LEFT(tmp, field); \ | |
648 | } \ | |
649 | else if (comp > 0) \ | |
650 | tmp = RB_RIGHT(tmp, field); \ | |
651 | else \ | |
652 | return (tmp); \ | |
653 | } \ | |
654 | return (res); \ | |
655 | } \ | |
656 | \ | |
657 | /* ARGSUSED */ \ | |
658 | attr struct type * \ | |
659 | name##_RB_NEXT(struct type *elm) \ | |
660 | { \ | |
661 | if (RB_RIGHT(elm, field)) { \ | |
662 | elm = RB_RIGHT(elm, field); \ | |
663 | while (RB_LEFT(elm, field)) \ | |
664 | elm = RB_LEFT(elm, field); \ | |
665 | } else { \ | |
666 | if (RB_PARENT(elm, field) && \ | |
667 | (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ | |
668 | elm = RB_PARENT(elm, field); \ | |
669 | else { \ | |
670 | while (RB_PARENT(elm, field) && \ | |
671 | (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ | |
672 | elm = RB_PARENT(elm, field); \ | |
673 | elm = RB_PARENT(elm, field); \ | |
674 | } \ | |
675 | } \ | |
676 | return (elm); \ | |
677 | } \ | |
678 | \ | |
679 | /* ARGSUSED */ \ | |
680 | attr struct type * \ | |
681 | name##_RB_PREV(struct type *elm) \ | |
682 | { \ | |
683 | if (RB_LEFT(elm, field)) { \ | |
684 | elm = RB_LEFT(elm, field); \ | |
685 | while (RB_RIGHT(elm, field)) \ | |
686 | elm = RB_RIGHT(elm, field); \ | |
687 | } else { \ | |
688 | if (RB_PARENT(elm, field) && \ | |
689 | (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ | |
690 | elm = RB_PARENT(elm, field); \ | |
691 | else { \ | |
692 | while (RB_PARENT(elm, field) && \ | |
693 | (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ | |
694 | elm = RB_PARENT(elm, field); \ | |
695 | elm = RB_PARENT(elm, field); \ | |
696 | } \ | |
697 | } \ | |
698 | return (elm); \ | |
699 | } \ | |
700 | \ | |
701 | attr struct type * \ | |
702 | name##_RB_MINMAX(struct name *head, int val) \ | |
703 | { \ | |
704 | struct type *tmp = RB_ROOT(head); \ | |
705 | struct type *parent = NULL; \ | |
706 | while (tmp) { \ | |
707 | parent = tmp; \ | |
708 | if (val < 0) \ | |
709 | tmp = RB_LEFT(tmp, field); \ | |
710 | else \ | |
711 | tmp = RB_RIGHT(tmp, field); \ | |
712 | } \ | |
713 | return (parent); \ | |
714 | } | |
715 | ||
716 | #define RB_NEGINF -1 | |
717 | #define RB_INF 1 | |
718 | ||
719 | #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | |
720 | #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | |
721 | #define RB_FIND(name, x, y) name##_RB_FIND(x, y) | |
722 | #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) | |
723 | #define RB_NEXT(name, x, y) name##_RB_NEXT(y) | |
724 | #define RB_PREV(name, x, y) name##_RB_PREV(y) | |
725 | #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | |
726 | #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | |
727 | ||
728 | #define RB_FOREACH(x, name, head) \ | |
729 | for ((x) = RB_MIN(name, head); \ | |
730 | (x) != NULL; \ | |
731 | (x) = name##_RB_NEXT(x)) | |
732 | ||
733 | #define RB_FOREACH_SAFE(x, name, head, y) \ | |
734 | for ((x) = RB_MIN(name, head); \ | |
735 | ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ | |
736 | (x) = (y)) | |
737 | ||
738 | #define RB_FOREACH_REVERSE(x, name, head) \ | |
739 | for ((x) = RB_MAX(name, head); \ | |
740 | (x) != NULL; \ | |
741 | (x) = name##_RB_PREV(x)) | |
742 | ||
743 | #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ | |
744 | for ((x) = RB_MAX(name, head); \ | |
745 | ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ | |
746 | (x) = (y)) | |
747 | ||
748 | #endif /* _SYS_TREE_H_ */ |