![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to atree.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / libaitio / inc|
Return to atree.h CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / libaitio / inc |
1.2 misho 1: /*************************************************************************
2: * (C) 2011 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
3: * by Michael Pounov <misho@elwix.org>
4: *
5: * $Author: misho $
1.4 ! misho 6: * $Id: atree.h,v 1.3.28.2 2012/08/17 22:00:03 misho Exp $
1.2 misho 7: *
8: **************************************************************************
9: The ELWIX and AITNET software is distributed under the following
10: terms:
11:
12: All of the documentation and software included in the ELWIX and AITNET
13: Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>
14:
1.4 ! misho 15: Copyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
1.2 misho 16: by Michael Pounov <misho@elwix.org>. All rights reserved.
17:
18: Redistribution and use in source and binary forms, with or without
19: modification, are permitted provided that the following conditions
20: are met:
21: 1. Redistributions of source code must retain the above copyright
22: notice, this list of conditions and the following disclaimer.
23: 2. Redistributions in binary form must reproduce the above copyright
24: notice, this list of conditions and the following disclaimer in the
25: documentation and/or other materials provided with the distribution.
26: 3. All advertising materials mentioning features or use of this software
27: must display the following acknowledgement:
28: This product includes software developed by Michael Pounov <misho@elwix.org>
29: ELWIX - Embedded LightWeight unIX and its contributors.
30: 4. Neither the name of AITNET nor the names of its contributors
31: may be used to endorse or promote products derived from this software
32: without specific prior written permission.
33:
34: THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
35: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37: ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38: FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39: DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40: OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41: HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42: LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43: OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44: SUCH DAMAGE.
45: */
46: /*
47: *
48: * AVL tree implementation, changes in other trees and file are
49: * Copyrighted 2011 Michael Pounov <misho@elwix.org>
50: * All rights reserved.
51: *
52: */
53: /* $OpenBSD: tree.h,v 1.12 2009/03/02 09:42:55 mikeb Exp $ */
54: /*
55: * Copyright 2002 Niels Provos <provos@citi.umich.edu>
56: * All rights reserved.
57: *
58: * Redistribution and use in source and binary forms, with or without
59: * modification, are permitted provided that the following conditions
60: * are met:
61: * 1. Redistributions of source code must retain the above copyright
62: * notice, this list of conditions and the following disclaimer.
63: * 2. Redistributions in binary form must reproduce the above copyright
64: * notice, this list of conditions and the following disclaimer in the
65: * documentation and/or other materials provided with the distribution.
66: *
67: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
68: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
69: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
70: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
71: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
72: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
73: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
74: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
75: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
76: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
77: */
78:
79: #ifndef _SYS_TREE_H_
80: #define _SYS_TREE_H_
81:
82: /*
83: * This file defines data structures for different types of trees:
84: * splay trees and red-black trees.
85: *
86: * A splay tree is a self-organizing data structure. Every operation
87: * on the tree causes a splay to happen. The splay moves the requested
88: * node to the root of the tree and partly rebalances it.
89: *
90: * This has the benefit that request locality causes faster lookups as
91: * the requested nodes move to the top of the tree. On the other hand,
92: * every lookup causes memory writes.
93: *
94: * The Balance Theorem bounds the total access time for m operations
95: * and n inserts on an initially empty tree as O((m + n)lg n). The
96: * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
97: *
98: * A red-black tree is a binary search tree with the node color as an
99: * extra attribute. It fulfills a set of conditions:
100: * - every search path from the root to a leaf consists of the
101: * same number of black nodes,
102: * - each red node (except for the root) has a black parent,
103: * - each leaf node is black.
104: *
105: * Every operation on a red-black tree is bounded as O(lg n).
106: * The maximum height of a red-black tree is 2lg (n+1).
107: */
108:
109: #define SPLAY_HEAD(name, type) \
110: struct name { \
111: struct type *sph_root; /* root of the tree */ \
112: }
113:
114: #define SPLAY_INITIALIZER(root) \
115: { NULL }
116:
117: #define SPLAY_INIT(root) do { \
118: (root)->sph_root = NULL; \
119: } while (0)
120:
121: #define SPLAY_ENTRY(type) \
122: struct { \
123: struct type *spe_left; /* left element */ \
124: struct type *spe_right; /* right element */ \
125: }
126:
127: #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
128: #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
129: #define SPLAY_ROOT(head) (head)->sph_root
130: #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
131:
132: /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
133: #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
134: SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
135: SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
136: (head)->sph_root = tmp; \
137: } while (0)
1.3 misho 138:
1.2 misho 139: #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
140: SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
141: SPLAY_LEFT(tmp, field) = (head)->sph_root; \
142: (head)->sph_root = tmp; \
143: } while (0)
144:
145: #define SPLAY_LINKLEFT(head, tmp, field) do { \
146: SPLAY_LEFT(tmp, field) = (head)->sph_root; \
147: tmp = (head)->sph_root; \
148: (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
149: } while (0)
150:
151: #define SPLAY_LINKRIGHT(head, tmp, field) do { \
152: SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
153: tmp = (head)->sph_root; \
154: (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
155: } while (0)
156:
157: #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
158: SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
159: SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
160: SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
161: SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
162: } while (0)
163:
164: /* Generates prototypes and inline functions */
165:
166: #define SPLAY_PROTOTYPE(name, type, field, cmp) \
167: void name##_SPLAY(struct name *, struct type *); \
168: void name##_SPLAY_MINMAX(struct name *, int); \
169: struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
170: struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
171: \
172: /* Finds the node with the same key as elm */ \
173: static __inline struct type * \
174: name##_SPLAY_FIND(struct name *head, struct type *elm) \
175: { \
176: if (SPLAY_EMPTY(head)) \
177: return(NULL); \
178: name##_SPLAY(head, elm); \
179: if ((cmp)(elm, (head)->sph_root) == 0) \
180: return (head->sph_root); \
181: return (NULL); \
182: } \
183: \
184: static __inline struct type * \
185: name##_SPLAY_NEXT(struct name *head, struct type *elm) \
186: { \
187: name##_SPLAY(head, elm); \
188: if (SPLAY_RIGHT(elm, field) != NULL) { \
189: elm = SPLAY_RIGHT(elm, field); \
190: while (SPLAY_LEFT(elm, field) != NULL) { \
191: elm = SPLAY_LEFT(elm, field); \
192: } \
193: } else \
194: elm = NULL; \
195: return (elm); \
196: } \
197: \
198: static __inline struct type * \
199: name##_SPLAY_MIN_MAX(struct name *head, int val) \
200: { \
201: name##_SPLAY_MINMAX(head, val); \
202: return (SPLAY_ROOT(head)); \
203: }
204:
205: /* Main splay operation.
206: * Moves node close to the key of elm to top
207: */
208: #define SPLAY_GENERATE(name, type, field, cmp) \
209: struct type * \
210: name##_SPLAY_INSERT(struct name *head, struct type *elm) \
211: { \
212: if (SPLAY_EMPTY(head)) { \
213: SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
214: } else { \
215: int __comp; \
216: name##_SPLAY(head, elm); \
217: __comp = (cmp)(elm, (head)->sph_root); \
218: if(__comp < 0) { \
219: SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
220: SPLAY_RIGHT(elm, field) = (head)->sph_root; \
221: SPLAY_LEFT((head)->sph_root, field) = NULL; \
222: } else if (__comp > 0) { \
223: SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
224: SPLAY_LEFT(elm, field) = (head)->sph_root; \
225: SPLAY_RIGHT((head)->sph_root, field) = NULL; \
226: } else \
227: return ((head)->sph_root); \
228: } \
229: (head)->sph_root = (elm); \
230: return (NULL); \
231: } \
232: \
233: struct type * \
234: name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
235: { \
236: struct type *__tmp; \
237: if (SPLAY_EMPTY(head)) \
238: return (NULL); \
239: name##_SPLAY(head, elm); \
240: if ((cmp)(elm, (head)->sph_root) == 0) { \
241: if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
242: (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
243: } else { \
244: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
245: (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
246: name##_SPLAY(head, elm); \
247: SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
248: } \
249: return (elm); \
250: } \
251: return (NULL); \
252: } \
253: \
254: void \
255: name##_SPLAY(struct name *head, struct type *elm) \
256: { \
257: struct type __node, *__left, *__right, *__tmp; \
258: int __comp; \
259: \
260: SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
261: __left = __right = &__node; \
262: \
263: while ((__comp = (cmp)(elm, (head)->sph_root))) { \
264: if (__comp < 0) { \
265: __tmp = SPLAY_LEFT((head)->sph_root, field); \
266: if (__tmp == NULL) \
267: break; \
268: if ((cmp)(elm, __tmp) < 0){ \
269: SPLAY_ROTATE_RIGHT(head, __tmp, field); \
270: if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
271: break; \
272: } \
273: SPLAY_LINKLEFT(head, __right, field); \
274: } else if (__comp > 0) { \
275: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
276: if (__tmp == NULL) \
277: break; \
278: if ((cmp)(elm, __tmp) > 0){ \
279: SPLAY_ROTATE_LEFT(head, __tmp, field); \
280: if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
281: break; \
282: } \
283: SPLAY_LINKRIGHT(head, __left, field); \
284: } \
285: } \
286: SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
287: } \
288: \
289: /* Splay with either the minimum or the maximum element \
290: * Used to find minimum or maximum element in tree. \
291: */ \
292: void name##_SPLAY_MINMAX(struct name *head, int __comp) \
293: { \
294: struct type __node, *__left, *__right, *__tmp; \
295: \
296: SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
297: __left = __right = &__node; \
298: \
299: while (1) { \
300: if (__comp < 0) { \
301: __tmp = SPLAY_LEFT((head)->sph_root, field); \
302: if (__tmp == NULL) \
303: break; \
304: if (__comp < 0){ \
305: SPLAY_ROTATE_RIGHT(head, __tmp, field); \
306: if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
307: break; \
308: } \
309: SPLAY_LINKLEFT(head, __right, field); \
310: } else if (__comp > 0) { \
311: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
312: if (__tmp == NULL) \
313: break; \
314: if (__comp > 0) { \
315: SPLAY_ROTATE_LEFT(head, __tmp, field); \
316: if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
317: break; \
318: } \
319: SPLAY_LINKRIGHT(head, __left, field); \
320: } \
321: } \
322: SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
323: }
324:
325: #define SPLAY_NEGINF -1
326: #define SPLAY_INF 1
327:
328: #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
329: #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
330: #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
331: #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
332: #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
333: : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
334: #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
335: : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
336:
337: #define SPLAY_FOREACH(x, name, head) \
338: for ((x) = SPLAY_MIN(name, head); \
339: (x) != NULL; \
340: (x) = SPLAY_NEXT(name, head, x))
341:
1.4 ! misho 342: #define SPLAY_FOREACH_SAFE(x, name, head, y) \
! 343: for ((x) = SPLAY_MIN(name, head); \
! 344: ((x) != NULL) && \
! 345: ((y) = SPLAY_NEXT(name, head, x), (x) != NULL); \
! 346: (x) = (y))
! 347:
! 348:
1.2 misho 349: /* Macros that define a red-black tree */
350: #define RB_HEAD(name, type) \
351: struct name { \
352: struct type *rbh_root; /* root of the tree */ \
353: }
354:
355: #define RB_INITIALIZER(root) \
356: { NULL }
357:
358: #define RB_INIT(root) do { \
359: (root)->rbh_root = NULL; \
360: } while (0)
361:
362: #define RB_BLACK 0
363: #define RB_RED 1
364: #define RB_ENTRY(type) \
365: struct { \
366: struct type *rbe_left; /* left element */ \
367: struct type *rbe_right; /* right element */ \
368: struct type *rbe_parent; /* parent element */ \
369: int rbe_color; /* node color */ \
370: }
371:
372: #define RB_LEFT(elm, field) (elm)->field.rbe_left
373: #define RB_RIGHT(elm, field) (elm)->field.rbe_right
374: #define RB_PARENT(elm, field) (elm)->field.rbe_parent
375: #define RB_COLOR(elm, field) (elm)->field.rbe_color
376: #define RB_ROOT(head) (head)->rbh_root
377: #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
378:
379: #define RB_SET(elm, parent, field) do { \
380: RB_PARENT(elm, field) = parent; \
381: RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
382: RB_COLOR(elm, field) = RB_RED; \
383: } while (0)
384:
385: #define RB_SET_BLACKRED(black, red, field) do { \
386: RB_COLOR(black, field) = RB_BLACK; \
387: RB_COLOR(red, field) = RB_RED; \
388: } while (0)
389:
390: #ifndef RB_AUGMENT
1.3 misho 391: #define RB_AUGMENT(x) (void)(x)
1.2 misho 392: #endif
393:
394: #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
395: (tmp) = RB_RIGHT(elm, field); \
396: if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
397: RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
398: } \
399: RB_AUGMENT(elm); \
400: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
401: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
402: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
403: else \
404: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
405: } else \
406: (head)->rbh_root = (tmp); \
407: RB_LEFT(tmp, field) = (elm); \
408: RB_PARENT(elm, field) = (tmp); \
409: RB_AUGMENT(tmp); \
410: if ((RB_PARENT(tmp, field))) \
411: RB_AUGMENT(RB_PARENT(tmp, field)); \
412: } while (0)
413:
414: #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
415: (tmp) = RB_LEFT(elm, field); \
416: if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
417: RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
418: } \
419: RB_AUGMENT(elm); \
420: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
421: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
422: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
423: else \
424: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
425: } else \
426: (head)->rbh_root = (tmp); \
427: RB_RIGHT(tmp, field) = (elm); \
428: RB_PARENT(elm, field) = (tmp); \
429: RB_AUGMENT(tmp); \
430: if ((RB_PARENT(tmp, field))) \
431: RB_AUGMENT(RB_PARENT(tmp, field)); \
432: } while (0)
433:
434: /* Generates prototypes and inline functions */
1.3 misho 435: #define RB_PROTOTYPE(name, type, field, cmp) \
1.2 misho 436: RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
437: #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
438: RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
439: #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
440: attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
441: attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
442: attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
443: attr struct type *name##_RB_INSERT(struct name *, struct type *); \
444: attr struct type *name##_RB_FIND(struct name *, struct type *); \
445: attr struct type *name##_RB_NFIND(struct name *, struct type *); \
446: attr struct type *name##_RB_NEXT(struct type *); \
447: attr struct type *name##_RB_PREV(struct type *); \
448: attr struct type *name##_RB_MINMAX(struct name *, int); \
449: \
450:
451: /* Main rb operation.
452: * Moves node close to the key of elm to top
453: */
454: #define RB_GENERATE(name, type, field, cmp) \
455: RB_GENERATE_INTERNAL(name, type, field, cmp,)
456: #define RB_GENERATE_STATIC(name, type, field, cmp) \
457: RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
458: #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
459: attr void \
460: name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
461: { \
462: struct type *parent, *gparent, *tmp; \
463: while ((parent = RB_PARENT(elm, field)) && \
464: RB_COLOR(parent, field) == RB_RED) { \
465: gparent = RB_PARENT(parent, field); \
466: if (parent == RB_LEFT(gparent, field)) { \
467: tmp = RB_RIGHT(gparent, field); \
468: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
469: RB_COLOR(tmp, field) = RB_BLACK; \
470: RB_SET_BLACKRED(parent, gparent, field);\
471: elm = gparent; \
472: continue; \
473: } \
474: if (RB_RIGHT(parent, field) == elm) { \
475: RB_ROTATE_LEFT(head, parent, tmp, field);\
476: tmp = parent; \
477: parent = elm; \
478: elm = tmp; \
479: } \
480: RB_SET_BLACKRED(parent, gparent, field); \
481: RB_ROTATE_RIGHT(head, gparent, tmp, field); \
482: } else { \
483: tmp = RB_LEFT(gparent, field); \
484: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
485: RB_COLOR(tmp, field) = RB_BLACK; \
486: RB_SET_BLACKRED(parent, gparent, field);\
487: elm = gparent; \
488: continue; \
489: } \
490: if (RB_LEFT(parent, field) == elm) { \
491: RB_ROTATE_RIGHT(head, parent, tmp, field);\
492: tmp = parent; \
493: parent = elm; \
494: elm = tmp; \
495: } \
496: RB_SET_BLACKRED(parent, gparent, field); \
497: RB_ROTATE_LEFT(head, gparent, tmp, field); \
498: } \
499: } \
500: RB_COLOR(head->rbh_root, field) = RB_BLACK; \
501: } \
502: \
503: attr void \
504: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
505: { \
506: struct type *tmp; \
507: while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
508: elm != RB_ROOT(head)) { \
509: if (RB_LEFT(parent, field) == elm) { \
510: tmp = RB_RIGHT(parent, field); \
511: if (RB_COLOR(tmp, field) == RB_RED) { \
512: RB_SET_BLACKRED(tmp, parent, field); \
513: RB_ROTATE_LEFT(head, parent, tmp, field);\
514: tmp = RB_RIGHT(parent, field); \
515: } \
516: if ((RB_LEFT(tmp, field) == NULL || \
517: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
518: (RB_RIGHT(tmp, field) == NULL || \
519: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
520: RB_COLOR(tmp, field) = RB_RED; \
521: elm = parent; \
522: parent = RB_PARENT(elm, field); \
523: } else { \
524: if (RB_RIGHT(tmp, field) == NULL || \
525: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
526: struct type *oleft; \
1.3 misho 527: if ((oleft = RB_LEFT(tmp, field))) \
1.2 misho 528: RB_COLOR(oleft, field) = RB_BLACK;\
529: RB_COLOR(tmp, field) = RB_RED; \
530: RB_ROTATE_RIGHT(head, tmp, oleft, field);\
531: tmp = RB_RIGHT(parent, field); \
532: } \
533: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
534: RB_COLOR(parent, field) = RB_BLACK; \
535: if (RB_RIGHT(tmp, field)) \
536: RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
537: RB_ROTATE_LEFT(head, parent, tmp, field);\
538: elm = RB_ROOT(head); \
539: break; \
540: } \
541: } else { \
542: tmp = RB_LEFT(parent, field); \
543: if (RB_COLOR(tmp, field) == RB_RED) { \
544: RB_SET_BLACKRED(tmp, parent, field); \
545: RB_ROTATE_RIGHT(head, parent, tmp, field);\
546: tmp = RB_LEFT(parent, field); \
547: } \
548: if ((RB_LEFT(tmp, field) == NULL || \
549: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
550: (RB_RIGHT(tmp, field) == NULL || \
551: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
552: RB_COLOR(tmp, field) = RB_RED; \
553: elm = parent; \
554: parent = RB_PARENT(elm, field); \
555: } else { \
556: if (RB_LEFT(tmp, field) == NULL || \
557: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
558: struct type *oright; \
1.3 misho 559: if ((oright = RB_RIGHT(tmp, field))) \
1.2 misho 560: RB_COLOR(oright, field) = RB_BLACK;\
561: RB_COLOR(tmp, field) = RB_RED; \
562: RB_ROTATE_LEFT(head, tmp, oright, field);\
563: tmp = RB_LEFT(parent, field); \
564: } \
565: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
566: RB_COLOR(parent, field) = RB_BLACK; \
567: if (RB_LEFT(tmp, field)) \
568: RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
569: RB_ROTATE_RIGHT(head, parent, tmp, field);\
570: elm = RB_ROOT(head); \
571: break; \
572: } \
573: } \
574: } \
575: if (elm) \
576: RB_COLOR(elm, field) = RB_BLACK; \
577: } \
578: \
579: attr struct type * \
580: name##_RB_REMOVE(struct name *head, struct type *elm) \
581: { \
582: struct type *child, *parent, *old = elm; \
583: int color; \
584: if (RB_LEFT(elm, field) == NULL) \
585: child = RB_RIGHT(elm, field); \
586: else if (RB_RIGHT(elm, field) == NULL) \
587: child = RB_LEFT(elm, field); \
588: else { \
589: struct type *left; \
590: elm = RB_RIGHT(elm, field); \
591: while ((left = RB_LEFT(elm, field))) \
592: elm = left; \
593: child = RB_RIGHT(elm, field); \
594: parent = RB_PARENT(elm, field); \
595: color = RB_COLOR(elm, field); \
596: if (child) \
597: RB_PARENT(child, field) = parent; \
598: if (parent) { \
599: if (RB_LEFT(parent, field) == elm) \
600: RB_LEFT(parent, field) = child; \
601: else \
602: RB_RIGHT(parent, field) = child; \
603: RB_AUGMENT(parent); \
604: } else \
605: RB_ROOT(head) = child; \
606: if (RB_PARENT(elm, field) == old) \
607: parent = elm; \
608: (elm)->field = (old)->field; \
609: if (RB_PARENT(old, field)) { \
610: if (RB_LEFT(RB_PARENT(old, field), field) == old)\
611: RB_LEFT(RB_PARENT(old, field), field) = elm;\
612: else \
613: RB_RIGHT(RB_PARENT(old, field), field) = elm;\
614: RB_AUGMENT(RB_PARENT(old, field)); \
615: } else \
616: RB_ROOT(head) = elm; \
617: RB_PARENT(RB_LEFT(old, field), field) = elm; \
618: if (RB_RIGHT(old, field)) \
619: RB_PARENT(RB_RIGHT(old, field), field) = elm; \
620: if (parent) { \
621: left = parent; \
622: do { \
623: RB_AUGMENT(left); \
624: } while ((left = RB_PARENT(left, field))); \
625: } \
626: goto color; \
627: } \
628: parent = RB_PARENT(elm, field); \
629: color = RB_COLOR(elm, field); \
630: if (child) \
631: RB_PARENT(child, field) = parent; \
632: if (parent) { \
633: if (RB_LEFT(parent, field) == elm) \
634: RB_LEFT(parent, field) = child; \
635: else \
636: RB_RIGHT(parent, field) = child; \
637: RB_AUGMENT(parent); \
638: } else \
639: RB_ROOT(head) = child; \
640: color: \
641: if (color == RB_BLACK) \
642: name##_RB_REMOVE_COLOR(head, parent, child); \
643: return (old); \
644: } \
645: \
646: /* Inserts a node into the RB tree */ \
647: attr struct type * \
648: name##_RB_INSERT(struct name *head, struct type *elm) \
649: { \
650: struct type *tmp; \
651: struct type *parent = NULL; \
652: int comp = 0; \
653: tmp = RB_ROOT(head); \
654: while (tmp) { \
655: parent = tmp; \
656: comp = (cmp)(elm, parent); \
657: if (comp < 0) \
658: tmp = RB_LEFT(tmp, field); \
659: else if (comp > 0) \
660: tmp = RB_RIGHT(tmp, field); \
661: else \
662: return (tmp); \
663: } \
664: RB_SET(elm, parent, field); \
665: if (parent != NULL) { \
666: if (comp < 0) \
667: RB_LEFT(parent, field) = elm; \
668: else \
669: RB_RIGHT(parent, field) = elm; \
670: RB_AUGMENT(parent); \
671: } else \
672: RB_ROOT(head) = elm; \
673: name##_RB_INSERT_COLOR(head, elm); \
674: return (NULL); \
675: } \
676: \
677: /* Finds the node with the same key as elm */ \
678: attr struct type * \
679: name##_RB_FIND(struct name *head, struct type *elm) \
680: { \
681: struct type *tmp = RB_ROOT(head); \
682: int comp; \
683: while (tmp) { \
684: comp = cmp(elm, tmp); \
685: if (comp < 0) \
686: tmp = RB_LEFT(tmp, field); \
687: else if (comp > 0) \
688: tmp = RB_RIGHT(tmp, field); \
689: else \
690: return (tmp); \
691: } \
692: return (NULL); \
693: } \
694: \
695: /* Finds the first node greater than or equal to the search key */ \
696: attr struct type * \
697: name##_RB_NFIND(struct name *head, struct type *elm) \
698: { \
699: struct type *tmp = RB_ROOT(head); \
700: struct type *res = NULL; \
701: int comp; \
702: while (tmp) { \
703: comp = cmp(elm, tmp); \
704: if (comp < 0) { \
705: res = tmp; \
706: tmp = RB_LEFT(tmp, field); \
707: } \
708: else if (comp > 0) \
709: tmp = RB_RIGHT(tmp, field); \
710: else \
711: return (tmp); \
712: } \
713: return (res); \
714: } \
715: \
716: /* ARGSUSED */ \
717: attr struct type * \
718: name##_RB_NEXT(struct type *elm) \
719: { \
720: if (RB_RIGHT(elm, field)) { \
721: elm = RB_RIGHT(elm, field); \
722: while (RB_LEFT(elm, field)) \
723: elm = RB_LEFT(elm, field); \
724: } else { \
725: if (RB_PARENT(elm, field) && \
726: (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
727: elm = RB_PARENT(elm, field); \
728: else { \
729: while (RB_PARENT(elm, field) && \
730: (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
731: elm = RB_PARENT(elm, field); \
732: elm = RB_PARENT(elm, field); \
733: } \
734: } \
735: return (elm); \
736: } \
737: \
738: /* ARGSUSED */ \
739: attr struct type * \
740: name##_RB_PREV(struct type *elm) \
741: { \
742: if (RB_LEFT(elm, field)) { \
743: elm = RB_LEFT(elm, field); \
744: while (RB_RIGHT(elm, field)) \
745: elm = RB_RIGHT(elm, field); \
746: } else { \
747: if (RB_PARENT(elm, field) && \
748: (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
749: elm = RB_PARENT(elm, field); \
750: else { \
751: while (RB_PARENT(elm, field) && \
752: (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
753: elm = RB_PARENT(elm, field); \
754: elm = RB_PARENT(elm, field); \
755: } \
756: } \
757: return (elm); \
758: } \
759: \
760: attr struct type * \
761: name##_RB_MINMAX(struct name *head, int val) \
762: { \
763: struct type *tmp = RB_ROOT(head); \
764: struct type *parent = NULL; \
765: while (tmp) { \
766: parent = tmp; \
767: if (val < 0) \
768: tmp = RB_LEFT(tmp, field); \
769: else \
770: tmp = RB_RIGHT(tmp, field); \
771: } \
772: return (parent); \
773: }
774:
775: #define RB_NEGINF -1
776: #define RB_INF 1
777:
778: #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
779: #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
780: #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
781: #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
782: #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
783: #define RB_PREV(name, x, y) name##_RB_PREV(y)
784: #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
785: #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
786:
787: #define RB_FOREACH(x, name, head) \
788: for ((x) = RB_MIN(name, head); \
789: (x) != NULL; \
790: (x) = name##_RB_NEXT(x))
791:
792: #define RB_FOREACH_FROM(x, name, y) \
793: for ((x) = (y); \
794: ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
795: (x) = (y))
796:
797: #define RB_FOREACH_SAFE(x, name, head, y) \
798: for ((x) = RB_MIN(name, head); \
799: ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
800: (x) = (y))
801:
802: #define RB_FOREACH_REVERSE(x, name, head) \
803: for ((x) = RB_MAX(name, head); \
804: (x) != NULL; \
805: (x) = name##_RB_PREV(x))
806:
807: #define RB_FOREACH_REVERSE_FROM(x, name, y) \
808: for ((x) = (y); \
809: ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
810: (x) = (y))
811:
812: #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
813: for ((x) = RB_MAX(name, head); \
814: ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
815: (x) = (y))
816:
817: /* Macros that define a avl tree */
1.4 ! misho 818: #ifndef AVL_MAX_HEIGHT
! 819: #define AVL_MAX_HEIGHT 32
! 820: #endif
1.2 misho 821: #define AVL_HEAD(name, type) \
822: struct name { \
1.4 ! misho 823: struct type *avlh_root; /* root of the tree */ \
1.2 misho 824: }
825:
826: #define AVL_INITIALIZER(root) \
1.4 ! misho 827: { NULL }
1.2 misho 828:
1.4 ! misho 829: #define AVL_INIT(root) do { \
1.2 misho 830: (root)->avlh_root = NULL; \
831: } while (0)
832:
833: #define AVL_ENTRY(type) \
834: struct { \
1.4 ! misho 835: struct type *avle_left; /* left element */ \
! 836: struct type *avle_right; /* right element */ \
! 837: int avle_height; /* node height */ \
1.2 misho 838: }
839:
840: #define AVL_LEFT(elm, field) (elm)->field.avle_left
841: #define AVL_RIGHT(elm, field) (elm)->field.avle_right
842: #define AVL_HEIGHT(elm, field) (elm)->field.avle_height
843: #define AVL_ROOT(head) (head)->avlh_root
844: #define AVL_EMPTY(head) (AVL_ROOT(head) == NULL)
845:
846: /* Generates prototypes and inline functions */
847: #define AVL_PROTOTYPE(name, type, field, cmp) \
848: AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
849: #define AVL_PROTOTYPE_STATIC(name, type, field, cmp) \
850: AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
851: #define AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
852: attr struct type *name##_AVL_REMOVE(struct name *, struct type *); \
853: attr struct type *name##_AVL_INSERT(struct name *, struct type *); \
854: attr struct type *name##_AVL_FIND(struct name *, struct type *); \
855: attr struct type *name##_AVL_NFIND(struct name *, struct type *); \
856: attr struct type *name##_AVL_NEXT(struct name *, struct type *); \
857: attr struct type *name##_AVL_PREV(struct name *, struct type *); \
858: attr struct type *name##_AVL_MIN(struct name *); \
859: attr struct type *name##_AVL_MAX(struct name *);
860:
861: #define AVL_ROTATE_LEFT(parent, elm, type, field) do { \
862: struct type *_rl = AVL_LEFT(elm, field); \
863: struct type *_rr = AVL_RIGHT(elm, field); \
864: int _l = !_rl ? 0 : AVL_HEIGHT(_rl, field); \
865: \
866: if (_rr && AVL_HEIGHT(_rr, field) >= _l) { \
867: AVL_RIGHT(*parent, field) = _rl; \
868: AVL_HEIGHT(*parent, field) = _l + 1; \
869: AVL_LEFT(elm, field) = (*parent); \
870: AVL_HEIGHT(elm, field) = _l + 2; \
871: (*parent) = (elm); \
872: } else { \
873: AVL_RIGHT(*parent, field) = AVL_LEFT(_rl, field); \
874: AVL_HEIGHT(*parent, field) = _l; \
875: AVL_LEFT(elm, field) = AVL_RIGHT(_rl, field); \
876: AVL_HEIGHT(elm, field) = _l; \
877: AVL_LEFT(_rl, field) = (*parent); \
878: AVL_RIGHT(_rl, field) = (elm); \
879: AVL_HEIGHT(_rl, field) = _l + 1; \
880: (*parent) = _rl; \
881: } \
882: } while (0)
883:
884: #define AVL_ROTATE_RIGHT(parent, elm, type, field) do { \
885: struct type *_ll = AVL_LEFT(elm, field); \
886: struct type *_lr = AVL_RIGHT(elm, field); \
887: int _r = !_lr ? 0 : AVL_HEIGHT(_lr, field); \
888: \
889: if (_ll && AVL_HEIGHT(_ll, field) >= _r) { \
890: AVL_LEFT(*(parent), field) = _lr; \
891: AVL_HEIGHT(*(parent), field) = _r + 1; \
892: AVL_RIGHT(elm, field) = *parent; \
893: AVL_HEIGHT(elm, field) = _r + 2; \
894: *(parent) = (elm); \
895: } else { \
896: AVL_RIGHT(elm, field) = AVL_LEFT(_lr, field); \
897: AVL_HEIGHT(elm, field) = _r; \
898: AVL_LEFT(*parent, field) = AVL_RIGHT(_lr, field); \
899: AVL_HEIGHT(*parent, field) = _r; \
900: AVL_LEFT(_lr, field) = (elm); \
901: AVL_RIGHT(_lr, field) = (*parent); \
902: AVL_HEIGHT(_lr, field) = _r + 1; \
903: (*parent) = _lr; \
904: } \
905: } while (0)
906:
907: #define AVL_REBALANCE(_anc, type, field, count) while (count-- > 0) { \
908: int _lh, _rh; \
909: struct type *_el = NULL; \
910: \
911: _lh = !AVL_LEFT(*_anc[count], field) ? 0 : \
912: AVL_HEIGHT(AVL_LEFT(*_anc[count], field), field); \
913: _rh = !AVL_RIGHT(*_anc[count], field) ? 0 : \
914: AVL_HEIGHT(AVL_RIGHT(*_anc[count], field), field); \
915: \
916: if (_rh - _lh < -1) { \
917: _el = AVL_LEFT(*_anc[count], field); \
918: AVL_ROTATE_RIGHT(_anc[count], _el, type, field); \
919: } else if (_rh - _lh > 1) { \
920: _el = AVL_RIGHT(*_anc[count], field); \
921: AVL_ROTATE_LEFT(_anc[count], _el, type, field); \
922: } else if (AVL_HEIGHT(*_anc[count], field) != ((_rh > _lh) ? _rh : _lh) + 1) \
923: AVL_HEIGHT(*_anc[count], field) = ((_rh > _lh) ? _rh : _lh) + 1; \
924: else \
925: break; \
926: }
927:
928: /* Main avl operation.
929: * Moves node close to the key of elm to top
930: */
931: #define AVL_GENERATE(name, type, field, cmp) \
932: AVL_GENERATE_INTERNAL(name, type, field, cmp,)
933: #define AVL_GENERATE_STATIC(name, type, field, cmp) \
934: AVL_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
935: #define AVL_GENERATE_INTERNAL(name, type, field, cmp, attr) \
936: attr struct type * \
937: name##_AVL_MIN(struct name *head) \
938: { \
939: struct type *t = AVL_ROOT(head); \
940: \
941: while (t && AVL_LEFT(t, field)) \
942: t = AVL_LEFT(t, field); \
943: return (t); \
944: } \
945: \
946: attr struct type * \
947: name##_AVL_MAX(struct name *head) \
948: { \
949: struct type *t = AVL_ROOT(head); \
950: \
951: while (t && AVL_RIGHT(t, field)) \
952: t = AVL_RIGHT(t, field); \
953: return (t); \
954: } \
955: \
956: /* Finds the node with the same key as elm */ \
957: attr struct type * \
958: name##_AVL_FIND(struct name *head, struct type *elm) \
959: { \
960: struct type *t = AVL_ROOT(head); \
961: int comp; \
962: while (t) { \
963: comp = cmp(t, elm); \
964: if (!comp) \
965: return (t); \
966: else if (comp < 0) \
967: t = AVL_LEFT(t, field); \
968: else \
969: t = AVL_RIGHT(t, field); \
970: } \
971: return (NULL); \
972: } \
973: \
974: /* Finds the first node less than or equal to the search key */ \
975: attr struct type * \
976: name##_AVL_NFIND(struct name *head, struct type *elm) \
977: { \
978: struct type *t = AVL_ROOT(head); \
979: struct type *res = NULL; \
980: int comp; \
981: while (t) { \
982: comp = cmp(t, elm); \
983: if (!comp) \
984: return (t); \
985: else if (comp < 0) { \
986: res = t; \
987: t = AVL_LEFT(t, field); \
988: } else \
989: t = AVL_RIGHT(t, field); \
990: } \
991: return (res); \
992: } \
993: \
994: /* ARGSUSED */ \
995: attr struct type * \
996: name##_AVL_NEXT(struct name *head, struct type *elm) \
997: { \
998: struct type *t = AVL_ROOT(head); \
999: struct type *res = NULL; \
1000: int comp; \
1001: while (t) { \
1002: comp = cmp(t, elm); \
1003: if (comp < 0) { \
1004: res = t; \
1005: t = AVL_LEFT(t, field); \
1006: } else \
1007: t = AVL_RIGHT(t, field); \
1008: } \
1009: return (res); \
1010: } \
1011: \
1012: /* ARGSUSED */ \
1013: attr struct type * \
1014: name##_AVL_PREV(struct name *head, struct type *elm) \
1015: { \
1016: struct type *t = AVL_ROOT(head); \
1017: struct type *res = NULL; \
1018: int comp; \
1019: while (t) { \
1020: comp = cmp(t, elm); \
1021: if (comp > 0) { \
1022: res = t; \
1023: t = AVL_RIGHT(t, field); \
1024: } else \
1025: t = AVL_LEFT(t, field); \
1026: } \
1027: return (res); \
1028: } \
1029: \
1030: /* Inserts a node into the AVL tree */ \
1031: attr struct type * \
1032: name##_AVL_INSERT(struct name *head, struct type *elm) \
1033: { \
1034: struct type *temp, **pt; \
1.4 ! misho 1035: struct type **ancestors[AVL_MAX_HEIGHT] = { 0 }; \
1.2 misho 1036: register int i; \
1037: int comp; \
1038: \
1.4 ! misho 1039: for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT && *pt; i++) { \
1.2 misho 1040: temp = *pt; \
1041: ancestors[i] = pt; \
1042: comp = (cmp)(temp, elm); \
1043: if (!comp) \
1044: return temp; \
1045: else if (comp < 0) \
1046: pt = &AVL_LEFT(temp, field); \
1047: else \
1048: pt = &AVL_RIGHT(temp, field); \
1049: } \
1050: *pt = elm; \
1051: \
1052: AVL_LEFT(elm, field) = AVL_RIGHT(elm, field) = (struct type *) NULL; \
1053: AVL_HEIGHT(elm, field) = 1; \
1054: \
1055: AVL_REBALANCE(ancestors, type, field, i); \
1056: return (NULL); \
1057: } \
1058: \
1059: attr struct type * \
1060: name##_AVL_REMOVE(struct name *head, struct type *elm) \
1061: { \
1062: struct type *temp, *old, **dp, **pt; \
1.4 ! misho 1063: struct type **ancestors[AVL_MAX_HEIGHT] = { 0 }; \
1.2 misho 1064: register int i; \
1065: int comp, delcnt; \
1066: \
1.4 ! misho 1067: for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT; i++) { \
1.2 misho 1068: if (!*pt) \
1069: return (NULL); \
1070: else \
1071: temp = *pt; \
1072: ancestors[i] = pt; \
1073: comp = (cmp)(temp, elm); \
1074: if (!comp) \
1075: break; \
1076: else if (comp < 0) \
1077: pt = &AVL_LEFT(temp, field); \
1078: else \
1079: pt = &AVL_RIGHT(temp, field); \
1080: } \
1081: old = temp; \
1082: \
1083: if (!AVL_LEFT(temp, field)) { \
1084: *pt = AVL_RIGHT(temp, field); \
1085: i--; \
1086: } else { \
1087: delcnt = i; \
1088: dp = pt; \
1.4 ! misho 1089: for (pt = &AVL_LEFT(temp, field); i < AVL_MAX_HEIGHT && \
1.2 misho 1090: AVL_RIGHT(temp, field); i++) { \
1091: temp = *pt; \
1092: ancestors[i] = pt; \
1093: pt = &AVL_RIGHT(temp, field); \
1094: } \
1095: *pt = AVL_LEFT(temp, field); \
1096: \
1097: AVL_LEFT(temp, field) = AVL_LEFT(old, field); \
1098: AVL_RIGHT(temp, field) = AVL_RIGHT(old, field); \
1099: AVL_HEIGHT(temp, field) = AVL_HEIGHT(old, field); \
1100: *dp = temp; \
1101: \
1102: ancestors[delcnt] = &AVL_LEFT(temp, field); \
1103: } \
1104: \
1105: AVL_REBALANCE(ancestors, type, field, i); \
1106: return (old); \
1107: }
1108:
1109: #define AVL_INSERT(name, x, y) name##_AVL_INSERT(x, y)
1110: #define AVL_REMOVE(name, x, y) name##_AVL_REMOVE(x, y)
1111: #define AVL_FIND(name, x, y) name##_AVL_FIND(x, y)
1112: #define AVL_NFIND(name, x, y) name##_AVL_NFIND(x, y)
1113: #define AVL_NEXT(name, x, y) name##_AVL_NEXT(x, y)
1114: #define AVL_PREV(name, x, y) name##_AVL_PREV(x, y)
1115: #define AVL_MIN(name, x) name##_AVL_MIN(x)
1116: #define AVL_MAX(name, x) name##_AVL_MAX(x)
1117:
1118: #define AVL_FOREACH(x, name, head) \
1119: for ((x) = name##_AVL_MIN(head); \
1120: (x) != NULL; \
1121: (x) = name##_AVL_NEXT(head, x))
1122:
1123: #define AVL_FOREACH_REVERSE(x, name, head) \
1124: for ((x) = name##_AVL_MAX(head); \
1125: (x) != NULL; \
1126: (x) = name##_AVL_PREV(head, x))
1127:
1128: #define AVL_FOREACH_SAFE(x, name, head, y) \
1129: for ((x) = name##_AVL_MIN(head); \
1130: (x) && ((y) = name##_AVL_NEXT(head, x), (x)); \
1131: (x) = (y))
1132:
1133: #define AVL_FOREACH_REVERSE_SAFE(x, name, head, y) \
1134: for ((x) = name##_AVL_MAX(head); \
1135: (x) && ((y) = name##_AVL_PREV(head, x), (x)); \
1136: (x) = (y))
1137:
1138:
1139: #endif /* _SYS_TREE_H_ */