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$ */ 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 33154548Sjasone#include <sys/cdefs.h> 34154548Sjasone 3598679Sdes/* 3698679Sdes * This file defines data structures for different types of trees: 3798679Sdes * splay trees and red-black trees. 3898679Sdes * 3998679Sdes * A splay tree is a self-organizing data structure. Every operation 4098679Sdes * on the tree causes a splay to happen. The splay moves the requested 4198679Sdes * node to the root of the tree and partly rebalances it. 4298679Sdes * 4398679Sdes * This has the benefit that request locality causes faster lookups as 4498679Sdes * the requested nodes move to the top of the tree. On the other hand, 4598679Sdes * every lookup causes memory writes. 4698679Sdes * 4798679Sdes * The Balance Theorem bounds the total access time for m operations 4898679Sdes * and n inserts on an initially empty tree as O((m + n)lg n). The 4998679Sdes * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 5098679Sdes * 5198679Sdes * A red-black tree is a binary search tree with the node color as an 5298679Sdes * extra attribute. It fulfills a set of conditions: 5398679Sdes * - every search path from the root to a leaf consists of the 5498679Sdes * same number of black nodes, 5598679Sdes * - each red node (except for the root) has a black parent, 5698679Sdes * - each leaf node is black. 5798679Sdes * 5898679Sdes * Every operation on a red-black tree is bounded as O(lg n). 5998679Sdes * The maximum height of a red-black tree is 2lg (n+1). 6098679Sdes */ 6198679Sdes 6298679Sdes#define SPLAY_HEAD(name, type) \ 6398679Sdesstruct name { \ 6498679Sdes struct type *sph_root; /* root of the tree */ \ 6598679Sdes} 6698679Sdes 6798679Sdes#define SPLAY_INITIALIZER(root) \ 6898679Sdes { NULL } 6998679Sdes 7098679Sdes#define SPLAY_INIT(root) do { \ 7198679Sdes (root)->sph_root = NULL; \ 72127403Sdes} while (/*CONSTCOND*/ 0) 7398679Sdes 7498679Sdes#define SPLAY_ENTRY(type) \ 7598679Sdesstruct { \ 7698679Sdes struct type *spe_left; /* left element */ \ 7798679Sdes struct type *spe_right; /* right element */ \ 7898679Sdes} 7998679Sdes 8098679Sdes#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 8198679Sdes#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 8298679Sdes#define SPLAY_ROOT(head) (head)->sph_root 8398679Sdes#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 8498679Sdes 8598679Sdes/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 8698679Sdes#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 8798679Sdes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 8898679Sdes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 8998679Sdes (head)->sph_root = tmp; \ 90127403Sdes} while (/*CONSTCOND*/ 0) 9198679Sdes 9298679Sdes#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 9398679Sdes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 9498679Sdes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 9598679Sdes (head)->sph_root = tmp; \ 96127403Sdes} while (/*CONSTCOND*/ 0) 9798679Sdes 9898679Sdes#define SPLAY_LINKLEFT(head, tmp, field) do { \ 9998679Sdes SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 10098679Sdes tmp = (head)->sph_root; \ 10198679Sdes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 102127403Sdes} while (/*CONSTCOND*/ 0) 10398679Sdes 10498679Sdes#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 10598679Sdes SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 10698679Sdes tmp = (head)->sph_root; \ 10798679Sdes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 108127403Sdes} while (/*CONSTCOND*/ 0) 10998679Sdes 11098679Sdes#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 11198679Sdes SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 11298679Sdes SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 11398679Sdes SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 11498679Sdes SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 115127403Sdes} while (/*CONSTCOND*/ 0) 11698679Sdes 11798679Sdes/* Generates prototypes and inline functions */ 11898679Sdes 11998679Sdes#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 12098679Sdesvoid name##_SPLAY(struct name *, struct type *); \ 12198679Sdesvoid name##_SPLAY_MINMAX(struct name *, int); \ 12298679Sdesstruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 12398679Sdesstruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 12498679Sdes \ 12598679Sdes/* Finds the node with the same key as elm */ \ 12698679Sdesstatic __inline struct type * \ 12798679Sdesname##_SPLAY_FIND(struct name *head, struct type *elm) \ 12898679Sdes{ \ 12998679Sdes if (SPLAY_EMPTY(head)) \ 13098679Sdes return(NULL); \ 13198679Sdes name##_SPLAY(head, elm); \ 13298679Sdes if ((cmp)(elm, (head)->sph_root) == 0) \ 13398679Sdes return (head->sph_root); \ 13498679Sdes return (NULL); \ 13598679Sdes} \ 13698679Sdes \ 13798679Sdesstatic __inline struct type * \ 13898679Sdesname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 13998679Sdes{ \ 14098679Sdes name##_SPLAY(head, elm); \ 14198679Sdes if (SPLAY_RIGHT(elm, field) != NULL) { \ 14298679Sdes elm = SPLAY_RIGHT(elm, field); \ 14398679Sdes while (SPLAY_LEFT(elm, field) != NULL) { \ 14498679Sdes elm = SPLAY_LEFT(elm, field); \ 14598679Sdes } \ 14698679Sdes } else \ 14798679Sdes elm = NULL; \ 14898679Sdes return (elm); \ 14998679Sdes} \ 15098679Sdes \ 15198679Sdesstatic __inline struct type * \ 15298679Sdesname##_SPLAY_MIN_MAX(struct name *head, int val) \ 15398679Sdes{ \ 15498679Sdes name##_SPLAY_MINMAX(head, val); \ 15598679Sdes return (SPLAY_ROOT(head)); \ 15698679Sdes} 15798679Sdes 15898679Sdes/* Main splay operation. 15998679Sdes * Moves node close to the key of elm to top 16098679Sdes */ 16198679Sdes#define SPLAY_GENERATE(name, type, field, cmp) \ 16298679Sdesstruct type * \ 16398679Sdesname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 16498679Sdes{ \ 16598679Sdes if (SPLAY_EMPTY(head)) { \ 16698679Sdes SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 16798679Sdes } else { \ 16898679Sdes int __comp; \ 16998679Sdes name##_SPLAY(head, elm); \ 17098679Sdes __comp = (cmp)(elm, (head)->sph_root); \ 17198679Sdes if(__comp < 0) { \ 17298679Sdes SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 17398679Sdes SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 17498679Sdes SPLAY_LEFT((head)->sph_root, field) = NULL; \ 17598679Sdes } else if (__comp > 0) { \ 17698679Sdes SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 17798679Sdes SPLAY_LEFT(elm, field) = (head)->sph_root; \ 17898679Sdes SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 17998679Sdes } else \ 18098679Sdes return ((head)->sph_root); \ 18198679Sdes } \ 18298679Sdes (head)->sph_root = (elm); \ 18398679Sdes return (NULL); \ 18498679Sdes} \ 18598679Sdes \ 18698679Sdesstruct type * \ 18798679Sdesname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 18898679Sdes{ \ 18998679Sdes struct type *__tmp; \ 19098679Sdes if (SPLAY_EMPTY(head)) \ 19198679Sdes return (NULL); \ 19298679Sdes name##_SPLAY(head, elm); \ 19398679Sdes if ((cmp)(elm, (head)->sph_root) == 0) { \ 19498679Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 19598679Sdes (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 19698679Sdes } else { \ 19798679Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 19898679Sdes (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 19998679Sdes name##_SPLAY(head, elm); \ 20098679Sdes SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 20198679Sdes } \ 20298679Sdes return (elm); \ 20398679Sdes } \ 20498679Sdes return (NULL); \ 20598679Sdes} \ 20698679Sdes \ 20798679Sdesvoid \ 20898679Sdesname##_SPLAY(struct name *head, struct type *elm) \ 20998679Sdes{ \ 21098679Sdes struct type __node, *__left, *__right, *__tmp; \ 21198679Sdes int __comp; \ 21298679Sdes\ 21398679Sdes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 21498679Sdes __left = __right = &__node; \ 21598679Sdes\ 216127403Sdes while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 21798679Sdes if (__comp < 0) { \ 21898679Sdes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 21998679Sdes if (__tmp == NULL) \ 22098679Sdes break; \ 22198679Sdes if ((cmp)(elm, __tmp) < 0){ \ 22298679Sdes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 22398679Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 22498679Sdes break; \ 22598679Sdes } \ 22698679Sdes SPLAY_LINKLEFT(head, __right, field); \ 22798679Sdes } else if (__comp > 0) { \ 22898679Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 22998679Sdes if (__tmp == NULL) \ 23098679Sdes break; \ 23198679Sdes if ((cmp)(elm, __tmp) > 0){ \ 23298679Sdes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 23398679Sdes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 23498679Sdes break; \ 23598679Sdes } \ 23698679Sdes SPLAY_LINKRIGHT(head, __left, field); \ 23798679Sdes } \ 23898679Sdes } \ 23998679Sdes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 24098679Sdes} \ 24198679Sdes \ 24298679Sdes/* Splay with either the minimum or the maximum element \ 24398679Sdes * Used to find minimum or maximum element in tree. \ 24498679Sdes */ \ 24598679Sdesvoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 24698679Sdes{ \ 24798679Sdes struct type __node, *__left, *__right, *__tmp; \ 24898679Sdes\ 24998679Sdes SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 25098679Sdes __left = __right = &__node; \ 25198679Sdes\ 25298679Sdes while (1) { \ 25398679Sdes if (__comp < 0) { \ 25498679Sdes __tmp = SPLAY_LEFT((head)->sph_root, field); \ 25598679Sdes if (__tmp == NULL) \ 25698679Sdes break; \ 25798679Sdes if (__comp < 0){ \ 25898679Sdes SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 25998679Sdes if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 26098679Sdes break; \ 26198679Sdes } \ 26298679Sdes SPLAY_LINKLEFT(head, __right, field); \ 26398679Sdes } else if (__comp > 0) { \ 26498679Sdes __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 26598679Sdes if (__tmp == NULL) \ 26698679Sdes break; \ 26798679Sdes if (__comp > 0) { \ 26898679Sdes SPLAY_ROTATE_LEFT(head, __tmp, field); \ 26998679Sdes if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 27098679Sdes break; \ 27198679Sdes } \ 27298679Sdes SPLAY_LINKRIGHT(head, __left, field); \ 27398679Sdes } \ 27498679Sdes } \ 27598679Sdes SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 27698679Sdes} 27798679Sdes 27898679Sdes#define SPLAY_NEGINF -1 27998679Sdes#define SPLAY_INF 1 28098679Sdes 28198679Sdes#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 28298679Sdes#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 28398679Sdes#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 28498679Sdes#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 28598679Sdes#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 28698679Sdes : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 28798679Sdes#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 28898679Sdes : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 28998679Sdes 29098679Sdes#define SPLAY_FOREACH(x, name, head) \ 29198679Sdes for ((x) = SPLAY_MIN(name, head); \ 29298679Sdes (x) != NULL; \ 29398679Sdes (x) = SPLAY_NEXT(name, head, x)) 29498679Sdes 295127403Sdes/* Macros that define a red-black tree */ 29698679Sdes#define RB_HEAD(name, type) \ 29798679Sdesstruct name { \ 29898679Sdes struct type *rbh_root; /* root of the tree */ \ 29998679Sdes} 30098679Sdes 30198679Sdes#define RB_INITIALIZER(root) \ 30298679Sdes { NULL } 30398679Sdes 30498679Sdes#define RB_INIT(root) do { \ 30598679Sdes (root)->rbh_root = NULL; \ 306127403Sdes} while (/*CONSTCOND*/ 0) 30798679Sdes 30898679Sdes#define RB_BLACK 0 30998679Sdes#define RB_RED 1 31098679Sdes#define RB_ENTRY(type) \ 31198679Sdesstruct { \ 31298679Sdes struct type *rbe_left; /* left element */ \ 31398679Sdes struct type *rbe_right; /* right element */ \ 31498679Sdes struct type *rbe_parent; /* parent element */ \ 31598679Sdes int rbe_color; /* node color */ \ 31698679Sdes} 31798679Sdes 31898679Sdes#define RB_LEFT(elm, field) (elm)->field.rbe_left 31998679Sdes#define RB_RIGHT(elm, field) (elm)->field.rbe_right 32098679Sdes#define RB_PARENT(elm, field) (elm)->field.rbe_parent 32198679Sdes#define RB_COLOR(elm, field) (elm)->field.rbe_color 32298679Sdes#define RB_ROOT(head) (head)->rbh_root 32398679Sdes#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 32498679Sdes 32598679Sdes#define RB_SET(elm, parent, field) do { \ 32698679Sdes RB_PARENT(elm, field) = parent; \ 32798679Sdes RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 32898679Sdes RB_COLOR(elm, field) = RB_RED; \ 329127403Sdes} while (/*CONSTCOND*/ 0) 33098679Sdes 33198679Sdes#define RB_SET_BLACKRED(black, red, field) do { \ 33298679Sdes RB_COLOR(black, field) = RB_BLACK; \ 33398679Sdes RB_COLOR(red, field) = RB_RED; \ 334127403Sdes} while (/*CONSTCOND*/ 0) 33598679Sdes 33698679Sdes#ifndef RB_AUGMENT 337147245Sharti#define RB_AUGMENT(x) do {} while (0) 33898679Sdes#endif 33998679Sdes 34098679Sdes#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 34198679Sdes (tmp) = RB_RIGHT(elm, field); \ 342127403Sdes if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 34398679Sdes RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 34498679Sdes } \ 34598679Sdes RB_AUGMENT(elm); \ 346127403Sdes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 34798679Sdes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 34898679Sdes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 34998679Sdes else \ 35098679Sdes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 35198679Sdes } else \ 35298679Sdes (head)->rbh_root = (tmp); \ 35398679Sdes RB_LEFT(tmp, field) = (elm); \ 35498679Sdes RB_PARENT(elm, field) = (tmp); \ 35598679Sdes RB_AUGMENT(tmp); \ 356127208Sdes if ((RB_PARENT(tmp, field))) \ 357127208Sdes RB_AUGMENT(RB_PARENT(tmp, field)); \ 358127403Sdes} while (/*CONSTCOND*/ 0) 35998679Sdes 36098679Sdes#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 36198679Sdes (tmp) = RB_LEFT(elm, field); \ 362127403Sdes if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 36398679Sdes RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 36498679Sdes } \ 36598679Sdes RB_AUGMENT(elm); \ 366127403Sdes if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 36798679Sdes if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 36898679Sdes RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 36998679Sdes else \ 37098679Sdes RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 37198679Sdes } else \ 37298679Sdes (head)->rbh_root = (tmp); \ 37398679Sdes RB_RIGHT(tmp, field) = (elm); \ 37498679Sdes RB_PARENT(elm, field) = (tmp); \ 37598679Sdes RB_AUGMENT(tmp); \ 376127208Sdes if ((RB_PARENT(tmp, field))) \ 377127208Sdes RB_AUGMENT(RB_PARENT(tmp, field)); \ 378127403Sdes} while (/*CONSTCOND*/ 0) 37998679Sdes 38098679Sdes/* Generates prototypes and inline functions */ 381154548Sjasone#define RB_PROTOTYPE(name, type, field, cmp) \ 382154548Sjasone RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 383154548Sjasone#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 384154548Sjasone RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 385154548Sjasone#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 386277642Skib RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 387277642Skib RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 388277642Skib RB_PROTOTYPE_INSERT(name, type, attr); \ 389277642Skib RB_PROTOTYPE_REMOVE(name, type, attr); \ 390277642Skib RB_PROTOTYPE_FIND(name, type, attr); \ 391277642Skib RB_PROTOTYPE_NFIND(name, type, attr); \ 392277642Skib RB_PROTOTYPE_NEXT(name, type, attr); \ 393277642Skib RB_PROTOTYPE_PREV(name, type, attr); \ 394277642Skib RB_PROTOTYPE_MINMAX(name, type, attr); 395277642Skib#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 396277642Skib attr void name##_RB_INSERT_COLOR(struct name *, struct type *) 397277642Skib#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 398277642Skib attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *) 399277642Skib#define RB_PROTOTYPE_REMOVE(name, type, attr) \ 400277642Skib attr struct type *name##_RB_REMOVE(struct name *, struct type *) 401277642Skib#define RB_PROTOTYPE_INSERT(name, type, attr) \ 402277642Skib attr struct type *name##_RB_INSERT(struct name *, struct type *) 403277642Skib#define RB_PROTOTYPE_FIND(name, type, attr) \ 404277642Skib attr struct type *name##_RB_FIND(struct name *, struct type *) 405277642Skib#define RB_PROTOTYPE_NFIND(name, type, attr) \ 406277642Skib attr struct type *name##_RB_NFIND(struct name *, struct type *) 407277642Skib#define RB_PROTOTYPE_NEXT(name, type, attr) \ 408277642Skib attr struct type *name##_RB_NEXT(struct type *) 409277642Skib#define RB_PROTOTYPE_PREV(name, type, attr) \ 410277642Skib attr struct type *name##_RB_PREV(struct type *) 411277642Skib#define RB_PROTOTYPE_MINMAX(name, type, attr) \ 412277642Skib attr struct type *name##_RB_MINMAX(struct name *, int) 41398679Sdes 41498679Sdes/* Main rb operation. 41598679Sdes * Moves node close to the key of elm to top 41698679Sdes */ 417154548Sjasone#define RB_GENERATE(name, type, field, cmp) \ 418154548Sjasone RB_GENERATE_INTERNAL(name, type, field, cmp,) 419154548Sjasone#define RB_GENERATE_STATIC(name, type, field, cmp) \ 420154548Sjasone RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 421154548Sjasone#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 422277642Skib RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 423277642Skib RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 424277642Skib RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 425277642Skib RB_GENERATE_REMOVE(name, type, field, attr) \ 426277642Skib RB_GENERATE_FIND(name, type, field, cmp, attr) \ 427277642Skib RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 428277642Skib RB_GENERATE_NEXT(name, type, field, attr) \ 429277642Skib RB_GENERATE_PREV(name, type, field, attr) \ 430277642Skib RB_GENERATE_MINMAX(name, type, field, attr) 431277642Skib 432277642Skib#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 433154548Sjasoneattr void \ 43498679Sdesname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 43598679Sdes{ \ 43698679Sdes struct type *parent, *gparent, *tmp; \ 437127403Sdes while ((parent = RB_PARENT(elm, field)) != NULL && \ 43898679Sdes RB_COLOR(parent, field) == RB_RED) { \ 43998679Sdes gparent = RB_PARENT(parent, field); \ 44098679Sdes if (parent == RB_LEFT(gparent, field)) { \ 44198679Sdes tmp = RB_RIGHT(gparent, field); \ 44298679Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 44398679Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 44498679Sdes RB_SET_BLACKRED(parent, gparent, field);\ 44598679Sdes elm = gparent; \ 44698679Sdes continue; \ 44798679Sdes } \ 44898679Sdes if (RB_RIGHT(parent, field) == elm) { \ 44998679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 45098679Sdes tmp = parent; \ 45198679Sdes parent = elm; \ 45298679Sdes elm = tmp; \ 45398679Sdes } \ 45498679Sdes RB_SET_BLACKRED(parent, gparent, field); \ 45598679Sdes RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 45698679Sdes } else { \ 45798679Sdes tmp = RB_LEFT(gparent, field); \ 45898679Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 45998679Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 46098679Sdes RB_SET_BLACKRED(parent, gparent, field);\ 46198679Sdes elm = gparent; \ 46298679Sdes continue; \ 46398679Sdes } \ 46498679Sdes if (RB_LEFT(parent, field) == elm) { \ 46598679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 46698679Sdes tmp = parent; \ 46798679Sdes parent = elm; \ 46898679Sdes elm = tmp; \ 46998679Sdes } \ 47098679Sdes RB_SET_BLACKRED(parent, gparent, field); \ 47198679Sdes RB_ROTATE_LEFT(head, gparent, tmp, field); \ 47298679Sdes } \ 47398679Sdes } \ 47498679Sdes RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 475277642Skib} 476277642Skib 477277642Skib#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 478154548Sjasoneattr void \ 47998679Sdesname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 48098679Sdes{ \ 48198679Sdes struct type *tmp; \ 48298679Sdes while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 48398679Sdes elm != RB_ROOT(head)) { \ 48498679Sdes if (RB_LEFT(parent, field) == elm) { \ 48598679Sdes tmp = RB_RIGHT(parent, field); \ 48698679Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 48798679Sdes RB_SET_BLACKRED(tmp, parent, field); \ 48898679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 48998679Sdes tmp = RB_RIGHT(parent, field); \ 49098679Sdes } \ 49198679Sdes if ((RB_LEFT(tmp, field) == NULL || \ 49298679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 49398679Sdes (RB_RIGHT(tmp, field) == NULL || \ 49498679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 49598679Sdes RB_COLOR(tmp, field) = RB_RED; \ 49698679Sdes elm = parent; \ 49798679Sdes parent = RB_PARENT(elm, field); \ 49898679Sdes } else { \ 49998679Sdes if (RB_RIGHT(tmp, field) == NULL || \ 50098679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 50198679Sdes struct type *oleft; \ 502127403Sdes if ((oleft = RB_LEFT(tmp, field)) \ 503127403Sdes != NULL) \ 50498679Sdes RB_COLOR(oleft, field) = RB_BLACK;\ 50598679Sdes RB_COLOR(tmp, field) = RB_RED; \ 50698679Sdes RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 50798679Sdes tmp = RB_RIGHT(parent, field); \ 50898679Sdes } \ 50998679Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 51098679Sdes RB_COLOR(parent, field) = RB_BLACK; \ 51198679Sdes if (RB_RIGHT(tmp, field)) \ 51298679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 51398679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 51498679Sdes elm = RB_ROOT(head); \ 51598679Sdes break; \ 51698679Sdes } \ 51798679Sdes } else { \ 51898679Sdes tmp = RB_LEFT(parent, field); \ 51998679Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 52098679Sdes RB_SET_BLACKRED(tmp, parent, field); \ 52198679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 52298679Sdes tmp = RB_LEFT(parent, field); \ 52398679Sdes } \ 52498679Sdes if ((RB_LEFT(tmp, field) == NULL || \ 52598679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 52698679Sdes (RB_RIGHT(tmp, field) == NULL || \ 52798679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 52898679Sdes RB_COLOR(tmp, field) = RB_RED; \ 52998679Sdes elm = parent; \ 53098679Sdes parent = RB_PARENT(elm, field); \ 53198679Sdes } else { \ 53298679Sdes if (RB_LEFT(tmp, field) == NULL || \ 53398679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 53498679Sdes struct type *oright; \ 535127403Sdes if ((oright = RB_RIGHT(tmp, field)) \ 536127403Sdes != NULL) \ 53798679Sdes RB_COLOR(oright, field) = RB_BLACK;\ 53898679Sdes RB_COLOR(tmp, field) = RB_RED; \ 53998679Sdes RB_ROTATE_LEFT(head, tmp, oright, field);\ 54098679Sdes tmp = RB_LEFT(parent, field); \ 54198679Sdes } \ 54298679Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 54398679Sdes RB_COLOR(parent, field) = RB_BLACK; \ 54498679Sdes if (RB_LEFT(tmp, field)) \ 54598679Sdes RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 54698679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 54798679Sdes elm = RB_ROOT(head); \ 54898679Sdes break; \ 54998679Sdes } \ 55098679Sdes } \ 55198679Sdes } \ 55298679Sdes if (elm) \ 55398679Sdes RB_COLOR(elm, field) = RB_BLACK; \ 554277642Skib} 555277642Skib 556277642Skib#define RB_GENERATE_REMOVE(name, type, field, attr) \ 557154548Sjasoneattr struct type * \ 55898679Sdesname##_RB_REMOVE(struct name *head, struct type *elm) \ 55998679Sdes{ \ 56098679Sdes struct type *child, *parent, *old = elm; \ 56198679Sdes int color; \ 56298679Sdes if (RB_LEFT(elm, field) == NULL) \ 56398679Sdes child = RB_RIGHT(elm, field); \ 56498679Sdes else if (RB_RIGHT(elm, field) == NULL) \ 56598679Sdes child = RB_LEFT(elm, field); \ 56698679Sdes else { \ 56798679Sdes struct type *left; \ 56898679Sdes elm = RB_RIGHT(elm, field); \ 569127403Sdes while ((left = RB_LEFT(elm, field)) != NULL) \ 57098679Sdes elm = left; \ 57198679Sdes child = RB_RIGHT(elm, field); \ 57298679Sdes parent = RB_PARENT(elm, field); \ 57398679Sdes color = RB_COLOR(elm, field); \ 57498679Sdes if (child) \ 57598679Sdes RB_PARENT(child, field) = parent; \ 57698679Sdes if (parent) { \ 57798679Sdes if (RB_LEFT(parent, field) == elm) \ 57898679Sdes RB_LEFT(parent, field) = child; \ 57998679Sdes else \ 58098679Sdes RB_RIGHT(parent, field) = child; \ 58198679Sdes RB_AUGMENT(parent); \ 58298679Sdes } else \ 58398679Sdes RB_ROOT(head) = child; \ 58498679Sdes if (RB_PARENT(elm, field) == old) \ 58598679Sdes parent = elm; \ 58698679Sdes (elm)->field = (old)->field; \ 58798679Sdes if (RB_PARENT(old, field)) { \ 58898679Sdes if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 58998679Sdes RB_LEFT(RB_PARENT(old, field), field) = elm;\ 59098679Sdes else \ 59198679Sdes RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 59298679Sdes RB_AUGMENT(RB_PARENT(old, field)); \ 59398679Sdes } else \ 59498679Sdes RB_ROOT(head) = elm; \ 59598679Sdes RB_PARENT(RB_LEFT(old, field), field) = elm; \ 59698679Sdes if (RB_RIGHT(old, field)) \ 59798679Sdes RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 59898679Sdes if (parent) { \ 59998679Sdes left = parent; \ 60098679Sdes do { \ 60198679Sdes RB_AUGMENT(left); \ 602127403Sdes } while ((left = RB_PARENT(left, field)) != NULL); \ 60398679Sdes } \ 60498679Sdes goto color; \ 60598679Sdes } \ 60698679Sdes parent = RB_PARENT(elm, field); \ 60798679Sdes color = RB_COLOR(elm, field); \ 60898679Sdes if (child) \ 60998679Sdes RB_PARENT(child, field) = parent; \ 61098679Sdes if (parent) { \ 61198679Sdes if (RB_LEFT(parent, field) == elm) \ 61298679Sdes RB_LEFT(parent, field) = child; \ 61398679Sdes else \ 61498679Sdes RB_RIGHT(parent, field) = child; \ 61598679Sdes RB_AUGMENT(parent); \ 61698679Sdes } else \ 61798679Sdes RB_ROOT(head) = child; \ 61898679Sdescolor: \ 61998679Sdes if (color == RB_BLACK) \ 62098679Sdes name##_RB_REMOVE_COLOR(head, parent, child); \ 62198679Sdes return (old); \ 62298679Sdes} \ 623277642Skib 624277642Skib#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 62598679Sdes/* Inserts a node into the RB tree */ \ 626154548Sjasoneattr struct type * \ 62798679Sdesname##_RB_INSERT(struct name *head, struct type *elm) \ 62898679Sdes{ \ 62998679Sdes struct type *tmp; \ 63098679Sdes struct type *parent = NULL; \ 63198679Sdes int comp = 0; \ 63298679Sdes tmp = RB_ROOT(head); \ 63398679Sdes while (tmp) { \ 63498679Sdes parent = tmp; \ 63598679Sdes comp = (cmp)(elm, parent); \ 63698679Sdes if (comp < 0) \ 63798679Sdes tmp = RB_LEFT(tmp, field); \ 63898679Sdes else if (comp > 0) \ 63998679Sdes tmp = RB_RIGHT(tmp, field); \ 64098679Sdes else \ 64198679Sdes return (tmp); \ 64298679Sdes } \ 64398679Sdes RB_SET(elm, parent, field); \ 64498679Sdes if (parent != NULL) { \ 64598679Sdes if (comp < 0) \ 64698679Sdes RB_LEFT(parent, field) = elm; \ 64798679Sdes else \ 64898679Sdes RB_RIGHT(parent, field) = elm; \ 64998679Sdes RB_AUGMENT(parent); \ 65098679Sdes } else \ 65198679Sdes RB_ROOT(head) = elm; \ 65298679Sdes name##_RB_INSERT_COLOR(head, elm); \ 65398679Sdes return (NULL); \ 654277642Skib} 655277642Skib 656277642Skib#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 65798679Sdes/* Finds the node with the same key as elm */ \ 658154548Sjasoneattr struct type * \ 65998679Sdesname##_RB_FIND(struct name *head, struct type *elm) \ 66098679Sdes{ \ 66198679Sdes struct type *tmp = RB_ROOT(head); \ 66298679Sdes int comp; \ 66398679Sdes while (tmp) { \ 66498679Sdes comp = cmp(elm, tmp); \ 66598679Sdes if (comp < 0) \ 66698679Sdes tmp = RB_LEFT(tmp, field); \ 66798679Sdes else if (comp > 0) \ 66898679Sdes tmp = RB_RIGHT(tmp, field); \ 66998679Sdes else \ 67098679Sdes return (tmp); \ 67198679Sdes } \ 67298679Sdes return (NULL); \ 673277642Skib} 674277642Skib 675277642Skib#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 676154227Sjasone/* Finds the first node greater than or equal to the search key */ \ 677154548Sjasoneattr struct type * \ 678154227Sjasonename##_RB_NFIND(struct name *head, struct type *elm) \ 679154227Sjasone{ \ 680170779Sjasone struct type *tmp = RB_ROOT(head); \ 681170779Sjasone struct type *res = NULL; \ 682154227Sjasone int comp; \ 683170779Sjasone while (tmp) { \ 684170779Sjasone comp = cmp(elm, tmp); \ 685154227Sjasone if (comp < 0) { \ 686170779Sjasone res = tmp; \ 687170779Sjasone tmp = RB_LEFT(tmp, field); \ 688154227Sjasone } \ 689170779Sjasone else if (comp > 0) \ 690170779Sjasone tmp = RB_RIGHT(tmp, field); \ 691170779Sjasone else \ 692170779Sjasone return (tmp); \ 693154227Sjasone } \ 694170779Sjasone return (res); \ 695277642Skib} 696277642Skib 697277642Skib#define RB_GENERATE_NEXT(name, type, field, attr) \ 698127403Sdes/* ARGSUSED */ \ 699154548Sjasoneattr struct type * \ 700127563Sdesname##_RB_NEXT(struct type *elm) \ 70198679Sdes{ \ 70298679Sdes if (RB_RIGHT(elm, field)) { \ 70398679Sdes elm = RB_RIGHT(elm, field); \ 70498679Sdes while (RB_LEFT(elm, field)) \ 70598679Sdes elm = RB_LEFT(elm, field); \ 70698679Sdes } else { \ 70798679Sdes if (RB_PARENT(elm, field) && \ 70898679Sdes (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 70998679Sdes elm = RB_PARENT(elm, field); \ 71098679Sdes else { \ 71198679Sdes while (RB_PARENT(elm, field) && \ 71298679Sdes (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 71398679Sdes elm = RB_PARENT(elm, field); \ 71498679Sdes elm = RB_PARENT(elm, field); \ 71598679Sdes } \ 71698679Sdes } \ 71798679Sdes return (elm); \ 718277642Skib} 719277642Skib 720277642Skib#define RB_GENERATE_PREV(name, type, field, attr) \ 721174955Sjasone/* ARGSUSED */ \ 722154548Sjasoneattr struct type * \ 723174955Sjasonename##_RB_PREV(struct type *elm) \ 724174955Sjasone{ \ 725174955Sjasone if (RB_LEFT(elm, field)) { \ 726174955Sjasone elm = RB_LEFT(elm, field); \ 727174955Sjasone while (RB_RIGHT(elm, field)) \ 728174955Sjasone elm = RB_RIGHT(elm, field); \ 729174955Sjasone } else { \ 730174955Sjasone if (RB_PARENT(elm, field) && \ 731174955Sjasone (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 732174955Sjasone elm = RB_PARENT(elm, field); \ 733174955Sjasone else { \ 734174955Sjasone while (RB_PARENT(elm, field) && \ 735174955Sjasone (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 736174955Sjasone elm = RB_PARENT(elm, field); \ 737174955Sjasone elm = RB_PARENT(elm, field); \ 738174955Sjasone } \ 739174955Sjasone } \ 740174955Sjasone return (elm); \ 741277642Skib} 742277642Skib 743277642Skib#define RB_GENERATE_MINMAX(name, type, field, attr) \ 744174955Sjasoneattr struct type * \ 74598679Sdesname##_RB_MINMAX(struct name *head, int val) \ 74698679Sdes{ \ 74798679Sdes struct type *tmp = RB_ROOT(head); \ 74898679Sdes struct type *parent = NULL; \ 74998679Sdes while (tmp) { \ 75098679Sdes parent = tmp; \ 75198679Sdes if (val < 0) \ 75298679Sdes tmp = RB_LEFT(tmp, field); \ 75398679Sdes else \ 75498679Sdes tmp = RB_RIGHT(tmp, field); \ 75598679Sdes } \ 75698679Sdes return (parent); \ 75798679Sdes} 75898679Sdes 75998679Sdes#define RB_NEGINF -1 76098679Sdes#define RB_INF 1 76198679Sdes 76298679Sdes#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 76398679Sdes#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 76498679Sdes#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 765154227Sjasone#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 766127563Sdes#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 767174955Sjasone#define RB_PREV(name, x, y) name##_RB_PREV(y) 76898679Sdes#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 76998679Sdes#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 77098679Sdes 77198679Sdes#define RB_FOREACH(x, name, head) \ 77298679Sdes for ((x) = RB_MIN(name, head); \ 77398679Sdes (x) != NULL; \ 774127563Sdes (x) = name##_RB_NEXT(x)) 77598679Sdes 776189204Sbms#define RB_FOREACH_FROM(x, name, y) \ 777189204Sbms for ((x) = (y); \ 778189204Sbms ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 779189204Sbms (x) = (y)) 780189204Sbms 781186479Sbms#define RB_FOREACH_SAFE(x, name, head, y) \ 782186479Sbms for ((x) = RB_MIN(name, head); \ 783189204Sbms ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 784186479Sbms (x) = (y)) 785186479Sbms 786174955Sjasone#define RB_FOREACH_REVERSE(x, name, head) \ 787174955Sjasone for ((x) = RB_MAX(name, head); \ 788174955Sjasone (x) != NULL; \ 789174955Sjasone (x) = name##_RB_PREV(x)) 790174955Sjasone 791189204Sbms#define RB_FOREACH_REVERSE_FROM(x, name, y) \ 792189204Sbms for ((x) = (y); \ 793189204Sbms ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 794189204Sbms (x) = (y)) 795189204Sbms 796189204Sbms#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 797189204Sbms for ((x) = RB_MAX(name, head); \ 798189204Sbms ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 799189204Sbms (x) = (y)) 800189204Sbms 80198679Sdes#endif /* _SYS_TREE_H_ */ 802