1bf21cd93STycho Nightingale /* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2bf21cd93STycho Nightingale /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3bf21cd93STycho Nightingale /* $FreeBSD: head/sys/sys/tree.h 189204 2009-03-01 04:57:23Z bms $ */ 4bf21cd93STycho Nightingale 5bf21cd93STycho Nightingale /*- 6bf21cd93STycho Nightingale * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7bf21cd93STycho Nightingale * All rights reserved. 8bf21cd93STycho Nightingale * 9bf21cd93STycho Nightingale * Redistribution and use in source and binary forms, with or without 10bf21cd93STycho Nightingale * modification, are permitted provided that the following conditions 11bf21cd93STycho Nightingale * are met: 12bf21cd93STycho Nightingale * 1. Redistributions of source code must retain the above copyright 13bf21cd93STycho Nightingale * notice, this list of conditions and the following disclaimer. 14bf21cd93STycho Nightingale * 2. Redistributions in binary form must reproduce the above copyright 15bf21cd93STycho Nightingale * notice, this list of conditions and the following disclaimer in the 16bf21cd93STycho Nightingale * documentation and/or other materials provided with the distribution. 17bf21cd93STycho Nightingale * 18bf21cd93STycho Nightingale * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19bf21cd93STycho Nightingale * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20bf21cd93STycho Nightingale * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21bf21cd93STycho Nightingale * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22bf21cd93STycho Nightingale * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23bf21cd93STycho Nightingale * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24bf21cd93STycho Nightingale * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25bf21cd93STycho Nightingale * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26bf21cd93STycho Nightingale * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27bf21cd93STycho Nightingale * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28bf21cd93STycho Nightingale */ 29bf21cd93STycho Nightingale 30bf21cd93STycho Nightingale #ifndef _SYS_TREE_H_ 31bf21cd93STycho Nightingale #define _SYS_TREE_H_ 32bf21cd93STycho Nightingale 33bf21cd93STycho Nightingale #include <sys/cdefs.h> 34bf21cd93STycho Nightingale 35bf21cd93STycho Nightingale /* 36bf21cd93STycho Nightingale * This file defines data structures for different types of trees: 37bf21cd93STycho Nightingale * splay trees and red-black trees. 38bf21cd93STycho Nightingale * 39bf21cd93STycho Nightingale * A splay tree is a self-organizing data structure. Every operation 40bf21cd93STycho Nightingale * on the tree causes a splay to happen. The splay moves the requested 41bf21cd93STycho Nightingale * node to the root of the tree and partly rebalances it. 42bf21cd93STycho Nightingale * 43bf21cd93STycho Nightingale * This has the benefit that request locality causes faster lookups as 44bf21cd93STycho Nightingale * the requested nodes move to the top of the tree. On the other hand, 45bf21cd93STycho Nightingale * every lookup causes memory writes. 46bf21cd93STycho Nightingale * 47bf21cd93STycho Nightingale * The Balance Theorem bounds the total access time for m operations 48bf21cd93STycho Nightingale * and n inserts on an initially empty tree as O((m + n)lg n). The 49bf21cd93STycho Nightingale * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 50bf21cd93STycho Nightingale * 51bf21cd93STycho Nightingale * A red-black tree is a binary search tree with the node color as an 52bf21cd93STycho Nightingale * extra attribute. It fulfills a set of conditions: 53bf21cd93STycho Nightingale * - every search path from the root to a leaf consists of the 54bf21cd93STycho Nightingale * same number of black nodes, 55bf21cd93STycho Nightingale * - each red node (except for the root) has a black parent, 56bf21cd93STycho Nightingale * - each leaf node is black. 57bf21cd93STycho Nightingale * 58bf21cd93STycho Nightingale * Every operation on a red-black tree is bounded as O(lg n). 59bf21cd93STycho Nightingale * The maximum height of a red-black tree is 2lg (n+1). 60bf21cd93STycho Nightingale */ 61bf21cd93STycho Nightingale 62bf21cd93STycho Nightingale #define SPLAY_HEAD(name, type) \ 63bf21cd93STycho Nightingale struct name { \ 64bf21cd93STycho Nightingale struct type *sph_root; /* root of the tree */ \ 65bf21cd93STycho Nightingale } 66bf21cd93STycho Nightingale 67bf21cd93STycho Nightingale #define SPLAY_INITIALIZER(root) \ 68bf21cd93STycho Nightingale { NULL } 69bf21cd93STycho Nightingale 70bf21cd93STycho Nightingale #define SPLAY_INIT(root) do { \ 71bf21cd93STycho Nightingale (root)->sph_root = NULL; \ 72bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 73bf21cd93STycho Nightingale 74bf21cd93STycho Nightingale #define SPLAY_ENTRY(type) \ 75bf21cd93STycho Nightingale struct { \ 76bf21cd93STycho Nightingale struct type *spe_left; /* left element */ \ 77bf21cd93STycho Nightingale struct type *spe_right; /* right element */ \ 78bf21cd93STycho Nightingale } 79bf21cd93STycho Nightingale 80bf21cd93STycho Nightingale #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 81bf21cd93STycho Nightingale #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 82bf21cd93STycho Nightingale #define SPLAY_ROOT(head) (head)->sph_root 83bf21cd93STycho Nightingale #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 84bf21cd93STycho Nightingale 85bf21cd93STycho Nightingale /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 86bf21cd93STycho Nightingale #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 87bf21cd93STycho Nightingale SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 88bf21cd93STycho Nightingale SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 89bf21cd93STycho Nightingale (head)->sph_root = tmp; \ 90bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 91bf21cd93STycho Nightingale 92bf21cd93STycho Nightingale #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 93bf21cd93STycho Nightingale SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 94bf21cd93STycho Nightingale SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95bf21cd93STycho Nightingale (head)->sph_root = tmp; \ 96bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 97bf21cd93STycho Nightingale 98bf21cd93STycho Nightingale #define SPLAY_LINKLEFT(head, tmp, field) do { \ 99bf21cd93STycho Nightingale SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 100bf21cd93STycho Nightingale tmp = (head)->sph_root; \ 101bf21cd93STycho Nightingale (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 102bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 103bf21cd93STycho Nightingale 104bf21cd93STycho Nightingale #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 105bf21cd93STycho Nightingale SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 106bf21cd93STycho Nightingale tmp = (head)->sph_root; \ 107bf21cd93STycho Nightingale (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 108bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 109bf21cd93STycho Nightingale 110bf21cd93STycho Nightingale #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 111bf21cd93STycho Nightingale SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 112bf21cd93STycho Nightingale SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 113bf21cd93STycho Nightingale SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 114bf21cd93STycho Nightingale SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 115bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 116bf21cd93STycho Nightingale 117bf21cd93STycho Nightingale /* Generates prototypes and inline functions */ 118bf21cd93STycho Nightingale 119bf21cd93STycho Nightingale #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 120bf21cd93STycho Nightingale void name##_SPLAY(struct name *, struct type *); \ 121bf21cd93STycho Nightingale void name##_SPLAY_MINMAX(struct name *, int); \ 122bf21cd93STycho Nightingale struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 123bf21cd93STycho Nightingale struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 124bf21cd93STycho Nightingale \ 125bf21cd93STycho Nightingale /* Finds the node with the same key as elm */ \ 126bf21cd93STycho Nightingale static __inline struct type * \ 127bf21cd93STycho Nightingale name##_SPLAY_FIND(struct name *head, struct type *elm) \ 128bf21cd93STycho Nightingale { \ 129bf21cd93STycho Nightingale if (SPLAY_EMPTY(head)) \ 130bf21cd93STycho Nightingale return(NULL); \ 131bf21cd93STycho Nightingale name##_SPLAY(head, elm); \ 132bf21cd93STycho Nightingale if ((cmp)(elm, (head)->sph_root) == 0) \ 133bf21cd93STycho Nightingale return (head->sph_root); \ 134bf21cd93STycho Nightingale return (NULL); \ 135bf21cd93STycho Nightingale } \ 136bf21cd93STycho Nightingale \ 137bf21cd93STycho Nightingale static __inline struct type * \ 138bf21cd93STycho Nightingale name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 139bf21cd93STycho Nightingale { \ 140bf21cd93STycho Nightingale name##_SPLAY(head, elm); \ 141bf21cd93STycho Nightingale if (SPLAY_RIGHT(elm, field) != NULL) { \ 142bf21cd93STycho Nightingale elm = SPLAY_RIGHT(elm, field); \ 143bf21cd93STycho Nightingale while (SPLAY_LEFT(elm, field) != NULL) { \ 144bf21cd93STycho Nightingale elm = SPLAY_LEFT(elm, field); \ 145bf21cd93STycho Nightingale } \ 146bf21cd93STycho Nightingale } else \ 147bf21cd93STycho Nightingale elm = NULL; \ 148bf21cd93STycho Nightingale return (elm); \ 149bf21cd93STycho Nightingale } \ 150bf21cd93STycho Nightingale \ 151bf21cd93STycho Nightingale static __inline struct type * \ 152bf21cd93STycho Nightingale name##_SPLAY_MIN_MAX(struct name *head, int val) \ 153bf21cd93STycho Nightingale { \ 154bf21cd93STycho Nightingale name##_SPLAY_MINMAX(head, val); \ 155bf21cd93STycho Nightingale return (SPLAY_ROOT(head)); \ 156bf21cd93STycho Nightingale } 157bf21cd93STycho Nightingale 158bf21cd93STycho Nightingale /* Main splay operation. 159bf21cd93STycho Nightingale * Moves node close to the key of elm to top 160bf21cd93STycho Nightingale */ 161bf21cd93STycho Nightingale #define SPLAY_GENERATE(name, type, field, cmp) \ 162bf21cd93STycho Nightingale struct type * \ 163bf21cd93STycho Nightingale name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 164bf21cd93STycho Nightingale { \ 165bf21cd93STycho Nightingale if (SPLAY_EMPTY(head)) { \ 166bf21cd93STycho Nightingale SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 167bf21cd93STycho Nightingale } else { \ 168bf21cd93STycho Nightingale int __comp; \ 169bf21cd93STycho Nightingale name##_SPLAY(head, elm); \ 170bf21cd93STycho Nightingale __comp = (cmp)(elm, (head)->sph_root); \ 171bf21cd93STycho Nightingale if(__comp < 0) { \ 172bf21cd93STycho Nightingale SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 173bf21cd93STycho Nightingale SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 174bf21cd93STycho Nightingale SPLAY_LEFT((head)->sph_root, field) = NULL; \ 175bf21cd93STycho Nightingale } else if (__comp > 0) { \ 176bf21cd93STycho Nightingale SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 177bf21cd93STycho Nightingale SPLAY_LEFT(elm, field) = (head)->sph_root; \ 178bf21cd93STycho Nightingale SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 179bf21cd93STycho Nightingale } else \ 180bf21cd93STycho Nightingale return ((head)->sph_root); \ 181bf21cd93STycho Nightingale } \ 182bf21cd93STycho Nightingale (head)->sph_root = (elm); \ 183bf21cd93STycho Nightingale return (NULL); \ 184bf21cd93STycho Nightingale } \ 185bf21cd93STycho Nightingale \ 186bf21cd93STycho Nightingale struct type * \ 187bf21cd93STycho Nightingale name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 188bf21cd93STycho Nightingale { \ 189bf21cd93STycho Nightingale struct type *__tmp; \ 190bf21cd93STycho Nightingale if (SPLAY_EMPTY(head)) \ 191bf21cd93STycho Nightingale return (NULL); \ 192bf21cd93STycho Nightingale name##_SPLAY(head, elm); \ 193bf21cd93STycho Nightingale if ((cmp)(elm, (head)->sph_root) == 0) { \ 194bf21cd93STycho Nightingale if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 195bf21cd93STycho Nightingale (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 196bf21cd93STycho Nightingale } else { \ 197bf21cd93STycho Nightingale __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 198bf21cd93STycho Nightingale (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 199bf21cd93STycho Nightingale name##_SPLAY(head, elm); \ 200bf21cd93STycho Nightingale SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 201bf21cd93STycho Nightingale } \ 202bf21cd93STycho Nightingale return (elm); \ 203bf21cd93STycho Nightingale } \ 204bf21cd93STycho Nightingale return (NULL); \ 205bf21cd93STycho Nightingale } \ 206bf21cd93STycho Nightingale \ 207bf21cd93STycho Nightingale void \ 208bf21cd93STycho Nightingale name##_SPLAY(struct name *head, struct type *elm) \ 209bf21cd93STycho Nightingale { \ 210bf21cd93STycho Nightingale struct type __node, *__left, *__right, *__tmp; \ 211bf21cd93STycho Nightingale int __comp; \ 212bf21cd93STycho Nightingale \ 213bf21cd93STycho Nightingale SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 214bf21cd93STycho Nightingale __left = __right = &__node; \ 215bf21cd93STycho Nightingale \ 216bf21cd93STycho Nightingale while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 217bf21cd93STycho Nightingale if (__comp < 0) { \ 218bf21cd93STycho Nightingale __tmp = SPLAY_LEFT((head)->sph_root, field); \ 219bf21cd93STycho Nightingale if (__tmp == NULL) \ 220bf21cd93STycho Nightingale break; \ 221bf21cd93STycho Nightingale if ((cmp)(elm, __tmp) < 0){ \ 222bf21cd93STycho Nightingale SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 223bf21cd93STycho Nightingale if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 224bf21cd93STycho Nightingale break; \ 225bf21cd93STycho Nightingale } \ 226bf21cd93STycho Nightingale SPLAY_LINKLEFT(head, __right, field); \ 227bf21cd93STycho Nightingale } else if (__comp > 0) { \ 228bf21cd93STycho Nightingale __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 229bf21cd93STycho Nightingale if (__tmp == NULL) \ 230bf21cd93STycho Nightingale break; \ 231bf21cd93STycho Nightingale if ((cmp)(elm, __tmp) > 0){ \ 232bf21cd93STycho Nightingale SPLAY_ROTATE_LEFT(head, __tmp, field); \ 233bf21cd93STycho Nightingale if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 234bf21cd93STycho Nightingale break; \ 235bf21cd93STycho Nightingale } \ 236bf21cd93STycho Nightingale SPLAY_LINKRIGHT(head, __left, field); \ 237bf21cd93STycho Nightingale } \ 238bf21cd93STycho Nightingale } \ 239bf21cd93STycho Nightingale SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 240bf21cd93STycho Nightingale } \ 241bf21cd93STycho Nightingale \ 242bf21cd93STycho Nightingale /* Splay with either the minimum or the maximum element \ 243bf21cd93STycho Nightingale * Used to find minimum or maximum element in tree. \ 244bf21cd93STycho Nightingale */ \ 245bf21cd93STycho Nightingale void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 246bf21cd93STycho Nightingale { \ 247bf21cd93STycho Nightingale struct type __node, *__left, *__right, *__tmp; \ 248bf21cd93STycho Nightingale \ 249bf21cd93STycho Nightingale SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 250bf21cd93STycho Nightingale __left = __right = &__node; \ 251bf21cd93STycho Nightingale \ 252bf21cd93STycho Nightingale while (1) { \ 253bf21cd93STycho Nightingale if (__comp < 0) { \ 254bf21cd93STycho Nightingale __tmp = SPLAY_LEFT((head)->sph_root, field); \ 255bf21cd93STycho Nightingale if (__tmp == NULL) \ 256bf21cd93STycho Nightingale break; \ 257bf21cd93STycho Nightingale if (__comp < 0){ \ 258bf21cd93STycho Nightingale SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 259bf21cd93STycho Nightingale if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 260bf21cd93STycho Nightingale break; \ 261bf21cd93STycho Nightingale } \ 262bf21cd93STycho Nightingale SPLAY_LINKLEFT(head, __right, field); \ 263bf21cd93STycho Nightingale } else if (__comp > 0) { \ 264bf21cd93STycho Nightingale __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 265bf21cd93STycho Nightingale if (__tmp == NULL) \ 266bf21cd93STycho Nightingale break; \ 267bf21cd93STycho Nightingale if (__comp > 0) { \ 268bf21cd93STycho Nightingale SPLAY_ROTATE_LEFT(head, __tmp, field); \ 269bf21cd93STycho Nightingale if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 270bf21cd93STycho Nightingale break; \ 271bf21cd93STycho Nightingale } \ 272bf21cd93STycho Nightingale SPLAY_LINKRIGHT(head, __left, field); \ 273bf21cd93STycho Nightingale } \ 274bf21cd93STycho Nightingale } \ 275bf21cd93STycho Nightingale SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 276bf21cd93STycho Nightingale } 277bf21cd93STycho Nightingale 278bf21cd93STycho Nightingale #define SPLAY_NEGINF -1 279bf21cd93STycho Nightingale #define SPLAY_INF 1 280bf21cd93STycho Nightingale 281bf21cd93STycho Nightingale #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 282bf21cd93STycho Nightingale #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 283bf21cd93STycho Nightingale #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 284bf21cd93STycho Nightingale #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 285bf21cd93STycho Nightingale #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 286bf21cd93STycho Nightingale : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 287bf21cd93STycho Nightingale #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 288bf21cd93STycho Nightingale : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 289bf21cd93STycho Nightingale 290bf21cd93STycho Nightingale #define SPLAY_FOREACH(x, name, head) \ 291bf21cd93STycho Nightingale for ((x) = SPLAY_MIN(name, head); \ 292bf21cd93STycho Nightingale (x) != NULL; \ 293bf21cd93STycho Nightingale (x) = SPLAY_NEXT(name, head, x)) 294bf21cd93STycho Nightingale 295bf21cd93STycho Nightingale /* Macros that define a red-black tree */ 296bf21cd93STycho Nightingale #define RB_HEAD(name, type) \ 297bf21cd93STycho Nightingale struct name { \ 298bf21cd93STycho Nightingale struct type *rbh_root; /* root of the tree */ \ 299bf21cd93STycho Nightingale } 300bf21cd93STycho Nightingale 301bf21cd93STycho Nightingale #define RB_INITIALIZER(root) \ 302bf21cd93STycho Nightingale { NULL } 303bf21cd93STycho Nightingale 304bf21cd93STycho Nightingale #define RB_INIT(root) do { \ 305bf21cd93STycho Nightingale (root)->rbh_root = NULL; \ 306bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 307bf21cd93STycho Nightingale 308bf21cd93STycho Nightingale #define RB_BLACK 0 309bf21cd93STycho Nightingale #define RB_RED 1 310bf21cd93STycho Nightingale #define RB_ENTRY(type) \ 311bf21cd93STycho Nightingale struct { \ 312bf21cd93STycho Nightingale struct type *rbe_left; /* left element */ \ 313bf21cd93STycho Nightingale struct type *rbe_right; /* right element */ \ 314bf21cd93STycho Nightingale struct type *rbe_parent; /* parent element */ \ 315bf21cd93STycho Nightingale int rbe_color; /* node color */ \ 316bf21cd93STycho Nightingale } 317bf21cd93STycho Nightingale 318bf21cd93STycho Nightingale #define RB_LEFT(elm, field) (elm)->field.rbe_left 319bf21cd93STycho Nightingale #define RB_RIGHT(elm, field) (elm)->field.rbe_right 320bf21cd93STycho Nightingale #define RB_PARENT(elm, field) (elm)->field.rbe_parent 321bf21cd93STycho Nightingale #define RB_COLOR(elm, field) (elm)->field.rbe_color 322bf21cd93STycho Nightingale #define RB_ROOT(head) (head)->rbh_root 323bf21cd93STycho Nightingale #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 324bf21cd93STycho Nightingale 325bf21cd93STycho Nightingale #define RB_SET(elm, parent, field) do { \ 326bf21cd93STycho Nightingale RB_PARENT(elm, field) = parent; \ 327bf21cd93STycho Nightingale RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 328bf21cd93STycho Nightingale RB_COLOR(elm, field) = RB_RED; \ 329bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 330bf21cd93STycho Nightingale 331bf21cd93STycho Nightingale #define RB_SET_BLACKRED(black, red, field) do { \ 332bf21cd93STycho Nightingale RB_COLOR(black, field) = RB_BLACK; \ 333bf21cd93STycho Nightingale RB_COLOR(red, field) = RB_RED; \ 334bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 335bf21cd93STycho Nightingale 336bf21cd93STycho Nightingale #ifndef RB_AUGMENT 337bf21cd93STycho Nightingale #define RB_AUGMENT(x) do {} while (0) 338bf21cd93STycho Nightingale #endif 339bf21cd93STycho Nightingale 340bf21cd93STycho Nightingale #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 341bf21cd93STycho Nightingale (tmp) = RB_RIGHT(elm, field); \ 342bf21cd93STycho Nightingale if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 343bf21cd93STycho Nightingale RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 344bf21cd93STycho Nightingale } \ 345bf21cd93STycho Nightingale RB_AUGMENT(elm); \ 346bf21cd93STycho Nightingale if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 347bf21cd93STycho Nightingale if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 348bf21cd93STycho Nightingale RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 349bf21cd93STycho Nightingale else \ 350bf21cd93STycho Nightingale RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 351bf21cd93STycho Nightingale } else \ 352bf21cd93STycho Nightingale (head)->rbh_root = (tmp); \ 353bf21cd93STycho Nightingale RB_LEFT(tmp, field) = (elm); \ 354bf21cd93STycho Nightingale RB_PARENT(elm, field) = (tmp); \ 355bf21cd93STycho Nightingale RB_AUGMENT(tmp); \ 356bf21cd93STycho Nightingale if ((RB_PARENT(tmp, field))) \ 357bf21cd93STycho Nightingale RB_AUGMENT(RB_PARENT(tmp, field)); \ 358bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 359bf21cd93STycho Nightingale 360bf21cd93STycho Nightingale #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 361bf21cd93STycho Nightingale (tmp) = RB_LEFT(elm, field); \ 362bf21cd93STycho Nightingale if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 363bf21cd93STycho Nightingale RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 364bf21cd93STycho Nightingale } \ 365bf21cd93STycho Nightingale RB_AUGMENT(elm); \ 366bf21cd93STycho Nightingale if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 367bf21cd93STycho Nightingale if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 368bf21cd93STycho Nightingale RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 369bf21cd93STycho Nightingale else \ 370bf21cd93STycho Nightingale RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 371bf21cd93STycho Nightingale } else \ 372bf21cd93STycho Nightingale (head)->rbh_root = (tmp); \ 373bf21cd93STycho Nightingale RB_RIGHT(tmp, field) = (elm); \ 374bf21cd93STycho Nightingale RB_PARENT(elm, field) = (tmp); \ 375bf21cd93STycho Nightingale RB_AUGMENT(tmp); \ 376bf21cd93STycho Nightingale if ((RB_PARENT(tmp, field))) \ 377bf21cd93STycho Nightingale RB_AUGMENT(RB_PARENT(tmp, field)); \ 378bf21cd93STycho Nightingale } while (/*CONSTCOND*/ 0) 379bf21cd93STycho Nightingale 380bf21cd93STycho Nightingale /* Generates prototypes and inline functions */ 381bf21cd93STycho Nightingale #define RB_PROTOTYPE(name, type, field, cmp) \ 382bf21cd93STycho Nightingale RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 383bf21cd93STycho Nightingale #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 384bf21cd93STycho Nightingale RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 385bf21cd93STycho Nightingale #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 386bf21cd93STycho Nightingale attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 387bf21cd93STycho Nightingale attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 388bf21cd93STycho Nightingale attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 389bf21cd93STycho Nightingale attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 390bf21cd93STycho Nightingale attr struct type *name##_RB_FIND(struct name *, struct type *); \ 391bf21cd93STycho Nightingale attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 392bf21cd93STycho Nightingale attr struct type *name##_RB_NEXT(struct type *); \ 393bf21cd93STycho Nightingale attr struct type *name##_RB_PREV(struct type *); \ 394bf21cd93STycho Nightingale attr struct type *name##_RB_MINMAX(struct name *, int); \ 395bf21cd93STycho Nightingale \ 396bf21cd93STycho Nightingale 397bf21cd93STycho Nightingale /* Main rb operation. 398bf21cd93STycho Nightingale * Moves node close to the key of elm to top 399bf21cd93STycho Nightingale */ 400bf21cd93STycho Nightingale #define RB_GENERATE(name, type, field, cmp) \ 401bf21cd93STycho Nightingale RB_GENERATE_INTERNAL(name, type, field, cmp,) 402bf21cd93STycho Nightingale #define RB_GENERATE_STATIC(name, type, field, cmp) \ 403bf21cd93STycho Nightingale RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 404bf21cd93STycho Nightingale #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 405bf21cd93STycho Nightingale attr void \ 406bf21cd93STycho Nightingale name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 407bf21cd93STycho Nightingale { \ 408bf21cd93STycho Nightingale struct type *parent, *gparent, *tmp; \ 409bf21cd93STycho Nightingale while ((parent = RB_PARENT(elm, field)) != NULL && \ 410bf21cd93STycho Nightingale RB_COLOR(parent, field) == RB_RED) { \ 411bf21cd93STycho Nightingale gparent = RB_PARENT(parent, field); \ 412bf21cd93STycho Nightingale if (parent == RB_LEFT(gparent, field)) { \ 413bf21cd93STycho Nightingale tmp = RB_RIGHT(gparent, field); \ 414bf21cd93STycho Nightingale if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 415bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_BLACK; \ 416bf21cd93STycho Nightingale RB_SET_BLACKRED(parent, gparent, field);\ 417bf21cd93STycho Nightingale elm = gparent; \ 418bf21cd93STycho Nightingale continue; \ 419bf21cd93STycho Nightingale } \ 420bf21cd93STycho Nightingale if (RB_RIGHT(parent, field) == elm) { \ 421bf21cd93STycho Nightingale RB_ROTATE_LEFT(head, parent, tmp, field);\ 422bf21cd93STycho Nightingale tmp = parent; \ 423bf21cd93STycho Nightingale parent = elm; \ 424bf21cd93STycho Nightingale elm = tmp; \ 425bf21cd93STycho Nightingale } \ 426bf21cd93STycho Nightingale RB_SET_BLACKRED(parent, gparent, field); \ 427bf21cd93STycho Nightingale RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 428bf21cd93STycho Nightingale } else { \ 429bf21cd93STycho Nightingale tmp = RB_LEFT(gparent, field); \ 430bf21cd93STycho Nightingale if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 431bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_BLACK; \ 432bf21cd93STycho Nightingale RB_SET_BLACKRED(parent, gparent, field);\ 433bf21cd93STycho Nightingale elm = gparent; \ 434bf21cd93STycho Nightingale continue; \ 435bf21cd93STycho Nightingale } \ 436bf21cd93STycho Nightingale if (RB_LEFT(parent, field) == elm) { \ 437bf21cd93STycho Nightingale RB_ROTATE_RIGHT(head, parent, tmp, field);\ 438bf21cd93STycho Nightingale tmp = parent; \ 439bf21cd93STycho Nightingale parent = elm; \ 440bf21cd93STycho Nightingale elm = tmp; \ 441bf21cd93STycho Nightingale } \ 442bf21cd93STycho Nightingale RB_SET_BLACKRED(parent, gparent, field); \ 443bf21cd93STycho Nightingale RB_ROTATE_LEFT(head, gparent, tmp, field); \ 444bf21cd93STycho Nightingale } \ 445bf21cd93STycho Nightingale } \ 446bf21cd93STycho Nightingale RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 447bf21cd93STycho Nightingale } \ 448bf21cd93STycho Nightingale \ 449bf21cd93STycho Nightingale attr void \ 450bf21cd93STycho Nightingale name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 451bf21cd93STycho Nightingale { \ 452bf21cd93STycho Nightingale struct type *tmp; \ 453bf21cd93STycho Nightingale while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 454bf21cd93STycho Nightingale elm != RB_ROOT(head)) { \ 455bf21cd93STycho Nightingale if (RB_LEFT(parent, field) == elm) { \ 456bf21cd93STycho Nightingale tmp = RB_RIGHT(parent, field); \ 457bf21cd93STycho Nightingale if (RB_COLOR(tmp, field) == RB_RED) { \ 458bf21cd93STycho Nightingale RB_SET_BLACKRED(tmp, parent, field); \ 459bf21cd93STycho Nightingale RB_ROTATE_LEFT(head, parent, tmp, field);\ 460bf21cd93STycho Nightingale tmp = RB_RIGHT(parent, field); \ 461bf21cd93STycho Nightingale } \ 462bf21cd93STycho Nightingale if ((RB_LEFT(tmp, field) == NULL || \ 463bf21cd93STycho Nightingale RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 464bf21cd93STycho Nightingale (RB_RIGHT(tmp, field) == NULL || \ 465bf21cd93STycho Nightingale RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 466bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_RED; \ 467bf21cd93STycho Nightingale elm = parent; \ 468bf21cd93STycho Nightingale parent = RB_PARENT(elm, field); \ 469bf21cd93STycho Nightingale } else { \ 470bf21cd93STycho Nightingale if (RB_RIGHT(tmp, field) == NULL || \ 471bf21cd93STycho Nightingale RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 472bf21cd93STycho Nightingale struct type *oleft; \ 473bf21cd93STycho Nightingale if ((oleft = RB_LEFT(tmp, field)) \ 474bf21cd93STycho Nightingale != NULL) \ 475bf21cd93STycho Nightingale RB_COLOR(oleft, field) = RB_BLACK;\ 476bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_RED; \ 477bf21cd93STycho Nightingale RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 478bf21cd93STycho Nightingale tmp = RB_RIGHT(parent, field); \ 479bf21cd93STycho Nightingale } \ 480bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 481bf21cd93STycho Nightingale RB_COLOR(parent, field) = RB_BLACK; \ 482bf21cd93STycho Nightingale if (RB_RIGHT(tmp, field)) \ 483bf21cd93STycho Nightingale RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 484bf21cd93STycho Nightingale RB_ROTATE_LEFT(head, parent, tmp, field);\ 485bf21cd93STycho Nightingale elm = RB_ROOT(head); \ 486bf21cd93STycho Nightingale break; \ 487bf21cd93STycho Nightingale } \ 488bf21cd93STycho Nightingale } else { \ 489bf21cd93STycho Nightingale tmp = RB_LEFT(parent, field); \ 490bf21cd93STycho Nightingale if (RB_COLOR(tmp, field) == RB_RED) { \ 491bf21cd93STycho Nightingale RB_SET_BLACKRED(tmp, parent, field); \ 492bf21cd93STycho Nightingale RB_ROTATE_RIGHT(head, parent, tmp, field);\ 493bf21cd93STycho Nightingale tmp = RB_LEFT(parent, field); \ 494bf21cd93STycho Nightingale } \ 495bf21cd93STycho Nightingale if ((RB_LEFT(tmp, field) == NULL || \ 496bf21cd93STycho Nightingale RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 497bf21cd93STycho Nightingale (RB_RIGHT(tmp, field) == NULL || \ 498bf21cd93STycho Nightingale RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 499bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_RED; \ 500bf21cd93STycho Nightingale elm = parent; \ 501bf21cd93STycho Nightingale parent = RB_PARENT(elm, field); \ 502bf21cd93STycho Nightingale } else { \ 503bf21cd93STycho Nightingale if (RB_LEFT(tmp, field) == NULL || \ 504bf21cd93STycho Nightingale RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 505bf21cd93STycho Nightingale struct type *oright; \ 506bf21cd93STycho Nightingale if ((oright = RB_RIGHT(tmp, field)) \ 507bf21cd93STycho Nightingale != NULL) \ 508bf21cd93STycho Nightingale RB_COLOR(oright, field) = RB_BLACK;\ 509bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_RED; \ 510bf21cd93STycho Nightingale RB_ROTATE_LEFT(head, tmp, oright, field);\ 511bf21cd93STycho Nightingale tmp = RB_LEFT(parent, field); \ 512bf21cd93STycho Nightingale } \ 513bf21cd93STycho Nightingale RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 514bf21cd93STycho Nightingale RB_COLOR(parent, field) = RB_BLACK; \ 515bf21cd93STycho Nightingale if (RB_LEFT(tmp, field)) \ 516bf21cd93STycho Nightingale RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 517bf21cd93STycho Nightingale RB_ROTATE_RIGHT(head, parent, tmp, field);\ 518bf21cd93STycho Nightingale elm = RB_ROOT(head); \ 519bf21cd93STycho Nightingale break; \ 520bf21cd93STycho Nightingale } \ 521bf21cd93STycho Nightingale } \ 522bf21cd93STycho Nightingale } \ 523bf21cd93STycho Nightingale if (elm) \ 524bf21cd93STycho Nightingale RB_COLOR(elm, field) = RB_BLACK; \ 525bf21cd93STycho Nightingale } \ 526bf21cd93STycho Nightingale \ 527bf21cd93STycho Nightingale attr struct type * \ 528bf21cd93STycho Nightingale name##_RB_REMOVE(struct name *head, struct type *elm) \ 529bf21cd93STycho Nightingale { \ 530bf21cd93STycho Nightingale struct type *child, *parent, *old = elm; \ 531bf21cd93STycho Nightingale int color; \ 532bf21cd93STycho Nightingale if (RB_LEFT(elm, field) == NULL) \ 533bf21cd93STycho Nightingale child = RB_RIGHT(elm, field); \ 534bf21cd93STycho Nightingale else if (RB_RIGHT(elm, field) == NULL) \ 535bf21cd93STycho Nightingale child = RB_LEFT(elm, field); \ 536bf21cd93STycho Nightingale else { \ 537bf21cd93STycho Nightingale struct type *left; \ 538bf21cd93STycho Nightingale elm = RB_RIGHT(elm, field); \ 539bf21cd93STycho Nightingale while ((left = RB_LEFT(elm, field)) != NULL) \ 540bf21cd93STycho Nightingale elm = left; \ 541bf21cd93STycho Nightingale child = RB_RIGHT(elm, field); \ 542bf21cd93STycho Nightingale parent = RB_PARENT(elm, field); \ 543bf21cd93STycho Nightingale color = RB_COLOR(elm, field); \ 544bf21cd93STycho Nightingale if (child) \ 545bf21cd93STycho Nightingale RB_PARENT(child, field) = parent; \ 546bf21cd93STycho Nightingale if (parent) { \ 547bf21cd93STycho Nightingale if (RB_LEFT(parent, field) == elm) \ 548bf21cd93STycho Nightingale RB_LEFT(parent, field) = child; \ 549bf21cd93STycho Nightingale else \ 550bf21cd93STycho Nightingale RB_RIGHT(parent, field) = child; \ 551bf21cd93STycho Nightingale RB_AUGMENT(parent); \ 552bf21cd93STycho Nightingale } else \ 553bf21cd93STycho Nightingale RB_ROOT(head) = child; \ 554bf21cd93STycho Nightingale if (RB_PARENT(elm, field) == old) \ 555bf21cd93STycho Nightingale parent = elm; \ 556bf21cd93STycho Nightingale (elm)->field = (old)->field; \ 557bf21cd93STycho Nightingale if (RB_PARENT(old, field)) { \ 558bf21cd93STycho Nightingale if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 559bf21cd93STycho Nightingale RB_LEFT(RB_PARENT(old, field), field) = elm;\ 560bf21cd93STycho Nightingale else \ 561bf21cd93STycho Nightingale RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 562bf21cd93STycho Nightingale RB_AUGMENT(RB_PARENT(old, field)); \ 563bf21cd93STycho Nightingale } else \ 564bf21cd93STycho Nightingale RB_ROOT(head) = elm; \ 565bf21cd93STycho Nightingale RB_PARENT(RB_LEFT(old, field), field) = elm; \ 566bf21cd93STycho Nightingale if (RB_RIGHT(old, field)) \ 567bf21cd93STycho Nightingale RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 568bf21cd93STycho Nightingale if (parent) { \ 569bf21cd93STycho Nightingale left = parent; \ 570bf21cd93STycho Nightingale do { \ 571bf21cd93STycho Nightingale RB_AUGMENT(left); \ 572bf21cd93STycho Nightingale } while ((left = RB_PARENT(left, field)) != NULL); \ 573bf21cd93STycho Nightingale } \ 574bf21cd93STycho Nightingale goto color; \ 575bf21cd93STycho Nightingale } \ 576bf21cd93STycho Nightingale parent = RB_PARENT(elm, field); \ 577bf21cd93STycho Nightingale color = RB_COLOR(elm, field); \ 578bf21cd93STycho Nightingale if (child) \ 579bf21cd93STycho Nightingale RB_PARENT(child, field) = parent; \ 580bf21cd93STycho Nightingale if (parent) { \ 581bf21cd93STycho Nightingale if (RB_LEFT(parent, field) == elm) \ 582bf21cd93STycho Nightingale RB_LEFT(parent, field) = child; \ 583bf21cd93STycho Nightingale else \ 584bf21cd93STycho Nightingale RB_RIGHT(parent, field) = child; \ 585bf21cd93STycho Nightingale RB_AUGMENT(parent); \ 586bf21cd93STycho Nightingale } else \ 587bf21cd93STycho Nightingale RB_ROOT(head) = child; \ 588bf21cd93STycho Nightingale color: \ 589bf21cd93STycho Nightingale if (color == RB_BLACK) \ 590bf21cd93STycho Nightingale name##_RB_REMOVE_COLOR(head, parent, child); \ 591bf21cd93STycho Nightingale return (old); \ 592bf21cd93STycho Nightingale } \ 593bf21cd93STycho Nightingale \ 594bf21cd93STycho Nightingale /* Inserts a node into the RB tree */ \ 595bf21cd93STycho Nightingale attr struct type * \ 596bf21cd93STycho Nightingale name##_RB_INSERT(struct name *head, struct type *elm) \ 597bf21cd93STycho Nightingale { \ 598bf21cd93STycho Nightingale struct type *tmp; \ 599bf21cd93STycho Nightingale struct type *parent = NULL; \ 600bf21cd93STycho Nightingale int comp = 0; \ 601bf21cd93STycho Nightingale tmp = RB_ROOT(head); \ 602bf21cd93STycho Nightingale while (tmp) { \ 603bf21cd93STycho Nightingale parent = tmp; \ 604bf21cd93STycho Nightingale comp = (cmp)(elm, parent); \ 605bf21cd93STycho Nightingale if (comp < 0) \ 606bf21cd93STycho Nightingale tmp = RB_LEFT(tmp, field); \ 607bf21cd93STycho Nightingale else if (comp > 0) \ 608bf21cd93STycho Nightingale tmp = RB_RIGHT(tmp, field); \ 609bf21cd93STycho Nightingale else \ 610bf21cd93STycho Nightingale return (tmp); \ 611bf21cd93STycho Nightingale } \ 612bf21cd93STycho Nightingale RB_SET(elm, parent, field); \ 613bf21cd93STycho Nightingale if (parent != NULL) { \ 614bf21cd93STycho Nightingale if (comp < 0) \ 615bf21cd93STycho Nightingale RB_LEFT(parent, field) = elm; \ 616bf21cd93STycho Nightingale else \ 617bf21cd93STycho Nightingale RB_RIGHT(parent, field) = elm; \ 618bf21cd93STycho Nightingale RB_AUGMENT(parent); \ 619bf21cd93STycho Nightingale } else \ 620bf21cd93STycho Nightingale RB_ROOT(head) = elm; \ 621bf21cd93STycho Nightingale name##_RB_INSERT_COLOR(head, elm); \ 622bf21cd93STycho Nightingale return (NULL); \ 623bf21cd93STycho Nightingale } \ 624bf21cd93STycho Nightingale \ 625bf21cd93STycho Nightingale /* Finds the node with the same key as elm */ \ 626bf21cd93STycho Nightingale attr struct type * \ 627bf21cd93STycho Nightingale name##_RB_FIND(struct name *head, struct type *elm) \ 628bf21cd93STycho Nightingale { \ 629bf21cd93STycho Nightingale struct type *tmp = RB_ROOT(head); \ 630bf21cd93STycho Nightingale int comp; \ 631bf21cd93STycho Nightingale while (tmp) { \ 632bf21cd93STycho Nightingale comp = cmp(elm, tmp); \ 633bf21cd93STycho Nightingale if (comp < 0) \ 634bf21cd93STycho Nightingale tmp = RB_LEFT(tmp, field); \ 635bf21cd93STycho Nightingale else if (comp > 0) \ 636bf21cd93STycho Nightingale tmp = RB_RIGHT(tmp, field); \ 637bf21cd93STycho Nightingale else \ 638bf21cd93STycho Nightingale return (tmp); \ 639bf21cd93STycho Nightingale } \ 640bf21cd93STycho Nightingale return (NULL); \ 641bf21cd93STycho Nightingale } \ 642bf21cd93STycho Nightingale \ 643bf21cd93STycho Nightingale /* Finds the first node greater than or equal to the search key */ \ 644bf21cd93STycho Nightingale attr struct type * \ 645bf21cd93STycho Nightingale name##_RB_NFIND(struct name *head, struct type *elm) \ 646bf21cd93STycho Nightingale { \ 647bf21cd93STycho Nightingale struct type *tmp = RB_ROOT(head); \ 648bf21cd93STycho Nightingale struct type *res = NULL; \ 649bf21cd93STycho Nightingale int comp; \ 650bf21cd93STycho Nightingale while (tmp) { \ 651bf21cd93STycho Nightingale comp = cmp(elm, tmp); \ 652bf21cd93STycho Nightingale if (comp < 0) { \ 653bf21cd93STycho Nightingale res = tmp; \ 654bf21cd93STycho Nightingale tmp = RB_LEFT(tmp, field); \ 655bf21cd93STycho Nightingale } \ 656bf21cd93STycho Nightingale else if (comp > 0) \ 657bf21cd93STycho Nightingale tmp = RB_RIGHT(tmp, field); \ 658bf21cd93STycho Nightingale else \ 659bf21cd93STycho Nightingale return (tmp); \ 660bf21cd93STycho Nightingale } \ 661bf21cd93STycho Nightingale return (res); \ 662bf21cd93STycho Nightingale } \ 663bf21cd93STycho Nightingale \ 664bf21cd93STycho Nightingale /* ARGSUSED */ \ 665bf21cd93STycho Nightingale attr struct type * \ 666bf21cd93STycho Nightingale name##_RB_NEXT(struct type *elm) \ 667bf21cd93STycho Nightingale { \ 668bf21cd93STycho Nightingale if (RB_RIGHT(elm, field)) { \ 669bf21cd93STycho Nightingale elm = RB_RIGHT(elm, field); \ 670bf21cd93STycho Nightingale while (RB_LEFT(elm, field)) \ 671bf21cd93STycho Nightingale elm = RB_LEFT(elm, field); \ 672bf21cd93STycho Nightingale } else { \ 673bf21cd93STycho Nightingale if (RB_PARENT(elm, field) && \ 674bf21cd93STycho Nightingale (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 675bf21cd93STycho Nightingale elm = RB_PARENT(elm, field); \ 676bf21cd93STycho Nightingale else { \ 677bf21cd93STycho Nightingale while (RB_PARENT(elm, field) && \ 678bf21cd93STycho Nightingale (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 679bf21cd93STycho Nightingale elm = RB_PARENT(elm, field); \ 680bf21cd93STycho Nightingale elm = RB_PARENT(elm, field); \ 681bf21cd93STycho Nightingale } \ 682bf21cd93STycho Nightingale } \ 683bf21cd93STycho Nightingale return (elm); \ 684bf21cd93STycho Nightingale } \ 685bf21cd93STycho Nightingale \ 686bf21cd93STycho Nightingale /* ARGSUSED */ \ 687bf21cd93STycho Nightingale attr struct type * \ 688bf21cd93STycho Nightingale name##_RB_PREV(struct type *elm) \ 689bf21cd93STycho Nightingale { \ 690bf21cd93STycho Nightingale if (RB_LEFT(elm, field)) { \ 691bf21cd93STycho Nightingale elm = RB_LEFT(elm, field); \ 692bf21cd93STycho Nightingale while (RB_RIGHT(elm, field)) \ 693bf21cd93STycho Nightingale elm = RB_RIGHT(elm, field); \ 694bf21cd93STycho Nightingale } else { \ 695bf21cd93STycho Nightingale if (RB_PARENT(elm, field) && \ 696bf21cd93STycho Nightingale (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 697bf21cd93STycho Nightingale elm = RB_PARENT(elm, field); \ 698bf21cd93STycho Nightingale else { \ 699bf21cd93STycho Nightingale while (RB_PARENT(elm, field) && \ 700bf21cd93STycho Nightingale (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 701bf21cd93STycho Nightingale elm = RB_PARENT(elm, field); \ 702bf21cd93STycho Nightingale elm = RB_PARENT(elm, field); \ 703bf21cd93STycho Nightingale } \ 704bf21cd93STycho Nightingale } \ 705bf21cd93STycho Nightingale return (elm); \ 706bf21cd93STycho Nightingale } \ 707bf21cd93STycho Nightingale \ 708bf21cd93STycho Nightingale attr struct type * \ 709bf21cd93STycho Nightingale name##_RB_MINMAX(struct name *head, int val) \ 710bf21cd93STycho Nightingale { \ 711bf21cd93STycho Nightingale struct type *tmp = RB_ROOT(head); \ 712bf21cd93STycho Nightingale struct type *parent = NULL; \ 713bf21cd93STycho Nightingale while (tmp) { \ 714bf21cd93STycho Nightingale parent = tmp; \ 715bf21cd93STycho Nightingale if (val < 0) \ 716bf21cd93STycho Nightingale tmp = RB_LEFT(tmp, field); \ 717bf21cd93STycho Nightingale else \ 718bf21cd93STycho Nightingale tmp = RB_RIGHT(tmp, field); \ 719bf21cd93STycho Nightingale } \ 720bf21cd93STycho Nightingale return (parent); \ 721bf21cd93STycho Nightingale } 722bf21cd93STycho Nightingale 723bf21cd93STycho Nightingale #define RB_NEGINF -1 724bf21cd93STycho Nightingale #define RB_INF 1 725bf21cd93STycho Nightingale 726bf21cd93STycho Nightingale #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 727bf21cd93STycho Nightingale #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 728bf21cd93STycho Nightingale #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 729bf21cd93STycho Nightingale #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 730bf21cd93STycho Nightingale #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 731bf21cd93STycho Nightingale #define RB_PREV(name, x, y) name##_RB_PREV(y) 732bf21cd93STycho Nightingale #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 733bf21cd93STycho Nightingale #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 734bf21cd93STycho Nightingale 735bf21cd93STycho Nightingale #define RB_FOREACH(x, name, head) \ 736bf21cd93STycho Nightingale for ((x) = RB_MIN(name, head); \ 737bf21cd93STycho Nightingale (x) != NULL; \ 738bf21cd93STycho Nightingale (x) = name##_RB_NEXT(x)) 739bf21cd93STycho Nightingale 740bf21cd93STycho Nightingale #define RB_FOREACH_FROM(x, name, y) \ 741bf21cd93STycho Nightingale for ((x) = (y); \ 742bf21cd93STycho Nightingale ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 743bf21cd93STycho Nightingale (x) = (y)) 744bf21cd93STycho Nightingale 745bf21cd93STycho Nightingale #define RB_FOREACH_SAFE(x, name, head, y) \ 746bf21cd93STycho Nightingale for ((x) = RB_MIN(name, head); \ 747bf21cd93STycho Nightingale ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 748bf21cd93STycho Nightingale (x) = (y)) 749bf21cd93STycho Nightingale 750bf21cd93STycho Nightingale #define RB_FOREACH_REVERSE(x, name, head) \ 751bf21cd93STycho Nightingale for ((x) = RB_MAX(name, head); \ 752bf21cd93STycho Nightingale (x) != NULL; \ 753bf21cd93STycho Nightingale (x) = name##_RB_PREV(x)) 754bf21cd93STycho Nightingale 755bf21cd93STycho Nightingale #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 756bf21cd93STycho Nightingale for ((x) = (y); \ 757bf21cd93STycho Nightingale ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 758bf21cd93STycho Nightingale (x) = (y)) 759bf21cd93STycho Nightingale 760bf21cd93STycho Nightingale #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 761bf21cd93STycho Nightingale for ((x) = RB_MAX(name, head); \ 762bf21cd93STycho Nightingale ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 763bf21cd93STycho Nightingale (x) = (y)) 764bf21cd93STycho Nightingale 765bf21cd93STycho Nightingale #endif /* _SYS_TREE_H_ */ 766