src/gn/hash_table_base_unittest.cc

// Copyright (c) 2020 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 "hash_table_base.h"

#include "util/test/test.h"

#include <algorithm>
#include <vector>

// This unit-test is also used to illustrate how to use HashTableBase<>
// in a concrete way. Here, each node is a simple pointer to a Int class
// that wraps a simple integer, but also keeps tracks of
// construction/destruction steps in global counters. This is used by the
// test to verify that operations like copies or moves do not miss or
// create allocations/deallocations.
//
// Because the derived table HashTableTest owns all pointer objects, it
// needs to manually create/deallocate them in its destructor, copy/move
// constructors and operators, as well as insert()/erase()/clear() methods.
//
// Finally, iteration support is provided through const_iterator and
// begin(), end() methods, which are enough for range-based for loops.
//

// A simple int wrapper class that can also count creation/destruction.
class Int {
 public:
  explicit Int(int x) : x_(x) { creation_counter++; }

  Int(const Int& other) : x_(other.x_) { creation_counter++; }

  ~Int() { destruction_counter++; }

  int& x() { return x_; }
  const int& x() const { return x_; }

  size_t hash() const { return static_cast<size_t>(x_); }

  static void ResetCounters() {
    creation_counter = 0;
    destruction_counter = 0;
  }

  int x_;

  static size_t creation_counter;
  static size_t destruction_counter;
};

size_t Int::creation_counter;
size_t Int::destruction_counter;

// A HashTableBase<> node type that contains a simple pointer to a Int value.
struct TestHashNode {
  Int* int_ptr;

  bool is_null() const { return !int_ptr; }
  bool is_tombstone() const { return int_ptr == &kTombstone; }
  bool is_valid() const { return !is_null() && !is_tombstone(); }
  size_t hash_value() const { return int_ptr->hash(); }

  static Int kTombstone;
};

// Value is irrelevant since only its address is used.
Int TestHashNode::kTombstone(-1);

// TestHashTable derives a HashTableBase<> instantiation to demonstrate
// full uses of the template. This includes:
//
//  - Storing a pointer in each node, and managing ownership of pointed
//    objects explicitly in the destructor, copy/move constructor and
//    operator, as well as insert() and erase() methods.
//
//  - The internal pointed objects are Int instance, but the TestHashTable
//    API masks that entirely, instead implementing a simple set of integers,
//    including iteration support.
//
//  Note that placing the integers directly in the nodes would be much easier,
//  but would not allow demonstrating how to manage ownership in thedestructor
class TestHashTable : public HashTableBase<TestHashNode> {
 public:
  using BaseType = HashTableBase<TestHashNode>;
  using Node = BaseType::Node;

  static_assert(std::is_same<Node, TestHashNode>::value,
                "HashTableBase<>::Node is not defined properly!");

  BaseType& asBaseType() { return *this; }
  const BaseType& asBaseType() const { return *this; }

  TestHashTable() = default;

  // IMPORTANT NOTE: Because the table contains bare owning pointers, we
  // have to use explicit copy and move constructor/operators for things
  // to work as expected. This is yet another reason why HashTableBase<>
  // should only be used with care (preferably with non-owning pointers).
  //
  TestHashTable(const TestHashTable& other) : BaseType(other) {
    // Only node (i.e. pointers) are copied by the base type.
    for (Node& node : ValidNodesRange()) {
      node.int_ptr = new Int(*node.int_ptr);
    }
  }

  TestHashTable& operator=(const TestHashTable& other) {
    if (this != &other) {
      this->~TestHashTable();
      new (this) TestHashTable(other);
    }
    return *this;
  }

  TestHashTable(TestHashTable&& other) noexcept : BaseType(std::move(other)) {}
  TestHashTable& operator=(TestHashTable&& other) noexcept {
    if (this != &other) {
      this->~TestHashTable();
      new (this) TestHashTable(std::move(other));
    }
    return *this;
  }

  ~TestHashTable() {
    // Discard all valid Int pointers in the hash table.
    for (Node& node : ValidNodesRange())
      delete node.int_ptr;
  }

  // Return true iff the table contains |x|.
  bool contains(int x) const {
    size_t hash = static_cast<size_t>(x);
    Node* node = NodeLookup(
        hash, [&](const Node* node) { return node->int_ptr->x() == x; });
    return node->is_valid();
  }

  // Try to insert |x| in the table. Returns true on success, or false if
  // the value was already in it.
  bool insert(int x) {
    size_t hash = static_cast<size_t>(x);
    Node* node = NodeLookup(
        hash, [&](const Node* node) { return node->int_ptr->x() == x; });
    if (node->is_valid())
      return false;

    bool was_tombstone = node->is_tombstone();
    node->int_ptr = new Int(x);
    UpdateAfterInsert(was_tombstone);
    return true;
  }

  // Try to remove |x| from the table. Return true on success, or false
  // if the value was not in it.
  bool erase(int x) {
    size_t hash = static_cast<size_t>(x);
    Node* node = NodeLookup(
        hash, [&](const Node* node) { return node->int_ptr->x() == x; });
    if (!node->is_valid())
      return false;

    delete node->int_ptr;
    node->int_ptr = &TestHashNode::kTombstone;
    UpdateAfterRemoval();
    return true;
  }

  // Remove all items
  void clear() {
    // Remove all pointed objects, since NodeClear() will not do it.
    for (Node& node : ValidNodesRange())
      delete node.int_ptr;

    NodeClear();
  }

  // Define const_iterator that point to the integer value instead of the node
  // of the Int instance to completely hide these from this class' API.
  struct const_iterator : public BaseType::NodeIterator {
    const int& operator*() const {
      return (this->BaseType::NodeIterator::operator*()).int_ptr->x();
    }
    const int* operator->() const { return &(this->operator*()); }
    const_iterator& operator++() {
      BaseType::NodeIterator::operator++();
      return *this;
    }
    const_iterator operator++(int) {
      const_iterator result = *this;
      BaseType::NodeIterator::operator++();
      return result;
    }
  };

  const_iterator begin() const { return {BaseType::NodeBegin()}; }

  const_iterator end() const { return {BaseType::NodeEnd()}; }
};

TEST(HashTableBaseTest, Construction) {
  Int::ResetCounters();
  {
    TestHashTable table;
    EXPECT_TRUE(table.empty());
    EXPECT_EQ(table.size(), 0u);
    EXPECT_EQ(table.begin(), table.end());
  }

  // No item was created or destroyed.
  EXPECT_EQ(Int::creation_counter, 0u);
  EXPECT_EQ(Int::destruction_counter, 0u);
}

TEST(HashTableBaseTest, InsertionsAndLookups) {
  Int::ResetCounters();
  {
    TestHashTable table;
    table.insert(1);
    table.insert(5);
    table.insert(7);

    EXPECT_FALSE(table.empty());
    EXPECT_EQ(table.size(), 3u);
    EXPECT_NE(table.begin(), table.end());

    EXPECT_EQ(Int::creation_counter, 3u);
    EXPECT_EQ(Int::destruction_counter, 0u);

    EXPECT_FALSE(table.contains(0));
    EXPECT_TRUE(table.contains(1));
    EXPECT_FALSE(table.contains(2));
    EXPECT_FALSE(table.contains(3));
    EXPECT_TRUE(table.contains(5));
    EXPECT_FALSE(table.contains(6));
    EXPECT_TRUE(table.contains(7));
    EXPECT_FALSE(table.contains(8));
  }

  EXPECT_EQ(Int::creation_counter, 3u);
  EXPECT_EQ(Int::destruction_counter, 3u);
}

TEST(HashTableBaseTest, CopyAssignment) {
  Int::ResetCounters();
  {
    TestHashTable table;
    table.insert(1);
    table.insert(5);
    table.insert(7);

    EXPECT_FALSE(table.empty());
    EXPECT_EQ(table.size(), 3u);

    TestHashTable table2;
    EXPECT_TRUE(table2.empty());
    table2 = table;
    EXPECT_FALSE(table2.empty());
    EXPECT_EQ(table2.size(), 3u);
    EXPECT_FALSE(table.empty());
    EXPECT_EQ(table.size(), 3u);

    EXPECT_EQ(Int::creation_counter, 6u);
    EXPECT_EQ(Int::destruction_counter, 0u);

    EXPECT_FALSE(table.contains(0));
    EXPECT_TRUE(table.contains(1));
    EXPECT_FALSE(table.contains(2));
    EXPECT_FALSE(table.contains(3));
    EXPECT_TRUE(table.contains(5));
    EXPECT_FALSE(table.contains(6));
    EXPECT_TRUE(table.contains(7));
    EXPECT_FALSE(table.contains(8));

    EXPECT_FALSE(table2.contains(0));
    EXPECT_TRUE(table2.contains(1));
    EXPECT_FALSE(table2.contains(2));
    EXPECT_FALSE(table2.contains(3));
    EXPECT_TRUE(table2.contains(5));
    EXPECT_FALSE(table2.contains(6));
    EXPECT_TRUE(table2.contains(7));
    EXPECT_FALSE(table2.contains(8));
  }

  EXPECT_EQ(Int::creation_counter, 6u);
  EXPECT_EQ(Int::destruction_counter, 6u);
}

TEST(HashTableBaseTest, MoveAssignment) {
  Int::ResetCounters();
  {
    TestHashTable table;
    table.insert(1);
    table.insert(5);
    table.insert(7);

    EXPECT_FALSE(table.empty());
    EXPECT_EQ(table.size(), 3u);

    TestHashTable table2;
    EXPECT_TRUE(table2.empty());
    table2 = std::move(table);
    EXPECT_FALSE(table2.empty());
    EXPECT_EQ(table2.size(), 3u);
    EXPECT_TRUE(table.empty());
    EXPECT_EQ(table.size(), 0u);

    EXPECT_EQ(Int::creation_counter, 3u);
    EXPECT_EQ(Int::destruction_counter, 0u);

    EXPECT_FALSE(table2.contains(0));
    EXPECT_TRUE(table2.contains(1));
    EXPECT_FALSE(table2.contains(2));
    EXPECT_FALSE(table2.contains(3));
    EXPECT_TRUE(table2.contains(5));
    EXPECT_FALSE(table2.contains(6));
    EXPECT_TRUE(table2.contains(7));
    EXPECT_FALSE(table2.contains(8));
  }

  EXPECT_EQ(Int::creation_counter, 3u);
  EXPECT_EQ(Int::destruction_counter, 3u);
}

TEST(HashTableBaseTest, Clear) {
  Int::ResetCounters();
  {
    TestHashTable table;
    table.insert(1);
    table.insert(5);
    table.insert(7);

    EXPECT_FALSE(table.empty());
    EXPECT_EQ(table.size(), 3u);

    table.clear();
    EXPECT_TRUE(table.empty());

    EXPECT_EQ(Int::creation_counter, 3u);
    EXPECT_EQ(Int::destruction_counter, 3u);
  }

  EXPECT_EQ(Int::creation_counter, 3u);
  EXPECT_EQ(Int::destruction_counter, 3u);
}

TEST(HashTableBaseTest, Iteration) {
  TestHashTable table;
  table.insert(1);
  table.insert(5);
  table.insert(7);

  EXPECT_FALSE(table.empty());
  EXPECT_EQ(table.size(), 3u);

  std::vector<int> values;

  for (const int& x : table)
    values.push_back(x);

  std::sort(values.begin(), values.end());
  EXPECT_EQ(values.size(), 3u);
  EXPECT_EQ(values[0], 1);
  EXPECT_EQ(values[1], 5);
  EXPECT_EQ(values[2], 7);
}

TEST(HashTableBaseTest, Erase) {
  TestHashTable table;
  // Use sequention hashes to test that tombstone_count_ grows the hash table.
  for (int i = 0; i < 16; ++i) {
    table.insert(i);
    table.erase(i);
    EXPECT_EQ(table.size(), 0u);
  }
}