RFR: 8354433: Assert in AbstractRBTree::visit_range_in_order(const K& from, const K& to, F f) is wrong

[Johan Sjölen]

On Tue, 15 Apr 2025 12:03:39 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

> There was an assert in `AbstractRBTree::visit_range_in_order` that could incorrectly trigger when:
> - The range contains no nodes, **but**
> - Nodes exist **outside** that range.
> 
> The assert checked `from <= to` indirectly via `from <= start <= to`, but `start` could be valid outside that range.
> 
> To fix this, I added the ability to supply a direct key comparison for intrusive trees to the `COMPARATOR` template. This already existed in the non-intrusive RBTree, and works the same as the other extra `cmp` function.
> 
> Additionally, I found another wrong assert in `replace_at_cursor` that is also fixed here.

src/hotspot/share/utilities/rbTree.inline.hpp line 553:

> 551: 
> 552:   if (new_node->is_left_child()) {
> 553:     assert(cmp((const NodeType*)new_node, (const NodeType*)new_node->parent()), "new node not < parent");

`const_cast` instead?

test/hotspot/gtest/utilities/test_rbtree.cpp line 345:

> 343:     rbtree.visit_range_in_order(7, 7, [&](const Node* x) {
> 344:       EXPECT_TRUE(false) << "Range should not visit nodes";
> 345:     });

Use `FAIL()` instead of `EXPECT_TRUE`. Why not an array of test cases?

```c++
int test_cases[][] = {{0,1}, {1,1}};
for test_case in test_cases ...

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/24658#discussion_r2058537560
PR Review Comment: https://git.openjdk.org/jdk/pull/24658#discussion_r2058541593