tree.h revision 154548
1135446Strhodes/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2153816Sdougb/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3135446Strhodes/* $FreeBSD: head/sys/sys/tree.h 154548 2006-01-19 07:20:20Z jasone $ */ 4135446Strhodes 5135446Strhodes/*- 6135446Strhodes * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7135446Strhodes * All rights reserved. 8135446Strhodes * 9135446Strhodes * Redistribution and use in source and binary forms, with or without 10135446Strhodes * modification, are permitted provided that the following conditions 11135446Strhodes * are met: 12135446Strhodes * 1. Redistributions of source code must retain the above copyright 13135446Strhodes * notice, this list of conditions and the following disclaimer. 14135446Strhodes * 2. Redistributions in binary form must reproduce the above copyright 15135446Strhodes * notice, this list of conditions and the following disclaimer in the 16135446Strhodes * documentation and/or other materials provided with the distribution. 17135446Strhodes * 18170222Sdougb * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19135446Strhodes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20135446Strhodes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21135446Strhodes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22135446Strhodes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23153816Sdougb * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24135446Strhodes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25135446Strhodes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26135446Strhodes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27135446Strhodes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28135446Strhodes */ 29135446Strhodes 30135446Strhodes#ifndef _SYS_TREE_H_ 31135446Strhodes#define _SYS_TREE_H_ 32135446Strhodes 33135446Strhodes#include <sys/cdefs.h> 34135446Strhodes 35135446Strhodes/* 36135446Strhodes * This file defines data structures for different types of trees: 37135446Strhodes * splay trees and red-black trees. 38135446Strhodes * 39135446Strhodes * A splay tree is a self-organizing data structure. Every operation 40135446Strhodes * on the tree causes a splay to happen. The splay moves the requested 41135446Strhodes * node to the root of the tree and partly rebalances it. 42135446Strhodes * 43170222Sdougb * This has the benefit that request locality causes faster lookups as 44170222Sdougb * the requested nodes move to the top of the tree. On the other hand, 45170222Sdougb * every lookup causes memory writes. 46170222Sdougb * 47170222Sdougb * The Balance Theorem bounds the total access time for m operations 48170222Sdougb * and n inserts on an initially empty tree as O((m + n)lg n). The 49170222Sdougb * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 50170222Sdougb * 51170222Sdougb * A red-black tree is a binary search tree with the node color as an 52170222Sdougb * extra attribute. It fulfills a set of conditions: 53170222Sdougb * - every search path from the root to a leaf consists of the 54170222Sdougb * same number of black nodes, 55170222Sdougb * - each red node (except for the root) has a black parent, 56170222Sdougb * - each leaf node is black. 57170222Sdougb * 58170222Sdougb * Every operation on a red-black tree is bounded as O(lg n). 59170222Sdougb * The maximum height of a red-black tree is 2lg (n+1). 60170222Sdougb */ 61170222Sdougb 62170222Sdougb#define SPLAY_HEAD(name, type) \ 63170222Sdougbstruct name { \ 64170222Sdougb struct type *sph_root; /* root of the tree */ \ 65170222Sdougb} 66170222Sdougb 67170222Sdougb#define SPLAY_INITIALIZER(root) \ 68170222Sdougb { NULL } 69170222Sdougb 70170222Sdougb#define SPLAY_INIT(root) do { \ 71170222Sdougb (root)->sph_root = NULL; \ 72170222Sdougb} while (/*CONSTCOND*/ 0) 73170222Sdougb 74170222Sdougb#define SPLAY_ENTRY(type) \ 75170222Sdougbstruct { \ 76170222Sdougb struct type *spe_left; /* left element */ \ 77170222Sdougb struct type *spe_right; /* right element */ \ 78170222Sdougb} 79170222Sdougb 80170222Sdougb#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 81135446Strhodes#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 82135446Strhodes#define SPLAY_ROOT(head) (head)->sph_root 83135446Strhodes#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 84135446Strhodes 85135446Strhodes/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 86135446Strhodes#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 87135446Strhodes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 88135446Strhodes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 89135446Strhodes (head)->sph_root = tmp; \ 90135446Strhodes} while (/*CONSTCOND*/ 0) 91135446Strhodes 92135446Strhodes#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 93135446Strhodes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 94135446Strhodes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95135446Strhodes (head)->sph_root = tmp; \ 96135446Strhodes} while (/*CONSTCOND*/ 0) 97135446Strhodes 98170222Sdougb#define SPLAY_LINKLEFT(head, tmp, field) do { \ 99135446Strhodes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 100135446Strhodes tmp = (head)->sph_root; \ 101135446Strhodes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 102135446Strhodes} while (/*CONSTCOND*/ 0) 103135446Strhodes 104135446Strhodes#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 105135446Strhodes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 106135446Strhodes tmp = (head)->sph_root; \ 107135446Strhodes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 108135446Strhodes} while (/*CONSTCOND*/ 0) 109135446Strhodes 110135446Strhodes#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 111135446Strhodes SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 112135446Strhodes SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 113135446Strhodes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 114135446Strhodes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 115135446Strhodes} while (/*CONSTCOND*/ 0) 116135446Strhodes 117135446Strhodes/* Generates prototypes and inline functions */ 118135446Strhodes 119135446Strhodes#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 120135446Strhodesvoid name##_SPLAY(struct name *, struct type *); \ 121135446Strhodesvoid name##_SPLAY_MINMAX(struct name *, int); \ 122135446Strhodesstruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 123135446Strhodesstruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 124135446Strhodes \ 125135446Strhodes/* Finds the node with the same key as elm */ \ 126135446Strhodesstatic __inline struct type * \ 127135446Strhodesname##_SPLAY_FIND(struct name *head, struct type *elm) \ 128135446Strhodes{ \ 129135446Strhodes if (SPLAY_EMPTY(head)) \ 130135446Strhodes return(NULL); \ 131135446Strhodes name##_SPLAY(head, elm); \ 132135446Strhodes if ((cmp)(elm, (head)->sph_root) == 0) \ 133135446Strhodes return (head->sph_root); \ 134135446Strhodes return (NULL); \ 135135446Strhodes} \ 136135446Strhodes \ 137135446Strhodesstatic __inline struct type * \ 138135446Strhodesname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 139135446Strhodes{ \ 140135446Strhodes name##_SPLAY(head, elm); \ 141135446Strhodes if (SPLAY_RIGHT(elm, field) != NULL) { \ 142135446Strhodes elm = SPLAY_RIGHT(elm, field); \ 143135446Strhodes while (SPLAY_LEFT(elm, field) != NULL) { \ 144135446Strhodes elm = SPLAY_LEFT(elm, field); \ 145135446Strhodes } \ 146135446Strhodes } else \ 147135446Strhodes elm = NULL; \ 148135446Strhodes return (elm); \ 149135446Strhodes} \ 150135446Strhodes \ 151135446Strhodesstatic __inline struct type * \ 152135446Strhodesname##_SPLAY_MIN_MAX(struct name *head, int val) \ 153135446Strhodes{ \ 154135446Strhodes name##_SPLAY_MINMAX(head, val); \ 155135446Strhodes return (SPLAY_ROOT(head)); \ 156135446Strhodes} 157135446Strhodes 158135446Strhodes/* Main splay operation. 159135446Strhodes * Moves node close to the key of elm to top 160135446Strhodes */ 161135446Strhodes#define SPLAY_GENERATE(name, type, field, cmp) \ 162135446Strhodesstruct type * \ 163135446Strhodesname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 164135446Strhodes{ \ 165135446Strhodes if (SPLAY_EMPTY(head)) { \ 166135446Strhodes SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 167135446Strhodes } else { \ 168135446Strhodes int __comp; \ 169135446Strhodes name##_SPLAY(head, elm); \ 170135446Strhodes __comp = (cmp)(elm, (head)->sph_root); \ 171135446Strhodes if(__comp < 0) { \ 172135446Strhodes SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 173135446Strhodes SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 174170222Sdougb SPLAY_LEFT((head)->sph_root, field) = NULL; \ 175135446Strhodes } else if (__comp > 0) { \ 176170222Sdougb SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 177135446Strhodes SPLAY_LEFT(elm, field) = (head)->sph_root; \ 178135446Strhodes SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 179135446Strhodes } else \ 180135446Strhodes return ((head)->sph_root); \ 181135446Strhodes } \ 182135446Strhodes (head)->sph_root = (elm); \ 183170222Sdougb return (NULL); \ 184135446Strhodes} \ 185135446Strhodes \ 186135446Strhodesstruct type * \ 187135446Strhodesname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 188135446Strhodes{ \ 189135446Strhodes struct type *__tmp; \ 190135446Strhodes if (SPLAY_EMPTY(head)) \ 191170222Sdougb return (NULL); \ 192135446Strhodes name##_SPLAY(head, elm); \ 193135446Strhodes if ((cmp)(elm, (head)->sph_root) == 0) { \ 194135446Strhodes if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 195170222Sdougb (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 196135446Strhodes } else { \ 197135446Strhodes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 198135446Strhodes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 199135446Strhodes name##_SPLAY(head, elm); \ 200135446Strhodes SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 201170222Sdougb } \ 202170222Sdougb return (elm); \ 203170222Sdougb } \ 204170222Sdougb return (NULL); \ 205135446Strhodes} \ 206135446Strhodes \ 207170222Sdougbvoid \ 208135446Strhodesname##_SPLAY(struct name *head, struct type *elm) \ 209170222Sdougb{ \ 210135446Strhodes struct type __node, *__left, *__right, *__tmp; \ 211170222Sdougb int __comp; \ 212135446Strhodes\ 213170222Sdougb SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 214135446Strhodes __left = __right = &__node; \ 215135446Strhodes\ 216135446Strhodes while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 217135446Strhodes if (__comp < 0) { \ 218135446Strhodes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 219135446Strhodes if (__tmp == NULL) \ 220170222Sdougb break; \ 221135446Strhodes if ((cmp)(elm, __tmp) < 0){ \ 222135446Strhodes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 223135446Strhodes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 224135446Strhodes break; \ 225170222Sdougb } \ 226170222Sdougb SPLAY_LINKLEFT(head, __right, field); \ 227170222Sdougb } else if (__comp > 0) { \ 228135446Strhodes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 229135446Strhodes if (__tmp == NULL) \ 230170222Sdougb break; \ 231135446Strhodes if ((cmp)(elm, __tmp) > 0){ \ 232135446Strhodes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 233135446Strhodes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 234135446Strhodes break; \ 235170222Sdougb } \ 236135446Strhodes SPLAY_LINKRIGHT(head, __left, field); \ 237135446Strhodes } \ 238170222Sdougb } \ 239135446Strhodes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 240135446Strhodes} \ 241135446Strhodes \ 242135446Strhodes/* Splay with either the minimum or the maximum element \ 243135446Strhodes * Used to find minimum or maximum element in tree. \ 244135446Strhodes */ \ 245135446Strhodesvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 246135446Strhodes{ \ 247135446Strhodes struct type __node, *__left, *__right, *__tmp; \ 248135446Strhodes\ 249135446Strhodes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 250135446Strhodes __left = __right = &__node; \ 251135446Strhodes\ 252135446Strhodes while (1) { \ 253135446Strhodes if (__comp < 0) { \ 254135446Strhodes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 255135446Strhodes if (__tmp == NULL) \ 256170222Sdougb break; \ 257135446Strhodes if (__comp < 0){ \ 258135446Strhodes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 259135446Strhodes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 260135446Strhodes break; \ 261135446Strhodes } \ 262135446Strhodes SPLAY_LINKLEFT(head, __right, field); \ 263135446Strhodes } else if (__comp > 0) { \ 264135446Strhodes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 265135446Strhodes if (__tmp == NULL) \ 266170222Sdougb break; \ 267135446Strhodes if (__comp > 0) { \ 268135446Strhodes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 269135446Strhodes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 270135446Strhodes break; \ 271135446Strhodes } \ 272135446Strhodes SPLAY_LINKRIGHT(head, __left, field); \ 273135446Strhodes } \ 274170222Sdougb } \ 275135446Strhodes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 276135446Strhodes} 277135446Strhodes 278135446Strhodes#define SPLAY_NEGINF -1 279135446Strhodes#define SPLAY_INF 1 280135446Strhodes 281135446Strhodes#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 282135446Strhodes#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 283135446Strhodes#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 284135446Strhodes#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 285135446Strhodes#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 286135446Strhodes : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 287135446Strhodes#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 288135446Strhodes : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 289135446Strhodes 290135446Strhodes#define SPLAY_FOREACH(x, name, head) \ 291135446Strhodes for ((x) = SPLAY_MIN(name, head); \ 292135446Strhodes (x) != NULL; \ 293135446Strhodes (x) = SPLAY_NEXT(name, head, x)) 294135446Strhodes 295135446Strhodes/* Macros that define a red-black tree */ 296135446Strhodes#define RB_HEAD(name, type) \ 297135446Strhodesstruct name { \ 298170222Sdougb struct type *rbh_root; /* root of the tree */ \ 299170222Sdougb} 300135446Strhodes 301170222Sdougb#define RB_INITIALIZER(root) \ 302170222Sdougb { NULL } 303170222Sdougb 304170222Sdougb#define RB_INIT(root) do { \ 305170222Sdougb (root)->rbh_root = NULL; \ 306170222Sdougb} while (/*CONSTCOND*/ 0) 307135446Strhodes 308170222Sdougb#define RB_BLACK 0 309135446Strhodes#define RB_RED 1 310170222Sdougb#define RB_ENTRY(type) \ 311170222Sdougbstruct { \ 312135446Strhodes struct type *rbe_left; /* left element */ \ 313135446Strhodes struct type *rbe_right; /* right element */ \ 314170222Sdougb struct type *rbe_parent; /* parent element */ \ 315135446Strhodes int rbe_color; /* node color */ \ 316135446Strhodes} 317170222Sdougb 318170222Sdougb#define RB_LEFT(elm, field) (elm)->field.rbe_left 319135446Strhodes#define RB_RIGHT(elm, field) (elm)->field.rbe_right 320170222Sdougb#define RB_PARENT(elm, field) (elm)->field.rbe_parent 321170222Sdougb#define RB_COLOR(elm, field) (elm)->field.rbe_color 322170222Sdougb#define RB_ROOT(head) (head)->rbh_root 323170222Sdougb#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 324170222Sdougb 325170222Sdougb#define RB_SET(elm, parent, field) do { \ 326170222Sdougb RB_PARENT(elm, field) = parent; \ 327170222Sdougb RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 328170222Sdougb RB_COLOR(elm, field) = RB_RED; \ 329170222Sdougb} while (/*CONSTCOND*/ 0) 330135446Strhodes 331135446Strhodes#define RB_SET_BLACKRED(black, red, field) do { \ 332135446Strhodes RB_COLOR(black, field) = RB_BLACK; \ 333135446Strhodes RB_COLOR(red, field) = RB_RED; \ 334135446Strhodes} while (/*CONSTCOND*/ 0) 335135446Strhodes 336135446Strhodes#ifndef RB_AUGMENT 337135446Strhodes#define RB_AUGMENT(x) do {} while (0) 338135446Strhodes#endif 339135446Strhodes 340135446Strhodes#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 341135446Strhodes (tmp) = RB_RIGHT(elm, field); \ 342135446Strhodes if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 343135446Strhodes RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 344135446Strhodes } \ 345135446Strhodes RB_AUGMENT(elm); \ 346135446Strhodes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 347135446Strhodes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 348135446Strhodes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 349135446Strhodes else \ 350135446Strhodes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 351135446Strhodes } else \ 352135446Strhodes (head)->rbh_root = (tmp); \ 353135446Strhodes RB_LEFT(tmp, field) = (elm); \ 354135446Strhodes RB_PARENT(elm, field) = (tmp); \ 355135446Strhodes RB_AUGMENT(tmp); \ 356135446Strhodes if ((RB_PARENT(tmp, field))) \ 357135446Strhodes RB_AUGMENT(RB_PARENT(tmp, field)); \ 358135446Strhodes} while (/*CONSTCOND*/ 0) 359135446Strhodes 360135446Strhodes#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 361135446Strhodes (tmp) = RB_LEFT(elm, field); \ 362135446Strhodes if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 363135446Strhodes RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 364135446Strhodes } \ 365135446Strhodes RB_AUGMENT(elm); \ 366135446Strhodes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 367135446Strhodes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 368135446Strhodes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 369135446Strhodes else \ 370135446Strhodes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 371135446Strhodes } else \ 372135446Strhodes (head)->rbh_root = (tmp); \ 373135446Strhodes RB_RIGHT(tmp, field) = (elm); \ 374135446Strhodes RB_PARENT(elm, field) = (tmp); \ 375135446Strhodes RB_AUGMENT(tmp); \ 376135446Strhodes if ((RB_PARENT(tmp, field))) \ 377135446Strhodes RB_AUGMENT(RB_PARENT(tmp, field)); \ 378135446Strhodes} while (/*CONSTCOND*/ 0) 379135446Strhodes 380135446Strhodes/* Generates prototypes and inline functions */ 381135446Strhodes#define RB_PROTOTYPE(name, type, field, cmp) \ 382135446Strhodes RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 383135446Strhodes#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 384135446Strhodes RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 385135446Strhodes#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 386135446Strhodesattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 387135446Strhodesattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 388135446Strhodesattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 389135446Strhodesattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 390135446Strhodesattr struct type *name##_RB_FIND(struct name *, struct type *); \ 391135446Strhodesattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 392135446Strhodesattr struct type *name##_RB_NEXT(struct type *); \ 393135446Strhodesattr struct type *name##_RB_MINMAX(struct name *, int); \ 394135446Strhodes \ 395135446Strhodes 396135446Strhodes/* Main rb operation. 397135446Strhodes * Moves node close to the key of elm to top 398135446Strhodes */ 399135446Strhodes#define RB_GENERATE(name, type, field, cmp) \ 400135446Strhodes RB_GENERATE_INTERNAL(name, type, field, cmp,) 401135446Strhodes#define RB_GENERATE_STATIC(name, type, field, cmp) \ 402135446Strhodes RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 403135446Strhodes#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 404135446Strhodesattr void \ 405135446Strhodesname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 406135446Strhodes{ \ 407135446Strhodes struct type *parent, *gparent, *tmp; \ 408135446Strhodes while ((parent = RB_PARENT(elm, field)) != NULL && \ 409135446Strhodes RB_COLOR(parent, field) == RB_RED) { \ 410135446Strhodes gparent = RB_PARENT(parent, field); \ 411135446Strhodes if (parent == RB_LEFT(gparent, field)) { \ 412135446Strhodes tmp = RB_RIGHT(gparent, field); \ 413135446Strhodes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 414135446Strhodes RB_COLOR(tmp, field) = RB_BLACK; \ 415135446Strhodes RB_SET_BLACKRED(parent, gparent, field);\ 416135446Strhodes elm = gparent; \ 417135446Strhodes continue; \ 418135446Strhodes } \ 419135446Strhodes if (RB_RIGHT(parent, field) == elm) { \ 420135446Strhodes RB_ROTATE_LEFT(head, parent, tmp, field);\ 421135446Strhodes tmp = parent; \ 422135446Strhodes parent = elm; \ 423135446Strhodes elm = tmp; \ 424135446Strhodes } \ 425135446Strhodes RB_SET_BLACKRED(parent, gparent, field); \ 426135446Strhodes RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 427135446Strhodes } else { \ 428135446Strhodes tmp = RB_LEFT(gparent, field); \ 429135446Strhodes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 430135446Strhodes RB_COLOR(tmp, field) = RB_BLACK; \ 431135446Strhodes RB_SET_BLACKRED(parent, gparent, field);\ 432135446Strhodes elm = gparent; \ 433135446Strhodes continue; \ 434135446Strhodes } \ 435135446Strhodes if (RB_LEFT(parent, field) == elm) { \ 436135446Strhodes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 437135446Strhodes tmp = parent; \ 438135446Strhodes parent = elm; \ 439135446Strhodes elm = tmp; \ 440135446Strhodes } \ 441135446Strhodes RB_SET_BLACKRED(parent, gparent, field); \ 442135446Strhodes RB_ROTATE_LEFT(head, gparent, tmp, field); \ 443135446Strhodes } \ 444135446Strhodes } \ 445135446Strhodes RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 446135446Strhodes} \ 447135446Strhodes \ 448135446Strhodesattr void \ 449135446Strhodesname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 450135446Strhodes{ \ 451135446Strhodes struct type *tmp; \ 452135446Strhodes while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 453135446Strhodes elm != RB_ROOT(head)) { \ 454135446Strhodes if (RB_LEFT(parent, field) == elm) { \ 455135446Strhodes tmp = RB_RIGHT(parent, field); \ 456135446Strhodes if (RB_COLOR(tmp, field) == RB_RED) { \ 457135446Strhodes RB_SET_BLACKRED(tmp, parent, field); \ 458135446Strhodes RB_ROTATE_LEFT(head, parent, tmp, field);\ 459135446Strhodes tmp = RB_RIGHT(parent, field); \ 460135446Strhodes } \ 461135446Strhodes if ((RB_LEFT(tmp, field) == NULL || \ 462135446Strhodes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 463135446Strhodes (RB_RIGHT(tmp, field) == NULL || \ 464135446Strhodes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 465135446Strhodes RB_COLOR(tmp, field) = RB_RED; \ 466135446Strhodes elm = parent; \ 467135446Strhodes parent = RB_PARENT(elm, field); \ 468135446Strhodes } else { \ 469135446Strhodes if (RB_RIGHT(tmp, field) == NULL || \ 470135446Strhodes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 471135446Strhodes struct type *oleft; \ 472135446Strhodes if ((oleft = RB_LEFT(tmp, field)) \ 473135446Strhodes != NULL) \ 474135446Strhodes RB_COLOR(oleft, field) = RB_BLACK;\ 475135446Strhodes RB_COLOR(tmp, field) = RB_RED; \ 476135446Strhodes RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 477135446Strhodes tmp = RB_RIGHT(parent, field); \ 478135446Strhodes } \ 479135446Strhodes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 480135446Strhodes RB_COLOR(parent, field) = RB_BLACK; \ 481135446Strhodes if (RB_RIGHT(tmp, field)) \ 482135446Strhodes RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 483135446Strhodes RB_ROTATE_LEFT(head, parent, tmp, field);\ 484135446Strhodes elm = RB_ROOT(head); \ 485135446Strhodes break; \ 486135446Strhodes } \ 487135446Strhodes } else { \ 488135446Strhodes tmp = RB_LEFT(parent, field); \ 489135446Strhodes if (RB_COLOR(tmp, field) == RB_RED) { \ 490135446Strhodes RB_SET_BLACKRED(tmp, parent, field); \ 491135446Strhodes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 492135446Strhodes tmp = RB_LEFT(parent, field); \ 493135446Strhodes } \ 494135446Strhodes if ((RB_LEFT(tmp, field) == NULL || \ 495135446Strhodes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 496135446Strhodes (RB_RIGHT(tmp, field) == NULL || \ 497135446Strhodes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 498135446Strhodes RB_COLOR(tmp, field) = RB_RED; \ 499135446Strhodes elm = parent; \ 500135446Strhodes parent = RB_PARENT(elm, field); \ 501135446Strhodes } else { \ 502135446Strhodes if (RB_LEFT(tmp, field) == NULL || \ 503135446Strhodes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 504135446Strhodes struct type *oright; \ 505135446Strhodes if ((oright = RB_RIGHT(tmp, field)) \ 506135446Strhodes != NULL) \ 507135446Strhodes RB_COLOR(oright, field) = RB_BLACK;\ 508135446Strhodes RB_COLOR(tmp, field) = RB_RED; \ 509135446Strhodes RB_ROTATE_LEFT(head, tmp, oright, field);\ 510135446Strhodes tmp = RB_LEFT(parent, field); \ 511135446Strhodes } \ 512135446Strhodes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 513135446Strhodes RB_COLOR(parent, field) = RB_BLACK; \ 514135446Strhodes if (RB_LEFT(tmp, field)) \ 515135446Strhodes RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 516135446Strhodes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 517135446Strhodes elm = RB_ROOT(head); \ 518135446Strhodes break; \ 519135446Strhodes } \ 520135446Strhodes } \ 521135446Strhodes } \ 522135446Strhodes if (elm) \ 523135446Strhodes RB_COLOR(elm, field) = RB_BLACK; \ 524135446Strhodes} \ 525135446Strhodes \ 526135446Strhodesattr struct type * \ 527135446Strhodesname##_RB_REMOVE(struct name *head, struct type *elm) \ 528135446Strhodes{ \ 529135446Strhodes struct type *child, *parent, *old = elm; \ 530135446Strhodes int color; \ 531135446Strhodes if (RB_LEFT(elm, field) == NULL) \ 532135446Strhodes child = RB_RIGHT(elm, field); \ 533135446Strhodes else if (RB_RIGHT(elm, field) == NULL) \ 534135446Strhodes child = RB_LEFT(elm, field); \ 535135446Strhodes else { \ 536135446Strhodes struct type *left; \ 537135446Strhodes elm = RB_RIGHT(elm, field); \ 538135446Strhodes while ((left = RB_LEFT(elm, field)) != NULL) \ 539135446Strhodes elm = left; \ 540135446Strhodes child = RB_RIGHT(elm, field); \ 541135446Strhodes parent = RB_PARENT(elm, field); \ 542135446Strhodes color = RB_COLOR(elm, field); \ 543135446Strhodes if (child) \ 544135446Strhodes RB_PARENT(child, field) = parent; \ 545135446Strhodes if (parent) { \ 546135446Strhodes if (RB_LEFT(parent, field) == elm) \ 547135446Strhodes RB_LEFT(parent, field) = child; \ 548135446Strhodes else \ 549135446Strhodes RB_RIGHT(parent, field) = child; \ 550135446Strhodes RB_AUGMENT(parent); \ 551135446Strhodes } else \ 552135446Strhodes RB_ROOT(head) = child; \ 553135446Strhodes if (RB_PARENT(elm, field) == old) \ 554135446Strhodes parent = elm; \ 555135446Strhodes (elm)->field = (old)->field; \ 556135446Strhodes if (RB_PARENT(old, field)) { \ 557135446Strhodes if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 558135446Strhodes RB_LEFT(RB_PARENT(old, field), field) = elm;\ 559135446Strhodes else \ 560135446Strhodes RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 561135446Strhodes RB_AUGMENT(RB_PARENT(old, field)); \ 562135446Strhodes } else \ 563135446Strhodes RB_ROOT(head) = elm; \ 564135446Strhodes RB_PARENT(RB_LEFT(old, field), field) = elm; \ 565135446Strhodes if (RB_RIGHT(old, field)) \ 566135446Strhodes RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 567135446Strhodes if (parent) { \ 568135446Strhodes left = parent; \ 569135446Strhodes do { \ 570135446Strhodes RB_AUGMENT(left); \ 571135446Strhodes } while ((left = RB_PARENT(left, field)) != NULL); \ 572135446Strhodes } \ 573135446Strhodes goto color; \ 574135446Strhodes } \ 575135446Strhodes parent = RB_PARENT(elm, field); \ 576135446Strhodes color = RB_COLOR(elm, field); \ 577135446Strhodes if (child) \ 578135446Strhodes RB_PARENT(child, field) = parent; \ 579135446Strhodes if (parent) { \ 580135446Strhodes if (RB_LEFT(parent, field) == elm) \ 581135446Strhodes RB_LEFT(parent, field) = child; \ 582135446Strhodes else \ 583135446Strhodes RB_RIGHT(parent, field) = child; \ 584135446Strhodes RB_AUGMENT(parent); \ 585135446Strhodes } else \ 586135446Strhodes RB_ROOT(head) = child; \ 587135446Strhodescolor: \ 588135446Strhodes if (color == RB_BLACK) \ 589135446Strhodes name##_RB_REMOVE_COLOR(head, parent, child); \ 590135446Strhodes return (old); \ 591135446Strhodes} \ 592135446Strhodes \ 593135446Strhodes/* Inserts a node into the RB tree */ \ 594135446Strhodesattr struct type * \ 595135446Strhodesname##_RB_INSERT(struct name *head, struct type *elm) \ 596135446Strhodes{ \ 597135446Strhodes struct type *tmp; \ 598135446Strhodes struct type *parent = NULL; \ 599135446Strhodes int comp = 0; \ 600135446Strhodes tmp = RB_ROOT(head); \ 601135446Strhodes while (tmp) { \ 602135446Strhodes parent = tmp; \ 603135446Strhodes comp = (cmp)(elm, parent); \ 604135446Strhodes if (comp < 0) \ 605135446Strhodes tmp = RB_LEFT(tmp, field); \ 606135446Strhodes else if (comp > 0) \ 607135446Strhodes tmp = RB_RIGHT(tmp, field); \ 608135446Strhodes else \ 609135446Strhodes return (tmp); \ 610135446Strhodes } \ 611135446Strhodes RB_SET(elm, parent, field); \ 612135446Strhodes if (parent != NULL) { \ 613135446Strhodes if (comp < 0) \ 614135446Strhodes RB_LEFT(parent, field) = elm; \ 615135446Strhodes else \ 616135446Strhodes RB_RIGHT(parent, field) = elm; \ 617135446Strhodes RB_AUGMENT(parent); \ 618135446Strhodes } else \ 619135446Strhodes RB_ROOT(head) = elm; \ 620135446Strhodes name##_RB_INSERT_COLOR(head, elm); \ 621135446Strhodes return (NULL); \ 622135446Strhodes} \ 623135446Strhodes \ 624135446Strhodes/* Finds the node with the same key as elm */ \ 625135446Strhodesattr struct type * \ 626135446Strhodesname##_RB_FIND(struct name *head, struct type *elm) \ 627135446Strhodes{ \ 628135446Strhodes struct type *tmp = RB_ROOT(head); \ 629135446Strhodes int comp; \ 630135446Strhodes while (tmp) { \ 631135446Strhodes comp = cmp(elm, tmp); \ 632135446Strhodes if (comp < 0) \ 633135446Strhodes tmp = RB_LEFT(tmp, field); \ 634135446Strhodes else if (comp > 0) \ 635135446Strhodes tmp = RB_RIGHT(tmp, field); \ 636135446Strhodes else \ 637135446Strhodes return (tmp); \ 638135446Strhodes } \ 639135446Strhodes return (NULL); \ 640135446Strhodes} \ 641135446Strhodes \ 642135446Strhodes/* Finds the first node greater than or equal to the search key */ \ 643135446Strhodesattr struct type * \ 644135446Strhodesname##_RB_NFIND(struct name *head, struct type *elm) \ 645135446Strhodes{ \ 646135446Strhodes struct type *ret = RB_ROOT(head); \ 647135446Strhodes struct type *tmp; \ 648135446Strhodes int comp; \ 649135446Strhodes while (ret && (comp = cmp(elm, ret)) != 0) { \ 650135446Strhodes if (comp < 0) { \ 651135446Strhodes if ((tmp = RB_LEFT(ret, field)) == NULL) \ 652135446Strhodes break; \ 653135446Strhodes ret = tmp; \ 654135446Strhodes } else { \ 655135446Strhodes if ((tmp = RB_RIGHT(ret, field)) == NULL) { \ 656135446Strhodes tmp = ret; \ 657135446Strhodes ret = RB_PARENT(ret, field); \ 658135446Strhodes while (ret && tmp == RB_RIGHT(ret, \ 659135446Strhodes field)) { \ 660135446Strhodes tmp = ret; \ 661135446Strhodes ret = RB_PARENT(ret, field); \ 662135446Strhodes } \ 663135446Strhodes break; \ 664135446Strhodes } \ 665135446Strhodes ret = tmp; \ 666135446Strhodes } \ 667135446Strhodes } \ 668135446Strhodes return (ret); \ 669135446Strhodes} \ 670135446Strhodes \ 671135446Strhodes/* ARGSUSED */ \ 672135446Strhodesattr struct type * \ 673135446Strhodesname##_RB_NEXT(struct type *elm) \ 674135446Strhodes{ \ 675135446Strhodes if (RB_RIGHT(elm, field)) { \ 676135446Strhodes elm = RB_RIGHT(elm, field); \ 677135446Strhodes while (RB_LEFT(elm, field)) \ 678135446Strhodes elm = RB_LEFT(elm, field); \ 679135446Strhodes } else { \ 680135446Strhodes if (RB_PARENT(elm, field) && \ 681135446Strhodes (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 682135446Strhodes elm = RB_PARENT(elm, field); \ 683135446Strhodes else { \ 684135446Strhodes while (RB_PARENT(elm, field) && \ 685135446Strhodes (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 686135446Strhodes elm = RB_PARENT(elm, field); \ 687135446Strhodes elm = RB_PARENT(elm, field); \ 688135446Strhodes } \ 689135446Strhodes } \ 690135446Strhodes return (elm); \ 691135446Strhodes} \ 692135446Strhodes \ 693135446Strhodesattr struct type * \ 694135446Strhodesname##_RB_MINMAX(struct name *head, int val) \ 695135446Strhodes{ \ 696135446Strhodes struct type *tmp = RB_ROOT(head); \ 697135446Strhodes struct type *parent = NULL; \ 698135446Strhodes while (tmp) { \ 699135446Strhodes parent = tmp; \ 700135446Strhodes if (val < 0) \ 701135446Strhodes tmp = RB_LEFT(tmp, field); \ 702135446Strhodes else \ 703135446Strhodes tmp = RB_RIGHT(tmp, field); \ 704135446Strhodes } \ 705135446Strhodes return (parent); \ 706135446Strhodes} 707135446Strhodes 708135446Strhodes#define RB_NEGINF -1 709135446Strhodes#define RB_INF 1 710135446Strhodes 711135446Strhodes#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 712135446Strhodes#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 713135446Strhodes#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 714135446Strhodes#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 715135446Strhodes#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 716135446Strhodes#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 717135446Strhodes#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 718135446Strhodes 719135446Strhodes#define RB_FOREACH(x, name, head) \ 720135446Strhodes for ((x) = RB_MIN(name, head); \ 721135446Strhodes (x) != NULL; \ 722135446Strhodes (x) = name##_RB_NEXT(x)) 723135446Strhodes 724135446Strhodes#endif /* _SYS_TREE_H_ */ 725135446Strhodes