From dd7b99ffd1445d824bd351488c6f7b976f77fc9e Mon Sep 17 00:00:00 2001 From: Chi-Kuan Chiu <105687635+devarajabc@users.noreply.github.com> Date: Wed, 6 Aug 2025 05:43:12 +0800 Subject: Add O(1) early-out to eusing cached bounds (#2901) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Add a fast-path in rb_get() and rb_get_64() that checks the tree’s cached leftmost->start and rightmost->end bounds before calling find_addr(). If the query address lies outside the address bounds, we return 0 immediately, avoiding an unnecessary tree walk. This mirrors the idea used in jserv/rbtree’s rb_cached_contains(), using cached min/max to short-circuit lookups. Behavior is unchanged (both functions still return 0 when not found); only negative lookups become cheaper. Co-authored-by: Jim Huang --- src/tools/rbtree.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/src/tools/rbtree.c b/src/tools/rbtree.c index 6fa05cb4..7e193906 100644 --- a/src/tools/rbtree.c +++ b/src/tools/rbtree.c @@ -569,15 +569,19 @@ static rbnode *succ_node(rbnode *node) { } uint32_t rb_get(rbtree_t *tree, uintptr_t addr) { + if (tree->leftmost && addr < tree->leftmost->start) return 0; + if (tree->rightmost && addr > tree->rightmost->end) return 0; rbnode *node = find_addr(tree, addr); if (node) return node->data; - else return 0; + return 0; } uint64_t rb_get_64(rbtree_t *tree, uintptr_t addr) { + if (tree->leftmost && addr < tree->leftmost->start) return 0; + if (tree->rightmost && addr > tree->rightmost->end) return 0; rbnode *node = find_addr(tree, addr); if (node) return node->data; - else return 0; + return 0; } int rb_get_end(rbtree_t* tree, uintptr_t addr, uint32_t* val, uintptr_t* end) { -- cgit 1.4.1