summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-03-03 11:22:10 -0800
committerGravatar Andy Soffer <asoffer@google.com>2020-03-03 17:32:55 -0500
commitb19ba96766db08b1f32605cb4424a0e7ea0c7584 (patch)
treec4ba295b067b000b9d84410ec81e0095715641a5
parent06f0e767d13d4d68071c4fc51e25724e0fc8bc74 (diff)
Export of internal Abseil changes
-- a3e58c1870a9626039f4d178d2d599319bd9f8a8 by Matt Kulukundis <kfm@google.com>: Allow MakeCordFromExternal to take a zero arg releaser. PiperOrigin-RevId: 298650274 -- 01897c4a9bb99f3dc329a794019498ad345ddebd by Samuel Benzaquen <sbenza@google.com>: 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 <dmauro@google.com>: Import GitHub #596: Unbreak stacktrace code for UWP apps PiperOrigin-RevId: 298600834 -- cd5cf6f8c87b35b85a9584e94da2a99057345b73 by Gennadiy Rozental <rogeeff@google.com>: 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 <matthewbr@google.com>: Ensure a deep copy and proper equality on absl::Status::ErasePayload PiperOrigin-RevId: 298482742 -- a5c9ccddf4b04f444e3f7e27dbc14faf1fcb5373 by Gennadiy Rozental <rogeeff@google.com>: 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 <absl-team@google.com>: 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 <absl-team@google.com>: 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 <absl-team@google.com>: Internal change PiperOrigin-RevId: 298219363 GitOrigin-RevId: a3e58c1870a9626039f4d178d2d599319bd9f8a8 Change-Id: I28dffc684b6fd0292b94807b88ec6664d5d0e183
Diffstat
-rw-r--r--absl/base/log_severity_test.cc2
-rw-r--r--absl/container/btree_benchmark.cc24
-rw-r--r--absl/container/btree_map.h4
-rw-r--r--absl/container/btree_set.h4
-rw-r--r--absl/container/btree_test.cc50
-rw-r--r--absl/container/internal/btree.h214
-rw-r--r--absl/container/internal/btree_container.h42
-rw-r--r--absl/debugging/internal/stacktrace_win32-inl.inc12
-rw-r--r--absl/flags/BUILD.bazel4
-rw-r--r--absl/flags/CMakeLists.txt3
-rw-r--r--absl/flags/flag.h1
-rw-r--r--absl/flags/flag_benchmark.cc8
-rw-r--r--absl/flags/flag_test.cc143
-rw-r--r--absl/flags/internal/commandlineflag.cc30
-rw-r--r--absl/flags/internal/commandlineflag.h6
-rw-r--r--absl/flags/internal/flag.cc107
-rw-r--r--absl/flags/internal/flag.h208
-rw-r--r--absl/hash/internal/hash.h15
-rw-r--r--absl/random/internal/BUILD.bazel1
-rw-r--r--absl/status/status.cc8
-rw-r--r--absl/status/status_test.cc57
-rw-r--r--absl/strings/cord.cc242
-rw-r--r--absl/strings/cord.h100
-rw-r--r--absl/strings/cord_test.cc56
24 files changed, 841 insertions, 500 deletions
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<absl::LogSeverity>::value,
+ absl::flags_internal::FlagUseOneWordStorage<absl::LogSeverity>::value,
"Flags of type absl::LogSeverity ought to be lock-free.");
using ParseFlagFromOutOfRangeIntegerTest = TestWithParam<int64_t>;
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<BigType<Size, Size>>(x);
}
- BigTypePtr(const BigTypePtr& x) {
- ptr = absl::make_unique<BigType<Size, Size>>(*x.ptr);
+ BigTypePtr(const BigTypePtr& other) {
+ ptr = absl::make_unique<BigType<Size, Size>>(*other.ptr);
}
- BigTypePtr(BigTypePtr&& x) noexcept = default;
- BigTypePtr& operator=(const BigTypePtr& x) {
- ptr = absl::make_unique<BigType<Size, Size>>(*x.ptr);
+ BigTypePtr(BigTypePtr&& other) noexcept = default;
+ BigTypePtr& operator=(const BigTypePtr& other) {
+ ptr = absl::make_unique<BigType<Size, Size>>(*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 <typename K> node_type extract(const K& x):
+ // template <typename K> 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 <typename K> node_type extract(const K& x):
+ // template <typename K> 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 <typename K> node_type extract(const K& x):
+ // template <typename K> 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 <typename K> node_type extract(const K& x):
+ // template <typename K> 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 <typename InputIterator>
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<typename TreeType::key_type,
typename TreeType::value_type>::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<TreeType, CheckerType> {
public:
unique_checker() : super_type() {}
- unique_checker(const unique_checker &x) : super_type(x) {}
+ unique_checker(const unique_checker &other) : super_type(other) {}
template <class InputIterator>
unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
unique_checker &operator=(const unique_checker &) = default;
// Insertion routines.
- std::pair<iterator, bool> insert(const value_type &x) {
+ std::pair<iterator, bool> insert(const value_type &v) {
int size = this->tree_.size();
std::pair<typename CheckerType::iterator, bool> checker_res =
- this->checker_.insert(x);
- std::pair<iterator, bool> tree_res = this->tree_.insert(x);
+ this->checker_.insert(v);
+ std::pair<iterator, bool> 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<typename CheckerType::iterator, bool> 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<TreeType, CheckerType> {
public:
multi_checker() : super_type() {}
- multi_checker(const multi_checker &x) : super_type(x) {}
+ multi_checker(const multi_checker &other) : super_type(other) {}
template <class InputIterator>
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_params<Key, Compare, Alloc, TargetNodeSize, Multi,
};
using is_map_container = std::true_type;
- static const Key &key(const value_type &x) { return x.first; }
- static const Key &key(const init_type &x) { return x.first; }
- static const Key &key(const slot_type *x) { return slot_policy::key(x); }
+ static const Key &key(const value_type &value) { return value.first; }
+ static const Key &key(const init_type &init) { return init.first; }
+ static const Key &key(const slot_type *s) { return slot_policy::key(s); }
static mapped_type &value(value_type *value) { return value->second; }
};
@@ -315,8 +315,8 @@ struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
using value_compare = typename set_params::common_params::key_compare;
using is_map_container = std::false_type;
- static const Key &key(const value_type &x) { return x; }
- static const Key &key(const slot_type *x) { return *x; }
+ static const Key &key(const value_type &value) { return value; }
+ static const Key &key(const slot_type *slot) { return *slot; }
};
// An adapter class that converts a lower-bound compare into an upper-bound
@@ -326,8 +326,8 @@ struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
template <typename Compare>
struct upper_bound_adapter {
explicit upper_bound_adapter(const Compare &c) : comp(c) {}
- template <typename K, typename LK>
- bool operator()(const K &a, const LK &b) const {
+ template <typename K1, typename K2>
+ 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<btree_iterator<N, R, P>, iterator>::value &&
std::is_same<btree_iterator, const_iterator>::value,
int> = 0>
- btree_iterator(const btree_iterator<N, R, P> &x) // NOLINT
- : node(x.node), position(x.position) {}
+ btree_iterator(const btree_iterator<N, R, P> &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<btree_iterator<N, R, P>, const_iterator>::value &&
std::is_same<btree_iterator, iterator>::value,
int> = 0>
- explicit btree_iterator(const btree_iterator<N, R, P> &x)
- : node(const_cast<node_type *>(x.node)), position(x.position) {}
+ explicit btree_iterator(const btree_iterator<N, R, P> &other)
+ : node(const_cast<node_type *>(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 <typename Btree>
- 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 <typename K, typename LK>
- bool compare_keys(const K &x, const LK &y) const {
- return compare_internal::compare_result_as_less_than(key_comp()(x, y));
+ template <typename K1, typename K2>
+ 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<P>::merge(btree_node *src, allocator_type *alloc) {
}
template <typename P>
-void btree_node<P>::swap(btree_node *x, allocator_type *alloc) {
+void btree_node<P>::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<P>::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<N, R, P>::decrement_slow() {
// btree methods
template <typename P>
template <typename Btree>
-void btree<P>::copy_or_move_values_in_order(Btree *x) {
+void btree<P>::copy_or_move_values_in_order(Btree *other) {
static_assert(std::is_same<btree, Btree>::value ||
std::is_same<const btree, Btree>::value,
"Btree type must be same or const.");
@@ -1822,11 +1822,11 @@ void btree<P>::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<P>::btree(const key_compare &comp, const allocator_type &alloc)
: root_(comp, alloc, EmptyNode()), rightmost_(EmptyNode()), size_(0) {}
template <typename P>
-btree<P>::btree(const btree &x) : btree(x.key_comp(), x.allocator()) {
- copy_or_move_values_in_order(&x);
+btree<P>::btree(const btree &other)
+ : btree(other.key_comp(), other.allocator()) {
+ copy_or_move_values_in_order(&other);
}
template <typename P>
@@ -1977,46 +1978,47 @@ void btree<P>::insert_iterator_multi(InputIterator b, InputIterator e) {
}
template <typename P>
-auto btree<P>::operator=(const btree &x) -> btree & {
- if (this != &x) {
+auto btree<P>::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 <typename P>
-auto btree<P>::operator=(btree &&x) noexcept -> btree & {
- if (this != &x) {
+auto btree<P>::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<P>::clear() {
}
template <typename P>
-void btree<P>::swap(btree &x) {
+void btree<P>::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 <typename P>
@@ -2417,8 +2419,7 @@ void btree<P>::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<P>::internal_emplace(iterator iter, Args &&... args)
new_leaf_root_node((std::min<int>)(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<Tree>::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<Tree> {
}
// Insertion routines.
- std::pair<iterator, bool> insert(const value_type &x) {
- return this->tree_.insert_unique(params_type::key(x), x);
+ std::pair<iterator, bool> insert(const value_type &v) {
+ return this->tree_.insert_unique(params_type::key(v), v);
}
- std::pair<iterator, bool> insert(value_type &&x) {
- return this->tree_.insert_unique(params_type::key(x), std::move(x));
+ std::pair<iterator, bool> insert(value_type &&v) {
+ return this->tree_.insert_unique(params_type::key(v), std::move(v));
}
template <typename... Args>
std::pair<iterator, bool> emplace(Args &&... args) {
init_type v(std::forward<Args>(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 <typename... Args>
@@ -562,15 +562,15 @@ class btree_multiset_container : public btree_container<Tree> {
}
// 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 <typename InputIterator>
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 <bool IS_STACK_FRAMES, bool IS_WITH_CONTEXT>
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<U>();
}
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 <typename T>
-bool TestConstructionFor() {
- constexpr flags::FlagHelpArg help_arg{flags::FlagHelpMsg("literal help"),
- flags::FlagHelpKind::kLiteral};
- constexpr flags::Flag<T> f1("f1", "file", help_arg, &TestMakeDflt<T>);
- EXPECT_EQ(f1.Name(), "f1");
- EXPECT_EQ(f1.Help(), "literal help");
- EXPECT_EQ(f1.Filename(), "file");
-
- ABSL_CONST_INIT static flags::Flag<T> f2(
- "f2", "file",
- {flags::FlagHelpMsg(&TestHelpMsg), flags::FlagHelpKind::kGenFunc},
- &TestMakeDflt<T>);
- flags::FlagRegistrar<T, false>(&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<int>(),
+ flags::FlagValueStorageKind::kOneWordAtomic);
+ EXPECT_EQ(flags::FlagValue::Kind<bool>(),
+ flags::FlagValueStorageKind::kOneWordAtomic);
+ EXPECT_EQ(flags::FlagValue::Kind<double>(),
+ flags::FlagValueStorageKind::kOneWordAtomic);
+ EXPECT_EQ(flags::FlagValue::Kind<int64_t>(),
+ flags::FlagValueStorageKind::kOneWordAtomic);
+
+#if defined(ABSL_FLAGS_INTERNAL_ATOMIC_DOUBLE_WORD)
+ EXPECT_EQ(flags::FlagValue::Kind<S1>(),
+ flags::FlagValueStorageKind::kTwoWordsAtomic);
+ EXPECT_EQ(flags::FlagValue::Kind<S2>(),
+ flags::FlagValueStorageKind::kTwoWordsAtomic);
+#else
+ EXPECT_EQ(flags::FlagValue::Kind<S1>(),
+ flags::FlagValueStorageKind::kHeapAllocated);
+ EXPECT_EQ(flags::FlagValue::Kind<S2>(),
+ flags::FlagValueStorageKind::kHeapAllocated);
+#endif
+
+ EXPECT_EQ(flags::FlagValue::Kind<std::string>(),
+ flags::FlagValueStorageKind::kHeapAllocated);
+ EXPECT_EQ(flags::FlagValue::Kind<std::vector<std::string>>(),
+ 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<T> f1##T("f1", "file", help_arg, &TestMakeDflt<T>); \
+ ABSL_CONST_INIT flags::Flag<T> f2##T( \
+ "f2", "file", \
+ {flags::FlagHelpMsg(&TestHelpMsg), flags::FlagHelpKind::kGenFunc}, \
+ &TestMakeDflt<T>)
+
+#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 <typename T>
+bool TestConstructionFor(const flags::Flag<T>& f1, flags::Flag<T>* f2) {
+ EXPECT_EQ(f1.Name(), "f1");
+ EXPECT_EQ(f1.Help(), "literal help");
+ EXPECT_EQ(f1.Filename(), "file");
+
+ flags::FlagRegistrar<T, false>(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<bool>();
- TestConstructionFor<int16_t>();
- TestConstructionFor<uint16_t>();
- TestConstructionFor<int32_t>();
- TestConstructionFor<uint32_t>();
- TestConstructionFor<int64_t>();
- TestConstructionFor<uint64_t>();
- TestConstructionFor<double>();
- TestConstructionFor<float>();
- TestConstructionFor<std::string>();
-
- TestConstructionFor<UDT>();
+ 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<void>(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<void>(absl::GetFlag(FLAGS_mistyped_int_flag)),
"Flag 'mistyped_int_flag' is defined as one type and declared "
"as another");
-
EXPECT_DEATH(static_cast<void>(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<std::string>{}),
"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<absl::Mutex*>(&data_guard_));
-
- value_.dynamic = MakeInitValue().release();
- StoreAtomic();
+ // At this point the default_value_ always points to gen_func.
+ std::unique_ptr<void, DynValueDeleter> 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<FlagImpl*>(this)->init_control_, &FlagImpl::Init,
const_cast<FlagImpl*>(this));
- // data_guard_ is initialized.
+ // data_guard_ is initialized inside Init.
return reinterpret_cast<absl::Mutex*>(&data_guard_);
}
@@ -129,8 +143,24 @@ std::unique_ptr<void, DynValueDeleter> 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<void, DynValueDeleter> 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 <typename T>
-struct IsAtomicFlagTypeTrait {
- static constexpr bool value =
- (sizeof(T) <= kMaxLockFreeAtomicSize &&
- type_traits_internal::is_trivially_copyable<T>::value);
-};
+using FlagUseOneWordStorage = std::integral_constant<
+ bool, absl::type_traits_internal::is_trivially_copyable<T>::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 <typename T, typename S = void>
-struct BestAtomicType {
- using type = int64_t;
- static constexpr int64_t AtomicInit() { return SmallAtomicInit(); }
+template <typename T>
+using FlagUseTwoWordsStorage = std::integral_constant<
+ bool, absl::type_traits_internal::is_trivially_copyable<T>::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 <typename T>
-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<bool, sizeof(T) != sizeof(T)>;
+#endif
+
+template <typename T>
+using FlagUseHeapStorage =
+ std::integral_constant<bool, !FlagUseOneWordStorage<T>::value &&
+ !FlagUseTwoWordsStorage<T>::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<int64_t> small_atomic;
- template <typename T,
- typename K = typename std::enable_if<
- (sizeof(T) <= kMinLockFreeAtomicSize), void>::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<FlagsInternalTwoWordsType> big_atomic;
- template <typename T, typename K = typename std::enable_if<
- (kMinLockFreeAtomicSize < sizeof(T) &&
- sizeof(T) <= kMaxLockFreeAtomicSize),
- void>::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 <typename T>
+ static constexpr FlagValueStorageKind Kind() {
+ return FlagUseHeapStorage<T>::value
+ ? FlagValueStorageKind::kHeapAllocated
+ : FlagUseOneWordStorage<T>::value
+ ? FlagValueStorageKind::kOneWordAtomic
+ : FlagUseTwoWordsStorage<T>::value
+ ? FlagValueStorageKind::kTwoWordsAtomic
+ : FlagValueStorageKind::kHeapAllocated;
+ }
+
+ void* dynamic;
+ std::atomic<int64_t> one_word_atomic;
+ std::atomic<flags_internal::AlignedTwoWords> 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<uint8_t>(help.kind)),
+ value_storage_kind_(static_cast<uint8_t>(value_kind)),
def_kind_(static_cast<uint8_t>(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 <typename T, typename std::enable_if<
- !IsAtomicFlagTypeTrait<T>::value, int>::type = 0>
+ template <typename T, typename std::enable_if<FlagUseHeapStorage<T>::value,
+ int>::type = 0>
void Get(T* dst) const {
- AssertValidType(&flags_internal::FlagStaticTypeIdGen<T>);
Read(dst);
}
- // Overload for `GetFlag()` for types that support lock-free reads.
- template <typename T, typename std::enable_if<IsAtomicFlagTypeTrait<T>::value,
+ template <typename T, typename std::enable_if<FlagUseOneWordStorage<T>::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<T>);
-#endif
- using U = flags_internal::BestAtomicType<T>;
- typename U::type r = value_.atomics.template load<T>();
- if (r != U::AtomicInit()) {
- std::memcpy(static_cast<void*>(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<const void*>(&one_word_val), sizeof(T));
}
- template <typename T>
- void Set(const T& src) {
- AssertValidType(&flags_internal::FlagStaticTypeIdGen<T>);
- Write(&src);
+ template <typename T, typename std::enable_if<
+ FlagUseTwoWordsStorage<T>::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<int> 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<FlagHelpKind>(help_source_kind_);
}
+ FlagValueStorageKind ValueStorageKind() const {
+ return static_cast<FlagValueStorageKind>(value_storage_kind_);
+ }
FlagDefaultKind DefaultKind() const
ABSL_EXCLUSIVE_LOCKS_REQUIRED(*DataGuard()) {
return static_cast<FlagDefaultKind>(def_kind_);
}
- // Used in read/write operations to validate source/target has correct type.
- // For example if flag is declared as absl::Flag<int> 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<T>, help, default_value_gen) {}
+ : impl_(name, filename, &FlagOps<T>, help, FlagValue::Kind<T>(),
+ 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<T>);
+#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<T>);
+ 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 <typename T>
-inline void FlagState<T>::Restore() const {
+void FlagState<T>::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<StatusCode>(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<const CordRepExternal*>(this);
}
+using CordTreeConstPath = CordTreePath<const CordRep*, MaxCordDepth()>;
+
+// 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<CordRep*, 2 * MaxCordDepth()>;
+
} // 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<CordRep*, kInlinedVectorSize> 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<CordRep*, kInlinedVectorSize> 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<CordRep*, kInlinedVectorSize> 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<CordRep*, kInlinedVectorSize> results;
- absl::InlinedVector<SubRange, kInlinedVectorSize> 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<SubRange, 2 * cord_internal::MaxCordDepth()> 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<CordRep*> 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<CordRep*, kInlinedVectorSize> trees_;
+ std::array<cord_internal::CordRep*, cord_internal::MaxCordDepth()> 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<CordRep*, kInlinedVectorSize> stack;
- absl::InlinedVector<int, kInlinedVectorSize> indents;
+ cord_internal::CordTreeConstPath stack;
+ cord_internal::CordTreePath<int, cord_internal::MaxCordDepth()> indents;
for (;;) {
*os << std::setw(3) << rep->refcount.Get();
*os << " " << std::setw(7) << rep->length;
*os << " [";
- if (include_data) *os << static_cast<void*>(rep);
+ if (include_data) *os << static_cast<const void*>(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<CordRep*, 2> 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<const CordRep*, kInlinedVectorSize> 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 <iostream>
#include <iterator>
#include <string>
+#include <type_traits>
#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 <typename H>
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 <typename CordRepPtr, size_t N>
+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<CordRep*, MaxCordDepth()>;
+} // 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<absl::cord_internal::CordRep*, 4>
- 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 <typename Releaser, typename = ::absl::base_internal::InvokeT<
+ Releaser, absl::string_view>>
+void InvokeReleaser(Rank0, Releaser&& releaser, absl::string_view data) {
+ ::absl::base_internal::Invoke(std::forward<Releaser>(releaser), data);
+}
+
+template <typename Releaser,
+ typename = ::absl::base_internal::InvokeT<Releaser>>
+void InvokeReleaser(Rank1, Releaser&& releaser, absl::string_view) {
+ ::absl::base_internal::Invoke(std::forward<Releaser>(releaser));
+}
+
// Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer
// to it, or `nullptr` if `data` was empty.
template <typename Releaser>
@@ -684,14 +766,14 @@ CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) {
using ReleaserType = absl::decay_t<Releaser>;
if (data.empty()) {
// Never create empty external nodes.
- ::absl::base_internal::Invoke(
- ReleaserType(std::forward<Releaser>(releaser)), data);
+ InvokeReleaser(Rank0{}, ReleaserType(std::forward<Releaser>(releaser)),
+ data);
return nullptr;
}
auto releaser_invoker = [](void* type_erased_releaser, absl::string_view d) {
auto* my_releaser = static_cast<ReleaserType*>(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<absl::Cord::CharIterator>::value,
"");
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-04 03:01:56 +0000