lib/interval_tree: skip the check before go to the right subtree
PATCH 1/1 lib/interval_tree: skip the check before go to the right subtree
The interval_tree_subtree_search() holds the loop invariant:
start <= node->ITSUBTREE
Let's say we have a following tree:
node
/ \
left rightSo we know node->ITSUBTREE is contributed by one of the following:
* left->ITSUBTREE
* ITLAST(node)
* right->ITSUBTREE
When we come to the right node, we are sure the first two don't contribute to node->ITSUBTREE and it must be the right node does the job.
So skip the check before go to the right subtree.
--- include/linux/interval_tree_generic.h | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-)
include/linux/interval_tree_generic.h +2 -6
@@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \if (ITSTART (node) <= last) {/* Cond1 */ \if (start <=ITLAST (node))/* Cond2 */ \return node;/* node is leftmost match */ \ -if (node->ITRB.rb_right) { \ - node =rb_entry (node->ITRB.rb_right, \ -ITSTRUCT ,ITRB ); \ -if (start <= node->ITSUBTREE) \ -continue ; \ - } \ + node =rb_entry (node->ITRB.rb_right,ITSTRUCT ,ITRB ); \ +continue ; \ } \return NULL ;/* No match */ \ } \
Signature · 1 line
2.34.1
Quoted 1 line · Wei Yang
So skip the check before go to the right subtree.
what testing have you done?
Quoted 4 lines · Matthew Wilcox
Quoted 1 line · Wei Yang
So skip the check before go to the right subtree.
what testing have you done?
I did kernel build test for about 50+ rounds on top of recent mmunstable tree.
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 7 lines · Wei Yang
Quoted 4 lines · Matthew Wilcox
Quoted 1 line · Wei Yang
So skip the check before go to the right subtree.
what testing have you done?
I did kernel build test for about 50+ rounds on top of recent mmunstable tree.
And did anything improve?