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 __FBSDID("$FreeBSD$"); -#define RB_AUGMENT(entry) iommu_gas_augment_entry(entry) +#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry) #include #include @@ -139,27 +139,35 @@ 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; - 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); + free_down = MAX(entry->start - child->last, child->free_down); + changed = entry->first != child->first; entry->first = child->first; - } else + } else { + free_down = 0; 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); + free_down = MAX(MAX(child->free_down, + child->first - entry->end), free_down); + changed = changed || entry->last != child->last; entry->last = child->last; - } else + } else { entry->last = entry->end; + changed = true; + } + changed = 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); \ } @@ -627,12 +637,11 @@ RB_SWAP_CHILD(head, old, elm, field); \ if (child != NULL) \ RB_SET_PARENT(child, parent, field); \ + elm = parent; \ + while (elm != NULL && RB_AUGMENT_CHECK(elm)) \ + elm = RB_PARENT(elm, field); \ if (parent != NULL) \ name##_RB_REMOVE_COLOR(head, parent, child); \ - while (parent != NULL) { \ - RB_AUGMENT(parent); \ - parent = RB_PARENT(parent, field); \ - } \ return (old); \ } @@ -662,11 +671,10 @@ RB_LEFT(parent, field) = elm; \ else \ RB_RIGHT(parent, field) = elm; \ + parent = elm; \ + while (parent != NULL && RB_AUGMENT_CHECK(parent)) \ + parent = RB_PARENT(parent, field); \ name##_RB_INSERT_COLOR(head, elm); \ - while (elm != NULL) { \ - RB_AUGMENT(elm); \ - elm = RB_PARENT(elm, field); \ - } \ return (NULL); \ }