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