Annotation of libaitio/inc/atree.h, revision 1.2
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 $
! 6: * $Id: atree.h,v 1.1.2.2 2011/06/07 11:18:13 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: /*
! 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)
! 138:
! 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
! 384: #define RB_AUGMENT(x) do {} while (0)
! 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 */
! 428: #define RB_PROTOTYPE(name, type, field, cmp) \
! 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; \
! 520: if ((oleft = RB_LEFT(tmp, field)))\
! 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; \
! 552: if ((oright = RB_RIGHT(tmp, field)))\
! 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_ */
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