Page MenuHomeFreeBSD
Files F133324791

D36509.id110499.diff
No OneTemporary
Actions

D36509.id110499.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
@@ -100,6 +100,7 @@
.Nm RB_REMOVE ,
.Nm RB_REINSERT ,
.Nm RB_AUGMENT
+.Nm RB_AUGMENT_CHECK,
.Nm RB_UPDATE_AUGMENT
.Nd "implementations of splay and rank-balanced (wavl) trees"
.Sh SYNOPSIS
@@ -197,6 +198,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"
.Ft "void"
.Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm"
.Sh DESCRIPTION
@@ -620,6 +623,21 @@
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.
+.Pp
+The
.Fn RB_UPDATE_AUGMENT
macro updates augmentation data of the element
.Fa elm
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,41 @@
return (0);
}
-static void
+/*
+ * Update augmentation data based on data from children.
+ * Return true if and only if the update changes the augmentation data.
+ */
+static bool
iommu_gas_augment_entry(struct iommu_map_entry *entry)
{
struct iommu_map_entry *child;
- iommu_gaddr_t free_down;
+ iommu_gaddr_t bound, delta, free_down;
free_down = 0;
+ bound = entry->start;
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);
- entry->first = child->first;
- } else
- entry->first = entry->start;
-
+ free_down = MAX(child->free_down, bound - child->last);
+ bound = child->first;
+ }
+ delta = bound - entry->first;
+ entry->first = bound;
+ bound = entry->end;
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);
- entry->last = child->last;
- } else
- entry->last = entry->end;
+ free_down = MAX(free_down, child->first - bound);
+ bound = child->last;
+ }
+ delta += entry->last - bound;
+ if (delta == 0)
+ delta = entry->free_down - free_down;
+ entry->last = bound;
entry->free_down = free_down;
+
+ /*
+ * Return true either if the value of last-first changed,
+ * or if free_down changed.
+ */
+ return (delta != 0);
}
RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry,
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -356,19 +356,26 @@
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
} while (/*CONSTCOND*/ 0)
+
/*
- * 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_UPDATE_AUGMENT(elm, field) do { \
__typeof(elm) rb_update_tmp = (elm); \
- do { \
- RB_AUGMENT(rb_update_tmp); \
- } while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \
+ while (RB_AUGMENT_CHECK(rb_update_tmp) && \
+ (rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \
} while (0)
#define RB_SWAP_CHILD(head, par, out, in, field) do { \
@@ -426,10 +433,10 @@
#define RB_PROTOTYPE_RANK(name, type, attr)
#endif
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
- attr void name##_RB_INSERT_COLOR(struct name *, \
+ attr struct type *name##_RB_INSERT_COLOR(struct name *, \
struct type *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
- attr void name##_RB_REMOVE_COLOR(struct name *, \
+ attr struct type *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 *)
@@ -469,7 +476,16 @@
RB_GENERATE_REINSERT(name, type, field, cmp, attr)
#ifdef _RB_DIAGNOSTIC
+#ifndef RB_AUGMENT
+#define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x)
+#else
+#define _RB_AUGMENT_VERIFY(x) false
+#endif
#define RB_GENERATE_RANK(name, type, field, attr) \
+/* \
+ * Return the rank of the subtree rooted at elm, or -1 if the subtree \
+ * is not rank-balanced, or has inconsistent augmentation data.
+ */ \
attr int \
name##_RB_RANK(struct type *elm) \
{ \
@@ -486,7 +502,8 @@
right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) + \
name##_RB_RANK(right); \
if (left_rank != right_rank || \
- (left_rank == 2 && left == NULL && right == NULL)) \
+ (left_rank == 2 && left == NULL && right == NULL) || \
+ _RB_AUGMENT_VERIFY(elm)) \
return (-1); \
return (left_rank); \
}
@@ -495,7 +512,7 @@
#endif
#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
-attr void \
+attr struct type * \
name##_RB_INSERT_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
@@ -520,7 +537,7 @@
if (_RB_BITS(gpar) & elmdir) { \
/* shorten the parent-elm edge to rebalance */ \
_RB_BITSUP(parent, field) ^= elmdir; \
- return; \
+ return (NULL); \
} \
sibdir = elmdir ^ _RB_LR; \
/* the other edge must change length */ \
@@ -586,10 +603,11 @@
_RB_UP(child, field) = gpar; \
RB_SWAP_CHILD(head, gpar, parent, child, field); \
if (elm != child) \
- RB_AUGMENT(elm); \
- RB_AUGMENT(parent); \
- break; \
+ RB_AUGMENT_CHECK(elm); \
+ RB_AUGMENT_CHECK(parent); \
+ return (child); \
} while ((parent = gpar) != NULL); \
+ return (NULL); \
}
#ifndef RB_STRICT_HST
@@ -604,7 +622,7 @@
#endif
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
-attr void \
+attr struct type * \
name##_RB_REMOVE_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
@@ -618,7 +636,7 @@
_RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \
elm = parent; \
if ((parent = _RB_UP(elm, field)) == NULL) \
- return; \
+ return (NULL); \
} \
do { \
/* the rank of the tree rooted at elm shrank */ \
@@ -628,7 +646,7 @@
if (_RB_BITS(gpar) & elmdir) { \
/* lengthen the parent-elm edge to rebalance */ \
_RB_UP(parent, field) = gpar; \
- return; \
+ return (NULL); \
} \
if (_RB_BITS(gpar) & _RB_LR) { \
/* shorten other edge, retry from parent */ \
@@ -711,11 +729,19 @@
RB_SET_PARENT(elm, gpar, field); \
RB_SWAP_CHILD(head, gpar, parent, elm, field); \
if (sib != elm) \
- RB_AUGMENT(sib); \
- break; \
+ RB_AUGMENT_CHECK(sib); \
+ return (parent); \
} while (elm = parent, (parent = gpar) != NULL); \
+ return (NULL); \
}
+#define _RB_AUGMENT_WALK(elm, match, field) \
+do { \
+ if (match == elm) \
+ match = NULL; \
+} while (RB_AUGMENT_CHECK(elm) && \
+ (elm = RB_PARENT(elm, field)) != NULL)
+
#define RB_GENERATE_REMOVE(name, type, field, attr) \
attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *out) \
@@ -748,12 +774,18 @@
if (child != NULL) \
_RB_UP(child, field) = parent; \
if (parent != NULL) { \
- name##_RB_REMOVE_COLOR(head, parent, child); \
+ opar = name##_RB_REMOVE_COLOR(head, parent, child); \
/* if rotation has made 'parent' the root of the same \
* subtree as before, don't re-augment it. */ \
- if (parent == in && RB_LEFT(parent, field) == NULL) \
+ if (parent == in && RB_LEFT(parent, field) == NULL) { \
+ opar = NULL; \
parent = RB_PARENT(parent, field); \
- RB_UPDATE_AUGMENT(parent, field); \
+ } \
+ _RB_AUGMENT_WALK(parent, opar, field); \
+ if (opar != NULL) { \
+ RB_AUGMENT_CHECK(opar); \
+ RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \
+ } \
} \
return (out); \
}
@@ -780,8 +812,10 @@
RB_SET(elm, parent, field); \
*tmpp = elm; \
if (parent != NULL) \
- name##_RB_INSERT_COLOR(head, parent, elm); \
- RB_UPDATE_AUGMENT(elm, field); \
+ tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
+ _RB_AUGMENT_WALK(elm, tmp, field); \
+ if (tmp != NULL) \
+ RB_AUGMENT_CHECK(tmp); \
return (NULL); \
}

File Metadata

Mime Type
text/plain
Expires
Sat, Oct 25, 10:48 PM (4 h, 45 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
24195884
Default Alt Text
D36509.id110499.diff (9 KB)

Event Timeline