libelwix/inc/elwix/atree.h - view

File: [ELWIX - Embedded LightWeight unIX -] / libelwix / inc / elwix / atree.h
Revision 1.5: download - view: text, annotated - select for diffs - revision graph
Mon Jan 22 15:24:28 2024 UTC (9 months, 1 week ago) by misho
Branches: MAIN
CVS tags: elwix6_6, elwix6_5, elwix6_4, elwix6_3, elwix6_2, elwix6_1, elwix5_9, elwix5_12, elwix5_11, elwix5_10, HEAD, ELWIX6_5, ELWIX6_4, ELWIX6_2, ELWIX6_1, ELWIX6_0, ELWIX5_9, ELWIX5_8, ELWIX5_11, ELWIX5_10

Version 5.8

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.5 2024/01/22 15:24:28 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 - 2023 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: long 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: long 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: long 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: long comp; \ 962: \ 963: while (t) { \ 964: comp = cmp(t, elm); \ 965: if (!comp) \ 966: return (t); \ 967: else if (comp < 0) \ 968: t = AVL_LEFT(t, field); \ 969: else \ 970: t = AVL_RIGHT(t, field); \ 971: } \ 972: return (NULL); \ 973: } \ 974: \ 975: /* Finds the first node less than or equal to the search key */ \ 976: attr struct type * \ 977: name##_AVL_NFIND(struct name *head, struct type *elm) \ 978: { \ 979: struct type *t = AVL_ROOT(head); \ 980: struct type *res = NULL; \ 981: long comp; \ 982: \ 983: while (t) { \ 984: comp = cmp(t, elm); \ 985: if (!comp) \ 986: return (t); \ 987: else if (comp < 0) { \ 988: res = t; \ 989: t = AVL_LEFT(t, field); \ 990: } else \ 991: t = AVL_RIGHT(t, field); \ 992: } \ 993: return (res); \ 994: } \ 995: \ 996: /* ARGSUSED */ \ 997: attr struct type * \ 998: name##_AVL_NEXT(struct name *head, struct type *elm) \ 999: { \ 1000: struct type *t = AVL_ROOT(head); \ 1001: struct type *res = NULL; \ 1002: long comp; \ 1003: \ 1004: while (t) { \ 1005: comp = cmp(t, elm); \ 1006: if (comp < 0) { \ 1007: res = t; \ 1008: t = AVL_LEFT(t, field); \ 1009: } else \ 1010: t = AVL_RIGHT(t, field); \ 1011: } \ 1012: return (res); \ 1013: } \ 1014: \ 1015: /* ARGSUSED */ \ 1016: attr struct type * \ 1017: name##_AVL_PREV(struct name *head, struct type *elm) \ 1018: { \ 1019: struct type *t = AVL_ROOT(head); \ 1020: struct type *res = NULL; \ 1021: long comp; \ 1022: \ 1023: while (t) { \ 1024: comp = cmp(t, elm); \ 1025: if (comp > 0) { \ 1026: res = t; \ 1027: t = AVL_RIGHT(t, field); \ 1028: } else \ 1029: t = AVL_LEFT(t, field); \ 1030: } \ 1031: return (res); \ 1032: } \ 1033: \ 1034: /* Inserts a node into the AVL tree */ \ 1035: attr struct type * \ 1036: name##_AVL_INSERT(struct name *head, struct type *elm) \ 1037: { \ 1038: struct type *temp, **pt; \ 1039: struct type **ancestors[AVL_MAX_HEIGHT] = { 0 }; \ 1040: register int i; \ 1041: long comp; \ 1042: \ 1043: for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT && *pt; i++) { \ 1044: temp = *pt; \ 1045: ancestors[i] = pt; \ 1046: comp = (cmp)(temp, elm); \ 1047: if (!comp) \ 1048: return temp; \ 1049: else if (comp < 0) \ 1050: pt = &AVL_LEFT(temp, field); \ 1051: else \ 1052: pt = &AVL_RIGHT(temp, field); \ 1053: } \ 1054: *pt = elm; \ 1055: \ 1056: AVL_LEFT(elm, field) = AVL_RIGHT(elm, field) = (struct type *) NULL; \ 1057: AVL_HEIGHT(elm, field) = 1; \ 1058: \ 1059: AVL_REBALANCE(ancestors, type, field, i); \ 1060: return (NULL); \ 1061: } \ 1062: \ 1063: attr struct type * \ 1064: name##_AVL_REMOVE(struct name *head, struct type *elm) \ 1065: { \ 1066: struct type *temp, *old, **dp, **pt; \ 1067: struct type **ancestors[AVL_MAX_HEIGHT] = { 0 }; \ 1068: register int i; \ 1069: int delcnt; \ 1070: long comp; \ 1071: \ 1072: for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT; i++) { \ 1073: if (!*pt) \ 1074: return (NULL); \ 1075: else \ 1076: temp = *pt; \ 1077: ancestors[i] = pt; \ 1078: comp = (cmp)(temp, elm); \ 1079: if (!comp) \ 1080: break; \ 1081: else if (comp < 0) \ 1082: pt = &AVL_LEFT(temp, field); \ 1083: else \ 1084: pt = &AVL_RIGHT(temp, field); \ 1085: } \ 1086: old = temp; \ 1087: \ 1088: if (!AVL_LEFT(temp, field)) { \ 1089: *pt = AVL_RIGHT(temp, field); \ 1090: i--; \ 1091: } else { \ 1092: delcnt = i; \ 1093: dp = pt; \ 1094: for (pt = &AVL_LEFT(temp, field); i < AVL_MAX_HEIGHT && \ 1095: AVL_RIGHT(temp, field); i++) { \ 1096: temp = *pt; \ 1097: ancestors[i] = pt; \ 1098: pt = &AVL_RIGHT(temp, field); \ 1099: } \ 1100: *pt = AVL_LEFT(temp, field); \ 1101: \ 1102: AVL_LEFT(temp, field) = AVL_LEFT(old, field); \ 1103: AVL_RIGHT(temp, field) = AVL_RIGHT(old, field); \ 1104: AVL_HEIGHT(temp, field) = AVL_HEIGHT(old, field); \ 1105: *dp = temp; \ 1106: \ 1107: ancestors[delcnt] = &AVL_LEFT(temp, field); \ 1108: } \ 1109: \ 1110: AVL_REBALANCE(ancestors, type, field, i); \ 1111: return (old); \ 1112: } 1113: 1114: #define AVL_INSERT(name, x, y) name##_AVL_INSERT(x, y) 1115: #define AVL_REMOVE(name, x, y) name##_AVL_REMOVE(x, y) 1116: #define AVL_FIND(name, x, y) name##_AVL_FIND(x, y) 1117: #define AVL_NFIND(name, x, y) name##_AVL_NFIND(x, y) 1118: #define AVL_NEXT(name, x, y) name##_AVL_NEXT(x, y) 1119: #define AVL_PREV(name, x, y) name##_AVL_PREV(x, y) 1120: #define AVL_MIN(name, x) name##_AVL_MIN(x) 1121: #define AVL_MAX(name, x) name##_AVL_MAX(x) 1122: 1123: #define AVL_FOREACH(x, name, head) \ 1124: for ((x) = name##_AVL_MIN(head); \ 1125: (x) != NULL; \ 1126: (x) = name##_AVL_NEXT(head, x)) 1127: 1128: #define AVL_FOREACH_REVERSE(x, name, head) \ 1129: for ((x) = name##_AVL_MAX(head); \ 1130: (x) != NULL; \ 1131: (x) = name##_AVL_PREV(head, x)) 1132: 1133: #define AVL_FOREACH_SAFE(x, name, head, y) \ 1134: for ((x) = name##_AVL_MIN(head); \ 1135: (x) && ((y) = name##_AVL_NEXT(head, x), (x)); \ 1136: (x) = (y)) 1137: 1138: #define AVL_FOREACH_REVERSE_SAFE(x, name, head, y) \ 1139: for ((x) = name##_AVL_MAX(head); \ 1140: (x) && ((y) = name##_AVL_PREV(head, x), (x)); \ 1141: (x) = (y)) 1142: 1143: 1144: #endif /* _SYS_TREE_H_ */