Page MenuHomeFreeBSD
Files F111631151

D25480.id73783.diff
No OneTemporary
Actions

D25480.id73783.diff
View Options

Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ share/man/man3/tree.3
@@ -99,7 +99,7 @@
.Nm RB_INSERT ,
.Nm RB_REMOVE ,
.Nm RB_REINSERT
-.Nd "implementations of splay and red-black trees"
+.Nd "implementations of splay and rank-balanced (wavl) trees"
.Sh SYNOPSIS
.In sys/tree.h
.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
@@ -195,7 +195,7 @@
.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
.Sh DESCRIPTION
These macros define data structures for different types of trees:
-splay trees and red-black trees.
+splay trees and rank-balanced (wavl) trees.
.Pp
In the macro definitions,
.Fa TYPE
@@ -364,26 +364,30 @@
The
.Fn SPLAY_EMPTY
macro should be used to check whether a splay tree is empty.
-.Sh RED-BLACK TREES
-A red-black tree is a binary search tree with the node color as an
-extra attribute.
-It fulfills a set of conditions:
+.Sh RANK-BALANCED TREES
+A rank-balanced tree is a binary search tree with an integer
+rank-difference as an attribute of each pointer from parent to child.
+The sum of the rank-differences on any path from a node down to null
+is the same, and defines the rank of that node. The rank of the null
+node is -1.
+.Pp
+Different additional conditions define different sorts of balanced
+trees, including "red-black" and "AVL" trees. The set of conditions
+applied here are the "weak-AVL" conditions of Haeupler, Sen and
+Tarjan:
.Bl -enum -offset indent
.It
-Every search path from the root to a leaf consists of the same number of
-black nodes.
+Every rank-difference is 1 or 2.
.It
-Each red node (except for the root) has a black parent.
-.It
-Each leaf node is black.
+The rank of any leaf is 1.
.El
.Pp
-Every operation on a red-black tree is bounded as
+Every operation on a rank-balanced tree is bounded as
.Fn O "lg n" .
-The maximum height of a red-black tree is
+The maximum height of a rank-balanced tree is
.Fn 2lg "n + 1" .
.Pp
-A red-black tree is headed by a structure defined by the
+A rank-balanced tree is headed by a structure defined by the
.Fn RB_HEAD
macro.
A
@@ -488,7 +492,7 @@
macro initializes the tree referenced by
.Fa head .
.Pp
-The red-black tree can also be initialized statically by using the
+The rank-balanced tree can also be initialized statically by using the
.Fn RB_INITIALIZER
macro like this:
.Bd -ragged -offset indent
@@ -567,7 +571,7 @@
.Pp
The
.Fn RB_EMPTY
-macro should be used to check whether a red-black tree is empty.
+macro should be used to check whether a rank-balanced tree is empty.
.Pp
The
.Fn RB_REINSERT
@@ -581,7 +585,7 @@
This is a lower overhead alternative to removing the element
and reinserting it again.
.Sh EXAMPLES
-The following example demonstrates how to declare a red-black tree
+The following example demonstrates how to declare a rank-balanced tree
holding integers.
Values are inserted into it and the contents of the tree are printed
in order.
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -36,7 +36,7 @@
/*
* 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
* on the tree causes a splay to happen. The splay moves the requested
@@ -50,15 +50,24 @@
* 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.
+ * A rank-balanced tree is a binary search tree with an integer
+ * rank-difference as an attribute of each pointer from parent to child.
+ * The sum of the rank-differences on any path from a node down to null is
+ * the same, and defines the rank of that node. The rank of the null node
+ * is -1.
*
- * 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).
+ * Different additional conditions define different sorts of balanced
+ * 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.
+ *
+ * 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) \
@@ -294,7 +303,7 @@
(x) != NULL; \
(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) \
struct name { \
struct type *rbh_root; /* root of the tree */ \
@@ -422,7 +431,8 @@
#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 *)
+ attr void name##_RB_REMOVE_COLOR(struct name *, \
+ struct type *, 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) \
@@ -464,123 +474,141 @@
attr void \
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) { \
- if (RB_LEFT(parent, field) == elm) \
- RB_FLIP_LEFT(parent, field); \
- else \
+ if (RB_LEFT(parent, field) == elm) { \
+ if (RB_RED_LEFT(parent, field)) { \
+ RB_FLIP_LEFT(parent, field); \
+ return; \
+ } \
RB_FLIP_RIGHT(parent, field); \
- if ((gparent = RB_PARENT(parent, field)) == NULL) \
- break; \
- if (RB_RED_LEFT(gparent, field) && \
- RB_RED_RIGHT(gparent, field)) { \
- RB_FLIP_LEFT(gparent, field); \
- RB_FLIP_RIGHT(gparent, field); \
- elm = gparent; \
- continue; \
- } \
- if (RB_RED_LEFT(gparent, field) && \
- parent == RB_LEFT(gparent, field)) { \
- if (RB_RIGHT(parent, field) == elm) { \
- RB_ROTATE_LEFT(head, parent, elm, field);\
+ if (RB_RED_RIGHT(parent, field)) { \
+ elm = parent; \
+ continue; \
+ } \
+ if (RB_RED_RIGHT(elm, field)) \
+ RB_FLIP_RIGHT(elm, field); \
+ else { \
+ RB_ROTATE_LEFT(head, elm, child, field);\
+ RB_FLIP_LEFT(elm, field); \
+ if (RB_RED_LEFT(child, field)) { \
+ RB_FLIP_LEFT(child, field); \
+ RB_FLIP_RIGHT(elm, field); \
+ } else if (RB_RED_RIGHT(child, field)) {\
+ RB_FLIP_RIGHT(child, field); \
+ RB_FLIP_LEFT(parent, field); \
+ } \
+ elm = child; \
+ } \
+ 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); \
+ if (RB_RED_LEFT(parent, field)) { \
+ elm = parent; \
+ continue; \
+ } \
+ if (RB_RED_LEFT(elm, field)) \
RB_FLIP_LEFT(elm, field); \
- parent = elm; \
- } \
- 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_FLIP_LEFT(parent, field); \
+ else { \
+ RB_ROTATE_RIGHT(head, elm, child, field);\
RB_FLIP_RIGHT(elm, field); \
- parent = elm; \
+ if (RB_RED_RIGHT(child, field)) { \
+ RB_FLIP_RIGHT(child, field); \
+ RB_FLIP_LEFT(elm, field); \
+ } else if (RB_RED_LEFT(child, field)) { \
+ RB_FLIP_LEFT(child, field); \
+ RB_FLIP_RIGHT(parent, field); \
+ } \
+ elm = child; \
} \
- RB_ROTATE_LEFT(head, gparent, parent, field); \
- RB_FLIP_RIGHT(gparent, field); \
- RB_FLIP_LEFT(parent, field); \
+ RB_ROTATE_LEFT(head, parent, elm, field); \
} \
- break; \
+ break; \
} \
}
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
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; \
- RB_BOOL left_elm, left_par, red_gpr; \
- left_par = (RB_LEFT(par, field) == NULL); \
- do { \
- left_elm = left_par; \
- if (left_elm ? \
- !RB_RED_RIGHT(par, field) : \
- !RB_RED_LEFT(par, field)) { \
- 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(par, field)) { \
- red_gpr = RB_TRUE; \
- RB_ROTATE_LEFT(head, par, gpr, field); \
- RB_FLIP_RIGHT(par, field); \
- RB_FLIP_LEFT(gpr, field); \
+ struct type *nec, *sib; \
+ do { \
+ if (RB_LEFT(parent, field) == elm) { \
+ if (!RB_RED_LEFT(parent, field)) { \
+ RB_FLIP_LEFT(parent, field); \
+ return; \
} \
- sib = RB_RIGHT(par, field); \
- if (RB_RED_RIGHT(sib, field)) { \
- if (RB_RED_LEFT(sib, field)) { \
- RB_FLIP_LEFT(sib, field); \
- RB_FLIP_RIGHT(par, field); \
- } \
- RB_FLIP_RIGHT(sib, field); \
- } else if (RB_RED_LEFT(sib, field)) { \
- RB_ROTATE_RIGHT(head, sib, nec, field); \
+ if (RB_RED_RIGHT(parent, field)) { \
+ RB_FLIP_RIGHT(parent, field); \
+ elm = parent; \
+ continue; \
+ } \
+ sib = RB_RIGHT(parent, field); \
+ RB_FLIP_RIGHT(sib, field); \
+ if (RB_RED_LEFT(sib, field) && \
+ !RB_RED_RIGHT(sib, field)) { \
RB_FLIP_LEFT(sib, field); \
- sib = nec; \
- } else { \
- RB_FLIP_RIGHT(par, field); \
- par = gpr; \
+ elm = parent; \
continue; \
} \
- RB_ROTATE_LEFT(head, par, sib, field); \
- return; \
+ if (RB_RED_LEFT(sib, field)) \
+ RB_FLIP_LEFT(parent, field); \
+ if (!RB_RED_RIGHT(sib, field)) { \
+ RB_FLIP_LEFT(parent, field); \
+ RB_ROTATE_RIGHT(head, sib, nec, field); \
+ if (RB_RED_RIGHT(nec, field)) \
+ RB_FLIP_LEFT(sib, field); \
+ else \
+ RB_FLIP_RIGHT(nec, field); \
+ if (RB_RED_LEFT(nec, field)) \
+ RB_FLIP_RIGHT(parent, field); \
+ else \
+ RB_FLIP_LEFT(nec, field); \
+ sib = nec; \
+ } \
+ RB_ROTATE_LEFT(head, parent, sib, field); \
} else { \
- if (RB_RED_LEFT(par, field)) { \
- red_gpr = RB_TRUE; \
- RB_ROTATE_RIGHT(head, par, gpr, field); \
- RB_FLIP_LEFT(par, field); \
- RB_FLIP_RIGHT(gpr, field); \
+ if (!RB_RED_RIGHT(parent, field)) { \
+ RB_FLIP_RIGHT(parent, field); \
+ return; \
} \
- sib = RB_LEFT(par, field); \
- if (RB_RED_LEFT(sib, field)) { \
- if (RB_RED_RIGHT(sib, field)) { \
- RB_FLIP_RIGHT(sib, field); \
- RB_FLIP_LEFT(par, field); \
- } \
- RB_FLIP_LEFT(sib, field); \
- } else if (RB_RED_RIGHT(sib, field)) { \
- RB_ROTATE_LEFT(head, sib, nec, field); \
+ if (RB_RED_LEFT(parent, field)) { \
+ RB_FLIP_LEFT(parent, field); \
+ elm = parent; \
+ continue; \
+ } \
+ sib = RB_LEFT(parent, field); \
+ RB_FLIP_LEFT(sib, field); \
+ if (RB_RED_RIGHT(sib, field) && \
+ !RB_RED_LEFT(sib, field)) { \
RB_FLIP_RIGHT(sib, field); \
- sib = nec; \
- } else { \
- RB_FLIP_LEFT(par, field); \
- par = gpr; \
+ elm = parent; \
continue; \
} \
- RB_ROTATE_RIGHT(head, par, sib, field); \
- return; \
+ if (RB_RED_RIGHT(sib, field)) \
+ RB_FLIP_RIGHT(parent, field); \
+ if (!RB_RED_LEFT(sib, field)) { \
+ RB_FLIP_RIGHT(parent, field); \
+ RB_ROTATE_LEFT(head, sib, nec, field); \
+ if (RB_RED_LEFT(nec, field)) \
+ RB_FLIP_RIGHT(sib, field); \
+ else \
+ RB_FLIP_LEFT(nec, field); \
+ if (RB_RED_RIGHT(nec, field)) \
+ RB_FLIP_LEFT(parent, field); \
+ else \
+ RB_FLIP_RIGHT(nec, field); \
+ sib = nec; \
+ } \
+ RB_ROTATE_RIGHT(head, parent, sib, field); \
} \
- } while (!red_gpr); \
- if (gpr == NULL); \
- else if (left_par) \
- RB_FLIP_LEFT(gpr, field); \
- else \
- RB_FLIP_RIGHT(gpr, field); \
+ break; \
+ } while ((parent = RB_PARENT(elm, field)) != NULL); \
}
#define RB_GENERATE_REMOVE(name, type, field, attr) \
@@ -601,7 +629,7 @@
if ((child = RB_LEFT(right, field)) == NULL) { \
child = RB_RIGHT(right, field); \
red = RB_RED_RIGHT(old, field); \
- if (red) \
+ if (!red) \
RB_FLIP_RIGHT(old, field); \
RB_RIGHT(old, field) = child; \
parent = elm = right; \
@@ -612,7 +640,7 @@
child = RB_RIGHT(elm, field); \
parent = RB_PARENT(elm, field); \
red = RB_RED_LEFT(parent, field); \
- if (red) \
+ if (!red) \
RB_FLIP_LEFT(parent, field); \
RB_LEFT(parent, field) = child; \
RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \
@@ -622,7 +650,7 @@
} \
if (elm == child) { \
red = RB_COLOR(old, field); \
- if (!red); \
+ if (red || parent == NULL); \
else if (RB_LEFT(parent, field) == old) \
RB_FLIP_LEFT(parent, field); \
else \
@@ -631,8 +659,18 @@
RB_SWAP_CHILD(head, old, elm, field); \
if (child != NULL) \
RB_SET_PARENT(child, parent, field); \
- else if (!red && parent != NULL) \
- name##_RB_REMOVE_COLOR(head, parent); \
+ else if (parent != NULL && \
+ RB_LEFT(parent, field) == NULL && \
+ RB_RIGHT(parent, field) == NULL) { \
+ RB_FLIP_LEFT(parent, field); \
+ RB_FLIP_RIGHT(parent, field); \
+ child = parent; \
+ do { RB_AUGMENT(parent); } while(0); \
+ parent = RB_PARENT(child, field); \
+ red = parent != NULL; \
+ } \
+ if (red) \
+ name##_RB_REMOVE_COLOR(head, parent, child); \
while (parent != NULL) { \
RB_AUGMENT(parent); \
parent = RB_PARENT(parent, field); \

File Metadata

Mime Type
text/plain
Expires
Fri, Mar 7, 6:38 AM (18 h, 18 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
17026769
Default Alt Text
D25480.id73783.diff (14 KB)

Event Timeline