zircon/system/ulib/fbl/test/include/fbl/tests/intrusive_containers/intrusive_wavl_tree_checker.h

// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef FBL_TESTS_INTRUSIVE_CONTAINERS_INTRUSIVE_WAVL_TREE_CHECKER_H_
#define FBL_TESTS_INTRUSIVE_CONTAINERS_INTRUSIVE_WAVL_TREE_CHECKER_H_

#include <fbl/intrusive_wavl_tree.h>
#include <zxtest/zxtest.h>

namespace fbl {
namespace tests {
namespace intrusive_containers {

using ::fbl::internal::is_sentinel_ptr;
using ::fbl::internal::valid_sentinel_ptr;

class WAVLTreeChecker {
 public:
  template <typename TreeType>
  static void VerifyParentBackLinks(const TreeType& tree, typename TreeType::RawPtrType node) {
    using NodeTraits = typename TreeType::NodeTraits;

    ASSERT_TRUE(valid_sentinel_ptr(node));
    const auto& ns = NodeTraits::node_state(*node);

    if (valid_sentinel_ptr(ns.left_)) {
      EXPECT_EQ(node, NodeTraits::node_state(*ns.left_).parent_,
                "Corrupt left-side parent back-link!");
    }

    if (valid_sentinel_ptr(ns.right_)) {
      EXPECT_EQ(node, NodeTraits::node_state(*ns.right_).parent_,
                "Corrupt right-side parent back-link!");
    }
  }

  template <typename TreeType>
  static void SanityCheck(const TreeType& tree) {
    using NodeTraits = typename TreeType::NodeTraits;
    using RawPtrType = typename TreeType::RawPtrType;
    using Observer = typename TreeType::Observer;

    // Enforce the sentinel requirements.
    if (tree.is_empty()) {
      // If the tree is empty, then the root should be null, and the
      // left/right-most members should be set to the sentinel value.
      ASSERT_NULL(tree.root_);
      ASSERT_EQ(tree.sentinel(), tree.left_most_);
      ASSERT_EQ(tree.sentinel(), tree.right_most_);
      EXPECT_EQ(0u, tree.size());
    } else {
      // If the tree is non-empty, then the root, left-most and
      // right-most pointers should all be valid.  The LR-child of the
      // LR-most element should be the sentinel value.
      ASSERT_NOT_NULL(tree.root_);
      ASSERT_FALSE(is_sentinel_ptr(tree.root_));

      ASSERT_NOT_NULL(tree.left_most_);
      ASSERT_FALSE(is_sentinel_ptr(tree.left_most_));
      ASSERT_EQ(tree.sentinel(), NodeTraits::node_state(*tree.left_most_).left_);

      ASSERT_NOT_NULL(tree.right_most_);
      ASSERT_FALSE(is_sentinel_ptr(tree.right_most_));
      ASSERT_EQ(tree.sentinel(), NodeTraits::node_state(*tree.right_most_).right_);

      EXPECT_LT(0u, tree.size());
    }

    // Compute the size and depth of the tree, verifying the parent
    // back-links as we go.  If this checker is being used as part of the
    // balance test, we will also verify the rank rule as we go as well as
    // the balance bounds at the end.
    uint64_t cur_depth = 0;
    uint64_t depth = 0;
    size_t size = 0;

    RawPtrType node = tree.root_;

    // Start by going left until we have determined the depth of the
    // left most node of the tree.
    while (valid_sentinel_ptr(node)) {
      ASSERT_NO_FAILURES(VerifyParentBackLinks(tree, node));

      auto& ns = NodeTraits::node_state(*node);
      ++cur_depth;

      if (!valid_sentinel_ptr(ns.left_))
        break;

      node = ns.left_;
    }

    // Now walk through the tree in ascending key order.  The basic
    // idea is...
    //
    // 1) "Visit" our current node, recording the new max depth if we
    //    have discovered one and checking the rank rule.
    // 2) If there is a right hand child, advance to the left-most node
    //    of the right hand sub-tree.
    // 3) If there is no right hand child, climb the tree until we
    //    traverse a left hand link.
    // 4) If we don't traverse a left hand link before hitting the root
    //    of the tree, then we are done.
    while (valid_sentinel_ptr(node)) {
      // #1: Visit
      if (depth < cur_depth)
        depth = cur_depth;
      ++size;

      ASSERT_NO_FAILURES(VerifyParentBackLinks(tree, node));

      // Verify the rank rule using the tree's observer's implementation.
      // If this sanity check is being run as part of the balance test, it
      // will use the implementation above.  For all other tests, only the
      // rank parity is stored in the node, so we cannot rigorously verify
      // the rule.  The default VerifyRankRule implementation will be used
      // instead.
      ASSERT_NO_FAILURES(Observer::VerifyRankRule(tree, node));

      // #2: Can we go right?
      const auto& ns = NodeTraits::node_state(*node);
      if (valid_sentinel_ptr(ns.right_)) {
        cur_depth++;
        node = ns.right_;
        ASSERT_NO_FAILURES(VerifyParentBackLinks(tree, node));

        // Now go as far left as we can.
        while (true) {
          auto& ns = NodeTraits::node_state(*node);

          if (!valid_sentinel_ptr(ns.left_))
            break;

          ++cur_depth;
          node = ns.left_;
          ASSERT_NO_FAILURES(VerifyParentBackLinks(tree, node));
        }

        // Loop and visit the next node.
        continue;
      }

      // #3: Climb until we traverse a left-hand link.
      RawPtrType parent = ns.parent_;
      bool keep_going;
      while ((keep_going = valid_sentinel_ptr(parent))) {
        auto& parent_ns = NodeTraits::node_state(*parent);
        bool is_left = (parent_ns.left_ == node);
        bool is_right = (parent_ns.right_ == node);

        ASSERT_TRUE(is_left != is_right);
        ASSERT_TRUE(is_left || is_right);

        node = parent;
        --cur_depth;

        if (is_left)
          break;

        parent = parent_ns.parent_;
      }

      // #4: If we ran out of valid parents to climb past, we are done.
      if (!keep_going)
        break;
    }

    // We should have visited all of the nodes by now.
    ASSERT_EQ(tree.size(), size);

    // If this is being called from the balance tests, check the balance
    // bounds, and computational complexity bounds.
    ASSERT_NO_FAILURES(Observer::VerifyBalance(tree, depth));
  }
};

}  // namespace intrusive_containers
}  // namespace tests
}  // namespace fbl

#endif  // FBL_TESTS_INTRUSIVE_CONTAINERS_INTRUSIVE_WAVL_TREE_CHECKER_H_