Export of internal Abseil changes

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

Import of CCTZ from GitHub.

PiperOrigin-RevId: 338723934

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

Add script to test GCC floor (the minimum version of GCC we support,
currently the GCC 5 series)

PiperOrigin-RevId: 338708581

--
afa440ac7c843126b4f99b89ebc071dda1d85a4d by Abseil Team <absl-team@google.com>:

Fix typo in documentation of StatusOr::value_or() ('of' -> 'if').

PiperOrigin-RevId: 338690089

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

Import of CCTZ from GitHub.

PiperOrigin-RevId: 338568224

--
da5e09a7fedb3217329465d9206b7cbc6677176b by Abseil Team <absl-team@google.com>:

Add `absl_btree_prefer_linear_node_search`

Allow keys of `btree_set`, `btree_map`, `btree_multiset`, and `btree_multimap`
to opt-in to linear search (instead of binary search).  Linear search was
used previously for arithmetic types with `key_compare` of `std::greater`
or `std::less`.

For example, this would be useful for key types that wrap an integer
and define their own cheap `operator<()`.

```
 class K {
  public:
   using absl_btree_prefer_linear_node_search = std::true_type;
   ...
  private:
   friend bool operator<(K a, K b) { return a.k_ < b.k_; }
   int k_;
 };

 absl::btree_map<K, V> m;  // Uses linear search
 assert((absl::btree_map<K, V>::testonly_uses_linear_node_search()));
```

PiperOrigin-RevId: 338476553

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

Import of CCTZ from GitHub.

PiperOrigin-RevId: 338419417
GitOrigin-RevId: 017c3924d21132085bc20c9be0ae469bfbf2c56c
Change-Id: I1199f3ae917280a3ef20ccc6038abbe34d96ec0b

2 files changed, 106 insertions, 3 deletions

diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index c2f098f0..7fa5d4f3 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1216,6 +1216,70 @@ class BtreeNodePeer {
 
 namespace {
 
+class BtreeMapTest : public ::testing::Test {
+ public:
+  struct Key {};
+  struct Cmp {
+    template <typename T>
+    bool operator()(T, T) const {
+      return false;
+    }
+  };
+
+  struct KeyLin {
+    using absl_btree_prefer_linear_node_search = std::true_type;
+  };
+  struct CmpLin : Cmp {
+    using absl_btree_prefer_linear_node_search = std::true_type;
+  };
+
+  struct KeyBin {
+    using absl_btree_prefer_linear_node_search = std::false_type;
+  };
+  struct CmpBin : Cmp {
+    using absl_btree_prefer_linear_node_search = std::false_type;
+  };
+
+  template <typename K, typename C>
+  static bool IsLinear() {
+    return BtreeNodePeer::UsesLinearNodeSearch<absl::btree_map<K, int, C>>();
+  }
+};
+
+TEST_F(BtreeMapTest, TestLinearSearchPreferredForKeyLinearViaAlias) {
+  // Test requesting linear search by directly exporting an alias.
+  EXPECT_FALSE((IsLinear<Key, Cmp>()));
+  EXPECT_TRUE((IsLinear<KeyLin, Cmp>()));
+  EXPECT_TRUE((IsLinear<Key, CmpLin>()));
+  EXPECT_TRUE((IsLinear<KeyLin, CmpLin>()));
+}
+
+TEST_F(BtreeMapTest, LinearChoiceTree) {
+  // Cmp has precedence, and is forcing binary
+  EXPECT_FALSE((IsLinear<Key, CmpBin>()));
+  EXPECT_FALSE((IsLinear<KeyLin, CmpBin>()));
+  EXPECT_FALSE((IsLinear<KeyBin, CmpBin>()));
+  EXPECT_FALSE((IsLinear<int, CmpBin>()));
+  EXPECT_FALSE((IsLinear<std::string, CmpBin>()));
+  // Cmp has precedence, and is forcing linear
+  EXPECT_TRUE((IsLinear<Key, CmpLin>()));
+  EXPECT_TRUE((IsLinear<KeyLin, CmpLin>()));
+  EXPECT_TRUE((IsLinear<KeyBin, CmpLin>()));
+  EXPECT_TRUE((IsLinear<int, CmpLin>()));
+  EXPECT_TRUE((IsLinear<std::string, CmpLin>()));
+  // Cmp has no preference, Key determines linear vs binary.
+  EXPECT_FALSE((IsLinear<Key, Cmp>()));
+  EXPECT_TRUE((IsLinear<KeyLin, Cmp>()));
+  EXPECT_FALSE((IsLinear<KeyBin, Cmp>()));
+  // arithmetic key w/ std::less or std::greater: linear
+  EXPECT_TRUE((IsLinear<int, std::less<int>>()));
+  EXPECT_TRUE((IsLinear<double, std::greater<double>>()));
+  // arithmetic key w/ custom compare: binary
+  EXPECT_FALSE((IsLinear<int, Cmp>()));
+  // non-arithmetic key: binary
+  EXPECT_FALSE((IsLinear<std::string, std::less<std::string>>()));
+}
+
 TEST(Btree, BtreeMapCanHoldMoveOnlyTypes) {
   absl::btree_map<std::string, std::unique_ptr<std::string>> m;
 
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index cadbeab1..a82b5177 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -182,6 +182,38 @@ struct key_compare_to_adapter<std::greater<absl::Cord>> {
   using type = StringBtreeDefaultGreater;
 };
 
+// Detects an 'absl_btree_prefer_linear_node_search' member. This is
+// a protocol used as an opt-in or opt-out of linear search.
+//
+//  For example, this would be useful for key types that wrap an integer
+//  and define their own cheap operator<(). For example:
+//
+//   class K {
+//    public:
+//     using absl_btree_prefer_linear_node_search = std::true_type;
+//     ...
+//    private:
+//     friend bool operator<(K a, K b) { return a.k_ < b.k_; }
+//     int k_;
+//   };
+//
+//   btree_map<K, V> m;  // Uses linear search
+//
+// If T has the preference tag, then it has a preference.
+// Btree will use the tag's truth value.
+template <typename T, typename = void>
+struct has_linear_node_search_preference : std::false_type {};
+template <typename T, typename = void>
+struct prefers_linear_node_search : std::false_type {};
+template <typename T>
+struct has_linear_node_search_preference<
+    T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>>
+    : std::true_type {};
+template <typename T>
+struct prefers_linear_node_search<
+    T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>>
+    : T::absl_btree_prefer_linear_node_search {};
+
 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
           bool Multi, typename SlotPolicy>
 struct common_params {
@@ -424,15 +456,22 @@ class btree_node {
   using difference_type = typename Params::difference_type;
 
   // Btree decides whether to use linear node search as follows:
+  //   - If the comparator expresses a preference, use that.
+  //   - If the key expresses a preference, use that.
   //   - If the key is arithmetic and the comparator is std::less or
   //     std::greater, choose linear.
   //   - Otherwise, choose binary.
   // TODO(ezb): Might make sense to add condition(s) based on node-size.
   using use_linear_search = std::integral_constant<
       bool,
-                std::is_arithmetic<key_type>::value &&
-                    (std::is_same<std::less<key_type>, key_compare>::value ||
-                     std::is_same<std::greater<key_type>, key_compare>::value)>;
+      has_linear_node_search_preference<key_compare>::value
+          ? prefers_linear_node_search<key_compare>::value
+          : has_linear_node_search_preference<key_type>::value
+                ? prefers_linear_node_search<key_type>::value
+                : std::is_arithmetic<key_type>::value &&
+                      (std::is_same<std::less<key_type>, key_compare>::value ||
+                       std::is_same<std::greater<key_type>,
+                                    key_compare>::value)>;
 
   // This class is organized by gtl::Layout as if it had the following
   // structure: