Changeset View
Changeset View
Standalone View
Standalone View
swh/loader/cvs/rcsparse/tree.h
- This file was added.
/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ | |||||
/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ | |||||
/* $DragonFly: src/sys/sys/tree.h,v 1.2 2005/04/15 19:08:13 dillon Exp $ */ | |||||
/* | |||||
* Copyright 2002 Niels Provos <provos@citi.umich.edu> | |||||
* All rights reserved. | |||||
* | |||||
* Redistribution and use in source and binary forms, with or without | |||||
* modification, are permitted provided that the following conditions | |||||
* are met: | |||||
* 1. Redistributions of source code must retain the above copyright | |||||
* notice, this list of conditions and the following disclaimer. | |||||
* 2. Redistributions in binary form must reproduce the above copyright | |||||
* notice, this list of conditions and the following disclaimer in the | |||||
* documentation and/or other materials provided with the distribution. | |||||
* | |||||
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | |||||
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | |||||
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | |||||
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | |||||
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |||||
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |||||
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |||||
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |||||
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | |||||
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |||||
*/ | |||||
#ifndef _SYS_TREE_H_ | |||||
#define _SYS_TREE_H_ | |||||
/* | |||||
* This file defines data structures for different types of trees: | |||||
* splay trees and red-black trees. | |||||
* | |||||
* A splay tree is a self-organizing data structure. Every operation | |||||
* on the tree causes a splay to happen. The splay moves the requested | |||||
* node to the root of the tree and partly rebalances it. | |||||
* | |||||
* This has the benefit that request locality causes faster lookups as | |||||
* the requested nodes move to the top of the tree. On the other hand, | |||||
* every lookup causes memory writes. | |||||
* | |||||
* The Balance Theorem bounds the total access time for m operations | |||||
* and n inserts on an initially empty tree as O((m + n)lg n). The | |||||
* amortized cost for a sequence of m accesses to a splay tree is O(lg n); | |||||
* | |||||
* A red-black tree is a binary search tree with the node color as an | |||||
* extra attribute. It fulfills a set of conditions: | |||||
* - every search path from the root to a leaf consists of the | |||||
* same number of black nodes, | |||||
* - each red node (except for the root) has a black parent, | |||||
* - each leaf node is black. | |||||
* | |||||
* Every operation on a red-black tree is bounded as O(lg n). | |||||
* The maximum height of a red-black tree is 2lg (n+1). | |||||
*/ | |||||
#define SPLAY_HEAD(name, type) \ | |||||
struct name { \ | |||||
struct type *sph_root; /* root of the tree */ \ | |||||
} | |||||
#define SPLAY_INITIALIZER(root) \ | |||||
{ NULL } | |||||
#define SPLAY_INIT(root) do { \ | |||||
(root)->sph_root = NULL; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define SPLAY_ENTRY(type) \ | |||||
struct { \ | |||||
struct type *spe_left; /* left element */ \ | |||||
struct type *spe_right; /* right element */ \ | |||||
} | |||||
#define SPLAY_LEFT(elm, field) (elm)->field.spe_left | |||||
#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right | |||||
#define SPLAY_ROOT(head) (head)->sph_root | |||||
#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) | |||||
/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ | |||||
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ | |||||
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ | |||||
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | |||||
(head)->sph_root = tmp; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ | |||||
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ | |||||
SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | |||||
(head)->sph_root = tmp; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define SPLAY_LINKLEFT(head, tmp, field) do { \ | |||||
SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | |||||
tmp = (head)->sph_root; \ | |||||
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define SPLAY_LINKRIGHT(head, tmp, field) do { \ | |||||
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | |||||
tmp = (head)->sph_root; \ | |||||
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ | |||||
SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ | |||||
SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ | |||||
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ | |||||
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
/* Generates prototypes and inline functions */ | |||||
#define SPLAY_PROTOTYPE(name, type, field, cmp) \ | |||||
void name##_SPLAY(struct name *, struct type *); \ | |||||
void name##_SPLAY_MINMAX(struct name *, int); \ | |||||
struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ | |||||
struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ | |||||
\ | |||||
/* Finds the node with the same key as elm */ \ | |||||
static __inline struct type * \ | |||||
name##_SPLAY_FIND(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
if (SPLAY_EMPTY(head)) \ | |||||
return(NULL); \ | |||||
name##_SPLAY(head, elm); \ | |||||
if ((cmp)(elm, (head)->sph_root) == 0) \ | |||||
return (head->sph_root); \ | |||||
return (NULL); \ | |||||
} \ | |||||
\ | |||||
static __inline struct type * \ | |||||
name##_SPLAY_NEXT(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
name##_SPLAY(head, elm); \ | |||||
if (SPLAY_RIGHT(elm, field) != NULL) { \ | |||||
elm = SPLAY_RIGHT(elm, field); \ | |||||
while (SPLAY_LEFT(elm, field) != NULL) { \ | |||||
elm = SPLAY_LEFT(elm, field); \ | |||||
} \ | |||||
} else \ | |||||
elm = NULL; \ | |||||
return (elm); \ | |||||
} \ | |||||
\ | |||||
static __inline struct type * \ | |||||
name##_SPLAY_MIN_MAX(struct name *head, int val) \ | |||||
{ \ | |||||
name##_SPLAY_MINMAX(head, val); \ | |||||
return (SPLAY_ROOT(head)); \ | |||||
} | |||||
/* Main splay operation. | |||||
* Moves node close to the key of elm to top | |||||
*/ | |||||
#define SPLAY_GENERATE(name, type, field, cmp) \ | |||||
struct type * \ | |||||
name##_SPLAY_INSERT(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
if (SPLAY_EMPTY(head)) { \ | |||||
SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ | |||||
} else { \ | |||||
int __comp; \ | |||||
name##_SPLAY(head, elm); \ | |||||
__comp = (cmp)(elm, (head)->sph_root); \ | |||||
if(__comp < 0) { \ | |||||
SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ | |||||
SPLAY_RIGHT(elm, field) = (head)->sph_root; \ | |||||
SPLAY_LEFT((head)->sph_root, field) = NULL; \ | |||||
} else if (__comp > 0) { \ | |||||
SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ | |||||
SPLAY_LEFT(elm, field) = (head)->sph_root; \ | |||||
SPLAY_RIGHT((head)->sph_root, field) = NULL; \ | |||||
} else \ | |||||
return ((head)->sph_root); \ | |||||
} \ | |||||
(head)->sph_root = (elm); \ | |||||
return (NULL); \ | |||||
} \ | |||||
\ | |||||
struct type * \ | |||||
name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
struct type *__tmp; \ | |||||
if (SPLAY_EMPTY(head)) \ | |||||
return (NULL); \ | |||||
name##_SPLAY(head, elm); \ | |||||
if ((cmp)(elm, (head)->sph_root) == 0) { \ | |||||
if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ | |||||
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ | |||||
} else { \ | |||||
__tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |||||
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ | |||||
name##_SPLAY(head, elm); \ | |||||
SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ | |||||
} \ | |||||
return (elm); \ | |||||
} \ | |||||
return (NULL); \ | |||||
} \ | |||||
\ | |||||
void \ | |||||
name##_SPLAY(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
struct type __node, *__left, *__right, *__tmp; \ | |||||
int __comp; \ | |||||
\ | |||||
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | |||||
__left = __right = &__node; \ | |||||
\ | |||||
while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ | |||||
if (__comp < 0) { \ | |||||
__tmp = SPLAY_LEFT((head)->sph_root, field); \ | |||||
if (__tmp == NULL) \ | |||||
break; \ | |||||
if ((cmp)(elm, __tmp) < 0){ \ | |||||
SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | |||||
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | |||||
break; \ | |||||
} \ | |||||
SPLAY_LINKLEFT(head, __right, field); \ | |||||
} else if (__comp > 0) { \ | |||||
__tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |||||
if (__tmp == NULL) \ | |||||
break; \ | |||||
if ((cmp)(elm, __tmp) > 0){ \ | |||||
SPLAY_ROTATE_LEFT(head, __tmp, field); \ | |||||
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | |||||
break; \ | |||||
} \ | |||||
SPLAY_LINKRIGHT(head, __left, field); \ | |||||
} \ | |||||
} \ | |||||
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | |||||
} \ | |||||
\ | |||||
/* Splay with either the minimum or the maximum element \ | |||||
* Used to find minimum or maximum element in tree. \ | |||||
*/ \ | |||||
void name##_SPLAY_MINMAX(struct name *head, int __comp) \ | |||||
{ \ | |||||
struct type __node, *__left, *__right, *__tmp; \ | |||||
\ | |||||
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | |||||
__left = __right = &__node; \ | |||||
\ | |||||
while (1) { \ | |||||
if (__comp < 0) { \ | |||||
__tmp = SPLAY_LEFT((head)->sph_root, field); \ | |||||
if (__tmp == NULL) \ | |||||
break; \ | |||||
if (__comp < 0){ \ | |||||
SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | |||||
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | |||||
break; \ | |||||
} \ | |||||
SPLAY_LINKLEFT(head, __right, field); \ | |||||
} else if (__comp > 0) { \ | |||||
__tmp = SPLAY_RIGHT((head)->sph_root, field); \ | |||||
if (__tmp == NULL) \ | |||||
break; \ | |||||
if (__comp > 0) { \ | |||||
SPLAY_ROTATE_LEFT(head, __tmp, field); \ | |||||
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | |||||
break; \ | |||||
} \ | |||||
SPLAY_LINKRIGHT(head, __left, field); \ | |||||
} \ | |||||
} \ | |||||
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | |||||
} | |||||
#define SPLAY_NEGINF -1 | |||||
#define SPLAY_INF 1 | |||||
#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) | |||||
#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) | |||||
#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) | |||||
#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) | |||||
#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ | |||||
: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) | |||||
#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ | |||||
: name##_SPLAY_MIN_MAX(x, SPLAY_INF)) | |||||
#define SPLAY_FOREACH(x, name, head) \ | |||||
for ((x) = SPLAY_MIN(name, head); \ | |||||
(x) != NULL; \ | |||||
(x) = SPLAY_NEXT(name, head, x)) | |||||
/* Macros that define a red-black tree */ | |||||
#define RB_SCAN_INFO(name, type) \ | |||||
struct name##_scan_info { \ | |||||
struct name##_scan_info *link; \ | |||||
struct type *node; \ | |||||
} | |||||
#define RB_HEAD(name, type) \ | |||||
struct name { \ | |||||
struct type *rbh_root; /* root of the tree */ \ | |||||
struct name##_scan_info *rbh_inprog; /* scans in progress */ \ | |||||
} | |||||
#define RB_INITIALIZER(root) \ | |||||
{ NULL, NULL } | |||||
#define RB_INIT(root) do { \ | |||||
(root)->rbh_root = NULL; \ | |||||
(root)->rbh_inprog = NULL; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define RB_BLACK 0 | |||||
#define RB_RED 1 | |||||
#define RB_ENTRY(type) \ | |||||
struct { \ | |||||
struct type *rbe_left; /* left element */ \ | |||||
struct type *rbe_right; /* right element */ \ | |||||
struct type *rbe_parent; /* parent element */ \ | |||||
int rbe_color; /* node color */ \ | |||||
} | |||||
#define RB_LEFT(elm, field) (elm)->field.rbe_left | |||||
#define RB_RIGHT(elm, field) (elm)->field.rbe_right | |||||
#define RB_PARENT(elm, field) (elm)->field.rbe_parent | |||||
#define RB_COLOR(elm, field) (elm)->field.rbe_color | |||||
#define RB_ROOT(head) (head)->rbh_root | |||||
#define RB_INPROG(head) (head)->rbh_inprog | |||||
#define RB_EMPTY(head) (RB_ROOT(head) == NULL) | |||||
#define RB_SET(elm, parent, field) do { \ | |||||
RB_PARENT(elm, field) = parent; \ | |||||
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | |||||
RB_COLOR(elm, field) = RB_RED; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define RB_SET_BLACKRED(black, red, field) do { \ | |||||
RB_COLOR(black, field) = RB_BLACK; \ | |||||
RB_COLOR(red, field) = RB_RED; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#ifndef RB_AUGMENT | |||||
#define RB_AUGMENT(x) | |||||
#endif | |||||
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | |||||
(tmp) = RB_RIGHT(elm, field); \ | |||||
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ | |||||
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ | |||||
} \ | |||||
RB_AUGMENT(elm); \ | |||||
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ | |||||
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |||||
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
else \ | |||||
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
} else \ | |||||
(head)->rbh_root = (tmp); \ | |||||
RB_LEFT(tmp, field) = (elm); \ | |||||
RB_PARENT(elm, field) = (tmp); \ | |||||
RB_AUGMENT(tmp); \ | |||||
if ((RB_PARENT(tmp, field))) \ | |||||
RB_AUGMENT(RB_PARENT(tmp, field)); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | |||||
(tmp) = RB_LEFT(elm, field); \ | |||||
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ | |||||
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ | |||||
} \ | |||||
RB_AUGMENT(elm); \ | |||||
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ | |||||
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |||||
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
else \ | |||||
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
} else \ | |||||
(head)->rbh_root = (tmp); \ | |||||
RB_RIGHT(tmp, field) = (elm); \ | |||||
RB_PARENT(elm, field) = (tmp); \ | |||||
RB_AUGMENT(tmp); \ | |||||
if ((RB_PARENT(tmp, field))) \ | |||||
RB_AUGMENT(RB_PARENT(tmp, field)); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
/* Generates prototypes and inline functions */ | |||||
#define RB_PROTOTYPE(name, type, field, cmp) \ | |||||
struct type *name##_RB_REMOVE(struct name *, struct type *); \ | |||||
struct type *name##_RB_INSERT(struct name *, struct type *); \ | |||||
struct type *name##_RB_FIND(struct name *, struct type *); \ | |||||
int name##_RB_SCAN(struct name *, int (*)(struct type *, void *), \ | |||||
int (*)(struct type *, void *), void *); \ | |||||
struct type *name##_RB_NEXT(struct type *); \ | |||||
struct type *name##_RB_MINMAX(struct name *, int); \ | |||||
RB_SCAN_INFO(name, type) \ | |||||
/* Main rb operation. | |||||
* Moves node close to the key of elm to top | |||||
*/ | |||||
#define RB_GENERATE(name, type, field, cmp) \ | |||||
static void \ | |||||
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
struct type *parent, *gparent, *tmp; \ | |||||
while ((parent = RB_PARENT(elm, field)) != NULL && \ | |||||
RB_COLOR(parent, field) == RB_RED) { \ | |||||
gparent = RB_PARENT(parent, field); \ | |||||
if (parent == RB_LEFT(gparent, field)) { \ | |||||
tmp = RB_RIGHT(gparent, field); \ | |||||
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | |||||
RB_COLOR(tmp, field) = RB_BLACK; \ | |||||
RB_SET_BLACKRED(parent, gparent, field);\ | |||||
elm = gparent; \ | |||||
continue; \ | |||||
} \ | |||||
if (RB_RIGHT(parent, field) == elm) { \ | |||||
RB_ROTATE_LEFT(head, parent, tmp, field);\ | |||||
tmp = parent; \ | |||||
parent = elm; \ | |||||
elm = tmp; \ | |||||
} \ | |||||
RB_SET_BLACKRED(parent, gparent, field); \ | |||||
RB_ROTATE_RIGHT(head, gparent, tmp, field); \ | |||||
} else { \ | |||||
tmp = RB_LEFT(gparent, field); \ | |||||
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | |||||
RB_COLOR(tmp, field) = RB_BLACK; \ | |||||
RB_SET_BLACKRED(parent, gparent, field);\ | |||||
elm = gparent; \ | |||||
continue; \ | |||||
} \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | |||||
RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |||||
tmp = parent; \ | |||||
parent = elm; \ | |||||
elm = tmp; \ | |||||
} \ | |||||
RB_SET_BLACKRED(parent, gparent, field); \ | |||||
RB_ROTATE_LEFT(head, gparent, tmp, field); \ | |||||
} \ | |||||
} \ | |||||
RB_COLOR(head->rbh_root, field) = RB_BLACK; \ | |||||
} \ | |||||
\ | |||||
static void \ | |||||
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ | |||||
struct type *elm) \ | |||||
{ \ | |||||
struct type *tmp; \ | |||||
while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ | |||||
elm != RB_ROOT(head)) { \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | |||||
tmp = RB_RIGHT(parent, field); \ | |||||
if (RB_COLOR(tmp, field) == RB_RED) { \ | |||||
RB_SET_BLACKRED(tmp, parent, field); \ | |||||
RB_ROTATE_LEFT(head, parent, tmp, field);\ | |||||
tmp = RB_RIGHT(parent, field); \ | |||||
} \ | |||||
if ((RB_LEFT(tmp, field) == NULL || \ | |||||
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | |||||
(RB_RIGHT(tmp, field) == NULL || \ | |||||
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | |||||
RB_COLOR(tmp, field) = RB_RED; \ | |||||
elm = parent; \ | |||||
parent = RB_PARENT(elm, field); \ | |||||
} else { \ | |||||
if (RB_RIGHT(tmp, field) == NULL || \ | |||||
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ | |||||
struct type *oleft; \ | |||||
if ((oleft = RB_LEFT(tmp, field)) \ | |||||
!= NULL) \ | |||||
RB_COLOR(oleft, field) = RB_BLACK;\ | |||||
RB_COLOR(tmp, field) = RB_RED; \ | |||||
RB_ROTATE_RIGHT(head, tmp, oleft, field);\ | |||||
tmp = RB_RIGHT(parent, field); \ | |||||
} \ | |||||
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | |||||
RB_COLOR(parent, field) = RB_BLACK; \ | |||||
if (RB_RIGHT(tmp, field)) \ | |||||
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ | |||||
RB_ROTATE_LEFT(head, parent, tmp, field);\ | |||||
elm = RB_ROOT(head); \ | |||||
break; \ | |||||
} \ | |||||
} else { \ | |||||
tmp = RB_LEFT(parent, field); \ | |||||
if (RB_COLOR(tmp, field) == RB_RED) { \ | |||||
RB_SET_BLACKRED(tmp, parent, field); \ | |||||
RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |||||
tmp = RB_LEFT(parent, field); \ | |||||
} \ | |||||
if ((RB_LEFT(tmp, field) == NULL || \ | |||||
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | |||||
(RB_RIGHT(tmp, field) == NULL || \ | |||||
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | |||||
RB_COLOR(tmp, field) = RB_RED; \ | |||||
elm = parent; \ | |||||
parent = RB_PARENT(elm, field); \ | |||||
} else { \ | |||||
if (RB_LEFT(tmp, field) == NULL || \ | |||||
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ | |||||
struct type *oright; \ | |||||
if ((oright = RB_RIGHT(tmp, field)) \ | |||||
!= NULL) \ | |||||
RB_COLOR(oright, field) = RB_BLACK;\ | |||||
RB_COLOR(tmp, field) = RB_RED; \ | |||||
RB_ROTATE_LEFT(head, tmp, oright, field);\ | |||||
tmp = RB_LEFT(parent, field); \ | |||||
} \ | |||||
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | |||||
RB_COLOR(parent, field) = RB_BLACK; \ | |||||
if (RB_LEFT(tmp, field)) \ | |||||
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ | |||||
RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |||||
elm = RB_ROOT(head); \ | |||||
break; \ | |||||
} \ | |||||
} \ | |||||
} \ | |||||
if (elm) \ | |||||
RB_COLOR(elm, field) = RB_BLACK; \ | |||||
} \ | |||||
\ | |||||
struct type * \ | |||||
name##_RB_REMOVE(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
struct type *child, *parent, *old; \ | |||||
struct name##_scan_info *inprog; \ | |||||
int color; \ | |||||
\ | |||||
for (inprog = RB_INPROG(head); inprog; inprog = inprog->link) { \ | |||||
if (inprog->node == elm) \ | |||||
inprog->node = RB_NEXT(name, head, elm); \ | |||||
} \ | |||||
\ | |||||
old = elm; \ | |||||
if (RB_LEFT(elm, field) == NULL) \ | |||||
child = RB_RIGHT(elm, field); \ | |||||
else if (RB_RIGHT(elm, field) == NULL) \ | |||||
child = RB_LEFT(elm, field); \ | |||||
else { \ | |||||
struct type *left; \ | |||||
elm = RB_RIGHT(elm, field); \ | |||||
while ((left = RB_LEFT(elm, field)) != NULL) \ | |||||
elm = left; \ | |||||
child = RB_RIGHT(elm, field); \ | |||||
parent = RB_PARENT(elm, field); \ | |||||
color = RB_COLOR(elm, field); \ | |||||
if (child) \ | |||||
RB_PARENT(child, field) = parent; \ | |||||
if (parent) { \ | |||||
if (RB_LEFT(parent, field) == elm) \ | |||||
RB_LEFT(parent, field) = child; \ | |||||
else \ | |||||
RB_RIGHT(parent, field) = child; \ | |||||
RB_AUGMENT(parent); \ | |||||
} else \ | |||||
RB_ROOT(head) = child; \ | |||||
if (RB_PARENT(elm, field) == old) \ | |||||
parent = elm; \ | |||||
(elm)->field = (old)->field; \ | |||||
if (RB_PARENT(old, field)) { \ | |||||
if (RB_LEFT(RB_PARENT(old, field), field) == old)\ | |||||
RB_LEFT(RB_PARENT(old, field), field) = elm;\ | |||||
else \ | |||||
RB_RIGHT(RB_PARENT(old, field), field) = elm;\ | |||||
RB_AUGMENT(RB_PARENT(old, field)); \ | |||||
} else \ | |||||
RB_ROOT(head) = elm; \ | |||||
RB_PARENT(RB_LEFT(old, field), field) = elm; \ | |||||
if (RB_RIGHT(old, field)) \ | |||||
RB_PARENT(RB_RIGHT(old, field), field) = elm; \ | |||||
if (parent) { \ | |||||
left = parent; \ | |||||
do { \ | |||||
RB_AUGMENT(left); \ | |||||
} while ((left = RB_PARENT(left, field)) != NULL); \ | |||||
} \ | |||||
goto color; \ | |||||
} \ | |||||
parent = RB_PARENT(elm, field); \ | |||||
color = RB_COLOR(elm, field); \ | |||||
if (child) \ | |||||
RB_PARENT(child, field) = parent; \ | |||||
if (parent) { \ | |||||
if (RB_LEFT(parent, field) == elm) \ | |||||
RB_LEFT(parent, field) = child; \ | |||||
else \ | |||||
RB_RIGHT(parent, field) = child; \ | |||||
RB_AUGMENT(parent); \ | |||||
} else \ | |||||
RB_ROOT(head) = child; \ | |||||
color: \ | |||||
if (color == RB_BLACK) \ | |||||
name##_RB_REMOVE_COLOR(head, parent, child); \ | |||||
return (old); \ | |||||
} \ | |||||
\ | |||||
/* Inserts a node into the RB tree */ \ | |||||
struct type * \ | |||||
name##_RB_INSERT(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
struct type *tmp; \ | |||||
struct type *parent = NULL; \ | |||||
int comp = 0; \ | |||||
tmp = RB_ROOT(head); \ | |||||
while (tmp) { \ | |||||
parent = tmp; \ | |||||
comp = (cmp)(elm, parent); \ | |||||
if (comp < 0) \ | |||||
tmp = RB_LEFT(tmp, field); \ | |||||
else if (comp > 0) \ | |||||
tmp = RB_RIGHT(tmp, field); \ | |||||
else \ | |||||
return(tmp); \ | |||||
} \ | |||||
RB_SET(elm, parent, field); \ | |||||
if (parent != NULL) { \ | |||||
if (comp < 0) \ | |||||
RB_LEFT(parent, field) = elm; \ | |||||
else \ | |||||
RB_RIGHT(parent, field) = elm; \ | |||||
RB_AUGMENT(parent); \ | |||||
} else \ | |||||
RB_ROOT(head) = elm; \ | |||||
name##_RB_INSERT_COLOR(head, elm); \ | |||||
return (NULL); \ | |||||
} \ | |||||
\ | |||||
/* Finds the node with the same key as elm */ \ | |||||
struct type * \ | |||||
name##_RB_FIND(struct name *head, struct type *elm) \ | |||||
{ \ | |||||
struct type *tmp = RB_ROOT(head); \ | |||||
int comp; \ | |||||
while (tmp) { \ | |||||
comp = cmp(elm, tmp); \ | |||||
if (comp < 0) \ | |||||
tmp = RB_LEFT(tmp, field); \ | |||||
else if (comp > 0) \ | |||||
tmp = RB_RIGHT(tmp, field); \ | |||||
else \ | |||||
return (tmp); \ | |||||
} \ | |||||
return (NULL); \ | |||||
} \ | |||||
\ | |||||
/* \ | |||||
* Issue a callback for all matching items. The scan function must \ | |||||
* return < 0 for items below the desired range, 0 for items within \ | |||||
* the range, and > 0 for items beyond the range. Any item may be \ | |||||
* deleted while the scan is in progress. \ | |||||
*/ \ | |||||
static int \ | |||||
name##_SCANCMP_ALL(struct type *type, void *data) \ | |||||
{ \ | |||||
return(0); \ | |||||
} \ | |||||
\ | |||||
int \ | |||||
name##_RB_SCAN(struct name *head, \ | |||||
int (*scancmp)(struct type *, void *), \ | |||||
int (*callback)(struct type *, void *), \ | |||||
void *data) \ | |||||
{ \ | |||||
struct name##_scan_info info; \ | |||||
struct name##_scan_info **infopp; \ | |||||
struct type *best; \ | |||||
struct type *tmp; \ | |||||
int count; \ | |||||
int comp; \ | |||||
\ | |||||
if (scancmp == NULL) \ | |||||
scancmp = name##_SCANCMP_ALL; \ | |||||
\ | |||||
/* \ | |||||
* Locate the first element. \ | |||||
*/ \ | |||||
tmp = RB_ROOT(head); \ | |||||
best = NULL; \ | |||||
while (tmp) { \ | |||||
comp = scancmp(tmp, data); \ | |||||
if (comp < 0) { \ | |||||
tmp = RB_RIGHT(tmp, field); \ | |||||
} else if (comp > 0) { \ | |||||
tmp = RB_LEFT(tmp, field); \ | |||||
} else { \ | |||||
best = tmp; \ | |||||
if (RB_LEFT(tmp, field) == NULL) \ | |||||
break; \ | |||||
tmp = RB_LEFT(tmp, field); \ | |||||
} \ | |||||
} \ | |||||
count = 0; \ | |||||
if (best) { \ | |||||
info.node = RB_NEXT(name, head, best); \ | |||||
info.link = RB_INPROG(head); \ | |||||
RB_INPROG(head) = &info; \ | |||||
while ((comp = callback(best, data)) >= 0) { \ | |||||
count += comp; \ | |||||
best = info.node; \ | |||||
if (best == NULL || scancmp(best, data) != 0) \ | |||||
break; \ | |||||
info.node = RB_NEXT(name, head, best); \ | |||||
} \ | |||||
if (comp < 0) /* error or termination */ \ | |||||
count = comp; \ | |||||
infopp = &RB_INPROG(head); \ | |||||
while (*infopp != &info) \ | |||||
infopp = &(*infopp)->link; \ | |||||
*infopp = info.link; \ | |||||
} \ | |||||
return(count); \ | |||||
} \ | |||||
\ | |||||
/* ARGSUSED */ \ | |||||
struct type * \ | |||||
name##_RB_NEXT(struct type *elm) \ | |||||
{ \ | |||||
if (RB_RIGHT(elm, field)) { \ | |||||
elm = RB_RIGHT(elm, field); \ | |||||
while (RB_LEFT(elm, field)) \ | |||||
elm = RB_LEFT(elm, field); \ | |||||
} else { \ | |||||
if (RB_PARENT(elm, field) && \ | |||||
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \ | |||||
elm = RB_PARENT(elm, field); \ | |||||
else { \ | |||||
while (RB_PARENT(elm, field) && \ | |||||
(elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ | |||||
elm = RB_PARENT(elm, field); \ | |||||
elm = RB_PARENT(elm, field); \ | |||||
} \ | |||||
} \ | |||||
return (elm); \ | |||||
} \ | |||||
\ | |||||
struct type * \ | |||||
name##_RB_MINMAX(struct name *head, int val) \ | |||||
{ \ | |||||
struct type *tmp = RB_ROOT(head); \ | |||||
struct type *parent = NULL; \ | |||||
while (tmp) { \ | |||||
parent = tmp; \ | |||||
if (val < 0) \ | |||||
tmp = RB_LEFT(tmp, field); \ | |||||
else \ | |||||
tmp = RB_RIGHT(tmp, field); \ | |||||
} \ | |||||
return (parent); \ | |||||
} | |||||
#define RB_NEGINF -1 | |||||
#define RB_INF 1 | |||||
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | |||||
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | |||||
#define RB_FIND(name, x, y) name##_RB_FIND(x, y) | |||||
#define RB_SCAN(name, root, cmp, callback, data) \ | |||||
name##_RB_SCAN(root, cmp, callback, data) | |||||
#define RB_NEXT(name, x, y) name##_RB_NEXT(y) | |||||
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | |||||
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | |||||
#define RB_FOREACH(x, name, head) \ | |||||
for ((x) = RB_MIN(name, head); \ | |||||
(x) != NULL; \ | |||||
(x) = name##_RB_NEXT(x)) | |||||
#endif /* _SYS_TREE_H_ */ |