Export of internal Abseil changes.

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

Release SwissTable - a fast, efficient, cache-friendly hash table.

https://www.youtube.com/watch?v=ncHmEUmJZf4

PiperOrigin-RevId: 214816527

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

Internal change

PiperOrigin-RevId: 214785288

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

Internal change

PiperOrigin-RevId: 214722931

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

Internal change

PiperOrigin-RevId: 214701684
GitOrigin-RevId: 4eacae3ff1b14b1d309e8092185bc10e8a6203cf
Change-Id: I9ba64e395b22ad7863213d157b8019b082adc19d

1 files changed, 187 insertions, 0 deletions

diff --git a/absl/container/internal/unordered_set_modifiers_test.h b/absl/container/internal/unordered_set_modifiers_test.h
new file mode 100644
index 000000000000..9beacf331697
--- /dev/null
+++ b/absl/container/internal/unordered_set_modifiers_test.h
@@ -0,0 +1,187 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
+#define ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/container/internal/hash_generator_testing.h"
+#include "absl/container/internal/hash_policy_testing.h"
+
+namespace absl {
+namespace container_internal {
+
+template <class UnordSet>
+class ModifiersTest : public ::testing::Test {};
+
+TYPED_TEST_CASE_P(ModifiersTest);
+
+TYPED_TEST_P(ModifiersTest, Clear) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end());
+  ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
+  m.clear();
+  EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
+  EXPECT_TRUE(m.empty());
+}
+
+TYPED_TEST_P(ModifiersTest, Insert) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  T val = hash_internal::Generator<T>()();
+  TypeParam m;
+  auto p = m.insert(val);
+  EXPECT_TRUE(p.second);
+  EXPECT_EQ(val, *p.first);
+  p = m.insert(val);
+  EXPECT_FALSE(p.second);
+}
+
+TYPED_TEST_P(ModifiersTest, InsertHint) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  T val = hash_internal::Generator<T>()();
+  TypeParam m;
+  auto it = m.insert(m.end(), val);
+  EXPECT_TRUE(it != m.end());
+  EXPECT_EQ(val, *it);
+  it = m.insert(it, val);
+  EXPECT_TRUE(it != m.end());
+  EXPECT_EQ(val, *it);
+}
+
+TYPED_TEST_P(ModifiersTest, InsertRange) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m;
+  m.insert(values.begin(), values.end());
+  ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
+}
+
+TYPED_TEST_P(ModifiersTest, Emplace) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  T val = hash_internal::Generator<T>()();
+  TypeParam m;
+  // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
+  // with test traits/policy.
+  auto p = m.emplace(val);
+  EXPECT_TRUE(p.second);
+  EXPECT_EQ(val, *p.first);
+  p = m.emplace(val);
+  EXPECT_FALSE(p.second);
+  EXPECT_EQ(val, *p.first);
+}
+
+TYPED_TEST_P(ModifiersTest, EmplaceHint) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  T val = hash_internal::Generator<T>()();
+  TypeParam m;
+  // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
+  // with test traits/policy.
+  auto it = m.emplace_hint(m.end(), val);
+  EXPECT_EQ(val, *it);
+  it = m.emplace_hint(it, val);
+  EXPECT_EQ(val, *it);
+}
+
+template <class V>
+using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
+
+// In openmap we chose not to return the iterator from erase because that's
+// more expensive. As such we adapt erase to return an iterator here.
+struct EraseFirst {
+  template <class Map>
+  auto operator()(Map* m, int) const
+      -> IfNotVoid<decltype(m->erase(m->begin()))> {
+    return m->erase(m->begin());
+  }
+  template <class Map>
+  typename Map::iterator operator()(Map* m, ...) const {
+    auto it = m->begin();
+    m->erase(it++);
+    return it;
+  }
+};
+
+TYPED_TEST_P(ModifiersTest, Erase) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end());
+  ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
+  std::vector<T> values2;
+  for (const auto& val : values)
+    if (val != *m.begin()) values2.push_back(val);
+  auto it = EraseFirst()(&m, 0);
+  ASSERT_TRUE(it != m.end());
+  EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
+  EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values2.begin(),
+                                                            values2.end()));
+}
+
+TYPED_TEST_P(ModifiersTest, EraseRange) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end());
+  ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
+  auto it = m.erase(m.begin(), m.end());
+  EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
+  EXPECT_TRUE(it == m.end());
+}
+
+TYPED_TEST_P(ModifiersTest, EraseKey) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  std::vector<T> values;
+  std::generate_n(std::back_inserter(values), 10,
+                  hash_internal::Generator<T>());
+  TypeParam m(values.begin(), values.end());
+  ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
+  EXPECT_EQ(1, m.erase(values[0]));
+  EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
+  EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
+                                                            values.end()));
+}
+
+TYPED_TEST_P(ModifiersTest, Swap) {
+  using T = hash_internal::GeneratedType<TypeParam>;
+  std::vector<T> v1;
+  std::vector<T> v2;
+  std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
+  std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
+  TypeParam m1(v1.begin(), v1.end());
+  TypeParam m2(v2.begin(), v2.end());
+  EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v1));
+  EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v2));
+  m1.swap(m2);
+  EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v2));
+  EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v1));
+}
+
+// TODO(alkis): Write tests for extract.
+// TODO(alkis): Write tests for merge.
+
+REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint,
+                           InsertRange, Emplace, EmplaceHint, Erase, EraseRange,
+                           EraseKey, Swap);
+
+}  // namespace container_internal
+}  // namespace absl
+#endif  // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_