cord_rep_btree_test.cc | Explore in Territory

// Copyright 2021 The Abseil Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "absl/strings/internal/cord_rep_btree.h"

#include <cmath>
#include <deque>
#include <iostream>
#include <string>
#include <vector>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/cleanup/cleanup.h"
#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_test_util.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/string_view.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {

class CordRepBtreeTestPeer { … };

namespace {

AutoUnref;
CordCollectRepsIf;
CordToString;
CordVisitReps;
CreateFlatsFromString;
CreateRandomString;
MakeExternal;
MakeFlat;
MakeSubstring;
_;
AllOf;
AnyOf;
Conditional;
ElementsAre;
ElementsAreArray;
Eq;
HasSubstr;
Le;
Ne;
Not;
SizeIs;
TypedEq;

MATCHER_P(EqFlatHolding, data, "Equals flat holding data") { … }

MATCHER_P(IsNode, height, absl::StrCat("Is a valid node of height ", height)) { … }

MATCHER_P2(IsSubstring, start, length,
           absl::StrCat("Is a substring(start = ", start, ", length = ", length,
                        ")")) { … }

MATCHER_P2(EqExtractResult, tree, rep, "Equals ExtractResult") { … }

// DataConsumer is a simple helper class used by tests to 'consume' string
// fragments from the provided input in forward or backward direction.
class DataConsumer { … };

// BtreeAdd returns either CordRepBtree::Append or CordRepBtree::Prepend.
CordRepBtree* BtreeAdd(CordRepBtree* node, bool append,
                       absl::string_view data) { … }

// Recursively collects all leaf edges from `tree` and appends them to `edges`.
void GetLeafEdges(const CordRepBtree* tree, std::vector<CordRep*>& edges) { … }

// Recursively collects and returns all leaf edges from `tree`.
std::vector<CordRep*> GetLeafEdges(const CordRepBtree* tree) { … }

// Creates a flat containing the hexadecimal value of `i` zero padded
// to at least 4 digits prefixed with "0x", e.g.: "0x04AC".
CordRepFlat* MakeHexFlat(size_t i) { … }

CordRepBtree* MakeLeaf(size_t size = CordRepBtree::kMaxCapacity) { … }

CordRepBtree* MakeTree(size_t size, bool append = true) { … }

CordRepBtree* CreateTree(absl::Span<CordRep* const> reps) { … }

CordRepBtree* CreateTree(absl::string_view data, size_t chunk_size) { … }

CordRepBtree* CreateTreeReverse(absl::string_view data, size_t chunk_size) { … }

class CordRepBtreeTest : public testing::TestWithParam<bool> { … };

INSTANTIATE_TEST_SUITE_P(…);

class CordRepBtreeHeightTest : public testing::TestWithParam<int> { … };

INSTANTIATE_TEST_SUITE_P(…);

TwoBools;

class CordRepBtreeDualTest : public testing::TestWithParam<TwoBools> { … };

INSTANTIATE_TEST_SUITE_P(…);

TEST(CordRepBtreeTest, SizeIsMultipleOf64) { … }

TEST(CordRepBtreeTest, NewDestroyEmptyTree) { … }

TEST(CordRepBtreeTest, NewDestroyEmptyTreeAtHeight) { … }

TEST(CordRepBtreeTest, Btree) { … }

TEST(CordRepBtreeTest, EdgeData) { … }

TEST(CordRepBtreeTest, CreateUnrefLeaf) { … }

TEST(CordRepBtreeTest, NewUnrefNode) { … }

TEST_P(CordRepBtreeTest, AppendToLeafToCapacity) { … }

TEST_P(CordRepBtreeTest, PrependToLeafToCapacity) { … }

// This test specifically aims at code aligning data at either the front or the
// back of the contained `edges[]` array, alternating Append and Prepend will
// move `begin()` and `end()` values as needed for each added value.
TEST_P(CordRepBtreeTest, AppendPrependToLeafToCapacity) { … }

TEST_P(CordRepBtreeTest, AppendToLeafBeyondCapacity) { … }

TEST_P(CordRepBtreeTest, PrependToLeafBeyondCapacity) { … }

TEST_P(CordRepBtreeTest, AppendToTreeOneDeep) { … }

TEST_P(CordRepBtreeTest, AppendToTreeTwoDeep) { … }

TEST_P(CordRepBtreeTest, PrependToTreeOneDeep) { … }

TEST_P(CordRepBtreeTest, PrependToTreeTwoDeep) { … }

TEST_P(CordRepBtreeDualTest, MergeLeafsNotExceedingCapacity) { … }

TEST_P(CordRepBtreeDualTest, MergeLeafsExceedingCapacity) { … }

TEST_P(CordRepBtreeDualTest, MergeEqualHeightTrees) { … }

TEST_P(CordRepBtreeDualTest, MergeLeafWithTreeNotExceedingLeafCapacity) { … }

TEST_P(CordRepBtreeDualTest, MergeLeafWithTreeExceedingLeafCapacity) { … }

void RefEdgesAt(size_t depth, AutoUnref& refs, CordRepBtree* tree) { … }

TEST(CordRepBtreeTest, MergeFuzzTest) { … }

TEST_P(CordRepBtreeTest, RemoveSuffix) { … }

TEST(CordRepBtreeTest, SubTree) { … }

TEST(CordRepBtreeTest, SubTreeOnExistingSubstring) { … }

TEST_P(CordRepBtreeTest, AddDataToLeaf) { … }

TEST_P(CordRepBtreeTest, AppendDataToTree) { … }

TEST_P(CordRepBtreeTest, PrependDataToTree) { … }

TEST_P(CordRepBtreeTest, AddDataToTreeThreeLevelsDeep) { … }

TEST_P(CordRepBtreeTest, AddLargeDataToLeaf) { … }

TEST_P(CordRepBtreeTest, CreateFromTreeReturnsTree) { … }

TEST(CordRepBtreeTest, GetCharacter) { … }

TEST_P(CordRepBtreeTest, IsFlatSingleFlat) { … }

TEST(CordRepBtreeTest, IsFlatMultiFlat) { … }

#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)

TEST_P(CordRepBtreeHeightTest, GetAppendBufferNotPrivate) { … }

#endif  // defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)

TEST_P(CordRepBtreeHeightTest, GetAppendBufferNotFlat) { … }

TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatNotPrivate) { … }

TEST_P(CordRepBtreeHeightTest, GetAppendBufferTreeNotPrivate) { … }

TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatNoCapacity) { … }

TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatWithCapacity) { … }

TEST(CordRepBtreeTest, Dump) { … }

TEST(CordRepBtreeTest, IsValid) { … }

TEST(CordRepBtreeTest, AssertValid) { … }

TEST(CordRepBtreeTest, CheckAssertValidShallowVsDeep) { … }

TEST_P(CordRepBtreeTest, Rebuild) { … }

// Convenience helper for CordRepBtree::ExtractAppendBuffer
CordRepBtree::ExtractResult ExtractLast(CordRepBtree* input, size_t cap = 1) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferLeafSingleFlat) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNodeSingleFlat) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferLeafTwoFlats) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNodeTwoFlats) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNodeTwoFlatsInTwoLeafs) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferLeafThreeFlats) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNodeThreeFlatsRightNoFolding) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNodeThreeFlatsRightLeafFolding) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNoCapacity) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferNotFlat) { … }

TEST(CordRepBtreeTest, ExtractAppendBufferShared) { … }

}  // namespace
}  // namespace cord_internal
ABSL_NAMESPACE_END
}  // namespace absl
chromium/third_party/abseil-cpp/absl/strings/internal/cord_rep_btree_test.cc
