Page MenuHomeFreeBSD
Files F142228728

D35502.id107423.diff
No OneTemporary
Actions

D35502.id107423.diff
View Options

Index: share/man/man3/Makefile
===================================================================
--- share/man/man3/Makefile
+++ share/man/man3/Makefile
@@ -320,6 +320,7 @@
timeradd.3 timespecisset.3 \
timeradd.3 timespeccmp.3
MLINKS+= tree.3 RB_AUGMENT.3 \
+ tree.3 RB_AUGMENT_CHECK.3 \
tree.3 RB_EMPTY.3 \
tree.3 RB_ENTRY.3 \
tree.3 RB_FIND.3 \
Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ share/man/man3/tree.3
@@ -99,7 +99,8 @@
.Nm RB_INSERT ,
.Nm RB_REMOVE ,
.Nm RB_REINSERT ,
-.Nm RB_AUGMENT
+.Nm RB_AUGMENT ,
+.Nm RB_AUGMENT_CHECK
.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 "bool"
+.Fn RB_AUGMENT_CHECK NAME "struct TYPE *elm"
.Sh DESCRIPTION
These macros define data structures for different types of trees:
splay trees and rank-balanced (wavl) trees.
@@ -598,6 +601,21 @@
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_AUGMENT_CHECK
+macro updates augmentation data of the element
+.Fa elm
+in the tree.
+By default, does nothing and returns false.
+If RB_AUGMENT_CHECK is defined, 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 toward the top, until it returns false to indicate that it did
+not change the element and so working further up the tree would
+change nothing.
+It is typically used to maintain some associative accumulation of tree
+elements, such as sums, minima, maxima, and the like.
.Sh EXAMPLES
The following example demonstrates how to declare a rank-balanced tree
holding integers.
Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -31,7 +31,7 @@
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
-#define RB_AUGMENT(entry) iommu_gas_augment_entry(entry)
+#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry)
#include <sys/param.h>
#include <sys/systm.h>
@@ -139,27 +139,37 @@
return (0);
}
-static void
+static bool
iommu_gas_augment_entry(struct iommu_map_entry *entry)
{
struct iommu_map_entry *child;
iommu_gaddr_t free_down;
+ bool changed;
+ changed = false;
free_down = 0;
if ((child = RB_LEFT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, entry->start - child->last);
+ changed |= entry->first != child->first;
entry->first = child->first;
- } else
+ } else {
entry->first = entry->start;
+ changed = true;
+ }
if ((child = RB_RIGHT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, child->first - entry->end);
+ changed |= entry->last != child->last;
entry->last = child->last;
- } else
+ } else {
entry->last = entry->end;
+ changed = true;
+ }
+ changed |= entry->free_down != free_down;
entry->free_down = free_down;
+ return (changed);
}
RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry,
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -362,12 +362,20 @@
RB_RED_LEFT(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,
- * from the bottom up to the root, to update augmented node data.
+ * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of
+ * every modified subtree, from the bottom up to the root, to update augmented
+ * node data. RB_AUGMENT_CHECK returns true only when the update changes the
+ * node data, so that updating can be stopped short of the root when it returns
+ * false.
*/
+#ifndef RB_AUGMENT_CHECK
#ifndef RB_AUGMENT
-#define RB_AUGMENT(x) break
+#define RB_AUGMENT_CHECK(x) false
+#else
+#define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), true)
+#endif
#endif
#define RB_SWAP_CHILD(head, out, in, field) do { \
@@ -387,7 +395,7 @@
RB_SWAP_CHILD(head, elm, tmp, field); \
RB_LEFT(tmp, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
- RB_AUGMENT(elm); \
+ RB_AUGMENT_CHECK(elm); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
@@ -398,7 +406,7 @@
RB_SWAP_CHILD(head, elm, tmp, field); \
RB_RIGHT(tmp, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
- RB_AUGMENT(elm); \
+ RB_AUGMENT_CHECK(elm); \
} while (/*CONSTCOND*/ 0)
/* Generates prototypes and inline functions */
@@ -508,6 +516,7 @@
RB_ROTATE_LEFT(head, parent, elm, field); \
} \
RB_BITS(elm, field) &= ~RB_RED_MASK; \
+ RB_AUGMENT_CHECK(elm); \
break; \
} \
}
@@ -590,6 +599,7 @@
} \
RB_ROTATE_RIGHT(head, parent, sib, field); \
} \
+ RB_AUGMENT_CHECK(sib); \
break; \
} while ((parent = RB_PARENT(elm, field)) != NULL); \
}
@@ -629,10 +639,8 @@
RB_SET_PARENT(child, parent, field); \
if (parent != NULL) \
name##_RB_REMOVE_COLOR(head, parent, child); \
- while (parent != NULL) { \
- RB_AUGMENT(parent); \
+ while (parent != NULL && RB_AUGMENT_CHECK(parent)) \
parent = RB_PARENT(parent, field); \
- } \
return (old); \
}
@@ -663,10 +671,8 @@
else \
RB_RIGHT(parent, field) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
- while (elm != NULL) { \
- RB_AUGMENT(elm); \
+ while (elm != NULL && RB_AUGMENT_CHECK(elm)) \
elm = RB_PARENT(elm, field); \
- } \
return (NULL); \
}

File Metadata

Mime Type
text/plain
Expires
Sun, Jan 18, 1:20 PM (15 h, 36 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27710054
Default Alt Text
D35502.id107423.diff (5 KB)

Event Timeline