aboutsummaryrefslogtreecommitdiff
path: root/sys/sys
diff options
context:
space:
mode:
authorDoug Moore <dougm@FreeBSD.org>2020-07-23 17:16:20 +0000
committerDoug Moore <dougm@FreeBSD.org>2020-07-23 17:16:20 +0000
commite605dcc939848312a201b4aa53bd7bb67d862b18 (patch)
tree6c800f06b56aa8da98656aafdd79fcc3afab41af /sys/sys
parent7df88b9ddd2e7db27ab71d38db8d0d6b4ad31e51 (diff)
downloadsrc-e605dcc939848312a201b4aa53bd7bb67d862b18.tar.gz
src-e605dcc939848312a201b4aa53bd7bb67d862b18.zip
Rank balanced (RB) trees are a class of balanced trees that includes
AVL trees, red-black trees, and others. Weak AVL (wavl) trees are a recently discovered member of that class. This change replaces red-black rebalancing with weak AVL rebalancing in the RB tree macros. Wavl trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have the stricter balance of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can decay to that of a red-black tree. Subsequent insertions can push balance back toward the stricter AVL conditions. Removing a node from a wavl tree never requires more than two rotations, which is better than either red-black or AVL trees. Inserting a node into a wavl tree never requires more than two rotations, which matches red-black and AVL trees. The only disadvantage of wavl trees to red-black trees is that more insertions are likely to adjust the tree a bit. That's the cost of keeping the tree more balanced. Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing. Reviewed by: alc, gbe, markj Tested by: pho Discussed with: emaste Differential Revision: https://reviews.freebsd.org/D25480
Notes
Notes: svn path=/head/; revision=363450
Diffstat (limited to 'sys/sys')
-rw-r--r--sys/sys/tree.h271
1 files changed, 133 insertions, 138 deletions
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index dae592ad7375..7fa7806c9a91 100644
--- a/sys/sys/tree.h
+++ b/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 @@ void name##_SPLAY_MINMAX(struct name *head, int __comp) \
(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 */ \
@@ -325,25 +334,16 @@ struct { \
* that the left or right child of the tree node is "red".
*/
#define RB_UP(elm, field) (elm)->field.rbe_parent
-#define RB_BITS(elm, field) *(__uintptr_t *)&RB_UP(elm, field)
-#define RB_RED_L (__uintptr_t)1
-#define RB_RED_R (__uintptr_t)2
-#define RB_RED_MASK (__uintptr_t)3
+#define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field))
+#define RB_RED_L ((__uintptr_t)1)
+#define RB_RED_R ((__uintptr_t)2)
+#define RB_RED_MASK ((__uintptr_t)3)
#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_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_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \
(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_EMPTY(head) (RB_ROOT(head) == NULL)
@@ -357,7 +357,7 @@ struct { \
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
} 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_RED_LEFT(RB_PARENT(elm, field), field) : \
RB_RED_RIGHT(RB_PARENT(elm, field), field))
@@ -422,7 +422,8 @@ struct { \
#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 +465,132 @@ struct { \
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);\
- RB_FLIP_RIGHT(parent, field); \
+ if (RB_RED_RIGHT(parent, field)) { \
+ elm = parent; \
+ continue; \
+ } \
+ if (!RB_RED_RIGHT(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_FLIP_LEFT(parent, field); \
- RB_FLIP_RIGHT(elm, field); \
- parent = elm; \
+ RB_ROTATE_RIGHT(head, parent, elm, field); \
+ } else { \
+ if (RB_RED_RIGHT(parent, field)) { \
+ RB_FLIP_RIGHT(parent, field); \
+ return; \
} \
- RB_ROTATE_LEFT(head, gparent, parent, field); \
- RB_FLIP_RIGHT(gparent, 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_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, parent, elm, field); \
} \
+ RB_BITS(elm, field) &= ~RB_RED_MASK; \
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 *sib; \
+ if (RB_LEFT(parent, field) == elm && \
+ RB_RIGHT(parent, field) == elm) { \
+ RB_BITS(parent, field) &= ~RB_RED_MASK; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ if (parent == NULL) \
+ return; \
+ } \
+ 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); \
- RB_FLIP_LEFT(sib, field); \
- sib = nec; \
- } else { \
- RB_FLIP_RIGHT(par, field); \
- par = gpr; \
+ if (RB_RED_RIGHT(parent, field)) { \
+ RB_FLIP_RIGHT(parent, field); \
+ elm = parent; \
continue; \
} \
- RB_ROTATE_LEFT(head, par, sib, field); \
- return; \
+ sib = RB_RIGHT(parent, field); \
+ if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
+ RB_BITS(sib, field) &= ~RB_RED_MASK; \
+ elm = parent; \
+ continue; \
+ } \
+ RB_FLIP_RIGHT(sib, field); \
+ if (RB_RED_LEFT(sib, 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); \
+ if (RB_RED_LEFT(elm, field)) \
+ RB_FLIP_RIGHT(parent, field); \
+ RB_BITS(elm, field) |= RB_RED_MASK; \
+ sib = elm; \
+ } \
+ 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); \
- RB_FLIP_RIGHT(sib, field); \
- sib = nec; \
- } else { \
- RB_FLIP_LEFT(par, field); \
- par = gpr; \
+ if (RB_RED_LEFT(parent, field)) { \
+ RB_FLIP_LEFT(parent, field); \
+ elm = parent; \
continue; \
} \
- RB_ROTATE_RIGHT(head, par, sib, field); \
- return; \
+ 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); \
+ if (RB_RED_RIGHT(sib, 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); \
+ if (RB_RED_RIGHT(elm, field)) \
+ RB_FLIP_LEFT(parent, field); \
+ RB_BITS(elm, field) |= RB_RED_MASK; \
+ sib = elm; \
+ } \
+ 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) \
@@ -588,7 +598,6 @@ attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *elm) \
{ \
struct type *child, *old, *parent, *right; \
- RB_BOOL red; \
\
old = elm; \
parent = RB_PARENT(elm, field); \
@@ -600,9 +609,6 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
else { \
if ((child = RB_LEFT(right, field)) == NULL) { \
child = RB_RIGHT(right, field); \
- red = RB_RED_RIGHT(old, field); \
- if (red) \
- RB_FLIP_RIGHT(old, field); \
RB_RIGHT(old, field) = child; \
parent = elm = right; \
} else { \
@@ -611,28 +617,17 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
while ((child = RB_LEFT(elm, field)) != NULL); \
child = RB_RIGHT(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_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); \
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); \
if (child != NULL) \
RB_SET_PARENT(child, parent, field); \
- else if (!red && parent != NULL) \
- name##_RB_REMOVE_COLOR(head, parent); \
+ if (parent != NULL) \
+ name##_RB_REMOVE_COLOR(head, parent, child); \
while (parent != NULL) { \
RB_AUGMENT(parent); \
parent = RB_PARENT(parent, field); \