aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--arch/x86/mm/pat_rbtree.c37
-rw-r--r--include/linux/rbtree.h30
-rw-r--r--lib/rbtree_test.c34
3 files changed, 34 insertions, 67 deletions
diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index 7e1515bd4770..4d116959075d 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -69,41 +69,8 @@ static u64 compute_subtree_max_end(struct memtype *data)
69 return max_end; 69 return max_end;
70} 70}
71 71
72/* Update 'subtree_max_end' for node and its parents */ 72RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
73static void memtype_rb_propagate_cb(struct rb_node *node, struct rb_node *stop) 73 u64, subtree_max_end, compute_subtree_max_end)
74{
75 while (node != stop) {
76 struct memtype *data = container_of(node, struct memtype, rb);
77 u64 subtree_max_end = compute_subtree_max_end(data);
78 if (data->subtree_max_end == subtree_max_end)
79 break;
80 data->subtree_max_end = subtree_max_end;
81 node = rb_parent(&data->rb);
82 }
83}
84
85static void memtype_rb_copy_cb(struct rb_node *old, struct rb_node *new)
86{
87 struct memtype *old_data = container_of(old, struct memtype, rb);
88 struct memtype *new_data = container_of(new, struct memtype, rb);
89
90 new_data->subtree_max_end = old_data->subtree_max_end;
91}
92
93/* Update 'subtree_max_end' after tree rotation. old and new are the
94 * former and current subtree roots */
95static void memtype_rb_rotate_cb(struct rb_node *old, struct rb_node *new)
96{
97 struct memtype *old_data = container_of(old, struct memtype, rb);
98 struct memtype *new_data = container_of(new, struct memtype, rb);
99
100 new_data->subtree_max_end = old_data->subtree_max_end;
101 old_data->subtree_max_end = compute_subtree_max_end(old_data);
102}
103
104static const struct rb_augment_callbacks memtype_rb_augment_cb = {
105 memtype_rb_propagate_cb, memtype_rb_copy_cb, memtype_rb_rotate_cb
106};
107 74
108/* Find the first (lowest start addr) overlapping range from rb tree */ 75/* Find the first (lowest start addr) overlapping range from rb tree */
109static struct memtype *memtype_rb_lowest_match(struct rb_root *root, 76static struct memtype *memtype_rb_lowest_match(struct rb_root *root,
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 4ace31b33380..8d1e83b1c87b 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -79,6 +79,36 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root,
79 __rb_insert_augmented(node, root, augment->rotate); 79 __rb_insert_augmented(node, root, augment->rotate);
80} 80}
81 81
82#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
83 rbtype, rbaugmented, rbcompute) \
84static void rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
85{ \
86 while (rb != stop) { \
87 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
88 rbtype augmented = rbcompute(node); \
89 if (node->rbaugmented == augmented) \
90 break; \
91 node->rbaugmented = augmented; \
92 rb = rb_parent(&node->rbfield); \
93 } \
94} \
95static void rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
96{ \
97 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
98 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
99 new->rbaugmented = old->rbaugmented; \
100} \
101static void rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
102{ \
103 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
104 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
105 new->rbaugmented = old->rbaugmented; \
106 old->rbaugmented = rbcompute(old); \
107} \
108rbstatic const struct rb_augment_callbacks rbname = { \
109 rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
110};
111
82 112
83/* Find logical next and previous nodes in a tree */ 113/* Find logical next and previous nodes in a tree */
84extern struct rb_node *rb_next(const struct rb_node *); 114extern struct rb_node *rb_next(const struct rb_node *);
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index e28345df09bf..b20e99969b0f 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -61,38 +61,8 @@ static inline u32 augment_recompute(struct test_node *node)
61 return max; 61 return max;
62} 62}
63 63
64static void augment_propagate(struct rb_node *rb, struct rb_node *stop) 64RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
65{ 65 u32, augmented, augment_recompute)
66 while (rb != stop) {
67 struct test_node *node = rb_entry(rb, struct test_node, rb);
68 u32 augmented = augment_recompute(node);
69 if (node->augmented == augmented)
70 break;
71 node->augmented = augmented;
72 rb = rb_parent(&node->rb);
73 }
74}
75
76static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
77{
78 struct test_node *old = rb_entry(rb_old, struct test_node, rb);
79 struct test_node *new = rb_entry(rb_new, struct test_node, rb);
80 new->augmented = old->augmented;
81}
82
83static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
84{
85 struct test_node *old = rb_entry(rb_old, struct test_node, rb);
86 struct test_node *new = rb_entry(rb_new, struct test_node, rb);
87
88 /* Rotation doesn't change subtree's augmented value */
89 new->augmented = old->augmented;
90 old->augmented = augment_recompute(old);
91}
92
93static const struct rb_augment_callbacks augment_callbacks = {
94 augment_propagate, augment_copy, augment_rotate
95};
96 66
97static void insert_augmented(struct test_node *node, struct rb_root *root) 67static void insert_augmented(struct test_node *node, struct rb_root *root)
98{ 68{
generated by cgit v1.2.2 (git 2.25.0) at 2025-02-27 19:21:37 -0500