tree.h revision 225736
1240116Smarcel/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2240116Smarcel/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3240116Smarcel/* $FreeBSD: stable/9/sys/sys/tree.h 189204 2009-03-01 04:57:23Z bms $ */ 4240116Smarcel 5240116Smarcel/*- 6240116Smarcel * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7240116Smarcel * All rights reserved. 8240116Smarcel * 9240116Smarcel * Redistribution and use in source and binary forms, with or without 10240116Smarcel * modification, are permitted provided that the following conditions 11240116Smarcel * are met: 12240116Smarcel * 1. Redistributions of source code must retain the above copyright 13240116Smarcel * notice, this list of conditions and the following disclaimer. 14240116Smarcel * 2. Redistributions in binary form must reproduce the above copyright 15240116Smarcel * notice, this list of conditions and the following disclaimer in the 16240116Smarcel * documentation and/or other materials provided with the distribution. 17240116Smarcel * 18240116Smarcel * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19240116Smarcel * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20240116Smarcel * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21240116Smarcel * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22240116Smarcel * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23240116Smarcel * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24240116Smarcel * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25240116Smarcel * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26240116Smarcel * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27240116Smarcel * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28240116Smarcel */ 29240116Smarcel 30240116Smarcel#ifndef _SYS_TREE_H_ 31240116Smarcel#define _SYS_TREE_H_ 32240116Smarcel 33240116Smarcel#include <sys/cdefs.h> 34240116Smarcel 35240116Smarcel/* 36240116Smarcel * This file defines data structures for different types of trees: 37240116Smarcel * splay trees and red-black trees. 38240116Smarcel * 39240116Smarcel * A splay tree is a self-organizing data structure. Every operation 40240116Smarcel * on the tree causes a splay to happen. The splay moves the requested 41240116Smarcel * node to the root of the tree and partly rebalances it. 42240116Smarcel * 43240116Smarcel * This has the benefit that request locality causes faster lookups as 44240116Smarcel * the requested nodes move to the top of the tree. On the other hand, 45240116Smarcel * every lookup causes memory writes. 46240116Smarcel * 47240116Smarcel * The Balance Theorem bounds the total access time for m operations 48240116Smarcel * and n inserts on an initially empty tree as O((m + n)lg n). The 49240116Smarcel * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 50240116Smarcel * 51240116Smarcel * A red-black tree is a binary search tree with the node color as an 52240116Smarcel * extra attribute. It fulfills a set of conditions: 53240116Smarcel * - every search path from the root to a leaf consists of the 54240116Smarcel * same number of black nodes, 55240116Smarcel * - each red node (except for the root) has a black parent, 56240116Smarcel * - each leaf node is black. 57240116Smarcel * 58240116Smarcel * Every operation on a red-black tree is bounded as O(lg n). 59240116Smarcel * The maximum height of a red-black tree is 2lg (n+1). 60240116Smarcel */ 61240116Smarcel 62240116Smarcel#define SPLAY_HEAD(name, type) \ 63240116Smarcelstruct name { \ 64240116Smarcel struct type *sph_root; /* root of the tree */ \ 65240116Smarcel} 66240116Smarcel 67240116Smarcel#define SPLAY_INITIALIZER(root) \ 68240116Smarcel { NULL } 69240116Smarcel 70240116Smarcel#define SPLAY_INIT(root) do { \ 71240116Smarcel (root)->sph_root = NULL; \ 72240116Smarcel} while (/*CONSTCOND*/ 0) 73240116Smarcel 74240116Smarcel#define SPLAY_ENTRY(type) \ 75240116Smarcelstruct { \ 76240116Smarcel struct type *spe_left; /* left element */ \ 77240116Smarcel struct type *spe_right; /* right element */ \ 78240116Smarcel} 79240116Smarcel 80240116Smarcel#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 81240116Smarcel#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 82240116Smarcel#define SPLAY_ROOT(head) (head)->sph_root 83240116Smarcel#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 84240116Smarcel 85240116Smarcel/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 86240116Smarcel#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 87240116Smarcel SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 88240116Smarcel SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 89240116Smarcel (head)->sph_root = tmp; \ 90240116Smarcel} while (/*CONSTCOND*/ 0) 91240116Smarcel 92240116Smarcel#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 93240116Smarcel SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 94240116Smarcel SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95240116Smarcel (head)->sph_root = tmp; \ 96240116Smarcel} while (/*CONSTCOND*/ 0) 97240116Smarcel 98240116Smarcel#define SPLAY_LINKLEFT(head, tmp, field) do { \ 99240116Smarcel SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 100240116Smarcel tmp = (head)->sph_root; \ 101240116Smarcel (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 102240116Smarcel} while (/*CONSTCOND*/ 0) 103240116Smarcel 104240116Smarcel#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 105240116Smarcel SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 106240116Smarcel tmp = (head)->sph_root; \ 107240116Smarcel (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 108240116Smarcel} while (/*CONSTCOND*/ 0) 109240116Smarcel 110240116Smarcel#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 111240116Smarcel SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 112240116Smarcel SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 113240116Smarcel SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 114240116Smarcel SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 115240116Smarcel} while (/*CONSTCOND*/ 0) 116240116Smarcel 117240116Smarcel/* Generates prototypes and inline functions */ 118240116Smarcel 119240116Smarcel#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 120240116Smarcelvoid name##_SPLAY(struct name *, struct type *); \ 121240116Smarcelvoid name##_SPLAY_MINMAX(struct name *, int); \ 122240116Smarcelstruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 123240116Smarcelstruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 124240116Smarcel \ 125240116Smarcel/* Finds the node with the same key as elm */ \ 126240116Smarcelstatic __inline struct type * \ 127240116Smarcelname##_SPLAY_FIND(struct name *head, struct type *elm) \ 128240116Smarcel{ \ 129240116Smarcel if (SPLAY_EMPTY(head)) \ 130240116Smarcel return(NULL); \ 131240116Smarcel name##_SPLAY(head, elm); \ 132240116Smarcel if ((cmp)(elm, (head)->sph_root) == 0) \ 133240116Smarcel return (head->sph_root); \ 134240116Smarcel return (NULL); \ 135240116Smarcel} \ 136240116Smarcel \ 137240116Smarcelstatic __inline struct type * \ 138240116Smarcelname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 139240116Smarcel{ \ 140240116Smarcel name##_SPLAY(head, elm); \ 141240116Smarcel if (SPLAY_RIGHT(elm, field) != NULL) { \ 142240116Smarcel elm = SPLAY_RIGHT(elm, field); \ 143240116Smarcel while (SPLAY_LEFT(elm, field) != NULL) { \ 144240116Smarcel elm = SPLAY_LEFT(elm, field); \ 145240116Smarcel } \ 146240116Smarcel } else \ 147240116Smarcel elm = NULL; \ 148240116Smarcel return (elm); \ 149240116Smarcel} \ 150240116Smarcel \ 151240116Smarcelstatic __inline struct type * \ 152240116Smarcelname##_SPLAY_MIN_MAX(struct name *head, int val) \ 153240116Smarcel{ \ 154240116Smarcel name##_SPLAY_MINMAX(head, val); \ 155240116Smarcel return (SPLAY_ROOT(head)); \ 156240116Smarcel} 157240116Smarcel 158240116Smarcel/* Main splay operation. 159240116Smarcel * Moves node close to the key of elm to top 160240116Smarcel */ 161240116Smarcel#define SPLAY_GENERATE(name, type, field, cmp) \ 162240116Smarcelstruct type * \ 163240116Smarcelname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 164240116Smarcel{ \ 165240116Smarcel if (SPLAY_EMPTY(head)) { \ 166240116Smarcel SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 167240116Smarcel } else { \ 168240116Smarcel int __comp; \ 169240116Smarcel name##_SPLAY(head, elm); \ 170240116Smarcel __comp = (cmp)(elm, (head)->sph_root); \ 171240116Smarcel if(__comp < 0) { \ 172240116Smarcel SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 173240116Smarcel SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 174240116Smarcel SPLAY_LEFT((head)->sph_root, field) = NULL; \ 175240116Smarcel } else if (__comp > 0) { \ 176240116Smarcel SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 177240116Smarcel SPLAY_LEFT(elm, field) = (head)->sph_root; \ 178240116Smarcel SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 179240116Smarcel } else \ 180240116Smarcel return ((head)->sph_root); \ 181240116Smarcel } \ 182240116Smarcel (head)->sph_root = (elm); \ 183240116Smarcel return (NULL); \ 184240116Smarcel} \ 185240116Smarcel \ 186240116Smarcelstruct type * \ 187240116Smarcelname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 188240116Smarcel{ \ 189240116Smarcel struct type *__tmp; \ 190240116Smarcel if (SPLAY_EMPTY(head)) \ 191240116Smarcel return (NULL); \ 192240116Smarcel name##_SPLAY(head, elm); \ 193240116Smarcel if ((cmp)(elm, (head)->sph_root) == 0) { \ 194240116Smarcel if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 195240116Smarcel (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 196240116Smarcel } else { \ 197240116Smarcel __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 198240116Smarcel (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 199240116Smarcel name##_SPLAY(head, elm); \ 200240116Smarcel SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 201240116Smarcel } \ 202240116Smarcel return (elm); \ 203240116Smarcel } \ 204240116Smarcel return (NULL); \ 205240116Smarcel} \ 206240116Smarcel \ 207240116Smarcelvoid \ 208240116Smarcelname##_SPLAY(struct name *head, struct type *elm) \ 209240116Smarcel{ \ 210240116Smarcel struct type __node, *__left, *__right, *__tmp; \ 211240116Smarcel int __comp; \ 212240116Smarcel\ 213240116Smarcel SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 214240116Smarcel __left = __right = &__node; \ 215240116Smarcel\ 216240116Smarcel while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 217240116Smarcel if (__comp < 0) { \ 218240116Smarcel __tmp = SPLAY_LEFT((head)->sph_root, field); \ 219240116Smarcel if (__tmp == NULL) \ 220240116Smarcel break; \ 221240116Smarcel if ((cmp)(elm, __tmp) < 0){ \ 222240116Smarcel SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 223240116Smarcel if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 224240116Smarcel break; \ 225240116Smarcel } \ 226240116Smarcel SPLAY_LINKLEFT(head, __right, field); \ 227240116Smarcel } else if (__comp > 0) { \ 228240116Smarcel __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 229240116Smarcel if (__tmp == NULL) \ 230240116Smarcel break; \ 231240116Smarcel if ((cmp)(elm, __tmp) > 0){ \ 232240116Smarcel SPLAY_ROTATE_LEFT(head, __tmp, field); \ 233240116Smarcel if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 234240116Smarcel break; \ 235240116Smarcel } \ 236240116Smarcel SPLAY_LINKRIGHT(head, __left, field); \ 237240116Smarcel } \ 238240116Smarcel } \ 239240116Smarcel SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 240240116Smarcel} \ 241240116Smarcel \ 242240116Smarcel/* Splay with either the minimum or the maximum element \ 243240116Smarcel * Used to find minimum or maximum element in tree. \ 244240116Smarcel */ \ 245240116Smarcelvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 246240116Smarcel{ \ 247240116Smarcel struct type __node, *__left, *__right, *__tmp; \ 248240116Smarcel\ 249240116Smarcel SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 250240116Smarcel __left = __right = &__node; \ 251240116Smarcel\ 252240116Smarcel while (1) { \ 253240116Smarcel if (__comp < 0) { \ 254240116Smarcel __tmp = SPLAY_LEFT((head)->sph_root, field); \ 255240116Smarcel if (__tmp == NULL) \ 256240116Smarcel break; \ 257240116Smarcel if (__comp < 0){ \ 258240116Smarcel SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 259240116Smarcel if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 260240116Smarcel break; \ 261240116Smarcel } \ 262240116Smarcel SPLAY_LINKLEFT(head, __right, field); \ 263240116Smarcel } else if (__comp > 0) { \ 264240116Smarcel __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 265240116Smarcel if (__tmp == NULL) \ 266240116Smarcel break; \ 267240116Smarcel if (__comp > 0) { \ 268240116Smarcel SPLAY_ROTATE_LEFT(head, __tmp, field); \ 269240116Smarcel if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 270240116Smarcel break; \ 271240116Smarcel } \ 272240116Smarcel SPLAY_LINKRIGHT(head, __left, field); \ 273240116Smarcel } \ 274240116Smarcel } \ 275240116Smarcel SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 276240116Smarcel} 277240116Smarcel 278240116Smarcel#define SPLAY_NEGINF -1 279240116Smarcel#define SPLAY_INF 1 280240116Smarcel 281240116Smarcel#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 282240116Smarcel#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 283240116Smarcel#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 284240116Smarcel#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 285240116Smarcel#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 286240116Smarcel : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 287240116Smarcel#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 288240116Smarcel : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 289240116Smarcel 290240116Smarcel#define SPLAY_FOREACH(x, name, head) \ 291240116Smarcel for ((x) = SPLAY_MIN(name, head); \ 292240116Smarcel (x) != NULL; \ 293240116Smarcel (x) = SPLAY_NEXT(name, head, x)) 294240116Smarcel 295240116Smarcel/* Macros that define a red-black tree */ 296240116Smarcel#define RB_HEAD(name, type) \ 297240116Smarcelstruct name { \ 298240116Smarcel struct type *rbh_root; /* root of the tree */ \ 299240116Smarcel} 300240116Smarcel 301240116Smarcel#define RB_INITIALIZER(root) \ 302240116Smarcel { NULL } 303240116Smarcel 304240116Smarcel#define RB_INIT(root) do { \ 305240116Smarcel (root)->rbh_root = NULL; \ 306240116Smarcel} while (/*CONSTCOND*/ 0) 307240116Smarcel 308240116Smarcel#define RB_BLACK 0 309240116Smarcel#define RB_RED 1 310240116Smarcel#define RB_ENTRY(type) \ 311240116Smarcelstruct { \ 312240116Smarcel struct type *rbe_left; /* left element */ \ 313240116Smarcel struct type *rbe_right; /* right element */ \ 314240116Smarcel struct type *rbe_parent; /* parent element */ \ 315240116Smarcel int rbe_color; /* node color */ \ 316240116Smarcel} 317240116Smarcel 318240116Smarcel#define RB_LEFT(elm, field) (elm)->field.rbe_left 319240116Smarcel#define RB_RIGHT(elm, field) (elm)->field.rbe_right 320240116Smarcel#define RB_PARENT(elm, field) (elm)->field.rbe_parent 321240116Smarcel#define RB_COLOR(elm, field) (elm)->field.rbe_color 322240116Smarcel#define RB_ROOT(head) (head)->rbh_root 323240116Smarcel#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 324240116Smarcel 325240116Smarcel#define RB_SET(elm, parent, field) do { \ 326240116Smarcel RB_PARENT(elm, field) = parent; \ 327240116Smarcel RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 328240116Smarcel RB_COLOR(elm, field) = RB_RED; \ 329240116Smarcel} while (/*CONSTCOND*/ 0) 330240116Smarcel 331240116Smarcel#define RB_SET_BLACKRED(black, red, field) do { \ 332240116Smarcel RB_COLOR(black, field) = RB_BLACK; \ 333240116Smarcel RB_COLOR(red, field) = RB_RED; \ 334240116Smarcel} while (/*CONSTCOND*/ 0) 335240116Smarcel 336240116Smarcel#ifndef RB_AUGMENT 337240116Smarcel#define RB_AUGMENT(x) do {} while (0) 338240116Smarcel#endif 339240116Smarcel 340240116Smarcel#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 341240116Smarcel (tmp) = RB_RIGHT(elm, field); \ 342240116Smarcel if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 343240116Smarcel RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 344240116Smarcel } \ 345240116Smarcel RB_AUGMENT(elm); \ 346240116Smarcel if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 347240116Smarcel if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 348240116Smarcel RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 349240116Smarcel else \ 350240116Smarcel RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 351240116Smarcel } else \ 352240116Smarcel (head)->rbh_root = (tmp); \ 353240116Smarcel RB_LEFT(tmp, field) = (elm); \ 354240116Smarcel RB_PARENT(elm, field) = (tmp); \ 355240116Smarcel RB_AUGMENT(tmp); \ 356240116Smarcel if ((RB_PARENT(tmp, field))) \ 357240116Smarcel RB_AUGMENT(RB_PARENT(tmp, field)); \ 358240116Smarcel} while (/*CONSTCOND*/ 0) 359240116Smarcel 360240116Smarcel#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 361240116Smarcel (tmp) = RB_LEFT(elm, field); \ 362240116Smarcel if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 363240116Smarcel RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 364240116Smarcel } \ 365240116Smarcel RB_AUGMENT(elm); \ 366240116Smarcel if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 367240116Smarcel if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 368240116Smarcel RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 369240116Smarcel else \ 370240116Smarcel RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 371240116Smarcel } else \ 372240116Smarcel (head)->rbh_root = (tmp); \ 373240116Smarcel RB_RIGHT(tmp, field) = (elm); \ 374240116Smarcel RB_PARENT(elm, field) = (tmp); \ 375240116Smarcel RB_AUGMENT(tmp); \ 376240116Smarcel if ((RB_PARENT(tmp, field))) \ 377240116Smarcel RB_AUGMENT(RB_PARENT(tmp, field)); \ 378240116Smarcel} while (/*CONSTCOND*/ 0) 379240116Smarcel 380240116Smarcel/* Generates prototypes and inline functions */ 381240116Smarcel#define RB_PROTOTYPE(name, type, field, cmp) \ 382240116Smarcel RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 383240116Smarcel#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 384240116Smarcel RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 385240116Smarcel#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 386240116Smarcelattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 387240116Smarcelattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 388240116Smarcelattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 389240116Smarcelattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 390240116Smarcelattr struct type *name##_RB_FIND(struct name *, struct type *); \ 391240116Smarcelattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 392240116Smarcelattr struct type *name##_RB_NEXT(struct type *); \ 393240116Smarcelattr struct type *name##_RB_PREV(struct type *); \ 394240116Smarcelattr struct type *name##_RB_MINMAX(struct name *, int); \ 395240116Smarcel \ 396240116Smarcel 397240116Smarcel/* Main rb operation. 398240116Smarcel * Moves node close to the key of elm to top 399240116Smarcel */ 400240116Smarcel#define RB_GENERATE(name, type, field, cmp) \ 401240116Smarcel RB_GENERATE_INTERNAL(name, type, field, cmp,) 402240116Smarcel#define RB_GENERATE_STATIC(name, type, field, cmp) \ 403240116Smarcel RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 404240116Smarcel#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 405240116Smarcelattr void \ 406240116Smarcelname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 407240116Smarcel{ \ 408240116Smarcel struct type *parent, *gparent, *tmp; \ 409240116Smarcel while ((parent = RB_PARENT(elm, field)) != NULL && \ 410240116Smarcel RB_COLOR(parent, field) == RB_RED) { \ 411240116Smarcel gparent = RB_PARENT(parent, field); \ 412240116Smarcel if (parent == RB_LEFT(gparent, field)) { \ 413240116Smarcel tmp = RB_RIGHT(gparent, field); \ 414240116Smarcel if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 415240116Smarcel RB_COLOR(tmp, field) = RB_BLACK; \ 416240116Smarcel RB_SET_BLACKRED(parent, gparent, field);\ 417240116Smarcel elm = gparent; \ 418240116Smarcel continue; \ 419240116Smarcel } \ 420240116Smarcel if (RB_RIGHT(parent, field) == elm) { \ 421240116Smarcel RB_ROTATE_LEFT(head, parent, tmp, field);\ 422240116Smarcel tmp = parent; \ 423240116Smarcel parent = elm; \ 424240116Smarcel elm = tmp; \ 425240116Smarcel } \ 426240116Smarcel RB_SET_BLACKRED(parent, gparent, field); \ 427240116Smarcel RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 428240116Smarcel } else { \ 429240116Smarcel tmp = RB_LEFT(gparent, field); \ 430240116Smarcel if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 431240116Smarcel RB_COLOR(tmp, field) = RB_BLACK; \ 432240116Smarcel RB_SET_BLACKRED(parent, gparent, field);\ 433240116Smarcel elm = gparent; \ 434240116Smarcel continue; \ 435240116Smarcel } \ 436240116Smarcel if (RB_LEFT(parent, field) == elm) { \ 437240116Smarcel RB_ROTATE_RIGHT(head, parent, tmp, field);\ 438240116Smarcel tmp = parent; \ 439240116Smarcel parent = elm; \ 440240116Smarcel elm = tmp; \ 441240116Smarcel } \ 442240116Smarcel RB_SET_BLACKRED(parent, gparent, field); \ 443240116Smarcel RB_ROTATE_LEFT(head, gparent, tmp, field); \ 444240116Smarcel } \ 445240116Smarcel } \ 446240116Smarcel RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 447240116Smarcel} \ 448240116Smarcel \ 449240116Smarcelattr void \ 450240116Smarcelname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 451240116Smarcel{ \ 452240116Smarcel struct type *tmp; \ 453240116Smarcel while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 454240116Smarcel elm != RB_ROOT(head)) { \ 455240116Smarcel if (RB_LEFT(parent, field) == elm) { \ 456240116Smarcel tmp = RB_RIGHT(parent, field); \ 457240116Smarcel if (RB_COLOR(tmp, field) == RB_RED) { \ 458240116Smarcel RB_SET_BLACKRED(tmp, parent, field); \ 459240116Smarcel RB_ROTATE_LEFT(head, parent, tmp, field);\ 460240116Smarcel tmp = RB_RIGHT(parent, field); \ 461240116Smarcel } \ 462240116Smarcel if ((RB_LEFT(tmp, field) == NULL || \ 463240116Smarcel RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 464240116Smarcel (RB_RIGHT(tmp, field) == NULL || \ 465240116Smarcel RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 466240116Smarcel RB_COLOR(tmp, field) = RB_RED; \ 467240116Smarcel elm = parent; \ 468240116Smarcel parent = RB_PARENT(elm, field); \ 469240116Smarcel } else { \ 470240116Smarcel if (RB_RIGHT(tmp, field) == NULL || \ 471240116Smarcel RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 472240116Smarcel struct type *oleft; \ 473240116Smarcel if ((oleft = RB_LEFT(tmp, field)) \ 474240116Smarcel != NULL) \ 475240116Smarcel RB_COLOR(oleft, field) = RB_BLACK;\ 476240116Smarcel RB_COLOR(tmp, field) = RB_RED; \ 477240116Smarcel RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 478240116Smarcel tmp = RB_RIGHT(parent, field); \ 479240116Smarcel } \ 480240116Smarcel RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 481240116Smarcel RB_COLOR(parent, field) = RB_BLACK; \ 482240116Smarcel if (RB_RIGHT(tmp, field)) \ 483240116Smarcel RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 484240116Smarcel RB_ROTATE_LEFT(head, parent, tmp, field);\ 485240116Smarcel elm = RB_ROOT(head); \ 486240116Smarcel break; \ 487240116Smarcel } \ 488240116Smarcel } else { \ 489240116Smarcel tmp = RB_LEFT(parent, field); \ 490240116Smarcel if (RB_COLOR(tmp, field) == RB_RED) { \ 491240116Smarcel RB_SET_BLACKRED(tmp, parent, field); \ 492240116Smarcel RB_ROTATE_RIGHT(head, parent, tmp, field);\ 493240116Smarcel tmp = RB_LEFT(parent, field); \ 494240116Smarcel } \ 495240116Smarcel if ((RB_LEFT(tmp, field) == NULL || \ 496240116Smarcel RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 497240116Smarcel (RB_RIGHT(tmp, field) == NULL || \ 498240116Smarcel RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 499240116Smarcel RB_COLOR(tmp, field) = RB_RED; \ 500240116Smarcel elm = parent; \ 501240116Smarcel parent = RB_PARENT(elm, field); \ 502240116Smarcel } else { \ 503240116Smarcel if (RB_LEFT(tmp, field) == NULL || \ 504240116Smarcel RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 505240116Smarcel struct type *oright; \ 506240116Smarcel if ((oright = RB_RIGHT(tmp, field)) \ 507240116Smarcel != NULL) \ 508240116Smarcel RB_COLOR(oright, field) = RB_BLACK;\ 509240116Smarcel RB_COLOR(tmp, field) = RB_RED; \ 510240116Smarcel RB_ROTATE_LEFT(head, tmp, oright, field);\ 511240116Smarcel tmp = RB_LEFT(parent, field); \ 512240116Smarcel } \ 513240116Smarcel RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 514240116Smarcel RB_COLOR(parent, field) = RB_BLACK; \ 515240116Smarcel if (RB_LEFT(tmp, field)) \ 516240116Smarcel RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 517240116Smarcel RB_ROTATE_RIGHT(head, parent, tmp, field);\ 518240116Smarcel elm = RB_ROOT(head); \ 519240116Smarcel break; \ 520240116Smarcel } \ 521240116Smarcel } \ 522240116Smarcel } \ 523240116Smarcel if (elm) \ 524240116Smarcel RB_COLOR(elm, field) = RB_BLACK; \ 525240116Smarcel} \ 526240116Smarcel \ 527240116Smarcelattr struct type * \ 528240116Smarcelname##_RB_REMOVE(struct name *head, struct type *elm) \ 529240116Smarcel{ \ 530240116Smarcel struct type *child, *parent, *old = elm; \ 531240116Smarcel int color; \ 532240116Smarcel if (RB_LEFT(elm, field) == NULL) \ 533240116Smarcel child = RB_RIGHT(elm, field); \ 534240116Smarcel else if (RB_RIGHT(elm, field) == NULL) \ 535240116Smarcel child = RB_LEFT(elm, field); \ 536240116Smarcel else { \ 537240116Smarcel struct type *left; \ 538240116Smarcel elm = RB_RIGHT(elm, field); \ 539240116Smarcel while ((left = RB_LEFT(elm, field)) != NULL) \ 540240116Smarcel elm = left; \ 541240116Smarcel child = RB_RIGHT(elm, field); \ 542240116Smarcel parent = RB_PARENT(elm, field); \ 543240116Smarcel color = RB_COLOR(elm, field); \ 544240116Smarcel if (child) \ 545240116Smarcel RB_PARENT(child, field) = parent; \ 546240116Smarcel if (parent) { \ 547240116Smarcel if (RB_LEFT(parent, field) == elm) \ 548240116Smarcel RB_LEFT(parent, field) = child; \ 549240116Smarcel else \ 550240116Smarcel RB_RIGHT(parent, field) = child; \ 551240116Smarcel RB_AUGMENT(parent); \ 552240116Smarcel } else \ 553240116Smarcel RB_ROOT(head) = child; \ 554240116Smarcel if (RB_PARENT(elm, field) == old) \ 555240116Smarcel parent = elm; \ 556240116Smarcel (elm)->field = (old)->field; \ 557240116Smarcel if (RB_PARENT(old, field)) { \ 558240116Smarcel if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 559240116Smarcel RB_LEFT(RB_PARENT(old, field), field) = elm;\ 560240116Smarcel else \ 561240116Smarcel RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 562240116Smarcel RB_AUGMENT(RB_PARENT(old, field)); \ 563240116Smarcel } else \ 564240116Smarcel RB_ROOT(head) = elm; \ 565240116Smarcel RB_PARENT(RB_LEFT(old, field), field) = elm; \ 566240116Smarcel if (RB_RIGHT(old, field)) \ 567240116Smarcel RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 568240116Smarcel if (parent) { \ 569240116Smarcel left = parent; \ 570240116Smarcel do { \ 571240116Smarcel RB_AUGMENT(left); \ 572240116Smarcel } while ((left = RB_PARENT(left, field)) != NULL); \ 573240116Smarcel } \ 574240116Smarcel goto color; \ 575240116Smarcel } \ 576240116Smarcel parent = RB_PARENT(elm, field); \ 577240116Smarcel color = RB_COLOR(elm, field); \ 578240116Smarcel if (child) \ 579240116Smarcel RB_PARENT(child, field) = parent; \ 580240116Smarcel if (parent) { \ 581240116Smarcel if (RB_LEFT(parent, field) == elm) \ 582240116Smarcel RB_LEFT(parent, field) = child; \ 583240116Smarcel else \ 584240116Smarcel RB_RIGHT(parent, field) = child; \ 585240116Smarcel RB_AUGMENT(parent); \ 586240116Smarcel } else \ 587240116Smarcel RB_ROOT(head) = child; \ 588240116Smarcelcolor: \ 589240116Smarcel if (color == RB_BLACK) \ 590240116Smarcel name##_RB_REMOVE_COLOR(head, parent, child); \ 591240116Smarcel return (old); \ 592240116Smarcel} \ 593240116Smarcel \ 594240116Smarcel/* Inserts a node into the RB tree */ \ 595240116Smarcelattr struct type * \ 596240116Smarcelname##_RB_INSERT(struct name *head, struct type *elm) \ 597240116Smarcel{ \ 598240116Smarcel struct type *tmp; \ 599240116Smarcel struct type *parent = NULL; \ 600240116Smarcel int comp = 0; \ 601240116Smarcel tmp = RB_ROOT(head); \ 602240116Smarcel while (tmp) { \ 603240116Smarcel parent = tmp; \ 604240116Smarcel comp = (cmp)(elm, parent); \ 605240116Smarcel if (comp < 0) \ 606240116Smarcel tmp = RB_LEFT(tmp, field); \ 607240116Smarcel else if (comp > 0) \ 608240116Smarcel tmp = RB_RIGHT(tmp, field); \ 609240116Smarcel else \ 610240116Smarcel return (tmp); \ 611240116Smarcel } \ 612240116Smarcel RB_SET(elm, parent, field); \ 613240116Smarcel if (parent != NULL) { \ 614240116Smarcel if (comp < 0) \ 615240116Smarcel RB_LEFT(parent, field) = elm; \ 616240116Smarcel else \ 617240116Smarcel RB_RIGHT(parent, field) = elm; \ 618 RB_AUGMENT(parent); \ 619 } else \ 620 RB_ROOT(head) = elm; \ 621 name##_RB_INSERT_COLOR(head, elm); \ 622 return (NULL); \ 623} \ 624 \ 625/* Finds the node with the same key as elm */ \ 626attr struct type * \ 627name##_RB_FIND(struct name *head, struct type *elm) \ 628{ \ 629 struct type *tmp = RB_ROOT(head); \ 630 int comp; \ 631 while (tmp) { \ 632 comp = cmp(elm, tmp); \ 633 if (comp < 0) \ 634 tmp = RB_LEFT(tmp, field); \ 635 else if (comp > 0) \ 636 tmp = RB_RIGHT(tmp, field); \ 637 else \ 638 return (tmp); \ 639 } \ 640 return (NULL); \ 641} \ 642 \ 643/* Finds the first node greater than or equal to the search key */ \ 644attr struct type * \ 645name##_RB_NFIND(struct name *head, struct type *elm) \ 646{ \ 647 struct type *tmp = RB_ROOT(head); \ 648 struct type *res = NULL; \ 649 int comp; \ 650 while (tmp) { \ 651 comp = cmp(elm, tmp); \ 652 if (comp < 0) { \ 653 res = tmp; \ 654 tmp = RB_LEFT(tmp, field); \ 655 } \ 656 else if (comp > 0) \ 657 tmp = RB_RIGHT(tmp, field); \ 658 else \ 659 return (tmp); \ 660 } \ 661 return (res); \ 662} \ 663 \ 664/* ARGSUSED */ \ 665attr struct type * \ 666name##_RB_NEXT(struct type *elm) \ 667{ \ 668 if (RB_RIGHT(elm, field)) { \ 669 elm = RB_RIGHT(elm, field); \ 670 while (RB_LEFT(elm, field)) \ 671 elm = RB_LEFT(elm, field); \ 672 } else { \ 673 if (RB_PARENT(elm, field) && \ 674 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 675 elm = RB_PARENT(elm, field); \ 676 else { \ 677 while (RB_PARENT(elm, field) && \ 678 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 679 elm = RB_PARENT(elm, field); \ 680 elm = RB_PARENT(elm, field); \ 681 } \ 682 } \ 683 return (elm); \ 684} \ 685 \ 686/* ARGSUSED */ \ 687attr struct type * \ 688name##_RB_PREV(struct type *elm) \ 689{ \ 690 if (RB_LEFT(elm, field)) { \ 691 elm = RB_LEFT(elm, field); \ 692 while (RB_RIGHT(elm, field)) \ 693 elm = RB_RIGHT(elm, field); \ 694 } else { \ 695 if (RB_PARENT(elm, field) && \ 696 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 697 elm = RB_PARENT(elm, field); \ 698 else { \ 699 while (RB_PARENT(elm, field) && \ 700 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 701 elm = RB_PARENT(elm, field); \ 702 elm = RB_PARENT(elm, field); \ 703 } \ 704 } \ 705 return (elm); \ 706} \ 707 \ 708attr struct type * \ 709name##_RB_MINMAX(struct name *head, int val) \ 710{ \ 711 struct type *tmp = RB_ROOT(head); \ 712 struct type *parent = NULL; \ 713 while (tmp) { \ 714 parent = tmp; \ 715 if (val < 0) \ 716 tmp = RB_LEFT(tmp, field); \ 717 else \ 718 tmp = RB_RIGHT(tmp, field); \ 719 } \ 720 return (parent); \ 721} 722 723#define RB_NEGINF -1 724#define RB_INF 1 725 726#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 727#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 728#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 729#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 730#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 731#define RB_PREV(name, x, y) name##_RB_PREV(y) 732#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 733#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 734 735#define RB_FOREACH(x, name, head) \ 736 for ((x) = RB_MIN(name, head); \ 737 (x) != NULL; \ 738 (x) = name##_RB_NEXT(x)) 739 740#define RB_FOREACH_FROM(x, name, y) \ 741 for ((x) = (y); \ 742 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 743 (x) = (y)) 744 745#define RB_FOREACH_SAFE(x, name, head, y) \ 746 for ((x) = RB_MIN(name, head); \ 747 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 748 (x) = (y)) 749 750#define RB_FOREACH_REVERSE(x, name, head) \ 751 for ((x) = RB_MAX(name, head); \ 752 (x) != NULL; \ 753 (x) = name##_RB_PREV(x)) 754 755#define RB_FOREACH_REVERSE_FROM(x, name, y) \ 756 for ((x) = (y); \ 757 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 758 (x) = (y)) 759 760#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 761 for ((x) = RB_MAX(name, head); \ 762 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 763 (x) = (y)) 764 765#endif /* _SYS_TREE_H_ */ 766