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