Page MenuHomeFreeBSD
Files F140761379

D36509.id110425.diff
No OneTemporary
Actions

D36509.id110425.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,42 @@
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(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,9 +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 *, struct type *)
+ attr struct type *name##_RB_INSERT_COLOR(struct name *, \
+ 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,6 +477,10 @@
#ifdef _RB_DIAGNOSTIC
#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) \
{ \
@@ -485,7 +497,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_CHECK(elm)) \
return (-1); \
return (left_rank); \
}
@@ -494,7 +507,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 *elm) \
{ \
/* \
@@ -507,7 +520,7 @@
* uninitialized 'child', and a later iteration can only happen \
* when a value has been assigned to 'child' in the previous \
* one. \
- */ \
+ */ \
struct type *child, *child_up, *gpar, *parent; \
__uintptr_t elmdir, sibdir; \
\
@@ -519,7 +532,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 */ \
@@ -585,10 +598,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); \
} \
+ return (NULL); \
}
#ifndef RB_STRICT_HST
@@ -603,7 +617,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) \
{ \
@@ -617,7 +631,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 */ \
@@ -627,7 +641,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 */ \
@@ -710,11 +724,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) \
@@ -747,12 +769,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); \
}
@@ -778,8 +806,10 @@
} \
RB_SET(elm, parent, field); \
*tmpp = elm; \
- name##_RB_INSERT_COLOR(head, elm); \
- RB_UPDATE_AUGMENT(elm, field); \
+ tmp = name##_RB_INSERT_COLOR(head, elm); \
+ _RB_AUGMENT_WALK(elm, tmp, field); \
+ if (tmp != NULL) \
+ RB_AUGMENT_CHECK(tmp); \
return (NULL); \
}

File Metadata

Mime Type
text/plain
Expires
Sun, Dec 28, 6:25 PM (1 h, 29 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27339403
Default Alt Text
D36509.id110425.diff (9 KB)

Event Timeline