| // 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_INTRUSIVE_WAVL_TREE_INTERNAL_H_ |
| #define FBL_INTRUSIVE_WAVL_TREE_INTERNAL_H_ |
| |
| #include <stdint.h> |
| |
| namespace fbl { |
| |
| namespace tests { |
| namespace intrusive_containers { |
| // Fwd decl of sanity checker class used by tests. |
| class WAVLTreeChecker; |
| |
| // Definition of the default (no-op) Observer. |
| // |
| // Observers are used by the test framework to record the number of insert, |
| // erase, rank-promote, rank-demote and rotation operations performed during |
| // usage. The DefaultWAVLTreeObserver does nothing and should fall out of the |
| // code during template expansion. |
| // |
| // Note: Records of promotions and demotions are used by tests to demonstrate |
| // that the computational complexity of insert/erase rebalancing is amortized |
| // constant. Promotions and demotions which are side effects of the rotation |
| // phase of rebalancing are considered to be part of the cost of rotation and |
| // are not tallied in the overall promote/demote accounting. |
| // |
| struct DefaultWAVLTreeObserver { |
| static void RecordInsert() { } |
| static void RecordInsertPromote() { } |
| static void RecordInsertRotation() { } |
| static void RecordInsertDoubleRotation() { } |
| |
| static void RecordErase() { } |
| static void RecordEraseDemote() { } |
| static void RecordEraseRotation() { } |
| static void RecordEraseDoubleRotation() { } |
| |
| template <typename TreeType> |
| static bool VerifyRankRule(const TreeType& tree, typename TreeType::RawPtrType node) { |
| return true; |
| } |
| |
| template <typename TreeType> |
| static bool VerifyBalance(const TreeType& tree, uint64_t depth) { |
| return true; |
| } |
| }; |
| |
| } // namespace tests |
| } // namespace intrusive_containers |
| |
| using DefaultWAVLTreeRankType = bool; |
| |
| // Prototypes for the WAVL tree node state. By default, we just use a bool to |
| // record the rank parity of a node. During testing, however, we actually use a |
| // specialized version of the node state in which the rank is stored as an |
| // int32_t so that extra sanity checks can be made during balance testing. |
| // |
| // Note: All of the data members are stored in the node state base, as are the |
| // helper methods IsValid and InContainer. Only the rank manipulation methods |
| // are in the derived WAVLTreeNodeState class. This is to ensure that that the |
| // WAVLTreeNodeState<> struct is a "standard layout type" which allows objects |
| // which include a WAVLTreeNodeState<> to be standard layout types, provided |
| // that they follow all of the other the rules as well. |
| // |
| template <typename PtrType, typename RankType> // Fwd decl |
| struct WAVLTreeNodeStateBase; |
| template <typename PtrType, typename RankType = DefaultWAVLTreeRankType> // Partial spec |
| struct WAVLTreeNodeState; |
| |
| template <typename PtrType> |
| struct WAVLTreeNodeState<PtrType, int32_t> : public WAVLTreeNodeStateBase<PtrType, int32_t> { |
| bool rank_parity() const { return ((this->rank_ & 0x1) != 0); } |
| void promote_rank() { this->rank_ += 1; } |
| void double_promote_rank() { this->rank_ += 2; } |
| void demote_rank() { this->rank_ -= 1; } |
| void double_demote_rank() { this->rank_ -= 2; } |
| }; |
| |
| } // namespace fbl |
| |
| #endif // FBL_INTRUSIVE_WAVL_TREE_INTERNAL_H_ |