diff options
Diffstat (limited to 'absl')
| -rw-r--r-- | absl/base/log_severity_test.cc | 2 | ||||
| -rw-r--r-- | absl/container/btree_benchmark.cc | 24 | ||||
| -rw-r--r-- | absl/container/btree_map.h | 4 | ||||
| -rw-r--r-- | absl/container/btree_set.h | 4 | ||||
| -rw-r--r-- | absl/container/btree_test.cc | 50 | ||||
| -rw-r--r-- | absl/container/internal/btree.h | 214 | ||||
| -rw-r--r-- | absl/container/internal/btree_container.h | 42 | ||||
| -rw-r--r-- | absl/debugging/internal/stacktrace_win32-inl.inc | 12 | ||||
| -rw-r--r-- | absl/flags/BUILD.bazel | 4 | ||||
| -rw-r--r-- | absl/flags/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | absl/flags/flag.h | 1 | ||||
| -rw-r--r-- | absl/flags/flag_benchmark.cc | 8 | ||||
| -rw-r--r-- | absl/flags/flag_test.cc | 143 | ||||
| -rw-r--r-- | absl/flags/internal/commandlineflag.cc | 30 | ||||
| -rw-r--r-- | absl/flags/internal/commandlineflag.h | 6 | ||||
| -rw-r--r-- | absl/flags/internal/flag.cc | 107 | ||||
| -rw-r--r-- | absl/flags/internal/flag.h | 208 | ||||
| -rw-r--r-- | absl/hash/internal/hash.h | 15 | ||||
| -rw-r--r-- | absl/random/internal/BUILD.bazel | 1 | ||||
| -rw-r--r-- | absl/status/status.cc | 8 | ||||
| -rw-r--r-- | absl/status/status_test.cc | 57 | ||||
| -rw-r--r-- | absl/strings/cord.cc | 242 | ||||
| -rw-r--r-- | absl/strings/cord.h | 100 | ||||
| -rw-r--r-- | absl/strings/cord_test.cc | 56 |
24 files changed, 841 insertions, 500 deletions
diff --git a/absl/base/log_severity_test.cc b/absl/base/log_severity_test.cc index 2302aa12086a..2c6872b00a64 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 4af92f9fd888..420cfa0d238c 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 d23f4ee5e648..bb450eadde7c 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 127fb940d40e..d3e78866a7ed 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 9edf38f9d0ac..ce12e8194ef4 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 fd5c0e7aba9c..2a5c7314ccae 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 f2e4c3a5358b..734c90ef3d9c 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 af4578a506b0..1c666c8b561f 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 cdb4e7e8fe78..9166f74c1b6e 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 1d25f0ded8b1..01cf09b1b52a 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 cff02c1fcb61..bb917654d597 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 87f731704c87..ff95bb5d7bfc 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 4984d28403b2..1e01b49cc4f2 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 000000000000..90765a3eb6f3 --- /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 6363c6615b12..e91ddde633df 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 5a921e28d74e..a944e16e5083 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 35a148cf6602..307b737752c9 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 ae7a60cd55ad..1cc2c5e5ae48 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 d7ad4efec989..1c9dabb5add1 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 bbc1895eb64d..df3b740f7729 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 7cc65e45cb84..ca9488ad228c 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 5cc68539941d..9b32b3cc46b6 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 40566cbaa011..68a7e52feb7a 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 434f3a247e08..68515cbf15b9 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, ""); |