Page MenuHomeFreeBSD
Files F111534620

D36010.id108825.diff
No OneTemporary
Actions

D36010.id108825.diff
View Options

diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3
--- a/share/man/man3/tree.3
+++ b/share/man/man3/tree.3
@@ -100,6 +100,7 @@
.Nm RB_REMOVE ,
.Nm RB_REINSERT ,
.Nm RB_AUGMENT
+.Nm RB_UPDATE_AUGMENT
.Nd "implementations of splay and rank-balanced (wavl) trees"
.Sh SYNOPSIS
.In sys/tree.h
@@ -196,6 +197,8 @@
.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
.Ft "void"
.Fn RB_AUGMENT NAME "struct TYPE *elm"
+.Ft "void"
+.Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm"
.Sh DESCRIPTION
These macros define data structures for different types of trees:
splay trees and rank-balanced (wavl) trees.
@@ -592,12 +595,25 @@
in the tree.
By default, it has no effect.
It is not meant to be invoked by the RB user.
-If RB_AUGMENT is defined by the RB user, then when an element is
-inserted or removed from the tree, it is invoked for every element in
-the tree that is the root of an altered subtree, working from the
-bottom of the tree up to the top.
+If
+.Fn RB_AUGMENT
+is defined by the RB user, then when an element is inserted or removed
+from the tree, it is invoked for every element in the tree that is the
+root of an altered subtree, working from the bottom of the tree up to
+the top.
It is typically used to maintain some associative accumulation of tree
elements, such as sums, minima, maxima, and the like.
+.Pp
+The
+.Fn RB_UPDATE_AUGMENT
+macro updates augmentation data of the element
+.Fa elm
+and its ancestors in the tree.
+If RB_AUGMENT is defined by the RB user, then when an element in the
+tree is changed, without changing the order of items in the tree,
+invoking this function on that element restores consistency of the
+augmentation state of the tree as if the element had been removed and
+inserted again.
.Sh EXAMPLES
The following example demonstrates how to declare a rank-balanced tree
holding integers.
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -371,6 +371,13 @@
#define RB_AUGMENT(x) break
#endif
+#define RB_UPDATE_AUGMENT(elm, field) do { \
+ __typeof(elm) tmp = (elm); \
+ do { \
+ RB_AUGMENT(tmp); \
+ } while ((tmp = RB_PARENT(tmp, field)) != NULL); \
+} while (0)
+
#define RB_SWAP_CHILD(head, out, in, field) do { \
if (RB_PARENT(out, field) == NULL) \
RB_ROOT(head) = (in); \
@@ -678,11 +685,9 @@
RB_SWAP_CHILD(head, old, elm, field); \
if (child != NULL) \
RB_SET_PARENT(child, parent, field); \
- if (parent != NULL) \
+ if (parent != NULL) { \
name##_RB_REMOVE_COLOR(head, parent, child); \
- while (parent != NULL) { \
- RB_AUGMENT(parent); \
- parent = RB_PARENT(parent, field); \
+ RB_UPDATE_AUGMENT(parent, field); \
} \
return (old); \
}
@@ -714,10 +719,7 @@
else \
RB_RIGHT(parent, field) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
- while (elm != NULL) { \
- RB_AUGMENT(elm); \
- elm = RB_PARENT(elm, field); \
- } \
+ RB_UPDATE_AUGMENT(elm, field); \
return (NULL); \
}

File Metadata

Mime Type
text/plain
Expires
Wed, Mar 5, 10:49 PM (3 h, 42 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
17003216
Default Alt Text
D36010.id108825.diff (2 KB)

Event Timeline