summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2022-02-23 06:56:15 -0800
committerGravatar rogeeff <rogeeff@google.com>2022-02-23 10:24:01 -0500
commit0ad7994f10624cd1538b1287e56cae5ac9c0cb40 (patch)
tree2b8d698744e29cacfa524aee77930f69a27794e3 /absl
parent808bc202fc13e85a7948db0d7fb58f0f051200b1 (diff)
Export of internal Abseil changes
-- 91d76b3ac9edff91f206d9eee60423c39eeeaf93 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 430442277 -- 9f8a87bcc5cc5b0fd8b7f0318f37d152fd8bea06 by Evan Brown <ezb@google.com>: Small refactoring to work towards allowing for node_btree_* containers. - Change common_params::transfer to rely on slot_policy transfer instead of manually doing construct/destruct. Transfer is not construct/destruct for node containers. - Move maps' value_compare into btree.h from btree_map.h so it can be reused for node_btree_map.h. - Also add a test for maps' value_compare protected members. PiperOrigin-RevId: 430245542 -- 0126e0b6295342317d9c9f0a66e2d7009b858426 by Martijn Vels <mvels@google.com>: Add CordRepSubString::Create function with hard checks on IsFlat() | IsExternal() This hardens internal invariants, IsFlat() || IsExternal() is a cheap, single predicted branch, and removes boilerplate code from cord.cc PiperOrigin-RevId: 429676041 -- ed98a92af49d9e238d9f1d1b69fb4eddcd1ccbc7 by Abseil Team <absl-team@google.com>: tweaks to status.h documentation to reflect general-purpose communication PiperOrigin-RevId: 429584104 GitOrigin-RevId: 91d76b3ac9edff91f206d9eee60423c39eeeaf93 Change-Id: I54d6d116a564f86a842b983ca76559bf9b388f72
Diffstat (limited to 'absl')
-rw-r--r--absl/container/btree_map.h31
-rw-r--r--absl/container/btree_set.h21
-rw-r--r--absl/container/btree_test.cc16
-rw-r--r--absl/container/internal/btree.h36
-rw-r--r--absl/status/status.h10
-rw-r--r--absl/strings/cord.cc30
-rw-r--r--absl/strings/cord_test.cc21
-rw-r--r--absl/strings/internal/cord_internal.cc7
-rw-r--r--absl/strings/internal/cord_internal.h58
9 files changed, 129 insertions, 101 deletions
diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h
index ad484ce0..286817f1 100644
--- a/absl/container/btree_map.h
+++ b/absl/container/btree_map.h
@@ -59,7 +59,7 @@ ABSL_NAMESPACE_BEGIN
namespace container_internal {
template <typename Key, typename Data, typename Compare, typename Alloc,
- int TargetNodeSize, bool Multi>
+ int TargetNodeSize, bool IsMulti>
struct map_params;
} // namespace container_internal
@@ -85,7 +85,7 @@ class btree_map
: public container_internal::btree_map_container<
container_internal::btree<container_internal::map_params<
Key, Value, Compare, Alloc, /*TargetNodeSize=*/256,
- /*Multi=*/false>>> {
+ /*IsMulti=*/false>>> {
using Base = typename btree_map::btree_map_container;
public:
@@ -507,7 +507,7 @@ class btree_multimap
: public container_internal::btree_multimap_container<
container_internal::btree<container_internal::map_params<
Key, Value, Compare, Alloc, /*TargetNodeSize=*/256,
- /*Multi=*/true>>> {
+ /*IsMulti=*/true>>> {
using Base = typename btree_multimap::btree_multimap_container;
public:
@@ -817,9 +817,9 @@ namespace container_internal {
// A parameters structure for holding the type parameters for a btree_map.
// Compare and Alloc should be nothrow copy-constructible.
template <typename Key, typename Data, typename Compare, typename Alloc,
- int TargetNodeSize, bool Multi>
-struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
- map_slot_policy<Key, Data>> {
+ int TargetNodeSize, bool IsMulti>
+struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, IsMulti,
+ /*IsMap=*/true, map_slot_policy<Key, Data>> {
using super_type = typename map_params::common_params;
using mapped_type = Data;
// This type allows us to move keys when it is safe to do so. It is safe
@@ -829,25 +829,6 @@ struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
using value_type = typename super_type::value_type;
using init_type = typename super_type::init_type;
- using original_key_compare = typename super_type::original_key_compare;
- // Reference: https://en.cppreference.com/w/cpp/container/map/value_compare
- class value_compare {
- template <typename Params>
- friend class btree;
-
- protected:
- explicit value_compare(original_key_compare c) : comp(std::move(c)) {}
-
- original_key_compare comp; // NOLINT
-
- public:
- auto operator()(const value_type &lhs, const value_type &rhs) const
- -> decltype(comp(lhs.first, rhs.first)) {
- return comp(lhs.first, rhs.first);
- }
- };
- using is_map_container = std::true_type;
-
template <typename V>
static auto key(const V &value) -> decltype(value.first) {
return value.first;
diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h
index 78826830..7b6655ad 100644
--- a/absl/container/btree_set.h
+++ b/absl/container/btree_set.h
@@ -61,7 +61,7 @@ template <typename Key>
struct set_slot_policy;
template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
- bool Multi>
+ bool IsMulti>
struct set_params;
} // namespace container_internal
@@ -87,7 +87,7 @@ class btree_set
: public container_internal::btree_set_container<
container_internal::btree<container_internal::set_params<
Key, Compare, Alloc, /*TargetNodeSize=*/256,
- /*Multi=*/false>>> {
+ /*IsMulti=*/false>>> {
using Base = typename btree_set::btree_set_container;
public:
@@ -427,7 +427,7 @@ class btree_multiset
: public container_internal::btree_multiset_container<
container_internal::btree<container_internal::set_params<
Key, Compare, Alloc, /*TargetNodeSize=*/256,
- /*Multi=*/true>>> {
+ /*IsMulti=*/true>>> {
using Base = typename btree_multiset::btree_multiset_container;
public:
@@ -757,6 +757,12 @@ struct set_slot_policy {
}
template <typename Alloc>
+ static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) {
+ construct(alloc, new_slot, old_slot);
+ destroy(alloc, old_slot);
+ }
+
+ template <typename Alloc>
static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) {
using std::swap;
swap(*a, *b);
@@ -771,14 +777,11 @@ struct set_slot_policy {
// A parameters structure for holding the type parameters for a btree_set.
// Compare and Alloc should be nothrow copy-constructible.
template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
- bool Multi>
-struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
- set_slot_policy<Key>> {
+ bool IsMulti>
+struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, IsMulti,
+ /*IsMap=*/false, set_slot_policy<Key>> {
using value_type = Key;
using slot_type = typename set_params::common_params::slot_type;
- using value_compare =
- typename set_params::common_params::original_key_compare;
- using is_map_container = std::false_type;
template <typename V>
static const V &key(const V &value) {
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index e829e0ba..4d4c64b2 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1762,6 +1762,22 @@ TEST(Btree, ValueComp) {
EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)));
}
+// Test that we have the protected members from the std::map::value_compare API.
+// See https://en.cppreference.com/w/cpp/container/map/value_compare.
+TEST(Btree, MapValueCompProtected) {
+ struct key_compare {
+ bool operator()(int l, int r) const { return l < r; }
+ int id;
+ };
+ using value_compare = absl::btree_map<int, int, key_compare>::value_compare;
+ struct value_comp_child : public value_compare {
+ explicit value_comp_child(key_compare kc) : value_compare(kc) {}
+ int GetId() const { return comp.id; }
+ };
+ value_comp_child c(key_compare{10});
+ EXPECT_EQ(c.GetId(), 10);
+}
+
TEST(Btree, DefaultConstruction) {
absl::btree_set<int> s;
absl::btree_map<int, int> m;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 6c10b00f..a22c9bd7 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -335,8 +335,27 @@ constexpr bool compare_has_valid_result_type() {
std::is_convertible<compare_result_type, absl::weak_ordering>::value;
}
+template <typename original_key_compare, typename value_type>
+class map_value_compare {
+ template <typename Params>
+ friend class btree;
+
+ // Note: this `protected` is part of the API of std::map::value_compare. See
+ // https://en.cppreference.com/w/cpp/container/map/value_compare.
+ protected:
+ explicit map_value_compare(original_key_compare c) : comp(std::move(c)) {}
+
+ original_key_compare comp; // NOLINT
+
+ public:
+ auto operator()(const value_type &lhs, const value_type &rhs) const
+ -> decltype(comp(lhs.first, rhs.first)) {
+ return comp(lhs.first, rhs.first);
+ }
+};
+
template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
- bool Multi, typename SlotPolicy>
+ bool IsMulti, bool IsMap, typename SlotPolicy>
struct common_params {
using original_key_compare = Compare;
@@ -384,6 +403,12 @@ struct common_params {
using reference = value_type &;
using const_reference = const value_type &;
+ using value_compare =
+ absl::conditional_t<IsMap,
+ map_value_compare<original_key_compare, value_type>,
+ original_key_compare>;
+ using is_map_container = std::integral_constant<bool, IsMap>;
+
// 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
@@ -394,9 +419,9 @@ struct common_params {
// that we know has the same equivalence classes for all lookup types.
template <typename LookupKey>
constexpr static bool can_have_multiple_equivalent_keys() {
- return Multi || (IsTransparent<key_compare>::value &&
- !std::is_same<LookupKey, Key>::value &&
- !kIsKeyCompareStringAdapted);
+ return IsMulti || (IsTransparent<key_compare>::value &&
+ !std::is_same<LookupKey, Key>::value &&
+ !kIsKeyCompareStringAdapted);
}
enum {
@@ -435,8 +460,7 @@ struct common_params {
slot_policy::destroy(alloc, slot);
}
static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) {
- construct(alloc, new_slot, old_slot);
- destroy(alloc, old_slot);
+ slot_policy::transfer(alloc, new_slot, old_slot);
}
static void swap(Alloc *alloc, slot_type *a, slot_type *b) {
slot_policy::swap(alloc, a, b);
diff --git a/absl/status/status.h b/absl/status/status.h
index db4b340a..2d003ce6 100644
--- a/absl/status/status.h
+++ b/absl/status/status.h
@@ -24,11 +24,11 @@
// * A set of helper functions for creating status codes and checking their
// values
//
-// Within Google, `absl::Status` is the primary mechanism for gracefully
-// handling errors across API boundaries (and in particular across RPC
-// boundaries). Some of these errors may be recoverable, but others may not.
-// Most functions that can produce a recoverable error should be designed to
-// return an `absl::Status` (or `absl::StatusOr`).
+// Within Google, `absl::Status` is the primary mechanism for communicating
+// errors in C++, and is used to represent error state in both in-process
+// library calls as well as RPC calls. Some of these errors may be recoverable,
+// but others may not. Most functions that can produce a recoverable error
+// should be designed to return an `absl::Status` (or `absl::StatusOr`).
//
// Example:
//
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 6547c2da..b65dc58b 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -151,23 +151,6 @@ void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep) {
} // namespace cord_internal
-static CordRep* NewSubstring(CordRep* child, size_t offset, size_t length) {
- // Never create empty substring nodes
- if (length == 0) {
- CordRep::Unref(child);
- return nullptr;
- } else {
- CordRepSubstring* rep = new CordRepSubstring();
- assert(child->IsExternal() || child->IsFlat());
- assert((offset + length) <= child->length);
- rep->length = length;
- rep->tag = cord_internal::SUBSTRING;
- rep->start = offset;
- rep->child = child;
- return VerifyTree(rep);
- }
-}
-
// Creates a CordRep from the provided string. If the string is large enough,
// and not wasteful, we move the string into an external cord rep, preserving
// the already allocated string contents.
@@ -643,7 +626,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
start += node->substring()->start;
node = node->substring()->child;
}
- node = NewSubstring(CordRep::Ref(node), start, len);
+ node = CordRepSubstring::Create(CordRep::Ref(node), start, len);
}
while (!rhs_stack.empty()) {
node = Concat(node, CordRep::Ref(rhs_stack.back()));
@@ -678,7 +661,7 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
start = node->substring()->start;
node = node->substring()->child;
}
- node = NewSubstring(CordRep::Ref(node), start, len);
+ node = CordRepSubstring::Create(CordRep::Ref(node), start, len);
}
while (!lhs_stack.empty()) {
node = Concat(CordRep::Ref(lhs_stack.back()), node);
@@ -768,7 +751,7 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
pos += node->substring()->start;
node = node->substring()->child;
}
- results.push_back(NewSubstring(CordRep::Ref(node), pos, n));
+ results.push_back(CordRepSubstring::Create(CordRep::Ref(node), pos, n));
}
} while (!todo.empty());
assert(results.size() == 1);
@@ -1157,12 +1140,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
: payload->flat()->Data();
const size_t offset = current_chunk_.data() - data;
- CordRepSubstring* tree = new CordRepSubstring();
- tree->tag = cord_internal::SUBSTRING;
- tree->length = n;
- tree->start = offset;
- tree->child = CordRep::Ref(payload);
-
+ auto* tree = CordRepSubstring::Create(CordRep::Ref(payload), offset, n);
subcord.contents_.EmplaceTree(VerifyTree(tree), method);
bytes_remaining_ -= n;
current_chunk_.remove_prefix(n);
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc
index 9dcc4ce5..f69209de 100644
--- a/absl/strings/cord_test.cc
+++ b/absl/strings/cord_test.cc
@@ -56,6 +56,7 @@ using absl::cord_internal::CordRepCrc;
using absl::cord_internal::CordRepExternal;
using absl::cord_internal::CordRepFlat;
using absl::cord_internal::CordRepSubstring;
+using absl::cord_internal::CordzUpdateTracker;
using absl::cord_internal::kFlatOverhead;
using absl::cord_internal::kMaxFlatLength;
@@ -212,14 +213,9 @@ class CordTestPeer {
ABSL_RAW_CHECK(src.ExpectedChecksum() == absl::nullopt,
"Can not be hardened");
Cord cord;
- auto* rep = new cord_internal::CordRepSubstring;
- rep->tag = cord_internal::SUBSTRING;
- rep->child = cord_internal::CordRep::Ref(
- cord_internal::SkipCrcNode(src.contents_.tree()));
- rep->start = offset;
- rep->length = length;
- cord.contents_.EmplaceTree(rep,
- cord_internal::CordzUpdateTracker::kSubCord);
+ auto* tree = cord_internal::SkipCrcNode(src.contents_.tree());
+ auto* rep = CordRepSubstring::Create(CordRep::Ref(tree), offset, length);
+ cord.contents_.EmplaceTree(rep, CordzUpdateTracker::kSubCord);
return cord;
}
};
@@ -645,15 +641,6 @@ TEST_P(CordTest, TryFlatSubstrExternal) {
EXPECT_EQ(sub.TryFlat(), "ell");
}
-TEST_P(CordTest, TryFlatSubstrConcat) {
- absl::Cord c = absl::MakeFragmentedCord({"hello", " world"});
- absl::Cord sub = absl::CordTestPeer::MakeSubstring(c, 1, c.size() - 1);
- MaybeHarden(sub);
- EXPECT_EQ(sub.TryFlat(), absl::nullopt);
- c.RemovePrefix(1);
- EXPECT_EQ(c.TryFlat(), absl::nullopt);
-}
-
TEST_P(CordTest, TryFlatCommonlyAssumedInvariants) {
// The behavior tested below is not part of the API contract of Cord, but it's
// something we intend to be true in our current implementation. This test
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 06119350..b6b06cfa 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -17,11 +17,13 @@
#include <cassert>
#include <memory>
+#include "absl/base/internal/raw_logging.h"
#include "absl/container/inlined_vector.h"
#include "absl/strings/internal/cord_rep_btree.h"
#include "absl/strings/internal/cord_rep_crc.h"
#include "absl/strings/internal/cord_rep_flat.h"
#include "absl/strings/internal/cord_rep_ring.h"
+#include "absl/strings/str_cat.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -33,6 +35,11 @@ ABSL_CONST_INIT std::atomic<bool> shallow_subcords_enabled(
kCordShallowSubcordsDefault);
ABSL_CONST_INIT std::atomic<bool> cord_btree_exhaustive_validation(false);
+void LogFatalNodeType(CordRep* rep) {
+ ABSL_INTERNAL_LOG(FATAL, absl::StrCat("Unexpected node type: ",
+ static_cast<int>(rep->tag)));
+}
+
void CordRep::Destroy(CordRep* rep) {
assert(rep != nullptr);
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index 8db6aa6d..ece3db15 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -21,6 +21,7 @@
#include <cstdint>
#include <type_traits>
+#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/endian.h"
#include "absl/base/internal/invoke.h"
@@ -33,6 +34,19 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {
+// The overhead of a vtable is too much for Cord, so we roll our own subclasses
+// using only a single byte to differentiate classes from each other - the "tag"
+// byte. Define the subclasses first so we can provide downcasting helper
+// functions in the base class.
+struct CordRep;
+struct CordRepConcat;
+struct CordRepExternal;
+struct CordRepFlat;
+struct CordRepSubstring;
+struct CordRepCrc;
+class CordRepRing;
+class CordRepBtree;
+
class CordzInfo;
// Default feature enable states for cord ring buffers
@@ -74,6 +88,9 @@ enum Constants {
kMaxBytesToCopy = 511
};
+// Emits a fatal error "Unexpected node type: xyz" and aborts the program.
+ABSL_ATTRIBUTE_NORETURN void LogFatalNodeType(CordRep* rep);
+
// Compact class for tracking the reference count and state flags for CordRep
// instances. Data is stored in an atomic int32_t for compactness and speed.
class RefcountAndFlags {
@@ -156,19 +173,6 @@ class RefcountAndFlags {
std::atomic<int32_t> count_;
};
-// The overhead of a vtable is too much for Cord, so we roll our own subclasses
-// using only a single byte to differentiate classes from each other - the "tag"
-// byte. Define the subclasses first so we can provide downcasting helper
-// functions in the base class.
-
-struct CordRepConcat;
-struct CordRepExternal;
-struct CordRepFlat;
-struct CordRepSubstring;
-struct CordRepCrc;
-class CordRepRing;
-class CordRepBtree;
-
// Various representations that we allow
enum CordRepKind {
UNUSED_0 = 0,
@@ -276,6 +280,12 @@ struct CordRep {
struct CordRepSubstring : public CordRep {
size_t start; // Starting offset of substring in child
CordRep* child;
+
+ // Creates a substring on `child`, adopting a reference on `child`.
+ // Requires `child` to be either a flat or external node, and `pos` and `n` to
+ // form a non-empty partial sub range of `'child`, i.e.:
+ // `n > 0 && n < length && n + pos <= length`
+ static inline CordRepSubstring* Create(CordRep* child, size_t pos, size_t n);
};
// Type for function pointer that will invoke the releaser function and also
@@ -339,6 +349,28 @@ struct CordRepExternalImpl
}
};
+inline CordRepSubstring* CordRepSubstring::Create(CordRep* child, size_t pos,
+ size_t n) {
+ assert(child != nullptr);
+ assert(n > 0);
+ assert(n < child->length);
+ assert(pos < child->length);
+ assert(n <= child->length - pos);
+
+ // TODO(b/217376272): Harden internal logic.
+ // Move to strategical places inside the Cord logic and make this an assert.
+ if (ABSL_PREDICT_FALSE(!(child->IsExternal() || child->IsFlat()))) {
+ LogFatalNodeType(child);
+ }
+
+ CordRepSubstring* rep = new CordRepSubstring();
+ rep->length = n;
+ rep->tag = SUBSTRING;
+ rep->start = pos;
+ rep->child = child;
+ return rep;
+}
+
inline void CordRepExternal::Delete(CordRep* rep) {
assert(rep != nullptr && rep->IsExternal());
auto* rep_external = static_cast<CordRepExternal*>(rep);