diff options
Diffstat (limited to 'newlib')
| -rw-r--r-- | newlib/libc/include/sys/tree.h | 864 |
1 files changed, 0 insertions, 864 deletions
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h deleted file mode 100644 index 2d3cec0..0000000 --- a/newlib/libc/include/sys/tree.h +++ /dev/null @@ -1,864 +0,0 @@ -/* $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 $ */ -/* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */ - -/*- - * SPDX-License-Identifier: BSD-2-Clause-FreeBSD - * - * 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_ - -#include <sys/cdefs.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 __unused __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 __unused __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 __unused __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_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = 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_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED) -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET_PARENT(dst, src, field) do { \ - RB_PARENT(dst, field) = src; \ -} while (/*CONSTCOND*/ 0) - -#define RB_SET(elm, parent, field) do { \ - RB_SET_PARENT(elm, parent, field); \ - 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) - -/* - * Something to be invoked in a loop at the root of every modified subtree, - * from the bottom up to the root, to update augmented node data. - */ -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) break -#endif - -#define RB_SWAP_CHILD(head, out, in, field) do { \ - if (RB_PARENT(out, field) == NULL) \ - RB_ROOT(head) = (in); \ - else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ - RB_LEFT(RB_PARENT(out, field), field) = (in); \ - else \ - RB_RIGHT(RB_PARENT(out, field), field) = (in); \ -} while (/*CONSTCOND*/ 0) - -#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_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ - } \ - RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ - RB_SWAP_CHILD(head, elm, tmp, field); \ - RB_LEFT(tmp, field) = (elm); \ - RB_SET_PARENT(elm, tmp, field); \ - RB_AUGMENT(elm); \ -} 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_SET_PARENT(RB_LEFT(elm, field), elm, field); \ - } \ - RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ - RB_SWAP_CHILD(head, elm, tmp, field); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_SET_PARENT(elm, tmp, field); \ - RB_AUGMENT(elm); \ -} while (/*CONSTCOND*/ 0) - -/* - * The RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT() rotations are - * specialized versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be - * used if the parent node exists and the direction of the child element is - * known. - */ - -#define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do { \ - (tmp) = RB_RIGHT(left, field); \ - if ((RB_RIGHT(left, field) = RB_LEFT(tmp, field)) != NULL) { \ - RB_SET_PARENT(RB_RIGHT(left, field), left, field); \ - } \ - RB_SET_PARENT(tmp, parent, field); \ - RB_LEFT(parent, field) = (tmp); \ - RB_LEFT(tmp, field) = (left); \ - RB_SET_PARENT(left, tmp, field); \ - RB_AUGMENT(left); \ -} while (/*CONSTCOND*/ 0) - -#define RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do { \ - (tmp) = RB_LEFT(right, field); \ - if ((RB_LEFT(right, field) = RB_RIGHT(tmp, field)) != NULL) { \ - RB_SET_PARENT(RB_LEFT(right, field), right, field); \ - } \ - RB_SET_PARENT(tmp, parent, field); \ - RB_RIGHT(parent, field) = (tmp); \ - RB_RIGHT(tmp, field) = (right); \ - RB_SET_PARENT(right, tmp, field); \ - RB_AUGMENT(right); \ -} while (/*CONSTCOND*/ 0) - -/* - * The RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() rotations are specialized - * versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be used if we - * rotate an element with a red child which has a black sibling. Such a red - * node must have at least two child nodes so that the following red-black tree - * invariant is fulfilled: - * - * Every path from a given node to any of its descendant NULL nodes goes - * through the same number of black nodes. - * - * elm (could be the root) - * / \ - * BLACK RED (left or right child) - * / \ - * BLACK BLACK - */ - -#define RB_RED_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ - RB_RIGHT(elm, field) = RB_LEFT(tmp, field); \ - RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ - RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ - RB_SWAP_CHILD(head, elm, tmp, field); \ - RB_LEFT(tmp, field) = (elm); \ - RB_SET_PARENT(elm, tmp, field); \ - RB_AUGMENT(elm); \ -} while (/*CONSTCOND*/ 0) - -#define RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ - RB_LEFT(elm, field) = RB_RIGHT(tmp, field); \ - RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ - RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ - RB_SWAP_CHILD(head, elm, tmp, field); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_SET_PARENT(elm, tmp, field); \ - RB_AUGMENT(elm); \ -} while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ - RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ - RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ - RB_PROTOTYPE_INSERT(name, type, attr); \ - RB_PROTOTYPE_REMOVE(name, type, attr); \ - RB_PROTOTYPE_FIND(name, type, attr); \ - RB_PROTOTYPE_NFIND(name, type, attr); \ - RB_PROTOTYPE_NEXT(name, type, attr); \ - RB_PROTOTYPE_PREV(name, type, attr); \ - RB_PROTOTYPE_MINMAX(name, type, attr); \ - RB_PROTOTYPE_REINSERT(name, type, attr); -#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name *, struct type *) -#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ - attr void name##_RB_REMOVE_COLOR(struct name *, struct type *) -#define RB_PROTOTYPE_REMOVE(name, type, attr) \ - attr struct type *name##_RB_REMOVE(struct name *, struct type *) -#define RB_PROTOTYPE_INSERT(name, type, attr) \ - attr struct type *name##_RB_INSERT(struct name *, struct type *) -#define RB_PROTOTYPE_FIND(name, type, attr) \ - attr struct type *name##_RB_FIND(struct name *, struct type *) -#define RB_PROTOTYPE_NFIND(name, type, attr) \ - attr struct type *name##_RB_NFIND(struct name *, struct type *) -#define RB_PROTOTYPE_NEXT(name, type, attr) \ - attr struct type *name##_RB_NEXT(struct type *) -#define RB_PROTOTYPE_PREV(name, type, attr) \ - attr struct type *name##_RB_PREV(struct type *) -#define RB_PROTOTYPE_MINMAX(name, type, attr) \ - attr struct type *name##_RB_MINMAX(struct name *, int) -#define RB_PROTOTYPE_REINSERT(name, type, attr) \ - attr struct type *name##_RB_REINSERT(struct name *, struct type *) - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp,) -#define RB_GENERATE_STATIC(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) -#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ - RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ - RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ - RB_GENERATE_INSERT(name, type, field, cmp, attr) \ - RB_GENERATE_REMOVE(name, type, field, attr) \ - RB_GENERATE_FIND(name, type, field, cmp, attr) \ - RB_GENERATE_NFIND(name, type, field, cmp, attr) \ - RB_GENERATE_NEXT(name, type, field, attr) \ - RB_GENERATE_PREV(name, type, field, attr) \ - RB_GENERATE_MINMAX(name, type, field, attr) \ - RB_GENERATE_REINSERT(name, type, field, cmp, attr) - - -#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ -attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ -{ \ - struct type *parent, *gparent, *tmp; \ - while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (RB_ISRED(tmp, field)) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_PARENT_ROTATE_LEFT(gparent, 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 (RB_ISRED(tmp, field)) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_PARENT_ROTATE_RIGHT(gparent, 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; \ -} - -#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ -attr void \ -name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \ -{ \ - struct type *elm, *tmp; \ - elm = NULL; \ - do { \ - 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_RED_ROTATE_LEFT(head, parent, tmp, field); \ - tmp = RB_RIGHT(parent, field); \ - } \ - if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ - else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ - struct type *oleft; \ - RB_PARENT_ROTATE_RIGHT(parent, tmp, \ - oleft, field); \ - RB_COLOR(oleft, field) = RB_BLACK; \ - tmp = oleft; \ - } else { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - continue; \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, 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_RED_ROTATE_RIGHT(head, parent, tmp, field); \ - tmp = RB_LEFT(parent, field); \ - } \ - if (RB_ISRED(RB_LEFT(tmp, field), field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ - else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ - struct type *oright; \ - RB_PARENT_ROTATE_LEFT(parent, tmp, \ - oright, field); \ - RB_COLOR(oright, field) = RB_BLACK; \ - tmp = oright; \ - } else { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - continue; \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ - } \ - } while (RB_COLOR(elm, field) == RB_BLACK && parent != NULL); \ - RB_COLOR(elm, field) = RB_BLACK; \ -} - -#define RB_GENERATE_REMOVE(name, type, field, attr) \ -attr struct type * \ -name##_RB_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *child, *old, *parent, *right; \ - int color; \ - \ - old = elm; \ - parent = RB_PARENT(elm, field); \ - right = RB_RIGHT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (RB_LEFT(elm, field) == NULL) \ - elm = child = right; \ - else if (right == NULL) \ - elm = child = RB_LEFT(elm, field); \ - else { \ - if ((child = RB_LEFT(right, field)) == NULL) { \ - child = RB_RIGHT(right, field); \ - RB_RIGHT(old, field) = child; \ - parent = elm = right; \ - } else { \ - do \ - elm = child; \ - while ((child = RB_LEFT(elm, field)) != NULL); \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - RB_LEFT(parent, field) = child; \ - RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ - } \ - RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ - color = RB_COLOR(elm, field); \ - elm->field = old->field; \ - } \ - RB_SWAP_CHILD(head, old, elm, field); \ - if (child != NULL) { \ - RB_SET_PARENT(child, parent, field); \ - RB_COLOR(child, field) = RB_BLACK; \ - } else if (color != RB_RED && parent != NULL) \ - name##_RB_REMOVE_COLOR(head, parent); \ - while (parent != NULL) { \ - RB_AUGMENT(parent); \ - parent = RB_PARENT(parent, field); \ - } \ - return (old); \ -} - -#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ -/* Inserts a node into the RB tree */ \ -attr 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; \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - while (elm != NULL) { \ - RB_AUGMENT(elm); \ - elm = RB_PARENT(elm, field); \ - } \ - return (NULL); \ -} - -#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ -/* Finds the node with the same key as elm */ \ -attr 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); \ -} - -#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RB_NFIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ -} - -#define RB_GENERATE_NEXT(name, type, field, attr) \ -/* ARGSUSED */ \ -attr 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); \ -} - -#define RB_GENERATE_PREV(name, type, field, attr) \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_PREV(struct type *elm) \ -{ \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} - -#define RB_GENERATE_MINMAX(name, type, field, attr) \ -attr 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_GENERATE_REINSERT(name, type, field, cmp, attr) \ -attr struct type * \ -name##_RB_REINSERT(struct name *head, struct type *elm) \ -{ \ - struct type *cmpelm; \ - if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ - cmp(cmpelm, elm) >= 0) || \ - ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ - cmp(elm, cmpelm) >= 0)) { \ - /* XXXLAS: Remove/insert is heavy handed. */ \ - RB_REMOVE(name, head, elm); \ - return (RB_INSERT(name, head, elm)); \ - } \ - return (NULL); \ -} \ - -#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_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(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_REINSERT(name, x, y) name##_RB_REINSERT(x, y) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_FROM(x, name, y) \ - for ((x) = (y); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_FROM(x, name, y) \ - for ((x) = (y); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ - (x) = (y)) - -#endif /* _SYS_TREE_H_ */ |