components/url_pattern_index/closed_hash_map_unittest.cc

// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/url_pattern_index/closed_hash_map.h"

#include <string>
#include <vector>

#include "components/url_pattern_index/uint64_hasher.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace url_pattern_index {

namespace {

template <typename MapType>
void ExpectHashMapIntegrity(const MapType& map, size_t min_capacity = 0) {
  EXPECT_EQ(map.entries().size(), map.size());
  EXPECT_EQ(map.hash_table().size(), map.table_size());
  EXPECT_LE(map.size() * 2, map.table_size());
  EXPECT_LE(min_capacity * 2, map.table_size());

  std::vector<bool> entry_is_referenced(map.size());
  for (size_t i = 0; i < map.table_size(); ++i) {
    SCOPED_TRACE(testing::Message() << "Hash-table slot: " << i);

    const uint32_t entry_index = map.hash_table()[i];
    if (static_cast<size_t>(entry_index) >= map.size())
      continue;
    EXPECT_FALSE(entry_is_referenced[entry_index]);
    entry_is_referenced[entry_index] = true;
  }

  for (size_t i = 0; i < map.size(); ++i) {
    SCOPED_TRACE(testing::Message() << "Hash-table entry index: " << i);
    EXPECT_TRUE(entry_is_referenced[i]);
  }
}

template <typename MapType>
void ExpectEmptyMap(const MapType& map, size_t min_capacity) {
  ExpectHashMapIntegrity(map, min_capacity);
  EXPECT_EQ(0u, map.size());
}

}  // namespace

TEST(ClosedHashMapTest, EmptyMapDefault) {
  HashMap<int, int> hm;
  ExpectEmptyMap(hm, 0);
  EXPECT_EQ(nullptr, hm.Get(0));
  EXPECT_EQ(nullptr, hm.Get(100500));
  EXPECT_GT(hm.table_size(), 0u);
}

TEST(ClosedHashMapTest, EmptyMapWithCapacity) {
  HashMap<int, int> hm(100);
  ExpectEmptyMap(hm, 100);
  EXPECT_EQ(nullptr, hm.Get(0));
  EXPECT_EQ(nullptr, hm.Get(100500));
}

TEST(ClosedHashMapTest, InsertDistinctAndGet) {
  HashMap<int, int> hm;
  static const int kKeys[] = {1, 5, 10, 3, -100500};
  for (int key : kKeys) {
    EXPECT_TRUE(hm.Insert(key, -key));
    ExpectHashMapIntegrity(hm);
  }
  for (int key : kKeys) {
    const int* value = hm.Get(key);
    ASSERT_NE(nullptr, value);
    EXPECT_EQ(-key, *value);
  }
  EXPECT_EQ(nullptr, hm.Get(1234567));
}

TEST(ClosedHashMapTest, InsertExistingAndGet) {
  HashMap<int, int> hm;

  EXPECT_TRUE(hm.Insert(123, -123));
  EXPECT_FALSE(hm.Insert(123, -124));
  ExpectHashMapIntegrity(hm);

  const int* value = hm.Get(123);
  ASSERT_NE(nullptr, value);
  EXPECT_EQ(-123, *value);
}

TEST(ClosedHashMapTest, InsertManyKeysWithCustomHasher) {
  using CustomProber = SimpleQuadraticProber<uint64_t, Uint64Hasher>;

  ClosedHashMap<uint64_t, std::string, CustomProber> hm;
  ExpectEmptyMap(hm, 0);

  std::vector<std::pair<uint64_t, std::string>> entries;
  for (int key = 10, i = 0; key < 1000000; key += ++i) {
    entries.push_back(std::make_pair(key, std::to_string(key)));
  }

  size_t expected_size = 0;
  for (const auto& entry : entries) {
    EXPECT_TRUE(hm.Insert(entry.first, entry.second));
    EXPECT_FALSE(hm.Insert(entry.first, "-1"));
    ++expected_size;

    EXPECT_EQ(expected_size, hm.size());
    EXPECT_LE(expected_size * 2, hm.table_size());
  }
  ExpectHashMapIntegrity(hm);

  for (const auto& entry : entries) {
    const std::string* value = hm.Get(entry.first);
    ASSERT_NE(nullptr, value);
    EXPECT_EQ(entry.second, *value);
  }
}

TEST(ClosedHashMapTest, OperatorBrackets) {
  HashMap<int, int> hm;

  for (int i = 0; i < 5; ++i) {
    const size_t expected_size = i ? 1 : 0;
    EXPECT_EQ(expected_size, hm.size());

    int expected_value = (i + 1) * 10;
    hm[123] = expected_value;
    EXPECT_EQ(1u, hm.size());

    const int* value_ptr = hm.Get(123);
    ASSERT_NE(nullptr, value_ptr);
    EXPECT_EQ(expected_value, *value_ptr);

    EXPECT_EQ(expected_value, hm[123]);
    EXPECT_EQ(1u, hm.size());

    expected_value *= 100;
    hm[123] = expected_value;
    EXPECT_EQ(expected_value, hm[123]);
  }
}

TEST(ClosedHashMapTest, ManualRehash) {
  HashMap<int, int> hm(3);
  const size_t expected_table_size = hm.table_size();

  static const int kKeys[] = {1, 5, 10};
  for (int key : kKeys) {
    EXPECT_TRUE(hm.Insert(key, -key));
  }
  // No rehashing occurred.
  EXPECT_EQ(expected_table_size, hm.table_size());

  for (int i = 1; i <= 2; ++i) {
    for (int key : kKeys) {
      const int* value = hm.Get(key);
      ASSERT_NE(nullptr, value);
      EXPECT_EQ(-key, *value);
    }
    hm.Rehash(100 * i);
    ExpectHashMapIntegrity(hm, 100 * i);
  }
}

}  // namespace url_pattern_index