1290001Sglebius/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 2290001Sglebius/* 3290001Sglebius * Copyright 2002 Niels Provos <provos@citi.umich.edu> 4290001Sglebius * All rights reserved. 5290001Sglebius * 6290001Sglebius * Redistribution and use in source and binary forms, with or without 7290001Sglebius * modification, are permitted provided that the following conditions 8290001Sglebius * are met: 9290001Sglebius * 1. Redistributions of source code must retain the above copyright 10290001Sglebius * notice, this list of conditions and the following disclaimer. 11290001Sglebius * 2. Redistributions in binary form must reproduce the above copyright 12290001Sglebius * notice, this list of conditions and the following disclaimer in the 13290001Sglebius * documentation and/or other materials provided with the distribution. 14290001Sglebius * 15290001Sglebius * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16290001Sglebius * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17290001Sglebius * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18290001Sglebius * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19290001Sglebius * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20290001Sglebius * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21290001Sglebius * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22290001Sglebius * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23290001Sglebius * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24290001Sglebius * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25290001Sglebius */ 26290001Sglebius 27290001Sglebius#ifndef _SYS_TREE_H_ 28290001Sglebius#define _SYS_TREE_H_ 29290001Sglebius 30290001Sglebius/* 31290001Sglebius * This file defines data structures for different types of trees: 32290001Sglebius * splay trees and red-black trees. 33290001Sglebius * 34290001Sglebius * A splay tree is a self-organizing data structure. Every operation 35290001Sglebius * on the tree causes a splay to happen. The splay moves the requested 36290001Sglebius * node to the root of the tree and partly rebalances it. 37290001Sglebius * 38290001Sglebius * This has the benefit that request locality causes faster lookups as 39290001Sglebius * the requested nodes move to the top of the tree. On the other hand, 40290001Sglebius * every lookup causes memory writes. 41290001Sglebius * 42290001Sglebius * The Balance Theorem bounds the total access time for m operations 43290001Sglebius * and n inserts on an initially empty tree as O((m + n)lg n). The 44290001Sglebius * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 45290001Sglebius * 46290001Sglebius * A red-black tree is a binary search tree with the node color as an 47290001Sglebius * extra attribute. It fulfills a set of conditions: 48290001Sglebius * - every search path from the root to a leaf consists of the 49290001Sglebius * same number of black nodes, 50290001Sglebius * - each red node (except for the root) has a black parent, 51290001Sglebius * - each leaf node is black. 52290001Sglebius * 53290001Sglebius * Every operation on a red-black tree is bounded as O(lg n). 54290001Sglebius * The maximum height of a red-black tree is 2lg (n+1). 55290001Sglebius */ 56290001Sglebius 57290001Sglebius#define SPLAY_HEAD(name, type) \ 58290001Sglebiusstruct name { \ 59290001Sglebius struct type *sph_root; /* root of the tree */ \ 60290001Sglebius} 61290001Sglebius 62290001Sglebius#define SPLAY_INITIALIZER(root) \ 63290001Sglebius { NULL } 64290001Sglebius 65290001Sglebius#define SPLAY_INIT(root) do { \ 66290001Sglebius (root)->sph_root = NULL; \ 67290001Sglebius} while (0) 68290001Sglebius 69290001Sglebius#define SPLAY_ENTRY(type) \ 70290001Sglebiusstruct { \ 71290001Sglebius struct type *spe_left; /* left element */ \ 72290001Sglebius struct type *spe_right; /* right element */ \ 73290001Sglebius} 74290001Sglebius 75290001Sglebius#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 76290001Sglebius#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 77290001Sglebius#define SPLAY_ROOT(head) (head)->sph_root 78290001Sglebius#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 79290001Sglebius 80290001Sglebius/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 81290001Sglebius#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 82290001Sglebius SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 83290001Sglebius SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 84290001Sglebius (head)->sph_root = tmp; \ 85290001Sglebius} while (0) 86290001Sglebius 87290001Sglebius#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 88290001Sglebius SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 89290001Sglebius SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 90290001Sglebius (head)->sph_root = tmp; \ 91290001Sglebius} while (0) 92290001Sglebius 93290001Sglebius#define SPLAY_LINKLEFT(head, tmp, field) do { \ 94290001Sglebius SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95290001Sglebius tmp = (head)->sph_root; \ 96290001Sglebius (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 97290001Sglebius} while (0) 98290001Sglebius 99290001Sglebius#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 100290001Sglebius SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 101290001Sglebius tmp = (head)->sph_root; \ 102290001Sglebius (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 103290001Sglebius} while (0) 104290001Sglebius 105290001Sglebius#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 106290001Sglebius SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 107290001Sglebius SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 108290001Sglebius SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 109290001Sglebius SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 110290001Sglebius} while (0) 111290001Sglebius 112290001Sglebius/* Generates prototypes and inline functions */ 113290001Sglebius 114290001Sglebius#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 115290001Sglebiusvoid name##_SPLAY(struct name *, struct type *); \ 116290001Sglebiusvoid name##_SPLAY_MINMAX(struct name *, int); \ 117290001Sglebiusstruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 118290001Sglebiusstruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 119290001Sglebius \ 120290001Sglebius/* Finds the node with the same key as elm */ \ 121290001Sglebiusstatic __inline struct type * \ 122290001Sglebiusname##_SPLAY_FIND(struct name *head, struct type *elm) \ 123290001Sglebius{ \ 124290001Sglebius if (SPLAY_EMPTY(head)) \ 125290001Sglebius return(NULL); \ 126290001Sglebius name##_SPLAY(head, elm); \ 127290001Sglebius if ((cmp)(elm, (head)->sph_root) == 0) \ 128290001Sglebius return (head->sph_root); \ 129290001Sglebius return (NULL); \ 130290001Sglebius} \ 131290001Sglebius \ 132290001Sglebiusstatic __inline struct type * \ 133290001Sglebiusname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 134290001Sglebius{ \ 135290001Sglebius name##_SPLAY(head, elm); \ 136290001Sglebius if (SPLAY_RIGHT(elm, field) != NULL) { \ 137290001Sglebius elm = SPLAY_RIGHT(elm, field); \ 138290001Sglebius while (SPLAY_LEFT(elm, field) != NULL) { \ 139290001Sglebius elm = SPLAY_LEFT(elm, field); \ 140290001Sglebius } \ 141290001Sglebius } else \ 142290001Sglebius elm = NULL; \ 143290001Sglebius return (elm); \ 144290001Sglebius} \ 145290001Sglebius \ 146290001Sglebiusstatic __inline struct type * \ 147290001Sglebiusname##_SPLAY_MIN_MAX(struct name *head, int val) \ 148290001Sglebius{ \ 149290001Sglebius name##_SPLAY_MINMAX(head, val); \ 150290001Sglebius return (SPLAY_ROOT(head)); \ 151290001Sglebius} 152290001Sglebius 153290001Sglebius/* Main splay operation. 154290001Sglebius * Moves node close to the key of elm to top 155290001Sglebius */ 156290001Sglebius#define SPLAY_GENERATE(name, type, field, cmp) \ 157290001Sglebiusstruct type * \ 158290001Sglebiusname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 159290001Sglebius{ \ 160290001Sglebius if (SPLAY_EMPTY(head)) { \ 161290001Sglebius SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 162290001Sglebius } else { \ 163290001Sglebius int __comp; \ 164290001Sglebius name##_SPLAY(head, elm); \ 165290001Sglebius __comp = (cmp)(elm, (head)->sph_root); \ 166290001Sglebius if(__comp < 0) { \ 167290001Sglebius SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 168290001Sglebius SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 169290001Sglebius SPLAY_LEFT((head)->sph_root, field) = NULL; \ 170290001Sglebius } else if (__comp > 0) { \ 171290001Sglebius SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 172290001Sglebius SPLAY_LEFT(elm, field) = (head)->sph_root; \ 173290001Sglebius SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 174290001Sglebius } else \ 175290001Sglebius return ((head)->sph_root); \ 176290001Sglebius } \ 177290001Sglebius (head)->sph_root = (elm); \ 178290001Sglebius return (NULL); \ 179290001Sglebius} \ 180290001Sglebius \ 181290001Sglebiusstruct type * \ 182290001Sglebiusname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 183290001Sglebius{ \ 184290001Sglebius struct type *__tmp; \ 185290001Sglebius if (SPLAY_EMPTY(head)) \ 186290001Sglebius return (NULL); \ 187290001Sglebius name##_SPLAY(head, elm); \ 188290001Sglebius if ((cmp)(elm, (head)->sph_root) == 0) { \ 189290001Sglebius if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 190290001Sglebius (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 191290001Sglebius } else { \ 192290001Sglebius __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 193290001Sglebius (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 194290001Sglebius name##_SPLAY(head, elm); \ 195290001Sglebius SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 196290001Sglebius } \ 197290001Sglebius return (elm); \ 198290001Sglebius } \ 199290001Sglebius return (NULL); \ 200290001Sglebius} \ 201290001Sglebius \ 202290001Sglebiusvoid \ 203290001Sglebiusname##_SPLAY(struct name *head, struct type *elm) \ 204290001Sglebius{ \ 205290001Sglebius struct type __node, *__left, *__right, *__tmp; \ 206290001Sglebius int __comp; \ 207290001Sglebius\ 208290001Sglebius SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 209290001Sglebius __left = __right = &__node; \ 210290001Sglebius\ 211290001Sglebius while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 212290001Sglebius if (__comp < 0) { \ 213290001Sglebius __tmp = SPLAY_LEFT((head)->sph_root, field); \ 214290001Sglebius if (__tmp == NULL) \ 215290001Sglebius break; \ 216290001Sglebius if ((cmp)(elm, __tmp) < 0){ \ 217290001Sglebius SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 218290001Sglebius if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 219290001Sglebius break; \ 220290001Sglebius } \ 221290001Sglebius SPLAY_LINKLEFT(head, __right, field); \ 222290001Sglebius } else if (__comp > 0) { \ 223290001Sglebius __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 224290001Sglebius if (__tmp == NULL) \ 225290001Sglebius break; \ 226290001Sglebius if ((cmp)(elm, __tmp) > 0){ \ 227290001Sglebius SPLAY_ROTATE_LEFT(head, __tmp, field); \ 228290001Sglebius if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 229290001Sglebius break; \ 230290001Sglebius } \ 231290001Sglebius SPLAY_LINKRIGHT(head, __left, field); \ 232290001Sglebius } \ 233290001Sglebius } \ 234290001Sglebius SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 235290001Sglebius} \ 236290001Sglebius \ 237290001Sglebius/* Splay with either the minimum or the maximum element \ 238290001Sglebius * Used to find minimum or maximum element in tree. \ 239290001Sglebius */ \ 240290001Sglebiusvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 241290001Sglebius{ \ 242290001Sglebius struct type __node, *__left, *__right, *__tmp; \ 243290001Sglebius\ 244290001Sglebius SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 245290001Sglebius __left = __right = &__node; \ 246290001Sglebius\ 247290001Sglebius while (1) { \ 248290001Sglebius if (__comp < 0) { \ 249290001Sglebius __tmp = SPLAY_LEFT((head)->sph_root, field); \ 250290001Sglebius if (__tmp == NULL) \ 251290001Sglebius break; \ 252290001Sglebius if (__comp < 0){ \ 253290001Sglebius SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 254290001Sglebius if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 255290001Sglebius break; \ 256290001Sglebius } \ 257290001Sglebius SPLAY_LINKLEFT(head, __right, field); \ 258290001Sglebius } else if (__comp > 0) { \ 259290001Sglebius __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 260290001Sglebius if (__tmp == NULL) \ 261290001Sglebius break; \ 262290001Sglebius if (__comp > 0) { \ 263290001Sglebius SPLAY_ROTATE_LEFT(head, __tmp, field); \ 264290001Sglebius if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 265290001Sglebius break; \ 266290001Sglebius } \ 267290001Sglebius SPLAY_LINKRIGHT(head, __left, field); \ 268290001Sglebius } \ 269290001Sglebius } \ 270290001Sglebius SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 271290001Sglebius} 272290001Sglebius 273290001Sglebius#define SPLAY_NEGINF -1 274290001Sglebius#define SPLAY_INF 1 275290001Sglebius 276290001Sglebius#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 277290001Sglebius#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 278290001Sglebius#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 279290001Sglebius#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 280290001Sglebius#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 281290001Sglebius : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 282290001Sglebius#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 283290001Sglebius : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 284290001Sglebius 285290001Sglebius#define SPLAY_FOREACH(x, name, head) \ 286290001Sglebius for ((x) = SPLAY_MIN(name, head); \ 287290001Sglebius (x) != NULL; \ 288290001Sglebius (x) = SPLAY_NEXT(name, head, x)) 289290001Sglebius 290290001Sglebius/* Macros that define a red-back tree */ 291290001Sglebius#define RB_HEAD(name, type) \ 292290001Sglebiusstruct name { \ 293290001Sglebius struct type *rbh_root; /* root of the tree */ \ 294290001Sglebius} 295290001Sglebius 296290001Sglebius#define RB_INITIALIZER(root) \ 297290001Sglebius { NULL } 298290001Sglebius 299290001Sglebius#define RB_INIT(root) do { \ 300290001Sglebius (root)->rbh_root = NULL; \ 301290001Sglebius} while (0) 302290001Sglebius 303290001Sglebius#define RB_BLACK 0 304290001Sglebius#define RB_RED 1 305290001Sglebius#define RB_ENTRY(type) \ 306290001Sglebiusstruct { \ 307290001Sglebius struct type *rbe_left; /* left element */ \ 308290001Sglebius struct type *rbe_right; /* right element */ \ 309290001Sglebius struct type *rbe_parent; /* parent element */ \ 310290001Sglebius int rbe_color; /* node color */ \ 311290001Sglebius} 312290001Sglebius 313290001Sglebius#define RB_LEFT(elm, field) (elm)->field.rbe_left 314290001Sglebius#define RB_RIGHT(elm, field) (elm)->field.rbe_right 315290001Sglebius#define RB_PARENT(elm, field) (elm)->field.rbe_parent 316290001Sglebius#define RB_COLOR(elm, field) (elm)->field.rbe_color 317290001Sglebius#define RB_ROOT(head) (head)->rbh_root 318290001Sglebius#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 319290001Sglebius 320290001Sglebius#define RB_SET(elm, parent, field) do { \ 321290001Sglebius RB_PARENT(elm, field) = parent; \ 322290001Sglebius RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 323290001Sglebius RB_COLOR(elm, field) = RB_RED; \ 324290001Sglebius} while (0) 325290001Sglebius 326290001Sglebius#define RB_SET_BLACKRED(black, red, field) do { \ 327290001Sglebius RB_COLOR(black, field) = RB_BLACK; \ 328290001Sglebius RB_COLOR(red, field) = RB_RED; \ 329290001Sglebius} while (0) 330290001Sglebius 331290001Sglebius#ifndef RB_AUGMENT 332290001Sglebius#define RB_AUGMENT(x) 333290001Sglebius#endif 334290001Sglebius 335290001Sglebius#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 336290001Sglebius (tmp) = RB_RIGHT(elm, field); \ 337290001Sglebius if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 338290001Sglebius RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 339290001Sglebius } \ 340290001Sglebius RB_AUGMENT(elm); \ 341290001Sglebius if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 342290001Sglebius if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 343290001Sglebius RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 344290001Sglebius else \ 345290001Sglebius RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 346290001Sglebius } else \ 347290001Sglebius (head)->rbh_root = (tmp); \ 348290001Sglebius RB_LEFT(tmp, field) = (elm); \ 349290001Sglebius RB_PARENT(elm, field) = (tmp); \ 350290001Sglebius RB_AUGMENT(tmp); \ 351290001Sglebius if ((RB_PARENT(tmp, field))) \ 352290001Sglebius RB_AUGMENT(RB_PARENT(tmp, field)); \ 353290001Sglebius} while (0) 354290001Sglebius 355290001Sglebius#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 356290001Sglebius (tmp) = RB_LEFT(elm, field); \ 357290001Sglebius if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 358290001Sglebius RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 359290001Sglebius } \ 360290001Sglebius RB_AUGMENT(elm); \ 361290001Sglebius if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 362290001Sglebius if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 363290001Sglebius RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 364290001Sglebius else \ 365290001Sglebius RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 366290001Sglebius } else \ 367290001Sglebius (head)->rbh_root = (tmp); \ 368290001Sglebius RB_RIGHT(tmp, field) = (elm); \ 369290001Sglebius RB_PARENT(elm, field) = (tmp); \ 370290001Sglebius RB_AUGMENT(tmp); \ 371290001Sglebius if ((RB_PARENT(tmp, field))) \ 372290001Sglebius RB_AUGMENT(RB_PARENT(tmp, field)); \ 373290001Sglebius} while (0) 374290001Sglebius 375290001Sglebius/* Generates prototypes and inline functions */ 376290001Sglebius#define RB_PROTOTYPE(name, type, field, cmp) \ 377290001Sglebiusvoid name##_RB_INSERT_COLOR(struct name *, struct type *); \ 378290001Sglebiusvoid name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 379290001Sglebiusstruct type *name##_RB_REMOVE(struct name *, struct type *); \ 380290001Sglebiusstruct type *name##_RB_INSERT(struct name *, struct type *); \ 381290001Sglebiusstruct type *name##_RB_FIND(struct name *, struct type *); \ 382290001Sglebiusstruct type *name##_RB_NEXT(struct type *); \ 383290001Sglebiusstruct type *name##_RB_MINMAX(struct name *, int); \ 384290001Sglebius \ 385290001Sglebius 386290001Sglebius/* Main rb operation. 387290001Sglebius * Moves node close to the key of elm to top 388290001Sglebius */ 389290001Sglebius#define RB_GENERATE(name, type, field, cmp) \ 390290001Sglebiusvoid \ 391290001Sglebiusname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 392290001Sglebius{ \ 393290001Sglebius struct type *parent, *gparent, *tmp; \ 394290001Sglebius while ((parent = RB_PARENT(elm, field)) && \ 395290001Sglebius RB_COLOR(parent, field) == RB_RED) { \ 396290001Sglebius gparent = RB_PARENT(parent, field); \ 397290001Sglebius if (parent == RB_LEFT(gparent, field)) { \ 398290001Sglebius tmp = RB_RIGHT(gparent, field); \ 399290001Sglebius if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 400290001Sglebius RB_COLOR(tmp, field) = RB_BLACK; \ 401290001Sglebius RB_SET_BLACKRED(parent, gparent, field);\ 402290001Sglebius elm = gparent; \ 403290001Sglebius continue; \ 404290001Sglebius } \ 405290001Sglebius if (RB_RIGHT(parent, field) == elm) { \ 406290001Sglebius RB_ROTATE_LEFT(head, parent, tmp, field);\ 407290001Sglebius tmp = parent; \ 408290001Sglebius parent = elm; \ 409290001Sglebius elm = tmp; \ 410290001Sglebius } \ 411290001Sglebius RB_SET_BLACKRED(parent, gparent, field); \ 412290001Sglebius RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 413290001Sglebius } else { \ 414290001Sglebius tmp = RB_LEFT(gparent, field); \ 415290001Sglebius if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 416290001Sglebius RB_COLOR(tmp, field) = RB_BLACK; \ 417290001Sglebius RB_SET_BLACKRED(parent, gparent, field);\ 418290001Sglebius elm = gparent; \ 419290001Sglebius continue; \ 420290001Sglebius } \ 421290001Sglebius if (RB_LEFT(parent, field) == elm) { \ 422290001Sglebius RB_ROTATE_RIGHT(head, parent, tmp, field);\ 423290001Sglebius tmp = parent; \ 424290001Sglebius parent = elm; \ 425290001Sglebius elm = tmp; \ 426290001Sglebius } \ 427290001Sglebius RB_SET_BLACKRED(parent, gparent, field); \ 428290001Sglebius RB_ROTATE_LEFT(head, gparent, tmp, field); \ 429290001Sglebius } \ 430290001Sglebius } \ 431290001Sglebius RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 432290001Sglebius} \ 433290001Sglebius \ 434290001Sglebiusvoid \ 435290001Sglebiusname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 436290001Sglebius{ \ 437290001Sglebius struct type *tmp; \ 438290001Sglebius while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 439290001Sglebius elm != RB_ROOT(head)) { \ 440290001Sglebius if (RB_LEFT(parent, field) == elm) { \ 441290001Sglebius tmp = RB_RIGHT(parent, field); \ 442290001Sglebius if (RB_COLOR(tmp, field) == RB_RED) { \ 443290001Sglebius RB_SET_BLACKRED(tmp, parent, field); \ 444290001Sglebius RB_ROTATE_LEFT(head, parent, tmp, field);\ 445290001Sglebius tmp = RB_RIGHT(parent, field); \ 446290001Sglebius } \ 447290001Sglebius if ((RB_LEFT(tmp, field) == NULL || \ 448290001Sglebius RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 449290001Sglebius (RB_RIGHT(tmp, field) == NULL || \ 450290001Sglebius RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 451290001Sglebius RB_COLOR(tmp, field) = RB_RED; \ 452290001Sglebius elm = parent; \ 453290001Sglebius parent = RB_PARENT(elm, field); \ 454290001Sglebius } else { \ 455290001Sglebius if (RB_RIGHT(tmp, field) == NULL || \ 456290001Sglebius RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 457290001Sglebius struct type *oleft; \ 458290001Sglebius if ((oleft = RB_LEFT(tmp, field)))\ 459290001Sglebius RB_COLOR(oleft, field) = RB_BLACK;\ 460290001Sglebius RB_COLOR(tmp, field) = RB_RED; \ 461290001Sglebius RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 462290001Sglebius tmp = RB_RIGHT(parent, field); \ 463290001Sglebius } \ 464290001Sglebius RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 465290001Sglebius RB_COLOR(parent, field) = RB_BLACK; \ 466290001Sglebius if (RB_RIGHT(tmp, field)) \ 467290001Sglebius RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 468290001Sglebius RB_ROTATE_LEFT(head, parent, tmp, field);\ 469290001Sglebius elm = RB_ROOT(head); \ 470290001Sglebius break; \ 471290001Sglebius } \ 472290001Sglebius } else { \ 473290001Sglebius tmp = RB_LEFT(parent, field); \ 474290001Sglebius if (RB_COLOR(tmp, field) == RB_RED) { \ 475290001Sglebius RB_SET_BLACKRED(tmp, parent, field); \ 476290001Sglebius RB_ROTATE_RIGHT(head, parent, tmp, field);\ 477290001Sglebius tmp = RB_LEFT(parent, field); \ 478290001Sglebius } \ 479290001Sglebius if ((RB_LEFT(tmp, field) == NULL || \ 480290001Sglebius RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 481290001Sglebius (RB_RIGHT(tmp, field) == NULL || \ 482290001Sglebius RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 483290001Sglebius RB_COLOR(tmp, field) = RB_RED; \ 484290001Sglebius elm = parent; \ 485290001Sglebius parent = RB_PARENT(elm, field); \ 486290001Sglebius } else { \ 487290001Sglebius if (RB_LEFT(tmp, field) == NULL || \ 488290001Sglebius RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 489290001Sglebius struct type *oright; \ 490290001Sglebius if ((oright = RB_RIGHT(tmp, field)))\ 491290001Sglebius RB_COLOR(oright, field) = RB_BLACK;\ 492290001Sglebius RB_COLOR(tmp, field) = RB_RED; \ 493290001Sglebius RB_ROTATE_LEFT(head, tmp, oright, field);\ 494290001Sglebius tmp = RB_LEFT(parent, field); \ 495290001Sglebius } \ 496290001Sglebius RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 497290001Sglebius RB_COLOR(parent, field) = RB_BLACK; \ 498290001Sglebius if (RB_LEFT(tmp, field)) \ 499290001Sglebius RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 500290001Sglebius RB_ROTATE_RIGHT(head, parent, tmp, field);\ 501290001Sglebius elm = RB_ROOT(head); \ 502290001Sglebius break; \ 503290001Sglebius } \ 504290001Sglebius } \ 505290001Sglebius } \ 506290001Sglebius if (elm) \ 507290001Sglebius RB_COLOR(elm, field) = RB_BLACK; \ 508290001Sglebius} \ 509290001Sglebius \ 510290001Sglebiusstruct type * \ 511290001Sglebiusname##_RB_REMOVE(struct name *head, struct type *elm) \ 512290001Sglebius{ \ 513290001Sglebius struct type *child, *parent, *old = elm; \ 514290001Sglebius int color; \ 515290001Sglebius if (RB_LEFT(elm, field) == NULL) \ 516290001Sglebius child = RB_RIGHT(elm, field); \ 517290001Sglebius else if (RB_RIGHT(elm, field) == NULL) \ 518290001Sglebius child = RB_LEFT(elm, field); \ 519290001Sglebius else { \ 520290001Sglebius struct type *left; \ 521290001Sglebius elm = RB_RIGHT(elm, field); \ 522290001Sglebius while ((left = RB_LEFT(elm, field))) \ 523290001Sglebius elm = left; \ 524290001Sglebius child = RB_RIGHT(elm, field); \ 525290001Sglebius parent = RB_PARENT(elm, field); \ 526290001Sglebius color = RB_COLOR(elm, field); \ 527290001Sglebius if (child) \ 528290001Sglebius RB_PARENT(child, field) = parent; \ 529290001Sglebius if (parent) { \ 530290001Sglebius if (RB_LEFT(parent, field) == elm) \ 531290001Sglebius RB_LEFT(parent, field) = child; \ 532290001Sglebius else \ 533290001Sglebius RB_RIGHT(parent, field) = child; \ 534290001Sglebius RB_AUGMENT(parent); \ 535290001Sglebius } else \ 536290001Sglebius RB_ROOT(head) = child; \ 537290001Sglebius if (RB_PARENT(elm, field) == old) \ 538290001Sglebius parent = elm; \ 539290001Sglebius (elm)->field = (old)->field; \ 540290001Sglebius if (RB_PARENT(old, field)) { \ 541290001Sglebius if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 542290001Sglebius RB_LEFT(RB_PARENT(old, field), field) = elm;\ 543290001Sglebius else \ 544290001Sglebius RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 545290001Sglebius RB_AUGMENT(RB_PARENT(old, field)); \ 546290001Sglebius } else \ 547290001Sglebius RB_ROOT(head) = elm; \ 548290001Sglebius RB_PARENT(RB_LEFT(old, field), field) = elm; \ 549290001Sglebius if (RB_RIGHT(old, field)) \ 550290001Sglebius RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 551290001Sglebius if (parent) { \ 552290001Sglebius left = parent; \ 553290001Sglebius do { \ 554290001Sglebius RB_AUGMENT(left); \ 555290001Sglebius } while ((left = RB_PARENT(left, field))); \ 556290001Sglebius } \ 557290001Sglebius goto color; \ 558290001Sglebius } \ 559290001Sglebius parent = RB_PARENT(elm, field); \ 560290001Sglebius color = RB_COLOR(elm, field); \ 561290001Sglebius if (child) \ 562290001Sglebius RB_PARENT(child, field) = parent; \ 563290001Sglebius if (parent) { \ 564290001Sglebius if (RB_LEFT(parent, field) == elm) \ 565290001Sglebius RB_LEFT(parent, field) = child; \ 566290001Sglebius else \ 567290001Sglebius RB_RIGHT(parent, field) = child; \ 568290001Sglebius RB_AUGMENT(parent); \ 569290001Sglebius } else \ 570290001Sglebius RB_ROOT(head) = child; \ 571290001Sglebiuscolor: \ 572290001Sglebius if (color == RB_BLACK) \ 573290001Sglebius name##_RB_REMOVE_COLOR(head, parent, child); \ 574290001Sglebius return (old); \ 575290001Sglebius} \ 576290001Sglebius \ 577290001Sglebius/* Inserts a node into the RB tree */ \ 578290001Sglebiusstruct type * \ 579290001Sglebiusname##_RB_INSERT(struct name *head, struct type *elm) \ 580290001Sglebius{ \ 581290001Sglebius struct type *tmp; \ 582290001Sglebius struct type *parent = NULL; \ 583290001Sglebius int comp = 0; \ 584290001Sglebius tmp = RB_ROOT(head); \ 585290001Sglebius while (tmp) { \ 586290001Sglebius parent = tmp; \ 587290001Sglebius comp = (cmp)(elm, parent); \ 588290001Sglebius if (comp < 0) \ 589290001Sglebius tmp = RB_LEFT(tmp, field); \ 590290001Sglebius else if (comp > 0) \ 591290001Sglebius tmp = RB_RIGHT(tmp, field); \ 592290001Sglebius else \ 593290001Sglebius return (tmp); \ 594290001Sglebius } \ 595290001Sglebius RB_SET(elm, parent, field); \ 596290001Sglebius if (parent != NULL) { \ 597290001Sglebius if (comp < 0) \ 598290001Sglebius RB_LEFT(parent, field) = elm; \ 599290001Sglebius else \ 600290001Sglebius RB_RIGHT(parent, field) = elm; \ 601290001Sglebius RB_AUGMENT(parent); \ 602290001Sglebius } else \ 603290001Sglebius RB_ROOT(head) = elm; \ 604290001Sglebius name##_RB_INSERT_COLOR(head, elm); \ 605290001Sglebius return (NULL); \ 606290001Sglebius} \ 607290001Sglebius \ 608290001Sglebius/* Finds the node with the same key as elm */ \ 609290001Sglebiusstruct type * \ 610290001Sglebiusname##_RB_FIND(struct name *head, struct type *elm) \ 611290001Sglebius{ \ 612290001Sglebius struct type *tmp = RB_ROOT(head); \ 613290001Sglebius int comp; \ 614290001Sglebius while (tmp) { \ 615290001Sglebius comp = cmp(elm, tmp); \ 616290001Sglebius if (comp < 0) \ 617290001Sglebius tmp = RB_LEFT(tmp, field); \ 618290001Sglebius else if (comp > 0) \ 619290001Sglebius tmp = RB_RIGHT(tmp, field); \ 620290001Sglebius else \ 621290001Sglebius return (tmp); \ 622290001Sglebius } \ 623290001Sglebius return (NULL); \ 624290001Sglebius} \ 625290001Sglebius \ 626290001Sglebiusstruct type * \ 627290001Sglebiusname##_RB_NEXT(struct type *elm) \ 628290001Sglebius{ \ 629290001Sglebius if (RB_RIGHT(elm, field)) { \ 630290001Sglebius elm = RB_RIGHT(elm, field); \ 631290001Sglebius while (RB_LEFT(elm, field)) \ 632290001Sglebius elm = RB_LEFT(elm, field); \ 633290001Sglebius } else { \ 634290001Sglebius if (RB_PARENT(elm, field) && \ 635290001Sglebius (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 636290001Sglebius elm = RB_PARENT(elm, field); \ 637290001Sglebius else { \ 638290001Sglebius while (RB_PARENT(elm, field) && \ 639290001Sglebius (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 640290001Sglebius elm = RB_PARENT(elm, field); \ 641290001Sglebius elm = RB_PARENT(elm, field); \ 642290001Sglebius } \ 643290001Sglebius } \ 644290001Sglebius return (elm); \ 645290001Sglebius} \ 646290001Sglebius \ 647290001Sglebiusstruct type * \ 648290001Sglebiusname##_RB_MINMAX(struct name *head, int val) \ 649290001Sglebius{ \ 650290001Sglebius struct type *tmp = RB_ROOT(head); \ 651290001Sglebius struct type *parent = NULL; \ 652290001Sglebius while (tmp) { \ 653290001Sglebius parent = tmp; \ 654290001Sglebius if (val < 0) \ 655290001Sglebius tmp = RB_LEFT(tmp, field); \ 656290001Sglebius else \ 657290001Sglebius tmp = RB_RIGHT(tmp, field); \ 658290001Sglebius } \ 659290001Sglebius return (parent); \ 660290001Sglebius} 661290001Sglebius 662290001Sglebius#define RB_NEGINF -1 663290001Sglebius#define RB_INF 1 664290001Sglebius 665290001Sglebius#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 666290001Sglebius#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 667290001Sglebius#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 668290001Sglebius#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 669290001Sglebius#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 670290001Sglebius#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 671290001Sglebius 672290001Sglebius#define RB_FOREACH(x, name, head) \ 673290001Sglebius for ((x) = RB_MIN(name, head); \ 674290001Sglebius (x) != NULL; \ 675290001Sglebius (x) = name##_RB_NEXT(x)) 676290001Sglebius 677290001Sglebius#endif /* _SYS_TREE_H_ */ 678