10Sstevel@tonic-gate /* $OpenBSD: tree.h,v 1.6 2002/06/11 22:09:52 provos Exp $ */ 20Sstevel@tonic-gate /* 30Sstevel@tonic-gate * Copyright 2002 Niels Provos <provos@citi.umich.edu> 40Sstevel@tonic-gate * All rights reserved. 50Sstevel@tonic-gate * 60Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 70Sstevel@tonic-gate * modification, are permitted provided that the following conditions 80Sstevel@tonic-gate * are met: 90Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright 100Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer. 110Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright 120Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the 130Sstevel@tonic-gate * documentation and/or other materials provided with the distribution. 140Sstevel@tonic-gate * 150Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 160Sstevel@tonic-gate * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 170Sstevel@tonic-gate * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 180Sstevel@tonic-gate * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 190Sstevel@tonic-gate * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 200Sstevel@tonic-gate * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 210Sstevel@tonic-gate * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 220Sstevel@tonic-gate * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 230Sstevel@tonic-gate * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 240Sstevel@tonic-gate * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 250Sstevel@tonic-gate */ 260Sstevel@tonic-gate 270Sstevel@tonic-gate #ifndef _SYS_TREE_H 280Sstevel@tonic-gate #define _SYS_TREE_H 290Sstevel@tonic-gate 300Sstevel@tonic-gate #ifdef __cplusplus 310Sstevel@tonic-gate extern "C" { 320Sstevel@tonic-gate #endif 330Sstevel@tonic-gate 340Sstevel@tonic-gate /* 350Sstevel@tonic-gate * This file defines data structures for different types of trees: 360Sstevel@tonic-gate * splay trees and red-black trees. 370Sstevel@tonic-gate * 380Sstevel@tonic-gate * A splay tree is a self-organizing data structure. Every operation 390Sstevel@tonic-gate * on the tree causes a splay to happen. The splay moves the requested 400Sstevel@tonic-gate * node to the root of the tree and partly rebalances it. 410Sstevel@tonic-gate * 420Sstevel@tonic-gate * This has the benefit that request locality causes faster lookups as 430Sstevel@tonic-gate * the requested nodes move to the top of the tree. On the other hand, 440Sstevel@tonic-gate * every lookup causes memory writes. 450Sstevel@tonic-gate * 460Sstevel@tonic-gate * The Balance Theorem bounds the total access time for m operations 470Sstevel@tonic-gate * and n inserts on an initially empty tree as O((m + n)lg n). The 480Sstevel@tonic-gate * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 490Sstevel@tonic-gate * 500Sstevel@tonic-gate * A red-black tree is a binary search tree with the node color as an 510Sstevel@tonic-gate * extra attribute. It fulfills a set of conditions: 520Sstevel@tonic-gate * - every search path from the root to a leaf consists of the 530Sstevel@tonic-gate * same number of black nodes, 540Sstevel@tonic-gate * - each red node (except for the root) has a black parent, 550Sstevel@tonic-gate * - each leaf node is black. 560Sstevel@tonic-gate * 570Sstevel@tonic-gate * Every operation on a red-black tree is bounded as O(lg n). 580Sstevel@tonic-gate * The maximum height of a red-black tree is 2lg (n+1). 590Sstevel@tonic-gate */ 600Sstevel@tonic-gate 610Sstevel@tonic-gate #define SPLAY_HEAD(name, type) \ 620Sstevel@tonic-gate struct name { \ 630Sstevel@tonic-gate struct type *sph_root; /* root of the tree */ \ 640Sstevel@tonic-gate } 650Sstevel@tonic-gate 660Sstevel@tonic-gate #define SPLAY_INITIALIZER(root) \ 670Sstevel@tonic-gate { NULL } 680Sstevel@tonic-gate 690Sstevel@tonic-gate #define SPLAY_INIT(root) do { \ 700Sstevel@tonic-gate (root)->sph_root = NULL; \ 710Sstevel@tonic-gate } while (0) 720Sstevel@tonic-gate 730Sstevel@tonic-gate #define SPLAY_ENTRY(type) \ 740Sstevel@tonic-gate struct { \ 750Sstevel@tonic-gate struct type *spe_left; /* left element */ \ 760Sstevel@tonic-gate struct type *spe_right; /* right element */ \ 770Sstevel@tonic-gate } 780Sstevel@tonic-gate 790Sstevel@tonic-gate #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 800Sstevel@tonic-gate #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 810Sstevel@tonic-gate #define SPLAY_ROOT(head) (head)->sph_root 820Sstevel@tonic-gate #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 830Sstevel@tonic-gate 840Sstevel@tonic-gate /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 850Sstevel@tonic-gate #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 860Sstevel@tonic-gate SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 870Sstevel@tonic-gate SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 880Sstevel@tonic-gate (head)->sph_root = tmp; \ 890Sstevel@tonic-gate } while (0) 900Sstevel@tonic-gate 910Sstevel@tonic-gate #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 920Sstevel@tonic-gate SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 930Sstevel@tonic-gate SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 940Sstevel@tonic-gate (head)->sph_root = tmp; \ 950Sstevel@tonic-gate } while (0) 960Sstevel@tonic-gate 970Sstevel@tonic-gate #define SPLAY_LINKLEFT(head, tmp, field) do { \ 980Sstevel@tonic-gate SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 990Sstevel@tonic-gate tmp = (head)->sph_root; \ 1000Sstevel@tonic-gate (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 1010Sstevel@tonic-gate } while (0) 1020Sstevel@tonic-gate 1030Sstevel@tonic-gate #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 1040Sstevel@tonic-gate SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 1050Sstevel@tonic-gate tmp = (head)->sph_root; \ 1060Sstevel@tonic-gate (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 1070Sstevel@tonic-gate } while (0) 1080Sstevel@tonic-gate 1090Sstevel@tonic-gate #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 1100Sstevel@tonic-gate SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 1110Sstevel@tonic-gate SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 1120Sstevel@tonic-gate SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 1130Sstevel@tonic-gate SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 1140Sstevel@tonic-gate } while (0) 1150Sstevel@tonic-gate 1160Sstevel@tonic-gate /* Generates prototypes and inline functions */ 1170Sstevel@tonic-gate 1180Sstevel@tonic-gate #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 1190Sstevel@tonic-gate void name##_SPLAY(struct name *, struct type *); \ 1200Sstevel@tonic-gate void name##_SPLAY_MINMAX(struct name *, int); \ 1210Sstevel@tonic-gate struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 1220Sstevel@tonic-gate struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 1230Sstevel@tonic-gate \ 1240Sstevel@tonic-gate /* Finds the node with the same key as elm */ \ 1250Sstevel@tonic-gate static __inline struct type * \ 1260Sstevel@tonic-gate name##_SPLAY_FIND(struct name *head, struct type *elm) \ 1270Sstevel@tonic-gate { \ 1280Sstevel@tonic-gate if (SPLAY_EMPTY(head)) \ 1290Sstevel@tonic-gate return(NULL); \ 1300Sstevel@tonic-gate name##_SPLAY(head, elm); \ 1310Sstevel@tonic-gate if ((cmp)(elm, (head)->sph_root) == 0) \ 1320Sstevel@tonic-gate return (head->sph_root); \ 1330Sstevel@tonic-gate return (NULL); \ 1340Sstevel@tonic-gate } \ 1350Sstevel@tonic-gate \ 1360Sstevel@tonic-gate static __inline struct type * \ 1370Sstevel@tonic-gate name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 1380Sstevel@tonic-gate { \ 1390Sstevel@tonic-gate name##_SPLAY(head, elm); \ 1400Sstevel@tonic-gate if (SPLAY_RIGHT(elm, field) != NULL) { \ 1410Sstevel@tonic-gate elm = SPLAY_RIGHT(elm, field); \ 1420Sstevel@tonic-gate while (SPLAY_LEFT(elm, field) != NULL) { \ 1430Sstevel@tonic-gate elm = SPLAY_LEFT(elm, field); \ 1440Sstevel@tonic-gate } \ 1450Sstevel@tonic-gate } else \ 1460Sstevel@tonic-gate elm = NULL; \ 1470Sstevel@tonic-gate return (elm); \ 1480Sstevel@tonic-gate } \ 1490Sstevel@tonic-gate \ 1500Sstevel@tonic-gate static __inline struct type * \ 1510Sstevel@tonic-gate name##_SPLAY_MIN_MAX(struct name *head, int val) \ 1520Sstevel@tonic-gate { \ 1530Sstevel@tonic-gate name##_SPLAY_MINMAX(head, val); \ 1540Sstevel@tonic-gate return (SPLAY_ROOT(head)); \ 1550Sstevel@tonic-gate } 1560Sstevel@tonic-gate 1570Sstevel@tonic-gate /* Main splay operation. 1580Sstevel@tonic-gate * Moves node close to the key of elm to top 1590Sstevel@tonic-gate */ 1600Sstevel@tonic-gate #define SPLAY_GENERATE(name, type, field, cmp) \ 1610Sstevel@tonic-gate struct type * \ 1620Sstevel@tonic-gate name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 1630Sstevel@tonic-gate { \ 1640Sstevel@tonic-gate if (SPLAY_EMPTY(head)) { \ 1650Sstevel@tonic-gate SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 1660Sstevel@tonic-gate } else { \ 1670Sstevel@tonic-gate int __comp; \ 1680Sstevel@tonic-gate name##_SPLAY(head, elm); \ 1690Sstevel@tonic-gate __comp = (cmp)(elm, (head)->sph_root); \ 1700Sstevel@tonic-gate if(__comp < 0) { \ 1710Sstevel@tonic-gate SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 1720Sstevel@tonic-gate SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 1730Sstevel@tonic-gate SPLAY_LEFT((head)->sph_root, field) = NULL; \ 1740Sstevel@tonic-gate } else if (__comp > 0) { \ 1750Sstevel@tonic-gate SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 1760Sstevel@tonic-gate SPLAY_LEFT(elm, field) = (head)->sph_root; \ 1770Sstevel@tonic-gate SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 1780Sstevel@tonic-gate } else \ 1790Sstevel@tonic-gate return ((head)->sph_root); \ 1800Sstevel@tonic-gate } \ 1810Sstevel@tonic-gate (head)->sph_root = (elm); \ 1820Sstevel@tonic-gate return (NULL); \ 1830Sstevel@tonic-gate } \ 1840Sstevel@tonic-gate \ 1850Sstevel@tonic-gate struct type * \ 1860Sstevel@tonic-gate name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 1870Sstevel@tonic-gate { \ 1880Sstevel@tonic-gate struct type *__tmp; \ 1890Sstevel@tonic-gate if (SPLAY_EMPTY(head)) \ 1900Sstevel@tonic-gate return (NULL); \ 1910Sstevel@tonic-gate name##_SPLAY(head, elm); \ 1920Sstevel@tonic-gate if ((cmp)(elm, (head)->sph_root) == 0) { \ 1930Sstevel@tonic-gate if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 1940Sstevel@tonic-gate (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 1950Sstevel@tonic-gate } else { \ 1960Sstevel@tonic-gate __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 1970Sstevel@tonic-gate (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 1980Sstevel@tonic-gate name##_SPLAY(head, elm); \ 1990Sstevel@tonic-gate SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 2000Sstevel@tonic-gate } \ 2010Sstevel@tonic-gate return (elm); \ 2020Sstevel@tonic-gate } \ 2030Sstevel@tonic-gate return (NULL); \ 2040Sstevel@tonic-gate } \ 2050Sstevel@tonic-gate \ 2060Sstevel@tonic-gate void \ 2070Sstevel@tonic-gate name##_SPLAY(struct name *head, struct type *elm) \ 2080Sstevel@tonic-gate { \ 2090Sstevel@tonic-gate struct type __node, *__left, *__right, *__tmp; \ 2100Sstevel@tonic-gate int __comp; \ 2110Sstevel@tonic-gate \ 2120Sstevel@tonic-gate SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 2130Sstevel@tonic-gate __left = __right = &__node; \ 2140Sstevel@tonic-gate \ 2150Sstevel@tonic-gate while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 2160Sstevel@tonic-gate if (__comp < 0) { \ 2170Sstevel@tonic-gate __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2180Sstevel@tonic-gate if (__tmp == NULL) \ 2190Sstevel@tonic-gate break; \ 2200Sstevel@tonic-gate if ((cmp)(elm, __tmp) < 0){ \ 2210Sstevel@tonic-gate SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2220Sstevel@tonic-gate if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 2230Sstevel@tonic-gate break; \ 2240Sstevel@tonic-gate } \ 2250Sstevel@tonic-gate SPLAY_LINKLEFT(head, __right, field); \ 2260Sstevel@tonic-gate } else if (__comp > 0) { \ 2270Sstevel@tonic-gate __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2280Sstevel@tonic-gate if (__tmp == NULL) \ 2290Sstevel@tonic-gate break; \ 2300Sstevel@tonic-gate if ((cmp)(elm, __tmp) > 0){ \ 2310Sstevel@tonic-gate SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2320Sstevel@tonic-gate if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 2330Sstevel@tonic-gate break; \ 2340Sstevel@tonic-gate } \ 2350Sstevel@tonic-gate SPLAY_LINKRIGHT(head, __left, field); \ 2360Sstevel@tonic-gate } \ 2370Sstevel@tonic-gate } \ 2380Sstevel@tonic-gate SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2390Sstevel@tonic-gate } \ 2400Sstevel@tonic-gate \ 2410Sstevel@tonic-gate /* Splay with either the minimum or the maximum element \ 2420Sstevel@tonic-gate * Used to find minimum or maximum element in tree. \ 2430Sstevel@tonic-gate */ \ 2440Sstevel@tonic-gate void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 2450Sstevel@tonic-gate { \ 2460Sstevel@tonic-gate struct type __node, *__left, *__right, *__tmp; \ 2470Sstevel@tonic-gate \ 2480Sstevel@tonic-gate SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 2490Sstevel@tonic-gate __left = __right = &__node; \ 2500Sstevel@tonic-gate \ 2510Sstevel@tonic-gate while (1) { \ 2520Sstevel@tonic-gate if (__comp < 0) { \ 2530Sstevel@tonic-gate __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2540Sstevel@tonic-gate if (__tmp == NULL) \ 2550Sstevel@tonic-gate break; \ 2560Sstevel@tonic-gate if (__comp < 0){ \ 2570Sstevel@tonic-gate SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2580Sstevel@tonic-gate if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 2590Sstevel@tonic-gate break; \ 2600Sstevel@tonic-gate } \ 2610Sstevel@tonic-gate SPLAY_LINKLEFT(head, __right, field); \ 2620Sstevel@tonic-gate } else if (__comp > 0) { \ 2630Sstevel@tonic-gate __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2640Sstevel@tonic-gate if (__tmp == NULL) \ 2650Sstevel@tonic-gate break; \ 2660Sstevel@tonic-gate if (__comp > 0) { \ 2670Sstevel@tonic-gate SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2680Sstevel@tonic-gate if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 2690Sstevel@tonic-gate break; \ 2700Sstevel@tonic-gate } \ 2710Sstevel@tonic-gate SPLAY_LINKRIGHT(head, __left, field); \ 2720Sstevel@tonic-gate } \ 2730Sstevel@tonic-gate } \ 2740Sstevel@tonic-gate SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2750Sstevel@tonic-gate } 2760Sstevel@tonic-gate 2770Sstevel@tonic-gate #define SPLAY_NEGINF -1 2780Sstevel@tonic-gate #define SPLAY_INF 1 2790Sstevel@tonic-gate 2800Sstevel@tonic-gate #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 2810Sstevel@tonic-gate #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 2820Sstevel@tonic-gate #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 2830Sstevel@tonic-gate #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 2840Sstevel@tonic-gate #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 2850Sstevel@tonic-gate : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 2860Sstevel@tonic-gate #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 2870Sstevel@tonic-gate : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 2880Sstevel@tonic-gate 2890Sstevel@tonic-gate #define SPLAY_FOREACH(x, name, head) \ 2900Sstevel@tonic-gate for ((x) = SPLAY_MIN(name, head); \ 2910Sstevel@tonic-gate (x) != NULL; \ 2920Sstevel@tonic-gate (x) = SPLAY_NEXT(name, head, x)) 2930Sstevel@tonic-gate 2940Sstevel@tonic-gate /* Macros that define a red-back tree */ 2950Sstevel@tonic-gate #define RB_HEAD(name, type) \ 2960Sstevel@tonic-gate struct name { \ 2970Sstevel@tonic-gate struct type *rbh_root; /* root of the tree */ \ 2980Sstevel@tonic-gate } 2990Sstevel@tonic-gate 3000Sstevel@tonic-gate #define RB_INITIALIZER(root) \ 3010Sstevel@tonic-gate { NULL } 3020Sstevel@tonic-gate 3030Sstevel@tonic-gate #define RB_INIT(root) do { \ 3040Sstevel@tonic-gate (root)->rbh_root = NULL; \ 3050Sstevel@tonic-gate } while (0) 3060Sstevel@tonic-gate 3070Sstevel@tonic-gate #define RB_BLACK 0 3080Sstevel@tonic-gate #define RB_RED 1 3090Sstevel@tonic-gate #define RB_ENTRY(type) \ 3100Sstevel@tonic-gate struct { \ 3110Sstevel@tonic-gate struct type *rbe_left; /* left element */ \ 3120Sstevel@tonic-gate struct type *rbe_right; /* right element */ \ 3130Sstevel@tonic-gate struct type *rbe_parent; /* parent element */ \ 3140Sstevel@tonic-gate int rbe_color; /* node color */ \ 3150Sstevel@tonic-gate } 3160Sstevel@tonic-gate 3170Sstevel@tonic-gate #define RB_LEFT(elm, field) (elm)->field.rbe_left 3180Sstevel@tonic-gate #define RB_RIGHT(elm, field) (elm)->field.rbe_right 3190Sstevel@tonic-gate #define RB_PARENT(elm, field) (elm)->field.rbe_parent 3200Sstevel@tonic-gate #define RB_COLOR(elm, field) (elm)->field.rbe_color 3210Sstevel@tonic-gate #define RB_ROOT(head) (head)->rbh_root 3220Sstevel@tonic-gate #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 3230Sstevel@tonic-gate 3240Sstevel@tonic-gate #define RB_SET(elm, parent, field) do { \ 3250Sstevel@tonic-gate RB_PARENT(elm, field) = parent; \ 3260Sstevel@tonic-gate RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 3270Sstevel@tonic-gate RB_COLOR(elm, field) = RB_RED; \ 3280Sstevel@tonic-gate } while (0) 3290Sstevel@tonic-gate 3300Sstevel@tonic-gate #define RB_SET_BLACKRED(black, red, field) do { \ 3310Sstevel@tonic-gate RB_COLOR(black, field) = RB_BLACK; \ 3320Sstevel@tonic-gate RB_COLOR(red, field) = RB_RED; \ 3330Sstevel@tonic-gate } while (0) 3340Sstevel@tonic-gate 3350Sstevel@tonic-gate #ifndef RB_AUGMENT 3360Sstevel@tonic-gate #define RB_AUGMENT(x) 3370Sstevel@tonic-gate #endif 3380Sstevel@tonic-gate 3390Sstevel@tonic-gate #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 3400Sstevel@tonic-gate (tmp) = RB_RIGHT(elm, field); \ 3410Sstevel@tonic-gate if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 3420Sstevel@tonic-gate RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 3430Sstevel@tonic-gate } \ 3440Sstevel@tonic-gate RB_AUGMENT(elm); \ 3450Sstevel@tonic-gate if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 3460Sstevel@tonic-gate if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3470Sstevel@tonic-gate RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3480Sstevel@tonic-gate else \ 3490Sstevel@tonic-gate RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3500Sstevel@tonic-gate RB_AUGMENT(RB_PARENT(elm, field)); \ 3510Sstevel@tonic-gate } else \ 3520Sstevel@tonic-gate (head)->rbh_root = (tmp); \ 3530Sstevel@tonic-gate RB_LEFT(tmp, field) = (elm); \ 3540Sstevel@tonic-gate RB_PARENT(elm, field) = (tmp); \ 3550Sstevel@tonic-gate RB_AUGMENT(tmp); \ 3560Sstevel@tonic-gate } while (0) 3570Sstevel@tonic-gate 3580Sstevel@tonic-gate #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 3590Sstevel@tonic-gate (tmp) = RB_LEFT(elm, field); \ 3600Sstevel@tonic-gate if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 3610Sstevel@tonic-gate RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 3620Sstevel@tonic-gate } \ 3630Sstevel@tonic-gate RB_AUGMENT(elm); \ 3640Sstevel@tonic-gate if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 3650Sstevel@tonic-gate if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3660Sstevel@tonic-gate RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3670Sstevel@tonic-gate else \ 3680Sstevel@tonic-gate RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3690Sstevel@tonic-gate RB_AUGMENT(RB_PARENT(elm, field)); \ 3700Sstevel@tonic-gate } else \ 3710Sstevel@tonic-gate (head)->rbh_root = (tmp); \ 3720Sstevel@tonic-gate RB_RIGHT(tmp, field) = (elm); \ 3730Sstevel@tonic-gate RB_PARENT(elm, field) = (tmp); \ 3740Sstevel@tonic-gate RB_AUGMENT(tmp); \ 3750Sstevel@tonic-gate } while (0) 3760Sstevel@tonic-gate 3770Sstevel@tonic-gate /* Generates prototypes and inline functions */ 3780Sstevel@tonic-gate #define RB_PROTOTYPE(name, type, field, cmp) \ 3790Sstevel@tonic-gate void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 3800Sstevel@tonic-gate void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 3810Sstevel@tonic-gate struct type *name##_RB_REMOVE(struct name *, struct type *); \ 3820Sstevel@tonic-gate struct type *name##_RB_INSERT(struct name *, struct type *); \ 3830Sstevel@tonic-gate struct type *name##_RB_FIND(struct name *, struct type *); \ 3840Sstevel@tonic-gate struct type *name##_RB_NEXT(struct name *, struct type *); \ 385*9845SJan.Pechanec@Sun.COM struct type *name##_RB_MINMAX(struct name *, int); 3860Sstevel@tonic-gate 3870Sstevel@tonic-gate /* Main rb operation. 3880Sstevel@tonic-gate * Moves node close to the key of elm to top 3890Sstevel@tonic-gate */ 3900Sstevel@tonic-gate #define RB_GENERATE(name, type, field, cmp) \ 3910Sstevel@tonic-gate void \ 3920Sstevel@tonic-gate name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 3930Sstevel@tonic-gate { \ 3940Sstevel@tonic-gate struct type *parent, *gparent, *tmp; \ 3950Sstevel@tonic-gate while ((parent = RB_PARENT(elm, field)) && \ 3960Sstevel@tonic-gate RB_COLOR(parent, field) == RB_RED) { \ 3970Sstevel@tonic-gate gparent = RB_PARENT(parent, field); \ 3980Sstevel@tonic-gate if (parent == RB_LEFT(gparent, field)) { \ 3990Sstevel@tonic-gate tmp = RB_RIGHT(gparent, field); \ 4000Sstevel@tonic-gate if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4010Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_BLACK; \ 4020Sstevel@tonic-gate RB_SET_BLACKRED(parent, gparent, field);\ 4030Sstevel@tonic-gate elm = gparent; \ 4040Sstevel@tonic-gate continue; \ 4050Sstevel@tonic-gate } \ 4060Sstevel@tonic-gate if (RB_RIGHT(parent, field) == elm) { \ 4070Sstevel@tonic-gate RB_ROTATE_LEFT(head, parent, tmp, field);\ 4080Sstevel@tonic-gate tmp = parent; \ 4090Sstevel@tonic-gate parent = elm; \ 4100Sstevel@tonic-gate elm = tmp; \ 4110Sstevel@tonic-gate } \ 4120Sstevel@tonic-gate RB_SET_BLACKRED(parent, gparent, field); \ 4130Sstevel@tonic-gate RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 4140Sstevel@tonic-gate } else { \ 4150Sstevel@tonic-gate tmp = RB_LEFT(gparent, field); \ 4160Sstevel@tonic-gate if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4170Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_BLACK; \ 4180Sstevel@tonic-gate RB_SET_BLACKRED(parent, gparent, field);\ 4190Sstevel@tonic-gate elm = gparent; \ 4200Sstevel@tonic-gate continue; \ 4210Sstevel@tonic-gate } \ 4220Sstevel@tonic-gate if (RB_LEFT(parent, field) == elm) { \ 4230Sstevel@tonic-gate RB_ROTATE_RIGHT(head, parent, tmp, field);\ 4240Sstevel@tonic-gate tmp = parent; \ 4250Sstevel@tonic-gate parent = elm; \ 4260Sstevel@tonic-gate elm = tmp; \ 4270Sstevel@tonic-gate } \ 4280Sstevel@tonic-gate RB_SET_BLACKRED(parent, gparent, field); \ 4290Sstevel@tonic-gate RB_ROTATE_LEFT(head, gparent, tmp, field); \ 4300Sstevel@tonic-gate } \ 4310Sstevel@tonic-gate } \ 4320Sstevel@tonic-gate RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 4330Sstevel@tonic-gate } \ 4340Sstevel@tonic-gate \ 4350Sstevel@tonic-gate void \ 4360Sstevel@tonic-gate name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 4370Sstevel@tonic-gate { \ 4380Sstevel@tonic-gate struct type *tmp; \ 4390Sstevel@tonic-gate while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 4400Sstevel@tonic-gate elm != RB_ROOT(head)) { \ 4410Sstevel@tonic-gate if (RB_LEFT(parent, field) == elm) { \ 4420Sstevel@tonic-gate tmp = RB_RIGHT(parent, field); \ 4430Sstevel@tonic-gate if (RB_COLOR(tmp, field) == RB_RED) { \ 4440Sstevel@tonic-gate RB_SET_BLACKRED(tmp, parent, field); \ 4450Sstevel@tonic-gate RB_ROTATE_LEFT(head, parent, tmp, field);\ 4460Sstevel@tonic-gate tmp = RB_RIGHT(parent, field); \ 4470Sstevel@tonic-gate } \ 4480Sstevel@tonic-gate if ((RB_LEFT(tmp, field) == NULL || \ 4490Sstevel@tonic-gate RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 4500Sstevel@tonic-gate (RB_RIGHT(tmp, field) == NULL || \ 4510Sstevel@tonic-gate RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 4520Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_RED; \ 4530Sstevel@tonic-gate elm = parent; \ 4540Sstevel@tonic-gate parent = RB_PARENT(elm, field); \ 4550Sstevel@tonic-gate } else { \ 4560Sstevel@tonic-gate if (RB_RIGHT(tmp, field) == NULL || \ 4570Sstevel@tonic-gate RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 4580Sstevel@tonic-gate struct type *oleft; \ 4590Sstevel@tonic-gate if ((oleft = RB_LEFT(tmp, field)))\ 4600Sstevel@tonic-gate RB_COLOR(oleft, field) = RB_BLACK;\ 4610Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_RED; \ 4620Sstevel@tonic-gate RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 4630Sstevel@tonic-gate tmp = RB_RIGHT(parent, field); \ 4640Sstevel@tonic-gate } \ 4650Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 4660Sstevel@tonic-gate RB_COLOR(parent, field) = RB_BLACK; \ 4670Sstevel@tonic-gate if (RB_RIGHT(tmp, field)) \ 4680Sstevel@tonic-gate RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 4690Sstevel@tonic-gate RB_ROTATE_LEFT(head, parent, tmp, field);\ 4700Sstevel@tonic-gate elm = RB_ROOT(head); \ 4710Sstevel@tonic-gate break; \ 4720Sstevel@tonic-gate } \ 4730Sstevel@tonic-gate } else { \ 4740Sstevel@tonic-gate tmp = RB_LEFT(parent, field); \ 4750Sstevel@tonic-gate if (RB_COLOR(tmp, field) == RB_RED) { \ 4760Sstevel@tonic-gate RB_SET_BLACKRED(tmp, parent, field); \ 4770Sstevel@tonic-gate RB_ROTATE_RIGHT(head, parent, tmp, field);\ 4780Sstevel@tonic-gate tmp = RB_LEFT(parent, field); \ 4790Sstevel@tonic-gate } \ 4800Sstevel@tonic-gate if ((RB_LEFT(tmp, field) == NULL || \ 4810Sstevel@tonic-gate RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 4820Sstevel@tonic-gate (RB_RIGHT(tmp, field) == NULL || \ 4830Sstevel@tonic-gate RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 4840Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_RED; \ 4850Sstevel@tonic-gate elm = parent; \ 4860Sstevel@tonic-gate parent = RB_PARENT(elm, field); \ 4870Sstevel@tonic-gate } else { \ 4880Sstevel@tonic-gate if (RB_LEFT(tmp, field) == NULL || \ 4890Sstevel@tonic-gate RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 4900Sstevel@tonic-gate struct type *oright; \ 4910Sstevel@tonic-gate if ((oright = RB_RIGHT(tmp, field)))\ 4920Sstevel@tonic-gate RB_COLOR(oright, field) = RB_BLACK;\ 4930Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_RED; \ 4940Sstevel@tonic-gate RB_ROTATE_LEFT(head, tmp, oright, field);\ 4950Sstevel@tonic-gate tmp = RB_LEFT(parent, field); \ 4960Sstevel@tonic-gate } \ 4970Sstevel@tonic-gate RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 4980Sstevel@tonic-gate RB_COLOR(parent, field) = RB_BLACK; \ 4990Sstevel@tonic-gate if (RB_LEFT(tmp, field)) \ 5000Sstevel@tonic-gate RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 5010Sstevel@tonic-gate RB_ROTATE_RIGHT(head, parent, tmp, field);\ 5020Sstevel@tonic-gate elm = RB_ROOT(head); \ 5030Sstevel@tonic-gate break; \ 5040Sstevel@tonic-gate } \ 5050Sstevel@tonic-gate } \ 5060Sstevel@tonic-gate } \ 5070Sstevel@tonic-gate if (elm) \ 5080Sstevel@tonic-gate RB_COLOR(elm, field) = RB_BLACK; \ 5090Sstevel@tonic-gate } \ 5100Sstevel@tonic-gate \ 5110Sstevel@tonic-gate struct type * \ 5120Sstevel@tonic-gate name##_RB_REMOVE(struct name *head, struct type *elm) \ 5130Sstevel@tonic-gate { \ 5140Sstevel@tonic-gate struct type *child, *parent, *old = elm; \ 5150Sstevel@tonic-gate int color; \ 5160Sstevel@tonic-gate if (RB_LEFT(elm, field) == NULL) \ 5170Sstevel@tonic-gate child = RB_RIGHT(elm, field); \ 5180Sstevel@tonic-gate else if (RB_RIGHT(elm, field) == NULL) \ 5190Sstevel@tonic-gate child = RB_LEFT(elm, field); \ 5200Sstevel@tonic-gate else { \ 5210Sstevel@tonic-gate struct type *left; \ 5220Sstevel@tonic-gate elm = RB_RIGHT(elm, field); \ 5230Sstevel@tonic-gate while ((left = RB_LEFT(elm, field))) \ 5240Sstevel@tonic-gate elm = left; \ 5250Sstevel@tonic-gate child = RB_RIGHT(elm, field); \ 5260Sstevel@tonic-gate parent = RB_PARENT(elm, field); \ 5270Sstevel@tonic-gate color = RB_COLOR(elm, field); \ 5280Sstevel@tonic-gate if (child) \ 5290Sstevel@tonic-gate RB_PARENT(child, field) = parent; \ 5300Sstevel@tonic-gate if (parent) { \ 5310Sstevel@tonic-gate if (RB_LEFT(parent, field) == elm) \ 5320Sstevel@tonic-gate RB_LEFT(parent, field) = child; \ 5330Sstevel@tonic-gate else \ 5340Sstevel@tonic-gate RB_RIGHT(parent, field) = child; \ 5350Sstevel@tonic-gate RB_AUGMENT(parent); \ 5360Sstevel@tonic-gate } else \ 5370Sstevel@tonic-gate RB_ROOT(head) = child; \ 5380Sstevel@tonic-gate if (RB_PARENT(elm, field) == old) \ 5390Sstevel@tonic-gate parent = elm; \ 5400Sstevel@tonic-gate (elm)->field = (old)->field; \ 5410Sstevel@tonic-gate if (RB_PARENT(old, field)) { \ 5420Sstevel@tonic-gate if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 5430Sstevel@tonic-gate RB_LEFT(RB_PARENT(old, field), field) = elm;\ 5440Sstevel@tonic-gate else \ 5450Sstevel@tonic-gate RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 5460Sstevel@tonic-gate RB_AUGMENT(RB_PARENT(old, field)); \ 5470Sstevel@tonic-gate } else \ 5480Sstevel@tonic-gate RB_ROOT(head) = elm; \ 5490Sstevel@tonic-gate RB_PARENT(RB_LEFT(old, field), field) = elm; \ 5500Sstevel@tonic-gate if (RB_RIGHT(old, field)) \ 5510Sstevel@tonic-gate RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 5520Sstevel@tonic-gate if (parent) { \ 5530Sstevel@tonic-gate left = parent; \ 5540Sstevel@tonic-gate do { \ 5550Sstevel@tonic-gate RB_AUGMENT(left); \ 5560Sstevel@tonic-gate } while ((left = RB_PARENT(left, field))); \ 5570Sstevel@tonic-gate } \ 5580Sstevel@tonic-gate goto color; \ 5590Sstevel@tonic-gate } \ 5600Sstevel@tonic-gate parent = RB_PARENT(elm, field); \ 5610Sstevel@tonic-gate color = RB_COLOR(elm, field); \ 5620Sstevel@tonic-gate if (child) \ 5630Sstevel@tonic-gate RB_PARENT(child, field) = parent; \ 5640Sstevel@tonic-gate if (parent) { \ 5650Sstevel@tonic-gate if (RB_LEFT(parent, field) == elm) \ 5660Sstevel@tonic-gate RB_LEFT(parent, field) = child; \ 5670Sstevel@tonic-gate else \ 5680Sstevel@tonic-gate RB_RIGHT(parent, field) = child; \ 5690Sstevel@tonic-gate RB_AUGMENT(parent); \ 5700Sstevel@tonic-gate } else \ 5710Sstevel@tonic-gate RB_ROOT(head) = child; \ 5720Sstevel@tonic-gate color: \ 5730Sstevel@tonic-gate if (color == RB_BLACK) \ 5740Sstevel@tonic-gate name##_RB_REMOVE_COLOR(head, parent, child); \ 5750Sstevel@tonic-gate return (old); \ 5760Sstevel@tonic-gate } \ 5770Sstevel@tonic-gate \ 5780Sstevel@tonic-gate /* Inserts a node into the RB tree */ \ 5790Sstevel@tonic-gate struct type * \ 5800Sstevel@tonic-gate name##_RB_INSERT(struct name *head, struct type *elm) \ 5810Sstevel@tonic-gate { \ 5820Sstevel@tonic-gate struct type *tmp; \ 5830Sstevel@tonic-gate struct type *parent = NULL; \ 5840Sstevel@tonic-gate int comp = 0; \ 5850Sstevel@tonic-gate tmp = RB_ROOT(head); \ 5860Sstevel@tonic-gate while (tmp) { \ 5870Sstevel@tonic-gate parent = tmp; \ 5880Sstevel@tonic-gate comp = (cmp)(elm, parent); \ 5890Sstevel@tonic-gate if (comp < 0) \ 5900Sstevel@tonic-gate tmp = RB_LEFT(tmp, field); \ 5910Sstevel@tonic-gate else if (comp > 0) \ 5920Sstevel@tonic-gate tmp = RB_RIGHT(tmp, field); \ 5930Sstevel@tonic-gate else \ 5940Sstevel@tonic-gate return (tmp); \ 5950Sstevel@tonic-gate } \ 5960Sstevel@tonic-gate RB_SET(elm, parent, field); \ 5970Sstevel@tonic-gate if (parent != NULL) { \ 5980Sstevel@tonic-gate if (comp < 0) \ 5990Sstevel@tonic-gate RB_LEFT(parent, field) = elm; \ 6000Sstevel@tonic-gate else \ 6010Sstevel@tonic-gate RB_RIGHT(parent, field) = elm; \ 6020Sstevel@tonic-gate RB_AUGMENT(parent); \ 6030Sstevel@tonic-gate } else \ 6040Sstevel@tonic-gate RB_ROOT(head) = elm; \ 6050Sstevel@tonic-gate name##_RB_INSERT_COLOR(head, elm); \ 6060Sstevel@tonic-gate return (NULL); \ 6070Sstevel@tonic-gate } \ 6080Sstevel@tonic-gate \ 6090Sstevel@tonic-gate /* Finds the node with the same key as elm */ \ 6100Sstevel@tonic-gate struct type * \ 6110Sstevel@tonic-gate name##_RB_FIND(struct name *head, struct type *elm) \ 6120Sstevel@tonic-gate { \ 6130Sstevel@tonic-gate struct type *tmp = RB_ROOT(head); \ 6140Sstevel@tonic-gate int comp; \ 6150Sstevel@tonic-gate while (tmp) { \ 6160Sstevel@tonic-gate comp = cmp(elm, tmp); \ 6170Sstevel@tonic-gate if (comp < 0) \ 6180Sstevel@tonic-gate tmp = RB_LEFT(tmp, field); \ 6190Sstevel@tonic-gate else if (comp > 0) \ 6200Sstevel@tonic-gate tmp = RB_RIGHT(tmp, field); \ 6210Sstevel@tonic-gate else \ 6220Sstevel@tonic-gate return (tmp); \ 6230Sstevel@tonic-gate } \ 6240Sstevel@tonic-gate return (NULL); \ 6250Sstevel@tonic-gate } \ 6260Sstevel@tonic-gate \ 6270Sstevel@tonic-gate struct type * \ 6280Sstevel@tonic-gate name##_RB_NEXT(struct name *head, struct type *elm) \ 6290Sstevel@tonic-gate { \ 6300Sstevel@tonic-gate if (RB_RIGHT(elm, field)) { \ 6310Sstevel@tonic-gate elm = RB_RIGHT(elm, field); \ 6320Sstevel@tonic-gate while (RB_LEFT(elm, field)) \ 6330Sstevel@tonic-gate elm = RB_LEFT(elm, field); \ 6340Sstevel@tonic-gate } else { \ 6350Sstevel@tonic-gate if (RB_PARENT(elm, field) && \ 6360Sstevel@tonic-gate (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 6370Sstevel@tonic-gate elm = RB_PARENT(elm, field); \ 6380Sstevel@tonic-gate else { \ 6390Sstevel@tonic-gate while (RB_PARENT(elm, field) && \ 6400Sstevel@tonic-gate (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 6410Sstevel@tonic-gate elm = RB_PARENT(elm, field); \ 6420Sstevel@tonic-gate elm = RB_PARENT(elm, field); \ 6430Sstevel@tonic-gate } \ 6440Sstevel@tonic-gate } \ 6450Sstevel@tonic-gate return (elm); \ 6460Sstevel@tonic-gate } \ 6470Sstevel@tonic-gate \ 6480Sstevel@tonic-gate struct type * \ 6490Sstevel@tonic-gate name##_RB_MINMAX(struct name *head, int val) \ 6500Sstevel@tonic-gate { \ 6510Sstevel@tonic-gate struct type *tmp = RB_ROOT(head); \ 6520Sstevel@tonic-gate struct type *parent = NULL; \ 6530Sstevel@tonic-gate while (tmp) { \ 6540Sstevel@tonic-gate parent = tmp; \ 6550Sstevel@tonic-gate if (val < 0) \ 6560Sstevel@tonic-gate tmp = RB_LEFT(tmp, field); \ 6570Sstevel@tonic-gate else \ 6580Sstevel@tonic-gate tmp = RB_RIGHT(tmp, field); \ 6590Sstevel@tonic-gate } \ 6600Sstevel@tonic-gate return (parent); \ 6610Sstevel@tonic-gate } 6620Sstevel@tonic-gate 6630Sstevel@tonic-gate #define RB_NEGINF -1 6640Sstevel@tonic-gate #define RB_INF 1 6650Sstevel@tonic-gate 6660Sstevel@tonic-gate #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 6670Sstevel@tonic-gate #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 6680Sstevel@tonic-gate #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 6690Sstevel@tonic-gate #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y) 6700Sstevel@tonic-gate #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 6710Sstevel@tonic-gate #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 6720Sstevel@tonic-gate 6730Sstevel@tonic-gate #define RB_FOREACH(x, name, head) \ 6740Sstevel@tonic-gate for ((x) = RB_MIN(name, head); \ 6750Sstevel@tonic-gate (x) != NULL; \ 6760Sstevel@tonic-gate (x) = name##_RB_NEXT(head, x)) 6770Sstevel@tonic-gate 6780Sstevel@tonic-gate #ifdef __cplusplus 6790Sstevel@tonic-gate } 6800Sstevel@tonic-gate #endif 6810Sstevel@tonic-gate 6820Sstevel@tonic-gate #endif /* _SYS_TREE_H */ 683