From 914ff44510505f209d8e85a01e31f4c5fb1b6a5b Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 20 Feb 2020 12:34:37 -0800 Subject: Export of internal Abseil changes -- bffb14058bb46137d42c7a113a36b6b582997cda by Xiaoyi Zhang : Add ABSL_MUST_USE_RESULT to Status. PiperOrigin-RevId: 296272498 -- b426fdd3b3f687d7a8aeb644925923bbab503778 by CJ Johnson : Optimizes absl::InlinedVector::clear() by not deallocating the data, if allocated. This allows allocations to be reused. This matches the behavior of std::vector::clear() PiperOrigin-RevId: 296197235 -- 8cb9fbfe20e749816065c1a042e84f72dac9bfc0 by CJ Johnson : Optimizes absl::InlinedVector::clear() by not deallocating the data, if allocated. This allows allocations to be reused. This matches the behavior of std::vector::clear() PiperOrigin-RevId: 296058092 -- 2558d3369a482879919155b6f46317ccafe0ca13 by Matthew Brown : Internal cleanup PiperOrigin-RevId: 296025806 -- cf7ee57228534021c15ed7421df92acf6c27c9c7 by Gennadiy Rozental : Make FlagOps enum class. We also add comments to all the functions used to invoke flag ops. PiperOrigin-RevId: 295975809 -- 74bbdbd12fbc54e9c4ebcb3005e727becf0e509d by Xiaoyi Zhang : Release `absl::Status`. PiperOrigin-RevId: 295777662 -- 3dbc622b4e2227863525da2f7de7ecbeb3ede21f by Xiaoyi Zhang : Internal change. PiperOrigin-RevId: 295733658 -- 48d74aa0ab01d611da6012b377f038d8b26c712e by Abseil Team : Fix typo in container/CMakeLists.txt for container_common PiperOrigin-RevId: 295491438 GitOrigin-RevId: bffb14058bb46137d42c7a113a36b6b582997cda Change-Id: Ia966857b07fa7412cd6489ac37b5fa26640e4141 --- absl/status/status_test.cc | 401 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 401 insertions(+) create mode 100644 absl/status/status_test.cc (limited to 'absl/status/status_test.cc') diff --git a/absl/status/status_test.cc b/absl/status/status_test.cc new file mode 100644 index 00000000..7cc65e45 --- /dev/null +++ b/absl/status/status_test.cc @@ -0,0 +1,401 @@ +// Copyright 2019 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/status/status.h" + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/strings/str_cat.h" + +namespace { + +using ::testing::Eq; +using ::testing::HasSubstr; +using ::testing::Optional; +using ::testing::UnorderedElementsAreArray; + +TEST(StatusCode, InsertionOperator) { + const absl::StatusCode code = absl::StatusCode::kUnknown; + std::ostringstream oss; + oss << code; + EXPECT_EQ(oss.str(), absl::StatusCodeToString(code)); +} + +// This structure holds the details for testing a single error code, +// its creator, and its classifier. +struct ErrorTest { + absl::StatusCode code; + using Creator = absl::Status (*)(absl::string_view); + using Classifier = bool (*)(const absl::Status&); + Creator creator; + Classifier classifier; +}; + +constexpr ErrorTest kErrorTests[]{ + {absl::StatusCode::kCancelled, absl::CancelledError, absl::IsCancelled}, + {absl::StatusCode::kUnknown, absl::UnknownError, absl::IsUnknown}, + {absl::StatusCode::kInvalidArgument, absl::InvalidArgumentError, + absl::IsInvalidArgument}, + {absl::StatusCode::kDeadlineExceeded, absl::DeadlineExceededError, + absl::IsDeadlineExceeded}, + {absl::StatusCode::kNotFound, absl::NotFoundError, absl::IsNotFound}, + {absl::StatusCode::kAlreadyExists, absl::AlreadyExistsError, + absl::IsAlreadyExists}, + {absl::StatusCode::kPermissionDenied, absl::PermissionDeniedError, + absl::IsPermissionDenied}, + {absl::StatusCode::kResourceExhausted, absl::ResourceExhaustedError, + absl::IsResourceExhausted}, + {absl::StatusCode::kFailedPrecondition, absl::FailedPreconditionError, + absl::IsFailedPrecondition}, + {absl::StatusCode::kAborted, absl::AbortedError, absl::IsAborted}, + {absl::StatusCode::kOutOfRange, absl::OutOfRangeError, absl::IsOutOfRange}, + {absl::StatusCode::kUnimplemented, absl::UnimplementedError, + absl::IsUnimplemented}, + {absl::StatusCode::kInternal, absl::InternalError, absl::IsInternal}, + {absl::StatusCode::kUnavailable, absl::UnavailableError, + absl::IsUnavailable}, + {absl::StatusCode::kDataLoss, absl::DataLossError, absl::IsDataLoss}, + {absl::StatusCode::kUnauthenticated, absl::UnauthenticatedError, + absl::IsUnauthenticated}, +}; + +TEST(Status, CreateAndClassify) { + for (const auto& test : kErrorTests) { + SCOPED_TRACE(absl::StatusCodeToString(test.code)); + + // Ensure that the creator does, in fact, create status objects with the + // expected error code and message. + std::string message = + absl::StrCat("error code ", test.code, " test message"); + absl::Status status = test.creator(message); + EXPECT_EQ(test.code, status.code()); + EXPECT_EQ(message, status.message()); + + // Ensure that the classifier returns true for a status produced by the + // creator. + EXPECT_TRUE(test.classifier(status)); + + // Ensure that the classifier returns false for status with a different + // code. + for (const auto& other : kErrorTests) { + if (other.code != test.code) { + EXPECT_FALSE(test.classifier(absl::Status(other.code, ""))) + << " other.code = " << other.code; + } + } + } +} + +TEST(Status, DefaultConstructor) { + absl::Status status; + EXPECT_TRUE(status.ok()); + EXPECT_EQ(absl::StatusCode::kOk, status.code()); + EXPECT_EQ("", status.message()); +} + +TEST(Status, OkStatus) { + absl::Status status = absl::OkStatus(); + EXPECT_TRUE(status.ok()); + EXPECT_EQ(absl::StatusCode::kOk, status.code()); + EXPECT_EQ("", status.message()); +} + +TEST(Status, ConstructorWithCodeMessage) { + { + absl::Status status(absl::StatusCode::kCancelled, ""); + EXPECT_FALSE(status.ok()); + EXPECT_EQ(absl::StatusCode::kCancelled, status.code()); + EXPECT_EQ("", status.message()); + } + { + absl::Status status(absl::StatusCode::kInternal, "message"); + EXPECT_FALSE(status.ok()); + EXPECT_EQ(absl::StatusCode::kInternal, status.code()); + EXPECT_EQ("message", status.message()); + } +} + +TEST(Status, ConstructOutOfRangeCode) { + const int kRawCode = 9999; + absl::Status status(static_cast(kRawCode), ""); + EXPECT_EQ(absl::StatusCode::kUnknown, status.code()); + EXPECT_EQ(kRawCode, status.raw_code()); +} + +constexpr char kUrl1[] = "url.payload.1"; +constexpr char kUrl2[] = "url.payload.2"; +constexpr char kUrl3[] = "url.payload.3"; +constexpr char kUrl4[] = "url.payload.xx"; + +constexpr char kPayload1[] = "aaaaa"; +constexpr char kPayload2[] = "bbbbb"; +constexpr char kPayload3[] = "ccccc"; + +using PayloadsVec = std::vector>; + +TEST(Status, TestGetSetPayload) { + absl::Status ok_status = absl::OkStatus(); + ok_status.SetPayload(kUrl1, absl::Cord(kPayload1)); + ok_status.SetPayload(kUrl2, absl::Cord(kPayload2)); + + EXPECT_FALSE(ok_status.GetPayload(kUrl1)); + EXPECT_FALSE(ok_status.GetPayload(kUrl2)); + + absl::Status bad_status(absl::StatusCode::kInternal, "fail"); + bad_status.SetPayload(kUrl1, absl::Cord(kPayload1)); + bad_status.SetPayload(kUrl2, absl::Cord(kPayload2)); + + EXPECT_THAT(bad_status.GetPayload(kUrl1), Optional(Eq(kPayload1))); + EXPECT_THAT(bad_status.GetPayload(kUrl2), Optional(Eq(kPayload2))); + + EXPECT_FALSE(bad_status.GetPayload(kUrl3)); + + bad_status.SetPayload(kUrl1, absl::Cord(kPayload3)); + EXPECT_THAT(bad_status.GetPayload(kUrl1), Optional(Eq(kPayload3))); + + // Testing dynamically generated type_url + bad_status.SetPayload(absl::StrCat(kUrl1, ".1"), absl::Cord(kPayload1)); + EXPECT_THAT(bad_status.GetPayload(absl::StrCat(kUrl1, ".1")), + Optional(Eq(kPayload1))); +} + +TEST(Status, TestErasePayload) { + absl::Status bad_status(absl::StatusCode::kInternal, "fail"); + bad_status.SetPayload(kUrl1, absl::Cord(kPayload1)); + bad_status.SetPayload(kUrl2, absl::Cord(kPayload2)); + bad_status.SetPayload(kUrl3, absl::Cord(kPayload3)); + + EXPECT_FALSE(bad_status.ErasePayload(kUrl4)); + + EXPECT_TRUE(bad_status.GetPayload(kUrl2)); + EXPECT_TRUE(bad_status.ErasePayload(kUrl2)); + EXPECT_FALSE(bad_status.GetPayload(kUrl2)); + EXPECT_FALSE(bad_status.ErasePayload(kUrl2)); + + EXPECT_TRUE(bad_status.ErasePayload(kUrl1)); + EXPECT_TRUE(bad_status.ErasePayload(kUrl3)); + + bad_status.SetPayload(kUrl1, absl::Cord(kPayload1)); + EXPECT_TRUE(bad_status.ErasePayload(kUrl1)); +} + +TEST(Status, TestComparePayloads) { + absl::Status bad_status1(absl::StatusCode::kInternal, "fail"); + bad_status1.SetPayload(kUrl1, absl::Cord(kPayload1)); + bad_status1.SetPayload(kUrl2, absl::Cord(kPayload2)); + bad_status1.SetPayload(kUrl3, absl::Cord(kPayload3)); + + absl::Status bad_status2(absl::StatusCode::kInternal, "fail"); + bad_status2.SetPayload(kUrl2, absl::Cord(kPayload2)); + bad_status2.SetPayload(kUrl3, absl::Cord(kPayload3)); + bad_status2.SetPayload(kUrl1, absl::Cord(kPayload1)); + + EXPECT_EQ(bad_status1, bad_status2); +} + +PayloadsVec AllVisitedPayloads(const absl::Status& s) { + PayloadsVec result; + + s.ForEachPayload([&](absl::string_view type_url, const absl::Cord& payload) { + result.push_back(std::make_pair(std::string(type_url), payload)); + }); + + return result; +} + +TEST(Status, TestForEachPayload) { + absl::Status bad_status(absl::StatusCode::kInternal, "fail"); + bad_status.SetPayload(kUrl1, absl::Cord(kPayload1)); + bad_status.SetPayload(kUrl2, absl::Cord(kPayload2)); + bad_status.SetPayload(kUrl3, absl::Cord(kPayload3)); + + int count = 0; + + bad_status.ForEachPayload( + [&count](absl::string_view, const absl::Cord&) { ++count; }); + + EXPECT_EQ(count, 3); + + PayloadsVec expected_payloads = {{kUrl1, absl::Cord(kPayload1)}, + {kUrl2, absl::Cord(kPayload2)}, + {kUrl3, absl::Cord(kPayload3)}}; + + // Test that we visit all the payloads in the status. + PayloadsVec visited_payloads = AllVisitedPayloads(bad_status); + EXPECT_THAT(visited_payloads, UnorderedElementsAreArray(expected_payloads)); + + // Test that visitation order is not consistent between run. + std::vector scratch; + while (true) { + scratch.emplace_back(absl::StatusCode::kInternal, "fail"); + + scratch.back().SetPayload(kUrl1, absl::Cord(kPayload1)); + scratch.back().SetPayload(kUrl2, absl::Cord(kPayload2)); + scratch.back().SetPayload(kUrl3, absl::Cord(kPayload3)); + + if (AllVisitedPayloads(scratch.back()) != visited_payloads) { + break; + } + } +} + +TEST(Status, ToString) { + absl::Status s(absl::StatusCode::kInternal, "fail"); + EXPECT_EQ("INTERNAL: fail", s.ToString()); + s.SetPayload("foo", absl::Cord("bar")); + EXPECT_EQ("INTERNAL: fail [foo='bar']", s.ToString()); + s.SetPayload("bar", absl::Cord("\377")); + EXPECT_THAT(s.ToString(), + AllOf(HasSubstr("INTERNAL: fail"), HasSubstr("[foo='bar']"), + HasSubstr("[bar='\\xff']"))); +} + +TEST(Status, CopyConstructor) { + { + absl::Status status; + absl::Status copy(status); + EXPECT_EQ(copy, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + absl::Status copy(status); + EXPECT_EQ(copy, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + status.SetPayload(kUrl1, absl::Cord(kPayload1)); + absl::Status copy(status); + EXPECT_EQ(copy, status); + } +} + +TEST(Status, CopyAssignment) { + absl::Status assignee; + { + absl::Status status; + assignee = status; + EXPECT_EQ(assignee, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + assignee = status; + EXPECT_EQ(assignee, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + status.SetPayload(kUrl1, absl::Cord(kPayload1)); + assignee = status; + EXPECT_EQ(assignee, status); + } +} + +TEST(Status, MoveConstructor) { + { + absl::Status status; + absl::Status copy(absl::Status{}); + EXPECT_EQ(copy, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + absl::Status copy( + absl::Status(absl::StatusCode::kInvalidArgument, "message")); + EXPECT_EQ(copy, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + status.SetPayload(kUrl1, absl::Cord(kPayload1)); + absl::Status copy1(status); + absl::Status copy2(std::move(status)); + EXPECT_EQ(copy1, copy2); + } +} + +TEST(Status, MoveAssignment) { + absl::Status assignee; + { + absl::Status status; + assignee = absl::Status(); + EXPECT_EQ(assignee, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + assignee = absl::Status(absl::StatusCode::kInvalidArgument, "message"); + EXPECT_EQ(assignee, status); + } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + status.SetPayload(kUrl1, absl::Cord(kPayload1)); + absl::Status copy(status); + assignee = std::move(status); + EXPECT_EQ(assignee, copy); + } +} + +TEST(Status, Update) { + absl::Status s; + s.Update(absl::OkStatus()); + EXPECT_TRUE(s.ok()); + const absl::Status a(absl::StatusCode::kCancelled, "message"); + s.Update(a); + EXPECT_EQ(s, a); + const absl::Status b(absl::StatusCode::kInternal, "other message"); + s.Update(b); + EXPECT_EQ(s, a); + s.Update(absl::OkStatus()); + EXPECT_EQ(s, a); + EXPECT_FALSE(s.ok()); +} + +TEST(Status, Equality) { + absl::Status ok; + absl::Status no_payload = absl::CancelledError("no payload"); + absl::Status one_payload = absl::InvalidArgumentError("one payload"); + one_payload.SetPayload(kUrl1, absl::Cord(kPayload1)); + absl::Status two_payloads = one_payload; + two_payloads.SetPayload(kUrl2, absl::Cord(kPayload2)); + const std::array status_arr = {ok, no_payload, one_payload, + two_payloads}; + for (int i = 0; i < status_arr.size(); i++) { + for (int j = 0; j < status_arr.size(); j++) { + if (i == j) { + EXPECT_TRUE(status_arr[i] == status_arr[j]); + EXPECT_FALSE(status_arr[i] != status_arr[j]); + } else { + EXPECT_TRUE(status_arr[i] != status_arr[j]); + EXPECT_FALSE(status_arr[i] == status_arr[j]); + } + } + } +} + +TEST(Status, Swap) { + auto test_swap = [](const absl::Status& s1, const absl::Status& s2) { + absl::Status copy1 = s1, copy2 = s2; + swap(copy1, copy2); + EXPECT_EQ(copy1, s2); + EXPECT_EQ(copy2, s1); + }; + const absl::Status ok; + const absl::Status no_payload(absl::StatusCode::kAlreadyExists, "no payload"); + absl::Status with_payload(absl::StatusCode::kInternal, "with payload"); + with_payload.SetPayload(kUrl1, absl::Cord(kPayload1)); + test_swap(ok, no_payload); + test_swap(no_payload, ok); + test_swap(ok, with_payload); + test_swap(with_payload, ok); + test_swap(no_payload, with_payload); + test_swap(with_payload, no_payload); +} + +} // namespace -- cgit v1.2.3 From b19ba96766db08b1f32605cb4424a0e7ea0c7584 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 3 Mar 2020 11:22:10 -0800 Subject: Export of internal Abseil changes -- a3e58c1870a9626039f4d178d2d599319bd9f8a8 by Matt Kulukundis : Allow MakeCordFromExternal to take a zero arg releaser. PiperOrigin-RevId: 298650274 -- 01897c4a9bb99f3dc329a794019498ad345ddebd by Samuel Benzaquen : Reduce library bloat for absl::Flag by moving the definition of base virtual functions to a .cc file. This removes the duplicate symbols in user translation units and has the side effect of moving the vtable definition too (re key function) PiperOrigin-RevId: 298617920 -- 190f0d3782c63aed01046886d7fbc1be5bca2de9 by Derek Mauro : Import GitHub #596: Unbreak stacktrace code for UWP apps PiperOrigin-RevId: 298600834 -- cd5cf6f8c87b35b85a9584e94da2a99057345b73 by Gennadiy Rozental : Use union of heap allocated pointer, one word atomic and two word atomic to represent flags value. Any type T, which is trivially copy-able and with with sizeof(T) <= 8, will be stored in atomic int64_t. Any type T, which is trivially copy-able and with with 8 < sizeof(T) <= 16, will be stored in atomic AlignedTwoWords. We also introducing value storage type to distinguish these cases. PiperOrigin-RevId: 298497200 -- f8fe7bd53bfed601f002f521e34ab4bc083fc28b by Matthew Brown : Ensure a deep copy and proper equality on absl::Status::ErasePayload PiperOrigin-RevId: 298482742 -- a5c9ccddf4b04f444e3f7e27dbc14faf1fcb5373 by Gennadiy Rozental : Change ChunkIterator implementation to use fixed capacity collection of CordRep*. We can now assume that depth never exceeds 91. That makes comparison operator exception safe. I've tested that with this CL we do not observe an overhead of chunk_end. Compiler optimized this iterator completely. PiperOrigin-RevId: 298458472 -- 327ea5e8910bc388b03389c730763f9823abfce5 by Abseil Team : Minor cleanups in b-tree code: - Rename some variables: fix issues of different param names between definition/declaration, move away from `x` as a default meaningless variable name. - Make init_leaf/init_internal be non-static methods (they already take the node as the first parameter). - In internal_emplace/try_shrink, update root/rightmost the same way as in insert_unique/insert_multi. - Replace a TODO with a comment. PiperOrigin-RevId: 298432836 -- 8020ce9ec8558ee712d9733ae3d660ac1d3ffe1a by Abseil Team : Guard against unnecessary copy in case the buffer is empty. This is important in cases were the user is explicitly tuning their chunks to match PiecewiseChunkSize(). PiperOrigin-RevId: 298366044 -- 89324441d1c0c697c90ba7d8fc63639805fcaa9d by Abseil Team : Internal change PiperOrigin-RevId: 298219363 GitOrigin-RevId: a3e58c1870a9626039f4d178d2d599319bd9f8a8 Change-Id: I28dffc684b6fd0292b94807b88ec6664d5d0e183 --- absl/base/log_severity_test.cc | 2 +- absl/container/btree_benchmark.cc | 24 +-- absl/container/btree_map.h | 4 +- absl/container/btree_set.h | 4 +- absl/container/btree_test.cc | 50 ++--- absl/container/internal/btree.h | 214 ++++++++++---------- absl/container/internal/btree_container.h | 42 ++-- absl/debugging/internal/stacktrace_win32-inl.inc | 12 +- absl/flags/BUILD.bazel | 4 + absl/flags/CMakeLists.txt | 3 + absl/flags/flag.h | 1 - absl/flags/flag_benchmark.cc | 8 + absl/flags/flag_test.cc | 143 ++++++++++---- absl/flags/internal/commandlineflag.cc | 30 +++ absl/flags/internal/commandlineflag.h | 6 +- absl/flags/internal/flag.cc | 107 +++++++--- absl/flags/internal/flag.h | 208 +++++++++---------- absl/hash/internal/hash.h | 15 +- absl/random/internal/BUILD.bazel | 1 + absl/status/status.cc | 8 + absl/status/status_test.cc | 57 ++++++ absl/strings/cord.cc | 242 +++++++++++------------ absl/strings/cord.h | 100 +++++++++- absl/strings/cord_test.cc | 56 ++++++ 24 files changed, 841 insertions(+), 500 deletions(-) create mode 100644 absl/flags/internal/commandlineflag.cc (limited to 'absl/status/status_test.cc') diff --git a/absl/base/log_severity_test.cc b/absl/base/log_severity_test.cc index 2302aa12..2c6872b0 100644 --- a/absl/base/log_severity_test.cc +++ b/absl/base/log_severity_test.cc @@ -53,7 +53,7 @@ TEST(StreamTest, Works) { } static_assert( - absl::flags_internal::IsAtomicFlagTypeTrait::value, + absl::flags_internal::FlagUseOneWordStorage::value, "Flags of type absl::LogSeverity ought to be lock-free."); using ParseFlagFromOutOfRangeIntegerTest = TestWithParam; diff --git a/absl/container/btree_benchmark.cc b/absl/container/btree_benchmark.cc index 4af92f9f..420cfa0d 100644 --- a/absl/container/btree_benchmark.cc +++ b/absl/container/btree_benchmark.cc @@ -538,19 +538,19 @@ struct BigType { BigType() : BigType(0) {} explicit BigType(int x) { std::iota(values.begin(), values.end(), x); } - void Copy(const BigType& x) { - for (int i = 0; i < Size && i < Copies; ++i) values[i] = x.values[i]; + void Copy(const BigType& other) { + for (int i = 0; i < Size && i < Copies; ++i) values[i] = other.values[i]; // If Copies > Size, do extra copies. for (int i = Size, idx = 0; i < Copies; ++i) { - int64_t tmp = x.values[idx]; + int64_t tmp = other.values[idx]; benchmark::DoNotOptimize(tmp); idx = idx + 1 == Size ? 0 : idx + 1; } } - BigType(const BigType& x) { Copy(x); } - BigType& operator=(const BigType& x) { - Copy(x); + BigType(const BigType& other) { Copy(other); } + BigType& operator=(const BigType& other) { + Copy(other); return *this; } @@ -641,14 +641,14 @@ struct BigTypePtr { explicit BigTypePtr(int x) { ptr = absl::make_unique>(x); } - BigTypePtr(const BigTypePtr& x) { - ptr = absl::make_unique>(*x.ptr); + BigTypePtr(const BigTypePtr& other) { + ptr = absl::make_unique>(*other.ptr); } - BigTypePtr(BigTypePtr&& x) noexcept = default; - BigTypePtr& operator=(const BigTypePtr& x) { - ptr = absl::make_unique>(*x.ptr); + BigTypePtr(BigTypePtr&& other) noexcept = default; + BigTypePtr& operator=(const BigTypePtr& other) { + ptr = absl::make_unique>(*other.ptr); } - BigTypePtr& operator=(BigTypePtr&& x) noexcept = default; + BigTypePtr& operator=(BigTypePtr&& other) noexcept = default; bool operator<(const BigTypePtr& other) const { return *ptr < *other.ptr; } bool operator==(const BigTypePtr& other) const { return *ptr == *other.ptr; } diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h index d23f4ee5..bb450ead 100644 --- a/absl/container/btree_map.h +++ b/absl/container/btree_map.h @@ -318,7 +318,7 @@ class btree_map // Extracts the element at the indicated position and returns a node handle // owning that extracted data. // - // template node_type extract(const K& x): + // template node_type extract(const K& k): // // Extracts the element with the key matching the passed key value and // returns a node handle owning that extracted data. If the `btree_map` @@ -645,7 +645,7 @@ class btree_multimap // Extracts the element at the indicated position and returns a node handle // owning that extracted data. // - // template node_type extract(const K& x): + // template node_type extract(const K& k): // // Extracts the element with the key matching the passed key value and // returns a node handle owning that extracted data. If the `btree_multimap` diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h index 127fb940..d3e78866 100644 --- a/absl/container/btree_set.h +++ b/absl/container/btree_set.h @@ -263,7 +263,7 @@ class btree_set // Extracts the element at the indicated position and returns a node handle // owning that extracted data. // - // template node_type extract(const K& x): + // template node_type extract(const K& k): // // Extracts the element with the key matching the passed key value and // returns a node handle owning that extracted data. If the `btree_set` @@ -567,7 +567,7 @@ class btree_multiset // Extracts the element at the indicated position and returns a node handle // owning that extracted data. // - // template node_type extract(const K& x): + // template node_type extract(const K& k): // // Extracts the element with the key matching the passed key value and // returns a node handle owning that extracted data. If the `btree_multiset` diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index 9edf38f9..ce12e819 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -89,8 +89,8 @@ class base_checker { public: base_checker() : const_tree_(tree_) {} - base_checker(const base_checker &x) - : tree_(x.tree_), const_tree_(tree_), checker_(x.checker_) {} + base_checker(const base_checker &other) + : tree_(other.tree_), const_tree_(tree_), checker_(other.checker_) {} template base_checker(InputIterator b, InputIterator e) : tree_(b, e), const_tree_(tree_), checker_(b, e) {} @@ -124,11 +124,11 @@ class base_checker { } return tree_iter; } - void value_check(const value_type &x) { + void value_check(const value_type &v) { typename KeyOfValue::type key_of_value; - const key_type &key = key_of_value(x); - CheckPairEquals(*find(key), x); + const key_type &key = key_of_value(v); + CheckPairEquals(*find(key), v); lower_bound(key); upper_bound(key); equal_range(key); @@ -187,9 +187,9 @@ class base_checker { return res; } - base_checker &operator=(const base_checker &x) { - tree_ = x.tree_; - checker_ = x.checker_; + base_checker &operator=(const base_checker &other) { + tree_ = other.tree_; + checker_ = other.checker_; return *this; } @@ -250,9 +250,9 @@ class base_checker { tree_.clear(); checker_.clear(); } - void swap(base_checker &x) { - tree_.swap(x.tree_); - checker_.swap(x.checker_); + void swap(base_checker &other) { + tree_.swap(other.tree_); + checker_.swap(other.checker_); } void verify() const { @@ -323,28 +323,28 @@ class unique_checker : public base_checker { public: unique_checker() : super_type() {} - unique_checker(const unique_checker &x) : super_type(x) {} + unique_checker(const unique_checker &other) : super_type(other) {} template unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {} unique_checker &operator=(const unique_checker &) = default; // Insertion routines. - std::pair insert(const value_type &x) { + std::pair insert(const value_type &v) { int size = this->tree_.size(); std::pair checker_res = - this->checker_.insert(x); - std::pair tree_res = this->tree_.insert(x); + this->checker_.insert(v); + std::pair tree_res = this->tree_.insert(v); CheckPairEquals(*tree_res.first, *checker_res.first); EXPECT_EQ(tree_res.second, checker_res.second); EXPECT_EQ(this->tree_.size(), this->checker_.size()); EXPECT_EQ(this->tree_.size(), size + tree_res.second); return tree_res; } - iterator insert(iterator position, const value_type &x) { + iterator insert(iterator position, const value_type &v) { int size = this->tree_.size(); std::pair checker_res = - this->checker_.insert(x); - iterator tree_res = this->tree_.insert(position, x); + this->checker_.insert(v); + iterator tree_res = this->tree_.insert(position, v); CheckPairEquals(*tree_res, *checker_res.first); EXPECT_EQ(this->tree_.size(), this->checker_.size()); EXPECT_EQ(this->tree_.size(), size + checker_res.second); @@ -371,25 +371,25 @@ class multi_checker : public base_checker { public: multi_checker() : super_type() {} - multi_checker(const multi_checker &x) : super_type(x) {} + multi_checker(const multi_checker &other) : super_type(other) {} template multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {} multi_checker &operator=(const multi_checker &) = default; // Insertion routines. - iterator insert(const value_type &x) { + iterator insert(const value_type &v) { int size = this->tree_.size(); - auto checker_res = this->checker_.insert(x); - iterator tree_res = this->tree_.insert(x); + auto checker_res = this->checker_.insert(v); + iterator tree_res = this->tree_.insert(v); CheckPairEquals(*tree_res, *checker_res); EXPECT_EQ(this->tree_.size(), this->checker_.size()); EXPECT_EQ(this->tree_.size(), size + 1); return tree_res; } - iterator insert(iterator position, const value_type &x) { + iterator insert(iterator position, const value_type &v) { int size = this->tree_.size(); - auto checker_res = this->checker_.insert(x); - iterator tree_res = this->tree_.insert(position, x); + auto checker_res = this->checker_.insert(v); + iterator tree_res = this->tree_.insert(position, v); CheckPairEquals(*tree_res, *checker_res); EXPECT_EQ(this->tree_.size(), this->checker_.size()); EXPECT_EQ(this->tree_.size(), size + 1); diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index fd5c0e7a..2a5c7314 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -252,9 +252,9 @@ struct map_params : common_paramssecond; } }; @@ -315,8 +315,8 @@ struct set_params : common_params struct upper_bound_adapter { explicit upper_bound_adapter(const Compare &c) : comp(c) {} - template - bool operator()(const K &a, const LK &b) const { + template + bool operator()(const K1 &a, const K2 &b) const { // Returns true when a is not greater than b. return !compare_internal::compare_result_as_less_than(comp(b, a)); } @@ -736,32 +736,28 @@ class btree_node { // Merges a node with its right sibling, moving all of the values and the // delimiting key in the parent node onto itself. - void merge(btree_node *sibling, allocator_type *alloc); + void merge(btree_node *src, allocator_type *alloc); - // Swap the contents of "this" and "src". - void swap(btree_node *src, allocator_type *alloc); + // Swaps the contents of `this` and `other`. + void swap(btree_node *other, allocator_type *alloc); // Node allocation/deletion routines. - static btree_node *init_leaf(btree_node *n, btree_node *parent, - int max_count) { - n->set_parent(parent); - n->set_position(0); - n->set_start(0); - n->set_finish(0); - n->set_max_count(max_count); + void init_leaf(btree_node *parent, int max_count) { + set_parent(parent); + set_position(0); + set_start(0); + set_finish(0); + set_max_count(max_count); absl::container_internal::SanitizerPoisonMemoryRegion( - n->start_slot(), max_count * sizeof(slot_type)); - return n; + start_slot(), max_count * sizeof(slot_type)); } - static btree_node *init_internal(btree_node *n, btree_node *parent) { - init_leaf(n, parent, kNodeValues); + void init_internal(btree_node *parent) { + init_leaf(parent, kNodeValues); // Set `max_count` to a sentinel value to indicate that this node is // internal. - n->set_max_count(kInternalNodeMaxCount); + set_max_count(kInternalNodeMaxCount); absl::container_internal::SanitizerPoisonMemoryRegion( - &n->mutable_child(n->start()), - (kNodeValues + 1) * sizeof(btree_node *)); - return n; + &mutable_child(start()), (kNodeValues + 1) * sizeof(btree_node *)); } void destroy(allocator_type *alloc) { for (int i = start(); i < finish(); ++i) { @@ -787,13 +783,13 @@ class btree_node { } // Move n values starting at value i in this node into the values starting at - // value j in node x. + // value j in dest_node. void uninitialized_move_n(const size_type n, const size_type i, - const size_type j, btree_node *x, + const size_type j, btree_node *dest_node, allocator_type *alloc) { absl::container_internal::SanitizerUnpoisonMemoryRegion( - x->slot(j), n * sizeof(slot_type)); - for (slot_type *src = slot(i), *end = src + n, *dest = x->slot(j); + dest_node->slot(j), n * sizeof(slot_type)); + for (slot_type *src = slot(i), *end = src + n, *dest = dest_node->slot(j); src != end; ++src, ++dest) { params_type::construct(alloc, dest, src); } @@ -856,8 +852,8 @@ struct btree_iterator { std::is_same, iterator>::value && std::is_same::value, int> = 0> - btree_iterator(const btree_iterator &x) // NOLINT - : node(x.node), position(x.position) {} + btree_iterator(const btree_iterator &other) // NOLINT + : node(other.node), position(other.position) {} private: // This SFINAE allows explicit conversions from const_iterator to @@ -869,8 +865,8 @@ struct btree_iterator { std::is_same, const_iterator>::value && std::is_same::value, int> = 0> - explicit btree_iterator(const btree_iterator &x) - : node(const_cast(x.node)), position(x.position) {} + explicit btree_iterator(const btree_iterator &other) + : node(const_cast(other.node)), position(other.position) {} // Increment/decrement the iterator. void increment() { @@ -890,11 +886,11 @@ struct btree_iterator { void decrement_slow(); public: - bool operator==(const const_iterator &x) const { - return node == x.node && position == x.position; + bool operator==(const const_iterator &other) const { + return node == other.node && position == other.position; } - bool operator!=(const const_iterator &x) const { - return node != x.node || position != x.position; + bool operator!=(const const_iterator &other) const { + return node != other.node || position != other.position; } // Accessors for the key/value the iterator is pointing at. @@ -942,7 +938,8 @@ struct btree_iterator { // The node in the tree the iterator is pointing at. Node *node; // The position within the node of the tree the iterator is pointing at. - // TODO(ezb): make this a field_type + // NOTE: this is an int rather than a field_type because iterators can point + // to invalid positions (such as -1) in certain circumstances. int position; }; @@ -994,9 +991,9 @@ class btree { node_stats(size_type l, size_type i) : leaf_nodes(l), internal_nodes(i) {} - node_stats &operator+=(const node_stats &x) { - leaf_nodes += x.leaf_nodes; - internal_nodes += x.internal_nodes; + node_stats &operator+=(const node_stats &other) { + leaf_nodes += other.leaf_nodes; + internal_nodes += other.internal_nodes; return *this; } @@ -1028,15 +1025,15 @@ class btree { private: // For use in copy_or_move_values_in_order. - const value_type &maybe_move_from_iterator(const_iterator x) { return *x; } - value_type &&maybe_move_from_iterator(iterator x) { return std::move(*x); } + const value_type &maybe_move_from_iterator(const_iterator it) { return *it; } + value_type &&maybe_move_from_iterator(iterator it) { return std::move(*it); } // Copies or moves (depending on the template parameter) the values in - // x into this btree in their order in x. This btree must be empty before this - // method is called. This method is used in copy construction, copy - // assignment, and move assignment. + // other into this btree in their order in other. This btree must be empty + // before this method is called. This method is used in copy construction, + // copy assignment, and move assignment. template - void copy_or_move_values_in_order(Btree *x); + void copy_or_move_values_in_order(Btree *other); // Validates that various assumptions/requirements are true at compile time. constexpr static bool static_assert_validation(); @@ -1044,12 +1041,12 @@ class btree { public: btree(const key_compare &comp, const allocator_type &alloc); - btree(const btree &x); - btree(btree &&x) noexcept - : root_(std::move(x.root_)), - rightmost_(absl::exchange(x.rightmost_, EmptyNode())), - size_(absl::exchange(x.size_, 0)) { - x.mutable_root() = EmptyNode(); + btree(const btree &other); + btree(btree &&other) noexcept + : root_(std::move(other.root_)), + rightmost_(absl::exchange(other.rightmost_, EmptyNode())), + size_(absl::exchange(other.size_, 0)) { + other.mutable_root() = EmptyNode(); } ~btree() { @@ -1059,9 +1056,9 @@ class btree { clear(); } - // Assign the contents of x to *this. - btree &operator=(const btree &x); - btree &operator=(btree &&x) noexcept; + // Assign the contents of other to *this. + btree &operator=(const btree &other); + btree &operator=(btree &&other) noexcept; iterator begin() { return iterator(leftmost()); } const_iterator begin() const { return const_iterator(leftmost()); } @@ -1204,15 +1201,15 @@ class btree { // Clear the btree, deleting all of the values it contains. void clear(); - // Swap the contents of *this and x. - void swap(btree &x); + // Swaps the contents of `this` and `other`. + void swap(btree &other); const key_compare &key_comp() const noexcept { return root_.template get<0>(); } - template - bool compare_keys(const K &x, const LK &y) const { - return compare_internal::compare_result_as_less_than(key_comp()(x, y)); + template + bool compare_keys(const K1 &a, const K2 &b) const { + return compare_internal::compare_result_as_less_than(key_comp()(a, b)); } value_compare value_comp() const { return value_compare(key_comp()); } @@ -1322,16 +1319,19 @@ class btree { // Node creation/deletion routines. node_type *new_internal_node(node_type *parent) { - node_type *p = allocate(node_type::InternalSize()); - return node_type::init_internal(p, parent); + node_type *n = allocate(node_type::InternalSize()); + n->init_internal(parent); + return n; } node_type *new_leaf_node(node_type *parent) { - node_type *p = allocate(node_type::LeafSize()); - return node_type::init_leaf(p, parent, kNodeValues); + node_type *n = allocate(node_type::LeafSize()); + n->init_leaf(parent, kNodeValues); + return n; } node_type *new_leaf_root_node(const int max_count) { - node_type *p = allocate(node_type::LeafSize(max_count)); - return node_type::init_leaf(p, p, max_count); + node_type *n = allocate(node_type::LeafSize(max_count)); + n->init_leaf(/*parent=*/n, max_count); + return n; } // Deletion helper routines. @@ -1715,12 +1715,12 @@ void btree_node

::merge(btree_node *src, allocator_type *alloc) { } template -void btree_node

::swap(btree_node *x, allocator_type *alloc) { +void btree_node

::swap(btree_node *other, allocator_type *alloc) { using std::swap; - assert(leaf() == x->leaf()); + assert(leaf() == other->leaf()); // Determine which is the smaller/larger node. - btree_node *smaller = this, *larger = x; + btree_node *smaller = this, *larger = other; if (smaller->count() > larger->count()) { swap(smaller, larger); } @@ -1759,7 +1759,7 @@ void btree_node

::swap(btree_node *x, allocator_type *alloc) { // Swap the `finish`s. // TODO(ezb): with floating storage, will also need to swap starts. - swap(mutable_finish(), x->mutable_finish()); + swap(mutable_finish(), other->mutable_finish()); } //// @@ -1814,7 +1814,7 @@ void btree_iterator::decrement_slow() { // btree methods template template -void btree

::copy_or_move_values_in_order(Btree *x) { +void btree

::copy_or_move_values_in_order(Btree *other) { static_assert(std::is_same::value || std::is_same::value, "Btree type must be same or const."); @@ -1822,11 +1822,11 @@ void btree

::copy_or_move_values_in_order(Btree *x) { // We can avoid key comparisons because we know the order of the // values is the same order we'll store them in. - auto iter = x->begin(); - if (iter == x->end()) return; + auto iter = other->begin(); + if (iter == other->end()) return; insert_multi(maybe_move_from_iterator(iter)); ++iter; - for (; iter != x->end(); ++iter) { + for (; iter != other->end(); ++iter) { // If the btree is not empty, we can just insert the new value at the end // of the tree. internal_emplace(end(), maybe_move_from_iterator(iter)); @@ -1869,8 +1869,9 @@ btree

::btree(const key_compare &comp, const allocator_type &alloc) : root_(comp, alloc, EmptyNode()), rightmost_(EmptyNode()), size_(0) {} template -btree

::btree(const btree &x) : btree(x.key_comp(), x.allocator()) { - copy_or_move_values_in_order(&x); +btree

::btree(const btree &other) + : btree(other.key_comp(), other.allocator()) { + copy_or_move_values_in_order(&other); } template @@ -1977,46 +1978,47 @@ void btree

::insert_iterator_multi(InputIterator b, InputIterator e) { } template -auto btree

::operator=(const btree &x) -> btree & { - if (this != &x) { +auto btree

::operator=(const btree &other) -> btree & { + if (this != &other) { clear(); - *mutable_key_comp() = x.key_comp(); + *mutable_key_comp() = other.key_comp(); if (absl::allocator_traits< allocator_type>::propagate_on_container_copy_assignment::value) { - *mutable_allocator() = x.allocator(); + *mutable_allocator() = other.allocator(); } - copy_or_move_values_in_order(&x); + copy_or_move_values_in_order(&other); } return *this; } template -auto btree

::operator=(btree &&x) noexcept -> btree & { - if (this != &x) { +auto btree

::operator=(btree &&other) noexcept -> btree & { + if (this != &other) { clear(); using std::swap; if (absl::allocator_traits< allocator_type>::propagate_on_container_copy_assignment::value) { // Note: `root_` also contains the allocator and the key comparator. - swap(root_, x.root_); - swap(rightmost_, x.rightmost_); - swap(size_, x.size_); + swap(root_, other.root_); + swap(rightmost_, other.rightmost_); + swap(size_, other.size_); } else { - if (allocator() == x.allocator()) { - swap(mutable_root(), x.mutable_root()); - swap(*mutable_key_comp(), *x.mutable_key_comp()); - swap(rightmost_, x.rightmost_); - swap(size_, x.size_); + if (allocator() == other.allocator()) { + swap(mutable_root(), other.mutable_root()); + swap(*mutable_key_comp(), *other.mutable_key_comp()); + swap(rightmost_, other.rightmost_); + swap(size_, other.size_); } else { // We aren't allowed to propagate the allocator and the allocator is // different so we can't take over its memory. We must move each element - // individually. We need both `x` and `this` to have `x`s key comparator - // while moving the values so we can't swap the key comparators. - *mutable_key_comp() = x.key_comp(); - copy_or_move_values_in_order(&x); + // individually. We need both `other` and `this` to have `other`s key + // comparator while moving the values so we can't swap the key + // comparators. + *mutable_key_comp() = other.key_comp(); + copy_or_move_values_in_order(&other); } } } @@ -2215,20 +2217,20 @@ void btree

::clear() { } template -void btree

::swap(btree &x) { +void btree

::swap(btree &other) { using std::swap; if (absl::allocator_traits< allocator_type>::propagate_on_container_swap::value) { // Note: `root_` also contains the allocator and the key comparator. - swap(root_, x.root_); + swap(root_, other.root_); } else { // It's undefined behavior if the allocators are unequal here. - assert(allocator() == x.allocator()); - swap(mutable_root(), x.mutable_root()); - swap(*mutable_key_comp(), *x.mutable_key_comp()); + assert(allocator() == other.allocator()); + swap(mutable_root(), other.mutable_root()); + swap(*mutable_key_comp(), *other.mutable_key_comp()); } - swap(rightmost_, x.rightmost_); - swap(size_, x.size_); + swap(rightmost_, other.rightmost_); + swap(size_, other.size_); } template @@ -2417,8 +2419,7 @@ void btree

::try_shrink() { if (root()->leaf()) { assert(size() == 0); delete_leaf_node(root()); - mutable_root() = EmptyNode(); - rightmost_ = EmptyNode(); + mutable_root() = rightmost_ = EmptyNode(); } else { node_type *child = root()->start_child(); child->make_root(); @@ -2463,8 +2464,7 @@ inline auto btree

::internal_emplace(iterator iter, Args &&... args) new_leaf_root_node((std::min)(kNodeValues, 2 * max_count)); iter.node->swap(root(), mutable_allocator()); delete_leaf_node(root()); - mutable_root() = iter.node; - rightmost_ = iter.node; + mutable_root() = rightmost_ = iter.node; } else { rebalance_or_split(&iter); } diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index f2e4c3a5..734c90ef 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h @@ -68,10 +68,10 @@ class btree_container { explicit btree_container(const key_compare &comp, const allocator_type &alloc = allocator_type()) : tree_(comp, alloc) {} - btree_container(const btree_container &x) = default; - btree_container(btree_container &&x) noexcept = default; - btree_container &operator=(const btree_container &x) = default; - btree_container &operator=(btree_container &&x) noexcept( + btree_container(const btree_container &other) = default; + btree_container(btree_container &&other) noexcept = default; + btree_container &operator=(const btree_container &other) = default; + btree_container &operator=(btree_container &&other) noexcept( std::is_nothrow_move_assignable::value) = default; // Iterator routines. @@ -154,7 +154,7 @@ class btree_container { public: // Utility routines. void clear() { tree_.clear(); } - void swap(btree_container &x) { tree_.swap(x.tree_); } + void swap(btree_container &other) { tree_.swap(other.tree_); } void verify() const { tree_.verify(); } // Size routines. @@ -257,26 +257,26 @@ class btree_set_container : public btree_container { } // Insertion routines. - std::pair insert(const value_type &x) { - return this->tree_.insert_unique(params_type::key(x), x); + std::pair insert(const value_type &v) { + return this->tree_.insert_unique(params_type::key(v), v); } - std::pair insert(value_type &&x) { - return this->tree_.insert_unique(params_type::key(x), std::move(x)); + std::pair insert(value_type &&v) { + return this->tree_.insert_unique(params_type::key(v), std::move(v)); } template std::pair emplace(Args &&... args) { init_type v(std::forward(args)...); return this->tree_.insert_unique(params_type::key(v), std::move(v)); } - iterator insert(const_iterator position, const value_type &x) { + iterator insert(const_iterator position, const value_type &v) { return this->tree_ - .insert_hint_unique(iterator(position), params_type::key(x), x) + .insert_hint_unique(iterator(position), params_type::key(v), v) .first; } - iterator insert(const_iterator position, value_type &&x) { + iterator insert(const_iterator position, value_type &&v) { return this->tree_ - .insert_hint_unique(iterator(position), params_type::key(x), - std::move(x)) + .insert_hint_unique(iterator(position), params_type::key(v), + std::move(v)) .first; } template @@ -562,15 +562,15 @@ class btree_multiset_container : public btree_container { } // Insertion routines. - iterator insert(const value_type &x) { return this->tree_.insert_multi(x); } - iterator insert(value_type &&x) { - return this->tree_.insert_multi(std::move(x)); + iterator insert(const value_type &v) { return this->tree_.insert_multi(v); } + iterator insert(value_type &&v) { + return this->tree_.insert_multi(std::move(v)); } - iterator insert(const_iterator position, const value_type &x) { - return this->tree_.insert_hint_multi(iterator(position), x); + iterator insert(const_iterator position, const value_type &v) { + return this->tree_.insert_hint_multi(iterator(position), v); } - iterator insert(const_iterator position, value_type &&x) { - return this->tree_.insert_hint_multi(iterator(position), std::move(x)); + iterator insert(const_iterator position, value_type &&v) { + return this->tree_.insert_hint_multi(iterator(position), std::move(v)); } template void insert(InputIterator b, InputIterator e) { diff --git a/absl/debugging/internal/stacktrace_win32-inl.inc b/absl/debugging/internal/stacktrace_win32-inl.inc index af4578a5..1c666c8b 100644 --- a/absl/debugging/internal/stacktrace_win32-inl.inc +++ b/absl/debugging/internal/stacktrace_win32-inl.inc @@ -46,9 +46,9 @@ typedef USHORT NTAPI RtlCaptureStackBackTrace_Function( OUT PVOID *backtrace, OUT PULONG backtrace_hash); -// It is not possible to load RtlCaptureStackBackTrace at static init time in -// UWP. CaptureStackBackTrace is the public version of RtlCaptureStackBackTrace -#if WINAPI_FAMILY_PARTITION(WINAPI_PARTITION_APP) && \ +// It is not possible to load RtlCaptureStackBackTrace at static init time in +// UWP. CaptureStackBackTrace is the public version of RtlCaptureStackBackTrace +#if WINAPI_FAMILY_PARTITION(WINAPI_PARTITION_APP) && \ !WINAPI_FAMILY_PARTITION(WINAPI_PARTITION_DESKTOP) static RtlCaptureStackBackTrace_Function* const RtlCaptureStackBackTrace_fn = &::CaptureStackBackTrace; @@ -56,9 +56,9 @@ static RtlCaptureStackBackTrace_Function* const RtlCaptureStackBackTrace_fn = // Load the function we need at static init time, where we don't have // to worry about someone else holding the loader's lock. static RtlCaptureStackBackTrace_Function* const RtlCaptureStackBackTrace_fn = - (RtlCaptureStackBackTrace_Function*) - GetProcAddress(GetModuleHandleA("ntdll.dll"), "RtlCaptureStackBackTrace"); -#endif // WINAPI_PARTITION_APP && !WINAPI_PARTITION_DESKTOP + (RtlCaptureStackBackTrace_Function*)GetProcAddress( + GetModuleHandleA("ntdll.dll"), "RtlCaptureStackBackTrace"); +#endif // WINAPI_PARTITION_APP && !WINAPI_PARTITION_DESKTOP template static int UnwindImpl(void** result, int* sizes, int max_depth, int skip_count, diff --git a/absl/flags/BUILD.bazel b/absl/flags/BUILD.bazel index cdb4e7e8..9166f74c 100644 --- a/absl/flags/BUILD.bazel +++ b/absl/flags/BUILD.bazel @@ -45,6 +45,7 @@ cc_library( "//absl/base:config", "//absl/base:core_headers", "//absl/memory", + "//absl/meta:type_traits", "//absl/strings", "//absl/synchronization", ], @@ -130,6 +131,9 @@ cc_library( cc_library( name = "handle", + srcs = [ + "internal/commandlineflag.cc", + ], hdrs = [ "internal/commandlineflag.h", ], diff --git a/absl/flags/CMakeLists.txt b/absl/flags/CMakeLists.txt index 1d25f0de..01cf09b1 100644 --- a/absl/flags/CMakeLists.txt +++ b/absl/flags/CMakeLists.txt @@ -33,6 +33,7 @@ absl_cc_library( absl::flags_handle absl::flags_registry absl::synchronization + absl::meta PUBLIC ) @@ -117,6 +118,8 @@ absl_cc_library( absl_cc_library( NAME flags_handle + SRCS + "internal/commandlineflag.cc" HDRS "internal/commandlineflag.h" COPTS diff --git a/absl/flags/flag.h b/absl/flags/flag.h index cff02c1f..bb917654 100644 --- a/absl/flags/flag.h +++ b/absl/flags/flag.h @@ -148,7 +148,6 @@ class Flag { return GetImpl()->template IsOfType(); } T Get() const { return GetImpl()->Get(); } - bool AtomicGet(T* v) const { return GetImpl()->AtomicGet(v); } void Set(const T& v) { GetImpl()->Set(v); } void SetCallback(const flags_internal::FlagCallbackFunc mutation_callback) { GetImpl()->SetCallback(mutation_callback); diff --git a/absl/flags/flag_benchmark.cc b/absl/flags/flag_benchmark.cc index 87f73170..ff95bb5d 100644 --- a/absl/flags/flag_benchmark.cc +++ b/absl/flags/flag_benchmark.cc @@ -109,3 +109,11 @@ namespace { BENCHMARKED_TYPES(BM_GetFlag) } // namespace + +#define InvokeGetFlag(T) \ + T AbslInvokeGetFlag##T() { return absl::GetFlag(FLAGS_##T##_flag); } \ + int odr##T = (benchmark::DoNotOptimize(AbslInvokeGetFlag##T), 1); + +BENCHMARKED_TYPES(InvokeGetFlag) + +// To veiw disassembly use: gdb ${BINARY} -batch -ex "disassemble /s $FUNC" diff --git a/absl/flags/flag_test.cc b/absl/flags/flag_test.cc index 4984d284..1e01b49c 100644 --- a/absl/flags/flag_test.cc +++ b/absl/flags/flag_test.cc @@ -49,28 +49,6 @@ void* TestMakeDflt() { } void TestCallback() {} -template -bool TestConstructionFor() { - constexpr flags::FlagHelpArg help_arg{flags::FlagHelpMsg("literal help"), - flags::FlagHelpKind::kLiteral}; - constexpr flags::Flag f1("f1", "file", help_arg, &TestMakeDflt); - EXPECT_EQ(f1.Name(), "f1"); - EXPECT_EQ(f1.Help(), "literal help"); - EXPECT_EQ(f1.Filename(), "file"); - - ABSL_CONST_INIT static flags::Flag f2( - "f2", "file", - {flags::FlagHelpMsg(&TestHelpMsg), flags::FlagHelpKind::kGenFunc}, - &TestMakeDflt); - flags::FlagRegistrar(&f2).OnUpdate(TestCallback); - - EXPECT_EQ(f2.Name(), "f2"); - EXPECT_EQ(f2.Help(), "dynamic help"); - EXPECT_EQ(f2.Filename(), "file"); - - return true; -} - struct UDT { UDT() = default; UDT(const UDT&) = default; @@ -98,19 +76,103 @@ class FlagTest : public testing::Test { } }; +struct S1 { + S1() = default; + S1(const S1&) = default; + int32_t f1; + int64_t f2; +}; + +struct S2 { + S2() = default; + S2(const S2&) = default; + int64_t f1; + double f2; +}; + +TEST_F(FlagTest, Traits) { + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kOneWordAtomic); + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kOneWordAtomic); + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kOneWordAtomic); + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kOneWordAtomic); + +#if defined(ABSL_FLAGS_INTERNAL_ATOMIC_DOUBLE_WORD) + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kTwoWordsAtomic); + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kTwoWordsAtomic); +#else + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kHeapAllocated); + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kHeapAllocated); +#endif + + EXPECT_EQ(flags::FlagValue::Kind(), + flags::FlagValueStorageKind::kHeapAllocated); + EXPECT_EQ(flags::FlagValue::Kind>(), + flags::FlagValueStorageKind::kHeapAllocated); +} + +// -------------------------------------------------------------------- + +constexpr flags::FlagHelpArg help_arg{flags::FlagHelpMsg("literal help"), + flags::FlagHelpKind::kLiteral}; + +using String = std::string; + +#define DEFINE_CONSTRUCTED_FLAG(T) \ + constexpr flags::Flag f1##T("f1", "file", help_arg, &TestMakeDflt); \ + ABSL_CONST_INIT flags::Flag f2##T( \ + "f2", "file", \ + {flags::FlagHelpMsg(&TestHelpMsg), flags::FlagHelpKind::kGenFunc}, \ + &TestMakeDflt) + +#define TEST_CONSTRUCTED_FLAG(T) TestConstructionFor(f1##T, &f2##T); + +DEFINE_CONSTRUCTED_FLAG(bool); +DEFINE_CONSTRUCTED_FLAG(int16_t); +DEFINE_CONSTRUCTED_FLAG(uint16_t); +DEFINE_CONSTRUCTED_FLAG(int32_t); +DEFINE_CONSTRUCTED_FLAG(uint32_t); +DEFINE_CONSTRUCTED_FLAG(int64_t); +DEFINE_CONSTRUCTED_FLAG(uint64_t); +DEFINE_CONSTRUCTED_FLAG(float); +DEFINE_CONSTRUCTED_FLAG(double); +DEFINE_CONSTRUCTED_FLAG(String); +DEFINE_CONSTRUCTED_FLAG(UDT); + +template +bool TestConstructionFor(const flags::Flag& f1, flags::Flag* f2) { + EXPECT_EQ(f1.Name(), "f1"); + EXPECT_EQ(f1.Help(), "literal help"); + EXPECT_EQ(f1.Filename(), "file"); + + flags::FlagRegistrar(f2).OnUpdate(TestCallback); + + EXPECT_EQ(f2->Name(), "f2"); + EXPECT_EQ(f2->Help(), "dynamic help"); + EXPECT_EQ(f2->Filename(), "file"); + + return true; +} + TEST_F(FlagTest, TestConstruction) { - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - TestConstructionFor(); - - TestConstructionFor(); + TEST_CONSTRUCTED_FLAG(bool); + TEST_CONSTRUCTED_FLAG(int16_t); + TEST_CONSTRUCTED_FLAG(uint16_t); + TEST_CONSTRUCTED_FLAG(int32_t); + TEST_CONSTRUCTED_FLAG(uint32_t); + TEST_CONSTRUCTED_FLAG(int64_t); + TEST_CONSTRUCTED_FLAG(uint64_t); + TEST_CONSTRUCTED_FLAG(float); + TEST_CONSTRUCTED_FLAG(double); + TEST_CONSTRUCTED_FLAG(String); + TEST_CONSTRUCTED_FLAG(UDT); } // -------------------------------------------------------------------- @@ -391,17 +453,18 @@ TEST_F(FlagTest, TestCustomUDT) { using FlagDeathTest = FlagTest; TEST_F(FlagDeathTest, TestTypeMismatchValidations) { - EXPECT_DEBUG_DEATH( - static_cast(absl::GetFlag(FLAGS_mistyped_int_flag)), - "Flag 'mistyped_int_flag' is defined as one type and declared " - "as another"); - EXPECT_DEATH(absl::SetFlag(&FLAGS_mistyped_int_flag, 1), +#if !defined(NDEBUG) + EXPECT_DEATH(static_cast(absl::GetFlag(FLAGS_mistyped_int_flag)), "Flag 'mistyped_int_flag' is defined as one type and declared " "as another"); - EXPECT_DEATH(static_cast(absl::GetFlag(FLAGS_mistyped_string_flag)), "Flag 'mistyped_string_flag' is defined as one type and " "declared as another"); +#endif + + EXPECT_DEATH(absl::SetFlag(&FLAGS_mistyped_int_flag, 1), + "Flag 'mistyped_int_flag' is defined as one type and declared " + "as another"); EXPECT_DEATH( absl::SetFlag(&FLAGS_mistyped_string_flag, std::vector{}), "Flag 'mistyped_string_flag' is defined as one type and declared as " diff --git a/absl/flags/internal/commandlineflag.cc b/absl/flags/internal/commandlineflag.cc new file mode 100644 index 00000000..90765a3e --- /dev/null +++ b/absl/flags/internal/commandlineflag.cc @@ -0,0 +1,30 @@ +// +// Copyright 2020 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/flags/internal/commandlineflag.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace flags_internal { + +FlagStateInterface::~FlagStateInterface() {} + +bool CommandLineFlag::IsRetired() const { return false; } +bool CommandLineFlag::IsAbseilFlag() const { return true; } + +} // namespace flags_internal +ABSL_NAMESPACE_END +} // namespace absl + diff --git a/absl/flags/internal/commandlineflag.h b/absl/flags/internal/commandlineflag.h index 6363c661..e91ddde6 100644 --- a/absl/flags/internal/commandlineflag.h +++ b/absl/flags/internal/commandlineflag.h @@ -77,7 +77,7 @@ enum ValueSource { // of a flag produced this flag state from method CommandLineFlag::SaveState(). class FlagStateInterface { public: - virtual ~FlagStateInterface() {} + virtual ~FlagStateInterface(); // Restores the flag originated this object to the saved state. virtual void Restore() const = 0; @@ -146,9 +146,9 @@ class CommandLineFlag { // Returns help message associated with this flag. virtual std::string Help() const = 0; // Returns true iff this object corresponds to retired flag. - virtual bool IsRetired() const { return false; } + virtual bool IsRetired() const; // Returns true iff this is a handle to an Abseil Flag. - virtual bool IsAbseilFlag() const { return true; } + virtual bool IsAbseilFlag() const; // Returns id of the flag's value type. virtual FlagStaticTypeId TypeId() const = 0; virtual bool IsModified() const = 0; diff --git a/absl/flags/internal/flag.cc b/absl/flags/internal/flag.cc index 5a921e28..a944e16e 100644 --- a/absl/flags/internal/flag.cc +++ b/absl/flags/internal/flag.cc @@ -77,19 +77,33 @@ class MutexRelock { void FlagImpl::Init() { new (&data_guard_) absl::Mutex; - absl::MutexLock lock(reinterpret_cast(&data_guard_)); - - value_.dynamic = MakeInitValue().release(); - StoreAtomic(); + // At this point the default_value_ always points to gen_func. + std::unique_ptr init_value( + (*default_value_.gen_func)(), DynValueDeleter{op_}); + switch (ValueStorageKind()) { + case FlagValueStorageKind::kHeapAllocated: + value_.dynamic = init_value.release(); + break; + case FlagValueStorageKind::kOneWordAtomic: { + int64_t atomic_value; + std::memcpy(&atomic_value, init_value.get(), Sizeof(op_)); + value_.one_word_atomic.store(atomic_value, std::memory_order_release); + break; + } + case FlagValueStorageKind::kTwoWordsAtomic: { + AlignedTwoWords atomic_value{0, 0}; + std::memcpy(&atomic_value, init_value.get(), Sizeof(op_)); + value_.two_words_atomic.store(atomic_value, std::memory_order_release); + break; + } + } } -// Ensures that the lazily initialized data is initialized, -// and returns pointer to the mutex guarding flags data. absl::Mutex* FlagImpl::DataGuard() const { absl::call_once(const_cast(this)->init_control_, &FlagImpl::Init, const_cast(this)); - // data_guard_ is initialized. + // data_guard_ is initialized inside Init. return reinterpret_cast(&data_guard_); } @@ -129,8 +143,24 @@ std::unique_ptr FlagImpl::MakeInitValue() const { } void FlagImpl::StoreValue(const void* src) { - flags_internal::Copy(op_, src, value_.dynamic); - StoreAtomic(); + switch (ValueStorageKind()) { + case FlagValueStorageKind::kHeapAllocated: + Copy(op_, src, value_.dynamic); + break; + case FlagValueStorageKind::kOneWordAtomic: { + int64_t one_word_val; + std::memcpy(&one_word_val, src, Sizeof(op_)); + value_.one_word_atomic.store(one_word_val, std::memory_order_release); + break; + } + case FlagValueStorageKind::kTwoWordsAtomic: { + AlignedTwoWords two_words_val{0, 0}; + std::memcpy(&two_words_val, src, Sizeof(op_)); + value_.two_words_atomic.store(two_words_val, std::memory_order_release); + break; + } + } + modified_ = true; ++counter_; InvokeCallback(); @@ -165,9 +195,25 @@ std::string FlagImpl::DefaultValue() const { } std::string FlagImpl::CurrentValue() const { - absl::MutexLock l(DataGuard()); + DataGuard(); // Make sure flag initialized + switch (ValueStorageKind()) { + case FlagValueStorageKind::kHeapAllocated: { + absl::MutexLock l(DataGuard()); + return flags_internal::Unparse(op_, value_.dynamic); + } + case FlagValueStorageKind::kOneWordAtomic: { + const auto one_word_val = + value_.one_word_atomic.load(std::memory_order_acquire); + return flags_internal::Unparse(op_, &one_word_val); + } + case FlagValueStorageKind::kTwoWordsAtomic: { + const auto two_words_val = + value_.two_words_atomic.load(std::memory_order_acquire); + return flags_internal::Unparse(op_, &two_words_val); + } + } - return flags_internal::Unparse(op_, value_.dynamic); + return ""; } void FlagImpl::SetCallback(const FlagCallbackFunc mutation_callback) { @@ -244,26 +290,27 @@ std::unique_ptr FlagImpl::TryParse( } void FlagImpl::Read(void* dst) const { - absl::ReaderMutexLock l(DataGuard()); + DataGuard(); // Make sure flag initialized + switch (ValueStorageKind()) { + case FlagValueStorageKind::kHeapAllocated: { + absl::MutexLock l(DataGuard()); - flags_internal::CopyConstruct(op_, value_.dynamic, dst); -} - -void FlagImpl::StoreAtomic() { - size_t data_size = flags_internal::Sizeof(op_); - - if (data_size <= sizeof(int64_t)) { - int64_t t = 0; - std::memcpy(&t, value_.dynamic, data_size); - value_.atomics.small_atomic.store(t, std::memory_order_release); - } -#if defined(ABSL_FLAGS_INTERNAL_ATOMIC_DOUBLE_WORD) - else if (data_size <= sizeof(FlagsInternalTwoWordsType)) { - FlagsInternalTwoWordsType t{0, 0}; - std::memcpy(&t, value_.dynamic, data_size); - value_.atomics.big_atomic.store(t, std::memory_order_release); + flags_internal::CopyConstruct(op_, value_.dynamic, dst); + break; + } + case FlagValueStorageKind::kOneWordAtomic: { + const auto one_word_val = + value_.one_word_atomic.load(std::memory_order_acquire); + std::memcpy(dst, &one_word_val, Sizeof(op_)); + break; + } + case FlagValueStorageKind::kTwoWordsAtomic: { + const auto two_words_val = + value_.two_words_atomic.load(std::memory_order_acquire); + std::memcpy(dst, &two_words_val, Sizeof(op_)); + break; + } } -#endif } void FlagImpl::Write(const void* src) { @@ -339,7 +386,7 @@ bool FlagImpl::SetFromString(absl::string_view value, FlagSettingMode set_mode, } if (!modified_) { - // Need to set both default value *and* current, in this case + // Need to set both default value *and* current, in this case. StoreValue(default_value_.dynamic_value); modified_ = false; } diff --git a/absl/flags/internal/flag.h b/absl/flags/internal/flag.h index 35a148cf..307b7377 100644 --- a/absl/flags/internal/flag.h +++ b/absl/flags/internal/flag.h @@ -31,6 +31,7 @@ #include "absl/flags/internal/commandlineflag.h" #include "absl/flags/internal/registry.h" #include "absl/memory/memory.h" +#include "absl/meta/type_traits.h" #include "absl/strings/str_cat.h" #include "absl/strings/string_view.h" #include "absl/synchronization/mutex.h" @@ -249,95 +250,66 @@ enum class FlagDefaultKind : uint8_t { kDynamicValue = 0, kGenFunc = 1 }; /////////////////////////////////////////////////////////////////////////////// // Flag current value auxiliary structs. -// The minimum atomic size we believe to generate lock free code, i.e. all -// trivially copyable types not bigger this size generate lock free code. -static constexpr int kMinLockFreeAtomicSize = 8; +constexpr int64_t UninitializedFlagValue() { return 0xababababababababll; } -// The same as kMinLockFreeAtomicSize but maximum atomic size. As double words -// might use two registers, we want to dispatch the logic for them. -#if defined(ABSL_FLAGS_INTERNAL_ATOMIC_DOUBLE_WORD) -static constexpr int kMaxLockFreeAtomicSize = 16; -#else -static constexpr int kMaxLockFreeAtomicSize = 8; -#endif - -// We can use atomic in cases when it fits in the register, trivially copyable -// in order to make memcpy operations. template -struct IsAtomicFlagTypeTrait { - static constexpr bool value = - (sizeof(T) <= kMaxLockFreeAtomicSize && - type_traits_internal::is_trivially_copyable::value); -}; +using FlagUseOneWordStorage = std::integral_constant< + bool, absl::type_traits_internal::is_trivially_copyable::value && + (sizeof(T) <= 8)>; +#if defined(ABSL_FLAGS_INTERNAL_ATOMIC_DOUBLE_WORD) // Clang does not always produce cmpxchg16b instruction when alignment of a 16 // bytes type is not 16. -struct alignas(16) FlagsInternalTwoWordsType { +struct alignas(16) AlignedTwoWords { int64_t first; int64_t second; }; -constexpr bool operator==(const FlagsInternalTwoWordsType& that, - const FlagsInternalTwoWordsType& other) { - return that.first == other.first && that.second == other.second; -} -constexpr bool operator!=(const FlagsInternalTwoWordsType& that, - const FlagsInternalTwoWordsType& other) { - return !(that == other); -} - -constexpr int64_t SmallAtomicInit() { return 0xababababababababll; } - -template -struct BestAtomicType { - using type = int64_t; - static constexpr int64_t AtomicInit() { return SmallAtomicInit(); } +template +using FlagUseTwoWordsStorage = std::integral_constant< + bool, absl::type_traits_internal::is_trivially_copyable::value && + (sizeof(T) > 8) && (sizeof(T) <= 16)>; +#else +// This is actually unused and only here to avoid ifdefs in other palces. +struct AlignedTwoWords { + constexpr AlignedTwoWords() = default; + constexpr AlignedTwoWords(int64_t, int64_t) {} }; +// This trait should be type dependent, otherwise SFINAE below will fail template -struct BestAtomicType< - T, typename std::enable_if<(kMinLockFreeAtomicSize < sizeof(T) && - sizeof(T) <= kMaxLockFreeAtomicSize), - void>::type> { - using type = FlagsInternalTwoWordsType; - static constexpr FlagsInternalTwoWordsType AtomicInit() { - return {SmallAtomicInit(), SmallAtomicInit()}; - } +using FlagUseTwoWordsStorage = + std::integral_constant; +#endif + +template +using FlagUseHeapStorage = + std::integral_constant::value && + !FlagUseTwoWordsStorage::value>; + +enum class FlagValueStorageKind : uint8_t { + kHeapAllocated = 0, + kOneWordAtomic = 1, + kTwoWordsAtomic = 2 }; -struct FlagValue { - // Heap allocated value. - void* dynamic = nullptr; - // For some types, a copy of the current value is kept in an atomically - // accessible field. - union Atomics { - // Using small atomic for small types. - std::atomic small_atomic; - template ::type> - int64_t load() const { - return small_atomic.load(std::memory_order_acquire); - } +union FlagValue { + constexpr explicit FlagValue(int64_t v) : one_word_atomic(v) {} -#if defined(ABSL_FLAGS_INTERNAL_ATOMIC_DOUBLE_WORD) - // Using big atomics for big types. - std::atomic big_atomic; - template ::type> - FlagsInternalTwoWordsType load() const { - return big_atomic.load(std::memory_order_acquire); - } - constexpr Atomics() - : big_atomic{FlagsInternalTwoWordsType{SmallAtomicInit(), - SmallAtomicInit()}} {} -#else - constexpr Atomics() : small_atomic{SmallAtomicInit()} {} -#endif - }; - Atomics atomics{}; + template + static constexpr FlagValueStorageKind Kind() { + return FlagUseHeapStorage::value + ? FlagValueStorageKind::kHeapAllocated + : FlagUseOneWordStorage::value + ? FlagValueStorageKind::kOneWordAtomic + : FlagUseTwoWordsStorage::value + ? FlagValueStorageKind::kTwoWordsAtomic + : FlagValueStorageKind::kHeapAllocated; + } + + void* dynamic; + std::atomic one_word_atomic; + std::atomic two_words_atomic; }; /////////////////////////////////////////////////////////////////////////////// @@ -369,18 +341,21 @@ struct DynValueDeleter { class FlagImpl { public: constexpr FlagImpl(const char* name, const char* filename, FlagOpFn op, - FlagHelpArg help, FlagDfltGenFunc default_value_gen) + FlagHelpArg help, FlagValueStorageKind value_kind, + FlagDfltGenFunc default_value_gen) : name_(name), filename_(filename), op_(op), help_(help.source), help_source_kind_(static_cast(help.kind)), + value_storage_kind_(static_cast(value_kind)), def_kind_(static_cast(FlagDefaultKind::kGenFunc)), modified_(false), on_command_line_(false), counter_(0), callback_(nullptr), default_value_(default_value_gen), + value_(flags_internal::UninitializedFlagValue()), data_guard_{} {} // Constant access methods @@ -393,34 +368,29 @@ class FlagImpl { std::string CurrentValue() const ABSL_LOCKS_EXCLUDED(*DataGuard()); void Read(void* dst) const ABSL_LOCKS_EXCLUDED(*DataGuard()); - template ::value, int>::type = 0> + template ::value, + int>::type = 0> void Get(T* dst) const { - AssertValidType(&flags_internal::FlagStaticTypeIdGen); Read(dst); } - // Overload for `GetFlag()` for types that support lock-free reads. - template ::value, + template ::value, int>::type = 0> void Get(T* dst) const { - // For flags of types which can be accessed "atomically" we want to avoid - // slowing down flag value access due to type validation. That's why - // this validation is hidden behind !NDEBUG -#ifndef NDEBUG - AssertValidType(&flags_internal::FlagStaticTypeIdGen); -#endif - using U = flags_internal::BestAtomicType; - typename U::type r = value_.atomics.template load(); - if (r != U::AtomicInit()) { - std::memcpy(static_cast(dst), &r, sizeof(T)); - } else { - Read(dst); + int64_t one_word_val = + value_.one_word_atomic.load(std::memory_order_acquire); + if (ABSL_PREDICT_FALSE(one_word_val == UninitializedFlagValue())) { + DataGuard(); // Make sure flag initialized + one_word_val = value_.one_word_atomic.load(std::memory_order_acquire); } + std::memcpy(dst, static_cast(&one_word_val), sizeof(T)); } - template - void Set(const T& src) { - AssertValidType(&flags_internal::FlagStaticTypeIdGen); - Write(&src); + template ::value, int>::type = 0> + void Get(T* dst) const { + DataGuard(); // Make sure flag initialized + const auto two_words_val = + value_.two_words_atomic.load(std::memory_order_acquire); + std::memcpy(dst, &two_words_val, sizeof(T)); } // Mutating access methods @@ -428,9 +398,6 @@ class FlagImpl { bool SetFromString(absl::string_view value, FlagSettingMode set_mode, ValueSource source, std::string* err) ABSL_LOCKS_EXCLUDED(*DataGuard()); - // If possible, updates copy of the Flag's value that is stored in an - // atomic word. - void StoreAtomic() ABSL_EXCLUSIVE_LOCKS_REQUIRED(*DataGuard()); // Interfaces to operate on callbacks. void SetCallback(const FlagCallbackFunc mutation_callback) @@ -456,6 +423,14 @@ class FlagImpl { bool ValidateInputValue(absl::string_view value) const ABSL_LOCKS_EXCLUDED(*DataGuard()); + // Used in read/write operations to validate source/target has correct type. + // For example if flag is declared as absl::Flag FLAGS_foo, a call to + // absl::GetFlag(FLAGS_foo) validates that the type of FLAGS_foo is indeed + // int. To do that we pass the "assumed" type id (which is deduced from type + // int) as an argument `op`, which is in turn is validated against the type id + // stored in flag object by flag definition statement. + void AssertValidType(FlagStaticTypeId type_id) const; + private: // Ensures that `data_guard_` is initialized and returns it. absl::Mutex* DataGuard() const ABSL_LOCK_RETURNED((absl::Mutex*)&data_guard_); @@ -475,17 +450,13 @@ class FlagImpl { FlagHelpKind HelpSourceKind() const { return static_cast(help_source_kind_); } + FlagValueStorageKind ValueStorageKind() const { + return static_cast(value_storage_kind_); + } FlagDefaultKind DefaultKind() const ABSL_EXCLUSIVE_LOCKS_REQUIRED(*DataGuard()) { return static_cast(def_kind_); } - // Used in read/write operations to validate source/target has correct type. - // For example if flag is declared as absl::Flag FLAGS_foo, a call to - // absl::GetFlag(FLAGS_foo) validates that the type of FLAGS_foo is indeed - // int. To do that we pass the "assumed" type id (which is deduced from type - // int) as an argument `op`, which is in turn is validated against the type id - // stored in flag object by flag definition statement. - void AssertValidType(FlagStaticTypeId type_id) const; // Immutable flag's state. @@ -499,6 +470,8 @@ class FlagImpl { const FlagHelpMsg help_; // Indicates if help message was supplied as literal or generator func. const uint8_t help_source_kind_ : 1; + // Kind of storage this flag is using for the flag's value. + const uint8_t value_storage_kind_ : 2; // ------------------------------------------------------------------------ // The bytes containing the const bitfields must not be shared with bytes @@ -530,8 +503,13 @@ class FlagImpl { // value specified in ABSL_FLAG or pointer to the dynamically set default // value via SetCommandLineOptionWithMode. def_kind_ is used to distinguish // these two cases. - FlagDefaultSrc default_value_ ABSL_GUARDED_BY(*DataGuard()); - // Current Flag Value + FlagDefaultSrc default_value_; + + // Atomically mutable flag's state + + // Flag's value. This can be either the atomically stored small value or + // pointer to the heap allocated dynamic value. value_storage_kind_ is used + // to distinguish these cases. FlagValue value_; // This is reserved space for an absl::Mutex to guard flag data. It will be @@ -553,7 +531,8 @@ class Flag final : public flags_internal::CommandLineFlag { public: constexpr Flag(const char* name, const char* filename, const FlagHelpArg help, const FlagDfltGenFunc default_value_gen) - : impl_(name, filename, &FlagOps, help, default_value_gen) {} + : impl_(name, filename, &FlagOps, help, FlagValue::Kind(), + default_value_gen) {} T Get() const { // See implementation notes in CommandLineFlag::Get(). @@ -564,10 +543,17 @@ class Flag final : public flags_internal::CommandLineFlag { }; U u; +#if !defined(NDEBUG) + impl_.AssertValidType(&flags_internal::FlagStaticTypeIdGen); +#endif + impl_.Get(&u.value); return std::move(u.value); } - void Set(const T& v) { impl_.Set(v); } + void Set(const T& v) { + impl_.AssertValidType(&flags_internal::FlagStaticTypeIdGen); + impl_.Write(&v); + } void SetCallback(const FlagCallbackFunc mutation_callback) { impl_.SetCallback(mutation_callback); } @@ -619,7 +605,7 @@ class Flag final : public flags_internal::CommandLineFlag { }; template -inline void FlagState::Restore() const { +void FlagState::Restore() const { if (flag_->RestoreState(*this)) { ABSL_INTERNAL_LOG(INFO, absl::StrCat("Restore saved value of ", flag_->Name(), diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index ae7a60cd..1cc2c5e5 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -955,12 +955,15 @@ H PiecewiseCombiner::add_buffer(H state, const unsigned char* data, return state; } - // Complete the buffer and hash it - const size_t bytes_needed = PiecewiseChunkSize() - position_; - memcpy(buf_ + position_, data, bytes_needed); - state = H::combine_contiguous(std::move(state), buf_, PiecewiseChunkSize()); - data += bytes_needed; - size -= bytes_needed; + // If the buffer is partially filled we need to complete the buffer + // and hash it. + if (position_ != 0) { + const size_t bytes_needed = PiecewiseChunkSize() - position_; + memcpy(buf_ + position_, data, bytes_needed); + state = H::combine_contiguous(std::move(state), buf_, PiecewiseChunkSize()); + data += bytes_needed; + size -= bytes_needed; + } // Hash whatever chunks we can without copying while (size >= PiecewiseChunkSize()) { diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index d7ad4efe..1c9dabb5 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -705,6 +705,7 @@ cc_test( cc_test( name = "randen_benchmarks", size = "medium", + timeout = "long", srcs = ["randen_benchmarks.cc"], copts = ABSL_TEST_COPTS + ABSL_RANDOM_RANDEN_COPTS, flaky = 1, diff --git a/absl/status/status.cc b/absl/status/status.cc index bbc1895e..df3b740f 100644 --- a/absl/status/status.cc +++ b/absl/status/status.cc @@ -147,7 +147,15 @@ void Status::SetPayload(absl::string_view type_url, absl::Cord payload) { bool Status::ErasePayload(absl::string_view type_url) { int index = status_internal::FindPayloadIndexByUrl(GetPayloads(), type_url); if (index != -1) { + PrepareToModify(); GetPayloads()->erase(GetPayloads()->begin() + index); + if (GetPayloads()->empty() && message().empty()) { + // Special case: If this can be represented inlined, it MUST be + // inlined (EqualsSlow depends on this behavior). + StatusCode c = static_cast(raw_code()); + Unref(rep_); + rep_ = CodeToInlinedRep(c); + } return true; } diff --git a/absl/status/status_test.cc b/absl/status/status_test.cc index 7cc65e45..ca9488ad 100644 --- a/absl/status/status_test.cc +++ b/absl/status/status_test.cc @@ -204,6 +204,25 @@ TEST(Status, TestComparePayloads) { EXPECT_EQ(bad_status1, bad_status2); } +TEST(Status, TestComparePayloadsAfterErase) { + absl::Status payload_status(absl::StatusCode::kInternal, ""); + payload_status.SetPayload(kUrl1, absl::Cord(kPayload1)); + payload_status.SetPayload(kUrl2, absl::Cord(kPayload2)); + + absl::Status empty_status(absl::StatusCode::kInternal, ""); + + // Different payloads, not equal + EXPECT_NE(payload_status, empty_status); + EXPECT_TRUE(payload_status.ErasePayload(kUrl1)); + + // Still Different payloads, still not equal. + EXPECT_NE(payload_status, empty_status); + EXPECT_TRUE(payload_status.ErasePayload(kUrl2)); + + // Both empty payloads, should be equal + EXPECT_EQ(payload_status, empty_status); +} + PayloadsVec AllVisitedPayloads(const absl::Status& s) { PayloadsVec result; @@ -261,6 +280,36 @@ TEST(Status, ToString) { HasSubstr("[bar='\\xff']"))); } +absl::Status EraseAndReturn(const absl::Status& base) { + absl::Status copy = base; + EXPECT_TRUE(copy.ErasePayload(kUrl1)); + return copy; +} + +TEST(Status, CopyOnWriteForErasePayload) { + { + absl::Status base(absl::StatusCode::kInvalidArgument, "fail"); + base.SetPayload(kUrl1, absl::Cord(kPayload1)); + EXPECT_TRUE(base.GetPayload(kUrl1).has_value()); + absl::Status copy = EraseAndReturn(base); + EXPECT_TRUE(base.GetPayload(kUrl1).has_value()); + EXPECT_FALSE(copy.GetPayload(kUrl1).has_value()); + } + { + absl::Status base(absl::StatusCode::kInvalidArgument, "fail"); + base.SetPayload(kUrl1, absl::Cord(kPayload1)); + absl::Status copy = base; + + EXPECT_TRUE(base.GetPayload(kUrl1).has_value()); + EXPECT_TRUE(copy.GetPayload(kUrl1).has_value()); + + EXPECT_TRUE(base.ErasePayload(kUrl1)); + + EXPECT_FALSE(base.GetPayload(kUrl1).has_value()); + EXPECT_TRUE(copy.GetPayload(kUrl1).has_value()); + } +} + TEST(Status, CopyConstructor) { { absl::Status status; @@ -300,6 +349,14 @@ TEST(Status, CopyAssignment) { } } +TEST(Status, CopyAssignmentIsNotRef) { + const absl::Status status_orig(absl::StatusCode::kInvalidArgument, "message"); + absl::Status status_copy = status_orig; + EXPECT_EQ(status_orig, status_copy); + status_copy.SetPayload(kUrl1, absl::Cord(kPayload1)); + EXPECT_NE(status_orig, status_copy); +} + TEST(Status, MoveConstructor) { { absl::Status status; diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index 5cc68539..9b32b3cc 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -30,7 +30,6 @@ #include "absl/base/internal/raw_logging.h" #include "absl/base/port.h" #include "absl/container/fixed_array.h" -#include "absl/container/inlined_vector.h" #include "absl/strings/escaping.h" #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/resize_uninitialized.h" @@ -132,6 +131,14 @@ inline const CordRepExternal* CordRep::external() const { return static_cast(this); } +using CordTreeConstPath = CordTreePath; + +// This type is used to store the list of pending nodes during re-balancing. +// Its maximum size is 2 * MaxCordDepth() because the tree has a maximum +// possible depth of MaxCordDepth() and every concat node along a tree path +// could theoretically be split during rebalancing. +using RebalancingStack = CordTreePath; + } // namespace cord_internal static const size_t kFlatOverhead = offsetof(CordRep, data); @@ -180,8 +187,8 @@ static constexpr size_t TagToLength(uint8_t tag) { // Enforce that kMaxFlatSize maps to a well-known exact tag value. static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic"); -constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) { - return n == 0 ? a : Fibonacci(n - 1, b, a + b); +constexpr uint64_t Fibonacci(uint8_t n, uint64_t a = 0, uint64_t b = 1) { + return n == 0 ? a : n == 1 ? b : Fibonacci(n - 1, b, a + b); } static_assert(Fibonacci(63) == 6557470319842, @@ -189,89 +196,68 @@ static_assert(Fibonacci(63) == 6557470319842, // Minimum length required for a given depth tree -- a tree is considered // balanced if -// length(t) >= min_length[depth(t)] -// The root node depth is allowed to become twice as large to reduce rebalancing -// for larger strings (see IsRootBalanced). -static constexpr uint64_t min_length[] = { - Fibonacci(2), - Fibonacci(3), - Fibonacci(4), - Fibonacci(5), - Fibonacci(6), - Fibonacci(7), - Fibonacci(8), - Fibonacci(9), - Fibonacci(10), - Fibonacci(11), - Fibonacci(12), - Fibonacci(13), - Fibonacci(14), - Fibonacci(15), - Fibonacci(16), - Fibonacci(17), - Fibonacci(18), - Fibonacci(19), - Fibonacci(20), - Fibonacci(21), - Fibonacci(22), - Fibonacci(23), - Fibonacci(24), - Fibonacci(25), - Fibonacci(26), - Fibonacci(27), - Fibonacci(28), - Fibonacci(29), - Fibonacci(30), - Fibonacci(31), - Fibonacci(32), - Fibonacci(33), - Fibonacci(34), - Fibonacci(35), - Fibonacci(36), - Fibonacci(37), - Fibonacci(38), - Fibonacci(39), - Fibonacci(40), - Fibonacci(41), - Fibonacci(42), - Fibonacci(43), - Fibonacci(44), - Fibonacci(45), - Fibonacci(46), - Fibonacci(47), - 0xffffffffffffffffull, // Avoid overflow -}; - -static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length); - -// The inlined size to use with absl::InlinedVector. -// -// Note: The InlinedVectors in this file (and in cord.h) do not need to use -// the same value for their inlined size. The fact that they do is historical. -// It may be desirable for each to use a different inlined size optimized for -// that InlinedVector's usage. -// -// TODO(jgm): Benchmark to see if there's a more optimal value than 47 for -// the inlined vector size (47 exists for backward compatibility). -static const int kInlinedVectorSize = 47; - -static inline bool IsRootBalanced(CordRep* node) { - if (node->tag != CONCAT) { - return true; - } else if (node->concat()->depth() <= 15) { - return true; - } else if (node->concat()->depth() > kMinLengthSize) { - return false; - } else { - // Allow depth to become twice as large as implied by fibonacci rule to - // reduce rebalancing for larger strings. - return (node->length >= min_length[node->concat()->depth() / 2]); - } +// length(t) >= kMinLength[depth(t)] +// The node depth is allowed to become larger to reduce rebalancing +// for larger strings (see ShouldRebalance). +constexpr uint64_t kMinLength[] = { + Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5), Fibonacci(6), + Fibonacci(7), Fibonacci(8), Fibonacci(9), Fibonacci(10), Fibonacci(11), + Fibonacci(12), Fibonacci(13), Fibonacci(14), Fibonacci(15), Fibonacci(16), + Fibonacci(17), Fibonacci(18), Fibonacci(19), Fibonacci(20), Fibonacci(21), + Fibonacci(22), Fibonacci(23), Fibonacci(24), Fibonacci(25), Fibonacci(26), + Fibonacci(27), Fibonacci(28), Fibonacci(29), Fibonacci(30), Fibonacci(31), + Fibonacci(32), Fibonacci(33), Fibonacci(34), Fibonacci(35), Fibonacci(36), + Fibonacci(37), Fibonacci(38), Fibonacci(39), Fibonacci(40), Fibonacci(41), + Fibonacci(42), Fibonacci(43), Fibonacci(44), Fibonacci(45), Fibonacci(46), + Fibonacci(47), Fibonacci(48), Fibonacci(49), Fibonacci(50), Fibonacci(51), + Fibonacci(52), Fibonacci(53), Fibonacci(54), Fibonacci(55), Fibonacci(56), + Fibonacci(57), Fibonacci(58), Fibonacci(59), Fibonacci(60), Fibonacci(61), + Fibonacci(62), Fibonacci(63), Fibonacci(64), Fibonacci(65), Fibonacci(66), + Fibonacci(67), Fibonacci(68), Fibonacci(69), Fibonacci(70), Fibonacci(71), + Fibonacci(72), Fibonacci(73), Fibonacci(74), Fibonacci(75), Fibonacci(76), + Fibonacci(77), Fibonacci(78), Fibonacci(79), Fibonacci(80), Fibonacci(81), + Fibonacci(82), Fibonacci(83), Fibonacci(84), Fibonacci(85), Fibonacci(86), + Fibonacci(87), Fibonacci(88), Fibonacci(89), Fibonacci(90), Fibonacci(91), + Fibonacci(92), Fibonacci(93)}; + +static_assert(sizeof(kMinLength) / sizeof(uint64_t) == + (cord_internal::MaxCordDepth() + 1), + "Not enough elements in kMinLength array to cover all the " + "supported Cord depth(s)"); + +inline bool ShouldRebalance(const CordRep* node) { + if (node->tag != CONCAT) return false; + + size_t node_depth = node->concat()->depth(); + + if (node_depth <= 15) return false; + + // Rebalancing Cords is expensive, so we reduce how often rebalancing occurs + // by allowing shallow Cords to have twice the depth that the Fibonacci rule + // would otherwise imply. Deep Cords need to follow the rule more closely, + // however to ensure algorithm correctness. We implement this with linear + // interpolation. Cords of depth 16 are treated as though they have a depth + // of 16 * 1/2, and Cords of depth MaxCordDepth() interpolate to + // MaxCordDepth() * 1. + return node->length < + kMinLength[(node_depth * (cord_internal::MaxCordDepth() - 16)) / + (2 * cord_internal::MaxCordDepth() - 16 - node_depth)]; +} + +// Unlike root balancing condition this one is part of the re-balancing +// algorithm and has to be always matching against right depth for +// algorithm to be correct. +inline bool IsNodeBalanced(const CordRep* node) { + if (node->tag != CONCAT) return true; + + size_t node_depth = node->concat()->depth(); + + return node->length >= kMinLength[node_depth]; } static CordRep* Rebalance(CordRep* node); -static void DumpNode(CordRep* rep, bool include_data, std::ostream* os); -static bool VerifyNode(CordRep* root, CordRep* start_node, +static void DumpNode(const CordRep* rep, bool include_data, std::ostream* os); +static bool VerifyNode(const CordRep* root, const CordRep* start_node, bool full_validation); static inline CordRep* VerifyTree(CordRep* node) { @@ -318,7 +304,8 @@ __attribute__((preserve_most)) static void UnrefInternal(CordRep* rep) { assert(rep != nullptr); - absl::InlinedVector pending; + cord_internal::RebalancingStack pending; + while (true) { if (rep->tag == CONCAT) { CordRepConcat* rep_concat = rep->concat(); @@ -400,6 +387,11 @@ static void SetConcatChildren(CordRepConcat* concat, CordRep* left, concat->length = left->length + right->length; concat->set_depth(1 + std::max(Depth(left), Depth(right))); + + ABSL_INTERNAL_CHECK(concat->depth() <= cord_internal::MaxCordDepth(), + "Cord depth exceeds max"); + ABSL_INTERNAL_CHECK(concat->length >= left->length, "Cord is too long"); + ABSL_INTERNAL_CHECK(concat->length >= right->length, "Cord is too long"); } // Create a concatenation of the specified nodes. @@ -425,7 +417,7 @@ static CordRep* RawConcat(CordRep* left, CordRep* right) { static CordRep* Concat(CordRep* left, CordRep* right) { CordRep* rep = RawConcat(left, right); - if (rep != nullptr && !IsRootBalanced(rep)) { + if (rep != nullptr && ShouldRebalance(rep)) { rep = Rebalance(rep); } return VerifyTree(rep); @@ -916,7 +908,7 @@ void Cord::Prepend(absl::string_view src) { static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { if (n >= node->length) return nullptr; if (n == 0) return Ref(node); - absl::InlinedVector rhs_stack; + cord_internal::CordTreeMutablePath rhs_stack; while (node->tag == CONCAT) { assert(n <= node->length); @@ -957,7 +949,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { if (n >= node->length) return nullptr; if (n == 0) return Ref(node); - absl::InlinedVector lhs_stack; + absl::cord_internal::CordTreeMutablePath lhs_stack; bool inplace_ok = node->refcount.IsOne(); while (node->tag == CONCAT) { @@ -1028,6 +1020,7 @@ void Cord::RemoveSuffix(size_t n) { // Work item for NewSubRange(). struct SubRange { + SubRange() = default; SubRange(CordRep* a_node, size_t a_pos, size_t a_n) : node(a_node), pos(a_pos), n(a_n) {} CordRep* node; // nullptr means concat last 2 results. @@ -1036,8 +1029,11 @@ struct SubRange { }; static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) { - absl::InlinedVector results; - absl::InlinedVector todo; + cord_internal::CordTreeMutablePath results; + // The algorithm below in worst case scenario adds up to 3 nodes to the `todo` + // list, but we also pop one out on every cycle. If original tree has depth d + // todo list can grew up to 2*d in size. + cord_internal::CordTreePath todo; todo.push_back(SubRange(node, pos, n)); do { const SubRange& sr = todo.back(); @@ -1074,7 +1070,7 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) { } } while (!todo.empty()); assert(results.size() == 1); - return results[0]; + return results.back(); } Cord Cord::Subcord(size_t pos, size_t new_size) const { @@ -1113,11 +1109,12 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const { class CordForest { public: - explicit CordForest(size_t length) - : root_length_(length), trees_(kMinLengthSize, nullptr) {} + explicit CordForest(size_t length) : root_length_(length), trees_({}) {} void Build(CordRep* cord_root) { - std::vector pending = {cord_root}; + // We are adding up to two nodes to the `pending` list, but we also popping + // one, so the size of `pending` will never exceed `MaxCordDepth()`. + cord_internal::CordTreeMutablePath pending(cord_root); while (!pending.empty()) { CordRep* node = pending.back(); @@ -1129,21 +1126,20 @@ class CordForest { } CordRepConcat* concat_node = node->concat(); - if (concat_node->depth() >= kMinLengthSize || - concat_node->length < min_length[concat_node->depth()]) { - pending.push_back(concat_node->right); - pending.push_back(concat_node->left); - - if (concat_node->refcount.IsOne()) { - concat_node->left = concat_freelist_; - concat_freelist_ = concat_node; - } else { - Ref(concat_node->right); - Ref(concat_node->left); - Unref(concat_node); - } - } else { + if (IsNodeBalanced(concat_node)) { AddNode(node); + continue; + } + pending.push_back(concat_node->right); + pending.push_back(concat_node->left); + + if (concat_node->refcount.IsOne()) { + concat_node->left = concat_freelist_; + concat_freelist_ = concat_node; + } else { + Ref(concat_node->right); + Ref(concat_node->left); + Unref(concat_node); } } } @@ -1175,7 +1171,7 @@ class CordForest { // Collect together everything with which we will merge node int i = 0; - for (; node->length > min_length[i + 1]; ++i) { + for (; node->length > kMinLength[i + 1]; ++i) { auto& tree_at_i = trees_[i]; if (tree_at_i == nullptr) continue; @@ -1186,7 +1182,7 @@ class CordForest { sum = AppendNode(node, sum); // Insert sum into appropriate place in the forest - for (; sum->length >= min_length[i]; ++i) { + for (; sum->length >= kMinLength[i]; ++i) { auto& tree_at_i = trees_[i]; if (tree_at_i == nullptr) continue; @@ -1194,7 +1190,7 @@ class CordForest { tree_at_i = nullptr; } - // min_length[0] == 1, which means sum->length >= min_length[0] + // kMinLength[0] == 1, which means sum->length >= kMinLength[0] assert(i > 0); trees_[i - 1] = sum; } @@ -1227,9 +1223,7 @@ class CordForest { } size_t root_length_; - - // use an inlined vector instead of a flat array to get bounds checking - absl::InlinedVector trees_; + std::array trees_; // List of concat nodes we can re-use for Cord balancing. CordRepConcat* concat_freelist_ = nullptr; @@ -1841,18 +1835,18 @@ absl::string_view Cord::FlattenSlowPath() { } } -static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) { +static void DumpNode(const CordRep* rep, bool include_data, std::ostream* os) { const int kIndentStep = 1; int indent = 0; - absl::InlinedVector stack; - absl::InlinedVector indents; + cord_internal::CordTreeConstPath stack; + cord_internal::CordTreePath indents; for (;;) { *os << std::setw(3) << rep->refcount.Get(); *os << " " << std::setw(7) << rep->length; *os << " ["; - if (include_data) *os << static_cast(rep); + if (include_data) *os << static_cast(rep); *os << "]"; - *os << " " << (IsRootBalanced(rep) ? 'b' : 'u'); + *os << " " << (IsNodeBalanced(rep) ? 'b' : 'u'); *os << " " << std::setw(indent) << ""; if (rep->tag == CONCAT) { *os << "CONCAT depth=" << Depth(rep) << "\n"; @@ -1873,7 +1867,7 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) { } else { *os << "FLAT cap=" << TagToLength(rep->tag) << " ["; if (include_data) - *os << absl::CEscape(std::string(rep->data, rep->length)); + *os << absl::CEscape(absl::string_view(rep->data, rep->length)); *os << "]\n"; } if (stack.empty()) break; @@ -1886,19 +1880,19 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) { ABSL_INTERNAL_CHECK(indents.empty(), ""); } -static std::string ReportError(CordRep* root, CordRep* node) { +static std::string ReportError(const CordRep* root, const CordRep* node) { std::ostringstream buf; buf << "Error at node " << node << " in:"; DumpNode(root, true, &buf); return buf.str(); } -static bool VerifyNode(CordRep* root, CordRep* start_node, +static bool VerifyNode(const CordRep* root, const CordRep* start_node, bool full_validation) { - absl::InlinedVector worklist; + cord_internal::CordTreeConstPath worklist; worklist.push_back(start_node); do { - CordRep* node = worklist.back(); + const CordRep* node = worklist.back(); worklist.pop_back(); ABSL_INTERNAL_CHECK(node != nullptr, ReportError(root, node)); @@ -1948,7 +1942,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node, // Iterate over the tree. cur_node is never a leaf node and leaf nodes will // never be appended to tree_stack. This reduces overhead from manipulating // tree_stack. - absl::InlinedVector tree_stack; + cord_internal::CordTreeConstPath tree_stack; const CordRep* cur_node = rep; while (true) { const CordRep* next_node = nullptr; diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 40566cba..68a7e52f 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -41,13 +41,13 @@ #include #include #include +#include #include "absl/base/internal/endian.h" #include "absl/base/internal/invoke.h" #include "absl/base/internal/per_thread_tls.h" #include "absl/base/macros.h" #include "absl/base/port.h" -#include "absl/container/inlined_vector.h" #include "absl/functional/function_ref.h" #include "absl/meta/type_traits.h" #include "absl/strings/internal/cord_internal.h" @@ -66,6 +66,73 @@ template H HashFragmentedCord(H, const Cord&); } +namespace cord_internal { + +// It's expensive to keep a tree perfectly balanced, so instead we keep trees +// approximately balanced. A tree node N of depth D(N) that contains a string +// of L(N) characters is considered balanced if L >= Fibonacci(D + 2). +// The "+ 2" is used to ensure that every leaf node contains at least one +// character. Here we presume that +// Fibonacci(0) = 0 +// Fibonacci(1) = 1 +// Fibonacci(2) = 1 +// Fibonacci(3) = 2 +// ... +// +// Fibonacci numbers are convenient because it means when two balanced trees of +// the same depth are made the children of a new node, the resulting tree is +// guaranteed to also be balanced: +// +// +// L(left) >= Fibonacci(D(left) + 2) +// L(right) >= Fibonacci(D(right) + 2) +// +// L(left) + L(right) >= Fibonacci(D(left) + 2) + Fibonacci(D(right) + 2) +// L(left) + L(right) == L(new_tree) +// +// L(new_tree) >= 2 * Fibonacci(D(child) + 2) +// D(child) == D(new_tree) - 1 +// +// L(new_tree) >= 2 * Fibonacci(D(new_tree) + 1) +// 2 * Fibonacci(N) >= Fibonacci(N + 1) +// +// L(new_tree) >= Fibonacci(D(new_tree) + 2) +// +// +// The 93rd Fibonacci number is the largest Fibonacci number that can be +// represented in 64 bits, so the size of a balanced Cord of depth 92 is too big +// for an unsigned 64 bit integer to hold. Therefore we can safely assume that +// the maximum depth of a Cord is 91. +constexpr size_t MaxCordDepth() { return 91; } + +// This class models fixed max size stack of CordRep pointers. +// The elements are being pushed back and popped from the back. +template +class CordTreePath { + public: + CordTreePath() {} + explicit CordTreePath(CordRepPtr root) { push_back(root); } + + bool empty() const { return size_ == 0; } + size_t size() const { return size_; } + void clear() { size_ = 0; } + + CordRepPtr back() { return data_[size_ - 1]; } + + void pop_back() { + --size_; + assert(size_ < N); + } + void push_back(CordRepPtr elem) { data_[size_++] = elem; } + + private: + CordRepPtr data_[N]; + size_t size_ = 0; +}; + +using CordTreeMutablePath = CordTreePath; +} // namespace cord_internal + // A Cord is a sequence of characters. class Cord { private: @@ -114,7 +181,8 @@ class Cord { // finished with `data`. The data must remain live and unchanging until the // releaser is called. The requirements for the releaser are that it: // * is move constructible, - // * supports `void operator()(absl::string_view) const`, + // * supports `void operator()(absl::string_view) const` or + // `void operator()() const`, // * does not have alignment requirement greater than what is guaranteed by // ::operator new. This is dictated by alignof(std::max_align_t) before // C++17 and __STDCPP_DEFAULT_NEW_ALIGNMENT__ if compiling with C++17 or @@ -127,8 +195,8 @@ class Cord { // FillBlock(block); // return absl::MakeCordFromExternal( // block->ToStringView(), - // [pool, block](absl::string_view /*ignored*/) { - // pool->FreeBlock(block); + // [pool, block](absl::string_view v) { + // pool->FreeBlock(block, v); // }); // } // @@ -282,8 +350,7 @@ class Cord { absl::cord_internal::CordRep* current_leaf_ = nullptr; // The number of bytes left in the `Cord` over which we are iterating. size_t bytes_remaining_ = 0; - absl::InlinedVector - stack_of_right_children_; + absl::cord_internal::CordTreeMutablePath stack_of_right_children_; }; // Returns an iterator to the first chunk of the `Cord`. @@ -667,6 +734,21 @@ ExternalRepReleaserPair NewExternalWithUninitializedReleaser( absl::string_view data, ExternalReleaserInvoker invoker, size_t releaser_size); +struct Rank1 {}; +struct Rank0 : Rank1 {}; + +template > +void InvokeReleaser(Rank0, Releaser&& releaser, absl::string_view data) { + ::absl::base_internal::Invoke(std::forward(releaser), data); +} + +template > +void InvokeReleaser(Rank1, Releaser&& releaser, absl::string_view) { + ::absl::base_internal::Invoke(std::forward(releaser)); +} + // Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer // to it, or `nullptr` if `data` was empty. template @@ -684,14 +766,14 @@ CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) { using ReleaserType = absl::decay_t; if (data.empty()) { // Never create empty external nodes. - ::absl::base_internal::Invoke( - ReleaserType(std::forward(releaser)), data); + InvokeReleaser(Rank0{}, ReleaserType(std::forward(releaser)), + data); return nullptr; } auto releaser_invoker = [](void* type_erased_releaser, absl::string_view d) { auto* my_releaser = static_cast(type_erased_releaser); - ::absl::base_internal::Invoke(std::move(*my_releaser), d); + InvokeReleaser(Rank0{}, std::move(*my_releaser), d); my_releaser->~ReleaserType(); return sizeof(Releaser); }; diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 434f3a24..68515cbf 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc @@ -1032,6 +1032,19 @@ TEST(ConstructFromExternal, MoveOnlyReleaser) { EXPECT_TRUE(invoked); } +TEST(ConstructFromExternal, NoArgLambda) { + bool invoked = false; + (void)absl::MakeCordFromExternal("dummy", [&invoked]() { invoked = true; }); + EXPECT_TRUE(invoked); +} + +TEST(ConstructFromExternal, StringViewArgLambda) { + bool invoked = false; + (void)absl::MakeCordFromExternal( + "dummy", [&invoked](absl::string_view) { invoked = true; }); + EXPECT_TRUE(invoked); +} + TEST(ConstructFromExternal, NonTrivialReleaserDestructor) { struct Releaser { explicit Releaser(bool* destroyed) : destroyed(destroyed) {} @@ -1346,6 +1359,49 @@ TEST(CordChunkIterator, Operations) { VerifyChunkIterator(subcords, 128); } +TEST(CordChunkIterator, MaxLengthFullTree) { + absl::Cord cord; + size_t size = 1; + AddExternalMemory("x", &cord); + EXPECT_EQ(cord.size(), size); + + for (int i = 0; i < 63; ++i) { + cord.Prepend(absl::Cord(cord)); + size <<= 1; + + EXPECT_EQ(cord.size(), size); + + auto chunk_it = cord.chunk_begin(); + EXPECT_EQ(*chunk_it, "x"); + } + + EXPECT_DEATH_IF_SUPPORTED( + (cord.Prepend(absl::Cord(cord)), *cord.chunk_begin()), + "Cord is too long"); +} + +TEST(CordChunkIterator, MaxDepth) { + // By reusing nodes, it's possible in pathological cases to build a Cord that + // exceeds both the maximum permissible length and depth. In this case, the + // violation of the maximum depth is reported. + absl::Cord left_child; + AddExternalMemory("x", &left_child); + absl::Cord root = left_child; + + for (int i = 0; i < 91; ++i) { + size_t new_size = left_child.size() + root.size(); + root.Prepend(left_child); + EXPECT_EQ(root.size(), new_size); + + auto chunk_it = root.chunk_begin(); + EXPECT_EQ(*chunk_it, "x"); + + std::swap(left_child, root); + } + + EXPECT_DEATH_IF_SUPPORTED(root.Prepend(left_child), "Cord depth exceeds max"); +} + TEST(CordCharIterator, Traits) { static_assert(std::is_copy_constructible::value, ""); -- cgit v1.2.3 From 938fd0f4e67ddb7dc321021968223317663156c5 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 10 Dec 2020 10:35:21 -0800 Subject: Export of internal Abseil changes -- 6e9f93888bbe6718997ed90bbd049f1f3572b066 by Abseil Team : Fix status to be safe for self move assignment. PiperOrigin-RevId: 346815392 -- 35cae74a977f258e81dfbe925fb5a34cb6632036 by Gennadiy Rozental : Eliminate unnecessary access to the global vars. PiperOrigin-RevId: 346777168 -- e7e786c243069060f5d6c1c945decb4b0b83f95b by Andy Getzendanner : Internal change. PiperOrigin-RevId: 346685656 -- 4ccd41c48f1a83cfa20b3ea534f743dd7d788376 by Abseil Team : Move CordRep Ref() and Unref() logic into cord_internal.h This change moves Ref() and Unref() logic out of cord.cc into cord_internal. The main purpose is to make upcoming ring buffer changes easier to isolate from existing cord.cc code. Notice that this removes the nullptr check from Unref() and now requires it to be non null (which held true most times). We may need to rethink if the 'unref unlikely one' is the common case: are cordreps most likely shared? This may be something between 'root' and non root nodes, i.e., is it more likely for leaf / flat nodes in large cords to be shared than top level cordreps being shared? Vice versa? Benchmarks say that we mostly shouldn't care, the caveat being that atomic ops seem more expensive on upcoming archs (arcadia) so we should error on the side of an extra IsOne() branch saving us single owned atomic ops. PiperOrigin-RevId: 346676121 -- f0babab103b9e60d61ba09482d468985e43eceb3 by Samuel Benzaquen : Fix iterator based constructor and `.insert` members to only require EmplaceConstructible as the standard specifies. PiperOrigin-RevId: 346616707 -- 8f48eedda02277f9c96a88ed7726e34b557cce20 by Evan Brown : Fix a bug in binary_search_impl when there's a transparent, three-way comparator that has different equivalence classes for different lookup types. Add a new can_have_multiple_equivalent_keys method to share the common logic for these cases. PiperOrigin-RevId: 346605948 -- 649183cb3cc9383431de9c81fb1c0f885d4001ae by Abseil Team : Add benchmark for accessing a Duration flag. PiperOrigin-RevId: 346594843 -- fefdb046520871af63ce2229e2f7cccfc0483dea by Abseil Team : Restructure CordReader for upcoming ring buffer changes. PiperOrigin-RevId: 346410642 -- 8b2f50e7da0ebab06ead5f94e366e984ca23cb6a by Abseil Team : Wire in an internal-only flag to toggle upcoming ring buffer changes on/off for experimentation. PiperOrigin-RevId: 346199111 GitOrigin-RevId: 6e9f93888bbe6718997ed90bbd049f1f3572b066 Change-Id: I8f34866b25a79209cb5448bbb28dd3044111d2e9 --- CMake/AbseilDll.cmake | 1 + absl/container/btree_test.cc | 40 ++++- absl/container/internal/btree.h | 42 ++--- absl/container/internal/raw_hash_set.h | 2 +- absl/container/internal/raw_hash_set_test.cc | 74 +++++++-- absl/flags/internal/usage.cc | 6 - absl/status/status.h | 8 +- absl/status/status_test.cc | 6 + absl/strings/BUILD.bazel | 10 +- absl/strings/CMakeLists.txt | 2 + absl/strings/cord.cc | 223 ++++++--------------------- absl/strings/cord.h | 1 + absl/strings/internal/cord_internal.cc | 76 +++++++++ absl/strings/internal/cord_internal.h | 107 +++++++++++++ absl/time/BUILD.bazel | 1 + absl/time/duration_benchmark.cc | 16 ++ 16 files changed, 394 insertions(+), 221 deletions(-) create mode 100644 absl/strings/internal/cord_internal.cc (limited to 'absl/status/status_test.cc') diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 68e28c22..be6e3484 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -192,6 +192,7 @@ set(ABSL_INTERNAL_DLL_FILES "strings/cord.h" "strings/escaping.cc" "strings/escaping.h" + "strings/internal/cord_internal.cc" "strings/internal/cord_internal.h" "strings/internal/cord_rep_flat.h" "strings/internal/charconv_bigint.cc" diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index 9b1b6436..a933386a 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -2696,8 +2696,36 @@ struct MultiKeyComp { bool operator()(const MultiKey a, const int b) const { return a.i1 < b; } }; -TEST(Btree, MultiKeyEqualRange) { - absl::btree_set set; +// A heterogeneous, three-way comparator that has different equivalence classes +// for different lookup types. +struct MultiKeyThreeWayComp { + using is_transparent = void; + absl::weak_ordering operator()(const MultiKey a, const MultiKey b) const { + if (a.i1 < b.i1) return absl::weak_ordering::less; + if (a.i1 > b.i1) return absl::weak_ordering::greater; + if (a.i2 < b.i2) return absl::weak_ordering::less; + if (a.i2 > b.i2) return absl::weak_ordering::greater; + return absl::weak_ordering::equivalent; + } + absl::weak_ordering operator()(const int a, const MultiKey b) const { + if (a < b.i1) return absl::weak_ordering::less; + if (a > b.i1) return absl::weak_ordering::greater; + return absl::weak_ordering::equivalent; + } + absl::weak_ordering operator()(const MultiKey a, const int b) const { + if (a.i1 < b) return absl::weak_ordering::less; + if (a.i1 > b) return absl::weak_ordering::greater; + return absl::weak_ordering::equivalent; + } +}; + +template +class BtreeMultiKeyTest : public ::testing::Test {}; +using MultiKeyComps = ::testing::Types; +TYPED_TEST_SUITE(BtreeMultiKeyTest, MultiKeyComps); + +TYPED_TEST(BtreeMultiKeyTest, EqualRange) { + absl::btree_set set; for (int i = 0; i < 100; ++i) { for (int j = 0; j < 100; ++j) { @@ -2713,15 +2741,15 @@ TEST(Btree, MultiKeyEqualRange) { } } -TEST(Btree, MultiKeyErase) { - absl::btree_set set = { +TYPED_TEST(BtreeMultiKeyTest, Erase) { + absl::btree_set set = { {1, 1}, {2, 1}, {2, 2}, {3, 1}}; EXPECT_EQ(set.erase(2), 2); EXPECT_THAT(set, ElementsAre(MultiKey{1, 1}, MultiKey{3, 1})); } -TEST(Btree, MultiKeyCount) { - const absl::btree_set set = { +TYPED_TEST(BtreeMultiKeyTest, Count) { + const absl::btree_set set = { {1, 1}, {2, 1}, {2, 2}, {3, 1}}; EXPECT_EQ(set.count(2), 2); } diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index dad580f5..d863cb30 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -220,9 +220,6 @@ struct common_params { // If Compare is a common comparator for a string-like type, then we adapt it // to use heterogeneous lookup and to be a key-compare-to comparator. using key_compare = typename key_compare_to_adapter::type; - // True when key_compare has been adapted to StringBtreeDefault{Less,Greater}. - using is_key_compare_adapted = - absl::negation>; // A type which indicates if we have a key-compare-to functor or a plain old // key-compare functor. using is_key_compare_to = btree_is_key_compare_to; @@ -232,9 +229,6 @@ struct common_params { using size_type = std::make_signed::type; using difference_type = ptrdiff_t; - // True if this is a multiset or multimap. - using is_multi_container = std::integral_constant; - using slot_policy = SlotPolicy; using slot_type = typename slot_policy::slot_type; using value_type = typename slot_policy::value_type; @@ -244,6 +238,23 @@ struct common_params { using reference = value_type &; using const_reference = const value_type &; + // For the given lookup key type, returns whether we can have multiple + // equivalent keys in the btree. If this is a multi-container, then we can. + // Otherwise, we can have multiple equivalent keys only if all of the + // following conditions are met: + // - The comparator is transparent. + // - The lookup key type is not the same as key_type. + // - The comparator is not a StringBtreeDefault{Less,Greater} comparator + // that we know has the same equivalence classes for all lookup types. + template + constexpr static bool can_have_multiple_equivalent_keys() { + return Multi || + (IsTransparent::value && + !std::is_same::value && + !std::is_same::value && + !std::is_same::value); + } + enum { kTargetNodeSize = TargetNodeSize, @@ -439,7 +450,6 @@ struct SearchResult { template class btree_node { using is_key_compare_to = typename Params::is_key_compare_to; - using is_multi_container = typename Params::is_multi_container; using field_type = typename Params::node_count_type; using allocator_type = typename Params::allocator_type; using slot_type = typename Params::slot_type; @@ -759,7 +769,7 @@ class btree_node { SearchResult binary_search_impl( const K &k, int s, int e, const CompareTo &comp, std::true_type /* IsCompareTo */) const { - if (is_multi_container::value) { + if (params_type::template can_have_multiple_equivalent_keys()) { MatchKind exact_match = MatchKind::kNe; while (s != e) { const int mid = (s + e) >> 1; @@ -770,14 +780,14 @@ class btree_node { e = mid; if (c == 0) { // Need to return the first value whose key is not less than k, - // which requires continuing the binary search if this is a - // multi-container. + // which requires continuing the binary search if there could be + // multiple equivalent keys. exact_match = MatchKind::kEq; } } } return {s, exact_match}; - } else { // Not a multi-container. + } else { // Can't have multiple equivalent keys. while (s != e) { const int mid = (s + e) >> 1; const absl::weak_ordering c = comp(key(mid), k); @@ -1054,8 +1064,6 @@ class btree { using is_key_compare_to = typename Params::is_key_compare_to; using init_type = typename Params::init_type; using field_type = typename node_type::field_type; - using is_multi_container = typename Params::is_multi_container; - using is_key_compare_adapted = typename Params::is_key_compare_adapted; // We use a static empty node for the root/leftmost/rightmost of empty btrees // in order to avoid branching in begin()/end(). @@ -1907,13 +1915,7 @@ auto btree

::equal_range(const K &key) -> std::pair { } const iterator next = std::next(lower); - // When the comparator is heterogeneous, we can't assume that comparison with - // non-`key_type` will be equivalent to `key_type` comparisons so there - // could be multiple equivalent keys even in a unique-container. But for - // heterogeneous comparisons from the default string adapted comparators, we - // don't need to worry about this. - if (!is_multi_container::value && - (std::is_same::value || is_key_compare_adapted::value)) { + if (!params_type::template can_have_multiple_equivalent_keys()) { // The next iterator after lower must point to a key greater than `key`. // Note: if this assert fails, then it may indicate that the comparator does // not meet the equivalence requirements for Compare diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 02158c4e..a958daaf 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -1085,7 +1085,7 @@ class raw_hash_set { template void insert(InputIt first, InputIt last) { - for (; first != last; ++first) insert(*first); + for (; first != last; ++first) emplace(*first); } template = 0, RequiresInsertable = 0> diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 33d2773d..0fba46ff 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -250,25 +250,43 @@ TEST(Group, CountLeadingEmptyOrDeleted) { } } -struct IntPolicy { - using slot_type = int64_t; - using key_type = int64_t; - using init_type = int64_t; +template +struct ValuePolicy { + using slot_type = T; + using key_type = T; + using init_type = T; - static void construct(void*, int64_t* slot, int64_t v) { *slot = v; } - static void destroy(void*, int64_t*) {} - static void transfer(void*, int64_t* new_slot, int64_t* old_slot) { - *new_slot = *old_slot; + template + static void construct(Allocator* alloc, slot_type* slot, Args&&... args) { + absl::allocator_traits::construct(*alloc, slot, + std::forward(args)...); } - static int64_t& element(slot_type* slot) { return *slot; } + template + static void destroy(Allocator* alloc, slot_type* slot) { + absl::allocator_traits::destroy(*alloc, slot); + } - template - static auto apply(F&& f, int64_t x) -> decltype(std::forward(f)(x, x)) { - return std::forward(f)(x, x); + template + static void transfer(Allocator* alloc, slot_type* new_slot, + slot_type* old_slot) { + construct(alloc, new_slot, std::move(*old_slot)); + destroy(alloc, old_slot); + } + + static T& element(slot_type* slot) { return *slot; } + + template + static decltype(absl::container_internal::DecomposeValue( + std::declval(), std::declval()...)) + apply(F&& f, Args&&... args) { + return absl::container_internal::DecomposeValue( + std::forward(f), std::forward(args)...); } }; +using IntPolicy = ValuePolicy; + class StringPolicy { template {}(v.value); + } + }; + + struct Table : raw_hash_set, H, std::equal_to, + std::allocator> { + using Base = typename Table::raw_hash_set; + using Base::Base; + }; + + std::string input[3]{"A", "B", "C"}; + + Table t(std::begin(input), std::end(input)); + EXPECT_THAT(t, UnorderedElementsAre(Value{"A"}, Value{"B"}, Value{"C"})); + + input[0] = "D"; + input[1] = "E"; + input[2] = "F"; + t.insert(std::begin(input), std::end(input)); + EXPECT_THAT(t, UnorderedElementsAre(Value{"A"}, Value{"B"}, Value{"C"}, + Value{"D"}, Value{"E"}, Value{"F"})); +} + TEST(Nodes, EmptyNodeType) { using node_type = StringTable::node_type; node_type n; diff --git a/absl/flags/internal/usage.cc b/absl/flags/internal/usage.cc index f29d7c9b..a588c7f7 100644 --- a/absl/flags/internal/usage.cc +++ b/absl/flags/internal/usage.cc @@ -437,12 +437,6 @@ void SetFlagsHelpMatchSubstr(absl::string_view substr) { HelpMode GetFlagsHelpMode() { absl::MutexLock l(&help_attributes_guard); - // Refer to dummy variales to prevent linker dropping them - if (FLAGS_help || FLAGS_helpfull || FLAGS_helpshort || FLAGS_helppackage || - FLAGS_version || FLAGS_only_check_args || FLAGS_helpon || - FLAGS_helpmatch) { - help_mode = HelpMode::kNone; - } return help_mode; } diff --git a/absl/status/status.h b/absl/status/status.h index 9019e6c2..08d3e806 100644 --- a/absl/status/status.h +++ b/absl/status/status.h @@ -705,9 +705,11 @@ inline Status::Status(Status&& x) noexcept : rep_(x.rep_) { inline Status& Status::operator=(Status&& x) { uintptr_t old_rep = rep_; - rep_ = x.rep_; - x.rep_ = MovedFromRep(); - Unref(old_rep); + if (x.rep_ != old_rep) { + rep_ = x.rep_; + x.rep_ = MovedFromRep(); + Unref(old_rep); + } return *this; } diff --git a/absl/status/status_test.cc b/absl/status/status_test.cc index ca9488ad..25333fa2 100644 --- a/absl/status/status_test.cc +++ b/absl/status/status_test.cc @@ -397,6 +397,12 @@ TEST(Status, MoveAssignment) { assignee = std::move(status); EXPECT_EQ(assignee, copy); } + { + absl::Status status(absl::StatusCode::kInvalidArgument, "message"); + absl::Status copy(status); + status = static_cast(status); + EXPECT_EQ(status, copy); + } } TEST(Status, Update) { diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index a1579a4a..aab3a286 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -267,16 +267,23 @@ cc_test( cc_library( name = "cord_internal", + srcs = [ + "internal/cord_internal.cc", + ], hdrs = [ "internal/cord_internal.h", "internal/cord_rep_flat.h", ], copts = ABSL_DEFAULT_COPTS, - visibility = ["//visibility:private"], + visibility = [ + "//visibility:private", + ], deps = [ ":strings", "//absl/base:base_internal", + "//absl/base:core_headers", "//absl/container:compressed_tuple", + "//absl/container:inlined_vector", "//absl/meta:type_traits", ], ) @@ -304,6 +311,7 @@ cc_library( "//absl/functional:function_ref", "//absl/meta:type_traits", "//absl/types:optional", + "//absl/types:variant", ], ) diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index af0b57d8..54c10151 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -556,6 +556,7 @@ absl_cc_library( "cord.h" SRCS "cord.cc" + "internal/cord_internal.cc" "internal/cord_internal.h" "internal/cord_rep_flat.h" COPTS @@ -570,6 +571,7 @@ absl_cc_library( absl::function_ref absl::inlined_vector absl::optional + absl::variant absl::raw_logging_internal absl::strings absl::strings_internal diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index badeb610..f475042c 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -60,51 +60,8 @@ using ::absl::cord_internal::EXTERNAL; using ::absl::cord_internal::FLAT; using ::absl::cord_internal::SUBSTRING; -namespace cord_internal { - -inline CordRepConcat* CordRep::concat() { - assert(tag == CONCAT); - return static_cast(this); -} - -inline const CordRepConcat* CordRep::concat() const { - assert(tag == CONCAT); - return static_cast(this); -} - -inline CordRepSubstring* CordRep::substring() { - assert(tag == SUBSTRING); - return static_cast(this); -} - -inline const CordRepSubstring* CordRep::substring() const { - assert(tag == SUBSTRING); - return static_cast(this); -} - -inline CordRepExternal* CordRep::external() { - assert(tag == EXTERNAL); - return static_cast(this); -} - -inline const CordRepExternal* CordRep::external() const { - assert(tag == EXTERNAL); - return static_cast(this); -} - -inline CordRepFlat* CordRep::flat() { - assert(tag >= FLAT); - return static_cast(this); -} -inline const CordRepFlat* CordRep::flat() const { - assert(tag >= FLAT); - return static_cast(this); -} - -} // namespace cord_internal - -// Prefer copying blocks of at most this size, otherwise reference count. -static const size_t kMaxBytesToCopy = 511; +using ::absl::cord_internal::kInlinedVectorSize; +using ::absl::cord_internal::kMaxBytesToCopy; constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) { return n == 0 ? a : Fibonacci(n - 1, b, a + b); @@ -136,17 +93,6 @@ static constexpr uint64_t min_length[] = { static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length); -// The inlined size to use with absl::InlinedVector. -// -// Note: The InlinedVectors in this file (and in cord.h) do not need to use -// the same value for their inlined size. The fact that they do is historical. -// It may be desirable for each to use a different inlined size optimized for -// that InlinedVector's usage. -// -// TODO(jgm): Benchmark to see if there's a more optimal value than 47 for -// the inlined vector size (47 exists for backward compatibility). -static const int kInlinedVectorSize = 47; - static inline bool IsRootBalanced(CordRep* node) { if (node->tag != CONCAT) { return true; @@ -182,86 +128,6 @@ static inline CordRep* VerifyTree(CordRep* node) { return node; } -// -------------------------------------------------------------------- -// Memory management - -inline CordRep* Ref(CordRep* rep) { - if (rep != nullptr) { - rep->refcount.Increment(); - } - return rep; -} - -// This internal routine is called from the cold path of Unref below. Keeping it -// in a separate routine allows good inlining of Unref into many profitable call -// sites. However, the call to this function can be highly disruptive to the -// register pressure in those callers. To minimize the cost to callers, we use -// a special LLVM calling convention that preserves most registers. This allows -// the call to this routine in cold paths to not disrupt the caller's register -// pressure. This calling convention is not available on all platforms; we -// intentionally allow LLVM to ignore the attribute rather than attempting to -// hardcode the list of supported platforms. -#if defined(__clang__) && !defined(__i386__) -#pragma clang diagnostic push -#pragma clang diagnostic ignored "-Wattributes" -__attribute__((preserve_most)) -#pragma clang diagnostic pop -#endif -static void UnrefInternal(CordRep* rep) { - assert(rep != nullptr); - - absl::InlinedVector pending; - while (true) { - assert(!rep->refcount.IsImmortal()); - if (rep->tag == CONCAT) { - CordRepConcat* rep_concat = rep->concat(); - CordRep* right = rep_concat->right; - if (!right->refcount.Decrement()) { - pending.push_back(right); - } - CordRep* left = rep_concat->left; - delete rep_concat; - rep = nullptr; - if (!left->refcount.Decrement()) { - rep = left; - continue; - } - } else if (rep->tag == EXTERNAL) { - CordRepExternal::Delete(rep); - rep = nullptr; - } else if (rep->tag == SUBSTRING) { - CordRepSubstring* rep_substring = rep->substring(); - CordRep* child = rep_substring->child; - delete rep_substring; - rep = nullptr; - if (!child->refcount.Decrement()) { - rep = child; - continue; - } - } else { - CordRepFlat::Delete(rep); - rep = nullptr; - } - - if (!pending.empty()) { - rep = pending.back(); - pending.pop_back(); - } else { - break; - } - } -} - -inline void Unref(CordRep* rep) { - // Fast-path for two common, hot cases: a null rep and a shared root. - if (ABSL_PREDICT_TRUE(rep == nullptr || - rep->refcount.DecrementExpectHighRefcount())) { - return; - } - - UnrefInternal(rep); -} - // Return the depth of a node static int Depth(const CordRep* rep) { if (rep->tag == CONCAT) { @@ -285,12 +151,14 @@ static void SetConcatChildren(CordRepConcat* concat, CordRep* left, // The returned node has a refcount of 1. static CordRep* RawConcat(CordRep* left, CordRep* right) { // Avoid making degenerate concat nodes (one child is empty) - if (left == nullptr || left->length == 0) { - Unref(left); + if (left == nullptr) return right; + if (right == nullptr) return left; + if (left->length == 0) { + CordRep::Unref(left); return right; } - if (right == nullptr || right->length == 0) { - Unref(right); + if (right->length == 0) { + CordRep::Unref(right); return left; } @@ -364,7 +232,7 @@ void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep) { static CordRep* NewSubstring(CordRep* child, size_t offset, size_t length) { // Never create empty substring nodes if (length == 0) { - Unref(child); + CordRep::Unref(child); return nullptr; } else { CordRepSubstring* rep = new CordRepSubstring(); @@ -562,13 +430,13 @@ void Cord::InlineRep::AssignSlow(const Cord::InlineRep& src) { data_ = src.data_; if (is_tree()) { - Ref(tree()); + CordRep::Ref(tree()); } } void Cord::InlineRep::ClearSlow() { if (is_tree()) { - Unref(tree()); + CordRep::Unref(tree()); } ResetToEmpty(); } @@ -577,7 +445,9 @@ void Cord::InlineRep::ClearSlow() { // Constructors and destructors Cord::Cord(const Cord& src) : contents_(src.contents_) { - Ref(contents_.tree()); // Does nothing if contents_ has embedded data + if (CordRep* tree = contents_.tree()) { + CordRep::Ref(tree); + } } Cord::Cord(absl::string_view src) { @@ -623,14 +493,18 @@ template Cord::Cord(std::string&& src); // The destruction code is separate so that the compiler can determine // that it does not need to call the destructor on a moved-from Cord. void Cord::DestroyCordSlow() { - Unref(VerifyTree(contents_.tree())); + if (CordRep* tree = contents_.tree()) { + CordRep::Unref(VerifyTree(tree)); + } } // -------------------------------------------------------------------- // Mutators void Cord::Clear() { - Unref(contents_.clear()); + if (CordRep* tree = contents_.clear()) { + CordRep::Unref(tree); + } } Cord& Cord::operator=(absl::string_view src) { @@ -641,7 +515,7 @@ Cord& Cord::operator=(absl::string_view src) { if (length <= InlineRep::kMaxInline) { // Embed into this->contents_ contents_.set_data(data, length, true); - Unref(tree); + if (tree) CordRep::Unref(tree); return *this; } if (tree != nullptr && tree->tag >= FLAT && @@ -654,7 +528,7 @@ Cord& Cord::operator=(absl::string_view src) { return *this; } contents_.set_tree(NewTree(data, length, 0)); - Unref(tree); + if (tree) CordRep::Unref(tree); return *this; } @@ -731,7 +605,7 @@ void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) { } inline CordRep* Cord::TakeRep() const& { - return Ref(contents_.tree()); + return CordRep::Ref(contents_.tree()); } inline CordRep* Cord::TakeRep() && { @@ -775,6 +649,7 @@ inline void Cord::AppendImpl(C&& src) { return; } + // Guaranteed to be a tree (kMaxBytesToCopy > kInlinedSize) contents_.AppendTree(std::forward(src).TakeRep()); } @@ -796,7 +671,7 @@ template void Cord::Append(std::string&& src); void Cord::Prepend(const Cord& src) { CordRep* src_tree = src.contents_.tree(); if (src_tree != nullptr) { - Ref(src_tree); + CordRep::Ref(src_tree); contents_.PrependTree(src_tree); return; } @@ -835,7 +710,7 @@ template void Cord::Prepend(std::string&& src); static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { if (n >= node->length) return nullptr; - if (n == 0) return Ref(node); + if (n == 0) return CordRep::Ref(node); absl::InlinedVector rhs_stack; while (node->tag == CONCAT) { @@ -853,7 +728,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { assert(n <= node->length); if (n == 0) { - Ref(node); + CordRep::Ref(node); } else { size_t start = n; size_t len = node->length - n; @@ -862,10 +737,10 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { start += node->substring()->start; node = node->substring()->child; } - node = NewSubstring(Ref(node), start, len); + node = NewSubstring(CordRep::Ref(node), start, len); } while (!rhs_stack.empty()) { - node = Concat(node, Ref(rhs_stack.back())); + node = Concat(node, CordRep::Ref(rhs_stack.back())); rhs_stack.pop_back(); } return node; @@ -876,7 +751,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { // edited in place iff that node and all its ancestors have a refcount of 1. static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { if (n >= node->length) return nullptr; - if (n == 0) return Ref(node); + if (n == 0) return CordRep::Ref(node); absl::InlinedVector lhs_stack; bool inplace_ok = node->refcount.IsOne(); @@ -896,11 +771,11 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { assert(n <= node->length); if (n == 0) { - Ref(node); + CordRep::Ref(node); } else if (inplace_ok && node->tag != EXTERNAL) { // Consider making a new buffer if the current node capacity is much // larger than the new length. - Ref(node); + CordRep::Ref(node); node->length -= n; } else { size_t start = 0; @@ -909,10 +784,10 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { start = node->substring()->start; node = node->substring()->child; } - node = NewSubstring(Ref(node), start, len); + node = NewSubstring(CordRep::Ref(node), start, len); } while (!lhs_stack.empty()) { - node = Concat(Ref(lhs_stack.back()), node); + node = Concat(CordRep::Ref(lhs_stack.back()), node); lhs_stack.pop_back(); } return node; @@ -927,7 +802,7 @@ void Cord::RemovePrefix(size_t n) { contents_.remove_prefix(n); } else { CordRep* newrep = RemovePrefixFrom(tree, n); - Unref(tree); + CordRep::Unref(tree); contents_.replace_tree(VerifyTree(newrep)); } } @@ -941,7 +816,7 @@ void Cord::RemoveSuffix(size_t n) { contents_.reduce_size(n); } else { CordRep* newrep = RemoveSuffixFrom(tree, n); - Unref(tree); + CordRep::Unref(tree); contents_.replace_tree(VerifyTree(newrep)); } } @@ -974,13 +849,13 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) { results.pop_back(); results.push_back(Concat(left, right)); } else if (pos == 0 && n == node->length) { - results.push_back(Ref(node)); + results.push_back(CordRep::Ref(node)); } else if (node->tag != CONCAT) { if (node->tag == SUBSTRING) { pos += node->substring()->start; node = node->substring()->child; } - results.push_back(NewSubstring(Ref(node), pos, n)); + results.push_back(NewSubstring(CordRep::Ref(node), pos, n)); } else if (pos + n <= node->concat()->left->length) { todo.push_back(SubRange(node->concat()->left, pos, n)); } else if (pos >= node->concat()->left->length) { @@ -1058,9 +933,9 @@ class CordForest { concat_node->left = concat_freelist_; concat_freelist_ = concat_node; } else { - Ref(concat_node->right); - Ref(concat_node->left); - Unref(concat_node); + CordRep::Ref(concat_node->right); + CordRep::Ref(concat_node->left); + CordRep::Unref(concat_node); } } else { AddNode(node); @@ -1488,7 +1363,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { if (n < current_chunk_.size()) { // Range to read is a proper subrange of the current chunk. assert(current_leaf_ != nullptr); - CordRep* subnode = Ref(current_leaf_); + CordRep* subnode = CordRep::Ref(current_leaf_); const char* data = subnode->tag == EXTERNAL ? subnode->external()->base : subnode->data; subnode = NewSubstring(subnode, current_chunk_.data() - data, n); @@ -1500,7 +1375,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // Range to read begins with a proper subrange of the current chunk. assert(!current_chunk_.empty()); assert(current_leaf_ != nullptr); - CordRep* subnode = Ref(current_leaf_); + CordRep* subnode = CordRep::Ref(current_leaf_); if (current_chunk_.size() < subnode->length) { const char* data = subnode->tag == EXTERNAL ? subnode->external()->base : subnode->data; @@ -1526,7 +1401,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // children starting from current_subtree_ if this loop exits while staying // below current_subtree_; etc.; alternatively, push parents instead of // right children on the stack). - subnode = Concat(subnode, Ref(node)); + subnode = Concat(subnode, CordRep::Ref(node)); n -= node->length; bytes_remaining_ -= node->length; node = nullptr; @@ -1548,7 +1423,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { node = node->concat()->left; } else { // Read left, descend right. - subnode = Concat(subnode, Ref(node->concat()->left)); + subnode = Concat(subnode, CordRep::Ref(node->concat()->left)); n -= node->concat()->left->length; bytes_remaining_ -= node->concat()->left->length; node = node->concat()->right; @@ -1567,7 +1442,9 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // chunk. assert(node->tag == EXTERNAL || node->tag >= FLAT); assert(length > n); - if (n > 0) subnode = Concat(subnode, NewSubstring(Ref(node), offset, n)); + if (n > 0) { + subnode = Concat(subnode, NewSubstring(CordRep::Ref(node), offset, n)); + } const char* data = node->tag == EXTERNAL ? node->external()->base : node->data; current_chunk_ = absl::string_view(data + offset + n, length - n); @@ -1691,7 +1568,9 @@ absl::string_view Cord::FlattenSlowPath() { s.size()); }); } - Unref(contents_.tree()); + if (CordRep* tree = contents_.tree()) { + CordRep::Unref(tree); + } contents_.set_tree(new_rep); return absl::string_view(new_buffer, total_size); } diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 5d5c897e..b9cdc435 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -82,6 +82,7 @@ #include "absl/strings/internal/string_constant.h" #include "absl/strings/string_view.h" #include "absl/types/optional.h" +#include "absl/types/variant.h" namespace absl { ABSL_NAMESPACE_BEGIN diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc new file mode 100644 index 00000000..35f4d235 --- /dev/null +++ b/absl/strings/internal/cord_internal.cc @@ -0,0 +1,76 @@ +// Copyright 2020 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_internal.h" + +#include +#include +#include + +#include "absl/container/inlined_vector.h" +#include "absl/strings/internal/cord_rep_flat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +ABSL_CONST_INIT std::atomic cord_ring_buffer_enabled(false); + +void CordRep::Destroy(CordRep* rep) { + assert(rep != nullptr); + + absl::InlinedVector pending; + while (true) { + assert(!rep->refcount.IsImmortal()); + if (rep->tag == CONCAT) { + CordRepConcat* rep_concat = rep->concat(); + CordRep* right = rep_concat->right; + if (!right->refcount.Decrement()) { + pending.push_back(right); + } + CordRep* left = rep_concat->left; + delete rep_concat; + rep = nullptr; + if (!left->refcount.Decrement()) { + rep = left; + continue; + } + } else if (rep->tag == EXTERNAL) { + CordRepExternal::Delete(rep); + rep = nullptr; + } else if (rep->tag == SUBSTRING) { + CordRepSubstring* rep_substring = rep->substring(); + CordRep* child = rep_substring->child; + delete rep_substring; + rep = nullptr; + if (!child->refcount.Decrement()) { + rep = child; + continue; + } + } else { + CordRepFlat::Delete(rep); + rep = nullptr; + } + + if (!pending.empty()) { + rep = pending.back(); + pending.pop_back(); + } else { + break; + } + } +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 6fb75c4f..f1af8e6e 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -22,6 +22,7 @@ #include #include "absl/base/internal/invoke.h" +#include "absl/base/optimization.h" #include "absl/container/internal/compressed_tuple.h" #include "absl/meta/type_traits.h" #include "absl/strings/string_view.h" @@ -30,6 +31,28 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { +extern std::atomic cord_ring_buffer_enabled; + +inline void enable_cord_ring_buffer(bool enable) { + cord_ring_buffer_enabled.store(enable, std::memory_order_relaxed); +} + +enum Constants { + // The inlined size to use with absl::InlinedVector. + // + // Note: The InlinedVectors in this file (and in cord.h) do not need to use + // the same value for their inlined size. The fact that they do is historical. + // It may be desirable for each to use a different inlined size optimized for + // that InlinedVector's usage. + // + // TODO(jgm): Benchmark to see if there's a more optimal value than 47 for + // the inlined vector size (47 exists for backward compatibility). + kInlinedVectorSize = 47, + + // Prefer copying blocks of at most this size, otherwise reference count. + kMaxBytesToCopy = 511 +}; + // Wraps std::atomic for reference counting. class Refcount { public: @@ -151,6 +174,34 @@ struct CordRep { inline const CordRepExternal* external() const; inline CordRepFlat* flat(); inline const CordRepFlat* flat() const; + + // -------------------------------------------------------------------- + // Memory management + + // This internal routine is called from the cold path of Unref below. Keeping + // it in a separate routine allows good inlining of Unref into many profitable + // call sites. However, the call to this function can be highly disruptive to + // the register pressure in those callers. To minimize the cost to callers, we + // use a special LLVM calling convention that preserves most registers. This + // allows the call to this routine in cold paths to not disrupt the caller's + // register pressure. This calling convention is not available on all + // platforms; we intentionally allow LLVM to ignore the attribute rather than + // attempting to hardcode the list of supported platforms. +#if defined(__clang__) && !defined(__i386__) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wattributes" + __attribute__((preserve_most)) +#pragma clang diagnostic pop +#endif + static void Destroy(CordRep* rep); + + // Increments the reference count of `rep`. + // Requires `rep` to be a non-null pointer value. + static inline CordRep* Ref(CordRep* rep); + + // Decrements the reference count of `rep`. Destroys rep if count reaches + // zero. Requires `rep` to be a non-null pointer value. + static inline void Unref(CordRep* rep); }; struct CordRepConcat : public CordRep { @@ -284,7 +335,63 @@ static_assert(sizeof(InlineData) == kMaxInline + 1, ""); static_assert(sizeof(AsTree) == sizeof(InlineData), ""); static_assert(offsetof(AsTree, tagged_size) == kMaxInline, ""); +inline CordRepConcat* CordRep::concat() { + assert(tag == CONCAT); + return static_cast(this); +} + +inline const CordRepConcat* CordRep::concat() const { + assert(tag == CONCAT); + return static_cast(this); +} + +inline CordRepSubstring* CordRep::substring() { + assert(tag == SUBSTRING); + return static_cast(this); +} + +inline const CordRepSubstring* CordRep::substring() const { + assert(tag == SUBSTRING); + return static_cast(this); +} + +inline CordRepExternal* CordRep::external() { + assert(tag == EXTERNAL); + return static_cast(this); +} + +inline const CordRepExternal* CordRep::external() const { + assert(tag == EXTERNAL); + return static_cast(this); +} + +inline CordRepFlat* CordRep::flat() { + assert(tag >= FLAT && tag <= MAX_FLAT_TAG); + return reinterpret_cast(this); +} + +inline const CordRepFlat* CordRep::flat() const { + assert(tag >= FLAT && tag <= MAX_FLAT_TAG); + return reinterpret_cast(this); +} + +inline CordRep* CordRep::Ref(CordRep* rep) { + assert(rep != nullptr); + rep->refcount.Increment(); + return rep; +} + +inline void CordRep::Unref(CordRep* rep) { + assert(rep != nullptr); + // Expect refcount to be 0. Avoiding the cost of an atomic decrement should + // typically outweigh the cost of an extra branch checking for ref == 1. + if (ABSL_PREDICT_FALSE(!rep->refcount.DecrementExpectHighRefcount())) { + Destroy(rep); + } +} + } // namespace cord_internal + ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_ diff --git a/absl/time/BUILD.bazel b/absl/time/BUILD.bazel index 991241a0..3e25ca26 100644 --- a/absl/time/BUILD.bazel +++ b/absl/time/BUILD.bazel @@ -119,6 +119,7 @@ cc_test( ":time", "//absl/base", "//absl/base:core_headers", + "//absl/flags:flag", "//absl/hash", "@com_github_google_benchmark//:benchmark_main", ], diff --git a/absl/time/duration_benchmark.cc b/absl/time/duration_benchmark.cc index 83a836c8..56820f37 100644 --- a/absl/time/duration_benchmark.cc +++ b/absl/time/duration_benchmark.cc @@ -18,9 +18,14 @@ #include #include "absl/base/attributes.h" +#include "absl/flags/flag.h" #include "absl/time/time.h" #include "benchmark/benchmark.h" +ABSL_FLAG(absl::Duration, absl_duration_flag_for_benchmark, + absl::Milliseconds(1), + "Flag to use for benchmarking duration flag access speed."); + namespace { // @@ -425,4 +430,15 @@ void BM_Duration_ParseDuration(benchmark::State& state) { } BENCHMARK(BM_Duration_ParseDuration)->DenseRange(0, kNumDurations - 1); +// +// Flag access +// +void BM_Duration_GetFlag(benchmark::State& state) { + while (state.KeepRunning()) { + benchmark::DoNotOptimize( + absl::GetFlag(FLAGS_absl_duration_flag_for_benchmark)); + } +} +BENCHMARK(BM_Duration_GetFlag); + } // namespace -- cgit v1.2.3 From 1d1ad2292bb5c7be26074e516b4cc70d9cc469f9 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 10 Feb 2021 08:52:54 -0800 Subject: Export of internal Abseil changes -- f9476c95cf7625d7b0fc4661f253b0aac4341044 by Abseil Team : Add a test to verify that the new checksum field in Hashtablez is calculated PiperOrigin-RevId: 356744293 -- ff8a3612463000e8c3d451e50367a3c65cb6cf21 by Abseil Team : Remove the implied support comment for port.h, attributes.h, and integral_types.h's C compatibility from the header documentations. Abseil-cpp is a C++ library; this brings port.h, attributes.h, and integral_types.h, into our stance for the rest of Abseil (aka, no assurance of C compatibility) There is no guarantee that future changes to port.h, attributes.h, and integral_types.h, and their dependencies, will remain compatible with C, even for macros and definitions that currently are. PiperOrigin-RevId: 356727505 -- be62292016381deee628dbb3f36cb6009bcc0282 by Abseil Team : internal change PiperOrigin-RevId: 356608125 -- 13b35f17171df3d6853ea7088797b3be611505fc by Evan Brown : Clarify the comments for CapacityToGrowth/GrowthToLowerboundCapacity methods to specify the intent that capacity should equal growth when `capacity+1 < kWidth`. Also add testing for this behavior. PiperOrigin-RevId: 356579041 GitOrigin-RevId: f9476c95cf7625d7b0fc4661f253b0aac4341044 Change-Id: Iadd094d109b4869998f2427319ef66d1cf1e8eff --- absl/base/attributes.h | 2 -- absl/base/port.h | 1 - absl/container/internal/raw_hash_set.h | 14 +++++++++--- absl/container/internal/raw_hash_set_test.cc | 34 ++++++++++++++++++++++++---- absl/status/status_test.cc | 1 - 5 files changed, 40 insertions(+), 12 deletions(-) (limited to 'absl/status/status_test.cc') diff --git a/absl/base/attributes.h b/absl/base/attributes.h index f14f7bb0..faa5b27e 100644 --- a/absl/base/attributes.h +++ b/absl/base/attributes.h @@ -18,8 +18,6 @@ // These macros are used within Abseil and allow the compiler to optimize, where // applicable, certain function calls. // -// This file is used for both C and C++! -// // Most macros here are exposing GCC or Clang features, and are stubbed out for // other compilers. // diff --git a/absl/base/port.h b/absl/base/port.h index 6c28068d..5bc4d6cd 100644 --- a/absl/base/port.h +++ b/absl/base/port.h @@ -14,7 +14,6 @@ // // This files is a forwarding header for other headers containing various // portability macros and functions. -// This file is used for both C and C++! #ifndef ABSL_BASE_PORT_H_ #define ABSL_BASE_PORT_H_ diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 74b2ef4c..80fc2cba 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -468,8 +468,16 @@ inline size_t NormalizeCapacity(size_t n) { return n ? ~size_t{} >> countl_zero(n) : 1; } -// We use 7/8th as maximum load factor. -// For 16-wide groups, that gives an average of two empty slots per group. +// General notes on capacity/growth methods below: +// - We use 7/8th as maximum load factor. For 16-wide groups, that gives an +// average of two empty slots per group. +// - For (capacity+1) >= Group::kWidth, growth is 7/8*capacity. +// - For (capacity+1) < Group::kWidth, growth == capacity. In this case, we +// never need to probe (the whole table fits in one group) so we don't need a +// load factor less than 1. + +// Given `capacity` of the table, returns the size (i.e. number of full slots) +// at which we should grow the capacity. inline size_t CapacityToGrowth(size_t capacity) { assert(IsValidCapacity(capacity)); // `capacity*7/8` @@ -480,7 +488,7 @@ inline size_t CapacityToGrowth(size_t capacity) { return capacity - capacity / 8; } // From desired "growth" to a lowerbound of the necessary capacity. -// Might not be a valid one and required NormalizeCapacity(). +// Might not be a valid one and requires NormalizeCapacity(). inline size_t GrowthToLowerboundCapacity(size_t growth) { // `growth*8/7` if (Group::kWidth == 8 && growth == 7) { diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 0fba46ff..81c4b47c 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -14,6 +14,7 @@ #include "absl/container/internal/raw_hash_set.h" +#include #include #include #include @@ -22,6 +23,8 @@ #include #include #include +#include +#include #include "gmock/gmock.h" #include "gtest/gtest.h" @@ -48,11 +51,10 @@ struct RawHashSetTestOnlyAccess { namespace { -using ::testing::DoubleNear; using ::testing::ElementsAre; +using ::testing::Eq; using ::testing::Ge; using ::testing::Lt; -using ::testing::Optional; using ::testing::Pair; using ::testing::UnorderedElementsAre; @@ -75,8 +77,14 @@ TEST(Util, GrowthAndCapacity) { for (size_t growth = 0; growth < 10000; ++growth) { SCOPED_TRACE(growth); size_t capacity = NormalizeCapacity(GrowthToLowerboundCapacity(growth)); - // The capacity is large enough for `growth` + // The capacity is large enough for `growth`. EXPECT_THAT(CapacityToGrowth(capacity), Ge(growth)); + // For (capacity+1) < kWidth, growth should equal capacity. + if (capacity + 1 < Group::kWidth) { + EXPECT_THAT(CapacityToGrowth(capacity), Eq(capacity)); + } else { + EXPECT_THAT(CapacityToGrowth(capacity), Lt(capacity)); + } if (growth != 0 && capacity > 1) { // There is no smaller capacity that works. EXPECT_THAT(CapacityToGrowth(capacity / 2), Lt(growth)); @@ -1875,18 +1883,34 @@ TEST(RawHashSamplerTest, Sample) { auto& sampler = HashtablezSampler::Global(); size_t start_size = 0; - start_size += sampler.Iterate([&](const HashtablezInfo&) { ++start_size; }); + std::unordered_set preexisting_info; + start_size += sampler.Iterate([&](const HashtablezInfo& info) { + preexisting_info.insert(&info); + ++start_size; + }); std::vector tables; for (int i = 0; i < 1000000; ++i) { tables.emplace_back(); tables.back().insert(1); + tables.back().insert(i % 5); } size_t end_size = 0; - end_size += sampler.Iterate([&](const HashtablezInfo&) { ++end_size; }); + std::unordered_map observed_checksums; + end_size += sampler.Iterate([&](const HashtablezInfo& info) { + if (preexisting_info.count(&info) == 0) { + observed_checksums[info.hashes_bitwise_xor.load( + std::memory_order_relaxed)]++; + } + ++end_size; + }); EXPECT_NEAR((end_size - start_size) / static_cast(tables.size()), 0.01, 0.005); + EXPECT_EQ(observed_checksums.size(), 5); + for (const auto& [_, count] : observed_checksums) { + EXPECT_NEAR((100 * count) / static_cast(tables.size()), 0.2, 0.05); + } } #endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE diff --git a/absl/status/status_test.cc b/absl/status/status_test.cc index 25333fa2..24eaed61 100644 --- a/absl/status/status_test.cc +++ b/absl/status/status_test.cc @@ -460,5 +460,4 @@ TEST(Status, Swap) { test_swap(no_payload, with_payload); test_swap(with_payload, no_payload); } - } // namespace -- cgit v1.2.3 From a76698790753d2ec71f655cdc84d61bcb27780d4 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 1 Mar 2021 06:24:39 -0800 Subject: Export of internal Abseil changes -- a9eb3c976c6d8ef4fca3d416847f8fca4bd90dd7 by Derek Mauro : Remove the deprecated container library, which doesn't do anything. This will help prevent user confusion, as seen in #183. PiperOrigin-RevId: 360172262 -- 4f872f651e25a528bdc59ee4e24543fbbd358f00 by Abseil Team : Remove unused nspace alias. PiperOrigin-RevId: 359487559 -- 43e877e464886cf9226012f5bb47910b8995e70f by Abseil Team : Create a StatusToStringMode to control how the ToString behaves. PiperOrigin-RevId: 359339603 -- 0da1291569e167341613359846948c72c8a838e1 by Greg Falcon : Fix a bug in SimpleAtoi/SimpleAtof, which accepted a prefix of "+-" (e.g., "+-5" was parsed as 5.0). This regression was introduced when we migrated these functions to use absl::from_chars. PiperOrigin-RevId: 359135105 GitOrigin-RevId: a9eb3c976c6d8ef4fca3d416847f8fca4bd90dd7 Change-Id: I0e2072cad80651e473ba1d34b1fb3a033dfaba80 --- absl/container/CMakeLists.txt | 9 ------ absl/flags/reflection_test.cc | 2 -- absl/status/status.cc | 30 +++++++++++-------- absl/status/status.h | 68 +++++++++++++++++++++++++++++++++++++------ absl/status/status_test.cc | 17 +++++++++++ absl/strings/numbers.cc | 10 +++++++ absl/strings/numbers_test.cc | 22 ++++++++++++++ 7 files changed, 126 insertions(+), 32 deletions(-) (limited to 'absl/status/status_test.cc') diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index eb202c45..2d7d0e65 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -14,15 +14,6 @@ # limitations under the License. # -# This is deprecated and will be removed in the future. It also doesn't do -# anything anyways. Prefer to use the library associated with the API you are -# using. -absl_cc_library( - NAME - container - PUBLIC -) - absl_cc_library( NAME btree diff --git a/absl/flags/reflection_test.cc b/absl/flags/reflection_test.cc index 4c809009..79cfa90c 100644 --- a/absl/flags/reflection_test.cc +++ b/absl/flags/reflection_test.cc @@ -34,8 +34,6 @@ ABSL_RETIRED_FLAG(bool, bool_retired_flag, false, "bool_retired_flag help"); namespace { -namespace flags = absl::flags_internal; - class ReflectionTest : public testing::Test { protected: void SetUp() override { flag_saver_ = absl::make_unique(); } diff --git a/absl/status/status.cc b/absl/status/status.cc index 7962bb9e..51a0d268 100644 --- a/absl/status/status.cc +++ b/absl/status/status.cc @@ -291,20 +291,26 @@ bool Status::EqualsSlow(const absl::Status& a, const absl::Status& b) { return true; } -std::string Status::ToStringSlow() const { +std::string Status::ToStringSlow(StatusToStringMode mode) const { std::string text; absl::StrAppend(&text, absl::StatusCodeToString(code()), ": ", message()); - status_internal::StatusPayloadPrinter printer = - status_internal::GetStatusPayloadPrinter(); - this->ForEachPayload([&](absl::string_view type_url, - const absl::Cord& payload) { - absl::optional result; - if (printer) result = printer(type_url, payload); - absl::StrAppend( - &text, " [", type_url, "='", - result.has_value() ? *result : absl::CHexEscape(std::string(payload)), - "']"); - }); + + const bool with_payload = (mode & StatusToStringMode::kWithPayload) == + StatusToStringMode::kWithPayload; + + if (with_payload) { + status_internal::StatusPayloadPrinter printer = + status_internal::GetStatusPayloadPrinter(); + this->ForEachPayload([&](absl::string_view type_url, + const absl::Cord& payload) { + absl::optional result; + if (printer) result = printer(type_url, payload); + absl::StrAppend( + &text, " [", type_url, "='", + result.has_value() ? *result : absl::CHexEscape(std::string(payload)), + "']"); + }); + } return text; } diff --git a/absl/status/status.h b/absl/status/status.h index 118f64fb..df9e330c 100644 --- a/absl/status/status.h +++ b/absl/status/status.h @@ -280,6 +280,55 @@ std::string StatusCodeToString(StatusCode code); // Streams StatusCodeToString(code) to `os`. std::ostream& operator<<(std::ostream& os, StatusCode code); +// absl::StatusToStringMode +// +// An `absl::StatusToStringMode` is an enumerated type indicating how +// `absl::Status::ToString()` should construct the output string for an non-ok +// status. +enum class StatusToStringMode : int { + // ToString will not contain any extra data (such as payloads). It will only + // contain the error code and message, if any. + kWithNoExtraData = 0, + // ToString will contain the payloads. + kWithPayload = 1 << 0, +}; + +// absl::StatusToStringMode is specified as a bitmask type, which means the +// following operations must be provided: +inline constexpr StatusToStringMode operator&(StatusToStringMode lhs, + StatusToStringMode rhs) { + return static_cast(static_cast(lhs) & + static_cast(rhs)); +} +inline constexpr StatusToStringMode operator|(StatusToStringMode lhs, + StatusToStringMode rhs) { + return static_cast(static_cast(lhs) | + static_cast(rhs)); +} +inline constexpr StatusToStringMode operator^(StatusToStringMode lhs, + StatusToStringMode rhs) { + return static_cast(static_cast(lhs) ^ + static_cast(rhs)); +} +inline constexpr StatusToStringMode operator~(StatusToStringMode arg) { + return static_cast(~static_cast(arg)); +} +inline StatusToStringMode& operator&=(StatusToStringMode& lhs, + StatusToStringMode rhs) { + lhs = lhs & rhs; + return lhs; +} +inline StatusToStringMode& operator|=(StatusToStringMode& lhs, + StatusToStringMode rhs) { + lhs = lhs | rhs; + return lhs; +} +inline StatusToStringMode& operator^=(StatusToStringMode& lhs, + StatusToStringMode rhs) { + lhs = lhs ^ rhs; + return lhs; +} + // absl::Status // // The `absl::Status` class is generally used to gracefully handle errors @@ -443,15 +492,17 @@ class ABSL_MUST_USE_RESULT Status final { // Status::ToString() // - // Returns a combination of the error code name, the message and any - // associated payload messages. This string is designed simply to be human - // readable and its exact format should not be load bearing. Do not depend on - // the exact format of the result of `ToString()` which is subject to change. + // Returns a string based on the `mode`. By default, it returns combination of + // the error code name, the message and any associated payload messages. This + // string is designed simply to be human readable and its exact format should + // not be load bearing. Do not depend on the exact format of the result of + // `ToString()` which is subject to change. // // The printed code name and the message are generally substrings of the // result, and the payloads to be printed use the status payload printer // mechanism (which is internal). - std::string ToString() const; + std::string ToString( + StatusToStringMode mode = StatusToStringMode::kWithPayload) const; // Status::IgnoreError() // @@ -582,8 +633,7 @@ class ABSL_MUST_USE_RESULT Status final { static uintptr_t PointerToRep(status_internal::StatusRep* r); static status_internal::StatusRep* RepToPointer(uintptr_t r); - // Returns string for non-ok Status. - std::string ToStringSlow() const; + std::string ToStringSlow(StatusToStringMode mode) const; // Status supports two different representations. // - When the low bit is off it is an inlined representation. @@ -747,8 +797,8 @@ inline bool operator!=(const Status& lhs, const Status& rhs) { return !(lhs == rhs); } -inline std::string Status::ToString() const { - return ok() ? "OK" : ToStringSlow(); +inline std::string Status::ToString(StatusToStringMode mode) const { + return ok() ? "OK" : ToStringSlow(mode); } inline void Status::IgnoreError() const { diff --git a/absl/status/status_test.cc b/absl/status/status_test.cc index 24eaed61..7116ba67 100644 --- a/absl/status/status_test.cc +++ b/absl/status/status_test.cc @@ -280,6 +280,23 @@ TEST(Status, ToString) { HasSubstr("[bar='\\xff']"))); } +TEST(Status, ToStringMode) { + absl::Status s(absl::StatusCode::kInternal, "fail"); + s.SetPayload("foo", absl::Cord("bar")); + s.SetPayload("bar", absl::Cord("\377")); + + EXPECT_EQ("INTERNAL: fail", + s.ToString(absl::StatusToStringMode::kWithNoExtraData)); + + EXPECT_THAT(s.ToString(absl::StatusToStringMode::kWithPayload), + AllOf(HasSubstr("INTERNAL: fail"), HasSubstr("[foo='bar']"), + HasSubstr("[bar='\\xff']"))); + + EXPECT_THAT(s.ToString(~absl::StatusToStringMode::kWithPayload), + AllOf(HasSubstr("INTERNAL: fail"), Not(HasSubstr("[foo='bar']")), + Not(HasSubstr("[bar='\\xff']")))); +} + absl::Status EraseAndReturn(const absl::Status& base) { absl::Status copy = base; EXPECT_TRUE(copy.ErasePayload(kUrl1)); diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index e6bf44ce..966d94bd 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -46,8 +46,13 @@ ABSL_NAMESPACE_BEGIN bool SimpleAtof(absl::string_view str, float* out) { *out = 0.0; str = StripAsciiWhitespace(str); + // std::from_chars doesn't accept an initial +, but SimpleAtof does, so if one + // is present, skip it, while avoiding accepting "+-0" as valid. if (!str.empty() && str[0] == '+') { str.remove_prefix(1); + if (!str.empty() && str[0] == '-') { + return false; + } } auto result = absl::from_chars(str.data(), str.data() + str.size(), *out); if (result.ec == std::errc::invalid_argument) { @@ -72,8 +77,13 @@ bool SimpleAtof(absl::string_view str, float* out) { bool SimpleAtod(absl::string_view str, double* out) { *out = 0.0; str = StripAsciiWhitespace(str); + // std::from_chars doesn't accept an initial +, but SimpleAtod does, so if one + // is present, skip it, while avoiding accepting "+-0" as valid. if (!str.empty() && str[0] == '+') { str.remove_prefix(1); + if (!str.empty() && str[0] == '-') { + return false; + } } auto result = absl::from_chars(str.data(), str.data() + str.size(), *out); if (result.ec == std::errc::invalid_argument) { diff --git a/absl/strings/numbers_test.cc b/absl/strings/numbers_test.cc index 27616bf8..f3103106 100644 --- a/absl/strings/numbers_test.cc +++ b/absl/strings/numbers_test.cc @@ -392,6 +392,28 @@ TEST(NumbersTest, Atod) { EXPECT_TRUE(std::isnan(d)); } +TEST(NumbersTest, Prefixes) { + double d; + EXPECT_FALSE(absl::SimpleAtod("++1", &d)); + EXPECT_FALSE(absl::SimpleAtod("+-1", &d)); + EXPECT_FALSE(absl::SimpleAtod("-+1", &d)); + EXPECT_FALSE(absl::SimpleAtod("--1", &d)); + EXPECT_TRUE(absl::SimpleAtod("-1", &d)); + EXPECT_EQ(d, -1.); + EXPECT_TRUE(absl::SimpleAtod("+1", &d)); + EXPECT_EQ(d, +1.); + + float f; + EXPECT_FALSE(absl::SimpleAtof("++1", &f)); + EXPECT_FALSE(absl::SimpleAtof("+-1", &f)); + EXPECT_FALSE(absl::SimpleAtof("-+1", &f)); + EXPECT_FALSE(absl::SimpleAtof("--1", &f)); + EXPECT_TRUE(absl::SimpleAtof("-1", &f)); + EXPECT_EQ(f, -1.f); + EXPECT_TRUE(absl::SimpleAtof("+1", &f)); + EXPECT_EQ(f, +1.f); +} + TEST(NumbersTest, Atoenum) { enum E01 { E01_zero = 0, -- cgit v1.2.3 From dcf4899377ca63246efb17f5468c40913855777c Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 17 Mar 2021 20:08:11 -0700 Subject: Export of internal Abseil changes -- 8e75347c10d85112296811be6ef35761744ad9bc by Derek Mauro : Big update to LTS release process * Add create_lts.py script to to the LTS modification This is simpler than copybara since very few changes are needed * Use the default installation paths instead of a versioned path. If a versioned path is needed, this is easy to change on the commandline. * Make the integration test use the LTS transformed version * Test both static and dynamic linking (fixes pkg-config dynamic linking) PiperOrigin-RevId: 363566934 -- e00e971a2de3138861f5e1900201c9cc7788f714 by Laramie Leavitt : Add a non-compile test to absl::BitGenRef for temporaries. PiperOrigin-RevId: 363437284 -- 3685644ec115d99789de32aceb76c32a00756fea by Derek Mauro : Make OSS code consistent with internal code by using the forward declaration of absl::Status that contains ABSL_MUST_USE_RESULT. PiperOrigin-RevId: 363426906 -- b85fec142c3aa3f632fa985f9f8f73a253819723 by Evan Brown : Move raw_hash_set::infoz_ into raw_hash_set::settings_. This reduces the size of raw_hash_sets by alignof(size_t) bytes when hashtablez is disabled. PiperOrigin-RevId: 363034264 -- c6fde3b17e5845191eb8b2bfc1760c8bfb9573ff by Mark Barolak : Internal change PiperOrigin-RevId: 362990378 -- 81713cf964905b43d1cbe32ce5fed97539029625 by Abseil Team : Fix typo in comment (execeptions -> exceptions). PiperOrigin-RevId: 362946191 -- 3ee92ca470feca44da417b03ee45a915c6eb5155 by Abseil Team : Add absl::FindAndReportLeaks and routes it to the corresponding __lsan_do_recoverable_leak_check. PiperOrigin-RevId: 362622199 -- b95b7194b20e02c20d72289fbc79a0d35b82e256 by Abseil Team : Add `kWithEverything` to StatusToStringMode PiperOrigin-RevId: 362595218 -- 0a960d96a0014eab7e1c55b479269450ed8e98d7 by Abseil Team : Accept e.g. ".__uniq" as a valid clone name. Further, bring the implementation on par with libiberty's demangler grammar. Clang introduced option -funique-internal-linkage-names that adds the suffix ".__uniq.[0-9]+" to internal linkage functions to give them a globally unique identifier. The suffix was designed to work with existing demanglers which do recognize a "_" along with the alphanumeric string. This change enhances the demangler to allow "_" with the alphanumeric string. Please refer to libiberty's cp-demangle.c where function d_clone_suffix implements the demangling of clone suffixes : 1. '_' is accepted as a valid character with the alphanumeric sequence. 2. The alphanumberic sequence is optional. 3. The digit sequence is optional. PiperOrigin-RevId: 362557420 -- 2ac5ea212c150afd2f58025a5cab8c45d16949c6 by Abseil Team : Change variable name 'slots' to 'slot_count' to avoid name-clash with Qt builds. PiperOrigin-RevId: 362556289 -- 934f0f409c9c548716a46363d6e243406fad4028 by Mark Barolak : Clarify the comment on ABSL_CACHELINE_SIZE to indicate that the macro definition itself shouldn't change, but rather that call sites should change when possible. This addresses the request for improved documentation in https://github.com/abseil/abseil-cpp/pull/842. PiperOrigin-RevId: 362354288 GitOrigin-RevId: 8e75347c10d85112296811be6ef35761744ad9bc Change-Id: I33ec8561d8d645c3353e9d2dd447501d0e1825a7 --- CMake/AbseilDll.cmake | 9 +- CMake/AbseilHelpers.cmake | 22 +++-- CMake/AbseilInstallDirs.cmake | 20 ---- CMake/install_test_project/test.sh | 138 +++++++-------------------- CMakeLists.txt | 14 +-- absl/base/optimization.h | 5 +- absl/container/internal/btree.h | 8 +- absl/container/internal/raw_hash_set.h | 57 +++++------ absl/container/internal/raw_hash_set_test.cc | 39 +++++--- absl/debugging/internal/demangle.cc | 28 +++--- absl/debugging/internal/demangle_test.cc | 30 +++++- absl/debugging/leak_check.cc | 1 + absl/debugging/leak_check.h | 13 +++ absl/status/internal/status_internal.h | 11 +++ absl/status/status.h | 9 +- absl/status/status_test.cc | 4 + absl/status/statusor.h | 2 +- absl/strings/numbers.h | 1 + ci/cmake_install_test.sh | 18 ++-- create_lts.py | 121 +++++++++++++++++++++++ 20 files changed, 339 insertions(+), 211 deletions(-) delete mode 100644 CMake/AbseilInstallDirs.cmake create mode 100755 create_lts.py (limited to 'absl/status/status_test.cc') diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 39f85f2f..253c73ff 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -1,4 +1,5 @@ include(CMakeParseArguments) +include(GNUInstallDirs) set(ABSL_INTERNAL_DLL_FILES "algorithm/algorithm.h" @@ -500,7 +501,7 @@ function(absl_make_dll) abseil_dll PUBLIC "$" - $ + $ ) target_compile_options( @@ -518,8 +519,8 @@ function(absl_make_dll) ${ABSL_CC_LIB_DEFINES} ) install(TARGETS abseil_dll EXPORT ${PROJECT_NAME}Targets - RUNTIME DESTINATION ${ABSL_INSTALL_BINDIR} - LIBRARY DESTINATION ${ABSL_INSTALL_LIBDIR} - ARCHIVE DESTINATION ${ABSL_INSTALL_LIBDIR} + RUNTIME DESTINATION ${CMAKE_INSTALL_BINDIR} + LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR} + ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR} ) endfunction() diff --git a/CMake/AbseilHelpers.cmake b/CMake/AbseilHelpers.cmake index 1541435d..4f6394ab 100644 --- a/CMake/AbseilHelpers.cmake +++ b/CMake/AbseilHelpers.cmake @@ -17,7 +17,6 @@ include(CMakeParseArguments) include(AbseilConfigureCopts) include(AbseilDll) -include(AbseilInstallDirs) # The IDE folder for Abseil that will be used if Abseil is included in a CMake # project that sets @@ -151,6 +150,10 @@ function(absl_cc_library) endif() foreach(dep ${ABSL_CC_LIB_DEPS}) if(${dep} MATCHES "^absl::(.*)") + # Join deps with commas. + if(PC_DEPS) + set(PC_DEPS "${PC_DEPS},") + endif() set(PC_DEPS "${PC_DEPS} absl_${CMAKE_MATCH_1} = ${PC_VERSION}") endif() endforeach() @@ -167,14 +170,14 @@ function(absl_cc_library) FILE(GENERATE OUTPUT "${CMAKE_BINARY_DIR}/lib/pkgconfig/absl_${_NAME}.pc" CONTENT "\ prefix=${CMAKE_INSTALL_PREFIX}\n\ exec_prefix=\${prefix}\n\ -libdir=\${prefix}/lib\n\ -includedir=\${prefix}/include\n\ +libdir=\${prefix}/${CMAKE_INSTALL_LIBDIR}\n\ +includedir=\${prefix}/${CMAKE_INSTALL_INCLUDEDIR}\n\ \n\ Name: absl_${_NAME}\n\ Description: Abseil ${_NAME} library\n\ URL: https://abseil.io/\n\ Version: ${PC_VERSION}\n\ -Requires.private:${PC_DEPS}\n\ +Requires:${PC_DEPS}\n\ Libs: -L\${libdir} $ $<$>:-labsl_${_NAME}>\n\ Cflags: -I\${includedir}${PC_CFLAGS}\n") INSTALL(FILES "${CMAKE_BINARY_DIR}/lib/pkgconfig/absl_${_NAME}.pc" @@ -235,7 +238,7 @@ Cflags: -I\${includedir}${PC_CFLAGS}\n") target_include_directories(${_NAME} PUBLIC "$" - $ + $ ) target_compile_options(${_NAME} PRIVATE ${ABSL_CC_LIB_COPTS}) @@ -260,7 +263,6 @@ Cflags: -I\${includedir}${PC_CFLAGS}\n") if(ABSL_ENABLE_INSTALL) set_target_properties(${_NAME} PROPERTIES OUTPUT_NAME "absl_${_NAME}" - # TODO(b/173696973): Figure out how to set SOVERSION for LTS releases. SOVERSION 0 ) endif() @@ -270,7 +272,7 @@ Cflags: -I\${includedir}${PC_CFLAGS}\n") target_include_directories(${_NAME} INTERFACE "$" - $ + $ ) if (_build_type STREQUAL "dll") @@ -290,9 +292,9 @@ Cflags: -I\${includedir}${PC_CFLAGS}\n") # installed abseil can't be tested. if(NOT ABSL_CC_LIB_TESTONLY AND ABSL_ENABLE_INSTALL) install(TARGETS ${_NAME} EXPORT ${PROJECT_NAME}Targets - RUNTIME DESTINATION ${ABSL_INSTALL_BINDIR} - LIBRARY DESTINATION ${ABSL_INSTALL_LIBDIR} - ARCHIVE DESTINATION ${ABSL_INSTALL_LIBDIR} + RUNTIME DESTINATION ${CMAKE_INSTALL_BINDIR} + LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR} + ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR} ) endif() diff --git a/CMake/AbseilInstallDirs.cmake b/CMake/AbseilInstallDirs.cmake deleted file mode 100644 index 6fc914b6..00000000 --- a/CMake/AbseilInstallDirs.cmake +++ /dev/null @@ -1,20 +0,0 @@ -include(GNUInstallDirs) - -# absl_VERSION is only set if we are an LTS release being installed, in which -# case it may be into a system directory and so we need to make subdirectories -# for each installed version of Abseil. This mechanism is implemented in -# Abseil's internal Copybara (https://github.com/google/copybara) workflows and -# isn't visible in the CMake buildsystem itself. - -if(absl_VERSION) - set(ABSL_SUBDIR "${PROJECT_NAME}_${PROJECT_VERSION}") - set(ABSL_INSTALL_BINDIR "${CMAKE_INSTALL_BINDIR}/${ABSL_SUBDIR}") - set(ABSL_INSTALL_CONFIGDIR "${CMAKE_INSTALL_LIBDIR}/cmake/${ABSL_SUBDIR}") - set(ABSL_INSTALL_INCLUDEDIR "${CMAKE_INSTALL_INCLUDEDIR}/${ABSL_SUBDIR}") - set(ABSL_INSTALL_LIBDIR "${CMAKE_INSTALL_LIBDIR}/${ABSL_SUBDIR}") -else() - set(ABSL_INSTALL_BINDIR "${CMAKE_INSTALL_BINDIR}") - set(ABSL_INSTALL_CONFIGDIR "${CMAKE_INSTALL_LIBDIR}/cmake/${PROJECT_NAME}") - set(ABSL_INSTALL_INCLUDEDIR "${CMAKE_INSTALL_INCLUDEDIR}") - set(ABSL_INSTALL_LIBDIR "${CMAKE_INSTALL_LIBDIR}") -endif() diff --git a/CMake/install_test_project/test.sh b/CMake/install_test_project/test.sh index ddc7726b..a3d39773 100755 --- a/CMake/install_test_project/test.sh +++ b/CMake/install_test_project/test.sh @@ -13,70 +13,44 @@ # 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. - -# "Unit" and integration tests for Absl CMake installation - -# TODO(absl-team): This script isn't fully hermetic because -# -DABSL_USE_GOOGLETEST_HEAD=ON means that this script isn't pinned to a fixed -# version of GoogleTest. This means that an upstream change to GoogleTest could -# break this test. Fix this by allowing this script to pin to a known-good -# version of GoogleTest. +# +# Unit and integration tests for Abseil LTS CMake installation # Fail on any error. Treat unset variables an error. Print commands as executed. set -euox pipefail -install_absl() { - pushd "${absl_build_dir}" - if [[ "${#}" -eq 1 ]]; then - cmake -DCMAKE_INSTALL_PREFIX="${1}" "${absl_dir}" - else - cmake "${absl_dir}" - fi - cmake --build . --target install -- -j - popd -} - -uninstall_absl() { - xargs rm < "${absl_build_dir}"/install_manifest.txt - rm -rf "${absl_build_dir}" - mkdir -p "${absl_build_dir}" -} - -lts_install="" - -while getopts ":l" lts; do - case "${lts}" in - l ) - lts_install="true" - ;; - esac -done +source ci/cmake_common.sh absl_dir=/abseil-cpp -absl_build_dir=/buildfs/absl-build +absl_build_dir=/buildfs project_dir="${absl_dir}"/CMake/install_test_project project_build_dir=/buildfs/project-build -mkdir -p "${absl_build_dir}" -mkdir -p "${project_build_dir}" - -if [[ "${lts_install}" ]]; then - install_dir="/usr/local" -else - install_dir="${project_build_dir}"/install +build_shared_libs="OFF" +if [ "${LINK_TYPE:-}" = "DYNAMIC" ]; then + build_shared_libs="ON" fi -mkdir -p "${install_dir}" -# Test build, install, and link against installed abseil -pushd "${project_build_dir}" -if [[ "${lts_install}" ]]; then - install_absl - cmake "${project_dir}" -else - install_absl "${install_dir}" - cmake "${project_dir}" -DCMAKE_PREFIX_PATH="${install_dir}" -fi +# Run the LTS transformations +./create_lts.py 99998877 + +# Install Abseil +pushd "${absl_build_dir}" +cmake "${absl_dir}" \ + -DABSL_GOOGLETEST_DOWNLOAD_URL="${ABSL_GOOGLETEST_DOWNLOAD_URL}" \ + -DCMAKE_BUILD_TYPE=Release \ + -DBUILD_TESTING=ON \ + -DBUILD_SHARED_LIBS="${build_shared_libs}" +make -j $(nproc) +ctest -j $(nproc) +make install +ldconfig +popd +# Test the project against the installed Abseil +mkdir -p "${project_build_dir}" +pushd "${project_build_dir}" +cmake "${project_dir}" cmake --build . --target simple output="$(${project_build_dir}/simple "printme" 2>&1)" @@ -88,32 +62,8 @@ fi popd -# Test that we haven't accidentally made absl::abslblah -pushd "${install_dir}" - -# Starting in CMake 3.12 the default install dir is lib$bit_width -if [[ -d lib64 ]]; then - libdir="lib64" -elif [[ -d lib ]]; then - libdir="lib" -else - echo "ls *, */*, */*/*:" - ls * - ls */* - ls */*/* - echo "unknown lib dir" -fi - -if [[ "${lts_install}" ]]; then - # LTS versions append the date of the release to the subdir. - # 9999/99/99 is the dummy date used in the local_lts workflow. - absl_subdir="absl_99999999" -else - absl_subdir="absl" -fi - -if ! grep absl::strings "${libdir}/cmake/${absl_subdir}/abslTargets.cmake"; then - cat "${libdir}"/cmake/absl/abslTargets.cmake +if ! grep absl::strings "/usr/local/lib/cmake/absl/abslTargets.cmake"; then + cat "/usr/local/lib/cmake/absl/abslTargets.cmake" echo "CMake targets named incorrectly" exit 1 fi @@ -129,34 +79,18 @@ int main(int argc, char **argv) { return EXIT_SUCCESS; } EOF -export PKG_CONFIG_PATH="${install_dir}/${libdir}/pkgconfig" -pc_args=($(pkg-config --cflags --libs --static absl_str_format)) -g++ -static -o hello-abseil hello-abseil.cc "${pc_args[@]}" + +if [ "${LINK_TYPE:-}" != "DYNAMIC" ]; then + pc_args=($(pkg-config --cflags --libs --static absl_str_format)) + g++ -static -o hello-abseil hello-abseil.cc "${pc_args[@]}" +else + pc_args=($(pkg-config --cflags --libs absl_str_format)) + g++ -o hello-abseil hello-abseil.cc "${pc_args[@]}" +fi hello="$(./hello-abseil)" [[ "${hello}" == "Hello Abseil!" ]] -popd -uninstall_absl popd -if [[ ! "${lts_install}" ]]; then - # Test that we warn if installed without a prefix or a system prefix - output="$(install_absl 2>&1)" - if [[ "${output}" != *"Please set CMAKE_INSTALL_PREFIX"* ]]; then - echo "Install without prefix didn't warn as expected. Output:" - echo "${output}" - exit 1 - fi - uninstall_absl - - output="$(install_absl /usr 2>&1)" - if [[ "${output}" != *"Please set CMAKE_INSTALL_PREFIX"* ]]; then - echo "Install with /usr didn't warn as expected. Output:" - echo "${output}" - exit 1 - fi - uninstall_absl -fi - echo "Install test complete!" exit 0 diff --git a/CMakeLists.txt b/CMakeLists.txt index 8843ee79..e09e335c 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -45,7 +45,7 @@ endif (POLICY CMP0077) # This must come before the project() and include(CTest) lines. OPTION(BUILD_TESTING "Build tests" OFF) -project(absl CXX) +project(absl LANGUAGES CXX) include(CTest) # Output directory is correct by default for most build setups. However, when @@ -67,8 +67,8 @@ list(APPEND CMAKE_MODULE_PATH ${CMAKE_CURRENT_LIST_DIR}/absl/copts ) -include(AbseilInstallDirs) include(CMakePackageConfigHelpers) +include(GNUInstallDirs) include(AbseilDll) include(AbseilHelpers) @@ -159,16 +159,16 @@ if(ABSL_ENABLE_INSTALL) # install as a subdirectory only install(EXPORT ${PROJECT_NAME}Targets NAMESPACE absl:: - DESTINATION "${ABSL_INSTALL_CONFIGDIR}" + DESTINATION "${CMAKE_INSTALL_LIBDIR}/cmake/${PROJECT_NAME}" ) configure_package_config_file( CMake/abslConfig.cmake.in "${PROJECT_BINARY_DIR}/${PROJECT_NAME}Config.cmake" - INSTALL_DESTINATION "${ABSL_INSTALL_CONFIGDIR}" + INSTALL_DESTINATION "${CMAKE_INSTALL_LIBDIR}/cmake/${PROJECT_NAME}" ) install(FILES "${PROJECT_BINARY_DIR}/${PROJECT_NAME}Config.cmake" - DESTINATION "${ABSL_INSTALL_CONFIGDIR}" + DESTINATION "${CMAKE_INSTALL_LIBDIR}/cmake/${PROJECT_NAME}" ) # Abseil only has a version in LTS releases. This mechanism is accomplished @@ -181,12 +181,12 @@ if(ABSL_ENABLE_INSTALL) ) install(FILES "${PROJECT_BINARY_DIR}/${PROJECT_NAME}ConfigVersion.cmake" - DESTINATION ${ABSL_INSTALL_CONFIGDIR} + DESTINATION "${CMAKE_INSTALL_LIBDIR}/cmake/${PROJECT_NAME}" ) endif() # absl_VERSION install(DIRECTORY absl - DESTINATION ${ABSL_INSTALL_INCLUDEDIR} + DESTINATION ${CMAKE_INSTALL_INCLUDEDIR} FILES_MATCHING PATTERN "*.inc" PATTERN "*.h" diff --git a/absl/base/optimization.h b/absl/base/optimization.h index 6332b625..d090be12 100644 --- a/absl/base/optimization.h +++ b/absl/base/optimization.h @@ -106,9 +106,10 @@ // Cacheline aligning objects properly allows constructive memory sharing and // prevents destructive (or "false") memory sharing. // -// NOTE: this macro should be replaced with usage of `alignas()` using +// NOTE: callers should replace uses of this macro with `alignas()` using // `std::hardware_constructive_interference_size` and/or -// `std::hardware_destructive_interference_size` when available within C++17. +// `std::hardware_destructive_interference_size` when C++17 becomes available to +// them. // // See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0154r1.html // for more information. diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 00444a53..0bb38366 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -579,10 +579,10 @@ class btree_node { }; // Leaves can have less than kNodeSlots values. - constexpr static layout_type LeafLayout(const int slots = kNodeSlots) { + constexpr static layout_type LeafLayout(const int slot_count = kNodeSlots) { return layout_type(/*parent*/ 1, /*position, start, finish, max_count*/ 4, - /*slots*/ slots, + /*slots*/ slot_count, /*children*/ 0); } constexpr static layout_type InternalLayout() { @@ -591,8 +591,8 @@ class btree_node { /*slots*/ kNodeSlots, /*children*/ kNodeSlots + 1); } - constexpr static size_type LeafSize(const int slots = kNodeSlots) { - return LeafLayout(slots).AllocSize(); + constexpr static size_type LeafSize(const int slot_count = kNodeSlots) { + return LeafLayout(slot_count).AllocSize(); } constexpr static size_type InternalSize() { return InternalLayout().AllocSize(); diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 80fc2cba..8615de8b 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -792,7 +792,8 @@ class raw_hash_set { explicit raw_hash_set(size_t bucket_count, const hasher& hash = hasher(), const key_equal& eq = key_equal(), const allocator_type& alloc = allocator_type()) - : ctrl_(EmptyGroup()), settings_(0, hash, eq, alloc) { + : ctrl_(EmptyGroup()), + settings_(0, HashtablezInfoHandle(), hash, eq, alloc) { if (bucket_count) { capacity_ = NormalizeCapacity(bucket_count); initialize_slots(); @@ -903,7 +904,7 @@ class raw_hash_set { auto target = find_first_non_full(ctrl_, hash, capacity_); set_ctrl(target.offset, H2(hash)); emplace_at(target.offset, v); - infoz_.RecordInsert(hash, target.probe_length); + infoz().RecordInsert(hash, target.probe_length); } size_ = that.size(); growth_left() -= that.size(); @@ -917,28 +918,27 @@ class raw_hash_set { slots_(absl::exchange(that.slots_, nullptr)), size_(absl::exchange(that.size_, 0)), capacity_(absl::exchange(that.capacity_, 0)), - infoz_(absl::exchange(that.infoz_, HashtablezInfoHandle())), // Hash, equality and allocator are copied instead of moved because // `that` must be left valid. If Hash is std::function, moving it // would create a nullptr functor that cannot be called. - settings_(that.settings_) { - // growth_left was copied above, reset the one from `that`. - that.growth_left() = 0; - } + settings_(absl::exchange(that.growth_left(), 0), + absl::exchange(that.infoz(), HashtablezInfoHandle()), + that.hash_ref(), that.eq_ref(), that.alloc_ref()) {} raw_hash_set(raw_hash_set&& that, const allocator_type& a) : ctrl_(EmptyGroup()), slots_(nullptr), size_(0), capacity_(0), - settings_(0, that.hash_ref(), that.eq_ref(), a) { + settings_(0, HashtablezInfoHandle(), that.hash_ref(), that.eq_ref(), + a) { if (a == that.alloc_ref()) { std::swap(ctrl_, that.ctrl_); std::swap(slots_, that.slots_); std::swap(size_, that.size_); std::swap(capacity_, that.capacity_); std::swap(growth_left(), that.growth_left()); - std::swap(infoz_, that.infoz_); + std::swap(infoz(), that.infoz()); } else { reserve(that.size()); // Note: this will copy elements of dense_set and unordered_set instead of @@ -1009,7 +1009,7 @@ class raw_hash_set { reset_growth_left(); } assert(empty()); - infoz_.RecordStorageChanged(0, capacity_); + infoz().RecordStorageChanged(0, capacity_); } // This overload kicks in when the argument is an rvalue of insertable and @@ -1301,7 +1301,7 @@ class raw_hash_set { swap(growth_left(), that.growth_left()); swap(hash_ref(), that.hash_ref()); swap(eq_ref(), that.eq_ref()); - swap(infoz_, that.infoz_); + swap(infoz(), that.infoz()); SwapAlloc(alloc_ref(), that.alloc_ref(), typename AllocTraits::propagate_on_container_swap{}); } @@ -1310,7 +1310,7 @@ class raw_hash_set { if (n == 0 && capacity_ == 0) return; if (n == 0 && size_ == 0) { destroy_slots(); - infoz_.RecordStorageChanged(0, 0); + infoz().RecordStorageChanged(0, 0); return; } // bitor is a faster way of doing `max` here. We will round up to the next @@ -1528,7 +1528,7 @@ class raw_hash_set { set_ctrl(index, was_never_full ? kEmpty : kDeleted); growth_left() += was_never_full; - infoz_.RecordErase(); + infoz().RecordErase(); } void initialize_slots() { @@ -1545,7 +1545,7 @@ class raw_hash_set { // bound more carefully. if (std::is_same>::value && slots_ == nullptr) { - infoz_ = Sample(); + infoz() = Sample(); } auto layout = MakeLayout(capacity_); @@ -1555,7 +1555,7 @@ class raw_hash_set { slots_ = layout.template Pointer<1>(mem); reset_ctrl(); reset_growth_left(); - infoz_.RecordStorageChanged(size_, capacity_); + infoz().RecordStorageChanged(size_, capacity_); } void destroy_slots() { @@ -1603,7 +1603,7 @@ class raw_hash_set { Deallocate(&alloc_ref(), old_ctrl, layout.AllocSize()); } - infoz_.RecordRehash(total_probe_length); + infoz().RecordRehash(total_probe_length); } void drop_deletes_without_resize() ABSL_ATTRIBUTE_NOINLINE { @@ -1669,7 +1669,7 @@ class raw_hash_set { } } reset_growth_left(); - infoz_.RecordRehash(total_probe_length); + infoz().RecordRehash(total_probe_length); } void rehash_and_grow_if_necessary() { @@ -1743,7 +1743,7 @@ class raw_hash_set { ++size_; growth_left() -= IsEmpty(ctrl_[target.offset]); set_ctrl(target.offset, H2(hash)); - infoz_.RecordInsert(hash, target.probe_length); + infoz().RecordInsert(hash, target.probe_length); return target.offset; } @@ -1800,13 +1800,15 @@ class raw_hash_set { size_t& growth_left() { return settings_.template get<0>(); } - hasher& hash_ref() { return settings_.template get<1>(); } - const hasher& hash_ref() const { return settings_.template get<1>(); } - key_equal& eq_ref() { return settings_.template get<2>(); } - const key_equal& eq_ref() const { return settings_.template get<2>(); } - allocator_type& alloc_ref() { return settings_.template get<3>(); } + HashtablezInfoHandle& infoz() { return settings_.template get<1>(); } + + hasher& hash_ref() { return settings_.template get<2>(); } + const hasher& hash_ref() const { return settings_.template get<2>(); } + key_equal& eq_ref() { return settings_.template get<3>(); } + const key_equal& eq_ref() const { return settings_.template get<3>(); } + allocator_type& alloc_ref() { return settings_.template get<4>(); } const allocator_type& alloc_ref() const { - return settings_.template get<3>(); + return settings_.template get<4>(); } // TODO(alkis): Investigate removing some of these fields: @@ -1816,10 +1818,11 @@ class raw_hash_set { slot_type* slots_ = nullptr; // [capacity * slot_type] size_t size_ = 0; // number of full slots size_t capacity_ = 0; // total number of slots - HashtablezInfoHandle infoz_; - absl::container_internal::CompressedTuple - settings_{0, hasher{}, key_equal{}, allocator_type{}}; + settings_{0, HashtablezInfoHandle{}, hasher{}, key_equal{}, + allocator_type{}}; }; // Erases all elements that satisfy the predicate `pred` from the container `c`. diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 81c4b47c..7dac65a0 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -419,6 +419,13 @@ TEST(Table, EmptyFunctorOptimization) { size_t growth_left; void* infoz; }; + struct MockTableInfozDisabled { + void* ctrl; + void* slots; + size_t size; + size_t capacity; + size_t growth_left; + }; struct StatelessHash { size_t operator()(absl::string_view) const { return 0; } }; @@ -426,17 +433,27 @@ TEST(Table, EmptyFunctorOptimization) { size_t dummy; }; - EXPECT_EQ( - sizeof(MockTable), - sizeof( - raw_hash_set, std::allocator>)); - - EXPECT_EQ( - sizeof(MockTable) + sizeof(StatefulHash), - sizeof( - raw_hash_set, std::allocator>)); + if (std::is_empty::value) { + EXPECT_EQ(sizeof(MockTableInfozDisabled), + sizeof(raw_hash_set, + std::allocator>)); + + EXPECT_EQ(sizeof(MockTableInfozDisabled) + sizeof(StatefulHash), + sizeof(raw_hash_set, + std::allocator>)); + } else { + EXPECT_EQ(sizeof(MockTable), + sizeof(raw_hash_set, + std::allocator>)); + + EXPECT_EQ(sizeof(MockTable) + sizeof(StatefulHash), + sizeof(raw_hash_set, + std::allocator>)); + } } TEST(Table, Empty) { diff --git a/absl/debugging/internal/demangle.cc b/absl/debugging/internal/demangle.cc index 46cdb67b..5cd56320 100644 --- a/absl/debugging/internal/demangle.cc +++ b/absl/debugging/internal/demangle.cc @@ -386,24 +386,28 @@ static bool IsDigit(char c) { return c >= '0' && c <= '9'; } // by GCC 4.5.x and later versions (and our locally-modified version of GCC // 4.4.x) to indicate functions which have been cloned during optimization. // We treat any sequence (.+.+)+ as a function clone suffix. +// Additionally, '_' is allowed along with the alphanumeric sequence. static bool IsFunctionCloneSuffix(const char *str) { size_t i = 0; while (str[i] != '\0') { - // Consume a single .+.+ sequence. - if (str[i] != '.' || !IsAlpha(str[i + 1])) { - return false; + bool parsed = false; + // Consume a single [. | _]*[.]* sequence. + if (str[i] == '.' && (IsAlpha(str[i + 1]) || str[i + 1] == '_')) { + parsed = true; + i += 2; + while (IsAlpha(str[i]) || str[i] == '_') { + ++i; + } } - i += 2; - while (IsAlpha(str[i])) { - ++i; + if (str[i] == '.' && IsDigit(str[i + 1])) { + parsed = true; + i += 2; + while (IsDigit(str[i])) { + ++i; + } } - if (str[i] != '.' || !IsDigit(str[i + 1])) { + if (!parsed) return false; - } - i += 2; - while (IsDigit(str[i])) { - ++i; - } } return true; // Consumed everything in "str". } diff --git a/absl/debugging/internal/demangle_test.cc b/absl/debugging/internal/demangle_test.cc index 0bed7359..6b142902 100644 --- a/absl/debugging/internal/demangle_test.cc +++ b/absl/debugging/internal/demangle_test.cc @@ -70,12 +70,34 @@ TEST(Demangle, Clones) { EXPECT_STREQ("Foo()", tmp); EXPECT_TRUE(Demangle("_ZL3Foov.isra.2.constprop.18", tmp, sizeof(tmp))); EXPECT_STREQ("Foo()", tmp); - // Invalid (truncated), should not demangle. - EXPECT_FALSE(Demangle("_ZL3Foov.clo", tmp, sizeof(tmp))); + // Demangle suffixes produced by -funique-internal-linkage-names. + EXPECT_TRUE(Demangle("_ZL3Foov.__uniq.12345", tmp, sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + EXPECT_TRUE(Demangle("_ZL3Foov.__uniq.12345.isra.2.constprop.18", tmp, + sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + // Suffixes without the number should also demangle. + EXPECT_TRUE(Demangle("_ZL3Foov.clo", tmp, sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + // Suffixes with just the number should also demangle. + EXPECT_TRUE(Demangle("_ZL3Foov.123", tmp, sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + // (.clone. followed by non-number), should also demangle. + EXPECT_TRUE(Demangle("_ZL3Foov.clone.foo", tmp, sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + // (.clone. followed by multiple numbers), should also demangle. + EXPECT_TRUE(Demangle("_ZL3Foov.clone.123.456", tmp, sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + // (a long valid suffix), should demangle. + EXPECT_TRUE(Demangle("_ZL3Foov.part.9.165493.constprop.775.31805", tmp, + sizeof(tmp))); + EXPECT_STREQ("Foo()", tmp); + // Invalid (. without anything else), should not demangle. + EXPECT_FALSE(Demangle("_ZL3Foov.", tmp, sizeof(tmp))); + // Invalid (. with mix of alpha and digits), should not demangle. + EXPECT_FALSE(Demangle("_ZL3Foov.abc123", tmp, sizeof(tmp))); // Invalid (.clone. not followed by number), should not demangle. EXPECT_FALSE(Demangle("_ZL3Foov.clone.", tmp, sizeof(tmp))); - // Invalid (.clone. followed by non-number), should not demangle. - EXPECT_FALSE(Demangle("_ZL3Foov.clone.foo", tmp, sizeof(tmp))); // Invalid (.constprop. not followed by number), should not demangle. EXPECT_FALSE(Demangle("_ZL3Foov.isra.2.constprop.", tmp, sizeof(tmp))); } diff --git a/absl/debugging/leak_check.cc b/absl/debugging/leak_check.cc index ff904955..db9d5d09 100644 --- a/absl/debugging/leak_check.cc +++ b/absl/debugging/leak_check.cc @@ -38,6 +38,7 @@ ABSL_NAMESPACE_END namespace absl { ABSL_NAMESPACE_BEGIN bool HaveLeakSanitizer() { return true; } +bool FindAndReportLeaks() { return __lsan_do_recoverable_leak_check(); } void DoIgnoreLeak(const void* ptr) { __lsan_ignore_object(ptr); } void RegisterLivePointers(const void* ptr, size_t size) { __lsan_register_root_region(ptr, size); diff --git a/absl/debugging/leak_check.h b/absl/debugging/leak_check.h index b66a81c3..61c3216f 100644 --- a/absl/debugging/leak_check.h +++ b/absl/debugging/leak_check.h @@ -71,6 +71,19 @@ T* IgnoreLeak(T* ptr) { return ptr; } +// FindAndReportLeaks() +// +// If any leaks are detected, prints a leak report and returns true. This +// function may be called repeatedly, and does not affect end-of-process leak +// checking. +// +// Example: +// if (FindAndReportLeaks()) { +// ... diagnostic already printed. Exit with failure code. +// exit(1) +// } +bool FindAndReportLeaks(); + // LeakCheckDisabler // // This helper class indicates that any heap allocations done in the code block diff --git a/absl/status/internal/status_internal.h b/absl/status/internal/status_internal.h index 279f8f55..99a2d964 100644 --- a/absl/status/internal/status_internal.h +++ b/absl/status/internal/status_internal.h @@ -19,6 +19,17 @@ #include "absl/container/inlined_vector.h" #include "absl/strings/cord.h" +#ifndef SWIG +// Disabled for SWIG as it doesn't parse attributes correctly. +namespace absl { +ABSL_NAMESPACE_BEGIN +// Returned Status objects may not be ignored. Codesearch doesn't handle ifdefs +// as part of a class definitions (b/6995610), so we use a forward declaration. +class ABSL_MUST_USE_RESULT Status; +ABSL_NAMESPACE_END +} // namespace absl +#endif // !SWIG + namespace absl { ABSL_NAMESPACE_BEGIN diff --git a/absl/status/status.h b/absl/status/status.h index df9e330c..61486fee 100644 --- a/absl/status/status.h +++ b/absl/status/status.h @@ -291,6 +291,8 @@ enum class StatusToStringMode : int { kWithNoExtraData = 0, // ToString will contain the payloads. kWithPayload = 1 << 0, + // ToString will include all the extra data this Status has. + kWithEverything = ~kWithNoExtraData, }; // absl::StatusToStringMode is specified as a bitmask type, which means the @@ -410,7 +412,12 @@ inline StatusToStringMode& operator^=(StatusToStringMode& lhs, // return result; // } // -class ABSL_MUST_USE_RESULT Status final { +// For documentation see https://abseil.io/docs/cpp/guides/status. +// +// Returned Status objects may not be ignored. status_internal.h has a forward +// declaration of the form +// class ABSL_MUST_USE_RESULT Status; +class Status final { public: // Constructors diff --git a/absl/status/status_test.cc b/absl/status/status_test.cc index 7116ba67..0e1a43ce 100644 --- a/absl/status/status_test.cc +++ b/absl/status/status_test.cc @@ -292,6 +292,10 @@ TEST(Status, ToStringMode) { AllOf(HasSubstr("INTERNAL: fail"), HasSubstr("[foo='bar']"), HasSubstr("[bar='\\xff']"))); + EXPECT_THAT(s.ToString(absl::StatusToStringMode::kWithEverything), + AllOf(HasSubstr("INTERNAL: fail"), HasSubstr("[foo='bar']"), + HasSubstr("[bar='\\xff']"))); + EXPECT_THAT(s.ToString(~absl::StatusToStringMode::kWithPayload), AllOf(HasSubstr("INTERNAL: fail"), Not(HasSubstr("[foo='bar']")), Not(HasSubstr("[bar='\\xff']")))); diff --git a/absl/status/statusor.h b/absl/status/statusor.h index 469d486f..b7c55cc8 100644 --- a/absl/status/statusor.h +++ b/absl/status/statusor.h @@ -135,7 +135,7 @@ class ABSL_MUST_USE_RESULT StatusOr; // // NOTE: using `absl::StatusOr::value()` when no valid value is present will // throw an exception if exceptions are enabled or terminate the process when -// execeptions are not enabled. +// exceptions are not enabled. // // Example: // diff --git a/absl/strings/numbers.h b/absl/strings/numbers.h index ffc738fa..1780bb44 100644 --- a/absl/strings/numbers.h +++ b/absl/strings/numbers.h @@ -124,6 +124,7 @@ inline void PutTwoDigits(size_t i, char* buf) { } // safe_strto?() functions for implementing SimpleAtoi() + bool safe_strto32_base(absl::string_view text, int32_t* value, int base); bool safe_strto64_base(absl::string_view text, int64_t* value, int base); bool safe_strto128_base(absl::string_view text, absl::int128* value, diff --git a/ci/cmake_install_test.sh b/ci/cmake_install_test.sh index 5bf540c5..ffc6b516 100755 --- a/ci/cmake_install_test.sh +++ b/ci/cmake_install_test.sh @@ -20,18 +20,24 @@ if [[ -z ${ABSEIL_ROOT:-} ]]; then ABSEIL_ROOT="$(realpath $(dirname ${0})/..)" fi +if [[ -z ${LINK_TYPE:-} ]]; then + LINK_TYPE="STATIC DYNAMIC" +fi + source "${ABSEIL_ROOT}/ci/cmake_common.sh" source "${ABSEIL_ROOT}/ci/linux_docker_containers.sh" readonly DOCKER_CONTAINER=${LINUX_GCC_LATEST_CONTAINER} -time docker run \ - --mount type=bind,source="${ABSEIL_ROOT}",target=/abseil-cpp,readonly \ - --workdir=/abseil-cpp \ +for link_type in ${LINK_TYPE}; do + time docker run \ + --mount type=bind,source="${ABSEIL_ROOT}",target=/abseil-cpp-ro,readonly \ --tmpfs=/buildfs:exec \ + --tmpfs=/abseil-cpp:exec \ + --workdir=/abseil-cpp \ --cap-add=SYS_PTRACE \ + -e "LINK_TYPE=${link_type}" \ --rm \ - -e CFLAGS="-Werror" \ - -e CXXFLAGS="-Werror" \ ${DOCKER_CONTAINER} \ - /bin/bash CMake/install_test_project/test.sh $@ + /bin/bash -c "cp -r /abseil-cpp-ro/* . && CMake/install_test_project/test.sh" +done diff --git a/create_lts.py b/create_lts.py new file mode 100755 index 00000000..a98c76b4 --- /dev/null +++ b/create_lts.py @@ -0,0 +1,121 @@ +#!/usr/bin/env python +# +# 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. +"""A script to do source transformations to create a new LTS release. + + Usage: ./create_lts.py YYYYMMDD +""" + +import sys + + +def ReplaceStringsInFile(filename, replacement_dict): + """Performs textual replacements in a file. + + Rewrites filename with the keys in replacement_dict replaced with + their values. This function assumes the file can fit in memory. + + Args: + filename: the filename to perform the replacement on + replacement_dict: a dictionary of key strings to be replaced with their + values + + Raises: + Exception: A failure occured + """ + f = open(filename, 'r') + content = f.read() + f.close() + + for key, value in replacement_dict.items(): + original = content + content = content.replace(key, value) + if content == original: + raise Exception('Failed to find {} in {}'.format(key, filename)) + + f = open(filename, 'w') + f.write(content) + f.close() + + +def StripContentBetweenTags(filename, strip_begin_tag, strip_end_tag): + """Strip contents from a file. + + Rewrites filename with by removing all content between + strip_begin_tag and strip_end_tag, including the tags themselves. + + Args: + filename: the filename to perform the replacement on + strip_begin_tag: the start of the content to be removed + strip_end_tag: the end of the content to be removed + + Raises: + Exception: A failure occured + """ + f = open(filename, 'r') + content = f.read() + f.close() + + while True: + begin = content.find(strip_begin_tag) + if begin == -1: + break + end = content.find(strip_end_tag, begin + len(strip_begin_tag)) + if end == -1: + raise Exception('{}: imbalanced strip begin ({}) and ' + 'end ({}) tags'.format(filename, strip_begin_tag, + strip_end_tag)) + content = content.replace(content[begin:end + len(strip_end_tag)], '') + + f = open(filename, 'w') + f.write(content) + f.close() + + +def main(argv): + if len(argv) != 2: + print('Usage: {} YYYYMMDD'.format(sys.argv[0], file=sys.stderr)) + sys.exit(1) + + datestamp = sys.argv[1] + if len(datestamp) != 8 or not datestamp.isdigit(): + raise Exception( + 'datestamp={} is not in the YYYYMMDD format'.format(datestamp)) + + # Replacement directives go here. + ReplaceStringsInFile( + 'absl/base/options.h', { + '#define ABSL_OPTION_USE_INLINE_NAMESPACE 0': + '#define ABSL_OPTION_USE_INLINE_NAMESPACE 1', + '#define ABSL_OPTION_INLINE_NAMESPACE_NAME head': + '#define ABSL_OPTION_INLINE_NAMESPACE_NAME lts_{}'.format( + datestamp) + }) + ReplaceStringsInFile( + 'CMakeLists.txt', { + 'project(absl LANGUAGES CXX)': + 'project(absl LANGUAGES CXX VERSION {})'.format(datestamp) + }) + # Set the SOVERSION to YYYYMMDD.0.0 - The first 0 means we only have + # ABI compatible changes, and the second 0 means we can increment it + # to mark changes as ABI-compatible, for patch releases. + ReplaceStringsInFile('CMake/AbseilHelpers.cmake', + {'SOVERSION 0': 'SOVERSION "{}.0.0"'.format(datestamp)}) + StripContentBetweenTags('CMakeLists.txt', '# absl:lts-remove-begin', + '# absl:lts-remove-end') + + +if __name__ == '__main__': + main(sys.argv) -- cgit v1.2.3