tree.h revision 154227
1127563Sdes/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2127208Sdes/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3139824Simp/* $FreeBSD: head/sys/sys/tree.h 154227 2006-01-11 15:48:36Z jasone $ */ 4139824Simp 5139824Simp/*- 698679Sdes * Copyright 2002 Niels Provos <provos@citi.umich.edu> 798679Sdes * All rights reserved. 898679Sdes * 998679Sdes * Redistribution and use in source and binary forms, with or without 1098679Sdes * modification, are permitted provided that the following conditions 1198679Sdes * are met: 1298679Sdes * 1. Redistributions of source code must retain the above copyright 1398679Sdes * notice, this list of conditions and the following disclaimer. 1498679Sdes * 2. Redistributions in binary form must reproduce the above copyright 1598679Sdes * notice, this list of conditions and the following disclaimer in the 1698679Sdes * documentation and/or other materials provided with the distribution. 1798679Sdes * 1898679Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1998679Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2098679Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2198679Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2298679Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2398679Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2498679Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2598679Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2698679Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2798679Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2898679Sdes */ 2998679Sdes 3098679Sdes#ifndef _SYS_TREE_H_ 3198679Sdes#define _SYS_TREE_H_ 3298679Sdes 3398679Sdes/* 3498679Sdes * This file defines data structures for different types of trees: 3598679Sdes * splay trees and red-black trees. 3698679Sdes * 3798679Sdes * A splay tree is a self-organizing data structure. Every operation 3898679Sdes * on the tree causes a splay to happen. The splay moves the requested 3998679Sdes * node to the root of the tree and partly rebalances it. 4098679Sdes * 4198679Sdes * This has the benefit that request locality causes faster lookups as 4298679Sdes * the requested nodes move to the top of the tree. On the other hand, 4398679Sdes * every lookup causes memory writes. 4498679Sdes * 4598679Sdes * The Balance Theorem bounds the total access time for m operations 4698679Sdes * and n inserts on an initially empty tree as O((m + n)lg n). The 4798679Sdes * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 4898679Sdes * 4998679Sdes * A red-black tree is a binary search tree with the node color as an 5098679Sdes * extra attribute. It fulfills a set of conditions: 5198679Sdes * - every search path from the root to a leaf consists of the 5298679Sdes * same number of black nodes, 5398679Sdes * - each red node (except for the root) has a black parent, 5498679Sdes * - each leaf node is black. 5598679Sdes * 5698679Sdes * Every operation on a red-black tree is bounded as O(lg n). 5798679Sdes * The maximum height of a red-black tree is 2lg (n+1). 5898679Sdes */ 5998679Sdes 6098679Sdes#define SPLAY_HEAD(name, type) \ 6198679Sdesstruct name { \ 6298679Sdes struct type *sph_root; /* root of the tree */ \ 6398679Sdes} 6498679Sdes 6598679Sdes#define SPLAY_INITIALIZER(root) \ 6698679Sdes { NULL } 6798679Sdes 6898679Sdes#define SPLAY_INIT(root) do { \ 6998679Sdes (root)->sph_root = NULL; \ 70127403Sdes} while (/*CONSTCOND*/ 0) 7198679Sdes 7298679Sdes#define SPLAY_ENTRY(type) \ 7398679Sdesstruct { \ 7498679Sdes struct type *spe_left; /* left element */ \ 7598679Sdes struct type *spe_right; /* right element */ \ 7698679Sdes} 7798679Sdes 7898679Sdes#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 7998679Sdes#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 8098679Sdes#define SPLAY_ROOT(head) (head)->sph_root 8198679Sdes#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 8298679Sdes 8398679Sdes/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 8498679Sdes#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 8598679Sdes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 8698679Sdes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 8798679Sdes (head)->sph_root = tmp; \ 88127403Sdes} while (/*CONSTCOND*/ 0) 8998679Sdes 9098679Sdes#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 9198679Sdes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 9298679Sdes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 9398679Sdes (head)->sph_root = tmp; \ 94127403Sdes} while (/*CONSTCOND*/ 0) 9598679Sdes 9698679Sdes#define SPLAY_LINKLEFT(head, tmp, field) do { \ 9798679Sdes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 9898679Sdes tmp = (head)->sph_root; \ 9998679Sdes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 100127403Sdes} while (/*CONSTCOND*/ 0) 10198679Sdes 10298679Sdes#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 10398679Sdes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 10498679Sdes tmp = (head)->sph_root; \ 10598679Sdes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 106127403Sdes} while (/*CONSTCOND*/ 0) 10798679Sdes 10898679Sdes#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 10998679Sdes SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 11098679Sdes SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 11198679Sdes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 11298679Sdes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 113127403Sdes} while (/*CONSTCOND*/ 0) 11498679Sdes 11598679Sdes/* Generates prototypes and inline functions */ 11698679Sdes 11798679Sdes#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 11898679Sdesvoid name##_SPLAY(struct name *, struct type *); \ 11998679Sdesvoid name##_SPLAY_MINMAX(struct name *, int); \ 12098679Sdesstruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 12198679Sdesstruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 12298679Sdes \ 12398679Sdes/* Finds the node with the same key as elm */ \ 12498679Sdesstatic __inline struct type * \ 12598679Sdesname##_SPLAY_FIND(struct name *head, struct type *elm) \ 12698679Sdes{ \ 12798679Sdes if (SPLAY_EMPTY(head)) \ 12898679Sdes return(NULL); \ 12998679Sdes name##_SPLAY(head, elm); \ 13098679Sdes if ((cmp)(elm, (head)->sph_root) == 0) \ 13198679Sdes return (head->sph_root); \ 13298679Sdes return (NULL); \ 13398679Sdes} \ 13498679Sdes \ 13598679Sdesstatic __inline struct type * \ 13698679Sdesname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 13798679Sdes{ \ 13898679Sdes name##_SPLAY(head, elm); \ 13998679Sdes if (SPLAY_RIGHT(elm, field) != NULL) { \ 14098679Sdes elm = SPLAY_RIGHT(elm, field); \ 14198679Sdes while (SPLAY_LEFT(elm, field) != NULL) { \ 14298679Sdes elm = SPLAY_LEFT(elm, field); \ 14398679Sdes } \ 14498679Sdes } else \ 14598679Sdes elm = NULL; \ 14698679Sdes return (elm); \ 14798679Sdes} \ 14898679Sdes \ 14998679Sdesstatic __inline struct type * \ 15098679Sdesname##_SPLAY_MIN_MAX(struct name *head, int val) \ 15198679Sdes{ \ 15298679Sdes name##_SPLAY_MINMAX(head, val); \ 15398679Sdes return (SPLAY_ROOT(head)); \ 15498679Sdes} 15598679Sdes 15698679Sdes/* Main splay operation. 15798679Sdes * Moves node close to the key of elm to top 15898679Sdes */ 15998679Sdes#define SPLAY_GENERATE(name, type, field, cmp) \ 16098679Sdesstruct type * \ 16198679Sdesname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 16298679Sdes{ \ 16398679Sdes if (SPLAY_EMPTY(head)) { \ 16498679Sdes SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 16598679Sdes } else { \ 16698679Sdes int __comp; \ 16798679Sdes name##_SPLAY(head, elm); \ 16898679Sdes __comp = (cmp)(elm, (head)->sph_root); \ 16998679Sdes if(__comp < 0) { \ 17098679Sdes SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 17198679Sdes SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 17298679Sdes SPLAY_LEFT((head)->sph_root, field) = NULL; \ 17398679Sdes } else if (__comp > 0) { \ 17498679Sdes SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 17598679Sdes SPLAY_LEFT(elm, field) = (head)->sph_root; \ 17698679Sdes SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 17798679Sdes } else \ 17898679Sdes return ((head)->sph_root); \ 17998679Sdes } \ 18098679Sdes (head)->sph_root = (elm); \ 18198679Sdes return (NULL); \ 18298679Sdes} \ 18398679Sdes \ 18498679Sdesstruct type * \ 18598679Sdesname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 18698679Sdes{ \ 18798679Sdes struct type *__tmp; \ 18898679Sdes if (SPLAY_EMPTY(head)) \ 18998679Sdes return (NULL); \ 19098679Sdes name##_SPLAY(head, elm); \ 19198679Sdes if ((cmp)(elm, (head)->sph_root) == 0) { \ 19298679Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 19398679Sdes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 19498679Sdes } else { \ 19598679Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 19698679Sdes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 19798679Sdes name##_SPLAY(head, elm); \ 19898679Sdes SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 19998679Sdes } \ 20098679Sdes return (elm); \ 20198679Sdes } \ 20298679Sdes return (NULL); \ 20398679Sdes} \ 20498679Sdes \ 20598679Sdesvoid \ 20698679Sdesname##_SPLAY(struct name *head, struct type *elm) \ 20798679Sdes{ \ 20898679Sdes struct type __node, *__left, *__right, *__tmp; \ 20998679Sdes int __comp; \ 21098679Sdes\ 21198679Sdes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 21298679Sdes __left = __right = &__node; \ 21398679Sdes\ 214127403Sdes while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 21598679Sdes if (__comp < 0) { \ 21698679Sdes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 21798679Sdes if (__tmp == NULL) \ 21898679Sdes break; \ 21998679Sdes if ((cmp)(elm, __tmp) < 0){ \ 22098679Sdes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 22198679Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 22298679Sdes break; \ 22398679Sdes } \ 22498679Sdes SPLAY_LINKLEFT(head, __right, field); \ 22598679Sdes } else if (__comp > 0) { \ 22698679Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 22798679Sdes if (__tmp == NULL) \ 22898679Sdes break; \ 22998679Sdes if ((cmp)(elm, __tmp) > 0){ \ 23098679Sdes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 23198679Sdes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 23298679Sdes break; \ 23398679Sdes } \ 23498679Sdes SPLAY_LINKRIGHT(head, __left, field); \ 23598679Sdes } \ 23698679Sdes } \ 23798679Sdes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 23898679Sdes} \ 23998679Sdes \ 24098679Sdes/* Splay with either the minimum or the maximum element \ 24198679Sdes * Used to find minimum or maximum element in tree. \ 24298679Sdes */ \ 24398679Sdesvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 24498679Sdes{ \ 24598679Sdes struct type __node, *__left, *__right, *__tmp; \ 24698679Sdes\ 24798679Sdes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 24898679Sdes __left = __right = &__node; \ 24998679Sdes\ 25098679Sdes while (1) { \ 25198679Sdes if (__comp < 0) { \ 25298679Sdes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 25398679Sdes if (__tmp == NULL) \ 25498679Sdes break; \ 25598679Sdes if (__comp < 0){ \ 25698679Sdes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 25798679Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 25898679Sdes break; \ 25998679Sdes } \ 26098679Sdes SPLAY_LINKLEFT(head, __right, field); \ 26198679Sdes } else if (__comp > 0) { \ 26298679Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 26398679Sdes if (__tmp == NULL) \ 26498679Sdes break; \ 26598679Sdes if (__comp > 0) { \ 26698679Sdes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 26798679Sdes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 26898679Sdes break; \ 26998679Sdes } \ 27098679Sdes SPLAY_LINKRIGHT(head, __left, field); \ 27198679Sdes } \ 27298679Sdes } \ 27398679Sdes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 27498679Sdes} 27598679Sdes 27698679Sdes#define SPLAY_NEGINF -1 27798679Sdes#define SPLAY_INF 1 27898679Sdes 27998679Sdes#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 28098679Sdes#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 28198679Sdes#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 28298679Sdes#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 28398679Sdes#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 28498679Sdes : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 28598679Sdes#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 28698679Sdes : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 28798679Sdes 28898679Sdes#define SPLAY_FOREACH(x, name, head) \ 28998679Sdes for ((x) = SPLAY_MIN(name, head); \ 29098679Sdes (x) != NULL; \ 29198679Sdes (x) = SPLAY_NEXT(name, head, x)) 29298679Sdes 293127403Sdes/* Macros that define a red-black tree */ 29498679Sdes#define RB_HEAD(name, type) \ 29598679Sdesstruct name { \ 29698679Sdes struct type *rbh_root; /* root of the tree */ \ 29798679Sdes} 29898679Sdes 29998679Sdes#define RB_INITIALIZER(root) \ 30098679Sdes { NULL } 30198679Sdes 30298679Sdes#define RB_INIT(root) do { \ 30398679Sdes (root)->rbh_root = NULL; \ 304127403Sdes} while (/*CONSTCOND*/ 0) 30598679Sdes 30698679Sdes#define RB_BLACK 0 30798679Sdes#define RB_RED 1 30898679Sdes#define RB_ENTRY(type) \ 30998679Sdesstruct { \ 31098679Sdes struct type *rbe_left; /* left element */ \ 31198679Sdes struct type *rbe_right; /* right element */ \ 31298679Sdes struct type *rbe_parent; /* parent element */ \ 31398679Sdes int rbe_color; /* node color */ \ 31498679Sdes} 31598679Sdes 31698679Sdes#define RB_LEFT(elm, field) (elm)->field.rbe_left 31798679Sdes#define RB_RIGHT(elm, field) (elm)->field.rbe_right 31898679Sdes#define RB_PARENT(elm, field) (elm)->field.rbe_parent 31998679Sdes#define RB_COLOR(elm, field) (elm)->field.rbe_color 32098679Sdes#define RB_ROOT(head) (head)->rbh_root 32198679Sdes#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 32298679Sdes 32398679Sdes#define RB_SET(elm, parent, field) do { \ 32498679Sdes RB_PARENT(elm, field) = parent; \ 32598679Sdes RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 32698679Sdes RB_COLOR(elm, field) = RB_RED; \ 327127403Sdes} while (/*CONSTCOND*/ 0) 32898679Sdes 32998679Sdes#define RB_SET_BLACKRED(black, red, field) do { \ 33098679Sdes RB_COLOR(black, field) = RB_BLACK; \ 33198679Sdes RB_COLOR(red, field) = RB_RED; \ 332127403Sdes} while (/*CONSTCOND*/ 0) 33398679Sdes 33498679Sdes#ifndef RB_AUGMENT 335147245Sharti#define RB_AUGMENT(x) do {} while (0) 33698679Sdes#endif 33798679Sdes 33898679Sdes#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 33998679Sdes (tmp) = RB_RIGHT(elm, field); \ 340127403Sdes if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 34198679Sdes RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 34298679Sdes } \ 34398679Sdes RB_AUGMENT(elm); \ 344127403Sdes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 34598679Sdes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 34698679Sdes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 34798679Sdes else \ 34898679Sdes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 34998679Sdes } else \ 35098679Sdes (head)->rbh_root = (tmp); \ 35198679Sdes RB_LEFT(tmp, field) = (elm); \ 35298679Sdes RB_PARENT(elm, field) = (tmp); \ 35398679Sdes RB_AUGMENT(tmp); \ 354127208Sdes if ((RB_PARENT(tmp, field))) \ 355127208Sdes RB_AUGMENT(RB_PARENT(tmp, field)); \ 356127403Sdes} while (/*CONSTCOND*/ 0) 35798679Sdes 35898679Sdes#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 35998679Sdes (tmp) = RB_LEFT(elm, field); \ 360127403Sdes if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 36198679Sdes RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 36298679Sdes } \ 36398679Sdes RB_AUGMENT(elm); \ 364127403Sdes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 36598679Sdes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 36698679Sdes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 36798679Sdes else \ 36898679Sdes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 36998679Sdes } else \ 37098679Sdes (head)->rbh_root = (tmp); \ 37198679Sdes RB_RIGHT(tmp, field) = (elm); \ 37298679Sdes RB_PARENT(elm, field) = (tmp); \ 37398679Sdes RB_AUGMENT(tmp); \ 374127208Sdes if ((RB_PARENT(tmp, field))) \ 375127208Sdes RB_AUGMENT(RB_PARENT(tmp, field)); \ 376127403Sdes} while (/*CONSTCOND*/ 0) 37798679Sdes 37898679Sdes/* Generates prototypes and inline functions */ 37998679Sdes#define RB_PROTOTYPE(name, type, field, cmp) \ 38098679Sdesvoid name##_RB_INSERT_COLOR(struct name *, struct type *); \ 38198679Sdesvoid name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 38298679Sdesstruct type *name##_RB_REMOVE(struct name *, struct type *); \ 38398679Sdesstruct type *name##_RB_INSERT(struct name *, struct type *); \ 38498679Sdesstruct type *name##_RB_FIND(struct name *, struct type *); \ 385154227Sjasonestruct type *name##_RB_NFIND(struct name *, struct type *); \ 386127563Sdesstruct type *name##_RB_NEXT(struct type *); \ 38798679Sdesstruct type *name##_RB_MINMAX(struct name *, int); \ 38898679Sdes \ 38998679Sdes 39098679Sdes/* Main rb operation. 39198679Sdes * Moves node close to the key of elm to top 39298679Sdes */ 39398679Sdes#define RB_GENERATE(name, type, field, cmp) \ 39498679Sdesvoid \ 39598679Sdesname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 39698679Sdes{ \ 39798679Sdes struct type *parent, *gparent, *tmp; \ 398127403Sdes while ((parent = RB_PARENT(elm, field)) != NULL && \ 39998679Sdes RB_COLOR(parent, field) == RB_RED) { \ 40098679Sdes gparent = RB_PARENT(parent, field); \ 40198679Sdes if (parent == RB_LEFT(gparent, field)) { \ 40298679Sdes tmp = RB_RIGHT(gparent, field); \ 40398679Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 40498679Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 40598679Sdes RB_SET_BLACKRED(parent, gparent, field);\ 40698679Sdes elm = gparent; \ 40798679Sdes continue; \ 40898679Sdes } \ 40998679Sdes if (RB_RIGHT(parent, field) == elm) { \ 41098679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 41198679Sdes tmp = parent; \ 41298679Sdes parent = elm; \ 41398679Sdes elm = tmp; \ 41498679Sdes } \ 41598679Sdes RB_SET_BLACKRED(parent, gparent, field); \ 41698679Sdes RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 41798679Sdes } else { \ 41898679Sdes tmp = RB_LEFT(gparent, field); \ 41998679Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 42098679Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 42198679Sdes RB_SET_BLACKRED(parent, gparent, field);\ 42298679Sdes elm = gparent; \ 42398679Sdes continue; \ 42498679Sdes } \ 42598679Sdes if (RB_LEFT(parent, field) == elm) { \ 42698679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 42798679Sdes tmp = parent; \ 42898679Sdes parent = elm; \ 42998679Sdes elm = tmp; \ 43098679Sdes } \ 43198679Sdes RB_SET_BLACKRED(parent, gparent, field); \ 43298679Sdes RB_ROTATE_LEFT(head, gparent, tmp, field); \ 43398679Sdes } \ 43498679Sdes } \ 43598679Sdes RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 43698679Sdes} \ 43798679Sdes \ 43898679Sdesvoid \ 43998679Sdesname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 44098679Sdes{ \ 44198679Sdes struct type *tmp; \ 44298679Sdes while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 44398679Sdes elm != RB_ROOT(head)) { \ 44498679Sdes if (RB_LEFT(parent, field) == elm) { \ 44598679Sdes tmp = RB_RIGHT(parent, field); \ 44698679Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 44798679Sdes RB_SET_BLACKRED(tmp, parent, field); \ 44898679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 44998679Sdes tmp = RB_RIGHT(parent, field); \ 45098679Sdes } \ 45198679Sdes if ((RB_LEFT(tmp, field) == NULL || \ 45298679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 45398679Sdes (RB_RIGHT(tmp, field) == NULL || \ 45498679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 45598679Sdes RB_COLOR(tmp, field) = RB_RED; \ 45698679Sdes elm = parent; \ 45798679Sdes parent = RB_PARENT(elm, field); \ 45898679Sdes } else { \ 45998679Sdes if (RB_RIGHT(tmp, field) == NULL || \ 46098679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 46198679Sdes struct type *oleft; \ 462127403Sdes if ((oleft = RB_LEFT(tmp, field)) \ 463127403Sdes != NULL) \ 46498679Sdes RB_COLOR(oleft, field) = RB_BLACK;\ 46598679Sdes RB_COLOR(tmp, field) = RB_RED; \ 46698679Sdes RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 46798679Sdes tmp = RB_RIGHT(parent, field); \ 46898679Sdes } \ 46998679Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 47098679Sdes RB_COLOR(parent, field) = RB_BLACK; \ 47198679Sdes if (RB_RIGHT(tmp, field)) \ 47298679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 47398679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 47498679Sdes elm = RB_ROOT(head); \ 47598679Sdes break; \ 47698679Sdes } \ 47798679Sdes } else { \ 47898679Sdes tmp = RB_LEFT(parent, field); \ 47998679Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 48098679Sdes RB_SET_BLACKRED(tmp, parent, field); \ 48198679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 48298679Sdes tmp = RB_LEFT(parent, field); \ 48398679Sdes } \ 48498679Sdes if ((RB_LEFT(tmp, field) == NULL || \ 48598679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 48698679Sdes (RB_RIGHT(tmp, field) == NULL || \ 48798679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 48898679Sdes RB_COLOR(tmp, field) = RB_RED; \ 48998679Sdes elm = parent; \ 49098679Sdes parent = RB_PARENT(elm, field); \ 49198679Sdes } else { \ 49298679Sdes if (RB_LEFT(tmp, field) == NULL || \ 49398679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 49498679Sdes struct type *oright; \ 495127403Sdes if ((oright = RB_RIGHT(tmp, field)) \ 496127403Sdes != NULL) \ 49798679Sdes RB_COLOR(oright, field) = RB_BLACK;\ 49898679Sdes RB_COLOR(tmp, field) = RB_RED; \ 49998679Sdes RB_ROTATE_LEFT(head, tmp, oright, field);\ 50098679Sdes tmp = RB_LEFT(parent, field); \ 50198679Sdes } \ 50298679Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 50398679Sdes RB_COLOR(parent, field) = RB_BLACK; \ 50498679Sdes if (RB_LEFT(tmp, field)) \ 50598679Sdes RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 50698679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 50798679Sdes elm = RB_ROOT(head); \ 50898679Sdes break; \ 50998679Sdes } \ 51098679Sdes } \ 51198679Sdes } \ 51298679Sdes if (elm) \ 51398679Sdes RB_COLOR(elm, field) = RB_BLACK; \ 51498679Sdes} \ 51598679Sdes \ 51698679Sdesstruct type * \ 51798679Sdesname##_RB_REMOVE(struct name *head, struct type *elm) \ 51898679Sdes{ \ 51998679Sdes struct type *child, *parent, *old = elm; \ 52098679Sdes int color; \ 52198679Sdes if (RB_LEFT(elm, field) == NULL) \ 52298679Sdes child = RB_RIGHT(elm, field); \ 52398679Sdes else if (RB_RIGHT(elm, field) == NULL) \ 52498679Sdes child = RB_LEFT(elm, field); \ 52598679Sdes else { \ 52698679Sdes struct type *left; \ 52798679Sdes elm = RB_RIGHT(elm, field); \ 528127403Sdes while ((left = RB_LEFT(elm, field)) != NULL) \ 52998679Sdes elm = left; \ 53098679Sdes child = RB_RIGHT(elm, field); \ 53198679Sdes parent = RB_PARENT(elm, field); \ 53298679Sdes color = RB_COLOR(elm, field); \ 53398679Sdes if (child) \ 53498679Sdes RB_PARENT(child, field) = parent; \ 53598679Sdes if (parent) { \ 53698679Sdes if (RB_LEFT(parent, field) == elm) \ 53798679Sdes RB_LEFT(parent, field) = child; \ 53898679Sdes else \ 53998679Sdes RB_RIGHT(parent, field) = child; \ 54098679Sdes RB_AUGMENT(parent); \ 54198679Sdes } else \ 54298679Sdes RB_ROOT(head) = child; \ 54398679Sdes if (RB_PARENT(elm, field) == old) \ 54498679Sdes parent = elm; \ 54598679Sdes (elm)->field = (old)->field; \ 54698679Sdes if (RB_PARENT(old, field)) { \ 54798679Sdes if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 54898679Sdes RB_LEFT(RB_PARENT(old, field), field) = elm;\ 54998679Sdes else \ 55098679Sdes RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 55198679Sdes RB_AUGMENT(RB_PARENT(old, field)); \ 55298679Sdes } else \ 55398679Sdes RB_ROOT(head) = elm; \ 55498679Sdes RB_PARENT(RB_LEFT(old, field), field) = elm; \ 55598679Sdes if (RB_RIGHT(old, field)) \ 55698679Sdes RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 55798679Sdes if (parent) { \ 55898679Sdes left = parent; \ 55998679Sdes do { \ 56098679Sdes RB_AUGMENT(left); \ 561127403Sdes } while ((left = RB_PARENT(left, field)) != NULL); \ 56298679Sdes } \ 56398679Sdes goto color; \ 56498679Sdes } \ 56598679Sdes parent = RB_PARENT(elm, field); \ 56698679Sdes color = RB_COLOR(elm, field); \ 56798679Sdes if (child) \ 56898679Sdes RB_PARENT(child, field) = parent; \ 56998679Sdes if (parent) { \ 57098679Sdes if (RB_LEFT(parent, field) == elm) \ 57198679Sdes RB_LEFT(parent, field) = child; \ 57298679Sdes else \ 57398679Sdes RB_RIGHT(parent, field) = child; \ 57498679Sdes RB_AUGMENT(parent); \ 57598679Sdes } else \ 57698679Sdes RB_ROOT(head) = child; \ 57798679Sdescolor: \ 57898679Sdes if (color == RB_BLACK) \ 57998679Sdes name##_RB_REMOVE_COLOR(head, parent, child); \ 58098679Sdes return (old); \ 58198679Sdes} \ 58298679Sdes \ 58398679Sdes/* Inserts a node into the RB tree */ \ 58498679Sdesstruct type * \ 58598679Sdesname##_RB_INSERT(struct name *head, struct type *elm) \ 58698679Sdes{ \ 58798679Sdes struct type *tmp; \ 58898679Sdes struct type *parent = NULL; \ 58998679Sdes int comp = 0; \ 59098679Sdes tmp = RB_ROOT(head); \ 59198679Sdes while (tmp) { \ 59298679Sdes parent = tmp; \ 59398679Sdes comp = (cmp)(elm, parent); \ 59498679Sdes if (comp < 0) \ 59598679Sdes tmp = RB_LEFT(tmp, field); \ 59698679Sdes else if (comp > 0) \ 59798679Sdes tmp = RB_RIGHT(tmp, field); \ 59898679Sdes else \ 59998679Sdes return (tmp); \ 60098679Sdes } \ 60198679Sdes RB_SET(elm, parent, field); \ 60298679Sdes if (parent != NULL) { \ 60398679Sdes if (comp < 0) \ 60498679Sdes RB_LEFT(parent, field) = elm; \ 60598679Sdes else \ 60698679Sdes RB_RIGHT(parent, field) = elm; \ 60798679Sdes RB_AUGMENT(parent); \ 60898679Sdes } else \ 60998679Sdes RB_ROOT(head) = elm; \ 61098679Sdes name##_RB_INSERT_COLOR(head, elm); \ 61198679Sdes return (NULL); \ 61298679Sdes} \ 61398679Sdes \ 61498679Sdes/* Finds the node with the same key as elm */ \ 61598679Sdesstruct type * \ 61698679Sdesname##_RB_FIND(struct name *head, struct type *elm) \ 61798679Sdes{ \ 61898679Sdes struct type *tmp = RB_ROOT(head); \ 61998679Sdes int comp; \ 62098679Sdes while (tmp) { \ 62198679Sdes comp = cmp(elm, tmp); \ 62298679Sdes if (comp < 0) \ 62398679Sdes tmp = RB_LEFT(tmp, field); \ 62498679Sdes else if (comp > 0) \ 62598679Sdes tmp = RB_RIGHT(tmp, field); \ 62698679Sdes else \ 62798679Sdes return (tmp); \ 62898679Sdes } \ 62998679Sdes return (NULL); \ 63098679Sdes} \ 63198679Sdes \ 632154227Sjasone/* Finds the first node greater than or equal to the search key */ \ 633154227Sjasonestruct type * \ 634154227Sjasonename##_RB_NFIND(struct name *head, struct type *elm) \ 635154227Sjasone{ \ 636154227Sjasone struct type *ret = RB_ROOT(head); \ 637154227Sjasone struct type *tmp; \ 638154227Sjasone int comp; \ 639154227Sjasone while (ret && (comp = cmp(elm, ret)) != 0) { \ 640154227Sjasone if (comp < 0) { \ 641154227Sjasone if ((tmp = RB_LEFT(ret, field)) == NULL) \ 642154227Sjasone break; \ 643154227Sjasone ret = tmp; \ 644154227Sjasone } else { \ 645154227Sjasone if ((tmp = RB_RIGHT(ret, field)) == NULL) { \ 646154227Sjasone tmp = ret; \ 647154227Sjasone ret = RB_PARENT(ret, field); \ 648154227Sjasone while (ret && tmp == RB_RIGHT(ret, \ 649154227Sjasone field)) { \ 650154227Sjasone tmp = ret; \ 651154227Sjasone ret = RB_PARENT(ret, field); \ 652154227Sjasone } \ 653154227Sjasone break; \ 654154227Sjasone } \ 655154227Sjasone ret = tmp; \ 656154227Sjasone } \ 657154227Sjasone } \ 658154227Sjasone return (ret); \ 659154227Sjasone} \ 660154227Sjasone \ 661127403Sdes/* ARGSUSED */ \ 66298679Sdesstruct type * \ 663127563Sdesname##_RB_NEXT(struct type *elm) \ 66498679Sdes{ \ 66598679Sdes if (RB_RIGHT(elm, field)) { \ 66698679Sdes elm = RB_RIGHT(elm, field); \ 66798679Sdes while (RB_LEFT(elm, field)) \ 66898679Sdes elm = RB_LEFT(elm, field); \ 66998679Sdes } else { \ 67098679Sdes if (RB_PARENT(elm, field) && \ 67198679Sdes (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 67298679Sdes elm = RB_PARENT(elm, field); \ 67398679Sdes else { \ 67498679Sdes while (RB_PARENT(elm, field) && \ 67598679Sdes (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 67698679Sdes elm = RB_PARENT(elm, field); \ 67798679Sdes elm = RB_PARENT(elm, field); \ 67898679Sdes } \ 67998679Sdes } \ 68098679Sdes return (elm); \ 68198679Sdes} \ 68298679Sdes \ 68398679Sdesstruct type * \ 68498679Sdesname##_RB_MINMAX(struct name *head, int val) \ 68598679Sdes{ \ 68698679Sdes struct type *tmp = RB_ROOT(head); \ 68798679Sdes struct type *parent = NULL; \ 68898679Sdes while (tmp) { \ 68998679Sdes parent = tmp; \ 69098679Sdes if (val < 0) \ 69198679Sdes tmp = RB_LEFT(tmp, field); \ 69298679Sdes else \ 69398679Sdes tmp = RB_RIGHT(tmp, field); \ 69498679Sdes } \ 69598679Sdes return (parent); \ 69698679Sdes} 69798679Sdes 69898679Sdes#define RB_NEGINF -1 69998679Sdes#define RB_INF 1 70098679Sdes 70198679Sdes#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 70298679Sdes#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 70398679Sdes#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 704154227Sjasone#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 705127563Sdes#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 70698679Sdes#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 70798679Sdes#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 70898679Sdes 70998679Sdes#define RB_FOREACH(x, name, head) \ 71098679Sdes for ((x) = RB_MIN(name, head); \ 71198679Sdes (x) != NULL; \ 712127563Sdes (x) = name##_RB_NEXT(x)) 71398679Sdes 71498679Sdes#endif /* _SYS_TREE_H_ */ 715