1248619Sdes/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ 2106121Sdes/* 3106121Sdes * Copyright 2002 Niels Provos <provos@citi.umich.edu> 4106121Sdes * All rights reserved. 5106121Sdes * 6106121Sdes * Redistribution and use in source and binary forms, with or without 7106121Sdes * modification, are permitted provided that the following conditions 8106121Sdes * are met: 9106121Sdes * 1. Redistributions of source code must retain the above copyright 10106121Sdes * notice, this list of conditions and the following disclaimer. 11106121Sdes * 2. Redistributions in binary form must reproduce the above copyright 12106121Sdes * notice, this list of conditions and the following disclaimer in the 13106121Sdes * documentation and/or other materials provided with the distribution. 14106121Sdes * 15106121Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16106121Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17106121Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18106121Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19106121Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20106121Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21106121Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22106121Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23106121Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24106121Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25106121Sdes */ 26106121Sdes 27157016Sdes/* OPENBSD ORIGINAL: sys/sys/tree.h */ 28157016Sdes 29248619Sdes#include "config.h" 30248619Sdes#ifdef NO_ATTRIBUTE_ON_RETURN_TYPE 31248619Sdes# define __attribute__(x) 32248619Sdes#endif 33248619Sdes 34106121Sdes#ifndef _SYS_TREE_H_ 35106121Sdes#define _SYS_TREE_H_ 36106121Sdes 37106121Sdes/* 38106121Sdes * This file defines data structures for different types of trees: 39106121Sdes * splay trees and red-black trees. 40106121Sdes * 41106121Sdes * A splay tree is a self-organizing data structure. Every operation 42106121Sdes * on the tree causes a splay to happen. The splay moves the requested 43106121Sdes * node to the root of the tree and partly rebalances it. 44106121Sdes * 45106121Sdes * This has the benefit that request locality causes faster lookups as 46106121Sdes * the requested nodes move to the top of the tree. On the other hand, 47106121Sdes * every lookup causes memory writes. 48106121Sdes * 49106121Sdes * The Balance Theorem bounds the total access time for m operations 50106121Sdes * and n inserts on an initially empty tree as O((m + n)lg n). The 51106121Sdes * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 52106121Sdes * 53106121Sdes * A red-black tree is a binary search tree with the node color as an 54106121Sdes * extra attribute. It fulfills a set of conditions: 55106121Sdes * - every search path from the root to a leaf consists of the 56106121Sdes * same number of black nodes, 57106121Sdes * - each red node (except for the root) has a black parent, 58106121Sdes * - each leaf node is black. 59106121Sdes * 60106121Sdes * Every operation on a red-black tree is bounded as O(lg n). 61106121Sdes * The maximum height of a red-black tree is 2lg (n+1). 62106121Sdes */ 63106121Sdes 64106121Sdes#define SPLAY_HEAD(name, type) \ 65106121Sdesstruct name { \ 66106121Sdes struct type *sph_root; /* root of the tree */ \ 67106121Sdes} 68106121Sdes 69106121Sdes#define SPLAY_INITIALIZER(root) \ 70106121Sdes { NULL } 71106121Sdes 72106121Sdes#define SPLAY_INIT(root) do { \ 73106121Sdes (root)->sph_root = NULL; \ 74106121Sdes} while (0) 75106121Sdes 76106121Sdes#define SPLAY_ENTRY(type) \ 77106121Sdesstruct { \ 78106121Sdes struct type *spe_left; /* left element */ \ 79106121Sdes struct type *spe_right; /* right element */ \ 80106121Sdes} 81106121Sdes 82106121Sdes#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 83106121Sdes#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 84106121Sdes#define SPLAY_ROOT(head) (head)->sph_root 85106121Sdes#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 86106121Sdes 87106121Sdes/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 88106121Sdes#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 89106121Sdes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 90106121Sdes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 91106121Sdes (head)->sph_root = tmp; \ 92106121Sdes} while (0) 93106121Sdes 94106121Sdes#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 95106121Sdes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 96106121Sdes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 97106121Sdes (head)->sph_root = tmp; \ 98106121Sdes} while (0) 99106121Sdes 100106121Sdes#define SPLAY_LINKLEFT(head, tmp, field) do { \ 101106121Sdes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 102106121Sdes tmp = (head)->sph_root; \ 103106121Sdes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 104106121Sdes} while (0) 105106121Sdes 106106121Sdes#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 107106121Sdes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 108106121Sdes tmp = (head)->sph_root; \ 109106121Sdes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 110106121Sdes} while (0) 111106121Sdes 112106121Sdes#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 113106121Sdes SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 114106121Sdes SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 115106121Sdes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 116106121Sdes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 117106121Sdes} while (0) 118106121Sdes 119106121Sdes/* Generates prototypes and inline functions */ 120106121Sdes 121106121Sdes#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 122106121Sdesvoid name##_SPLAY(struct name *, struct type *); \ 123106121Sdesvoid name##_SPLAY_MINMAX(struct name *, int); \ 124106121Sdesstruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 125106121Sdesstruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 126106121Sdes \ 127106121Sdes/* Finds the node with the same key as elm */ \ 128106121Sdesstatic __inline struct type * \ 129106121Sdesname##_SPLAY_FIND(struct name *head, struct type *elm) \ 130106121Sdes{ \ 131106121Sdes if (SPLAY_EMPTY(head)) \ 132106121Sdes return(NULL); \ 133106121Sdes name##_SPLAY(head, elm); \ 134106121Sdes if ((cmp)(elm, (head)->sph_root) == 0) \ 135106121Sdes return (head->sph_root); \ 136106121Sdes return (NULL); \ 137106121Sdes} \ 138106121Sdes \ 139106121Sdesstatic __inline struct type * \ 140106121Sdesname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 141106121Sdes{ \ 142106121Sdes name##_SPLAY(head, elm); \ 143106121Sdes if (SPLAY_RIGHT(elm, field) != NULL) { \ 144106121Sdes elm = SPLAY_RIGHT(elm, field); \ 145106121Sdes while (SPLAY_LEFT(elm, field) != NULL) { \ 146106121Sdes elm = SPLAY_LEFT(elm, field); \ 147106121Sdes } \ 148106121Sdes } else \ 149106121Sdes elm = NULL; \ 150106121Sdes return (elm); \ 151106121Sdes} \ 152106121Sdes \ 153106121Sdesstatic __inline struct type * \ 154106121Sdesname##_SPLAY_MIN_MAX(struct name *head, int val) \ 155106121Sdes{ \ 156106121Sdes name##_SPLAY_MINMAX(head, val); \ 157106121Sdes return (SPLAY_ROOT(head)); \ 158106121Sdes} 159106121Sdes 160106121Sdes/* Main splay operation. 161106121Sdes * Moves node close to the key of elm to top 162106121Sdes */ 163106121Sdes#define SPLAY_GENERATE(name, type, field, cmp) \ 164106121Sdesstruct type * \ 165106121Sdesname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 166106121Sdes{ \ 167106121Sdes if (SPLAY_EMPTY(head)) { \ 168106121Sdes SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 169106121Sdes } else { \ 170106121Sdes int __comp; \ 171106121Sdes name##_SPLAY(head, elm); \ 172106121Sdes __comp = (cmp)(elm, (head)->sph_root); \ 173106121Sdes if(__comp < 0) { \ 174106121Sdes SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 175106121Sdes SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 176106121Sdes SPLAY_LEFT((head)->sph_root, field) = NULL; \ 177106121Sdes } else if (__comp > 0) { \ 178106121Sdes SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 179106121Sdes SPLAY_LEFT(elm, field) = (head)->sph_root; \ 180106121Sdes SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 181106121Sdes } else \ 182106121Sdes return ((head)->sph_root); \ 183106121Sdes } \ 184106121Sdes (head)->sph_root = (elm); \ 185106121Sdes return (NULL); \ 186106121Sdes} \ 187106121Sdes \ 188106121Sdesstruct type * \ 189106121Sdesname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 190106121Sdes{ \ 191106121Sdes struct type *__tmp; \ 192106121Sdes if (SPLAY_EMPTY(head)) \ 193106121Sdes return (NULL); \ 194106121Sdes name##_SPLAY(head, elm); \ 195106121Sdes if ((cmp)(elm, (head)->sph_root) == 0) { \ 196106121Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 197106121Sdes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 198106121Sdes } else { \ 199106121Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 200106121Sdes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 201106121Sdes name##_SPLAY(head, elm); \ 202106121Sdes SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 203106121Sdes } \ 204106121Sdes return (elm); \ 205106121Sdes } \ 206106121Sdes return (NULL); \ 207106121Sdes} \ 208106121Sdes \ 209106121Sdesvoid \ 210106121Sdesname##_SPLAY(struct name *head, struct type *elm) \ 211106121Sdes{ \ 212106121Sdes struct type __node, *__left, *__right, *__tmp; \ 213106121Sdes int __comp; \ 214106121Sdes\ 215106121Sdes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 216106121Sdes __left = __right = &__node; \ 217106121Sdes\ 218106121Sdes while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 219106121Sdes if (__comp < 0) { \ 220106121Sdes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 221106121Sdes if (__tmp == NULL) \ 222106121Sdes break; \ 223106121Sdes if ((cmp)(elm, __tmp) < 0){ \ 224106121Sdes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 225106121Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 226106121Sdes break; \ 227106121Sdes } \ 228106121Sdes SPLAY_LINKLEFT(head, __right, field); \ 229106121Sdes } else if (__comp > 0) { \ 230106121Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 231106121Sdes if (__tmp == NULL) \ 232106121Sdes break; \ 233106121Sdes if ((cmp)(elm, __tmp) > 0){ \ 234106121Sdes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 235106121Sdes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 236106121Sdes break; \ 237106121Sdes } \ 238106121Sdes SPLAY_LINKRIGHT(head, __left, field); \ 239106121Sdes } \ 240106121Sdes } \ 241106121Sdes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 242106121Sdes} \ 243106121Sdes \ 244106121Sdes/* Splay with either the minimum or the maximum element \ 245106121Sdes * Used to find minimum or maximum element in tree. \ 246106121Sdes */ \ 247106121Sdesvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 248106121Sdes{ \ 249106121Sdes struct type __node, *__left, *__right, *__tmp; \ 250106121Sdes\ 251106121Sdes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 252106121Sdes __left = __right = &__node; \ 253106121Sdes\ 254106121Sdes while (1) { \ 255106121Sdes if (__comp < 0) { \ 256106121Sdes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 257106121Sdes if (__tmp == NULL) \ 258106121Sdes break; \ 259106121Sdes if (__comp < 0){ \ 260106121Sdes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 261106121Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 262106121Sdes break; \ 263106121Sdes } \ 264106121Sdes SPLAY_LINKLEFT(head, __right, field); \ 265106121Sdes } else if (__comp > 0) { \ 266106121Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 267106121Sdes if (__tmp == NULL) \ 268106121Sdes break; \ 269106121Sdes if (__comp > 0) { \ 270106121Sdes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 271106121Sdes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 272106121Sdes break; \ 273106121Sdes } \ 274106121Sdes SPLAY_LINKRIGHT(head, __left, field); \ 275106121Sdes } \ 276106121Sdes } \ 277106121Sdes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 278106121Sdes} 279106121Sdes 280106121Sdes#define SPLAY_NEGINF -1 281106121Sdes#define SPLAY_INF 1 282106121Sdes 283106121Sdes#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 284106121Sdes#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 285106121Sdes#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 286106121Sdes#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 287106121Sdes#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 288106121Sdes : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 289106121Sdes#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 290106121Sdes : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 291106121Sdes 292106121Sdes#define SPLAY_FOREACH(x, name, head) \ 293106121Sdes for ((x) = SPLAY_MIN(name, head); \ 294106121Sdes (x) != NULL; \ 295106121Sdes (x) = SPLAY_NEXT(name, head, x)) 296106121Sdes 297181111Sdes/* Macros that define a red-black tree */ 298106121Sdes#define RB_HEAD(name, type) \ 299106121Sdesstruct name { \ 300106121Sdes struct type *rbh_root; /* root of the tree */ \ 301106121Sdes} 302106121Sdes 303106121Sdes#define RB_INITIALIZER(root) \ 304106121Sdes { NULL } 305106121Sdes 306106121Sdes#define RB_INIT(root) do { \ 307106121Sdes (root)->rbh_root = NULL; \ 308106121Sdes} while (0) 309106121Sdes 310106121Sdes#define RB_BLACK 0 311106121Sdes#define RB_RED 1 312106121Sdes#define RB_ENTRY(type) \ 313106121Sdesstruct { \ 314106121Sdes struct type *rbe_left; /* left element */ \ 315106121Sdes struct type *rbe_right; /* right element */ \ 316106121Sdes struct type *rbe_parent; /* parent element */ \ 317106121Sdes int rbe_color; /* node color */ \ 318106121Sdes} 319106121Sdes 320106121Sdes#define RB_LEFT(elm, field) (elm)->field.rbe_left 321106121Sdes#define RB_RIGHT(elm, field) (elm)->field.rbe_right 322106121Sdes#define RB_PARENT(elm, field) (elm)->field.rbe_parent 323106121Sdes#define RB_COLOR(elm, field) (elm)->field.rbe_color 324106121Sdes#define RB_ROOT(head) (head)->rbh_root 325106121Sdes#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 326106121Sdes 327106121Sdes#define RB_SET(elm, parent, field) do { \ 328106121Sdes RB_PARENT(elm, field) = parent; \ 329106121Sdes RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 330106121Sdes RB_COLOR(elm, field) = RB_RED; \ 331106121Sdes} while (0) 332106121Sdes 333106121Sdes#define RB_SET_BLACKRED(black, red, field) do { \ 334106121Sdes RB_COLOR(black, field) = RB_BLACK; \ 335106121Sdes RB_COLOR(red, field) = RB_RED; \ 336106121Sdes} while (0) 337106121Sdes 338106121Sdes#ifndef RB_AUGMENT 339248619Sdes#define RB_AUGMENT(x) do {} while (0) 340106121Sdes#endif 341106121Sdes 342106121Sdes#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 343106121Sdes (tmp) = RB_RIGHT(elm, field); \ 344106121Sdes if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 345106121Sdes RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 346106121Sdes } \ 347106121Sdes RB_AUGMENT(elm); \ 348106121Sdes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 349106121Sdes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 350106121Sdes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 351106121Sdes else \ 352106121Sdes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 353106121Sdes } else \ 354106121Sdes (head)->rbh_root = (tmp); \ 355106121Sdes RB_LEFT(tmp, field) = (elm); \ 356106121Sdes RB_PARENT(elm, field) = (tmp); \ 357106121Sdes RB_AUGMENT(tmp); \ 358113908Sdes if ((RB_PARENT(tmp, field))) \ 359113908Sdes RB_AUGMENT(RB_PARENT(tmp, field)); \ 360106121Sdes} while (0) 361106121Sdes 362106121Sdes#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 363106121Sdes (tmp) = RB_LEFT(elm, field); \ 364106121Sdes if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 365106121Sdes RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 366106121Sdes } \ 367106121Sdes RB_AUGMENT(elm); \ 368106121Sdes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 369106121Sdes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 370106121Sdes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 371106121Sdes else \ 372106121Sdes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 373106121Sdes } else \ 374106121Sdes (head)->rbh_root = (tmp); \ 375106121Sdes RB_RIGHT(tmp, field) = (elm); \ 376106121Sdes RB_PARENT(elm, field) = (tmp); \ 377106121Sdes RB_AUGMENT(tmp); \ 378113908Sdes if ((RB_PARENT(tmp, field))) \ 379113908Sdes RB_AUGMENT(RB_PARENT(tmp, field)); \ 380106121Sdes} while (0) 381106121Sdes 382106121Sdes/* Generates prototypes and inline functions */ 383248619Sdes#define RB_PROTOTYPE(name, type, field, cmp) \ 384248619Sdes RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 385248619Sdes#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 386248619Sdes RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 387248619Sdes#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 388248619Sdesattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 389248619Sdesattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 390248619Sdesattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 391248619Sdesattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 392248619Sdesattr struct type *name##_RB_FIND(struct name *, struct type *); \ 393248619Sdesattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 394248619Sdesattr struct type *name##_RB_NEXT(struct type *); \ 395248619Sdesattr struct type *name##_RB_PREV(struct type *); \ 396248619Sdesattr struct type *name##_RB_MINMAX(struct name *, int); \ 397248619Sdes \ 398106121Sdes 399106121Sdes/* Main rb operation. 400106121Sdes * Moves node close to the key of elm to top 401106121Sdes */ 402248619Sdes#define RB_GENERATE(name, type, field, cmp) \ 403248619Sdes RB_GENERATE_INTERNAL(name, type, field, cmp,) 404248619Sdes#define RB_GENERATE_STATIC(name, type, field, cmp) \ 405248619Sdes RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 406248619Sdes#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 407248619Sdesattr void \ 408106121Sdesname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 409106121Sdes{ \ 410106121Sdes struct type *parent, *gparent, *tmp; \ 411106121Sdes while ((parent = RB_PARENT(elm, field)) && \ 412106121Sdes RB_COLOR(parent, field) == RB_RED) { \ 413106121Sdes gparent = RB_PARENT(parent, field); \ 414106121Sdes if (parent == RB_LEFT(gparent, field)) { \ 415106121Sdes tmp = RB_RIGHT(gparent, field); \ 416106121Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 417106121Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 418106121Sdes RB_SET_BLACKRED(parent, gparent, field);\ 419106121Sdes elm = gparent; \ 420106121Sdes continue; \ 421106121Sdes } \ 422106121Sdes if (RB_RIGHT(parent, field) == elm) { \ 423106121Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 424106121Sdes tmp = parent; \ 425106121Sdes parent = elm; \ 426106121Sdes elm = tmp; \ 427106121Sdes } \ 428106121Sdes RB_SET_BLACKRED(parent, gparent, field); \ 429106121Sdes RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 430106121Sdes } else { \ 431106121Sdes tmp = RB_LEFT(gparent, field); \ 432106121Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 433106121Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 434106121Sdes RB_SET_BLACKRED(parent, gparent, field);\ 435106121Sdes elm = gparent; \ 436106121Sdes continue; \ 437106121Sdes } \ 438106121Sdes if (RB_LEFT(parent, field) == elm) { \ 439106121Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 440106121Sdes tmp = parent; \ 441106121Sdes parent = elm; \ 442106121Sdes elm = tmp; \ 443106121Sdes } \ 444106121Sdes RB_SET_BLACKRED(parent, gparent, field); \ 445106121Sdes RB_ROTATE_LEFT(head, gparent, tmp, field); \ 446106121Sdes } \ 447106121Sdes } \ 448106121Sdes RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 449106121Sdes} \ 450106121Sdes \ 451248619Sdesattr void \ 452106121Sdesname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 453106121Sdes{ \ 454106121Sdes struct type *tmp; \ 455106121Sdes while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 456106121Sdes elm != RB_ROOT(head)) { \ 457106121Sdes if (RB_LEFT(parent, field) == elm) { \ 458106121Sdes tmp = RB_RIGHT(parent, field); \ 459106121Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 460106121Sdes RB_SET_BLACKRED(tmp, parent, field); \ 461106121Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 462106121Sdes tmp = RB_RIGHT(parent, field); \ 463106121Sdes } \ 464106121Sdes if ((RB_LEFT(tmp, field) == NULL || \ 465106121Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 466106121Sdes (RB_RIGHT(tmp, field) == NULL || \ 467106121Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 468106121Sdes RB_COLOR(tmp, field) = RB_RED; \ 469106121Sdes elm = parent; \ 470106121Sdes parent = RB_PARENT(elm, field); \ 471106121Sdes } else { \ 472106121Sdes if (RB_RIGHT(tmp, field) == NULL || \ 473106121Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 474106121Sdes struct type *oleft; \ 475106121Sdes if ((oleft = RB_LEFT(tmp, field)))\ 476106121Sdes RB_COLOR(oleft, field) = RB_BLACK;\ 477106121Sdes RB_COLOR(tmp, field) = RB_RED; \ 478106121Sdes RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 479106121Sdes tmp = RB_RIGHT(parent, field); \ 480106121Sdes } \ 481106121Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 482106121Sdes RB_COLOR(parent, field) = RB_BLACK; \ 483106121Sdes if (RB_RIGHT(tmp, field)) \ 484106121Sdes RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 485106121Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 486106121Sdes elm = RB_ROOT(head); \ 487106121Sdes break; \ 488106121Sdes } \ 489106121Sdes } else { \ 490106121Sdes tmp = RB_LEFT(parent, field); \ 491106121Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 492106121Sdes RB_SET_BLACKRED(tmp, parent, field); \ 493106121Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 494106121Sdes tmp = RB_LEFT(parent, field); \ 495106121Sdes } \ 496106121Sdes if ((RB_LEFT(tmp, field) == NULL || \ 497106121Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 498106121Sdes (RB_RIGHT(tmp, field) == NULL || \ 499106121Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 500106121Sdes RB_COLOR(tmp, field) = RB_RED; \ 501106121Sdes elm = parent; \ 502106121Sdes parent = RB_PARENT(elm, field); \ 503106121Sdes } else { \ 504106121Sdes if (RB_LEFT(tmp, field) == NULL || \ 505106121Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 506106121Sdes struct type *oright; \ 507106121Sdes if ((oright = RB_RIGHT(tmp, field)))\ 508106121Sdes RB_COLOR(oright, field) = RB_BLACK;\ 509106121Sdes RB_COLOR(tmp, field) = RB_RED; \ 510106121Sdes RB_ROTATE_LEFT(head, tmp, oright, field);\ 511106121Sdes tmp = RB_LEFT(parent, field); \ 512106121Sdes } \ 513106121Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 514106121Sdes RB_COLOR(parent, field) = RB_BLACK; \ 515106121Sdes if (RB_LEFT(tmp, field)) \ 516106121Sdes RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 517106121Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 518106121Sdes elm = RB_ROOT(head); \ 519106121Sdes break; \ 520106121Sdes } \ 521106121Sdes } \ 522106121Sdes } \ 523106121Sdes if (elm) \ 524106121Sdes RB_COLOR(elm, field) = RB_BLACK; \ 525106121Sdes} \ 526106121Sdes \ 527248619Sdesattr struct type * \ 528106121Sdesname##_RB_REMOVE(struct name *head, struct type *elm) \ 529106121Sdes{ \ 530106121Sdes struct type *child, *parent, *old = elm; \ 531106121Sdes int color; \ 532106121Sdes if (RB_LEFT(elm, field) == NULL) \ 533106121Sdes child = RB_RIGHT(elm, field); \ 534106121Sdes else if (RB_RIGHT(elm, field) == NULL) \ 535106121Sdes child = RB_LEFT(elm, field); \ 536106121Sdes else { \ 537106121Sdes struct type *left; \ 538106121Sdes elm = RB_RIGHT(elm, field); \ 539106121Sdes while ((left = RB_LEFT(elm, field))) \ 540106121Sdes elm = left; \ 541106121Sdes child = RB_RIGHT(elm, field); \ 542106121Sdes parent = RB_PARENT(elm, field); \ 543106121Sdes color = RB_COLOR(elm, field); \ 544106121Sdes if (child) \ 545106121Sdes RB_PARENT(child, field) = parent; \ 546106121Sdes if (parent) { \ 547106121Sdes if (RB_LEFT(parent, field) == elm) \ 548106121Sdes RB_LEFT(parent, field) = child; \ 549106121Sdes else \ 550106121Sdes RB_RIGHT(parent, field) = child; \ 551106121Sdes RB_AUGMENT(parent); \ 552106121Sdes } else \ 553106121Sdes RB_ROOT(head) = child; \ 554106121Sdes if (RB_PARENT(elm, field) == old) \ 555106121Sdes parent = elm; \ 556106121Sdes (elm)->field = (old)->field; \ 557106121Sdes if (RB_PARENT(old, field)) { \ 558106121Sdes if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 559106121Sdes RB_LEFT(RB_PARENT(old, field), field) = elm;\ 560106121Sdes else \ 561106121Sdes RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 562106121Sdes RB_AUGMENT(RB_PARENT(old, field)); \ 563106121Sdes } else \ 564106121Sdes RB_ROOT(head) = elm; \ 565106121Sdes RB_PARENT(RB_LEFT(old, field), field) = elm; \ 566106121Sdes if (RB_RIGHT(old, field)) \ 567106121Sdes RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 568106121Sdes if (parent) { \ 569106121Sdes left = parent; \ 570106121Sdes do { \ 571106121Sdes RB_AUGMENT(left); \ 572106121Sdes } while ((left = RB_PARENT(left, field))); \ 573106121Sdes } \ 574106121Sdes goto color; \ 575106121Sdes } \ 576106121Sdes parent = RB_PARENT(elm, field); \ 577106121Sdes color = RB_COLOR(elm, field); \ 578106121Sdes if (child) \ 579106121Sdes RB_PARENT(child, field) = parent; \ 580106121Sdes if (parent) { \ 581106121Sdes if (RB_LEFT(parent, field) == elm) \ 582106121Sdes RB_LEFT(parent, field) = child; \ 583106121Sdes else \ 584106121Sdes RB_RIGHT(parent, field) = child; \ 585106121Sdes RB_AUGMENT(parent); \ 586106121Sdes } else \ 587106121Sdes RB_ROOT(head) = child; \ 588106121Sdescolor: \ 589106121Sdes if (color == RB_BLACK) \ 590106121Sdes name##_RB_REMOVE_COLOR(head, parent, child); \ 591106121Sdes return (old); \ 592106121Sdes} \ 593106121Sdes \ 594106121Sdes/* Inserts a node into the RB tree */ \ 595248619Sdesattr struct type * \ 596106121Sdesname##_RB_INSERT(struct name *head, struct type *elm) \ 597106121Sdes{ \ 598106121Sdes struct type *tmp; \ 599106121Sdes struct type *parent = NULL; \ 600106121Sdes int comp = 0; \ 601106121Sdes tmp = RB_ROOT(head); \ 602106121Sdes while (tmp) { \ 603106121Sdes parent = tmp; \ 604106121Sdes comp = (cmp)(elm, parent); \ 605106121Sdes if (comp < 0) \ 606106121Sdes tmp = RB_LEFT(tmp, field); \ 607106121Sdes else if (comp > 0) \ 608106121Sdes tmp = RB_RIGHT(tmp, field); \ 609106121Sdes else \ 610106121Sdes return (tmp); \ 611106121Sdes } \ 612106121Sdes RB_SET(elm, parent, field); \ 613106121Sdes if (parent != NULL) { \ 614106121Sdes if (comp < 0) \ 615106121Sdes RB_LEFT(parent, field) = elm; \ 616106121Sdes else \ 617106121Sdes RB_RIGHT(parent, field) = elm; \ 618106121Sdes RB_AUGMENT(parent); \ 619106121Sdes } else \ 620106121Sdes RB_ROOT(head) = elm; \ 621106121Sdes name##_RB_INSERT_COLOR(head, elm); \ 622106121Sdes return (NULL); \ 623106121Sdes} \ 624106121Sdes \ 625106121Sdes/* Finds the node with the same key as elm */ \ 626248619Sdesattr struct type * \ 627106121Sdesname##_RB_FIND(struct name *head, struct type *elm) \ 628106121Sdes{ \ 629106121Sdes struct type *tmp = RB_ROOT(head); \ 630106121Sdes int comp; \ 631106121Sdes while (tmp) { \ 632106121Sdes comp = cmp(elm, tmp); \ 633106121Sdes if (comp < 0) \ 634106121Sdes tmp = RB_LEFT(tmp, field); \ 635106121Sdes else if (comp > 0) \ 636106121Sdes tmp = RB_RIGHT(tmp, field); \ 637106121Sdes else \ 638106121Sdes return (tmp); \ 639106121Sdes } \ 640106121Sdes return (NULL); \ 641106121Sdes} \ 642106121Sdes \ 643248619Sdes/* Finds the first node greater than or equal to the search key */ \ 644248619Sdesattr struct type * \ 645248619Sdesname##_RB_NFIND(struct name *head, struct type *elm) \ 646248619Sdes{ \ 647248619Sdes struct type *tmp = RB_ROOT(head); \ 648248619Sdes struct type *res = NULL; \ 649248619Sdes int comp; \ 650248619Sdes while (tmp) { \ 651248619Sdes comp = cmp(elm, tmp); \ 652248619Sdes if (comp < 0) { \ 653248619Sdes res = tmp; \ 654248619Sdes tmp = RB_LEFT(tmp, field); \ 655248619Sdes } \ 656248619Sdes else if (comp > 0) \ 657248619Sdes tmp = RB_RIGHT(tmp, field); \ 658248619Sdes else \ 659248619Sdes return (tmp); \ 660248619Sdes } \ 661248619Sdes return (res); \ 662248619Sdes} \ 663248619Sdes \ 664248619Sdes/* ARGSUSED */ \ 665248619Sdesattr struct type * \ 666181111Sdesname##_RB_NEXT(struct type *elm) \ 667106121Sdes{ \ 668106121Sdes if (RB_RIGHT(elm, field)) { \ 669106121Sdes elm = RB_RIGHT(elm, field); \ 670106121Sdes while (RB_LEFT(elm, field)) \ 671106121Sdes elm = RB_LEFT(elm, field); \ 672106121Sdes } else { \ 673106121Sdes if (RB_PARENT(elm, field) && \ 674106121Sdes (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 675106121Sdes elm = RB_PARENT(elm, field); \ 676106121Sdes else { \ 677106121Sdes while (RB_PARENT(elm, field) && \ 678106121Sdes (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 679106121Sdes elm = RB_PARENT(elm, field); \ 680106121Sdes elm = RB_PARENT(elm, field); \ 681106121Sdes } \ 682106121Sdes } \ 683106121Sdes return (elm); \ 684106121Sdes} \ 685106121Sdes \ 686248619Sdes/* ARGSUSED */ \ 687248619Sdesattr struct type * \ 688248619Sdesname##_RB_PREV(struct type *elm) \ 689248619Sdes{ \ 690248619Sdes if (RB_LEFT(elm, field)) { \ 691248619Sdes elm = RB_LEFT(elm, field); \ 692248619Sdes while (RB_RIGHT(elm, field)) \ 693248619Sdes elm = RB_RIGHT(elm, field); \ 694248619Sdes } else { \ 695248619Sdes if (RB_PARENT(elm, field) && \ 696248619Sdes (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 697248619Sdes elm = RB_PARENT(elm, field); \ 698248619Sdes else { \ 699248619Sdes while (RB_PARENT(elm, field) && \ 700248619Sdes (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 701248619Sdes elm = RB_PARENT(elm, field); \ 702248619Sdes elm = RB_PARENT(elm, field); \ 703248619Sdes } \ 704248619Sdes } \ 705248619Sdes return (elm); \ 706248619Sdes} \ 707248619Sdes \ 708248619Sdesattr struct type * \ 709106121Sdesname##_RB_MINMAX(struct name *head, int val) \ 710106121Sdes{ \ 711106121Sdes struct type *tmp = RB_ROOT(head); \ 712106121Sdes struct type *parent = NULL; \ 713106121Sdes while (tmp) { \ 714106121Sdes parent = tmp; \ 715106121Sdes if (val < 0) \ 716106121Sdes tmp = RB_LEFT(tmp, field); \ 717106121Sdes else \ 718106121Sdes tmp = RB_RIGHT(tmp, field); \ 719106121Sdes } \ 720106121Sdes return (parent); \ 721106121Sdes} 722106121Sdes 723106121Sdes#define RB_NEGINF -1 724106121Sdes#define RB_INF 1 725106121Sdes 726106121Sdes#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 727106121Sdes#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 728106121Sdes#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 729248619Sdes#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 730181111Sdes#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 731248619Sdes#define RB_PREV(name, x, y) name##_RB_PREV(y) 732106121Sdes#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 733106121Sdes#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 734106121Sdes 735106121Sdes#define RB_FOREACH(x, name, head) \ 736106121Sdes for ((x) = RB_MIN(name, head); \ 737106121Sdes (x) != NULL; \ 738181111Sdes (x) = name##_RB_NEXT(x)) 739106121Sdes 740248619Sdes#define RB_FOREACH_SAFE(x, name, head, y) \ 741248619Sdes for ((x) = RB_MIN(name, head); \ 742248619Sdes ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ 743248619Sdes (x) = (y)) 744248619Sdes 745248619Sdes#define RB_FOREACH_REVERSE(x, name, head) \ 746248619Sdes for ((x) = RB_MAX(name, head); \ 747248619Sdes (x) != NULL; \ 748248619Sdes (x) = name##_RB_PREV(x)) 749248619Sdes 750248619Sdes#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 751248619Sdes for ((x) = RB_MAX(name, head); \ 752248619Sdes ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ 753248619Sdes (x) = (y)) 754248619Sdes 755106121Sdes#endif /* _SYS_TREE_H_ */ 756