From cfccbd2eb5b051f3c33f1a5bb441ec3029cb0a24 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 30 Mar 2022 10:48:56 -0700 Subject: Export of internal Abseil changes -- fb671efb2a70f452f17a884b17cf18817b977a8f by Abseil Team : Remove extra semicolon in ABSL_INTERNAL_ASSERT_IS_FULL macro To fix compilation when empty statement warning is treated as error. PiperOrigin-RevId: 438342663 Change-Id: I3067fbeffa2691888f37554e88f229f24fb55ecc -- a58c9396f1d88d11347aed36ef2e1b633071363c by Martijn Vels : Fix kMaxHeight bounds to kMaxDepth for CordrepBtreeNavigator Added unit test (confirmed failure mode with old code) and extra assertion in the implementation. PiperOrigin-RevId: 438327463 Change-Id: I32242c86b0c879b8a42cb9a92075e537d588e09f -- f348e85dbfc9187ef59085fa2b999374f1670338 by Jorge Gorbe Moya : Make the flags enum in `RefcountAndFlags` a named enum to workaround an lldb issue (https://github.com/llvm/llvm-project/issues/54602). PiperOrigin-RevId: 438146097 Change-Id: Ibc2ee26489d99de515a779a903b6458dd0befef7 -- a960a3e9fb2a2e3418f806178e73d8566b78bc85 by Gennadiy Rozental : Introduce support for std::optional/absl::optional flag types. PiperOrigin-RevId: 438129500 Change-Id: I3d925c0a7f9ce9f857277fac3b0bf664ccd3a95c GitOrigin-RevId: fb671efb2a70f452f17a884b17cf18817b977a8f --- absl/strings/internal/cord_internal.h | 2 +- absl/strings/internal/cord_rep_btree_navigator.h | 6 ++++-- .../internal/cord_rep_btree_navigator_test.cc | 21 +++++++++++++++++++++ 3 files changed, 26 insertions(+), 3 deletions(-) (limited to 'absl/strings') diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 2087ffec..5ca5e589 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -156,7 +156,7 @@ class RefcountAndFlags { // used for the StringConstant constructor to avoid collecting immutable // constant cords. // kReservedFlag is reserved for future use. - enum { + enum Flags { kNumFlags = 2, kImmortalFlag = 0x1, diff --git a/absl/strings/internal/cord_rep_btree_navigator.h b/absl/strings/internal/cord_rep_btree_navigator.h index 971b92ed..3d581c87 100644 --- a/absl/strings/internal/cord_rep_btree_navigator.h +++ b/absl/strings/internal/cord_rep_btree_navigator.h @@ -143,8 +143,8 @@ class CordRepBtreeNavigator { // `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]; + uint8_t index_[CordRepBtree::kMaxDepth]; + CordRepBtree* node_[CordRepBtree::kMaxDepth]; }; // Returns true if this instance is not empty. @@ -173,6 +173,7 @@ template inline CordRep* CordRepBtreeNavigator::Init(CordRepBtree* tree) { assert(tree != nullptr); assert(tree->size() > 0); + assert(tree->height() <= CordRepBtree::kMaxHeight); int height = height_ = tree->height(); size_t index = tree->index(edge_type); node_[height] = tree; @@ -206,6 +207,7 @@ inline CordRepBtreeNavigator::Position CordRepBtreeNavigator::Seek( inline CordRepBtreeNavigator::Position CordRepBtreeNavigator::InitOffset( CordRepBtree* tree, size_t offset) { assert(tree != nullptr); + assert(tree->height() <= CordRepBtree::kMaxHeight); if (ABSL_PREDICT_FALSE(offset >= tree->length)) return {nullptr, 0}; height_ = tree->height(); node_[height_] = tree; diff --git a/absl/strings/internal/cord_rep_btree_navigator_test.cc b/absl/strings/internal/cord_rep_btree_navigator_test.cc index ce09b199..4f9bd4e5 100644 --- a/absl/strings/internal/cord_rep_btree_navigator_test.cc +++ b/absl/strings/internal/cord_rep_btree_navigator_test.cc @@ -319,6 +319,27 @@ TEST_P(CordRepBtreeNavigatorTest, ReadBeyondLengthOfTree) { ASSERT_THAT(result.tree, Eq(nullptr)); } +TEST(CordRepBtreeNavigatorTest, NavigateMaximumTreeDepth) { + CordRepFlat* flat1 = MakeFlat("Hello world"); + CordRepFlat* flat2 = MakeFlat("World Hello"); + + CordRepBtree* node = CordRepBtree::Create(flat1); + node = CordRepBtree::Append(node, flat2); + while (node->height() < CordRepBtree::kMaxHeight) { + node = CordRepBtree::New(node); + } + + CordRepBtreeNavigator nav; + CordRep* edge = nav.InitFirst(node); + EXPECT_THAT(edge, Eq(flat1)); + EXPECT_THAT(nav.Next(), Eq(flat2)); + EXPECT_THAT(nav.Next(), Eq(nullptr)); + EXPECT_THAT(nav.Previous(), Eq(flat1)); + EXPECT_THAT(nav.Previous(), Eq(nullptr)); + + CordRep::Unref(node); +} + } // namespace } // namespace cord_internal ABSL_NAMESPACE_END -- cgit v1.2.3