1254219Scy/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2254219Scy/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3254219Scy/* $FreeBSD: src/sys/sys/tree.h,v 1.7 2007/12/28 07:03:26 jasone Exp $ */ 4254219Scy 5254219Scy/*- 6254219Scy * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7254219Scy * All rights reserved. 8254219Scy * 9254219Scy * Redistribution and use in source and binary forms, with or without 10254219Scy * modification, are permitted provided that the following conditions 11254219Scy * are met: 12254219Scy * 1. Redistributions of source code must retain the above copyright 13254219Scy * notice, this list of conditions and the following disclaimer. 14254219Scy * 2. Redistributions in binary form must reproduce the above copyright 15254219Scy * notice, this list of conditions and the following disclaimer in the 16254219Scy * documentation and/or other materials provided with the distribution. 17254219Scy * 18254219Scy * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19254219Scy * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20254219Scy * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21254219Scy * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22254219Scy * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23254219Scy * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24254219Scy * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25254219Scy * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26254219Scy * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27254219Scy * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28254219Scy */ 29254219Scy 30254219Scy#ifndef _SYS_TREE_H_ 31254219Scy#define _SYS_TREE_H_ 32254219Scy 33254219Scy/* 34254219Scy * This file defines data structures for different types of trees: 35254219Scy * splay trees and red-black trees. 36254219Scy * 37254219Scy * A splay tree is a self-organizing data structure. Every operation 38254219Scy * on the tree causes a splay to happen. The splay moves the requested 39254219Scy * node to the root of the tree and partly rebalances it. 40254219Scy * 41254219Scy * This has the benefit that request locality causes faster lookups as 42254219Scy * the requested nodes move to the top of the tree. On the other hand, 43254219Scy * every lookup causes memory writes. 44254219Scy * 45254219Scy * The Balance Theorem bounds the total access time for m operations 46254219Scy * and n inserts on an initially empty tree as O((m + n)lg n). The 47254219Scy * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 48254219Scy * 49254219Scy * A red-black tree is a binary search tree with the node color as an 50254219Scy * extra attribute. It fulfills a set of conditions: 51254219Scy * - every search path from the root to a leaf consists of the 52254219Scy * same number of black nodes, 53254219Scy * - each red node (except for the root) has a black parent, 54254219Scy * - each leaf node is black. 55254219Scy * 56254219Scy * Every operation on a red-black tree is bounded as O(lg n). 57254219Scy * The maximum height of a red-black tree is 2lg (n+1). 58254219Scy */ 59254219Scy 60254219Scy#define SPLAY_HEAD(name, type) \ 61254219Scystruct name { \ 62254219Scy struct type *sph_root; /* root of the tree */ \ 63254219Scy} 64254219Scy 65254219Scy#define SPLAY_INITIALIZER(root) \ 66254219Scy { NULL } 67254219Scy 68254219Scy#define SPLAY_INIT(root) do { \ 69254219Scy (root)->sph_root = NULL; \ 70254219Scy} while (/*CONSTCOND*/ 0) 71254219Scy 72254219Scy#define SPLAY_ENTRY(type) \ 73254219Scystruct { \ 74254219Scy struct type *spe_left; /* left element */ \ 75254219Scy struct type *spe_right; /* right element */ \ 76254219Scy} 77254219Scy 78254219Scy#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 79254219Scy#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 80254219Scy#define SPLAY_ROOT(head) (head)->sph_root 81254219Scy#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 82254219Scy 83254219Scy/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 84254219Scy#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 85254219Scy SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 86254219Scy SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 87254219Scy (head)->sph_root = tmp; \ 88254219Scy} while (/*CONSTCOND*/ 0) 89254219Scy 90254219Scy#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 91254219Scy SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 92254219Scy SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 93254219Scy (head)->sph_root = tmp; \ 94254219Scy} while (/*CONSTCOND*/ 0) 95254219Scy 96254219Scy#define SPLAY_LINKLEFT(head, tmp, field) do { \ 97254219Scy SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 98254219Scy tmp = (head)->sph_root; \ 99254219Scy (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 100254219Scy} while (/*CONSTCOND*/ 0) 101254219Scy 102254219Scy#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 103254219Scy SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 104254219Scy tmp = (head)->sph_root; \ 105254219Scy (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 106254219Scy} while (/*CONSTCOND*/ 0) 107254219Scy 108254219Scy#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 109254219Scy SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 110254219Scy SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 111254219Scy SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 112254219Scy SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 113254219Scy} while (/*CONSTCOND*/ 0) 114254219Scy 115254219Scy/* Generates prototypes and inline functions */ 116254219Scy 117254219Scy#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 118254219Scyvoid name##_SPLAY(struct name *, struct type *); \ 119254219Scyvoid name##_SPLAY_MINMAX(struct name *, int); \ 120254219Scystruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 121254219Scystruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 122254219Scy \ 123254219Scy/* Finds the node with the same key as elm */ \ 124254219Scystatic __inline struct type * \ 125254219Scyname##_SPLAY_FIND(struct name *head, struct type *elm) \ 126254219Scy{ \ 127254219Scy if (SPLAY_EMPTY(head)) \ 128254219Scy return(NULL); \ 129254219Scy name##_SPLAY(head, elm); \ 130254219Scy if ((cmp)(elm, (head)->sph_root) == 0) \ 131254219Scy return (head->sph_root); \ 132254219Scy return (NULL); \ 133254219Scy} \ 134254219Scy \ 135254219Scystatic __inline struct type * \ 136254219Scyname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 137254219Scy{ \ 138254219Scy name##_SPLAY(head, elm); \ 139254219Scy if (SPLAY_RIGHT(elm, field) != NULL) { \ 140254219Scy elm = SPLAY_RIGHT(elm, field); \ 141254219Scy while (SPLAY_LEFT(elm, field) != NULL) { \ 142254219Scy elm = SPLAY_LEFT(elm, field); \ 143254219Scy } \ 144254219Scy } else \ 145254219Scy elm = NULL; \ 146254219Scy return (elm); \ 147254219Scy} \ 148254219Scy \ 149254219Scystatic __inline struct type * \ 150254219Scyname##_SPLAY_MIN_MAX(struct name *head, int val) \ 151254219Scy{ \ 152254219Scy name##_SPLAY_MINMAX(head, val); \ 153254219Scy return (SPLAY_ROOT(head)); \ 154254219Scy} 155254219Scy 156254219Scy/* Main splay operation. 157254219Scy * Moves node close to the key of elm to top 158254219Scy */ 159254219Scy#define SPLAY_GENERATE(name, type, field, cmp) \ 160254219Scystruct type * \ 161254219Scyname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 162254219Scy{ \ 163254219Scy if (SPLAY_EMPTY(head)) { \ 164254219Scy SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 165254219Scy } else { \ 166254219Scy int __comp; \ 167254219Scy name##_SPLAY(head, elm); \ 168254219Scy __comp = (cmp)(elm, (head)->sph_root); \ 169254219Scy if(__comp < 0) { \ 170254219Scy SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 171254219Scy SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 172254219Scy SPLAY_LEFT((head)->sph_root, field) = NULL; \ 173254219Scy } else if (__comp > 0) { \ 174254219Scy SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 175254219Scy SPLAY_LEFT(elm, field) = (head)->sph_root; \ 176254219Scy SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 177254219Scy } else \ 178254219Scy return ((head)->sph_root); \ 179254219Scy } \ 180254219Scy (head)->sph_root = (elm); \ 181254219Scy return (NULL); \ 182254219Scy} \ 183254219Scy \ 184254219Scystruct type * \ 185254219Scyname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 186254219Scy{ \ 187254219Scy struct type *__tmp; \ 188254219Scy if (SPLAY_EMPTY(head)) \ 189254219Scy return (NULL); \ 190254219Scy name##_SPLAY(head, elm); \ 191254219Scy if ((cmp)(elm, (head)->sph_root) == 0) { \ 192254219Scy if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 193254219Scy (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 194254219Scy } else { \ 195254219Scy __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 196254219Scy (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 197254219Scy name##_SPLAY(head, elm); \ 198254219Scy SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 199254219Scy } \ 200254219Scy return (elm); \ 201254219Scy } \ 202254219Scy return (NULL); \ 203254219Scy} \ 204254219Scy \ 205254219Scyvoid \ 206254219Scyname##_SPLAY(struct name *head, struct type *elm) \ 207254219Scy{ \ 208254219Scy struct type __node, *__left, *__right, *__tmp; \ 209254219Scy int __comp; \ 210254219Scy\ 211254219Scy SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 212254219Scy __left = __right = &__node; \ 213254219Scy\ 214254219Scy while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 215254219Scy if (__comp < 0) { \ 216254219Scy __tmp = SPLAY_LEFT((head)->sph_root, field); \ 217254219Scy if (__tmp == NULL) \ 218254219Scy break; \ 219254219Scy if ((cmp)(elm, __tmp) < 0){ \ 220254219Scy SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 221254219Scy if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 222254219Scy break; \ 223254219Scy } \ 224254219Scy SPLAY_LINKLEFT(head, __right, field); \ 225254219Scy } else if (__comp > 0) { \ 226254219Scy __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 227254219Scy if (__tmp == NULL) \ 228254219Scy break; \ 229254219Scy if ((cmp)(elm, __tmp) > 0){ \ 230254219Scy SPLAY_ROTATE_LEFT(head, __tmp, field); \ 231254219Scy if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 232254219Scy break; \ 233254219Scy } \ 234254219Scy SPLAY_LINKRIGHT(head, __left, field); \ 235254219Scy } \ 236254219Scy } \ 237254219Scy SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 238254219Scy} \ 239254219Scy \ 240254219Scy/* Splay with either the minimum or the maximum element \ 241254219Scy * Used to find minimum or maximum element in tree. \ 242254219Scy */ \ 243254219Scyvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 244254219Scy{ \ 245254219Scy struct type __node, *__left, *__right, *__tmp; \ 246254219Scy\ 247254219Scy SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 248254219Scy __left = __right = &__node; \ 249254219Scy\ 250254219Scy while (1) { \ 251254219Scy if (__comp < 0) { \ 252254219Scy __tmp = SPLAY_LEFT((head)->sph_root, field); \ 253254219Scy if (__tmp == NULL) \ 254254219Scy break; \ 255254219Scy if (__comp < 0){ \ 256254219Scy SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 257254219Scy if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 258254219Scy break; \ 259254219Scy } \ 260254219Scy SPLAY_LINKLEFT(head, __right, field); \ 261254219Scy } else if (__comp > 0) { \ 262254219Scy __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 263254219Scy if (__tmp == NULL) \ 264254219Scy break; \ 265254219Scy if (__comp > 0) { \ 266254219Scy SPLAY_ROTATE_LEFT(head, __tmp, field); \ 267254219Scy if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 268254219Scy break; \ 269254219Scy } \ 270254219Scy SPLAY_LINKRIGHT(head, __left, field); \ 271254219Scy } \ 272254219Scy } \ 273254219Scy SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 274254219Scy} 275254219Scy 276254219Scy#define SPLAY_NEGINF -1 277254219Scy#define SPLAY_INF 1 278254219Scy 279254219Scy#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 280254219Scy#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 281254219Scy#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 282254219Scy#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 283254219Scy#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 284254219Scy : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 285254219Scy#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 286254219Scy : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 287254219Scy 288254219Scy#define SPLAY_FOREACH(x, name, head) \ 289254219Scy for ((x) = SPLAY_MIN(name, head); \ 290254219Scy (x) != NULL; \ 291254219Scy (x) = SPLAY_NEXT(name, head, x)) 292254219Scy 293254219Scy/* Macros that define a red-black tree */ 294254219Scy#define RB_HEAD(name, type) \ 295254219Scystruct name { \ 296254219Scy struct type *rbh_root; /* root of the tree */ \ 297254219Scy} 298254219Scy 299254219Scy#define RB_INITIALIZER(root) \ 300254219Scy { NULL } 301254219Scy 302254219Scy#define RB_INIT(root) do { \ 303254219Scy (root)->rbh_root = NULL; \ 304254219Scy} while (/*CONSTCOND*/ 0) 305254219Scy 306254219Scy/* 307254219Scy * Undef for Linux 308254219Scy */ 309254219Scy#undef RB_BLACK 310254219Scy#undef RB_RED 311254219Scy#undef RB_ROOT 312254219Scy 313254219Scy#define RB_BLACK 0 314254219Scy#define RB_RED 1 315254219Scy#define RB_ENTRY(type) \ 316254219Scystruct { \ 317254219Scy struct type *rbe_left; /* left element */ \ 318254219Scy struct type *rbe_right; /* right element */ \ 319254219Scy struct type *rbe_parent; /* parent element */ \ 320254219Scy int rbe_color; /* node color */ \ 321254219Scy} 322254219Scy 323254219Scy#define RB_LEFT(elm, field) (elm)->field.rbe_left 324254219Scy#define RB_RIGHT(elm, field) (elm)->field.rbe_right 325254219Scy#define RB_PARENT(elm, field) (elm)->field.rbe_parent 326254219Scy#define RB_COLOR(elm, field) (elm)->field.rbe_color 327254219Scy#define RB_ROOT(head) (head)->rbh_root 328254219Scy#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 329254219Scy 330254219Scy#define RB_SET(elm, parent, field) do { \ 331254219Scy RB_PARENT(elm, field) = parent; \ 332254219Scy RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 333254219Scy RB_COLOR(elm, field) = RB_RED; \ 334254219Scy} while (/*CONSTCOND*/ 0) 335254219Scy 336254219Scy#define RB_SET_BLACKRED(black, red, field) do { \ 337254219Scy RB_COLOR(black, field) = RB_BLACK; \ 338254219Scy RB_COLOR(red, field) = RB_RED; \ 339254219Scy} while (/*CONSTCOND*/ 0) 340254219Scy 341254219Scy#ifndef RB_AUGMENT 342254219Scy#define RB_AUGMENT(x) do {} while (0) 343254219Scy#endif 344254219Scy 345254219Scy#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 346254219Scy (tmp) = RB_RIGHT(elm, field); \ 347254219Scy if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 348254219Scy RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 349254219Scy } \ 350254219Scy RB_AUGMENT(elm); \ 351254219Scy if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 352254219Scy if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 353254219Scy RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 354254219Scy else \ 355254219Scy RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 356254219Scy } else \ 357254219Scy (head)->rbh_root = (tmp); \ 358254219Scy RB_LEFT(tmp, field) = (elm); \ 359254219Scy RB_PARENT(elm, field) = (tmp); \ 360254219Scy RB_AUGMENT(tmp); \ 361254219Scy if ((RB_PARENT(tmp, field))) \ 362254219Scy RB_AUGMENT(RB_PARENT(tmp, field)); \ 363254219Scy} while (/*CONSTCOND*/ 0) 364254219Scy 365254219Scy#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 366254219Scy (tmp) = RB_LEFT(elm, field); \ 367254219Scy if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 368254219Scy RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 369254219Scy } \ 370254219Scy RB_AUGMENT(elm); \ 371254219Scy if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 372254219Scy if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 373254219Scy RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 374254219Scy else \ 375254219Scy RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 376254219Scy } else \ 377254219Scy (head)->rbh_root = (tmp); \ 378254219Scy RB_RIGHT(tmp, field) = (elm); \ 379254219Scy RB_PARENT(elm, field) = (tmp); \ 380254219Scy RB_AUGMENT(tmp); \ 381254219Scy if ((RB_PARENT(tmp, field))) \ 382254219Scy RB_AUGMENT(RB_PARENT(tmp, field)); \ 383254219Scy} while (/*CONSTCOND*/ 0) 384254219Scy 385254219Scy/* Generates prototypes and inline functions */ 386254219Scy#define RB_PROTOTYPE(name, type, field, cmp) \ 387254219Scy RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 388254219Scy#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 389254219Scy RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 390254219Scy#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 391254219Scyattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 392254219Scyattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 393254219Scyattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 394254219Scyattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 395254219Scyattr struct type *name##_RB_FIND(struct name *, struct type *); \ 396254219Scyattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 397254219Scyattr struct type *name##_RB_NEXT(struct type *); \ 398254219Scyattr struct type *name##_RB_PREV(struct type *); \ 399254219Scyattr struct type *name##_RB_MINMAX(struct name *, int); \ 400254219Scy \ 401254219Scy 402254219Scy/* Main rb operation. 403254219Scy * Moves node close to the key of elm to top 404254219Scy */ 405254219Scy#define RB_GENERATE(name, type, field, cmp) \ 406254219Scy RB_GENERATE_INTERNAL(name, type, field, cmp,) 407254219Scy#define RB_GENERATE_STATIC(name, type, field, cmp) \ 408254219Scy RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 409254219Scy#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 410254219Scyattr void \ 411254219Scyname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 412254219Scy{ \ 413254219Scy struct type *parent, *gparent, *tmp; \ 414254219Scy while ((parent = RB_PARENT(elm, field)) != NULL && \ 415254219Scy RB_COLOR(parent, field) == RB_RED) { \ 416254219Scy gparent = RB_PARENT(parent, field); \ 417254219Scy if (parent == RB_LEFT(gparent, field)) { \ 418254219Scy tmp = RB_RIGHT(gparent, field); \ 419254219Scy if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 420254219Scy RB_COLOR(tmp, field) = RB_BLACK; \ 421254219Scy RB_SET_BLACKRED(parent, gparent, field);\ 422254219Scy elm = gparent; \ 423254219Scy continue; \ 424254219Scy } \ 425254219Scy if (RB_RIGHT(parent, field) == elm) { \ 426254219Scy RB_ROTATE_LEFT(head, parent, tmp, field);\ 427254219Scy tmp = parent; \ 428254219Scy parent = elm; \ 429254219Scy elm = tmp; \ 430254219Scy } \ 431254219Scy RB_SET_BLACKRED(parent, gparent, field); \ 432254219Scy RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 433254219Scy } else { \ 434254219Scy tmp = RB_LEFT(gparent, field); \ 435254219Scy if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 436254219Scy RB_COLOR(tmp, field) = RB_BLACK; \ 437254219Scy RB_SET_BLACKRED(parent, gparent, field);\ 438254219Scy elm = gparent; \ 439254219Scy continue; \ 440254219Scy } \ 441254219Scy if (RB_LEFT(parent, field) == elm) { \ 442254219Scy RB_ROTATE_RIGHT(head, parent, tmp, field);\ 443254219Scy tmp = parent; \ 444254219Scy parent = elm; \ 445254219Scy elm = tmp; \ 446254219Scy } \ 447254219Scy RB_SET_BLACKRED(parent, gparent, field); \ 448254219Scy RB_ROTATE_LEFT(head, gparent, tmp, field); \ 449254219Scy } \ 450254219Scy } \ 451254219Scy RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 452254219Scy} \ 453254219Scy \ 454254219Scyattr void \ 455254219Scyname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 456254219Scy{ \ 457254219Scy struct type *tmp; \ 458254219Scy while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 459254219Scy elm != RB_ROOT(head)) { \ 460254219Scy if (RB_LEFT(parent, field) == elm) { \ 461254219Scy tmp = RB_RIGHT(parent, field); \ 462254219Scy if (RB_COLOR(tmp, field) == RB_RED) { \ 463254219Scy RB_SET_BLACKRED(tmp, parent, field); \ 464254219Scy RB_ROTATE_LEFT(head, parent, tmp, field);\ 465254219Scy tmp = RB_RIGHT(parent, field); \ 466254219Scy } \ 467254219Scy if ((RB_LEFT(tmp, field) == NULL || \ 468254219Scy RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 469254219Scy (RB_RIGHT(tmp, field) == NULL || \ 470254219Scy RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 471254219Scy RB_COLOR(tmp, field) = RB_RED; \ 472254219Scy elm = parent; \ 473254219Scy parent = RB_PARENT(elm, field); \ 474254219Scy } else { \ 475254219Scy if (RB_RIGHT(tmp, field) == NULL || \ 476254219Scy RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 477254219Scy struct type *oleft; \ 478254219Scy if ((oleft = RB_LEFT(tmp, field)) \ 479254219Scy != NULL) \ 480254219Scy RB_COLOR(oleft, field) = RB_BLACK;\ 481254219Scy RB_COLOR(tmp, field) = RB_RED; \ 482254219Scy RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 483254219Scy tmp = RB_RIGHT(parent, field); \ 484254219Scy } \ 485254219Scy RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 486254219Scy RB_COLOR(parent, field) = RB_BLACK; \ 487254219Scy if (RB_RIGHT(tmp, field)) \ 488254219Scy RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 489254219Scy RB_ROTATE_LEFT(head, parent, tmp, field);\ 490254219Scy elm = RB_ROOT(head); \ 491254219Scy break; \ 492254219Scy } \ 493254219Scy } else { \ 494254219Scy tmp = RB_LEFT(parent, field); \ 495254219Scy if (RB_COLOR(tmp, field) == RB_RED) { \ 496254219Scy RB_SET_BLACKRED(tmp, parent, field); \ 497254219Scy RB_ROTATE_RIGHT(head, parent, tmp, field);\ 498254219Scy tmp = RB_LEFT(parent, field); \ 499254219Scy } \ 500254219Scy if ((RB_LEFT(tmp, field) == NULL || \ 501254219Scy RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 502254219Scy (RB_RIGHT(tmp, field) == NULL || \ 503254219Scy RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 504254219Scy RB_COLOR(tmp, field) = RB_RED; \ 505254219Scy elm = parent; \ 506254219Scy parent = RB_PARENT(elm, field); \ 507254219Scy } else { \ 508254219Scy if (RB_LEFT(tmp, field) == NULL || \ 509254219Scy RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 510254219Scy struct type *oright; \ 511254219Scy if ((oright = RB_RIGHT(tmp, field)) \ 512254219Scy != NULL) \ 513254219Scy RB_COLOR(oright, field) = RB_BLACK;\ 514254219Scy RB_COLOR(tmp, field) = RB_RED; \ 515254219Scy RB_ROTATE_LEFT(head, tmp, oright, field);\ 516254219Scy tmp = RB_LEFT(parent, field); \ 517254219Scy } \ 518254219Scy RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 519254219Scy RB_COLOR(parent, field) = RB_BLACK; \ 520254219Scy if (RB_LEFT(tmp, field)) \ 521254219Scy RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 522254219Scy RB_ROTATE_RIGHT(head, parent, tmp, field);\ 523254219Scy elm = RB_ROOT(head); \ 524254219Scy break; \ 525254219Scy } \ 526254219Scy } \ 527254219Scy } \ 528254219Scy if (elm) \ 529254219Scy RB_COLOR(elm, field) = RB_BLACK; \ 530254219Scy} \ 531254219Scy \ 532254219Scyattr struct type * \ 533254219Scyname##_RB_REMOVE(struct name *head, struct type *elm) \ 534254219Scy{ \ 535254219Scy struct type *child, *parent, *old = elm; \ 536254219Scy int color; \ 537254219Scy if (RB_LEFT(elm, field) == NULL) \ 538254219Scy child = RB_RIGHT(elm, field); \ 539254219Scy else if (RB_RIGHT(elm, field) == NULL) \ 540254219Scy child = RB_LEFT(elm, field); \ 541254219Scy else { \ 542254219Scy struct type *left; \ 543254219Scy elm = RB_RIGHT(elm, field); \ 544254219Scy while ((left = RB_LEFT(elm, field)) != NULL) \ 545254219Scy elm = left; \ 546254219Scy child = RB_RIGHT(elm, field); \ 547254219Scy parent = RB_PARENT(elm, field); \ 548254219Scy color = RB_COLOR(elm, field); \ 549254219Scy if (child) \ 550254219Scy RB_PARENT(child, field) = parent; \ 551254219Scy if (parent) { \ 552254219Scy if (RB_LEFT(parent, field) == elm) \ 553254219Scy RB_LEFT(parent, field) = child; \ 554254219Scy else \ 555254219Scy RB_RIGHT(parent, field) = child; \ 556254219Scy RB_AUGMENT(parent); \ 557254219Scy } else \ 558254219Scy RB_ROOT(head) = child; \ 559254219Scy if (RB_PARENT(elm, field) == old) \ 560254219Scy parent = elm; \ 561254219Scy (elm)->field = (old)->field; \ 562254219Scy if (RB_PARENT(old, field)) { \ 563254219Scy if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 564254219Scy RB_LEFT(RB_PARENT(old, field), field) = elm;\ 565254219Scy else \ 566254219Scy RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 567254219Scy RB_AUGMENT(RB_PARENT(old, field)); \ 568254219Scy } else \ 569254219Scy RB_ROOT(head) = elm; \ 570254219Scy RB_PARENT(RB_LEFT(old, field), field) = elm; \ 571254219Scy if (RB_RIGHT(old, field)) \ 572254219Scy RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 573254219Scy if (parent) { \ 574254219Scy left = parent; \ 575254219Scy do { \ 576254219Scy RB_AUGMENT(left); \ 577254219Scy } while ((left = RB_PARENT(left, field)) != NULL); \ 578254219Scy } \ 579254219Scy goto color; \ 580254219Scy } \ 581254219Scy parent = RB_PARENT(elm, field); \ 582254219Scy color = RB_COLOR(elm, field); \ 583254219Scy if (child) \ 584254219Scy RB_PARENT(child, field) = parent; \ 585254219Scy if (parent) { \ 586254219Scy if (RB_LEFT(parent, field) == elm) \ 587254219Scy RB_LEFT(parent, field) = child; \ 588254219Scy else \ 589254219Scy RB_RIGHT(parent, field) = child; \ 590254219Scy RB_AUGMENT(parent); \ 591254219Scy } else \ 592254219Scy RB_ROOT(head) = child; \ 593254219Scycolor: \ 594254219Scy if (color == RB_BLACK) \ 595254219Scy name##_RB_REMOVE_COLOR(head, parent, child); \ 596254219Scy return (old); \ 597254219Scy} \ 598254219Scy \ 599254219Scy/* Inserts a node into the RB tree */ \ 600254219Scyattr struct type * \ 601254219Scyname##_RB_INSERT(struct name *head, struct type *elm) \ 602254219Scy{ \ 603254219Scy struct type *tmp; \ 604254219Scy struct type *parent = NULL; \ 605254219Scy int comp = 0; \ 606254219Scy tmp = RB_ROOT(head); \ 607254219Scy while (tmp) { \ 608254219Scy parent = tmp; \ 609254219Scy comp = (cmp)(elm, parent); \ 610254219Scy if (comp < 0) \ 611254219Scy tmp = RB_LEFT(tmp, field); \ 612254219Scy else if (comp > 0) \ 613254219Scy tmp = RB_RIGHT(tmp, field); \ 614254219Scy else \ 615254219Scy return (tmp); \ 616254219Scy } \ 617254219Scy RB_SET(elm, parent, field); \ 618254219Scy if (parent != NULL) { \ 619254219Scy if (comp < 0) \ 620254219Scy RB_LEFT(parent, field) = elm; \ 621254219Scy else \ 622254219Scy RB_RIGHT(parent, field) = elm; \ 623254219Scy RB_AUGMENT(parent); \ 624254219Scy } else \ 625254219Scy RB_ROOT(head) = elm; \ 626254219Scy name##_RB_INSERT_COLOR(head, elm); \ 627254219Scy return (NULL); \ 628254219Scy} \ 629254219Scy \ 630254219Scy/* Finds the node with the same key as elm */ \ 631254219Scyattr struct type * \ 632254219Scyname##_RB_FIND(struct name *head, struct type *elm) \ 633254219Scy{ \ 634254219Scy struct type *tmp = RB_ROOT(head); \ 635254219Scy int comp; \ 636254219Scy while (tmp) { \ 637254219Scy comp = cmp(elm, tmp); \ 638254219Scy if (comp < 0) \ 639254219Scy tmp = RB_LEFT(tmp, field); \ 640254219Scy else if (comp > 0) \ 641254219Scy tmp = RB_RIGHT(tmp, field); \ 642254219Scy else \ 643254219Scy return (tmp); \ 644254219Scy } \ 645254219Scy return (NULL); \ 646254219Scy} \ 647254219Scy \ 648254219Scy/* Finds the first node greater than or equal to the search key */ \ 649254219Scyattr struct type * \ 650254219Scyname##_RB_NFIND(struct name *head, struct type *elm) \ 651254219Scy{ \ 652254219Scy struct type *tmp = RB_ROOT(head); \ 653254219Scy struct type *res = NULL; \ 654254219Scy int comp; \ 655254219Scy while (tmp) { \ 656254219Scy comp = cmp(elm, tmp); \ 657254219Scy if (comp < 0) { \ 658254219Scy res = tmp; \ 659254219Scy tmp = RB_LEFT(tmp, field); \ 660254219Scy } \ 661254219Scy else if (comp > 0) \ 662254219Scy tmp = RB_RIGHT(tmp, field); \ 663254219Scy else \ 664254219Scy return (tmp); \ 665254219Scy } \ 666254219Scy return (res); \ 667254219Scy} \ 668254219Scy \ 669254219Scy/* ARGSUSED */ \ 670254219Scyattr struct type * \ 671254219Scyname##_RB_NEXT(struct type *elm) \ 672254219Scy{ \ 673254219Scy if (RB_RIGHT(elm, field)) { \ 674254219Scy elm = RB_RIGHT(elm, field); \ 675254219Scy while (RB_LEFT(elm, field)) \ 676254219Scy elm = RB_LEFT(elm, field); \ 677254219Scy } else { \ 678254219Scy if (RB_PARENT(elm, field) && \ 679254219Scy (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 680254219Scy elm = RB_PARENT(elm, field); \ 681254219Scy else { \ 682254219Scy while (RB_PARENT(elm, field) && \ 683254219Scy (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 684254219Scy elm = RB_PARENT(elm, field); \ 685254219Scy elm = RB_PARENT(elm, field); \ 686254219Scy } \ 687254219Scy } \ 688254219Scy return (elm); \ 689254219Scy} \ 690254219Scy \ 691254219Scy/* ARGSUSED */ \ 692254219Scyattr struct type * \ 693254219Scyname##_RB_PREV(struct type *elm) \ 694254219Scy{ \ 695254219Scy if (RB_LEFT(elm, field)) { \ 696254219Scy elm = RB_LEFT(elm, field); \ 697254219Scy while (RB_RIGHT(elm, field)) \ 698254219Scy elm = RB_RIGHT(elm, field); \ 699254219Scy } else { \ 700254219Scy if (RB_PARENT(elm, field) && \ 701254219Scy (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 702254219Scy elm = RB_PARENT(elm, field); \ 703254219Scy else { \ 704254219Scy while (RB_PARENT(elm, field) && \ 705254219Scy (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 706254219Scy elm = RB_PARENT(elm, field); \ 707254219Scy elm = RB_PARENT(elm, field); \ 708254219Scy } \ 709254219Scy } \ 710254219Scy return (elm); \ 711254219Scy} \ 712254219Scy \ 713254219Scyattr struct type * \ 714254219Scyname##_RB_MINMAX(struct name *head, int val) \ 715254219Scy{ \ 716254219Scy struct type *tmp = RB_ROOT(head); \ 717254219Scy struct type *parent = NULL; \ 718254219Scy while (tmp) { \ 719254219Scy parent = tmp; \ 720254219Scy if (val < 0) \ 721254219Scy tmp = RB_LEFT(tmp, field); \ 722254219Scy else \ 723254219Scy tmp = RB_RIGHT(tmp, field); \ 724254219Scy } \ 725254219Scy return (parent); \ 726254219Scy} 727254219Scy 728254219Scy#define RB_NEGINF -1 729254219Scy#define RB_INF 1 730254219Scy 731254219Scy#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 732254219Scy#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 733254219Scy#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 734254219Scy#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 735254219Scy#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 736254219Scy#define RB_PREV(name, x, y) name##_RB_PREV(y) 737254219Scy#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 738254219Scy#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 739254219Scy 740254219Scy#define RB_FOREACH(x, name, head) \ 741254219Scy for ((x) = RB_MIN(name, head); \ 742254219Scy (x) != NULL; \ 743254219Scy (x) = name##_RB_NEXT(x)) 744254219Scy 745254219Scy#define RB_FOREACH_REVERSE(x, name, head) \ 746254219Scy for ((x) = RB_MAX(name, head); \ 747254219Scy (x) != NULL; \ 748254219Scy (x) = name##_RB_PREV(x)) 749254219Scy 750254219Scy#endif /* _SYS_TREE_H_ */ 751