summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2023-05-04 08:59:39 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2023-05-04 09:00:29 -0700
commit25852951133d0a0fae309c9ebc85c751076c609c (patch)
treed3645ba386b0107ee178acc1a4bde44eb8541b0f
parent20c087a795638e904792c471d8de158cc97c208a (diff)
Add lifetimebound attribute to more Abseil container methods and remove them from internal ones.
PiperOrigin-RevId: 529423722 Change-Id: Ib1cc427299100956c0f2ae6cb5214467ef5a3790
-rw-r--r--absl/container/internal/btree.h68
-rw-r--r--absl/container/internal/btree_container.h100
2 files changed, 92 insertions, 76 deletions
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index e927c44a..18409a09 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -1444,54 +1444,43 @@ class btree {
btree &operator=(const btree &other);
btree &operator=(btree &&other) noexcept;
- iterator begin() ABSL_ATTRIBUTE_LIFETIME_BOUND {
- return iterator(leftmost());
- }
- const_iterator begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
- return const_iterator(leftmost());
- }
- iterator end() ABSL_ATTRIBUTE_LIFETIME_BOUND {
- return iterator(rightmost(), rightmost()->finish());
- }
- const_iterator end() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ iterator begin() { return iterator(leftmost()); }
+ const_iterator begin() const { return const_iterator(leftmost()); }
+ iterator end() { return iterator(rightmost(), rightmost()->finish()); }
+ const_iterator end() const {
return const_iterator(rightmost(), rightmost()->finish());
}
- reverse_iterator rbegin() ABSL_ATTRIBUTE_LIFETIME_BOUND {
- return reverse_iterator(end());
- }
- const_reverse_iterator rbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ reverse_iterator rbegin() { return reverse_iterator(end()); }
+ const_reverse_iterator rbegin() const {
return const_reverse_iterator(end());
}
- reverse_iterator rend() ABSL_ATTRIBUTE_LIFETIME_BOUND {
- return reverse_iterator(begin());
- }
- const_reverse_iterator rend() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ reverse_iterator rend() { return reverse_iterator(begin()); }
+ const_reverse_iterator rend() const {
return const_reverse_iterator(begin());
}
// Finds the first element whose key is not less than `key`.
template <typename K>
- iterator lower_bound(const K &key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ iterator lower_bound(const K &key) {
return internal_end(internal_lower_bound(key).value);
}
template <typename K>
- const_iterator lower_bound(const K &key) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ const_iterator lower_bound(const K &key) const {
return internal_end(internal_lower_bound(key).value);
}
// Finds the first element whose key is not less than `key` and also returns
// whether that element is equal to `key`.
template <typename K>
- std::pair<iterator, bool> lower_bound_equal(const K &key) const
- ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ std::pair<iterator, bool> lower_bound_equal(const K &key) const;
// Finds the first element whose key is greater than `key`.
template <typename K>
- iterator upper_bound(const K &key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ iterator upper_bound(const K &key) {
return internal_end(internal_upper_bound(key));
}
template <typename K>
- const_iterator upper_bound(const K &key) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ const_iterator upper_bound(const K &key) const {
return internal_end(internal_upper_bound(key));
}
@@ -1499,11 +1488,9 @@ class btree {
// the returned pair is equal to lower_bound(key). The second member of the
// pair is equal to upper_bound(key).
template <typename K>
- std::pair<iterator, iterator> equal_range(const K &key)
- ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ std::pair<iterator, iterator> equal_range(const K &key);
template <typename K>
- std::pair<const_iterator, const_iterator> equal_range(const K &key) const
- ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ std::pair<const_iterator, const_iterator> equal_range(const K &key) const {
return const_cast<btree *>(this)->equal_range(key);
}
@@ -1512,8 +1499,7 @@ class btree {
// Requirement: if `key` already exists in the btree, does not consume `args`.
// Requirement: `key` is never referenced after consuming `args`.
template <typename K, typename... Args>
- std::pair<iterator, bool> insert_unique(const K &key, Args &&...args)
- ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ std::pair<iterator, bool> insert_unique(const K &key, Args &&...args);
// Inserts with hint. Checks to see if the value should be placed immediately
// before `position` in the tree. If so, then the insertion will take
@@ -1523,8 +1509,7 @@ class btree {
// Requirement: `key` is never referenced after consuming `args`.
template <typename K, typename... Args>
std::pair<iterator, bool> insert_hint_unique(iterator position, const K &key,
- Args &&...args)
- ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ Args &&...args);
// Insert a range of values into the btree.
// Note: the first overload avoids constructing a value_type if the key
@@ -1541,12 +1526,11 @@ class btree {
// Inserts a value into the btree.
template <typename ValueType>
- iterator insert_multi(const key_type &key,
- ValueType &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ iterator insert_multi(const key_type &key, ValueType &&v);
// Inserts a value into the btree.
template <typename ValueType>
- iterator insert_multi(ValueType &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ iterator insert_multi(ValueType &&v) {
return insert_multi(params_type::key(v), std::forward<ValueType>(v));
}
@@ -1555,8 +1539,7 @@ class btree {
// amortized constant time. If not, the insertion will take amortized
// logarithmic time as if a call to insert_multi(v) were made.
template <typename ValueType>
- iterator insert_hint_multi(iterator position,
- ValueType &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ iterator insert_hint_multi(iterator position, ValueType &&v);
// Insert a range of values into the btree.
template <typename InputIterator>
@@ -1567,21 +1550,20 @@ class btree {
// (i.e. not equal to end()). Return an iterator pointing to the node after
// the one that was erased (or end() if none exists).
// Requirement: does not read the value at `*iter`.
- iterator erase(iterator iter) ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ iterator erase(iterator iter);
// Erases range. Returns the number of keys erased and an iterator pointing
// to the element after the last erased element.
- std::pair<size_type, iterator> erase_range(iterator begin, iterator end)
- ABSL_ATTRIBUTE_LIFETIME_BOUND;
+ std::pair<size_type, iterator> erase_range(iterator begin, iterator end);
// Finds an element with key equivalent to `key` or returns `end()` if `key`
// is not present.
template <typename K>
- iterator find(const K &key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ iterator find(const K &key) {
return internal_end(internal_find(key));
}
template <typename K>
- const_iterator find(const K &key) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ const_iterator find(const K &key) const {
return internal_end(internal_find(key));
}
@@ -1591,7 +1573,7 @@ class btree {
// Swaps the contents of `this` and `other`.
void swap(btree &other);
- const key_compare &key_comp() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ const key_compare &key_comp() const noexcept {
return rightmost_.template get<0>();
}
template <typename K1, typename K2>
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 3c404500..a68ce445 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -95,18 +95,36 @@ class btree_container {
std::is_nothrow_move_assignable<Tree>::value) = default;
// Iterator routines.
- iterator begin() { return tree_.begin(); }
- const_iterator begin() const { return tree_.begin(); }
- const_iterator cbegin() const { return tree_.begin(); }
- iterator end() { return tree_.end(); }
- const_iterator end() const { return tree_.end(); }
- const_iterator cend() const { return tree_.end(); }
- reverse_iterator rbegin() { return tree_.rbegin(); }
- const_reverse_iterator rbegin() const { return tree_.rbegin(); }
- const_reverse_iterator crbegin() const { return tree_.rbegin(); }
- reverse_iterator rend() { return tree_.rend(); }
- const_reverse_iterator rend() const { return tree_.rend(); }
- const_reverse_iterator crend() const { return tree_.rend(); }
+ iterator begin() ABSL_ATTRIBUTE_LIFETIME_BOUND { return tree_.begin(); }
+ const_iterator begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.begin();
+ }
+ const_iterator cbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.begin();
+ }
+ iterator end() ABSL_ATTRIBUTE_LIFETIME_BOUND { return tree_.end(); }
+ const_iterator end() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.end();
+ }
+ const_iterator cend() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.end();
+ }
+ reverse_iterator rbegin() ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.rbegin();
+ }
+ const_reverse_iterator rbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.rbegin();
+ }
+ const_reverse_iterator crbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.rbegin();
+ }
+ reverse_iterator rend() ABSL_ATTRIBUTE_LIFETIME_BOUND { return tree_.rend(); }
+ const_reverse_iterator rend() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.rend();
+ }
+ const_reverse_iterator crend() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.rend();
+ }
// Lookup routines.
template <typename K = key_type>
@@ -115,11 +133,12 @@ class btree_container {
return equal_range.second - equal_range.first;
}
template <typename K = key_type>
- iterator find(const key_arg<K> &key) {
+ iterator find(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.find(key);
}
template <typename K = key_type>
- const_iterator find(const key_arg<K> &key) const {
+ const_iterator find(const key_arg<K> &key) const
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.find(key);
}
template <typename K = key_type>
@@ -127,28 +146,31 @@ class btree_container {
return find(key) != end();
}
template <typename K = key_type>
- iterator lower_bound(const key_arg<K> &key) {
+ iterator lower_bound(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.lower_bound(key);
}
template <typename K = key_type>
- const_iterator lower_bound(const key_arg<K> &key) const {
+ const_iterator lower_bound(const key_arg<K> &key) const
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.lower_bound(key);
}
template <typename K = key_type>
- iterator upper_bound(const key_arg<K> &key) {
+ iterator upper_bound(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.upper_bound(key);
}
template <typename K = key_type>
- const_iterator upper_bound(const key_arg<K> &key) const {
+ const_iterator upper_bound(const key_arg<K> &key) const
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.upper_bound(key);
}
template <typename K = key_type>
- std::pair<iterator, iterator> equal_range(const key_arg<K> &key) {
+ std::pair<iterator, iterator> equal_range(const key_arg<K> &key)
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.equal_range(key);
}
template <typename K = key_type>
std::pair<const_iterator, const_iterator> equal_range(
- const key_arg<K> &key) const {
+ const key_arg<K> &key) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.equal_range(key);
}
@@ -158,9 +180,14 @@ class btree_container {
// Erase the specified iterator from the btree. The iterator must be valid
// (i.e. not equal to end()). Return an iterator pointing to the node after
// the one that was erased (or end() if none exists).
- iterator erase(const_iterator iter) { return tree_.erase(iterator(iter)); }
- iterator erase(iterator iter) { return tree_.erase(iter); }
- iterator erase(const_iterator first, const_iterator last) {
+ iterator erase(const_iterator iter) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.erase(iterator(iter));
+ }
+ iterator erase(iterator iter) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ return tree_.erase(iter);
+ }
+ iterator erase(const_iterator first,
+ const_iterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND {
return tree_.erase_range(iterator(first), iterator(last)).second;
}
template <typename K = key_type>
@@ -170,8 +197,8 @@ class btree_container {
}
// Extract routines.
- extract_and_get_next_return_type extract_and_get_next(
- const_iterator position) {
+ extract_and_get_next_return_type extract_and_get_next(const_iterator position)
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
// Use Construct instead of Transfer because the rebalancing code will
// destroy the slot later.
// Note: we rely on erase() taking place after Construct().
@@ -298,32 +325,38 @@ class btree_set_container : public btree_container<Tree> {
: btree_set_container(init.begin(), init.end(), alloc) {}
// Insertion routines.
- std::pair<iterator, bool> insert(const value_type &v) {
+ std::pair<iterator, bool> insert(const value_type &v)
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
return this->tree_.insert_unique(params_type::key(v), v);
}
- std::pair<iterator, bool> insert(value_type &&v) {
+ std::pair<iterator, bool> insert(value_type &&v)
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
return this->tree_.insert_unique(params_type::key(v), std::move(v));
}
template <typename... Args>
- std::pair<iterator, bool> emplace(Args &&... args) {
+ std::pair<iterator, bool> emplace(Args &&...args)
+ ABSL_ATTRIBUTE_LIFETIME_BOUND {
// Use a node handle to manage a temp slot.
auto node = CommonAccess::Construct<node_type>(this->get_allocator(),
std::forward<Args>(args)...);
auto *slot = CommonAccess::GetSlot(node);
return this->tree_.insert_unique(params_type::key(slot), slot);
}
- iterator insert(const_iterator hint, const value_type &v) {
+ iterator insert(const_iterator hint,
+ const value_type &v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
return this->tree_
.insert_hint_unique(iterator(hint), params_type::key(v), v)
.first;
}
- iterator insert(const_iterator hint, value_type &&v) {
+ iterator insert(const_iterator hint,
+ value_type &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
return this->tree_
.insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
.first;
}
template <typename... Args>
- iterator emplace_hint(const_iterator hint, Args &&... args) {
+ iterator emplace_hint(const_iterator hint,
+ Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
// Use a node handle to manage a temp slot.
auto node = CommonAccess::Construct<node_type>(this->get_allocator(),
std::forward<Args>(args)...);
@@ -339,7 +372,7 @@ class btree_set_container : public btree_container<Tree> {
void insert(std::initializer_list<init_type> init) {
this->tree_.insert_iterator_unique(init.begin(), init.end(), 0);
}
- insert_return_type insert(node_type &&node) {
+ insert_return_type insert(node_type &&node) ABSL_ATTRIBUTE_LIFETIME_BOUND {
if (!node) return {this->end(), false, node_type()};
std::pair<iterator, bool> res =
this->tree_.insert_unique(params_type::key(CommonAccess::GetSlot(node)),
@@ -351,7 +384,8 @@ class btree_set_container : public btree_container<Tree> {
return {res.first, false, std::move(node)};
}
}
- iterator insert(const_iterator hint, node_type &&node) {
+ iterator insert(const_iterator hint,
+ node_type &&node) ABSL_ATTRIBUTE_LIFETIME_BOUND {
if (!node) return this->end();
std::pair<iterator, bool> res = this->tree_.insert_hint_unique(
iterator(hint), params_type::key(CommonAccess::GetSlot(node)),