AbstractRBTree<K, NodeType, COMPARATOR>::visit_range_in_order(const K& from, const K& to, F f) assert does not work when the two keys are not in the tree but another key that is < than them is.
Adding the following test crashes in first 6 `visit_range_in_order` calls. The last 3 succeeds.
```
{
RBTreeInt rbtree;
using Node = RBTreeIntNode;
rbtree.upsert(2, 0);
rbtree.upsert(5, 0);
rbtree.visit_range_in_order(0, 0, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(0, 1, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(1, 1, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(3, 3, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(3, 4, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(4, 4, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(6,6, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(6, 7, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(7, 7, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
}
```
Because we are not provided the tools to compare the keys directly, we have to do some sort of best effort. The best I could come up with was:
```
if (start != nullptr) {
assert_leq(from, start);
if (cursor_start.found()) {
assert_geq(to, start);
}
if (cursor_end.found()) {
assert_leq(from, cursor_end.node());
}
if (!cursor_start.found() && !cursor_end.found()) {
assert((end == nullptr) || // to after right-most, from is not
(start == end) || // their next nodes should at least be ordered,
(cmp(start, end)), // start <= end, from <= to may still be false,
// but we do not have the tools too check.
"expected: from <= to");
}
} else {
assert(end == nullptr, "end node found but not start node");
}
```
Maybe the solution is simply to allow the user to provide a key compare (already a must in the none intrusive tree) Especially since my proposal also requires the the user to prove a node verifier call for cmp(start, end) to catch an error.
Adding the following test crashes in first 6 `visit_range_in_order` calls. The last 3 succeeds.
```
{
RBTreeInt rbtree;
using Node = RBTreeIntNode;
rbtree.upsert(2, 0);
rbtree.upsert(5, 0);
rbtree.visit_range_in_order(0, 0, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(0, 1, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(1, 1, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(3, 3, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(3, 4, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(4, 4, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(6,6, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(6, 7, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
rbtree.visit_range_in_order(7, 7, [&](const Node* x) {
EXPECT_TRUE(false) << "Range should not visit nodes";
});
}
```
Because we are not provided the tools to compare the keys directly, we have to do some sort of best effort. The best I could come up with was:
```
if (start != nullptr) {
assert_leq(from, start);
if (cursor_start.found()) {
assert_geq(to, start);
}
if (cursor_end.found()) {
assert_leq(from, cursor_end.node());
}
if (!cursor_start.found() && !cursor_end.found()) {
assert((end == nullptr) || // to after right-most, from is not
(start == end) || // their next nodes should at least be ordered,
(cmp(start, end)), // start <= end, from <= to may still be false,
// but we do not have the tools too check.
"expected: from <= to");
}
} else {
assert(end == nullptr, "end node found but not start node");
}
```
Maybe the solution is simply to allow the user to provide a key compare (already a must in the none intrusive tree) Especially since my proposal also requires the the user to prove a node verifier call for cmp(start, end) to catch an error.
- links to
-
Review(master) openjdk/jdk/24658