tree.h revision 186479
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 186479 2008-12-24 19:57:22Z bms $ */ 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) \ 386154548Sjasoneattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 387154548Sjasoneattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 388154548Sjasoneattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 389154548Sjasoneattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 390154548Sjasoneattr struct type *name##_RB_FIND(struct name *, struct type *); \ 391154548Sjasoneattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 392154548Sjasoneattr struct type *name##_RB_NEXT(struct type *); \ 393174955Sjasoneattr struct type *name##_RB_PREV(struct type *); \ 394154548Sjasoneattr struct type *name##_RB_MINMAX(struct name *, int); \ 39598679Sdes \ 39698679Sdes 39798679Sdes/* Main rb operation. 39898679Sdes * Moves node close to the key of elm to top 39998679Sdes */ 400154548Sjasone#define RB_GENERATE(name, type, field, cmp) \ 401154548Sjasone RB_GENERATE_INTERNAL(name, type, field, cmp,) 402154548Sjasone#define RB_GENERATE_STATIC(name, type, field, cmp) \ 403154548Sjasone RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 404154548Sjasone#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 405154548Sjasoneattr void \ 40698679Sdesname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 40798679Sdes{ \ 40898679Sdes struct type *parent, *gparent, *tmp; \ 409127403Sdes while ((parent = RB_PARENT(elm, field)) != NULL && \ 41098679Sdes RB_COLOR(parent, field) == RB_RED) { \ 41198679Sdes gparent = RB_PARENT(parent, field); \ 41298679Sdes if (parent == RB_LEFT(gparent, field)) { \ 41398679Sdes tmp = RB_RIGHT(gparent, field); \ 41498679Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 41598679Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 41698679Sdes RB_SET_BLACKRED(parent, gparent, field);\ 41798679Sdes elm = gparent; \ 41898679Sdes continue; \ 41998679Sdes } \ 42098679Sdes if (RB_RIGHT(parent, field) == elm) { \ 42198679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 42298679Sdes tmp = parent; \ 42398679Sdes parent = elm; \ 42498679Sdes elm = tmp; \ 42598679Sdes } \ 42698679Sdes RB_SET_BLACKRED(parent, gparent, field); \ 42798679Sdes RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 42898679Sdes } else { \ 42998679Sdes tmp = RB_LEFT(gparent, field); \ 43098679Sdes if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 43198679Sdes RB_COLOR(tmp, field) = RB_BLACK; \ 43298679Sdes RB_SET_BLACKRED(parent, gparent, field);\ 43398679Sdes elm = gparent; \ 43498679Sdes continue; \ 43598679Sdes } \ 43698679Sdes if (RB_LEFT(parent, field) == elm) { \ 43798679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 43898679Sdes tmp = parent; \ 43998679Sdes parent = elm; \ 44098679Sdes elm = tmp; \ 44198679Sdes } \ 44298679Sdes RB_SET_BLACKRED(parent, gparent, field); \ 44398679Sdes RB_ROTATE_LEFT(head, gparent, tmp, field); \ 44498679Sdes } \ 44598679Sdes } \ 44698679Sdes RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 44798679Sdes} \ 44898679Sdes \ 449154548Sjasoneattr void \ 45098679Sdesname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 45198679Sdes{ \ 45298679Sdes struct type *tmp; \ 45398679Sdes while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 45498679Sdes elm != RB_ROOT(head)) { \ 45598679Sdes if (RB_LEFT(parent, field) == elm) { \ 45698679Sdes tmp = RB_RIGHT(parent, field); \ 45798679Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 45898679Sdes RB_SET_BLACKRED(tmp, parent, field); \ 45998679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 46098679Sdes tmp = RB_RIGHT(parent, field); \ 46198679Sdes } \ 46298679Sdes if ((RB_LEFT(tmp, field) == NULL || \ 46398679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 46498679Sdes (RB_RIGHT(tmp, field) == NULL || \ 46598679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 46698679Sdes RB_COLOR(tmp, field) = RB_RED; \ 46798679Sdes elm = parent; \ 46898679Sdes parent = RB_PARENT(elm, field); \ 46998679Sdes } else { \ 47098679Sdes if (RB_RIGHT(tmp, field) == NULL || \ 47198679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 47298679Sdes struct type *oleft; \ 473127403Sdes if ((oleft = RB_LEFT(tmp, field)) \ 474127403Sdes != NULL) \ 47598679Sdes RB_COLOR(oleft, field) = RB_BLACK;\ 47698679Sdes RB_COLOR(tmp, field) = RB_RED; \ 47798679Sdes RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 47898679Sdes tmp = RB_RIGHT(parent, field); \ 47998679Sdes } \ 48098679Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 48198679Sdes RB_COLOR(parent, field) = RB_BLACK; \ 48298679Sdes if (RB_RIGHT(tmp, field)) \ 48398679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 48498679Sdes RB_ROTATE_LEFT(head, parent, tmp, field);\ 48598679Sdes elm = RB_ROOT(head); \ 48698679Sdes break; \ 48798679Sdes } \ 48898679Sdes } else { \ 48998679Sdes tmp = RB_LEFT(parent, field); \ 49098679Sdes if (RB_COLOR(tmp, field) == RB_RED) { \ 49198679Sdes RB_SET_BLACKRED(tmp, parent, field); \ 49298679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 49398679Sdes tmp = RB_LEFT(parent, field); \ 49498679Sdes } \ 49598679Sdes if ((RB_LEFT(tmp, field) == NULL || \ 49698679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 49798679Sdes (RB_RIGHT(tmp, field) == NULL || \ 49898679Sdes RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 49998679Sdes RB_COLOR(tmp, field) = RB_RED; \ 50098679Sdes elm = parent; \ 50198679Sdes parent = RB_PARENT(elm, field); \ 50298679Sdes } else { \ 50398679Sdes if (RB_LEFT(tmp, field) == NULL || \ 50498679Sdes RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 50598679Sdes struct type *oright; \ 506127403Sdes if ((oright = RB_RIGHT(tmp, field)) \ 507127403Sdes != NULL) \ 50898679Sdes RB_COLOR(oright, field) = RB_BLACK;\ 50998679Sdes RB_COLOR(tmp, field) = RB_RED; \ 51098679Sdes RB_ROTATE_LEFT(head, tmp, oright, field);\ 51198679Sdes tmp = RB_LEFT(parent, field); \ 51298679Sdes } \ 51398679Sdes RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 51498679Sdes RB_COLOR(parent, field) = RB_BLACK; \ 51598679Sdes if (RB_LEFT(tmp, field)) \ 51698679Sdes RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 51798679Sdes RB_ROTATE_RIGHT(head, parent, tmp, field);\ 51898679Sdes elm = RB_ROOT(head); \ 51998679Sdes break; \ 52098679Sdes } \ 52198679Sdes } \ 52298679Sdes } \ 52398679Sdes if (elm) \ 52498679Sdes RB_COLOR(elm, field) = RB_BLACK; \ 52598679Sdes} \ 52698679Sdes \ 527154548Sjasoneattr struct type * \ 52898679Sdesname##_RB_REMOVE(struct name *head, struct type *elm) \ 52998679Sdes{ \ 53098679Sdes struct type *child, *parent, *old = elm; \ 53198679Sdes int color; \ 53298679Sdes if (RB_LEFT(elm, field) == NULL) \ 53398679Sdes child = RB_RIGHT(elm, field); \ 53498679Sdes else if (RB_RIGHT(elm, field) == NULL) \ 53598679Sdes child = RB_LEFT(elm, field); \ 53698679Sdes else { \ 53798679Sdes struct type *left; \ 53898679Sdes elm = RB_RIGHT(elm, field); \ 539127403Sdes while ((left = RB_LEFT(elm, field)) != NULL) \ 54098679Sdes elm = left; \ 54198679Sdes child = RB_RIGHT(elm, field); \ 54298679Sdes parent = RB_PARENT(elm, field); \ 54398679Sdes color = RB_COLOR(elm, field); \ 54498679Sdes if (child) \ 54598679Sdes RB_PARENT(child, field) = parent; \ 54698679Sdes if (parent) { \ 54798679Sdes if (RB_LEFT(parent, field) == elm) \ 54898679Sdes RB_LEFT(parent, field) = child; \ 54998679Sdes else \ 55098679Sdes RB_RIGHT(parent, field) = child; \ 55198679Sdes RB_AUGMENT(parent); \ 55298679Sdes } else \ 55398679Sdes RB_ROOT(head) = child; \ 55498679Sdes if (RB_PARENT(elm, field) == old) \ 55598679Sdes parent = elm; \ 55698679Sdes (elm)->field = (old)->field; \ 55798679Sdes if (RB_PARENT(old, field)) { \ 55898679Sdes if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 55998679Sdes RB_LEFT(RB_PARENT(old, field), field) = elm;\ 56098679Sdes else \ 56198679Sdes RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 56298679Sdes RB_AUGMENT(RB_PARENT(old, field)); \ 56398679Sdes } else \ 56498679Sdes RB_ROOT(head) = elm; \ 56598679Sdes RB_PARENT(RB_LEFT(old, field), field) = elm; \ 56698679Sdes if (RB_RIGHT(old, field)) \ 56798679Sdes RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 56898679Sdes if (parent) { \ 56998679Sdes left = parent; \ 57098679Sdes do { \ 57198679Sdes RB_AUGMENT(left); \ 572127403Sdes } while ((left = RB_PARENT(left, field)) != NULL); \ 57398679Sdes } \ 57498679Sdes goto color; \ 57598679Sdes } \ 57698679Sdes parent = RB_PARENT(elm, field); \ 57798679Sdes color = RB_COLOR(elm, field); \ 57898679Sdes if (child) \ 57998679Sdes RB_PARENT(child, field) = parent; \ 58098679Sdes if (parent) { \ 58198679Sdes if (RB_LEFT(parent, field) == elm) \ 58298679Sdes RB_LEFT(parent, field) = child; \ 58398679Sdes else \ 58498679Sdes RB_RIGHT(parent, field) = child; \ 58598679Sdes RB_AUGMENT(parent); \ 58698679Sdes } else \ 58798679Sdes RB_ROOT(head) = child; \ 58898679Sdescolor: \ 58998679Sdes if (color == RB_BLACK) \ 59098679Sdes name##_RB_REMOVE_COLOR(head, parent, child); \ 59198679Sdes return (old); \ 59298679Sdes} \ 59398679Sdes \ 59498679Sdes/* Inserts a node into the RB tree */ \ 595154548Sjasoneattr struct type * \ 59698679Sdesname##_RB_INSERT(struct name *head, struct type *elm) \ 59798679Sdes{ \ 59898679Sdes struct type *tmp; \ 59998679Sdes struct type *parent = NULL; \ 60098679Sdes int comp = 0; \ 60198679Sdes tmp = RB_ROOT(head); \ 60298679Sdes while (tmp) { \ 60398679Sdes parent = tmp; \ 60498679Sdes comp = (cmp)(elm, parent); \ 60598679Sdes if (comp < 0) \ 60698679Sdes tmp = RB_LEFT(tmp, field); \ 60798679Sdes else if (comp > 0) \ 60898679Sdes tmp = RB_RIGHT(tmp, field); \ 60998679Sdes else \ 61098679Sdes return (tmp); \ 61198679Sdes } \ 61298679Sdes RB_SET(elm, parent, field); \ 61398679Sdes if (parent != NULL) { \ 61498679Sdes if (comp < 0) \ 61598679Sdes RB_LEFT(parent, field) = elm; \ 61698679Sdes else \ 61798679Sdes RB_RIGHT(parent, field) = elm; \ 61898679Sdes RB_AUGMENT(parent); \ 61998679Sdes } else \ 62098679Sdes RB_ROOT(head) = elm; \ 62198679Sdes name##_RB_INSERT_COLOR(head, elm); \ 62298679Sdes return (NULL); \ 62398679Sdes} \ 62498679Sdes \ 62598679Sdes/* Finds the node with the same key as elm */ \ 626154548Sjasoneattr struct type * \ 62798679Sdesname##_RB_FIND(struct name *head, struct type *elm) \ 62898679Sdes{ \ 62998679Sdes struct type *tmp = RB_ROOT(head); \ 63098679Sdes int comp; \ 63198679Sdes while (tmp) { \ 63298679Sdes comp = cmp(elm, tmp); \ 63398679Sdes if (comp < 0) \ 63498679Sdes tmp = RB_LEFT(tmp, field); \ 63598679Sdes else if (comp > 0) \ 63698679Sdes tmp = RB_RIGHT(tmp, field); \ 63798679Sdes else \ 63898679Sdes return (tmp); \ 63998679Sdes } \ 64098679Sdes return (NULL); \ 64198679Sdes} \ 64298679Sdes \ 643154227Sjasone/* Finds the first node greater than or equal to the search key */ \ 644154548Sjasoneattr struct type * \ 645154227Sjasonename##_RB_NFIND(struct name *head, struct type *elm) \ 646154227Sjasone{ \ 647170779Sjasone struct type *tmp = RB_ROOT(head); \ 648170779Sjasone struct type *res = NULL; \ 649154227Sjasone int comp; \ 650170779Sjasone while (tmp) { \ 651170779Sjasone comp = cmp(elm, tmp); \ 652154227Sjasone if (comp < 0) { \ 653170779Sjasone res = tmp; \ 654170779Sjasone tmp = RB_LEFT(tmp, field); \ 655154227Sjasone } \ 656170779Sjasone else if (comp > 0) \ 657170779Sjasone tmp = RB_RIGHT(tmp, field); \ 658170779Sjasone else \ 659170779Sjasone return (tmp); \ 660154227Sjasone } \ 661170779Sjasone return (res); \ 662154227Sjasone} \ 663154227Sjasone \ 664127403Sdes/* ARGSUSED */ \ 665154548Sjasoneattr struct type * \ 666127563Sdesname##_RB_NEXT(struct type *elm) \ 66798679Sdes{ \ 66898679Sdes if (RB_RIGHT(elm, field)) { \ 66998679Sdes elm = RB_RIGHT(elm, field); \ 67098679Sdes while (RB_LEFT(elm, field)) \ 67198679Sdes elm = RB_LEFT(elm, field); \ 67298679Sdes } else { \ 67398679Sdes if (RB_PARENT(elm, field) && \ 67498679Sdes (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 67598679Sdes elm = RB_PARENT(elm, field); \ 67698679Sdes else { \ 67798679Sdes while (RB_PARENT(elm, field) && \ 67898679Sdes (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 67998679Sdes elm = RB_PARENT(elm, field); \ 68098679Sdes elm = RB_PARENT(elm, field); \ 68198679Sdes } \ 68298679Sdes } \ 68398679Sdes return (elm); \ 68498679Sdes} \ 68598679Sdes \ 686174955Sjasone/* ARGSUSED */ \ 687154548Sjasoneattr struct type * \ 688174955Sjasonename##_RB_PREV(struct type *elm) \ 689174955Sjasone{ \ 690174955Sjasone if (RB_LEFT(elm, field)) { \ 691174955Sjasone elm = RB_LEFT(elm, field); \ 692174955Sjasone while (RB_RIGHT(elm, field)) \ 693174955Sjasone elm = RB_RIGHT(elm, field); \ 694174955Sjasone } else { \ 695174955Sjasone if (RB_PARENT(elm, field) && \ 696174955Sjasone (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 697174955Sjasone elm = RB_PARENT(elm, field); \ 698174955Sjasone else { \ 699174955Sjasone while (RB_PARENT(elm, field) && \ 700174955Sjasone (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 701174955Sjasone elm = RB_PARENT(elm, field); \ 702174955Sjasone elm = RB_PARENT(elm, field); \ 703174955Sjasone } \ 704174955Sjasone } \ 705174955Sjasone return (elm); \ 706174955Sjasone} \ 707174955Sjasone \ 708174955Sjasoneattr struct type * \ 70998679Sdesname##_RB_MINMAX(struct name *head, int val) \ 71098679Sdes{ \ 71198679Sdes struct type *tmp = RB_ROOT(head); \ 71298679Sdes struct type *parent = NULL; \ 71398679Sdes while (tmp) { \ 71498679Sdes parent = tmp; \ 71598679Sdes if (val < 0) \ 71698679Sdes tmp = RB_LEFT(tmp, field); \ 71798679Sdes else \ 71898679Sdes tmp = RB_RIGHT(tmp, field); \ 71998679Sdes } \ 72098679Sdes return (parent); \ 72198679Sdes} 72298679Sdes 72398679Sdes#define RB_NEGINF -1 72498679Sdes#define RB_INF 1 72598679Sdes 72698679Sdes#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 72798679Sdes#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 72898679Sdes#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 729154227Sjasone#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 730127563Sdes#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 731174955Sjasone#define RB_PREV(name, x, y) name##_RB_PREV(y) 73298679Sdes#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 73398679Sdes#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 73498679Sdes 73598679Sdes#define RB_FOREACH(x, name, head) \ 73698679Sdes for ((x) = RB_MIN(name, head); \ 73798679Sdes (x) != NULL; \ 738127563Sdes (x) = name##_RB_NEXT(x)) 73998679Sdes 740186479Sbms#define RB_FOREACH_SAFE(x, name, head, y) \ 741186479Sbms for ((x) = RB_MIN(name, head); \ 742186479Sbms (x) != NULL && ((y) = name##_RB_NEXT(x)); \ 743186479Sbms (x) = (y)) 744186479Sbms 745174955Sjasone#define RB_FOREACH_REVERSE(x, name, head) \ 746174955Sjasone for ((x) = RB_MAX(name, head); \ 747174955Sjasone (x) != NULL; \ 748174955Sjasone (x) = name##_RB_PREV(x)) 749174955Sjasone 75098679Sdes#endif /* _SYS_TREE_H_ */ 751