Export of internal Abseil changes

--
d2b7a83bafb90d35b2b7d8eb4177e9d712e8d62c by Gennadiy Rozental <rogeeff@google.com>:

Introduce ABSL specific macros for detecting the usage of sanitizers.

PiperOrigin-RevId: 321687443

--
a41342cc04b1088087dda12d7272aa3835f8e36a by Evan Brown <ezb@google.com>:

Get rid of recursion in clear_and_delete().

PiperOrigin-RevId: 321583786

--
99c6d300b17f186c28867b08cc79f1e55077e88a by Evan Brown <ezb@google.com>:

Code simplification: consolidate methods to erase values/nodes.

Motivation: this will make floating storage work simpler.

- Delete erase_same_node/erase_from_leaf_node/remove_value/remove_values_ignore_children.
- Move node deletion methods inside btree_node.
- Delete three-argument move() and use transfer_n() instead.
- Note: there's still one usage of move (in btree::erase(iterator)) that could use transfer, but I think doing so would add more complexity than it's worth.

PiperOrigin-RevId: 321407673

--
c3efed6c1763190c6b3bccbede9b2989ab21b258 by Evan Brown <ezb@google.com>:

Support heterogeneous insert_or_assign, try_emplace, operator[] for btree_map.

Also do a bit of cleanup:
- Add _impl methods for insert_or_assign/try_emplace.
- Rename some hint iterator params from `position` to `hint`.

PiperOrigin-RevId: 321399557
GitOrigin-RevId: d2b7a83bafb90d35b2b7d8eb4177e9d712e8d62c
Change-Id: Ie2d0c7c3ed197c2b53d475248941392cbad20e59

1 files changed, 96 insertions, 103 deletions

diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index d0fc645..3b2e8a9 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -268,23 +268,21 @@ class btree_set_container : public btree_container<Tree> {
     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 &v) {
+  iterator insert(const_iterator hint, const value_type &v) {
     return this->tree_
-        .insert_hint_unique(iterator(position), params_type::key(v), v)
+        .insert_hint_unique(iterator(hint), params_type::key(v), v)
         .first;
   }
-  iterator insert(const_iterator position, value_type &&v) {
+  iterator insert(const_iterator hint, value_type &&v) {
     return this->tree_
-        .insert_hint_unique(iterator(position), params_type::key(v),
-                            std::move(v))
+        .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
         .first;
   }
   template <typename... Args>
-  iterator emplace_hint(const_iterator position, Args &&... args) {
+  iterator emplace_hint(const_iterator hint, Args &&... args) {
     init_type v(std::forward<Args>(args)...);
     return this->tree_
-        .insert_hint_unique(iterator(position), params_type::key(v),
-                            std::move(v))
+        .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
         .first;
   }
   template <typename InputIterator>
@@ -392,111 +390,72 @@ class btree_map_container : public btree_set_container<Tree> {
   // Insertion routines.
   // Note: the nullptr template arguments and extra `const M&` overloads allow
   // for supporting bitfield arguments.
-  // Note: when we call `std::forward<M>(obj)` twice, it's safe because
-  // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
-  // `ret.second` is false.
-  template <class M>
-  std::pair<iterator, bool> insert_or_assign(const key_type &k, const M &obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_unique(k, k, obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret;
+  template <typename K = key_type, class M>
+  std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k,
+                                             const M &obj) {
+    return insert_or_assign_impl(k, obj);
   }
-  template <class M, key_type * = nullptr>
-  std::pair<iterator, bool> insert_or_assign(key_type &&k, const M &obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_unique(k, std::move(k), obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret;
+  template <typename K = key_type, class M, K * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, const M &obj) {
+    return insert_or_assign_impl(std::forward<K>(k), obj);
   }
-  template <class M, M * = nullptr>
-  std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_unique(k, k, std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret;
+  template <typename K = key_type, class M, M * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k, M &&obj) {
+    return insert_or_assign_impl(k, std::forward<M>(obj));
   }
-  template <class M, key_type * = nullptr, M * = nullptr>
-  std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_unique(k, std::move(k), std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret;
+  template <typename K = key_type, class M, K * = nullptr, M * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, M &&obj) {
+    return insert_or_assign_impl(std::forward<K>(k), std::forward<M>(obj));
   }
-  template <class M>
-  iterator insert_or_assign(const_iterator position, const key_type &k,
+  template <typename K = key_type, class M>
+  iterator insert_or_assign(const_iterator hint, const key_arg<K> &k,
                             const M &obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_hint_unique(iterator(position), k, k, obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret.first;
+    return insert_or_assign_hint_impl(hint, k, obj);
   }
-  template <class M, key_type * = nullptr>
-  iterator insert_or_assign(const_iterator position, key_type &&k,
-                            const M &obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
-        iterator(position), k, std::move(k), obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret.first;
+  template <typename K = key_type, class M, K * = nullptr>
+  iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, const M &obj) {
+    return insert_or_assign_hint_impl(hint, std::forward<K>(k), obj);
   }
-  template <class M, M * = nullptr>
-  iterator insert_or_assign(const_iterator position, const key_type &k,
-                            M &&obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
-        iterator(position), k, k, std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret.first;
+  template <typename K = key_type, class M, M * = nullptr>
+  iterator insert_or_assign(const_iterator hint, const key_arg<K> &k, M &&obj) {
+    return insert_or_assign_hint_impl(hint, k, std::forward<M>(obj));
   }
-  template <class M, key_type * = nullptr, M * = nullptr>
-  iterator insert_or_assign(const_iterator position, key_type &&k, M &&obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
-        iterator(position), k, std::move(k), std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret.first;
+  template <typename K = key_type, class M, K * = nullptr, M * = nullptr>
+  iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, M &&obj) {
+    return insert_or_assign_hint_impl(hint, std::forward<K>(k),
+                                      std::forward<M>(obj));
   }
-  template <typename... Args>
-  std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args) {
-    return this->tree_.insert_unique(
-        k, std::piecewise_construct, std::forward_as_tuple(k),
-        std::forward_as_tuple(std::forward<Args>(args)...));
+
+  template <typename K = key_type, typename... Args,
+            typename absl::enable_if_t<
+                !std::is_convertible<K, const_iterator>::value, int> = 0>
+  std::pair<iterator, bool> try_emplace(const key_arg<K> &k, Args &&... args) {
+    return try_emplace_impl(k, std::forward<Args>(args)...);
   }
-  template <typename... Args>
-  std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args) {
-    // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
-    // and then using `k` unsequenced. This is safe because the move is into a
-    // forwarding reference and insert_unique guarantees that `key` is never
-    // referenced after consuming `args`.
-    const key_type &key_ref = k;
-    return this->tree_.insert_unique(
-        key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)),
-        std::forward_as_tuple(std::forward<Args>(args)...));
+  template <typename K = key_type, typename... Args,
+            typename absl::enable_if_t<
+                !std::is_convertible<K, const_iterator>::value, int> = 0>
+  std::pair<iterator, bool> try_emplace(key_arg<K> &&k, Args &&... args) {
+    return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
   }
-  template <typename... Args>
-  iterator try_emplace(const_iterator hint, const key_type &k,
+  template <typename K = key_type, typename... Args>
+  iterator try_emplace(const_iterator hint, const key_arg<K> &k,
                        Args &&... args) {
-    return this->tree_
-        .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
-                            std::forward_as_tuple(k),
-                            std::forward_as_tuple(std::forward<Args>(args)...))
-        .first;
+    return try_emplace_hint_impl(hint, k, std::forward<Args>(args)...);
   }
-  template <typename... Args>
-  iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args) {
-    // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
-    // and then using `k` unsequenced. This is safe because the move is into a
-    // forwarding reference and insert_hint_unique guarantees that `key` is
-    // never referenced after consuming `args`.
-    const key_type &key_ref = k;
-    return this->tree_
-        .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct,
-                            std::forward_as_tuple(std::move(k)),
-                            std::forward_as_tuple(std::forward<Args>(args)...))
-        .first;
+  template <typename K = key_type, typename... Args>
+  iterator try_emplace(const_iterator hint, key_arg<K> &&k, Args &&... args) {
+    return try_emplace_hint_impl(hint, std::forward<K>(k),
+                                 std::forward<Args>(args)...);
   }
-  mapped_type &operator[](const key_type &k) {
+
+  template <typename K = key_type>
+  mapped_type &operator[](const key_arg<K> &k) {
     return try_emplace(k).first->second;
   }
-  mapped_type &operator[](key_type &&k) {
-    return try_emplace(std::move(k)).first->second;
+  template <typename K = key_type>
+  mapped_type &operator[](key_arg<K> &&k) {
+    return try_emplace(std::forward<K>(k)).first->second;
   }
 
   template <typename K = key_type>
@@ -513,6 +472,40 @@ class btree_map_container : public btree_set_container<Tree> {
       base_internal::ThrowStdOutOfRange("absl::btree_map::at");
     return it->second;
   }
+
+ private:
+  // Note: when we call `std::forward<M>(obj)` twice, it's safe because
+  // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
+  // `ret.second` is false.
+  template <class K, class M>
+  std::pair<iterator, bool> insert_or_assign_impl(K &&k, M &&obj) {
+    const std::pair<iterator, bool> ret =
+        this->tree_.insert_unique(k, std::forward<K>(k), std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret;
+  }
+  template <class K, class M>
+  iterator insert_or_assign_hint_impl(const_iterator hint, K &&k, M &&obj) {
+    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
+        iterator(hint), k, std::forward<K>(k), std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret.first;
+  }
+
+  template <class K, class... Args>
+  std::pair<iterator, bool> try_emplace_impl(K &&k, Args &&... args) {
+    return this->tree_.insert_unique(
+        k, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(k)),
+        std::forward_as_tuple(std::forward<Args>(args)...));
+  }
+  template <class K, class... Args>
+  iterator try_emplace_hint_impl(const_iterator hint, K &&k, Args &&... args) {
+    return this->tree_
+        .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
+                            std::forward_as_tuple(std::forward<K>(k)),
+                            std::forward_as_tuple(std::forward<Args>(args)...))
+        .first;
+  }
 };
 
 // A common base class for btree_multiset and btree_multimap.
@@ -566,11 +559,11 @@ class btree_multiset_container : public btree_container<Tree> {
   iterator insert(value_type &&v) {
     return this->tree_.insert_multi(std::move(v));
   }
-  iterator insert(const_iterator position, const value_type &v) {
-    return this->tree_.insert_hint_multi(iterator(position), v);
+  iterator insert(const_iterator hint, const value_type &v) {
+    return this->tree_.insert_hint_multi(iterator(hint), v);
   }
-  iterator insert(const_iterator position, value_type &&v) {
-    return this->tree_.insert_hint_multi(iterator(position), std::move(v));
+  iterator insert(const_iterator hint, value_type &&v) {
+    return this->tree_.insert_hint_multi(iterator(hint), std::move(v));
   }
   template <typename InputIterator>
   void insert(InputIterator b, InputIterator e) {
@@ -584,9 +577,9 @@ class btree_multiset_container : public btree_container<Tree> {
     return this->tree_.insert_multi(init_type(std::forward<Args>(args)...));
   }
   template <typename... Args>
-  iterator emplace_hint(const_iterator position, Args &&... args) {
+  iterator emplace_hint(const_iterator hint, Args &&... args) {
     return this->tree_.insert_hint_multi(
-        iterator(position), init_type(std::forward<Args>(args)...));
+        iterator(hint), init_type(std::forward<Args>(args)...));
   }
   iterator insert(node_type &&node) {
     if (!node) return this->end();