]> www.infradead.org Git - users/jedix/linux-maple.git/commit
lib/interval_tree: skip the check before go to the right subtree
authorWei Yang <richard.weiyang@gmail.com>
Mon, 10 Mar 2025 07:49:37 +0000 (07:49 +0000)
committerAndrew Morton <akpm@linux-foundation.org>
Mon, 17 Mar 2025 19:17:01 +0000 (12:17 -0700)
commit19811285784f7f3d4abaa6e94623f2e7d10219d0
treefb3a2f42527b03fd27a9e43e14fd5661e033fce0
parentccaf3efceefc2c3abc6c23277d5a93238efa5c58
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  right

So 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.

Link: https://lkml.kernel.org/r/20250310074938.26756-7-richard.weiyang@gmail.com
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Michel Lespinasse <michel@lespinasse.org>
Cc: Jason Gunthorpe <jgg@nvidia.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
include/linux/interval_tree_generic.h