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

1 files changed, 64 insertions, 0 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;