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,33 @@ 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; + iommu_gaddr_t bound, free_down; + bool changed; 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; + } + changed = entry->first != bound; + 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; + } + changed = changed || + (entry->last != bound) || (entry->free_down != free_down); + entry->last = bound; 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 @@ -364,11 +364,18 @@ 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 { \ @@ -388,7 +395,6 @@ RB_SWAP_CHILD(head, elm, tmp, field); \ RB_LEFT(tmp, field) = (elm); \ RB_SET_PARENT(elm, tmp, field); \ - RB_AUGMENT(elm); \ } while (/*CONSTCOND*/ 0) #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ @@ -399,7 +405,6 @@ RB_SWAP_CHILD(head, elm, tmp, field); \ RB_RIGHT(tmp, field) = (elm); \ RB_SET_PARENT(elm, tmp, field); \ - RB_AUGMENT(elm); \ } while (/*CONSTCOND*/ 0) /* Generates prototypes and inline functions */ @@ -419,9 +424,10 @@ RB_PROTOTYPE_MINMAX(name, type, attr); \ RB_PROTOTYPE_REINSERT(name, type, attr); #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 *) @@ -460,7 +466,7 @@ RB_GENERATE_REINSERT(name, type, field, cmp, attr) #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ -attr void \ +attr struct type * \ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ { \ /* \ @@ -473,13 +479,13 @@ * uninitialized 'child', and a later iteration can only happen \ * when a value has been assigned to 'child' in the previous \ * one. \ - */ \ + */ \ struct type *child, *parent; \ while ((parent = RB_PARENT(elm, field)) != NULL) { \ if (RB_LEFT(parent, field) == elm) { \ if (RB_RED_LEFT(parent, field)) { \ RB_FLIP_LEFT(parent, field); \ - return; \ + break; \ } \ RB_FLIP_RIGHT(parent, field); \ if (RB_RED_RIGHT(parent, field)) { \ @@ -490,19 +496,28 @@ if (!RB_RED_RIGHT(elm, field)) { \ /* coverity[uninit_use] */ \ RB_ROTATE_LEFT(head, elm, child, field);\ - if (RB_RED_RIGHT(child, field)) \ + switch (RB_BITS(child, field) & \ + RB_RED_MASK) { \ + case RB_RED_R: \ + RB_AUGMENT_CHECK(elm); \ RB_FLIP_LEFT(parent, field); \ - if (RB_RED_LEFT(child, field)) \ - RB_FLIP_ALL(elm, field); \ - else \ + /* FALLTHROUGH */ \ + default: \ RB_FLIP_LEFT(elm, field); \ + break; \ + case RB_RED_L: \ + RB_AUGMENT_CHECK(elm); \ + RB_FLIP_ALL(elm, field); \ + break; \ + } \ elm = child; \ } \ RB_ROTATE_RIGHT(head, parent, elm, field); \ + RB_AUGMENT_CHECK(parent); \ } else { \ if (RB_RED_RIGHT(parent, field)) { \ RB_FLIP_RIGHT(parent, field); \ - return; \ + break; \ } \ RB_FLIP_LEFT(parent, field); \ if (RB_RED_LEFT(parent, field)) { \ @@ -513,19 +528,29 @@ if (!RB_RED_LEFT(elm, field)) { \ /* coverity[uninit_use] */ \ RB_ROTATE_RIGHT(head, elm, child, field);\ - if (RB_RED_LEFT(child, field)) \ + switch (RB_BITS(child, field) & \ + RB_RED_MASK) { \ + case RB_RED_L: \ + RB_AUGMENT_CHECK(elm); \ RB_FLIP_RIGHT(parent, field); \ - if (RB_RED_RIGHT(child, field)) \ - RB_FLIP_ALL(elm, field); \ - else \ + /* FALLTHROUGH */ \ + default: \ RB_FLIP_RIGHT(elm, field); \ + break; \ + case RB_RED_R: \ + RB_AUGMENT_CHECK(elm); \ + RB_FLIP_ALL(elm, field); \ + break; \ + } \ elm = child; \ } \ RB_ROTATE_LEFT(head, parent, elm, field); \ + RB_AUGMENT_CHECK(parent); \ } \ RB_BITS(elm, field) &= ~RB_RED_MASK; \ - break; \ + return (elm); \ } \ + return (NULL); \ } #ifndef RB_STRICT_HST @@ -540,7 +565,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) \ { \ @@ -551,13 +576,13 @@ elm = parent; \ parent = RB_PARENT(elm, field); \ if (parent == NULL) \ - return; \ + return (NULL); \ } \ do { \ if (RB_LEFT(parent, field) == elm) { \ if (!RB_RED_LEFT(parent, field)) { \ RB_FLIP_LEFT(parent, field); \ - return; \ + break; \ } \ if (RB_RED_RIGHT(parent, field)) { \ RB_FLIP_RIGHT(parent, field); \ @@ -573,6 +598,7 @@ case RB_RED_R: \ elm = RB_LEFT(sib, field); \ RB_ROTATE_RIGHT(head, sib, elm, field); \ + RB_AUGMENT_CHECK(sib); \ if (RB_RED_LEFT(elm, field)) \ RB_FLIP_ALL(parent, field); \ else \ @@ -600,7 +626,7 @@ } else { \ if (!RB_RED_RIGHT(parent, field)) { \ RB_FLIP_RIGHT(parent, field); \ - return; \ + break; \ } \ if (RB_RED_LEFT(parent, field)) { \ RB_FLIP_LEFT(parent, field); \ @@ -616,6 +642,7 @@ case RB_RED_L: \ elm = RB_RIGHT(sib, field); \ RB_ROTATE_LEFT(head, sib, elm, field); \ + RB_AUGMENT_CHECK(sib); \ if (RB_RED_RIGHT(elm, field)) \ RB_FLIP_ALL(parent, field); \ else \ @@ -641,8 +668,9 @@ } \ RB_ROTATE_RIGHT(head, parent, sib, field); \ } \ - break; \ + return (parent); \ } while ((parent = RB_PARENT(elm, field)) != NULL); \ + return (NULL); \ } #define RB_GENERATE_REMOVE(name, type, field, attr) \ @@ -678,11 +706,23 @@ RB_SWAP_CHILD(head, old, elm, field); \ if (child != NULL) \ RB_SET_PARENT(child, parent, field); \ - if (parent != NULL) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - while (parent != NULL) { \ - RB_AUGMENT(parent); \ - parent = RB_PARENT(parent, field); \ + if (parent != NULL) { \ + struct type *rotator; \ + rotator = name##_RB_REMOVE_COLOR(head, parent, child); \ + if (rotator == parent && parent == elm && \ + RB_LEFT(parent, field) == NULL) { \ + rotator = NULL; \ + parent = RB_PARENT(parent, field); \ + } \ + do { \ + if (rotator == parent) \ + rotator = NULL; \ + } while (RB_AUGMENT_CHECK(parent) && \ + (parent = RB_PARENT(parent, field)) != NULL); \ + if (rotator != NULL) { \ + RB_AUGMENT_CHECK(rotator); \ + RB_AUGMENT_CHECK(RB_PARENT(rotator, field)); \ + } \ } \ return (old); \ } @@ -713,11 +753,14 @@ RB_LEFT(parent, field) = elm; \ else \ RB_RIGHT(parent, field) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - while (elm != NULL) { \ - RB_AUGMENT(elm); \ - elm = RB_PARENT(elm, field); \ - } \ + parent = name##_RB_INSERT_COLOR(head, elm); \ + do { \ + if (parent == elm) \ + parent = NULL; \ + } while (RB_AUGMENT_CHECK(elm) && \ + (elm = RB_PARENT(elm, field)) != NULL); \ + if (parent != NULL) \ + RB_AUGMENT_CHECK(parent); \ return (NULL); \ }