Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8354433

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

XMLWordPrintable

    • Icon: Bug Bug
    • Resolution: Unresolved
    • Icon: P4 P4
    • 25
    • 25
    • hotspot
    • None

      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.

            cnorrbin Casper Norrbin
            aboldtch Axel Boldt-Christmas
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated: