1// Copyright 2016 The Fuchsia Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#pragma once 6 7#include <stdint.h> 8 9namespace fbl { 10 11namespace tests { 12namespace intrusive_containers { 13// Fwd decl of sanity checker class used by tests. 14class WAVLTreeChecker; 15 16// Definition of the default (no-op) Observer. 17// 18// Observers are used by the test framework to record the number of insert, 19// erase, rank-promote, rank-demote and rotation operations performed during 20// usage. The DefaultWAVLTreeObserver does nothing and should fall out of the 21// code during template expansion. 22// 23// Note: Records of promotions and demotions are used by tests to demonstrate 24// that the computational complexity of insert/erase rebalancing is amortized 25// constant. Promotions and demotions which are side effects of the rotation 26// phase of rebalancing are considered to be part of the cost of rotation and 27// are not tallied in the overall promote/demote accounting. 28// 29struct DefaultWAVLTreeObserver { 30 static void RecordInsert() { } 31 static void RecordInsertPromote() { } 32 static void RecordInsertRotation() { } 33 static void RecordInsertDoubleRotation() { } 34 35 static void RecordErase() { } 36 static void RecordEraseDemote() { } 37 static void RecordEraseRotation() { } 38 static void RecordEraseDoubleRotation() { } 39 40 template <typename TreeType> 41 static bool VerifyRankRule(const TreeType& tree, typename TreeType::RawPtrType node) { 42 return true; 43 } 44 45 template <typename TreeType> 46 static bool VerifyBalance(const TreeType& tree, uint64_t depth) { 47 return true; 48 } 49}; 50 51} // namespace tests 52} // namespace intrusive_containers 53 54// Prototypes for the WAVL tree node state. By default, we just use a bool to 55// record the rank parity of a node. During testing, however, we actually use a 56// specialized version of the node state in which the rank is stored as an 57// int32_t so that extra sanity checks can be made during balance testing. 58// 59// Note: All of the data members are stored in the node state base, as are the 60// helper methods IsValid and InContainer. Only the rank manipulation methods 61// are in the derived WAVLTreeNodeState class. This is to ensure that that the 62// WAVLTreeNodeState<> struct is a "standard layout type" which allows objects 63// which include a WAVLTreeNodeState<> to be standard layout types, provided 64// that they follow all of the other the rules as well. 65// 66template <typename PtrType, typename RankType> struct WAVLTreeNodeStateBase; // Fwd decl 67template <typename PtrType, typename RankType = bool> struct WAVLTreeNodeState; // Partial spec 68 69template <typename PtrType> 70struct WAVLTreeNodeState<PtrType, int32_t> : public WAVLTreeNodeStateBase<PtrType, int32_t> { 71 bool rank_parity() const { return ((this->rank_ & 0x1) != 0); } 72 void promote_rank() { this->rank_ += 1; } 73 void double_promote_rank() { this->rank_ += 2; } 74 void demote_rank() { this->rank_ -= 1; } 75 void double_demote_rank() { this->rank_ -= 2; } 76}; 77 78} // namespace fbl 79