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