On Fri, Jun 28, 2019 at 05:49:52PM -0700, Michel Lespinasse wrote:
> - Change the definition of the RBCOMPUTE function. The propagate
> callback repeatedly calls RBCOMPUTE as it moves from leaf to root.
> it wants to stop recomputing once the augmented subtree information
> doesn't change. This was previously checked using the == operator,
> but that only works when the augmented subtree information is a
> scalar field. This commit modifies the RBCOMPUTE function so that
> it now sets the augmented subtree information instead of returning it,
> and returns a boolean value indicating if the propagate callback
> should stop.
>
> - Reorder the RB_DECLARE_CALLBACKS macro arguments, following the
> style of the INTERVAL_TREE_DEFINE macro, so that RBSTATIC and RBNAME
> are passed last.
>
> The generated code should not change when the RBCOMPUTE function is inlined,
> which is the typical / intended case.
This seems something that shoud (:-) be easy to verify; no reason to be
uncertain about this. Either it does or does not change generated code.
> The motivation for this change is that I want to introduce augmented rbtree
> uses where the augmented data for the subtree is a struct instead of a scalar.
>
> Signed-off-by: Michel Lespinasse <wal...@google.com>
> @@ -66,11 +66,14 @@ static u64 compute_subtree_max_end(struct memtype *data)
> if (child_max_end > max_end)
> max_end = child_max_end;
>
> - return max_end;
> + if (exit && data->subtree_max_end == max_end)
> + return true;
> + data->subtree_max_end = max_end;
> + return false;
> }
> @@ -35,11 +35,14 @@ compute_subtree_last(struct drbd_interval *node)
> if (right > max)
> max = right;
> }
> - return max;
> + if (exit && node->end == max)
> + return true;
> + node->end = max;
> + return false;
> }
> @@ -57,11 +58,15 @@ static inline ITTYPE ITPREFIX ##
> _compute_subtree_last(ITSTRUCT *node) \
> if (max < subtree_last) \
> max = subtree_last; \
> } \
> - return max; \
> + if (exit && node->ITSUBTREE == max) \
> + return true; \
> + node->ITSUBTREE = max; \
> + return false; \
> } \
> @@ -91,11 +91,14 @@ static inline u32 augment_recompute(struct test_node
> *node)
> if (max < child_augmented)
> max = child_augmented;
> }
> - return max;
> + if (exit && node->augmented == max)
> + return true;
> + node->augmented = max;
> + return false;
> }
> @@ -318,7 +318,10 @@ static long vma_compute_subtree_gap(struct
> vm_area_struct *vma)
> if (subtree_gap > max)
> max = subtree_gap;
> }
> - return max;
> + if (exit && vma->rb_subtree_gap == max)
> + return true;
> + vma->rb_subtree_gap = max;
> + return false;
> }
And that is _really_ unfortunate, as in 5 copies of exactly the same
logic sucks.
Can't we have a helper macro that converts an old (scalar) style compute
into a new style compute and avoid this unfortunate and error prone
copy/pasta ?
Something like:
#define RBCOMPUTE_SCALAR(_comp, _rb _exit)
({
RBSTRUCT *node = rb_entry((_rb), RBSTRUCT, RBFIELD);
RBTYPE augmented = _comp(node);
bool ret = true;
if (!((_exit) && node->RBAUGMENTED == augmented)) {
node->RBAUGMENTED = augmented;
ret = false;
}
ret;
})
