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