Export of internal Abseil changes

--
e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5 by Greg Falcon <gfalcon@google.com>:

Add extra tests exercising ShiftLeft() at boundary conditions, to guard against logic errors in our memory bounds checking.

PiperOrigin-RevId: 339326030

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

Fix a bug in b-tree erase() and count() in which we weren't accounting for cases where the comparator is heterogeneous and has different equivalence classes for different lookup types.

Optimize equal_range to avoid comparisons when possible.

PiperOrigin-RevId: 339270230

--
b4aa337c156fa91f74f25c676c679ae146311968 by Derek Mauro <dmauro@google.com>:

Fix execution of the cmake build scripts when not on Kokoro

PiperOrigin-RevId: 339131253

--
fa3d1f602f711be72fde6b5f29d6341b9b5f8a2c by Derek Mauro <dmauro@google.com>:

Update Docker container used for Alpine Linux testing

PiperOrigin-RevId: 339074246
GitOrigin-RevId: e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5
Change-Id: I2cc3adc4de3493203c8a944aedee40efa54af0c0

3 files changed, 58 insertions, 93 deletions

diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 4a495067..9b1b6436 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2680,6 +2680,12 @@ struct MultiKey {
   int i2;
 };
 
+bool operator==(const MultiKey a, const MultiKey b) {
+  return a.i1 == b.i1 && a.i2 == b.i2;
+}
+
+// A heterogeneous comparator that has different equivalence classes for
+// different lookup types.
 struct MultiKeyComp {
   using is_transparent = void;
   bool operator()(const MultiKey a, const MultiKey b) const {
@@ -2690,8 +2696,6 @@ struct MultiKeyComp {
   bool operator()(const MultiKey a, const int b) const { return a.i1 < b; }
 };
 
-// Test that when there's a heterogeneous comparator that behaves differently
-// for some heterogeneous operators, we get equal_range() right.
 TEST(Btree, MultiKeyEqualRange) {
   absl::btree_set<MultiKey, MultiKeyComp> set;
 
@@ -2709,6 +2713,19 @@ TEST(Btree, MultiKeyEqualRange) {
   }
 }
 
+TEST(Btree, MultiKeyErase) {
+  absl::btree_set<MultiKey, MultiKeyComp> set = {
+      {1, 1}, {2, 1}, {2, 2}, {3, 1}};
+  EXPECT_EQ(set.erase(2), 2);
+  EXPECT_THAT(set, ElementsAre(MultiKey{1, 1}, MultiKey{3, 1}));
+}
+
+TEST(Btree, MultiKeyCount) {
+  const absl::btree_set<MultiKey, MultiKeyComp> set = {
+      {1, 1}, {2, 1}, {2, 2}, {3, 1}};
+  EXPECT_EQ(set.count(2), 2);
+}
+
 TEST(Btree, AllocConstructor) {
   using Alloc = CountingAllocator<int>;
   using Set = absl::btree_set<int, std::less<int>, Alloc>;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 8547d68e..f2fc31df 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -423,6 +423,7 @@ struct SearchResult {
 // useful information.
 template <typename V>
 struct SearchResult<V, false> {
+  SearchResult() {}
   explicit SearchResult(V value) : value(value) {}
   SearchResult(V value, MatchKind /*match*/) : value(value) {}
 
@@ -1200,11 +1201,11 @@ class btree {
   // Finds the first element whose key is not less than key.
   template <typename K>
   iterator lower_bound(const K &key) {
-    return internal_end(internal_lower_bound(key));
+    return internal_end(internal_lower_bound(key).value);
   }
   template <typename K>
   const_iterator lower_bound(const K &key) const {
-    return internal_end(internal_lower_bound(key));
+    return internal_end(internal_lower_bound(key).value);
   }
 
   // Finds the first element whose key is greater than key.
@@ -1289,16 +1290,6 @@ class btree {
   // to the element after the last erased element.
   std::pair<size_type, iterator> erase_range(iterator begin, iterator end);
 
-  // Erases the specified key from the btree. Returns 1 if an element was
-  // erased and 0 otherwise.
-  template <typename K>
-  size_type erase_unique(const K &key);
-
-  // Erases all of the entries matching the specified key from the
-  // btree. Returns the number of elements erased.
-  template <typename K>
-  size_type erase_multi(const K &key);
-
   // Finds the iterator corresponding to a key or returns end() if the key is
   // not present.
   template <typename K>
@@ -1310,23 +1301,6 @@ class btree {
     return internal_end(internal_find(key));
   }
 
-  // Returns a count of the number of times the key appears in the btree.
-  template <typename K>
-  size_type count_unique(const K &key) const {
-    const iterator begin = internal_find(key);
-    if (begin.node == nullptr) {
-      // The key doesn't exist in the tree.
-      return 0;
-    }
-    return 1;
-  }
-  // Returns a count of the number of times the key appears in the btree.
-  template <typename K>
-  size_type count_multi(const K &key) const {
-    const auto range = equal_range(key);
-    return std::distance(range.first, range.second);
-  }
-
   // Clear the btree, deleting all of the values it contains.
   void clear();
 
@@ -1514,7 +1488,8 @@ class btree {
 
   // Internal routine which implements lower_bound().
   template <typename K>
-  iterator internal_lower_bound(const K &key) const;
+  SearchResult<iterator, is_key_compare_to::value> internal_lower_bound(
+      const K &key) const;
 
   // Internal routine which implements upper_bound().
   template <typename K>
@@ -1918,10 +1893,13 @@ constexpr bool btree<P>::static_assert_validation() {
 template <typename P>
 template <typename K>
 auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
-  const iterator lower = lower_bound(key);
-  // TODO(ezb): we should be able to avoid this comparison when there's a
-  // three-way comparator.
-  if (lower == end() || compare_keys(key, lower.key())) return {lower, lower};
+  const SearchResult<iterator, is_key_compare_to::value> res =
+      internal_lower_bound(key);
+  const iterator lower = internal_end(res.value);
+  if (res.HasMatch() ? !res.IsEq()
+                     : lower == end() || compare_keys(key, lower.key())) {
+    return {lower, lower};
+  }
 
   const iterator next = std::next(lower);
   // When the comparator is heterogeneous, we can't assume that comparison with
@@ -1941,7 +1919,7 @@ auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
   // Try once more to avoid the call to upper_bound() if there's only one
   // equivalent key. This should prevent all calls to upper_bound() in cases of
   // unique-containers with heterogeneous comparators in which all comparison
-  // operators are equivalent.
+  // operators have the same equivalence classes.
   if (next == end() || compare_keys(key, next.key())) return {lower, next};
 
   // In this case, we need to call upper_bound() to avoid worst case O(N)
@@ -2226,31 +2204,6 @@ auto btree<P>::erase_range(iterator begin, iterator end)
 }
 
 template <typename P>
-template <typename K>
-auto btree<P>::erase_unique(const K &key) -> size_type {
-  const iterator iter = internal_find(key);
-  if (iter.node == nullptr) {
-    // The key doesn't exist in the tree, return nothing done.
-    return 0;
-  }
-  erase(iter);
-  return 1;
-}
-
-template <typename P>
-template <typename K>
-auto btree<P>::erase_multi(const K &key) -> size_type {
-  const iterator begin = internal_lower_bound(key);
-  if (begin.node == nullptr) {
-    // The key doesn't exist in the tree, return nothing done.
-    return 0;
-  }
-  // Delete all of the keys between begin and upper_bound(key).
-  const iterator end = internal_end(internal_upper_bound(key));
-  return erase_range(begin, end).first;
-}
-
-template <typename P>
 void btree<P>::clear() {
   if (!empty()) {
     node_type::clear_and_delete(root(), mutable_allocator());
@@ -2548,16 +2501,24 @@ inline auto btree<P>::internal_locate(const K &key) const
 
 template <typename P>
 template <typename K>
-auto btree<P>::internal_lower_bound(const K &key) const -> iterator {
+auto btree<P>::internal_lower_bound(const K &key) const
+    -> SearchResult<iterator, is_key_compare_to::value> {
   iterator iter(const_cast<node_type *>(root()));
+  SearchResult<int, is_key_compare_to::value> res;
+  bool seen_eq = false;
   for (;;) {
-    iter.position = iter.node->lower_bound(key, key_comp()).value;
+    res = iter.node->lower_bound(key, key_comp());
+    iter.position = res.value;
+    // TODO(ezb): we should be able to terminate early on IsEq() if there can't
+    // be multiple equivalent keys in container for this lookup type.
     if (iter.node->leaf()) {
       break;
     }
+    seen_eq = seen_eq || res.IsEq();
     iter.node = iter.node->child(iter.position);
   }
-  return internal_last(iter);
+  if (res.IsEq()) return {iter, MatchKind::kEq};
+  return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe};
 }
 
 template <typename P>
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 3792bc21..887eda41 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -104,6 +104,11 @@ class btree_container {
 
   // Lookup routines.
   template <typename K = key_type>
+  size_type count(const key_arg<K> &key) const {
+    auto equal_range = this->equal_range(key);
+    return std::distance(equal_range.first, equal_range.second);
+  }
+  template <typename K = key_type>
   iterator find(const key_arg<K> &key) {
     return tree_.find(key);
   }
@@ -152,6 +157,11 @@ class btree_container {
   iterator erase(const_iterator first, const_iterator last) {
     return tree_.erase_range(iterator(first), iterator(last)).second;
   }
+  template <typename K = key_type>
+  size_type erase(const key_arg<K> &key) {
+    auto equal_range = this->equal_range(key);
+    return tree_.erase_range(equal_range.first, equal_range.second).first;
+  }
 
   // Extract routines.
   node_type extract(iterator position) {
@@ -270,12 +280,6 @@ class btree_set_container : public btree_container<Tree> {
                       const allocator_type &alloc)
       : btree_set_container(init.begin(), init.end(), alloc) {}
 
-  // Lookup routines.
-  template <typename K = key_type>
-  size_type count(const key_arg<K> &key) const {
-    return this->tree_.count_unique(key);
-  }
-
   // Insertion routines.
   std::pair<iterator, bool> insert(const value_type &v) {
     return this->tree_.insert_unique(params_type::key(v), v);
@@ -333,16 +337,10 @@ class btree_set_container : public btree_container<Tree> {
     return res.first;
   }
 
-  // Deletion routines.
-  // TODO(ezb): we should support heterogeneous comparators that have different
-  // behavior for K!=key_type.
-  template <typename K = key_type>
-  size_type erase(const key_arg<K> &key) {
-    return this->tree_.erase_unique(key);
-  }
-  using super_type::erase;
-
   // Node extraction routines.
+  // TODO(ezb): when the comparator is heterogeneous and has different
+  // equivalence classes for different lookup types, we should extract the first
+  // equivalent value if there are multiple.
   template <typename K = key_type>
   node_type extract(const key_arg<K> &key) {
     auto it = this->find(key);
@@ -578,12 +576,6 @@ class btree_multiset_container : public btree_container<Tree> {
                            const allocator_type &alloc)
       : btree_multiset_container(init.begin(), init.end(), alloc) {}
 
-  // Lookup routines.
-  template <typename K = key_type>
-  size_type count(const key_arg<K> &key) const {
-    return this->tree_.count_multi(key);
-  }
-
   // Insertion routines.
   iterator insert(const value_type &v) { return this->tree_.insert_multi(v); }
   iterator insert(value_type &&v) {
@@ -628,14 +620,9 @@ class btree_multiset_container : public btree_container<Tree> {
     return res;
   }
 
-  // Deletion routines.
-  template <typename K = key_type>
-  size_type erase(const key_arg<K> &key) {
-    return this->tree_.erase_multi(key);
-  }
-  using super_type::erase;
-
   // Node extraction routines.
+  // TODO(ezb): we are supposed to extract the first equivalent key if there are
+  // multiple, but this isn't guaranteed to extract the first one.
   template <typename K = key_type>
   node_type extract(const key_arg<K> &key) {
     auto it = this->find(key);