diff options
Diffstat (limited to 'absl/strings')
| -rw-r--r-- | absl/strings/BUILD.bazel | 18 | ||||
| -rw-r--r-- | absl/strings/CMakeLists.txt | 20 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree.h | 6 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree_navigator.cc | 185 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree_navigator.h | 265 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree_navigator_test.cc | 325 | ||||
| -rw-r--r-- | absl/strings/string_view.h | 10 |
7 files changed, 825 insertions, 4 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index c686e05a..7e0245a3 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -270,12 +270,14 @@ cc_library( srcs = [ "internal/cord_internal.cc", "internal/cord_rep_btree.cc", + "internal/cord_rep_btree_navigator.cc", "internal/cord_rep_consume.cc", "internal/cord_rep_ring.cc", ], hdrs = [ "internal/cord_internal.h", "internal/cord_rep_btree.h", + "internal/cord_rep_btree_navigator.h", "internal/cord_rep_consume.h", "internal/cord_rep_flat.h", "internal/cord_rep_ring.h", @@ -318,6 +320,22 @@ cc_test( ], ) +cc_test( + name = "cord_rep_btree_navigator_test", + size = "medium", + srcs = ["internal/cord_rep_btree_navigator_test.cc"], + copts = ABSL_TEST_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":cord_internal", + ":cord_rep_test_util", + ":strings", + "//absl/base:config", + "//absl/base:raw_logging_internal", + "@com_google_googletest//:gtest_main", + ], +) + cc_library( name = "cordz_update_tracker", hdrs = ["internal/cordz_update_tracker.h"], diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 2ddd3c48..e55c035d 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -556,6 +556,7 @@ absl_cc_library( HDRS "internal/cord_internal.h" "internal/cord_rep_btree.h" + "internal/cord_rep_btree_navigator.h" "internal/cord_rep_consume.h" "internal/cord_rep_flat.h" "internal/cord_rep_ring.h" @@ -563,6 +564,7 @@ absl_cc_library( SRCS "internal/cord_internal.cc" "internal/cord_rep_btree.cc" + "internal/cord_rep_btree_navigator.cc" "internal/cord_rep_consume.cc" "internal/cord_rep_ring.cc" COPTS @@ -959,6 +961,24 @@ absl_cc_test( absl_cc_test( NAME + cord_rep_btree_navigator_test + SRCS + "internal/cord_rep_btree_navigator_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::base + absl::config + absl::cord_internal + absl::cord_rep_test_util + absl::core_headers + absl::raw_logging_internal + absl::strings + GTest::gmock_main +) + +absl_cc_test( + NAME cord_ring_test SRCS "cord_ring_test.cc" diff --git a/absl/strings/internal/cord_rep_btree.h b/absl/strings/internal/cord_rep_btree.h index f4118fc0..7d854731 100644 --- a/absl/strings/internal/cord_rep_btree.h +++ b/absl/strings/internal/cord_rep_btree.h @@ -507,9 +507,9 @@ inline const CordRepBtree* CordRep::btree() const { inline void CordRepBtree::InitInstance(int height, size_t begin, size_t end) { tag = BTREE; - storage[0] = height; - storage[1] = begin; - storage[2] = end; + storage[0] = static_cast<uint8_t>(height); + storage[1] = static_cast<uint8_t>(begin); + storage[2] = static_cast<uint8_t>(end); } inline CordRep* CordRepBtree::Edge(size_t index) const { diff --git a/absl/strings/internal/cord_rep_btree_navigator.cc b/absl/strings/internal/cord_rep_btree_navigator.cc new file mode 100644 index 00000000..d1f9995d --- /dev/null +++ b/absl/strings/internal/cord_rep_btree_navigator.cc @@ -0,0 +1,185 @@ +// 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_navigator.h" + +#include <cassert> + +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +using ReadResult = CordRepBtreeNavigator::ReadResult; + +namespace { + +// Returns a `CordRepSubstring` from `rep` starting at `offset` of size `n`. +// If `rep` is already a `CordRepSubstring` instance, an adjusted instance is +// created based on the old offset and new offset. +// Adopts a reference on `rep`. Rep must be a valid data edge. Returns +// nullptr if `n == 0`, `rep` if `n == rep->length`. +// Requires `offset < rep->length` and `offset + n <= rep->length`. +// TODO(192061034): move to utility library in internal and optimize for small +// substrings of larger reps. +inline CordRep* Substring(CordRep* rep, size_t offset, size_t n) { + assert(n <= rep->length); + assert(offset < rep->length); + assert(offset <= rep->length - n); + assert(CordRepBtree::IsDataEdge(rep)); + + if (n == 0) return nullptr; + if (n == rep->length) return CordRep::Ref(rep); + + if (rep->tag == SUBSTRING) { + offset += rep->substring()->start; + rep = rep->substring()->child; + } + + CordRepSubstring* substring = new CordRepSubstring(); + substring->length = n; + substring->tag = SUBSTRING; + substring->start = offset; + substring->child = CordRep::Ref(rep); + return substring; +} + +inline CordRep* Substring(CordRep* rep, size_t offset) { + return Substring(rep, offset, rep->length - offset); +} + +} // namespace + +CordRepBtreeNavigator::Position CordRepBtreeNavigator::Skip(size_t n) { + int height = 0; + size_t index = index_[0]; + CordRepBtree* node = node_[0]; + CordRep* edge = node->Edge(index); + + // Overall logic: Find an edge of at least the length we need to skip. + // We consume all edges which are smaller (i.e., must be 100% skipped). + // If we exhausted all edges on the current level, we move one level + // up the tree, and repeat until we either find the edge, or until we hit + // the top of the tree meaning the skip exceeds tree->length. + while (n >= edge->length) { + n -= edge->length; + while (++index == node->end()) { + if (++height > height_) return {nullptr, n}; + node = node_[height]; + index = index_[height]; + } + edge = node->Edge(index); + } + + // If we moved up the tree, descend down to the leaf level, consuming all + // edges that must be skipped. + while (height > 0) { + node = edge->btree(); + index_[height] = index; + node_[--height] = node; + index = node->begin(); + edge = node->Edge(index); + while (n >= edge->length) { + n -= edge->length; + ++index; + assert(index != node->end()); + edge = node->Edge(index); + } + } + index_[0] = index; + return {edge, n}; +} + +ReadResult CordRepBtreeNavigator::Read(size_t edge_offset, size_t n) { + int height = 0; + size_t length = edge_offset + n; + size_t index = index_[0]; + CordRepBtree* node = node_[0]; + CordRep* edge = node->Edge(index); + assert(edge_offset < edge->length); + + if (length < edge->length) { + return {Substring(edge, edge_offset, n), length}; + } + + // Similar to 'Skip', we consume all edges that are inside the 'length' of + // data that needs to be read. If we exhaust the current level, we move one + // level up the tree and repeat until we hit the final edge that must be + // (partially) read. We consume all edges into `subtree`. + CordRepBtree* subtree = CordRepBtree::New(Substring(edge, edge_offset)); + size_t subtree_end = 1; + do { + length -= edge->length; + while (++index == node->end()) { + index_[height] = index; + if (++height > height_) { + subtree->set_end(subtree_end); + if (length == 0) return {subtree, 0}; + CordRep::Unref(subtree); + return {nullptr, length}; + } + if (length != 0) { + subtree->set_end(subtree_end); + subtree = CordRepBtree::New(subtree); + subtree_end = 1; + } + node = node_[height]; + index = index_[height]; + } + edge = node->Edge(index); + if (length >= edge->length) { + subtree->length += edge->length; + subtree->edges_[subtree_end++] = CordRep::Ref(edge); + } + } while (length >= edge->length); + CordRepBtree* tree = subtree; + subtree->length += length; + + // If we moved up the tree, descend down to the leaf level, consuming all + // edges that must be read, adding 'down' nodes to `subtree`. + while (height > 0) { + node = edge->btree(); + index_[height] = index; + node_[--height] = node; + index = node->begin(); + edge = node->Edge(index); + + if (length != 0) { + CordRepBtree* right = CordRepBtree::New(height); + right->length = length; + subtree->edges_[subtree_end++] = right; + subtree->set_end(subtree_end); + subtree = right; + subtree_end = 0; + while (length >= edge->length) { + subtree->edges_[subtree_end++] = CordRep::Ref(edge); + length -= edge->length; + edge = node->Edge(++index); + } + } + } + // Add any (partial) edge still remaining at the leaf level. + if (length != 0) { + subtree->edges_[subtree_end++] = Substring(edge, 0, length); + } + subtree->set_end(subtree_end); + index_[0] = index; + return {tree, length}; +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_rep_btree_navigator.h b/absl/strings/internal/cord_rep_btree_navigator.h new file mode 100644 index 00000000..971b92ed --- /dev/null +++ b/absl/strings/internal/cord_rep_btree_navigator.h @@ -0,0 +1,265 @@ +// 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. + +#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_NAVIGATOR_H_ +#define ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_NAVIGATOR_H_ + +#include <cassert> +#include <iostream> + +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// CordRepBtreeNavigator is a bi-directional navigator allowing callers to +// navigate all the (leaf) data edges in a CordRepBtree instance. +// +// A CordRepBtreeNavigator instance is by default empty. Callers initialize a +// navigator instance by calling one of `InitFirst()`, `InitLast()` or +// `InitOffset()`, which establishes a current position. Callers can then +// navigate using the `Next`, `Previous`, `Skip` and `Seek` methods. +// +// The navigator instance does not take or adopt a reference on the provided +// `tree` on any of the initialization calls. Callers are responsible for +// guaranteeing the lifecycle of the provided tree. A navigator instance can +// be reset to the empty state by calling `Reset`. +// +// A navigator only keeps positional state on the 'current data edge', it does +// explicitly not keep any 'offset' state. The class does accept and return +// offsets in the `Read()`, `Skip()` and 'Seek()` methods as these would +// otherwise put a big burden on callers. Callers are expected to maintain +// (returned) offset info if they require such granular state. +class CordRepBtreeNavigator { + public: + // The logical position as returned by the Seek() and Skip() functions. + // Returns the current leaf edge for the desired seek or skip position and + // the offset of that position inside that edge. + struct Position { + CordRep* edge; + size_t offset; + }; + + // The read result as returned by the Read() function. + // `tree` contains the resulting tree which is identical to the result + // of calling CordRepBtree::SubTree(...) on the tree being navigated. + // `n` contains the number of bytes used from the last navigated to + // edge of the tree. + struct ReadResult { + CordRep* tree; + size_t n; + }; + + // Returns true if this instance is not empty. + explicit operator bool() const; + + // Returns the tree for this instance or nullptr if empty. + CordRepBtree* btree() const; + + // Returns the data edge of the current position. + // Requires this instance to not be empty. + CordRep* Current() const; + + // Resets this navigator to `tree`, returning the first data edge in the tree. + CordRep* InitFirst(CordRepBtree* tree); + + // Resets this navigator to `tree`, returning the last data edge in the tree. + CordRep* InitLast(CordRepBtree* tree); + + // Resets this navigator to `tree` returning the data edge at position + // `offset` and the relative offset of `offset` into that data edge. + // Returns `Position.edge = nullptr` if the provided offset is greater + // than or equal to the length of the tree, in which case the state of + // the navigator instance remains unchanged. + Position InitOffset(CordRepBtree* tree, size_t offset); + + // Navigates to the next data edge. + // Returns the next data edge or nullptr if there is no next data edge, in + // which case the current position remains unchanged. + CordRep* Next(); + + // Navigates to the previous data edge. + // Returns the previous data edge or nullptr if there is no previous data + // edge, in which case the current position remains unchanged. + CordRep* Previous(); + + // Navigates to the data edge at position `offset`. Returns the navigated to + // data edge in `Position.edge` and the relative offset of `offset` into that + // data edge in `Position.offset`. Returns `Position.edge = nullptr` if the + // provide offset is greater than or equal to the tree's length. + Position Seek(size_t offset); + + // Reads `n` bytes of data starting at offset `edge_offset` of the current + // data edge, and returns the result in `ReadResult.tree`. `ReadResult.n` + // contains the 'bytes used` from the last / current data edge in the tree. + // This allows users that mix regular navigation (using string views) and + // 'read into cord' navigation to keep track of the current state, and which + // bytes have been consumed from a navigator. + // This function returns `ReadResult.tree = nullptr` if the requested length + // exceeds the length of the tree starting at the current data edge. + ReadResult Read(size_t edge_offset, size_t n); + + // Skips `n` bytes forward from the current data edge, returning the navigated + // to data edge in `Position.edge` and `Position.offset` containing the offset + // inside that data edge. Note that the state of the navigator is left + // unchanged if `n` is smaller than the length of the current data edge. + Position Skip(size_t n); + + // Resets this instance to the default / empty state. + void Reset(); + + private: + // Slow path for Next() if Next() reached the end of a leaf node. Backtracks + // up the stack until it finds a node that has a 'next' position available, + // and then does a 'front dive' towards the next leaf node. + CordRep* NextUp(); + + // Slow path for Previous() if Previous() reached the beginning of a leaf + // node. Backtracks up the stack until it finds a node that has a 'previous' + // position available, and then does a 'back dive' towards the previous leaf + // node. + CordRep* PreviousUp(); + + // Generic implementation of InitFirst() and InitLast(). + template <CordRepBtree::EdgeType edge_type> + CordRep* Init(CordRepBtree* tree); + + // `height_` contains the height of the current tree, or -1 if empty. + int height_ = -1; + + // `index_` and `node_` contain the navigation state as the 'path' to the + // current data edge which is at `node_[0]->Edge(index_[0])`. The contents + // of these are undefined until the instance is initialized (`height_ >= 0`). + uint8_t index_[CordRepBtree::kMaxHeight]; + CordRepBtree* node_[CordRepBtree::kMaxHeight]; +}; + +// Returns true if this instance is not empty. +inline CordRepBtreeNavigator::operator bool() const { return height_ >= 0; } + +inline CordRepBtree* CordRepBtreeNavigator::btree() const { + return height_ >= 0 ? node_[height_] : nullptr; +} + +inline CordRep* CordRepBtreeNavigator::Current() const { + assert(height_ >= 0); + return node_[0]->Edge(index_[0]); +} + +inline void CordRepBtreeNavigator::Reset() { height_ = -1; } + +inline CordRep* CordRepBtreeNavigator::InitFirst(CordRepBtree* tree) { + return Init<CordRepBtree::kFront>(tree); +} + +inline CordRep* CordRepBtreeNavigator::InitLast(CordRepBtree* tree) { + return Init<CordRepBtree::kBack>(tree); +} + +template <CordRepBtree::EdgeType edge_type> +inline CordRep* CordRepBtreeNavigator::Init(CordRepBtree* tree) { + assert(tree != nullptr); + assert(tree->size() > 0); + int height = height_ = tree->height(); + size_t index = tree->index(edge_type); + node_[height] = tree; + index_[height] = static_cast<uint8_t>(index); + while (--height >= 0) { + tree = tree->Edge(index)->btree(); + node_[height] = tree; + index = tree->index(edge_type); + index_[height] = static_cast<uint8_t>(index); + } + return node_[0]->Edge(index); +} + +inline CordRepBtreeNavigator::Position CordRepBtreeNavigator::Seek( + size_t offset) { + assert(btree() != nullptr); + int height = height_; + CordRepBtree* edge = node_[height]; + if (ABSL_PREDICT_FALSE(offset >= edge->length)) return {nullptr, 0}; + CordRepBtree::Position index = edge->IndexOf(offset); + index_[height] = static_cast<uint8_t>(index.index); + while (--height >= 0) { + edge = edge->Edge(index.index)->btree(); + node_[height] = edge; + index = edge->IndexOf(index.n); + index_[height] = static_cast<uint8_t>(index.index); + } + return {edge->Edge(index.index), index.n}; +} + +inline CordRepBtreeNavigator::Position CordRepBtreeNavigator::InitOffset( + CordRepBtree* tree, size_t offset) { + assert(tree != nullptr); + if (ABSL_PREDICT_FALSE(offset >= tree->length)) return {nullptr, 0}; + height_ = tree->height(); + node_[height_] = tree; + return Seek(offset); +} + +inline CordRep* CordRepBtreeNavigator::Next() { + CordRepBtree* edge = node_[0]; + return index_[0] == edge->back() ? NextUp() : edge->Edge(++index_[0]); +} + +inline CordRep* CordRepBtreeNavigator::Previous() { + CordRepBtree* edge = node_[0]; + return index_[0] == edge->begin() ? PreviousUp() : edge->Edge(--index_[0]); +} + +inline CordRep* CordRepBtreeNavigator::NextUp() { + assert(index_[0] == node_[0]->back()); + CordRepBtree* edge; + size_t index; + int height = 0; + do { + if (++height > height_) return nullptr; + edge = node_[height]; + index = index_[height] + 1; + } while (index == edge->end()); + index_[height] = static_cast<uint8_t>(index); + do { + node_[--height] = edge = edge->Edge(index)->btree(); + index_[height] = static_cast<uint8_t>(index = edge->begin()); + } while (height > 0); + return edge->Edge(index); +} + +inline CordRep* CordRepBtreeNavigator::PreviousUp() { + assert(index_[0] == node_[0]->begin()); + CordRepBtree* edge; + size_t index; + int height = 0; + do { + if (++height > height_) return nullptr; + edge = node_[height]; + index = index_[height]; + } while (index == edge->begin()); + index_[height] = static_cast<uint8_t>(--index); + do { + node_[--height] = edge = edge->Edge(index)->btree(); + index_[height] = static_cast<uint8_t>(index = edge->back()); + } while (height > 0); + return edge->Edge(index); +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_NAVIGATOR_H_ diff --git a/absl/strings/internal/cord_rep_btree_navigator_test.cc b/absl/strings/internal/cord_rep_btree_navigator_test.cc new file mode 100644 index 00000000..ce09b199 --- /dev/null +++ b/absl/strings/internal/cord_rep_btree_navigator_test.cc @@ -0,0 +1,325 @@ +// 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_navigator.h" + +#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/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.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 { +namespace { + +using ::testing::Eq; +using ::testing::Ne; + +using ::absl::cordrep_testing::CordRepBtreeFromFlats; +using ::absl::cordrep_testing::CordToString; +using ::absl::cordrep_testing::CreateFlatsFromString; +using ::absl::cordrep_testing::CreateRandomString; +using ::absl::cordrep_testing::MakeFlat; +using ::absl::cordrep_testing::MakeSubstring; + +using ReadResult = CordRepBtreeNavigator::ReadResult; +using Position = CordRepBtreeNavigator::Position; + +// CordRepBtreeNavigatorTest is a test fixture which automatically creates a +// tree to test navigation logic on. The parameter `count' defines the number of +// data edges in the test tree. +class CordRepBtreeNavigatorTest : public testing::TestWithParam<int> { + public: + using Flats = std::vector<CordRep*>; + static constexpr size_t kCharsPerFlat = 3; + + CordRepBtreeNavigatorTest() { + data_ = CreateRandomString(count() * kCharsPerFlat); + flats_ = CreateFlatsFromString(data_, kCharsPerFlat); + + // Turn flat 0 or 1 into a substring to cover partial reads on substrings. + if (count() > 1) { + CordRep::Unref(flats_[1]); + flats_[1] = MakeSubstring(kCharsPerFlat, kCharsPerFlat, MakeFlat(data_)); + } else { + CordRep::Unref(flats_[0]); + flats_[0] = MakeSubstring(0, kCharsPerFlat, MakeFlat(data_)); + } + + tree_ = CordRepBtreeFromFlats(flats_); + } + + ~CordRepBtreeNavigatorTest() override { CordRep::Unref(tree_); } + + int count() const { return GetParam(); } + CordRepBtree* tree() { return tree_; } + const std::string& data() const { return data_; } + const std::vector<CordRep*>& flats() const { return flats_; } + + static std::string ToString(testing::TestParamInfo<int> param) { + return absl::StrCat(param.param, "_Flats"); + } + + private: + std::string data_; + Flats flats_; + CordRepBtree* tree_; +}; + +INSTANTIATE_TEST_SUITE_P( + WithParam, CordRepBtreeNavigatorTest, + testing::Values(1, CordRepBtree::kMaxCapacity - 1, + CordRepBtree::kMaxCapacity, + CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity - 1, + CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity, + CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity + 1, + CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity * 2 + + 17), + CordRepBtreeNavigatorTest::ToString); + +TEST(CordRepBtreeNavigatorTest, Uninitialized) { + CordRepBtreeNavigator nav; + EXPECT_FALSE(nav); + EXPECT_THAT(nav.btree(), Eq(nullptr)); +#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) + EXPECT_DEATH(nav.Current(), ".*"); +#endif +} + +TEST_P(CordRepBtreeNavigatorTest, InitFirst) { + CordRepBtreeNavigator nav; + CordRep* edge = nav.InitFirst(tree()); + EXPECT_TRUE(nav); + EXPECT_THAT(nav.btree(), Eq(tree())); + EXPECT_THAT(nav.Current(), Eq(flats().front())); + EXPECT_THAT(edge, Eq(flats().front())); +} + +TEST_P(CordRepBtreeNavigatorTest, InitLast) { + CordRepBtreeNavigator nav; + CordRep* edge = nav.InitLast(tree()); + EXPECT_TRUE(nav); + EXPECT_THAT(nav.btree(), Eq(tree())); + EXPECT_THAT(nav.Current(), Eq(flats().back())); + EXPECT_THAT(edge, Eq(flats().back())); +} + +TEST_P(CordRepBtreeNavigatorTest, NextPrev) { + CordRepBtreeNavigator nav; + nav.InitFirst(tree()); + const Flats& flats = this->flats(); + + EXPECT_THAT(nav.Previous(), Eq(nullptr)); + EXPECT_THAT(nav.Current(), Eq(flats.front())); + for (int i = 1; i < flats.size(); ++i) { + ASSERT_THAT(nav.Next(), Eq(flats[i])); + EXPECT_THAT(nav.Current(), Eq(flats[i])); + } + EXPECT_THAT(nav.Next(), Eq(nullptr)); + EXPECT_THAT(nav.Current(), Eq(flats.back())); + for (int i = static_cast<int>(flats.size()) - 2; i >= 0; --i) { + ASSERT_THAT(nav.Previous(), Eq(flats[i])); + EXPECT_THAT(nav.Current(), Eq(flats[i])); + } + EXPECT_THAT(nav.Previous(), Eq(nullptr)); + EXPECT_THAT(nav.Current(), Eq(flats.front())); +} + +TEST_P(CordRepBtreeNavigatorTest, PrevNext) { + CordRepBtreeNavigator nav; + nav.InitLast(tree()); + const Flats& flats = this->flats(); + + EXPECT_THAT(nav.Next(), Eq(nullptr)); + EXPECT_THAT(nav.Current(), Eq(flats.back())); + for (int i = static_cast<int>(flats.size()) - 2; i >= 0; --i) { + ASSERT_THAT(nav.Previous(), Eq(flats[i])); + EXPECT_THAT(nav.Current(), Eq(flats[i])); + } + EXPECT_THAT(nav.Previous(), Eq(nullptr)); + EXPECT_THAT(nav.Current(), Eq(flats.front())); + for (int i = 1; i < flats.size(); ++i) { + ASSERT_THAT(nav.Next(), Eq(flats[i])); + EXPECT_THAT(nav.Current(), Eq(flats[i])); + } + EXPECT_THAT(nav.Next(), Eq(nullptr)); + EXPECT_THAT(nav.Current(), Eq(flats.back())); +} + +TEST(CordRepBtreeNavigatorTest, Reset) { + CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc")); + CordRepBtreeNavigator nav; + nav.InitFirst(tree); + nav.Reset(); + EXPECT_FALSE(nav); + EXPECT_THAT(nav.btree(), Eq(nullptr)); +#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) + EXPECT_DEATH(nav.Current(), ".*"); +#endif + CordRep::Unref(tree); +} + +TEST_P(CordRepBtreeNavigatorTest, Skip) { + int count = this->count(); + const Flats& flats = this->flats(); + CordRepBtreeNavigator nav; + nav.InitFirst(tree()); + + for (int char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { + Position pos = nav.Skip(char_offset); + EXPECT_THAT(pos.edge, Eq(nav.Current())); + EXPECT_THAT(pos.edge, Eq(flats[0])); + EXPECT_THAT(pos.offset, Eq(char_offset)); + } + + for (int index1 = 0; index1 < count; ++index1) { + for (int index2 = index1; index2 < count; ++index2) { + for (int char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { + CordRepBtreeNavigator nav; + nav.InitFirst(tree()); + + size_t length1 = index1 * kCharsPerFlat; + Position pos1 = nav.Skip(length1 + char_offset); + ASSERT_THAT(pos1.edge, Eq(flats[index1])); + ASSERT_THAT(pos1.edge, Eq(nav.Current())); + ASSERT_THAT(pos1.offset, Eq(char_offset)); + + size_t length2 = index2 * kCharsPerFlat; + Position pos2 = nav.Skip(length2 - length1 + char_offset); + ASSERT_THAT(pos2.edge, Eq(flats[index2])); + ASSERT_THAT(pos2.edge, Eq(nav.Current())); + ASSERT_THAT(pos2.offset, Eq(char_offset)); + } + } + } +} + +TEST_P(CordRepBtreeNavigatorTest, Seek) { + int count = this->count(); + const Flats& flats = this->flats(); + CordRepBtreeNavigator nav; + nav.InitFirst(tree()); + + for (int char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { + Position pos = nav.Seek(char_offset); + EXPECT_THAT(pos.edge, Eq(nav.Current())); + EXPECT_THAT(pos.edge, Eq(flats[0])); + EXPECT_THAT(pos.offset, Eq(char_offset)); + } + + for (int index = 0; index < count; ++index) { + for (int char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { + size_t offset = index * kCharsPerFlat + char_offset; + Position pos1 = nav.Seek(offset); + ASSERT_THAT(pos1.edge, Eq(flats[index])); + ASSERT_THAT(pos1.edge, Eq(nav.Current())); + ASSERT_THAT(pos1.offset, Eq(char_offset)); + } + } +} + +TEST(CordRepBtreeNavigatorTest, InitOffset) { + // Whitebox: InitOffset() is implemented in terms of Seek() which is + // exhaustively tested. Only test it initializes / forwards properly.. + CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc")); + tree = CordRepBtree::Append(tree, MakeFlat("def")); + CordRepBtreeNavigator nav; + Position pos = nav.InitOffset(tree, 5); + EXPECT_TRUE(nav); + EXPECT_THAT(nav.btree(), Eq(tree)); + EXPECT_THAT(pos.edge, Eq(tree->Edges()[1])); + EXPECT_THAT(pos.edge, Eq(nav.Current())); + EXPECT_THAT(pos.offset, Eq(2)); + CordRep::Unref(tree); +} + +TEST(CordRepBtreeNavigatorTest, InitOffsetAndSeekBeyondLength) { + CordRepBtree* tree1 = CordRepBtree::Create(MakeFlat("abc")); + CordRepBtree* tree2 = CordRepBtree::Create(MakeFlat("def")); + + CordRepBtreeNavigator nav; + nav.InitFirst(tree1); + EXPECT_THAT(nav.Seek(3).edge, Eq(nullptr)); + EXPECT_THAT(nav.Seek(100).edge, Eq(nullptr)); + EXPECT_THAT(nav.btree(), Eq(tree1)); + EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front())); + + EXPECT_THAT(nav.InitOffset(tree2, 3).edge, Eq(nullptr)); + EXPECT_THAT(nav.InitOffset(tree2, 100).edge, Eq(nullptr)); + EXPECT_THAT(nav.btree(), Eq(tree1)); + EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front())); + + CordRep::Unref(tree1); + CordRep::Unref(tree2); +} + +TEST_P(CordRepBtreeNavigatorTest, Read) { + const Flats& flats = this->flats(); + const std::string& data = this->data(); + + for (size_t offset = 0; offset < data.size(); ++offset) { + for (size_t length = 1; length <= data.size() - offset; ++length) { + CordRepBtreeNavigator nav; + nav.InitFirst(tree()); + + // Skip towards edge holding offset + size_t edge_offset = nav.Skip(offset).offset; + + // Read node + ReadResult result = nav.Read(edge_offset, length); + ASSERT_THAT(result.tree, Ne(nullptr)); + EXPECT_THAT(result.tree->length, Eq(length)); + if (result.tree->tag == BTREE) { + ASSERT_TRUE(CordRepBtree::IsValid(result.tree->btree())); + } + + // Verify contents + std::string value = CordToString(result.tree); + EXPECT_THAT(value, Eq(data.substr(offset, length))); + + // Verify 'partial last edge' reads. + size_t partial = (offset + length) % kCharsPerFlat; + ASSERT_THAT(result.n, Eq(partial)); + + // Verify ending position if not EOF + if (offset + length < data.size()) { + size_t index = (offset + length) / kCharsPerFlat; + EXPECT_THAT(nav.Current(), Eq(flats[index])); + } + + CordRep::Unref(result.tree); + } + } +} + +TEST_P(CordRepBtreeNavigatorTest, ReadBeyondLengthOfTree) { + CordRepBtreeNavigator nav; + nav.InitFirst(tree()); + ReadResult result = nav.Read(2, tree()->length); + ASSERT_THAT(result.tree, Eq(nullptr)); +} + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/string_view.h b/absl/strings/string_view.h index 968549be..ec6c431f 100644 --- a/absl/strings/string_view.h +++ b/absl/strings/string_view.h @@ -191,7 +191,9 @@ class string_view { ABSL_ATTRIBUTE_LIFETIME_BOUND) noexcept // This is implemented in terms of `string_view(p, n)` so `str.size()` // doesn't need to be reevaluated after `ptr_` is set. - : string_view(str.data(), str.size()) {} + // The length check is also skipped since it is unnecessary and causes + // code bloat. + : string_view(str.data(), str.size(), SkipCheckLengthTag{}) {} // Implicit constructor of a `string_view` from NUL-terminated `str`. When // accepting possibly null strings, use `absl::NullSafeStringView(str)` @@ -594,6 +596,12 @@ class string_view { } private: + // The constructor from std::string delegates to this constuctor. + // See the comment on that constructor for the rationale. + struct SkipCheckLengthTag {}; + string_view(const char* data, size_type len, SkipCheckLengthTag) noexcept + : ptr_(data), length_(len) {} + static constexpr size_type kMaxSize = (std::numeric_limits<difference_type>::max)(); |