Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show All 30 Lines | |||||
#ifndef _SYS_TREE_H_ | #ifndef _SYS_TREE_H_ | ||||
#define _SYS_TREE_H_ | #define _SYS_TREE_H_ | ||||
#include <sys/cdefs.h> | #include <sys/cdefs.h> | ||||
/* | /* | ||||
* This file defines data structures for different types of trees: | * This file defines data structures for different types of trees: | ||||
* splay trees and red-black trees. | * splay trees and rank-balanced trees. | ||||
* | * | ||||
* A splay tree is a self-organizing data structure. Every operation | * A splay tree is a self-organizing data structure. Every operation | ||||
* on the tree causes a splay to happen. The splay moves the requested | * on the tree causes a splay to happen. The splay moves the requested | ||||
* node to the root of the tree and partly rebalances it. | * node to the root of the tree and partly rebalances it. | ||||
* | * | ||||
* This has the benefit that request locality causes faster lookups as | * 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, | * the requested nodes move to the top of the tree. On the other hand, | ||||
* every lookup causes memory writes. | * every lookup causes memory writes. | ||||
* | * | ||||
* The Balance Theorem bounds the total access time for m operations | * 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 | * 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); | * 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 | * A rank-balanced tree is a binary search tree with an integer | ||||
* extra attribute. It fulfills a set of conditions: | * rank-difference as an attribute of each pointer from parent to child. | ||||
* - every search path from the root to a leaf consists of the | * The sum of the rank-differences on any path from a node down to null is | ||||
* same number of black nodes, | * the same, and defines the rank of that node. The rank of the null node | ||||
* - each red node (except for the root) has a black parent, | * is -1. | ||||
* - each leaf node is black. | |||||
* | * | ||||
* Every operation on a red-black tree is bounded as O(lg n). | * Different additional conditions define different sorts of balanced | ||||
* The maximum height of a red-black tree is 2lg (n+1). | * trees, including "red-black" and "AVL" trees. The set of conditions | ||||
* applied here are the "weak-AVL" conditions of Haeupler, Sen and Tarjan: | |||||
* - every rank-difference is 1 or 2. | |||||
* - the rank of any leaf is 1. | |||||
* | |||||
* For historical reasons, rank differences that are even are associated | |||||
* with the color red (Rank-Even-Difference), and the child that a red edge | |||||
* points to is called a red child. | |||||
markj: It is a bit confusing that during rebalancing, a 0-child's rank difference is even, but the… | |||||
* | |||||
* Every operation on a rank-balanced tree is bounded as O(lg n). | |||||
* The maximum height of a rank-balanced tree is 2lg (n+1). | |||||
*/ | */ | ||||
#define SPLAY_HEAD(name, type) \ | #define SPLAY_HEAD(name, type) \ | ||||
struct name { \ | struct name { \ | ||||
struct type *sph_root; /* root of the tree */ \ | struct type *sph_root; /* root of the tree */ \ | ||||
} | } | ||||
#define SPLAY_INITIALIZER(root) \ | #define SPLAY_INITIALIZER(root) \ | ||||
▲ Show 20 Lines • Show All 219 Lines • ▼ Show 20 Lines | |||||
#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ | #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ | ||||
: name##_SPLAY_MIN_MAX(x, SPLAY_INF)) | : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) | ||||
#define SPLAY_FOREACH(x, name, head) \ | #define SPLAY_FOREACH(x, name, head) \ | ||||
for ((x) = SPLAY_MIN(name, head); \ | for ((x) = SPLAY_MIN(name, head); \ | ||||
(x) != NULL; \ | (x) != NULL; \ | ||||
(x) = SPLAY_NEXT(name, head, x)) | (x) = SPLAY_NEXT(name, head, x)) | ||||
/* Macros that define a red-black tree */ | /* Macros that define a rank-balanced tree */ | ||||
#define RB_HEAD(name, type) \ | #define RB_HEAD(name, type) \ | ||||
struct name { \ | struct name { \ | ||||
struct type *rbh_root; /* root of the tree */ \ | struct type *rbh_root; /* root of the tree */ \ | ||||
} | } | ||||
#define RB_INITIALIZER(root) \ | #define RB_INITIALIZER(root) \ | ||||
{ NULL } | { NULL } | ||||
Show All 14 Lines | |||||
/* | /* | ||||
* With the expectation that any object of struct type has an | * With the expectation that any object of struct type has an | ||||
* address that is a multiple of 4, and that therefore the | * address that is a multiple of 4, and that therefore the | ||||
* 2 least significant bits of a pointer to struct type are | * 2 least significant bits of a pointer to struct type are | ||||
* always zero, this implementation sets those bits to indicate | * always zero, this implementation sets those bits to indicate | ||||
* that the left or right child of the tree node is "red". | * that the left or right child of the tree node is "red". | ||||
*/ | */ | ||||
#define RB_UP(elm, field) (elm)->field.rbe_parent | #define RB_UP(elm, field) (elm)->field.rbe_parent | ||||
#define RB_BITS(elm, field) *(__uintptr_t *)&RB_UP(elm, field) | #define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) | ||||
#define RB_RED_L (__uintptr_t)1 | #define RB_RED_L ((__uintptr_t)1) | ||||
#define RB_RED_R (__uintptr_t)2 | #define RB_RED_R ((__uintptr_t)2) | ||||
#define RB_RED_MASK (__uintptr_t)3 | #define RB_RED_MASK ((__uintptr_t)3) | ||||
Done Inline ActionsI think these should be enclosed by parentheses since they are used in compound expressions, like ~RB_BITS(...). RB_BITS() is also used as an lvalue, but I believe that they can be parenthesized. markj: I think these should be enclosed by parentheses since they are used in compound expressions… | |||||
#define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) | #define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) | ||||
#define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) | #define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) | ||||
#define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) | #define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) | ||||
#define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) | #define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) | ||||
#define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ | #define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ | ||||
(RB_BITS(elm, field) & ~RB_RED_MASK)) | (RB_BITS(elm, field) & ~RB_RED_MASK)) | ||||
/* | |||||
* This header may appear in user code where 'bool' is not defined, | |||||
* so it defines its own boolean type to avoid breaking that code. | |||||
*/ | |||||
#define RB_BOOL int | |||||
#define RB_TRUE 1 | |||||
#define RB_FALSE 0 | |||||
#define RB_ROOT(head) (head)->rbh_root | #define RB_ROOT(head) (head)->rbh_root | ||||
#define RB_EMPTY(head) (RB_ROOT(head) == NULL) | #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | ||||
#define RB_SET_PARENT(dst, src, field) do { \ | #define RB_SET_PARENT(dst, src, field) do { \ | ||||
RB_BITS(dst, field) &= RB_RED_MASK; \ | RB_BITS(dst, field) &= RB_RED_MASK; \ | ||||
RB_BITS(dst, field) |= (__uintptr_t)src; \ | RB_BITS(dst, field) |= (__uintptr_t)src; \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_SET(elm, parent, field) do { \ | #define RB_SET(elm, parent, field) do { \ | ||||
RB_UP(elm, field) = parent; \ | RB_UP(elm, field) = parent; \ | ||||
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \ | #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ | ||||
RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ | RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ | ||||
RB_RED_LEFT(RB_PARENT(elm, field), field) : \ | RB_RED_LEFT(RB_PARENT(elm, field), field) : \ | ||||
RB_RED_RIGHT(RB_PARENT(elm, field), field)) | RB_RED_RIGHT(RB_PARENT(elm, field), field)) | ||||
/* | /* | ||||
* Something to be invoked in a loop at the root of every modified subtree, | * 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. | * from the bottom up to the root, to update augmented node data. | ||||
*/ | */ | ||||
▲ Show 20 Lines • Show All 48 Lines • ▼ Show 20 Lines | #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_PROTOTYPE_NFIND(name, type, attr); \ | RB_PROTOTYPE_NFIND(name, type, attr); \ | ||||
RB_PROTOTYPE_NEXT(name, type, attr); \ | RB_PROTOTYPE_NEXT(name, type, attr); \ | ||||
RB_PROTOTYPE_PREV(name, type, attr); \ | RB_PROTOTYPE_PREV(name, type, attr); \ | ||||
RB_PROTOTYPE_MINMAX(name, type, attr); \ | RB_PROTOTYPE_MINMAX(name, type, attr); \ | ||||
RB_PROTOTYPE_REINSERT(name, type, attr); | RB_PROTOTYPE_REINSERT(name, type, attr); | ||||
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ | #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ | ||||
attr void name##_RB_INSERT_COLOR(struct name *, struct type *) | attr void name##_RB_INSERT_COLOR(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ | #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ | ||||
attr void name##_RB_REMOVE_COLOR(struct name *, struct type *) | attr void name##_RB_REMOVE_COLOR(struct name *, \ | ||||
struct type *, struct type *) | |||||
#define RB_PROTOTYPE_REMOVE(name, type, attr) \ | #define RB_PROTOTYPE_REMOVE(name, type, attr) \ | ||||
attr struct type *name##_RB_REMOVE(struct name *, struct type *) | attr struct type *name##_RB_REMOVE(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_INSERT(name, type, attr) \ | #define RB_PROTOTYPE_INSERT(name, type, attr) \ | ||||
attr struct type *name##_RB_INSERT(struct name *, struct type *) | attr struct type *name##_RB_INSERT(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_FIND(name, type, attr) \ | #define RB_PROTOTYPE_FIND(name, type, attr) \ | ||||
attr struct type *name##_RB_FIND(struct name *, struct type *) | attr struct type *name##_RB_FIND(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_NFIND(name, type, attr) \ | #define RB_PROTOTYPE_NFIND(name, type, attr) \ | ||||
attr struct type *name##_RB_NFIND(struct name *, struct type *) | attr struct type *name##_RB_NFIND(struct name *, struct type *) | ||||
Show All 25 Lines | #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_MINMAX(name, type, field, attr) \ | RB_GENERATE_MINMAX(name, type, field, attr) \ | ||||
RB_GENERATE_REINSERT(name, type, field, cmp, attr) | RB_GENERATE_REINSERT(name, type, field, cmp, attr) | ||||
#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ | #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ | ||||
attr void \ | attr void \ | ||||
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | ||||
{ \ | { \ | ||||
struct type *gparent, *parent; \ | struct type *child, *parent; \ | ||||
while ((parent = RB_PARENT(elm, field)) != NULL) { \ | while ((parent = RB_PARENT(elm, field)) != NULL) { \ | ||||
if (RB_LEFT(parent, field) == elm) \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | |||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
else \ | return; \ | ||||
} \ | |||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if ((gparent = RB_PARENT(parent, field)) == NULL) \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
break; \ | elm = parent; \ | ||||
if (RB_RED_LEFT(gparent, field) && \ | |||||
RB_RED_RIGHT(gparent, field)) { \ | |||||
RB_FLIP_LEFT(gparent, field); \ | |||||
RB_FLIP_RIGHT(gparent, field); \ | |||||
elm = gparent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (RB_RED_LEFT(gparent, field) && \ | if (!RB_RED_RIGHT(elm, field)) { \ | ||||
parent == RB_LEFT(gparent, field)) { \ | |||||
if (RB_RIGHT(parent, field) == elm) { \ | |||||
RB_ROTATE_LEFT(head, parent, elm, field);\ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
RB_FLIP_LEFT(elm, field); \ | RB_FLIP_LEFT(elm, field); \ | ||||
parent = elm; \ | RB_ROTATE_LEFT(head, elm, child, field);\ | ||||
if (RB_RED_LEFT(child, field)) \ | |||||
RB_FLIP_RIGHT(elm, field); \ | |||||
else if (RB_RED_RIGHT(child, field)) \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
elm = child; \ | |||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, gparent, parent, field); \ | |||||
RB_FLIP_LEFT(gparent, field); \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
} else if (RB_RED_RIGHT(gparent, field) && \ | |||||
parent == RB_RIGHT(gparent, field)) { \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | |||||
RB_ROTATE_RIGHT(head, parent, elm, field);\ | RB_ROTATE_RIGHT(head, parent, elm, field); \ | ||||
} else { \ | |||||
if (RB_RED_RIGHT(parent, field)) { \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
return; \ | |||||
} \ | |||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | |||||
elm = parent; \ | |||||
continue; \ | |||||
} \ | |||||
if (!RB_RED_LEFT(elm, field)) { \ | |||||
RB_FLIP_RIGHT(elm, field); \ | RB_FLIP_RIGHT(elm, field); \ | ||||
parent = elm; \ | RB_ROTATE_RIGHT(head, elm, child, field);\ | ||||
if (RB_RED_RIGHT(child, field)) \ | |||||
RB_FLIP_LEFT(elm, field); \ | |||||
else if (RB_RED_LEFT(child, field)) \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
elm = child; \ | |||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, gparent, parent, field); \ | RB_ROTATE_LEFT(head, parent, elm, field); \ | ||||
RB_FLIP_RIGHT(gparent, field); \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
} \ | } \ | ||||
RB_BITS(elm, field) &= ~RB_RED_MASK; \ | |||||
break; \ | break; \ | ||||
} \ | } \ | ||||
} | } | ||||
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | ||||
attr void \ | attr void \ | ||||
name##_RB_REMOVE_COLOR(struct name *head, struct type *par) \ | name##_RB_REMOVE_COLOR(struct name *head, \ | ||||
struct type *parent, struct type *elm) \ | |||||
{ \ | { \ | ||||
struct type *gpr, *sib, *nec; \ | struct type *sib; \ | ||||
RB_BOOL left_elm, left_par, red_gpr; \ | if (RB_LEFT(parent, field) == elm && \ | ||||
left_par = (RB_LEFT(par, field) == NULL); \ | RB_RIGHT(parent, field) == elm) { \ | ||||
RB_BITS(parent, field) &= ~RB_RED_MASK; \ | |||||
elm = parent; \ | |||||
parent = RB_PARENT(elm, field); \ | |||||
if (parent == NULL) \ | |||||
return; \ | |||||
} \ | |||||
do { \ | do { \ | ||||
left_elm = left_par; \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (left_elm ? \ | if (!RB_RED_LEFT(parent, field)) { \ | ||||
!RB_RED_RIGHT(par, field) : \ | RB_FLIP_LEFT(parent, field); \ | ||||
!RB_RED_LEFT(par, field)) { \ | return; \ | ||||
gpr = RB_PARENT(par, field); \ | |||||
left_par = gpr != NULL && \ | |||||
RB_LEFT(gpr, field) == par; \ | |||||
red_gpr = gpr == NULL ? \ | |||||
RB_TRUE: RB_COLOR(par, field); \ | |||||
} \ | } \ | ||||
if (left_elm) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
if (RB_RED_RIGHT(par, field)) { \ | RB_FLIP_RIGHT(parent, field); \ | ||||
red_gpr = RB_TRUE; \ | elm = parent; \ | ||||
RB_ROTATE_LEFT(head, par, gpr, field); \ | continue; \ | ||||
RB_FLIP_RIGHT(par, field); \ | |||||
RB_FLIP_LEFT(gpr, field); \ | |||||
} \ | } \ | ||||
sib = RB_RIGHT(par, field); \ | sib = RB_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(sib, field)) { \ | if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | ||||
if (RB_RED_LEFT(sib, field)) { \ | RB_BITS(sib, field) &= ~RB_RED_MASK; \ | ||||
RB_FLIP_LEFT(sib, field); \ | elm = parent; \ | ||||
RB_FLIP_RIGHT(par, field); \ | continue; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(sib, field); \ | ||||
} else if (RB_RED_LEFT(sib, field)) { \ | if (RB_RED_LEFT(sib, field)) \ | ||||
RB_ROTATE_RIGHT(head, sib, nec, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
else if (!RB_RED_RIGHT(sib, field)) { \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
RB_ROTATE_RIGHT(head, sib, elm, field); \ | |||||
if (RB_RED_RIGHT(elm, field)) \ | |||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(sib, field); \ | ||||
sib = nec; \ | if (RB_RED_LEFT(elm, field)) \ | ||||
} else { \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_FLIP_RIGHT(par, field); \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
par = gpr; \ | sib = elm; \ | ||||
continue; \ | |||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, par, sib, field); \ | RB_ROTATE_LEFT(head, parent, sib, field); \ | ||||
return; \ | |||||
} else { \ | } else { \ | ||||
if (RB_RED_LEFT(par, field)) { \ | if (!RB_RED_RIGHT(parent, field)) { \ | ||||
red_gpr = RB_TRUE; \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_ROTATE_RIGHT(head, par, gpr, field); \ | return; \ | ||||
RB_FLIP_LEFT(par, field); \ | |||||
RB_FLIP_RIGHT(gpr, field); \ | |||||
} \ | } \ | ||||
sib = RB_LEFT(par, field); \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
if (RB_RED_LEFT(sib, field)) { \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_RIGHT(sib, field)) { \ | elm = parent; \ | ||||
RB_FLIP_RIGHT(sib, field); \ | continue; \ | ||||
RB_FLIP_LEFT(par, field); \ | |||||
} \ | } \ | ||||
sib = RB_LEFT(parent, field); \ | |||||
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | |||||
RB_BITS(sib, field) &= ~RB_RED_MASK; \ | |||||
elm = parent; \ | |||||
continue; \ | |||||
} \ | |||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(sib, field); \ | ||||
} else if (RB_RED_RIGHT(sib, field)) { \ | if (RB_RED_RIGHT(sib, field)) \ | ||||
RB_ROTATE_LEFT(head, sib, nec, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
else if (!RB_RED_LEFT(sib, field)) { \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
RB_ROTATE_LEFT(head, sib, elm, field); \ | |||||
if (RB_RED_LEFT(elm, field)) \ | |||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(sib, field); \ | ||||
sib = nec; \ | if (RB_RED_RIGHT(elm, field)) \ | ||||
} else { \ | RB_FLIP_LEFT(parent, field); \ | ||||
RB_FLIP_LEFT(par, field); \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
par = gpr; \ | sib = elm; \ | ||||
continue; \ | |||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, par, sib, field); \ | RB_ROTATE_RIGHT(head, parent, sib, field); \ | ||||
return; \ | |||||
} \ | } \ | ||||
} while (!red_gpr); \ | break; \ | ||||
if (gpr == NULL); \ | } while ((parent = RB_PARENT(elm, field)) != NULL); \ | ||||
else if (left_par) \ | |||||
RB_FLIP_LEFT(gpr, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(gpr, field); \ | |||||
} | } | ||||
#define RB_GENERATE_REMOVE(name, type, field, attr) \ | #define RB_GENERATE_REMOVE(name, type, field, attr) \ | ||||
attr struct type * \ | attr struct type * \ | ||||
name##_RB_REMOVE(struct name *head, struct type *elm) \ | name##_RB_REMOVE(struct name *head, struct type *elm) \ | ||||
{ \ | { \ | ||||
struct type *child, *old, *parent, *right; \ | struct type *child, *old, *parent, *right; \ | ||||
RB_BOOL red; \ | |||||
\ | \ | ||||
old = elm; \ | old = elm; \ | ||||
parent = RB_PARENT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
right = RB_RIGHT(elm, field); \ | right = RB_RIGHT(elm, field); \ | ||||
if (RB_LEFT(elm, field) == NULL) \ | if (RB_LEFT(elm, field) == NULL) \ | ||||
elm = child = right; \ | elm = child = right; \ | ||||
else if (right == NULL) \ | else if (right == NULL) \ | ||||
elm = child = RB_LEFT(elm, field); \ | elm = child = RB_LEFT(elm, field); \ | ||||
else { \ | else { \ | ||||
if ((child = RB_LEFT(right, field)) == NULL) { \ | if ((child = RB_LEFT(right, field)) == NULL) { \ | ||||
child = RB_RIGHT(right, field); \ | child = RB_RIGHT(right, field); \ | ||||
red = RB_RED_RIGHT(old, field); \ | |||||
if (red) \ | |||||
RB_FLIP_RIGHT(old, field); \ | |||||
RB_RIGHT(old, field) = child; \ | RB_RIGHT(old, field) = child; \ | ||||
parent = elm = right; \ | parent = elm = right; \ | ||||
} else { \ | } else { \ | ||||
do \ | do \ | ||||
elm = child; \ | elm = child; \ | ||||
while ((child = RB_LEFT(elm, field)) != NULL); \ | while ((child = RB_LEFT(elm, field)) != NULL); \ | ||||
child = RB_RIGHT(elm, field); \ | child = RB_RIGHT(elm, field); \ | ||||
parent = RB_PARENT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
red = RB_RED_LEFT(parent, field); \ | |||||
if (red) \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
RB_LEFT(parent, field) = child; \ | RB_LEFT(parent, field) = child; \ | ||||
RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ | RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\ | ||||
} \ | } \ | ||||
RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | ||||
elm->field = old->field; \ | elm->field = old->field; \ | ||||
} \ | } \ | ||||
if (elm == child) { \ | |||||
red = RB_COLOR(old, field); \ | |||||
if (!red); \ | |||||
else if (RB_LEFT(parent, field) == old) \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
} \ | |||||
RB_SWAP_CHILD(head, old, elm, field); \ | RB_SWAP_CHILD(head, old, elm, field); \ | ||||
if (child != NULL) \ | if (child != NULL) \ | ||||
RB_SET_PARENT(child, parent, field); \ | RB_SET_PARENT(child, parent, field); \ | ||||
else if (!red && parent != NULL) \ | if (parent != NULL) \ | ||||
name##_RB_REMOVE_COLOR(head, parent); \ | name##_RB_REMOVE_COLOR(head, parent, child); \ | ||||
while (parent != NULL) { \ | while (parent != NULL) { \ | ||||
RB_AUGMENT(parent); \ | RB_AUGMENT(parent); \ | ||||
parent = RB_PARENT(parent, field); \ | parent = RB_PARENT(parent, field); \ | ||||
} \ | } \ | ||||
return (old); \ | return (old); \ | ||||
} | } | ||||
#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | ||||
▲ Show 20 Lines • Show All 196 Lines • Show Last 20 Lines |
It is a bit confusing that during rebalancing, a 0-child's rank difference is even, but the child is not red. I can't see a way around that without complicating the encoding, though.