Annotation of libaitio/inc/atree.h, revision 1.3.28.1
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.28.1! misho 6: * $Id: atree.h,v 1.3 2011/08/29 12:00:57 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.3.28.1! 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:
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 */
1.3.28.1! misho 811: #ifndef AVL_MAX_HEIGHT
! 812: #define AVL_MAX_HEIGHT 32
! 813: #endif
1.2 misho 814: #define AVL_HEAD(name, type) \
815: struct name { \
1.3.28.1! misho 816: struct type *avlh_root; /* root of the tree */ \
1.2 misho 817: }
818:
819: #define AVL_INITIALIZER(root) \
1.3.28.1! misho 820: { NULL }
1.2 misho 821:
1.3.28.1! misho 822: #define AVL_INIT(root) do { \
1.2 misho 823: (root)->avlh_root = NULL; \
824: } while (0)
825:
826: #define AVL_ENTRY(type) \
827: struct { \
1.3.28.1! misho 828: struct type *avle_left; /* left element */ \
! 829: struct type *avle_right; /* right element */ \
! 830: int avle_height; /* node height */ \
1.2 misho 831: }
832:
833: #define AVL_LEFT(elm, field) (elm)->field.avle_left
834: #define AVL_RIGHT(elm, field) (elm)->field.avle_right
835: #define AVL_HEIGHT(elm, field) (elm)->field.avle_height
836: #define AVL_ROOT(head) (head)->avlh_root
837: #define AVL_EMPTY(head) (AVL_ROOT(head) == NULL)
838:
839: /* Generates prototypes and inline functions */
840: #define AVL_PROTOTYPE(name, type, field, cmp) \
841: AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
842: #define AVL_PROTOTYPE_STATIC(name, type, field, cmp) \
843: AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
844: #define AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
845: attr struct type *name##_AVL_REMOVE(struct name *, struct type *); \
846: attr struct type *name##_AVL_INSERT(struct name *, struct type *); \
847: attr struct type *name##_AVL_FIND(struct name *, struct type *); \
848: attr struct type *name##_AVL_NFIND(struct name *, struct type *); \
849: attr struct type *name##_AVL_NEXT(struct name *, struct type *); \
850: attr struct type *name##_AVL_PREV(struct name *, struct type *); \
851: attr struct type *name##_AVL_MIN(struct name *); \
852: attr struct type *name##_AVL_MAX(struct name *);
853:
854: #define AVL_ROTATE_LEFT(parent, elm, type, field) do { \
855: struct type *_rl = AVL_LEFT(elm, field); \
856: struct type *_rr = AVL_RIGHT(elm, field); \
857: int _l = !_rl ? 0 : AVL_HEIGHT(_rl, field); \
858: \
859: if (_rr && AVL_HEIGHT(_rr, field) >= _l) { \
860: AVL_RIGHT(*parent, field) = _rl; \
861: AVL_HEIGHT(*parent, field) = _l + 1; \
862: AVL_LEFT(elm, field) = (*parent); \
863: AVL_HEIGHT(elm, field) = _l + 2; \
864: (*parent) = (elm); \
865: } else { \
866: AVL_RIGHT(*parent, field) = AVL_LEFT(_rl, field); \
867: AVL_HEIGHT(*parent, field) = _l; \
868: AVL_LEFT(elm, field) = AVL_RIGHT(_rl, field); \
869: AVL_HEIGHT(elm, field) = _l; \
870: AVL_LEFT(_rl, field) = (*parent); \
871: AVL_RIGHT(_rl, field) = (elm); \
872: AVL_HEIGHT(_rl, field) = _l + 1; \
873: (*parent) = _rl; \
874: } \
875: } while (0)
876:
877: #define AVL_ROTATE_RIGHT(parent, elm, type, field) do { \
878: struct type *_ll = AVL_LEFT(elm, field); \
879: struct type *_lr = AVL_RIGHT(elm, field); \
880: int _r = !_lr ? 0 : AVL_HEIGHT(_lr, field); \
881: \
882: if (_ll && AVL_HEIGHT(_ll, field) >= _r) { \
883: AVL_LEFT(*(parent), field) = _lr; \
884: AVL_HEIGHT(*(parent), field) = _r + 1; \
885: AVL_RIGHT(elm, field) = *parent; \
886: AVL_HEIGHT(elm, field) = _r + 2; \
887: *(parent) = (elm); \
888: } else { \
889: AVL_RIGHT(elm, field) = AVL_LEFT(_lr, field); \
890: AVL_HEIGHT(elm, field) = _r; \
891: AVL_LEFT(*parent, field) = AVL_RIGHT(_lr, field); \
892: AVL_HEIGHT(*parent, field) = _r; \
893: AVL_LEFT(_lr, field) = (elm); \
894: AVL_RIGHT(_lr, field) = (*parent); \
895: AVL_HEIGHT(_lr, field) = _r + 1; \
896: (*parent) = _lr; \
897: } \
898: } while (0)
899:
900: #define AVL_REBALANCE(_anc, type, field, count) while (count-- > 0) { \
901: int _lh, _rh; \
902: struct type *_el = NULL; \
903: \
904: _lh = !AVL_LEFT(*_anc[count], field) ? 0 : \
905: AVL_HEIGHT(AVL_LEFT(*_anc[count], field), field); \
906: _rh = !AVL_RIGHT(*_anc[count], field) ? 0 : \
907: AVL_HEIGHT(AVL_RIGHT(*_anc[count], field), field); \
908: \
909: if (_rh - _lh < -1) { \
910: _el = AVL_LEFT(*_anc[count], field); \
911: AVL_ROTATE_RIGHT(_anc[count], _el, type, field); \
912: } else if (_rh - _lh > 1) { \
913: _el = AVL_RIGHT(*_anc[count], field); \
914: AVL_ROTATE_LEFT(_anc[count], _el, type, field); \
915: } else if (AVL_HEIGHT(*_anc[count], field) != ((_rh > _lh) ? _rh : _lh) + 1) \
916: AVL_HEIGHT(*_anc[count], field) = ((_rh > _lh) ? _rh : _lh) + 1; \
917: else \
918: break; \
919: }
920:
921: /* Main avl operation.
922: * Moves node close to the key of elm to top
923: */
924: #define AVL_GENERATE(name, type, field, cmp) \
925: AVL_GENERATE_INTERNAL(name, type, field, cmp,)
926: #define AVL_GENERATE_STATIC(name, type, field, cmp) \
927: AVL_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
928: #define AVL_GENERATE_INTERNAL(name, type, field, cmp, attr) \
929: attr struct type * \
930: name##_AVL_MIN(struct name *head) \
931: { \
932: struct type *t = AVL_ROOT(head); \
933: \
934: while (t && AVL_LEFT(t, field)) \
935: t = AVL_LEFT(t, field); \
936: return (t); \
937: } \
938: \
939: attr struct type * \
940: name##_AVL_MAX(struct name *head) \
941: { \
942: struct type *t = AVL_ROOT(head); \
943: \
944: while (t && AVL_RIGHT(t, field)) \
945: t = AVL_RIGHT(t, field); \
946: return (t); \
947: } \
948: \
949: /* Finds the node with the same key as elm */ \
950: attr struct type * \
951: name##_AVL_FIND(struct name *head, struct type *elm) \
952: { \
953: struct type *t = AVL_ROOT(head); \
954: int comp; \
955: while (t) { \
956: comp = cmp(t, elm); \
957: if (!comp) \
958: return (t); \
959: else if (comp < 0) \
960: t = AVL_LEFT(t, field); \
961: else \
962: t = AVL_RIGHT(t, field); \
963: } \
964: return (NULL); \
965: } \
966: \
967: /* Finds the first node less than or equal to the search key */ \
968: attr struct type * \
969: name##_AVL_NFIND(struct name *head, struct type *elm) \
970: { \
971: struct type *t = AVL_ROOT(head); \
972: struct type *res = NULL; \
973: int comp; \
974: while (t) { \
975: comp = cmp(t, elm); \
976: if (!comp) \
977: return (t); \
978: else if (comp < 0) { \
979: res = t; \
980: t = AVL_LEFT(t, field); \
981: } else \
982: t = AVL_RIGHT(t, field); \
983: } \
984: return (res); \
985: } \
986: \
987: /* ARGSUSED */ \
988: attr struct type * \
989: name##_AVL_NEXT(struct name *head, struct type *elm) \
990: { \
991: struct type *t = AVL_ROOT(head); \
992: struct type *res = NULL; \
993: int comp; \
994: while (t) { \
995: comp = cmp(t, elm); \
996: if (comp < 0) { \
997: res = t; \
998: t = AVL_LEFT(t, field); \
999: } else \
1000: t = AVL_RIGHT(t, field); \
1001: } \
1002: return (res); \
1003: } \
1004: \
1005: /* ARGSUSED */ \
1006: attr struct type * \
1007: name##_AVL_PREV(struct name *head, struct type *elm) \
1008: { \
1009: struct type *t = AVL_ROOT(head); \
1010: struct type *res = NULL; \
1011: int comp; \
1012: while (t) { \
1013: comp = cmp(t, elm); \
1014: if (comp > 0) { \
1015: res = t; \
1016: t = AVL_RIGHT(t, field); \
1017: } else \
1018: t = AVL_LEFT(t, field); \
1019: } \
1020: return (res); \
1021: } \
1022: \
1023: /* Inserts a node into the AVL tree */ \
1024: attr struct type * \
1025: name##_AVL_INSERT(struct name *head, struct type *elm) \
1026: { \
1027: struct type *temp, **pt; \
1.3.28.1! misho 1028: struct type **ancestors[AVL_MAX_HEIGHT] = { 0 }; \
1.2 misho 1029: register int i; \
1030: int comp; \
1031: \
1.3.28.1! misho 1032: for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT && *pt; i++) { \
1.2 misho 1033: temp = *pt; \
1034: ancestors[i] = pt; \
1035: comp = (cmp)(temp, elm); \
1036: if (!comp) \
1037: return temp; \
1038: else if (comp < 0) \
1039: pt = &AVL_LEFT(temp, field); \
1040: else \
1041: pt = &AVL_RIGHT(temp, field); \
1042: } \
1043: *pt = elm; \
1044: \
1045: AVL_LEFT(elm, field) = AVL_RIGHT(elm, field) = (struct type *) NULL; \
1046: AVL_HEIGHT(elm, field) = 1; \
1047: \
1048: AVL_REBALANCE(ancestors, type, field, i); \
1049: return (NULL); \
1050: } \
1051: \
1052: attr struct type * \
1053: name##_AVL_REMOVE(struct name *head, struct type *elm) \
1054: { \
1055: struct type *temp, *old, **dp, **pt; \
1.3.28.1! misho 1056: struct type **ancestors[AVL_MAX_HEIGHT] = { 0 }; \
1.2 misho 1057: register int i; \
1058: int comp, delcnt; \
1059: \
1.3.28.1! misho 1060: for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT; i++) { \
1.2 misho 1061: if (!*pt) \
1062: return (NULL); \
1063: else \
1064: temp = *pt; \
1065: ancestors[i] = pt; \
1066: comp = (cmp)(temp, elm); \
1067: if (!comp) \
1068: break; \
1069: else if (comp < 0) \
1070: pt = &AVL_LEFT(temp, field); \
1071: else \
1072: pt = &AVL_RIGHT(temp, field); \
1073: } \
1074: old = temp; \
1075: \
1076: if (!AVL_LEFT(temp, field)) { \
1077: *pt = AVL_RIGHT(temp, field); \
1078: i--; \
1079: } else { \
1080: delcnt = i; \
1081: dp = pt; \
1.3.28.1! misho 1082: for (pt = &AVL_LEFT(temp, field); i < AVL_MAX_HEIGHT && \
1.2 misho 1083: AVL_RIGHT(temp, field); i++) { \
1084: temp = *pt; \
1085: ancestors[i] = pt; \
1086: pt = &AVL_RIGHT(temp, field); \
1087: } \
1088: *pt = AVL_LEFT(temp, field); \
1089: \
1090: AVL_LEFT(temp, field) = AVL_LEFT(old, field); \
1091: AVL_RIGHT(temp, field) = AVL_RIGHT(old, field); \
1092: AVL_HEIGHT(temp, field) = AVL_HEIGHT(old, field); \
1093: *dp = temp; \
1094: \
1095: ancestors[delcnt] = &AVL_LEFT(temp, field); \
1096: } \
1097: \
1098: AVL_REBALANCE(ancestors, type, field, i); \
1099: return (old); \
1100: }
1101:
1102: #define AVL_INSERT(name, x, y) name##_AVL_INSERT(x, y)
1103: #define AVL_REMOVE(name, x, y) name##_AVL_REMOVE(x, y)
1104: #define AVL_FIND(name, x, y) name##_AVL_FIND(x, y)
1105: #define AVL_NFIND(name, x, y) name##_AVL_NFIND(x, y)
1106: #define AVL_NEXT(name, x, y) name##_AVL_NEXT(x, y)
1107: #define AVL_PREV(name, x, y) name##_AVL_PREV(x, y)
1108: #define AVL_MIN(name, x) name##_AVL_MIN(x)
1109: #define AVL_MAX(name, x) name##_AVL_MAX(x)
1110:
1111: #define AVL_FOREACH(x, name, head) \
1112: for ((x) = name##_AVL_MIN(head); \
1113: (x) != NULL; \
1114: (x) = name##_AVL_NEXT(head, x))
1115:
1116: #define AVL_FOREACH_REVERSE(x, name, head) \
1117: for ((x) = name##_AVL_MAX(head); \
1118: (x) != NULL; \
1119: (x) = name##_AVL_PREV(head, x))
1120:
1121: #define AVL_FOREACH_SAFE(x, name, head, y) \
1122: for ((x) = name##_AVL_MIN(head); \
1123: (x) && ((y) = name##_AVL_NEXT(head, x), (x)); \
1124: (x) = (y))
1125:
1126: #define AVL_FOREACH_REVERSE_SAFE(x, name, head, y) \
1127: for ((x) = name##_AVL_MAX(head); \
1128: (x) && ((y) = name##_AVL_PREV(head, x), (x)); \
1129: (x) = (y))
1130:
1131:
1132: #endif /* _SYS_TREE_H_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>