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