Add O(1) early-out to eusing cached bounds (#2901)

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 <jserv@ccns.ncku.edu.tw>

1 files 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) {