![[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.3 ! misho 6: * $Id: atree.h,v 1.2.2.1 2011/06/20 15:05:48 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:
15: Copyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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:
342: /* Macros that define a red-black tree */
343: #define RB_HEAD(name, type) \
344: struct name { \
345: struct type *rbh_root; /* root of the tree */ \
346: }
347:
348: #define RB_INITIALIZER(root) \
349: { NULL }
350:
351: #define RB_INIT(root) do { \
352: (root)->rbh_root = NULL; \
353: } while (0)
354:
355: #define RB_BLACK 0
356: #define RB_RED 1
357: #define RB_ENTRY(type) \
358: struct { \
359: struct type *rbe_left; /* left element */ \
360: struct type *rbe_right; /* right element */ \
361: struct type *rbe_parent; /* parent element */ \
362: int rbe_color; /* node color */ \
363: }
364:
365: #define RB_LEFT(elm, field) (elm)->field.rbe_left
366: #define RB_RIGHT(elm, field) (elm)->field.rbe_right
367: #define RB_PARENT(elm, field) (elm)->field.rbe_parent
368: #define RB_COLOR(elm, field) (elm)->field.rbe_color
369: #define RB_ROOT(head) (head)->rbh_root
370: #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
371:
372: #define RB_SET(elm, parent, field) do { \
373: RB_PARENT(elm, field) = parent; \
374: RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
375: RB_COLOR(elm, field) = RB_RED; \
376: } while (0)
377:
378: #define RB_SET_BLACKRED(black, red, field) do { \
379: RB_COLOR(black, field) = RB_BLACK; \
380: RB_COLOR(red, field) = RB_RED; \
381: } while (0)
382:
383: #ifndef RB_AUGMENT
1.3 ! misho 384: #define RB_AUGMENT(x) (void)(x)
1.2 misho 385: #endif
386:
387: #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
388: (tmp) = RB_RIGHT(elm, field); \
389: if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
390: RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
391: } \
392: RB_AUGMENT(elm); \
393: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
394: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
395: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
396: else \
397: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
398: } else \
399: (head)->rbh_root = (tmp); \
400: RB_LEFT(tmp, field) = (elm); \
401: RB_PARENT(elm, field) = (tmp); \
402: RB_AUGMENT(tmp); \
403: if ((RB_PARENT(tmp, field))) \
404: RB_AUGMENT(RB_PARENT(tmp, field)); \
405: } while (0)
406:
407: #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
408: (tmp) = RB_LEFT(elm, field); \
409: if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
410: RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
411: } \
412: RB_AUGMENT(elm); \
413: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
414: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
415: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
416: else \
417: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
418: } else \
419: (head)->rbh_root = (tmp); \
420: RB_RIGHT(tmp, field) = (elm); \
421: RB_PARENT(elm, field) = (tmp); \
422: RB_AUGMENT(tmp); \
423: if ((RB_PARENT(tmp, field))) \
424: RB_AUGMENT(RB_PARENT(tmp, field)); \
425: } while (0)
426:
427: /* Generates prototypes and inline functions */
1.3 ! misho 428: #define RB_PROTOTYPE(name, type, field, cmp) \
1.2 misho 429: RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
430: #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
431: RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
432: #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
433: attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
434: attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
435: attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
436: attr struct type *name##_RB_INSERT(struct name *, struct type *); \
437: attr struct type *name##_RB_FIND(struct name *, struct type *); \
438: attr struct type *name##_RB_NFIND(struct name *, struct type *); \
439: attr struct type *name##_RB_NEXT(struct type *); \
440: attr struct type *name##_RB_PREV(struct type *); \
441: attr struct type *name##_RB_MINMAX(struct name *, int); \
442: \
443:
444: /* Main rb operation.
445: * Moves node close to the key of elm to top
446: */
447: #define RB_GENERATE(name, type, field, cmp) \
448: RB_GENERATE_INTERNAL(name, type, field, cmp,)
449: #define RB_GENERATE_STATIC(name, type, field, cmp) \
450: RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
451: #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
452: attr void \
453: name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
454: { \
455: struct type *parent, *gparent, *tmp; \
456: while ((parent = RB_PARENT(elm, field)) && \
457: RB_COLOR(parent, field) == RB_RED) { \
458: gparent = RB_PARENT(parent, field); \
459: if (parent == RB_LEFT(gparent, field)) { \
460: tmp = RB_RIGHT(gparent, field); \
461: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
462: RB_COLOR(tmp, field) = RB_BLACK; \
463: RB_SET_BLACKRED(parent, gparent, field);\
464: elm = gparent; \
465: continue; \
466: } \
467: if (RB_RIGHT(parent, field) == elm) { \
468: RB_ROTATE_LEFT(head, parent, tmp, field);\
469: tmp = parent; \
470: parent = elm; \
471: elm = tmp; \
472: } \
473: RB_SET_BLACKRED(parent, gparent, field); \
474: RB_ROTATE_RIGHT(head, gparent, tmp, field); \
475: } else { \
476: tmp = RB_LEFT(gparent, field); \
477: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
478: RB_COLOR(tmp, field) = RB_BLACK; \
479: RB_SET_BLACKRED(parent, gparent, field);\
480: elm = gparent; \
481: continue; \
482: } \
483: if (RB_LEFT(parent, field) == elm) { \
484: RB_ROTATE_RIGHT(head, parent, tmp, field);\
485: tmp = parent; \
486: parent = elm; \
487: elm = tmp; \
488: } \
489: RB_SET_BLACKRED(parent, gparent, field); \
490: RB_ROTATE_LEFT(head, gparent, tmp, field); \
491: } \
492: } \
493: RB_COLOR(head->rbh_root, field) = RB_BLACK; \
494: } \
495: \
496: attr void \
497: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
498: { \
499: struct type *tmp; \
500: while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
501: elm != RB_ROOT(head)) { \
502: if (RB_LEFT(parent, field) == elm) { \
503: tmp = RB_RIGHT(parent, field); \
504: if (RB_COLOR(tmp, field) == RB_RED) { \
505: RB_SET_BLACKRED(tmp, parent, field); \
506: RB_ROTATE_LEFT(head, parent, tmp, field);\
507: tmp = RB_RIGHT(parent, field); \
508: } \
509: if ((RB_LEFT(tmp, field) == NULL || \
510: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
511: (RB_RIGHT(tmp, field) == NULL || \
512: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
513: RB_COLOR(tmp, field) = RB_RED; \
514: elm = parent; \
515: parent = RB_PARENT(elm, field); \
516: } else { \
517: if (RB_RIGHT(tmp, field) == NULL || \
518: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
519: struct type *oleft; \
1.3 ! misho 520: if ((oleft = RB_LEFT(tmp, field))) \
1.2 misho 521: RB_COLOR(oleft, field) = RB_BLACK;\
522: RB_COLOR(tmp, field) = RB_RED; \
523: RB_ROTATE_RIGHT(head, tmp, oleft, field);\
524: tmp = RB_RIGHT(parent, field); \
525: } \
526: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
527: RB_COLOR(parent, field) = RB_BLACK; \
528: if (RB_RIGHT(tmp, field)) \
529: RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
530: RB_ROTATE_LEFT(head, parent, tmp, field);\
531: elm = RB_ROOT(head); \
532: break; \
533: } \
534: } else { \
535: tmp = RB_LEFT(parent, field); \
536: if (RB_COLOR(tmp, field) == RB_RED) { \
537: RB_SET_BLACKRED(tmp, parent, field); \
538: RB_ROTATE_RIGHT(head, parent, tmp, field);\
539: tmp = RB_LEFT(parent, field); \
540: } \
541: if ((RB_LEFT(tmp, field) == NULL || \
542: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
543: (RB_RIGHT(tmp, field) == NULL || \
544: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
545: RB_COLOR(tmp, field) = RB_RED; \
546: elm = parent; \
547: parent = RB_PARENT(elm, field); \
548: } else { \
549: if (RB_LEFT(tmp, field) == NULL || \
550: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
551: struct type *oright; \
1.3 ! misho 552: if ((oright = RB_RIGHT(tmp, field))) \
1.2 misho 553: RB_COLOR(oright, field) = RB_BLACK;\
554: RB_COLOR(tmp, field) = RB_RED; \
555: RB_ROTATE_LEFT(head, tmp, oright, field);\
556: tmp = RB_LEFT(parent, field); \
557: } \
558: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
559: RB_COLOR(parent, field) = RB_BLACK; \
560: if (RB_LEFT(tmp, field)) \
561: RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
562: RB_ROTATE_RIGHT(head, parent, tmp, field);\
563: elm = RB_ROOT(head); \
564: break; \
565: } \
566: } \
567: } \
568: if (elm) \
569: RB_COLOR(elm, field) = RB_BLACK; \
570: } \
571: \
572: attr struct type * \
573: name##_RB_REMOVE(struct name *head, struct type *elm) \
574: { \
575: struct type *child, *parent, *old = elm; \
576: int color; \
577: if (RB_LEFT(elm, field) == NULL) \
578: child = RB_RIGHT(elm, field); \
579: else if (RB_RIGHT(elm, field) == NULL) \
580: child = RB_LEFT(elm, field); \
581: else { \
582: struct type *left; \
583: elm = RB_RIGHT(elm, field); \
584: while ((left = RB_LEFT(elm, field))) \
585: elm = left; \
586: child = RB_RIGHT(elm, field); \
587: parent = RB_PARENT(elm, field); \
588: color = RB_COLOR(elm, field); \
589: if (child) \
590: RB_PARENT(child, field) = parent; \
591: if (parent) { \
592: if (RB_LEFT(parent, field) == elm) \
593: RB_LEFT(parent, field) = child; \
594: else \
595: RB_RIGHT(parent, field) = child; \
596: RB_AUGMENT(parent); \
597: } else \
598: RB_ROOT(head) = child; \
599: if (RB_PARENT(elm, field) == old) \
600: parent = elm; \
601: (elm)->field = (old)->field; \
602: if (RB_PARENT(old, field)) { \
603: if (RB_LEFT(RB_PARENT(old, field), field) == old)\
604: RB_LEFT(RB_PARENT(old, field), field) = elm;\
605: else \
606: RB_RIGHT(RB_PARENT(old, field), field) = elm;\
607: RB_AUGMENT(RB_PARENT(old, field)); \
608: } else \
609: RB_ROOT(head) = elm; \
610: RB_PARENT(RB_LEFT(old, field), field) = elm; \
611: if (RB_RIGHT(old, field)) \
612: RB_PARENT(RB_RIGHT(old, field), field) = elm; \
613: if (parent) { \
614: left = parent; \
615: do { \
616: RB_AUGMENT(left); \
617: } while ((left = RB_PARENT(left, field))); \
618: } \
619: goto color; \
620: } \
621: parent = RB_PARENT(elm, field); \
622: color = RB_COLOR(elm, field); \
623: if (child) \
624: RB_PARENT(child, field) = parent; \
625: if (parent) { \
626: if (RB_LEFT(parent, field) == elm) \
627: RB_LEFT(parent, field) = child; \
628: else \
629: RB_RIGHT(parent, field) = child; \
630: RB_AUGMENT(parent); \
631: } else \
632: RB_ROOT(head) = child; \
633: color: \
634: if (color == RB_BLACK) \
635: name##_RB_REMOVE_COLOR(head, parent, child); \
636: return (old); \
637: } \
638: \
639: /* Inserts a node into the RB tree */ \
640: attr struct type * \
641: name##_RB_INSERT(struct name *head, struct type *elm) \
642: { \
643: struct type *tmp; \
644: struct type *parent = NULL; \
645: int comp = 0; \
646: tmp = RB_ROOT(head); \
647: while (tmp) { \
648: parent = tmp; \
649: comp = (cmp)(elm, parent); \
650: if (comp < 0) \
651: tmp = RB_LEFT(tmp, field); \
652: else if (comp > 0) \
653: tmp = RB_RIGHT(tmp, field); \
654: else \
655: return (tmp); \
656: } \
657: RB_SET(elm, parent, field); \
658: if (parent != NULL) { \
659: if (comp < 0) \
660: RB_LEFT(parent, field) = elm; \
661: else \
662: RB_RIGHT(parent, field) = elm; \
663: RB_AUGMENT(parent); \
664: } else \
665: RB_ROOT(head) = elm; \
666: name##_RB_INSERT_COLOR(head, elm); \
667: return (NULL); \
668: } \
669: \
670: /* Finds the node with the same key as elm */ \
671: attr struct type * \
672: name##_RB_FIND(struct name *head, struct type *elm) \
673: { \
674: struct type *tmp = RB_ROOT(head); \
675: int comp; \
676: while (tmp) { \
677: comp = cmp(elm, tmp); \
678: if (comp < 0) \
679: tmp = RB_LEFT(tmp, field); \
680: else if (comp > 0) \
681: tmp = RB_RIGHT(tmp, field); \
682: else \
683: return (tmp); \
684: } \
685: return (NULL); \
686: } \
687: \
688: /* Finds the first node greater than or equal to the search key */ \
689: attr struct type * \
690: name##_RB_NFIND(struct name *head, struct type *elm) \
691: { \
692: struct type *tmp = RB_ROOT(head); \
693: struct type *res = NULL; \
694: int comp; \
695: while (tmp) { \
696: comp = cmp(elm, tmp); \
697: if (comp < 0) { \
698: res = tmp; \
699: tmp = RB_LEFT(tmp, field); \
700: } \
701: else if (comp > 0) \
702: tmp = RB_RIGHT(tmp, field); \
703: else \
704: return (tmp); \
705: } \
706: return (res); \
707: } \
708: \
709: /* ARGSUSED */ \
710: attr struct type * \
711: name##_RB_NEXT(struct type *elm) \
712: { \
713: if (RB_RIGHT(elm, field)) { \
714: elm = RB_RIGHT(elm, field); \
715: while (RB_LEFT(elm, field)) \
716: elm = RB_LEFT(elm, field); \
717: } else { \
718: if (RB_PARENT(elm, field) && \
719: (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
720: elm = RB_PARENT(elm, field); \
721: else { \
722: while (RB_PARENT(elm, field) && \
723: (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
724: elm = RB_PARENT(elm, field); \
725: elm = RB_PARENT(elm, field); \
726: } \
727: } \
728: return (elm); \
729: } \
730: \
731: /* ARGSUSED */ \
732: attr struct type * \
733: name##_RB_PREV(struct type *elm) \
734: { \
735: if (RB_LEFT(elm, field)) { \
736: elm = RB_LEFT(elm, field); \
737: while (RB_RIGHT(elm, field)) \
738: elm = RB_RIGHT(elm, field); \
739: } else { \
740: if (RB_PARENT(elm, field) && \
741: (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
742: elm = RB_PARENT(elm, field); \
743: else { \
744: while (RB_PARENT(elm, field) && \
745: (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
746: elm = RB_PARENT(elm, field); \
747: elm = RB_PARENT(elm, field); \
748: } \
749: } \
750: return (elm); \
751: } \
752: \
753: attr struct type * \
754: name##_RB_MINMAX(struct name *head, int val) \
755: { \
756: struct type *tmp = RB_ROOT(head); \
757: struct type *parent = NULL; \
758: while (tmp) { \
759: parent = tmp; \
760: if (val < 0) \
761: tmp = RB_LEFT(tmp, field); \
762: else \
763: tmp = RB_RIGHT(tmp, field); \
764: } \
765: return (parent); \
766: }
767:
768: #define RB_NEGINF -1
769: #define RB_INF 1
770:
771: #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
772: #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
773: #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
774: #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
775: #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
776: #define RB_PREV(name, x, y) name##_RB_PREV(y)
777: #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
778: #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
779:
780: #define RB_FOREACH(x, name, head) \
781: for ((x) = RB_MIN(name, head); \
782: (x) != NULL; \
783: (x) = name##_RB_NEXT(x))
784:
785: #define RB_FOREACH_FROM(x, name, y) \
786: for ((x) = (y); \
787: ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
788: (x) = (y))
789:
790: #define RB_FOREACH_SAFE(x, name, head, y) \
791: for ((x) = RB_MIN(name, head); \
792: ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
793: (x) = (y))
794:
795: #define RB_FOREACH_REVERSE(x, name, head) \
796: for ((x) = RB_MAX(name, head); \
797: (x) != NULL; \
798: (x) = name##_RB_PREV(x))
799:
800: #define RB_FOREACH_REVERSE_FROM(x, name, y) \
801: for ((x) = (y); \
802: ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
803: (x) = (y))
804:
805: #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
806: for ((x) = RB_MAX(name, head); \
807: ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
808: (x) = (y))
809:
810: /* Macros that define a avl tree */
811: #define AVL_MAX_HEIGHT 42
812: #define AVL_HEAD(name, type) \
813: struct name { \
814: struct type *avlh_root; /* root of the tree */ \
815: int avlh_height; \
816: long avlh_count; \
817: }
818:
819: #define AVL_INITIALIZER(root) \
820: { NULL, 0, 0 }
821:
822: #define AVL_INIT(root, height) do { \
823: (root)->avlh_root = NULL; \
824: (root)->avlh_height = !height ? AVL_MAX_HEIGHT : height; \
825: (root)->avlh_count = 0; \
826: } while (0)
827:
828: #define AVL_ENTRY(type) \
829: struct { \
830: struct type *avle_left; /* left element */ \
831: struct type *avle_right; /* right element */ \
832: int avle_height; /* node color */ \
833: }
834:
835: #define AVL_LEFT(elm, field) (elm)->field.avle_left
836: #define AVL_RIGHT(elm, field) (elm)->field.avle_right
837: #define AVL_HEIGHT(elm, field) (elm)->field.avle_height
838: #define AVL_ROOT(head) (head)->avlh_root
839: #define AVL_EMPTY(head) (AVL_ROOT(head) == NULL)
840: #define AVL_ROOT_HEIGHT(head) (head)->avlh_height
841: #define AVL_ROOT_COUNT(head) (head)->avlh_count
842:
843: /* Generates prototypes and inline functions */
844: #define AVL_PROTOTYPE(name, type, field, cmp) \
845: AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
846: #define AVL_PROTOTYPE_STATIC(name, type, field, cmp) \
847: AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
848: #define AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
849: attr struct type *name##_AVL_REMOVE(struct name *, struct type *); \
850: attr struct type *name##_AVL_INSERT(struct name *, struct type *); \
851: attr struct type *name##_AVL_FIND(struct name *, struct type *); \
852: attr struct type *name##_AVL_NFIND(struct name *, struct type *); \
853: attr struct type *name##_AVL_NEXT(struct name *, struct type *); \
854: attr struct type *name##_AVL_PREV(struct name *, struct type *); \
855: attr struct type *name##_AVL_MIN(struct name *); \
856: attr struct type *name##_AVL_MAX(struct name *);
857:
858: #define AVL_ROTATE_LEFT(parent, elm, type, field) do { \
859: struct type *_rl = AVL_LEFT(elm, field); \
860: struct type *_rr = AVL_RIGHT(elm, field); \
861: int _l = !_rl ? 0 : AVL_HEIGHT(_rl, field); \
862: \
863: if (_rr && AVL_HEIGHT(_rr, field) >= _l) { \
864: AVL_RIGHT(*parent, field) = _rl; \
865: AVL_HEIGHT(*parent, field) = _l + 1; \
866: AVL_LEFT(elm, field) = (*parent); \
867: AVL_HEIGHT(elm, field) = _l + 2; \
868: (*parent) = (elm); \
869: } else { \
870: AVL_RIGHT(*parent, field) = AVL_LEFT(_rl, field); \
871: AVL_HEIGHT(*parent, field) = _l; \
872: AVL_LEFT(elm, field) = AVL_RIGHT(_rl, field); \
873: AVL_HEIGHT(elm, field) = _l; \
874: AVL_LEFT(_rl, field) = (*parent); \
875: AVL_RIGHT(_rl, field) = (elm); \
876: AVL_HEIGHT(_rl, field) = _l + 1; \
877: (*parent) = _rl; \
878: } \
879: } while (0)
880:
881: #define AVL_ROTATE_RIGHT(parent, elm, type, field) do { \
882: struct type *_ll = AVL_LEFT(elm, field); \
883: struct type *_lr = AVL_RIGHT(elm, field); \
884: int _r = !_lr ? 0 : AVL_HEIGHT(_lr, field); \
885: \
886: if (_ll && AVL_HEIGHT(_ll, field) >= _r) { \
887: AVL_LEFT(*(parent), field) = _lr; \
888: AVL_HEIGHT(*(parent), field) = _r + 1; \
889: AVL_RIGHT(elm, field) = *parent; \
890: AVL_HEIGHT(elm, field) = _r + 2; \
891: *(parent) = (elm); \
892: } else { \
893: AVL_RIGHT(elm, field) = AVL_LEFT(_lr, field); \
894: AVL_HEIGHT(elm, field) = _r; \
895: AVL_LEFT(*parent, field) = AVL_RIGHT(_lr, field); \
896: AVL_HEIGHT(*parent, field) = _r; \
897: AVL_LEFT(_lr, field) = (elm); \
898: AVL_RIGHT(_lr, field) = (*parent); \
899: AVL_HEIGHT(_lr, field) = _r + 1; \
900: (*parent) = _lr; \
901: } \
902: } while (0)
903:
904: #define AVL_REBALANCE(_anc, type, field, count) while (count-- > 0) { \
905: int _lh, _rh; \
906: struct type *_el = NULL; \
907: \
908: _lh = !AVL_LEFT(*_anc[count], field) ? 0 : \
909: AVL_HEIGHT(AVL_LEFT(*_anc[count], field), field); \
910: _rh = !AVL_RIGHT(*_anc[count], field) ? 0 : \
911: AVL_HEIGHT(AVL_RIGHT(*_anc[count], field), field); \
912: \
913: if (_rh - _lh < -1) { \
914: _el = AVL_LEFT(*_anc[count], field); \
915: AVL_ROTATE_RIGHT(_anc[count], _el, type, field); \
916: } else if (_rh - _lh > 1) { \
917: _el = AVL_RIGHT(*_anc[count], field); \
918: AVL_ROTATE_LEFT(_anc[count], _el, type, field); \
919: } else if (AVL_HEIGHT(*_anc[count], field) != ((_rh > _lh) ? _rh : _lh) + 1) \
920: AVL_HEIGHT(*_anc[count], field) = ((_rh > _lh) ? _rh : _lh) + 1; \
921: else \
922: break; \
923: }
924:
925: /* Main avl operation.
926: * Moves node close to the key of elm to top
927: */
928: #define AVL_GENERATE(name, type, field, cmp) \
929: AVL_GENERATE_INTERNAL(name, type, field, cmp,)
930: #define AVL_GENERATE_STATIC(name, type, field, cmp) \
931: AVL_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
932: #define AVL_GENERATE_INTERNAL(name, type, field, cmp, attr) \
933: attr struct type * \
934: name##_AVL_MIN(struct name *head) \
935: { \
936: struct type *t = AVL_ROOT(head); \
937: \
938: while (t && AVL_LEFT(t, field)) \
939: t = AVL_LEFT(t, field); \
940: return (t); \
941: } \
942: \
943: attr struct type * \
944: name##_AVL_MAX(struct name *head) \
945: { \
946: struct type *t = AVL_ROOT(head); \
947: \
948: while (t && AVL_RIGHT(t, field)) \
949: t = AVL_RIGHT(t, field); \
950: return (t); \
951: } \
952: \
953: /* Finds the node with the same key as elm */ \
954: attr struct type * \
955: name##_AVL_FIND(struct name *head, struct type *elm) \
956: { \
957: struct type *t = AVL_ROOT(head); \
958: int comp; \
959: while (t) { \
960: comp = cmp(t, elm); \
961: if (!comp) \
962: return (t); \
963: else if (comp < 0) \
964: t = AVL_LEFT(t, field); \
965: else \
966: t = AVL_RIGHT(t, field); \
967: } \
968: return (NULL); \
969: } \
970: \
971: /* Finds the first node less than or equal to the search key */ \
972: attr struct type * \
973: name##_AVL_NFIND(struct name *head, struct type *elm) \
974: { \
975: struct type *t = AVL_ROOT(head); \
976: struct type *res = NULL; \
977: int comp; \
978: while (t) { \
979: comp = cmp(t, elm); \
980: if (!comp) \
981: return (t); \
982: else if (comp < 0) { \
983: res = t; \
984: t = AVL_LEFT(t, field); \
985: } else \
986: t = AVL_RIGHT(t, field); \
987: } \
988: return (res); \
989: } \
990: \
991: /* ARGSUSED */ \
992: attr struct type * \
993: name##_AVL_NEXT(struct name *head, struct type *elm) \
994: { \
995: struct type *t = AVL_ROOT(head); \
996: struct type *res = NULL; \
997: int comp; \
998: while (t) { \
999: comp = cmp(t, elm); \
1000: if (comp < 0) { \
1001: res = t; \
1002: t = AVL_LEFT(t, field); \
1003: } else \
1004: t = AVL_RIGHT(t, field); \
1005: } \
1006: return (res); \
1007: } \
1008: \
1009: /* ARGSUSED */ \
1010: attr struct type * \
1011: name##_AVL_PREV(struct name *head, struct type *elm) \
1012: { \
1013: struct type *t = AVL_ROOT(head); \
1014: struct type *res = NULL; \
1015: int comp; \
1016: while (t) { \
1017: comp = cmp(t, elm); \
1018: if (comp > 0) { \
1019: res = t; \
1020: t = AVL_RIGHT(t, field); \
1021: } else \
1022: t = AVL_LEFT(t, field); \
1023: } \
1024: return (res); \
1025: } \
1026: \
1027: /* Inserts a node into the AVL tree */ \
1028: attr struct type * \
1029: name##_AVL_INSERT(struct name *head, struct type *elm) \
1030: { \
1031: struct type *temp, **pt; \
1032: struct type ***ancestors; \
1033: register int i; \
1034: int comp; \
1035: \
1036: ancestors = (struct type ***) alloca(AVL_ROOT_HEIGHT(head) * sizeof(void*)); \
1037: if (!ancestors) \
1038: return (struct type *) -1; \
1039: else \
1040: memset(ancestors, 0, AVL_ROOT_HEIGHT(head) * sizeof(void*)); \
1041: for (i = 0, pt = &AVL_ROOT(head); i < AVL_ROOT_HEIGHT(head) && *pt; i++) { \
1042: temp = *pt; \
1043: ancestors[i] = pt; \
1044: comp = (cmp)(temp, elm); \
1045: if (!comp) \
1046: return temp; \
1047: else if (comp < 0) \
1048: pt = &AVL_LEFT(temp, field); \
1049: else \
1050: pt = &AVL_RIGHT(temp, field); \
1051: } \
1052: *pt = elm; \
1053: \
1054: AVL_LEFT(elm, field) = AVL_RIGHT(elm, field) = (struct type *) NULL; \
1055: AVL_HEIGHT(elm, field) = 1; \
1056: \
1057: AVL_ROOT_COUNT(head)++; \
1058: AVL_REBALANCE(ancestors, type, field, i); \
1059: return (NULL); \
1060: } \
1061: \
1062: attr struct type * \
1063: name##_AVL_REMOVE(struct name *head, struct type *elm) \
1064: { \
1065: struct type *temp, *old, **dp, **pt; \
1066: struct type ***ancestors; \
1067: register int i; \
1068: int comp, delcnt; \
1069: \
1070: ancestors = (struct type ***) alloca(AVL_ROOT_HEIGHT(head) * sizeof(void*)); \
1071: if (!ancestors) \
1072: return (NULL); \
1073: else \
1074: memset(ancestors, 0, AVL_ROOT_HEIGHT(head) * sizeof(void*)); \
1075: for (i = 0, pt = &AVL_ROOT(head); i < AVL_ROOT_HEIGHT(head); i++) { \
1076: if (!*pt) \
1077: return (NULL); \
1078: else \
1079: temp = *pt; \
1080: ancestors[i] = pt; \
1081: comp = (cmp)(temp, elm); \
1082: if (!comp) \
1083: break; \
1084: else if (comp < 0) \
1085: pt = &AVL_LEFT(temp, field); \
1086: else \
1087: pt = &AVL_RIGHT(temp, field); \
1088: } \
1089: old = temp; \
1090: \
1091: if (!AVL_LEFT(temp, field)) { \
1092: *pt = AVL_RIGHT(temp, field); \
1093: i--; \
1094: } else { \
1095: delcnt = i; \
1096: dp = pt; \
1097: for (pt = &AVL_LEFT(temp, field); i < AVL_ROOT_HEIGHT(head) && \
1098: AVL_RIGHT(temp, field); i++) { \
1099: temp = *pt; \
1100: ancestors[i] = pt; \
1101: pt = &AVL_RIGHT(temp, field); \
1102: } \
1103: *pt = AVL_LEFT(temp, field); \
1104: \
1105: AVL_LEFT(temp, field) = AVL_LEFT(old, field); \
1106: AVL_RIGHT(temp, field) = AVL_RIGHT(old, field); \
1107: AVL_HEIGHT(temp, field) = AVL_HEIGHT(old, field); \
1108: *dp = temp; \
1109: \
1110: ancestors[delcnt] = &AVL_LEFT(temp, field); \
1111: } \
1112: \
1113: AVL_ROOT_COUNT(head)--; \
1114: AVL_REBALANCE(ancestors, type, field, i); \
1115: return (old); \
1116: }
1117:
1118: #define AVL_INSERT(name, x, y) name##_AVL_INSERT(x, y)
1119: #define AVL_REMOVE(name, x, y) name##_AVL_REMOVE(x, y)
1120: #define AVL_FIND(name, x, y) name##_AVL_FIND(x, y)
1121: #define AVL_NFIND(name, x, y) name##_AVL_NFIND(x, y)
1122: #define AVL_NEXT(name, x, y) name##_AVL_NEXT(x, y)
1123: #define AVL_PREV(name, x, y) name##_AVL_PREV(x, y)
1124: #define AVL_MIN(name, x) name##_AVL_MIN(x)
1125: #define AVL_MAX(name, x) name##_AVL_MAX(x)
1126:
1127: #define AVL_FOREACH(x, name, head) \
1128: for ((x) = name##_AVL_MIN(head); \
1129: (x) != NULL; \
1130: (x) = name##_AVL_NEXT(head, x))
1131:
1132: #define AVL_FOREACH_REVERSE(x, name, head) \
1133: for ((x) = name##_AVL_MAX(head); \
1134: (x) != NULL; \
1135: (x) = name##_AVL_PREV(head, x))
1136:
1137: #define AVL_FOREACH_SAFE(x, name, head, y) \
1138: for ((x) = name##_AVL_MIN(head); \
1139: (x) && ((y) = name##_AVL_NEXT(head, x), (x)); \
1140: (x) = (y))
1141:
1142: #define AVL_FOREACH_REVERSE_SAFE(x, name, head, y) \
1143: for ((x) = name##_AVL_MAX(head); \
1144: (x) && ((y) = name##_AVL_PREV(head, x), (x)); \
1145: (x) = (y))
1146:
1147:
1148: #endif /* _SYS_TREE_H_ */