tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

flat_hash_set_test.cc (11677B)

      1 // Copyright 2018 The Abseil Authors.
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      https://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 #include "absl/container/flat_hash_set.h"
     16 
     17 #include <cstddef>
     18 #include <cstdint>
     19 #include <memory>
     20 #include <string>
     21 #include <type_traits>
     22 #include <utility>
     23 #include <vector>
     24 
     25 #include "gmock/gmock.h"
     26 #include "gtest/gtest.h"
     27 #include "absl/base/config.h"
     28 #include "absl/container/hash_container_defaults.h"
     29 #include "absl/container/internal/container_memory.h"
     30 #include "absl/container/internal/hash_generator_testing.h"
     31 #include "absl/container/internal/test_allocator.h"
     32 #include "absl/container/internal/unordered_set_constructor_test.h"
     33 #include "absl/container/internal/unordered_set_lookup_test.h"
     34 #include "absl/container/internal/unordered_set_members_test.h"
     35 #include "absl/container/internal/unordered_set_modifiers_test.h"
     36 #include "absl/hash/hash.h"
     37 #include "absl/log/check.h"
     38 #include "absl/memory/memory.h"
     39 #include "absl/strings/string_view.h"
     40 
     41 namespace absl {
     42 ABSL_NAMESPACE_BEGIN
     43 namespace container_internal {
     44 namespace {
     45 
     46 using ::absl::container_internal::hash_internal::Enum;
     47 using ::absl::container_internal::hash_internal::EnumClass;
     48 using ::testing::IsEmpty;
     49 using ::testing::Pointee;
     50 using ::testing::UnorderedElementsAre;
     51 using ::testing::UnorderedElementsAreArray;
     52 
     53 // Check that absl::flat_hash_set works in a global constructor.
     54 struct BeforeMain {
     55  BeforeMain() {
     56    absl::flat_hash_set<int> x;
     57    x.insert(1);
     58    CHECK(!x.contains(0)) << "x should not contain 0";
     59    CHECK(x.contains(1)) << "x should contain 1";
     60  }
     61 };
     62 const BeforeMain before_main;
     63 
     64 template <class T>
     65 using Set =
     66    absl::flat_hash_set<T, StatefulTestingHash, StatefulTestingEqual, Alloc<T>>;
     67 
     68 using SetTypes =
     69    ::testing::Types<Set<int>, Set<std::string>, Set<Enum>, Set<EnumClass>>;
     70 
     71 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ConstructorTest, SetTypes);
     72 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, LookupTest, SetTypes);
     73 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, MembersTest, SetTypes);
     74 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ModifiersTest, SetTypes);
     75 
     76 TEST(FlatHashSet, EmplaceString) {
     77  std::vector<std::string> v = {"a", "b"};
     78  absl::flat_hash_set<absl::string_view> hs(v.begin(), v.end());
     79  EXPECT_THAT(hs, UnorderedElementsAreArray(v));
     80 }
     81 
     82 TEST(FlatHashSet, BitfieldArgument) {
     83  union {
     84    int n : 1;
     85  };
     86  n = 0;
     87  absl::flat_hash_set<int> s = {n};
     88  s.insert(n);
     89  s.insert(s.end(), n);
     90  s.insert({n});
     91  s.erase(n);
     92  s.count(n);
     93  s.prefetch(n);
     94  s.find(n);
     95  s.contains(n);
     96  s.equal_range(n);
     97 }
     98 
     99 TEST(FlatHashSet, MergeExtractInsert) {
    100  struct Hash {
    101    size_t operator()(const std::unique_ptr<int>& p) const { return *p; }
    102  };
    103  struct Eq {
    104    bool operator()(const std::unique_ptr<int>& a,
    105                    const std::unique_ptr<int>& b) const {
    106      return *a == *b;
    107    }
    108  };
    109  absl::flat_hash_set<std::unique_ptr<int>, Hash, Eq> set1, set2;
    110  set1.insert(absl::make_unique<int>(7));
    111  set1.insert(absl::make_unique<int>(17));
    112 
    113  set2.insert(absl::make_unique<int>(7));
    114  set2.insert(absl::make_unique<int>(19));
    115 
    116  EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17)));
    117  EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(19)));
    118 
    119  set1.merge(set2);
    120 
    121  EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17), Pointee(19)));
    122  EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
    123 
    124  auto node = set1.extract(absl::make_unique<int>(7));
    125  EXPECT_TRUE(node);
    126  EXPECT_THAT(node.value(), Pointee(7));
    127  EXPECT_THAT(set1, UnorderedElementsAre(Pointee(17), Pointee(19)));
    128 
    129  auto insert_result = set2.insert(std::move(node));
    130  EXPECT_FALSE(node);
    131  EXPECT_FALSE(insert_result.inserted);
    132  EXPECT_TRUE(insert_result.node);
    133  EXPECT_THAT(insert_result.node.value(), Pointee(7));
    134  EXPECT_EQ(**insert_result.position, 7);
    135  EXPECT_NE(insert_result.position->get(), insert_result.node.value().get());
    136  EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
    137 
    138  node = set1.extract(absl::make_unique<int>(17));
    139  EXPECT_TRUE(node);
    140  EXPECT_THAT(node.value(), Pointee(17));
    141  EXPECT_THAT(set1, UnorderedElementsAre(Pointee(19)));
    142 
    143  node.value() = absl::make_unique<int>(23);
    144 
    145  insert_result = set2.insert(std::move(node));
    146  EXPECT_FALSE(node);
    147  EXPECT_TRUE(insert_result.inserted);
    148  EXPECT_FALSE(insert_result.node);
    149  EXPECT_EQ(**insert_result.position, 23);
    150  EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23)));
    151 }
    152 
    153 bool IsEven(int k) { return k % 2 == 0; }
    154 
    155 TEST(FlatHashSet, EraseIf) {
    156  // Erase all elements.
    157  {
    158    flat_hash_set<int> s = {1, 2, 3, 4, 5};
    159    EXPECT_EQ(erase_if(s, [](int) { return true; }), 5);
    160    EXPECT_THAT(s, IsEmpty());
    161  }
    162  // Erase no elements.
    163  {
    164    flat_hash_set<int> s = {1, 2, 3, 4, 5};
    165    EXPECT_EQ(erase_if(s, [](int) { return false; }), 0);
    166    EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5));
    167  }
    168  // Erase specific elements.
    169  {
    170    flat_hash_set<int> s = {1, 2, 3, 4, 5};
    171    EXPECT_EQ(erase_if(s, [](int k) { return k % 2 == 1; }), 3);
    172    EXPECT_THAT(s, UnorderedElementsAre(2, 4));
    173  }
    174  // Predicate is function reference.
    175  {
    176    flat_hash_set<int> s = {1, 2, 3, 4, 5};
    177    EXPECT_EQ(erase_if(s, IsEven), 2);
    178    EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
    179  }
    180  // Predicate is function pointer.
    181  {
    182    flat_hash_set<int> s = {1, 2, 3, 4, 5};
    183    EXPECT_EQ(erase_if(s, &IsEven), 2);
    184    EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
    185  }
    186 }
    187 
    188 TEST(FlatHashSet, CForEach) {
    189  using ValueType = std::pair<int, int>;
    190  flat_hash_set<ValueType> s;
    191  std::vector<ValueType> expected;
    192  for (int i = 0; i < 100; ++i) {
    193    {
    194      SCOPED_TRACE("mutable object iteration");
    195      std::vector<ValueType> v;
    196      absl::container_internal::c_for_each_fast(
    197          s, [&v](const ValueType& p) { v.push_back(p); });
    198      ASSERT_THAT(v, UnorderedElementsAreArray(expected));
    199    }
    200    {
    201      SCOPED_TRACE("const object iteration");
    202      std::vector<ValueType> v;
    203      const flat_hash_set<ValueType>& cs = s;
    204      absl::container_internal::c_for_each_fast(
    205          cs, [&v](const ValueType& p) { v.push_back(p); });
    206      ASSERT_THAT(v, UnorderedElementsAreArray(expected));
    207    }
    208    {
    209      SCOPED_TRACE("temporary object iteration");
    210      std::vector<ValueType> v;
    211      absl::container_internal::c_for_each_fast(
    212          flat_hash_set<ValueType>(s),
    213          [&v](const ValueType& p) { v.push_back(p); });
    214      ASSERT_THAT(v, UnorderedElementsAreArray(expected));
    215    }
    216    s.emplace(i, i);
    217    expected.emplace_back(i, i);
    218  }
    219 }
    220 
    221 class PoisonSoo {
    222  int64_t data_;
    223 
    224 public:
    225  explicit PoisonSoo(int64_t d) : data_(d) { SanitizerPoisonObject(&data_); }
    226  PoisonSoo(const PoisonSoo& that) : PoisonSoo(*that) {}
    227  ~PoisonSoo() { SanitizerUnpoisonObject(&data_); }
    228 
    229  int64_t operator*() const {
    230    SanitizerUnpoisonObject(&data_);
    231    const int64_t ret = data_;
    232    SanitizerPoisonObject(&data_);
    233    return ret;
    234  }
    235  template <typename H>
    236  friend H AbslHashValue(H h, const PoisonSoo& pi) {
    237    return H::combine(std::move(h), *pi);
    238  }
    239  bool operator==(const PoisonSoo& rhs) const { return **this == *rhs; }
    240 };
    241 
    242 TEST(FlatHashSet, PoisonSooBasic) {
    243  PoisonSoo a(0), b(1);
    244  flat_hash_set<PoisonSoo> set;
    245  set.insert(a);
    246  EXPECT_THAT(set, UnorderedElementsAre(a));
    247  set.insert(b);
    248  EXPECT_THAT(set, UnorderedElementsAre(a, b));
    249  set.erase(a);
    250  EXPECT_THAT(set, UnorderedElementsAre(b));
    251  set.rehash(0);  // Shrink to SOO.
    252  EXPECT_THAT(set, UnorderedElementsAre(b));
    253 }
    254 
    255 TEST(FlatHashSet, PoisonSooMoveConstructSooToSoo) {
    256  PoisonSoo a(0);
    257  flat_hash_set<PoisonSoo> set;
    258  set.insert(a);
    259  flat_hash_set<PoisonSoo> set2(std::move(set));
    260  EXPECT_THAT(set2, UnorderedElementsAre(a));
    261 }
    262 
    263 TEST(FlatHashSet, PoisonSooAllocMoveConstructSooToSoo) {
    264  PoisonSoo a(0);
    265  flat_hash_set<PoisonSoo> set;
    266  set.insert(a);
    267  flat_hash_set<PoisonSoo> set2(std::move(set), std::allocator<PoisonSoo>());
    268  EXPECT_THAT(set2, UnorderedElementsAre(a));
    269 }
    270 
    271 TEST(FlatHashSet, PoisonSooMoveAssignFullSooToEmptySoo) {
    272  PoisonSoo a(0);
    273  flat_hash_set<PoisonSoo> set, set2;
    274  set.insert(a);
    275  set2 = std::move(set);
    276  EXPECT_THAT(set2, UnorderedElementsAre(a));
    277 }
    278 
    279 TEST(FlatHashSet, PoisonSooMoveAssignFullSooToFullSoo) {
    280  PoisonSoo a(0), b(1);
    281  flat_hash_set<PoisonSoo> set, set2;
    282  set.insert(a);
    283  set2.insert(b);
    284  set2 = std::move(set);
    285  EXPECT_THAT(set2, UnorderedElementsAre(a));
    286 }
    287 
    288 TEST(FlatHashSet, FlatHashSetPolicyDestroyReturnsTrue) {
    289  EXPECT_TRUE((decltype(FlatHashSetPolicy<int>::destroy<std::allocator<int>>(
    290      nullptr, nullptr))()));
    291  EXPECT_FALSE(
    292      (decltype(FlatHashSetPolicy<int>::destroy<CountingAllocator<int>>(
    293          nullptr, nullptr))()));
    294  EXPECT_FALSE((decltype(FlatHashSetPolicy<std::unique_ptr<int>>::destroy<
    295                         std::allocator<int>>(nullptr, nullptr))()));
    296 }
    297 
    298 struct HashEqInvalidOnMove {
    299  HashEqInvalidOnMove() = default;
    300  HashEqInvalidOnMove(const HashEqInvalidOnMove& rhs) = default;
    301  HashEqInvalidOnMove(HashEqInvalidOnMove&& rhs) { rhs.moved = true; }
    302  HashEqInvalidOnMove& operator=(const HashEqInvalidOnMove& rhs) = default;
    303  HashEqInvalidOnMove& operator=(HashEqInvalidOnMove&& rhs) {
    304    rhs.moved = true;
    305    return *this;
    306  }
    307 
    308  size_t operator()(int x) const {
    309    CHECK(!moved);
    310    return absl::HashOf(x);
    311  }
    312 
    313  bool operator()(int x, int y) const {
    314    CHECK(!moved);
    315    return x == y;
    316  }
    317 
    318  bool moved = false;
    319 };
    320 
    321 TEST(FlatHashSet, MovedFromCleared_HashMustBeValid) {
    322  flat_hash_set<int, HashEqInvalidOnMove> s1, s2;
    323  // Moving the hashtable must not move the hasher because we need to support
    324  // this behavior.
    325  s2 = std::move(s1);
    326  s1.clear();
    327  s1.insert(2);
    328  EXPECT_THAT(s1, UnorderedElementsAre(2));
    329 }
    330 
    331 TEST(FlatHashSet, MovedFromCleared_EqMustBeValid) {
    332  flat_hash_set<int, DefaultHashContainerHash<int>, HashEqInvalidOnMove> s1, s2;
    333  // Moving the hashtable must not move the equality functor because we need to
    334  // support this behavior.
    335  s2 = std::move(s1);
    336  s1.clear();
    337  s1.insert(2);
    338  EXPECT_THAT(s1, UnorderedElementsAre(2));
    339 }
    340 
    341 TEST(FlatHashSet, Equality) {
    342  {
    343    flat_hash_set<int> s1 = {1, 2, 3};
    344    flat_hash_set<int> s2 = {1, 2, 3};
    345    EXPECT_EQ(s1, s2);
    346  }
    347  {
    348    flat_hash_set<std::string> s1 = {"a", "b", "c"};
    349    flat_hash_set<std::string> s2 = {"a", "b", "c"};
    350    EXPECT_EQ(s1, s2);
    351  }
    352 }
    353 
    354 class MoveOnlyInt {
    355 public:
    356  explicit MoveOnlyInt(int value) : value_(value) {}
    357 
    358  MoveOnlyInt(const MoveOnlyInt& other) = delete;
    359  MoveOnlyInt& operator=(const MoveOnlyInt& other) = delete;
    360 
    361  MoveOnlyInt(MoveOnlyInt&& other) = default;
    362  MoveOnlyInt& operator=(MoveOnlyInt&& other) = default;
    363 
    364  bool operator==(const MoveOnlyInt& other) const {
    365    return value_ == other.value_;
    366  }
    367  bool operator==(int other) const { return value_ == other; }
    368 
    369 private:
    370  template <typename H>
    371  friend H AbslHashValue(H h, const MoveOnlyInt& m) {
    372    return H::combine(std::move(h), m.value_);
    373  }
    374 
    375  int value_;
    376 };
    377 
    378 TEST(FlatHashSet, MoveOnlyKey) {
    379  flat_hash_set<MoveOnlyInt> s;
    380  s.insert(MoveOnlyInt(1));
    381  s.insert(MoveOnlyInt(2));
    382  s.insert(MoveOnlyInt(3));
    383  EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3));
    384 }
    385 
    386 }  // namespace
    387 }  // namespace container_internal
    388 ABSL_NAMESPACE_END
    389 }  // namespace absl