diff options
Diffstat (limited to 'include/linux/rbtree_augmented.h')
| -rw-r--r-- | include/linux/rbtree_augmented.h | 201 |
1 files changed, 143 insertions, 58 deletions
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h index d2fa1c41bfd2..b9fc1be86ae3 100644 --- a/include/linux/rbtree_augmented.h +++ b/include/linux/rbtree_augmented.h @@ -15,6 +15,8 @@ #include <linux/compiler.h> #include <linux/rbtree.h> #include <linux/rcupdate.h> +#include <linux/args.h> +#include <linux/minmax.h> /* * Please note - only struct rb_augment_callbacks and the prototypes for @@ -28,6 +30,7 @@ struct rb_augment_callbacks { void (*propagate)(struct rb_node *node, struct rb_node *stop); void (*copy)(struct rb_node *old, struct rb_node *new); void (*rotate)(struct rb_node *old, struct rb_node *new); + void (*merge)(struct rb_node *node, struct rb_node *new); }; extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, @@ -60,6 +63,12 @@ rb_insert_augmented_cached(struct rb_node *node, rb_insert_augmented(node, &root->rb_root, augment); } +/* + * Insert @node into the leftmost cached augmented tree @tree. + * + * The augmented data of @node must already describe @node alone; it is + * merged into every ancestor on the way down through augment->merge(). + */ static __always_inline struct rb_node * rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree, bool (*less)(struct rb_node *, const struct rb_node *), @@ -71,6 +80,7 @@ rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree, while (*link) { parent = *link; + augment->merge(parent, node); if (less(node, parent)) { link = &parent->rb_left; } else { @@ -80,12 +90,108 @@ rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree, } rb_link_node(node, parent, link); - augment->propagate(parent, NULL); /* suboptimal */ rb_insert_augmented_cached(node, tree, leftmost, augment); return leftmost ? node : NULL; } +#define RB_FOR_EACH_1(what, RBNAME, RBSTRUCT, RBFIELD, x) \ + what(1, RBNAME, RBSTRUCT, RBFIELD, x) + +#define RB_FOR_EACH_2(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(2, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_1(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH_3(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(3, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_2(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH_4(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(4, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_3(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH_5(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(5, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_4(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH_6(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(6, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_5(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH_7(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(7, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_6(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH_8(what, RBNAME, RBSTRUCT, RBFIELD, x, ...) \ + what(8, RBNAME, RBSTRUCT, RBFIELD, x) \ + RB_FOR_EACH_7(what, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +#define RB_FOR_EACH(action, RBNAME, RBSTRUCT, RBFIELD, ...) \ + CONCATENATE(RB_FOR_EACH_, COUNT_ARGS(__VA_ARGS__)) \ + (action, RBNAME, RBSTRUCT, RBFIELD, __VA_ARGS__) + +/* + * One augmented field: @val is the node's own contribution (a member for + * RB_AUG(), a function of the node for RB_AUG_FUNC()), @aug the member + * holding the aggregate over the subtree, and @fold(a, b) combines two + * aggregates: min, max, a sum, ... It must be commutative and associative. + */ +#define RB_AUG_FUNC(val, aug, fold) (val(s), aug, fold) +#define RB_AUG(val, aug, fold) (s->val, aug, fold) +#define RB_UNPACK(...) __VA_ARGS__ + +#define __RB_INST(n, RBNAME, RBSTRUCT, RBFIELD, val, aug, fold) \ +static inline void \ +RBNAME ## _copy_ ## n(RBSTRUCT *old, RBSTRUCT *new) \ +{ \ + new->aug = old->aug; \ +} \ +static inline bool \ +RBNAME ## _compute_ ## n(RBSTRUCT *s, bool exit) \ +{ \ + TYPEOF_UNQUAL(s->aug) _old_aug = s->aug; \ + TYPEOF_UNQUAL(s->aug) _val = val; \ + struct rb_node *_node = &s->RBFIELD; \ + if (_node->rb_right) { \ + RBSTRUCT *_c = container_of(_node->rb_right, typeof(*s), RBFIELD); \ + _val = fold(_val, _c->aug); \ + } \ + if (_node->rb_left) { \ + RBSTRUCT *_c = container_of(_node->rb_left, typeof(*s), RBFIELD); \ + _val = fold(_val, _c->aug); \ + } \ + if (exit && _old_aug == _val) \ + return true; \ + s->aug = _val; \ + return false; \ +} +#define _RB_INST(n, RBNAME, RBSTRUCT, RBFIELD, args) \ + __RB_INST(n, RBNAME, RBSTRUCT, RBFIELD, args) +#define RB_INST(n, RBNAME, RBSTRUCT, RBFIELD, x) \ + _RB_INST(n, RBNAME, RBSTRUCT, RBFIELD, RB_UNPACK x) + +#define __RB_COPY(n, RBNAME, RBSTRUCT, RBFIELD, val, aug, fold) \ + RBNAME ## _copy_ ## n(old, new); +#define _RB_COPY(n, RBNAME, RBSTRUCT, RBFIELD, args) \ + __RB_COPY(n, RBNAME, RBSTRUCT, RBFIELD, args) +#define RB_COPY(n, RBNAME, RBSTRUCT, RBFIELD, x) \ + _RB_COPY(n, RBNAME, RBSTRUCT, RBFIELD, RB_UNPACK x) + +#define __RB_COMPUTE(n, RBNAME, RBSTRUCT, RBFIELD, val, aug, fold) \ + ret &= RBNAME ## _compute_ ## n(node, exit); +#define _RB_COMPUTE(n, RBNAME, RBSTRUCT, RBFIELD, args) \ + __RB_COMPUTE(n, RBNAME, RBSTRUCT, RBFIELD, args) +#define RB_COMPUTE(n, RBNAME, RBSTRUCT, RBFIELD, x) \ + _RB_COMPUTE(n, RBNAME, RBSTRUCT, RBFIELD, RB_UNPACK x) + +/* fold @new, about to become a descendant of @node, into @node */ +#define __RB_MERGE(n, RBNAME, RBSTRUCT, RBFIELD, val, aug, fold) \ + node->aug = fold(node->aug, new->aug); +#define _RB_MERGE(n, RBNAME, RBSTRUCT, RBFIELD, args) \ + __RB_MERGE(n, RBNAME, RBSTRUCT, RBFIELD, args) +#define RB_MERGE(n, RBNAME, RBSTRUCT, RBFIELD, x) \ + _RB_MERGE(n, RBNAME, RBSTRUCT, RBFIELD, RB_UNPACK x) + /* * Template for declaring augmented rbtree callbacks (generic multi fields) * @@ -93,18 +199,29 @@ rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree, * RBNAME: name of the rb_augment_callbacks structure * RBSTRUCT: struct type of the tree nodes * RBFIELD: name of struct rb_node field within RBSTRUCT - * RBCOPY: name of function that copies the RBAUGMENTED datas - * RBCOMPUTE: name of function that recomputes the RBAUGMENTED datas + * RBAUG...: list of RB_AUG() describing the augmented data */ - -#define RB_DECLARE_CALLBACKS_MULTI(RBSTATIC, RBNAME, \ - RBSTRUCT, RBFIELD, RBCOPY, RBCOMPUTE) \ +#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \ + RBSTRUCT, RBFIELD, RBAUG...) \ +RB_FOR_EACH(RB_INST, RBNAME, RBSTRUCT, RBFIELD, RBAUG) \ +static inline void \ +RBNAME ## __copy(RBSTRUCT *old, RBSTRUCT *new) \ +{ \ + RB_FOR_EACH(RB_COPY, RBNAME, RBSTRUCT, RBFIELD, RBAUG); \ +} \ +static inline bool \ +RBNAME ## __compute(RBSTRUCT *node, bool exit) \ +{ \ + bool ret = true; \ + RB_FOR_EACH(RB_COMPUTE, RBNAME, RBSTRUCT, RBFIELD, RBAUG); \ + return ret; \ +} \ static inline void \ RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop) \ { \ while (rb != stop) { \ RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \ - if (RBCOMPUTE(node, true)) \ + if (RBNAME ## __compute(node, true)) \ break; \ rb = rb_parent(&node->RBFIELD); \ } \ @@ -114,44 +231,31 @@ RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ { \ RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \ RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \ - RBCOPY(new, old); \ + RBNAME ## __copy(old, new); \ } \ static void \ RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ { \ RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \ RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \ - RBCOPY(new, old); \ - RBCOMPUTE(old, false); \ + RBNAME ## __copy(old, new); \ + RBNAME ## __compute(old, false); \ +} \ +static inline void \ +RBNAME ## _merge(struct rb_node *rb, struct rb_node *rb_new) \ +{ \ + RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \ + RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \ + RB_FOR_EACH(RB_MERGE, RBNAME, RBSTRUCT, RBFIELD, RBAUG); \ } \ RBSTATIC const struct rb_augment_callbacks RBNAME = { \ .propagate = RBNAME ## _propagate, \ .copy = RBNAME ## _copy, \ - .rotate = RBNAME ## _rotate \ + .rotate = RBNAME ## _rotate, \ + .merge = RBNAME ## _merge \ }; /* - * Template for declaring augmented rbtree callbacks (generic single field) - * - * RBSTATIC: 'static' or empty - * RBNAME: name of the rb_augment_callbacks structure - * RBSTRUCT: struct type of the tree nodes - * RBFIELD: name of struct rb_node field within RBSTRUCT - * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree - * RBCOMPUTE: name of function that recomputes the RBAUGMENTED data - */ - -#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \ - RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \ -static inline void \ -RBNAME ## _copy_single(RBSTRUCT *new, RBSTRUCT *old) \ -{ \ - new->RBAUGMENTED = old->RBAUGMENTED; \ -} \ -RB_DECLARE_CALLBACKS_MULTI(RBSTATIC, RBNAME, \ - RBSTRUCT, RBFIELD, RBNAME ## _copy_single, RBCOMPUTE) - -/* * Template for declaring augmented rbtree callbacks, * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes. * @@ -159,34 +263,15 @@ RB_DECLARE_CALLBACKS_MULTI(RBSTATIC, RBNAME, \ * RBNAME: name of the rb_augment_callbacks structure * RBSTRUCT: struct type of the tree nodes * RBFIELD: name of struct rb_node field within RBSTRUCT - * RBTYPE: type of the RBAUGMENTED field - * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree - * RBCOMPUTE: name of function that returns the per-node RBTYPE scalar + * RBTYPE: type of the RBAUGMENTED field -- unused, assumed typeof(RBAUGMENTED) + * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree + * RBVALUE: name of function that returns the per-node RBTYPE scalar */ -#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \ - RBTYPE, RBAUGMENTED, RBCOMPUTE) \ -static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit) \ -{ \ - RBSTRUCT *child; \ - RBTYPE max = RBCOMPUTE(node); \ - if (node->RBFIELD.rb_left) { \ - child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \ - if (child->RBAUGMENTED > max) \ - max = child->RBAUGMENTED; \ - } \ - if (node->RBFIELD.rb_right) { \ - child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \ - if (child->RBAUGMENTED > max) \ - max = child->RBAUGMENTED; \ - } \ - if (exit && node->RBAUGMENTED == max) \ - return true; \ - node->RBAUGMENTED = max; \ - return false; \ -} \ -RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \ - RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max) +#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \ + RBTYPE, RBAUGMENTED, RBVALUE) \ +RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \ + RB_AUG_FUNC(RBVALUE, RBAUGMENTED, max)) #define RB_RED 0 |