/**
 *   Copyright 2011-2015 Quickstep Technologies LLC.
 *   Copyright 2015-2016 Pivotal Software, Inc.
 *
 *   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 QUICKSTEP_STORAGE_TESTS_HASHTABLE_UNITTEST_COMMON_HPP_
#define QUICKSTEP_STORAGE_TESTS_HASHTABLE_UNITTEST_COMMON_HPP_

#include <algorithm>
#include <atomic>
#include <bitset>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <memory>
#include <sstream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include "gtest/gtest.h"

#include "catalog/CatalogTypedefs.hpp"
#include "storage/HashTable.hpp"
#include "storage/StorageBlockInfo.hpp"
#include "storage/StorageConstants.hpp"
#include "storage/StorageManager.hpp"
#include "threading/Thread.hpp"
#include "types/Type.hpp"
#include "types/TypeFactory.hpp"
#include "types/TypeID.hpp"
#include "types/TypedValue.hpp"
#include "types/containers/ColumnVector.hpp"
#include "types/containers/ColumnVectorsValueAccessor.hpp"
#include "utility/Macros.hpp"
#include "utility/ScopedBuffer.hpp"

// NetBSD's libc has atoll, but it doesn't show up in the std namespace for
// C++.
#ifndef __NetBSD__
using std::atoll;
#endif

namespace quickstep {

constexpr std::int64_t kNumSampleKeys = 1024;
// Not exactly aligned to word size so we can make sure there are no alignment
// problems for arbitrary-length types.
constexpr std::size_t kStringLengthParam = 18;
constexpr std::size_t kNumConcurrentThreads = 8;

class TestHashPayload {
 public:
  explicit TestHashPayload(const int payload)
      : internal_int_(payload) {
  }

  TestHashPayload(const TestHashPayload &orig)
      : internal_int_(orig.internal_int_.load()) {
  }

  std::atomic<int>* accessInternalInt() {
    return &internal_int_;
  }

  int loadInternalInt() const {
    return internal_int_.load(std::memory_order_relaxed);
  }

 private:
  std::atomic<int> internal_int_;
};

class NonTriviallyDestructibleTestHashPayload {
 public:
  NonTriviallyDestructibleTestHashPayload()
      : destruct_count_(nullptr) {
  }

  explicit NonTriviallyDestructibleTestHashPayload(std::atomic<int> *destruct_count)
      : destruct_count_(destruct_count) {
  }

  void clearDestructCountPtr() {
    destruct_count_ = nullptr;
  }

  ~NonTriviallyDestructibleTestHashPayload() {
    if (destruct_count_ != nullptr) {
      destruct_count_->fetch_add(1, std::memory_order_relaxed);
    }
  }

 private:
  std::atomic<int> *destruct_count_;
};

// Insertion functor that creates a TestHashPayload containing the tuple_id for
// each tuple visited in a ValueAccessor.
class TestInserter {
 public:
  template <typename ValueAccessorT>
  TestHashPayload operator()(const ValueAccessorT &accessor) {
    return TestHashPayload(accessor.getCurrentPosition());
  }
};

// Simple upserter that just atomically increments a TestHashPayload's value.
class TestUpserter {
 public:
  TestUpserter()
      : call_count_(0) {
  }

  void operator()(TestHashPayload *value) {
    ++call_count_;
    value->accessInternalInt()->fetch_add(1, std::memory_order_relaxed);
  }

  template <typename ValueAccessorT>
  void operator()(const ValueAccessorT &accessor, TestHashPayload *value) {
    ++call_count_;
    value->accessInternalInt()->fetch_add(1, std::memory_order_relaxed);
  }

  std::size_t call_count() const {
    return call_count_;
  }

 private:
  std::size_t call_count_;
};

// Visitor to test HashTable::forEach() and HashTable::forEachCompositeKey().
// For each key-value pair, extracts and remembers the key's original seed and
// the value stored in the TestHashPayload which it maps to.
class TestVisitor {
 public:
  TestVisitor()
      : test_key_type_id_(kNumTypeIDs) {
  }

  explicit TestVisitor(const TypeID test_key_type_id)
      : test_key_type_id_(test_key_type_id) {
  }

  void operator()(const TypedValue &key, const TestHashPayload &payload) {
    internal_map_.emplace(extractScalarSeed(key), payload.loadInternalInt());
  }

  void operator()(const std::vector<TypedValue> &key, const TestHashPayload &payload) {
    internal_map_.emplace(extractCompositeSeed(key), payload.loadInternalInt());
  }

  template <typename ValueAccessorT>
  void operator()(const ValueAccessorT &accessor, const TestHashPayload &payload) {
    std::vector<TypedValue> composite_key;
    composite_key.emplace_back(accessor.getTypedValue(0));
    composite_key.emplace_back(accessor.getTypedValue(1));
    composite_key.emplace_back(accessor.getTypedValue(2));

    internal_map_.emplace(extractCompositeSeed(composite_key),
                          payload.loadInternalInt());
  }

  const std::unordered_multimap<std::int64_t, int>& internal_map() const {
    return internal_map_;
  }

 private:
  std::int64_t extractScalarSeed(const TypedValue &key) {
    switch (test_key_type_id_) {
      case TypeID::kLong: {
        EXPECT_EQ(TypeID::kLong, key.getTypeID());
        return key.getLiteral<std::int64_t>();
      }
      case TypeID::kChar: {
        EXPECT_EQ(TypeID::kChar, key.getTypeID());
        return atoll(static_cast<const char*>(key.getDataPtr()));
      }
      case TypeID::kVarChar: {
        EXPECT_EQ(TypeID::kVarChar, key.getTypeID());
        return atoll(static_cast<const char*>(key.getDataPtr()));
      }
      default:
        FATAL_ERROR("TypeID not covered\n");
    }
  }

  std::int64_t extractCompositeSeed(const std::vector<TypedValue> &key) {
    EXPECT_EQ(3u, key.size());

    EXPECT_EQ(TypeID::kLong, key[0].getTypeID());
    const std::int64_t seed = key[0].getLiteral<std::int64_t>();

    EXPECT_EQ(TypeID::kChar, key[1].getTypeID());
    EXPECT_EQ(seed, atoll(static_cast<const char*>(key[1].getDataPtr())));

    EXPECT_EQ(TypeID::kVarChar, key[2].getTypeID());
    EXPECT_EQ(seed, atoll(static_cast<const char*>(key[2].getDataPtr())));

    return seed;
  }

  const TypeID test_key_type_id_;
  std::unordered_multimap<std::int64_t, int> internal_map_;
};

template <typename HashTableImpl>
class HashTableTest : public ::testing::Test {
 protected:
  class InserterThread : public Thread {
   public:
    InserterThread(const int my_id,
                   const std::vector<TypedValue> &keys,
                   HashTableImpl *hash_table)
        : my_id_(my_id),
          keys_(keys),
          hash_table_(hash_table),
          insert_succeeded_(keys.size(), false) {
      // Randomize insert order.
      for (std::vector<TypedValue>::size_type i = 0;
           i < keys_.size();
           ++i) {
        insert_order_.push_back(i);
      }
      std::random_shuffle(insert_order_.begin(), insert_order_.end());
    }

    int getID() const {
      return my_id_;
    }

    const std::vector<bool>& insert_succeeded() const {
      return insert_succeeded_;
    }

   protected:
    void run() override {
      for (const std::vector<TypedValue>::size_type i : insert_order_) {
        TestHashPayload value(i * kNumSampleKeys + my_id_);
        insert_succeeded_[i] = hash_table_->put(keys_[i], value) == HashTablePutResult::kOK;
      }
    }

   private:
    const int my_id_;
    const std::vector<TypedValue> &keys_;
    HashTableImpl *hash_table_;
    std::vector<std::vector<TypedValue>::size_type> insert_order_;
    std::vector<bool> insert_succeeded_;
  };

  class CompositeKeyInserterThread : public Thread {
   public:
    CompositeKeyInserterThread(const int my_id,
                               const std::vector<std::vector<TypedValue>> &keys,
                               HashTableImpl *hash_table)
        : my_id_(my_id),
          keys_(keys),
          hash_table_(hash_table),
          insert_succeeded_(keys.size(), false) {
      // Randomize insert order.
      for (std::vector<TypedValue>::size_type i = 0;
           i < keys_.size();
           ++i) {
        insert_order_.push_back(i);
      }
      std::random_shuffle(insert_order_.begin(), insert_order_.end());
    }

    int getID() const {
      return my_id_;
    }

    const std::vector<bool>& insert_succeeded() const {
      return insert_succeeded_;
    }

   protected:
    void run() override {
      for (const std::vector<std::vector<TypedValue>>::size_type i : insert_order_) {
        TestHashPayload value(i * kNumSampleKeys + my_id_);
        insert_succeeded_[i]
            = hash_table_->putCompositeKey(keys_[i], value) == HashTablePutResult::kOK;
      }
    }

   private:
    const int my_id_;
    const std::vector<std::vector<TypedValue>> &keys_;
    HashTableImpl *hash_table_;
    std::vector<std::vector<std::vector<TypedValue>>::size_type> insert_order_;
    std::vector<bool> insert_succeeded_;
  };

  virtual void SetUp() {
    storage_manager_.reset(new StorageManager("./test_data/"));
  }

  static std::vector<const Type*> SetupScalarKeyType(const TypeID type_id) {
    std::vector<const Type*> key_type_vec;
    switch (type_id) {
      case kLong:
        key_type_vec.push_back(&TypeFactory::GetType(kLong, false));
        break;
      case kChar:
        key_type_vec.push_back(&TypeFactory::GetType(kChar, kStringLengthParam, false));
        break;
      case kVarChar:
        key_type_vec.push_back(&TypeFactory::GetType(kVarChar, kStringLengthParam, false));
        break;
      default:
        FATAL_ERROR("TypeID not covered\n");
    }
    return key_type_vec;
  }

  static std::vector<const Type*> SetupCompositeKeyType() {
    std::vector<const Type*> key_type_vec;
    key_type_vec.push_back(&TypeFactory::GetType(kLong, false));
    key_type_vec.push_back(&TypeFactory::GetType(kChar, kStringLengthParam, false));
    key_type_vec.push_back(&TypeFactory::GetType(kVarChar, kStringLengthParam, false));
    return key_type_vec;
  }

  void createResizableHashTable(const std::vector<const Type*> &key_types,
                                const std::size_t num_entries) {
    hash_table_.reset(new HashTableImpl(key_types,
                                        num_entries,
                                        storage_manager_.get()));
  }

  void createNonresizableHashTable(const std::vector<const Type*> &key_types,
                                   const std::size_t buffer_size,
                                   const std::size_t offset_in_buffer) {
    assert(offset_in_buffer < buffer_size);
    memory_buffer_.reset(new ScopedBuffer(buffer_size, kCacheLineBytes));
    hash_table_.reset(new HashTableImpl(
        key_types,
        static_cast<char*>(memory_buffer_->get()) + offset_in_buffer,
        buffer_size - offset_in_buffer,
        true,
        false));
  }

  void createHashTableSimple(const std::vector<const Type*> &key_types,
                             const std::size_t num_entries) {
    if (HashTableImpl::template_resizable) {
      createResizableHashTable(key_types, num_entries);
    } else {
      // Allocate space for 'num_entries' generously.
      std::size_t key_size = 0;
      for (const Type *type : key_types) {
        key_size += type->maximumByteLength();
      }
      createNonresizableHashTable(
          key_types,
          256 + num_entries * 8 * (key_size + sizeof(typename HashTableImpl::value_type)),
          0);
    }
  }

  TypedValue createLongKey(const std::int64_t seed) const {
    return TypedValue(seed);
  }

  TypedValue createCharKey(const std::int64_t seed) {
    std::ostringstream stream;
    stream << seed;
    external_strings_.emplace_back(stream.str().size() + 1);
    std::memcpy(external_strings_.back().get(),
                stream.str().c_str(),
                stream.str().size() + 1);
    return TypeFactory::GetType(kChar, kStringLengthParam, false).makeValue(external_strings_.back().get(),
                                                                     stream.str().size() + 1);
  }

  TypedValue createVarCharKey(const std::int64_t seed) {
    std::ostringstream stream;
    stream << seed;
    external_strings_.emplace_back(stream.str().size() + 1);
    std::memcpy(external_strings_.back().get(),
                stream.str().c_str(),
                stream.str().size() + 1);
    return TypeFactory::GetType(kVarChar, kStringLengthParam, false).makeValue(external_strings_.back().get(),
                                                                        stream.str().size() + 1);
  }

  TypedValue createScalarKey(const TypeID test_key_type_id,
                             const std::int64_t seed) {
    switch (test_key_type_id) {
      case TypeID::kLong:
        return createLongKey(seed);
      case TypeID::kChar:
        return createCharKey(seed);
      case TypeID::kVarChar:
        return createVarCharKey(seed);
      default:
        FATAL_ERROR("TypeID not covered\n");
    }
  }

  std::vector<TypedValue> createCompositeKey(const std::int64_t seed) {
    std::vector<TypedValue> key;
    key.emplace_back(createLongKey(seed));
    key.emplace_back(createCharKey(seed));
    key.emplace_back(createVarCharKey(seed));
    return key;
  }

  ColumnVectorsValueAccessor* createSampleValueAccessor() {
    // Create a ColumnVectorsValueAccessor to simulate a table with 3 columns:
    // Long, Char, & VarChar.
    ColumnVectorsValueAccessor *accessor = new ColumnVectorsValueAccessor();

    NativeColumnVector *long_column
        = new NativeColumnVector(TypeFactory::GetType(kLong, true),
                                 kNumSampleKeys + 1);
    NativeColumnVector *char_column
        = new NativeColumnVector(TypeFactory::GetType(kChar, kStringLengthParam, true),
                                 kNumSampleKeys + 1);
    IndirectColumnVector *varchar_column
        = new IndirectColumnVector(TypeFactory::GetType(kVarChar, kStringLengthParam, true),
                                   kNumSampleKeys + 1);

    for (std::int64_t i = 0; i < kNumSampleKeys / 2; ++i) {
      long_column->appendTypedValue(createScalarKey(kLong, i * (i + 1)));
      char_column->appendTypedValue(createScalarKey(kChar, i * (i + 1)));
      varchar_column->appendTypedValue(createScalarKey(kVarChar, i * (i + 1)));
    }

    // Put some nulls in the middle of each column.
    long_column->appendTypedValue(TypedValue(kLong));
    char_column->appendTypedValue(TypedValue(kChar));
    varchar_column->appendTypedValue(TypedValue(kVarChar));

    // Finish filling the columns.
    for (std::int64_t i = kNumSampleKeys / 2;
         i < kNumSampleKeys;
         ++i) {
      long_column->appendTypedValue(createScalarKey(kLong, i * (i + 1)));
      char_column->appendTypedValue(createScalarKey(kChar, i * (i + 1)));
      varchar_column->appendTypedValue(createScalarKey(kVarChar, i * (i + 1)));
    }

    accessor->addColumn(long_column);
    accessor->addColumn(char_column);
    accessor->addColumn(varchar_column);

    return accessor;
  }

  void runScalarKeyPutAndGetTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys);

    // Insert some key/value pairs.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      TestHashPayload value(i);
      EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, value));
    }

    // Read them back out.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      std::vector<TypedValue> key_vec(1, key);

      // Use getSingle() if duplicate keys are not allowed.
      if (!HashTableImpl::template_allow_duplicate_keys) {
        const TestHashPayload *value = hash_table_->getSingle(key);
        ASSERT_NE(nullptr, value);
        EXPECT_EQ(i, value->loadInternalInt());

        value = hash_table_->getSingleCompositeKey(key_vec);
        ASSERT_NE(nullptr, value);
        EXPECT_EQ(i, value->loadInternalInt());
      }

      // Test getAll() in all cases.
      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(i, matches.front()->loadInternalInt());

      matches.clear();
      hash_table_->getAllCompositeKey(key_vec, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(i, matches.front()->loadInternalInt());
    }

    // Check a nonexistent key.
    TypedValue nonexistent_key(createScalarKey(test_key_type_id,
                                               kNumSampleKeys * kNumSampleKeys * kNumSampleKeys));
    if (!HashTableImpl::template_allow_duplicate_keys) {
      const TestHashPayload *nonexistent_value = hash_table_->getSingle(nonexistent_key);
      EXPECT_EQ(nullptr, nonexistent_value);
    }
    std::vector<const TestHashPayload*> nonexistent_matches;
    hash_table_->getAll(nonexistent_key, &nonexistent_matches);
    EXPECT_TRUE(nonexistent_matches.empty());

    // Also test forEach().
    TestVisitor visitor(test_key_type_id);
    EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys),
              hash_table_->forEach(&visitor));
    EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys),
              visitor.internal_map().size());
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      ASSERT_EQ(1u, visitor.internal_map().count(i * (i + 1)));
      EXPECT_EQ(i, visitor.internal_map().find(i * (i + 1))->second);
    }
  }

  void runDuplicateScalarKeysPutAndGetTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys * 2);

    // Attempt to insert 1-3 values for each distinct key.
    std::size_t total_inserted = 0;
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      TestHashPayload first_value(i * kNumSampleKeys);
      EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, first_value));
      ++total_inserted;

      for (int extra_value_num = 1;
           extra_value_num <= i % 3;
           ++extra_value_num) {
        TestHashPayload additional_value(i * kNumSampleKeys + extra_value_num);
        if (HashTableImpl::template_allow_duplicate_keys) {
          EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, additional_value));
          ++total_inserted;
        } else {
          EXPECT_EQ(HashTablePutResult::kDuplicateKey, hash_table_->put(key, additional_value));
        }
      }
    }

    // Read them back out.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      std::vector<TypedValue> key_vec(1, key);

      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      if (HashTableImpl::template_allow_duplicate_keys) {
        EXPECT_EQ(static_cast<std::size_t>((i % 3) + 1), matches.size());
        std::bitset<3> value_found;
        for (const TestHashPayload *match : matches) {
          ASSERT_LE(match->loadInternalInt() - i * kNumSampleKeys, 3);
          EXPECT_FALSE(value_found[match->loadInternalInt() - i * kNumSampleKeys]);
          value_found.set(match->loadInternalInt() - i * kNumSampleKeys, true);
        }
        EXPECT_TRUE(value_found[0]);
        if (i % 3 > 0) {
          EXPECT_TRUE(value_found[1]);
        } else {
          EXPECT_FALSE(value_found[1]);
        }
        if (i % 3 > 1) {
          EXPECT_TRUE(value_found[2]);
        } else {
          EXPECT_FALSE(value_found[2]);
        }
      } else {
        ASSERT_EQ(1u, matches.size());
        EXPECT_EQ(i * kNumSampleKeys,
                  matches.front()->loadInternalInt());
      }
    }

    // Check a nonexistent key.
    TypedValue nonexistent_key(createScalarKey(test_key_type_id,
                                               kNumSampleKeys * kNumSampleKeys * kNumSampleKeys));
    std::vector<const TestHashPayload*> nonexistent_matches;
    hash_table_->getAll(nonexistent_key, &nonexistent_matches);
    EXPECT_TRUE(nonexistent_matches.empty());

    // Also test forEach().
    TestVisitor visitor(test_key_type_id);
    EXPECT_EQ(total_inserted, hash_table_->forEach(&visitor));
    EXPECT_EQ(total_inserted, visitor.internal_map().size());
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      if (HashTableImpl::template_allow_duplicate_keys) {
        ASSERT_EQ(static_cast<std::size_t>(1 + (i % 3)),
                  visitor.internal_map().count(i * (i + 1)));
        std::bitset<3> value_found;
        std::pair<std::unordered_multimap<std::int64_t, int>::const_iterator,
                  std::unordered_multimap<std::int64_t, int>::const_iterator> match_range
            = visitor.internal_map().equal_range(i * (i + 1));
        for (std::unordered_multimap<std::int64_t, int>::const_iterator match_it = match_range.first;
             match_it != match_range.second;
             ++match_it) {
          ASSERT_LE(match_it->second - i * kNumSampleKeys, 3);
          EXPECT_FALSE(value_found[match_it->second - i * kNumSampleKeys]);
          value_found.set(match_it->second - i * kNumSampleKeys, true);
        }

        EXPECT_TRUE(value_found[0]);
        if (i % 3 > 0) {
          EXPECT_TRUE(value_found[1]);
        } else {
          EXPECT_FALSE(value_found[1]);
        }
        if (i % 3 > 1) {
          EXPECT_TRUE(value_found[2]);
        } else {
          EXPECT_FALSE(value_found[2]);
        }
      } else {
        ASSERT_EQ(1u, visitor.internal_map().count(i * (i + 1)));
        EXPECT_EQ(i * kNumSampleKeys,
                  visitor.internal_map().find(i * (i + 1))->second);
      }
    }
  }

  void runScalarKeyPutAndGetFromValueAccessorTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys);

    std::unique_ptr<ColumnVectorsValueAccessor> accessor(createSampleValueAccessor());

    attribute_id key_attr_id;
    switch (test_key_type_id) {
      case kLong:
        key_attr_id = 0;
        break;
      case kChar:
        key_attr_id = 1;
        break;
      case kVarChar:
        key_attr_id = 2;
        break;
      default:
        FATAL_ERROR("TypeID not covered\n");
    }

    // Vectorized insert, skipping over null keys.
    TestInserter inserter;
    EXPECT_EQ(HashTablePutResult::kOK, hash_table_->putValueAccessor(accessor.get(),
                                                                     key_attr_id,
                                                                     true,
                                                                     &inserter));

    // Read values back out.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(i + (i >= kNumSampleKeys / 2),
                matches.front()->loadInternalInt());
    }

    // Also read the values out using the vectorized interface.
    accessor->beginIteration();
    TestVisitor visitor;
    hash_table_->getAllFromValueAccessor(accessor.get(),
                                         key_attr_id,
                                         true,
                                         &visitor);
    EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys),
              visitor.internal_map().size());
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      ASSERT_EQ(1u, visitor.internal_map().count(i * (i + 1)));
      EXPECT_EQ(i + (i >= kNumSampleKeys / 2),
                visitor.internal_map().find(i * (i + 1))->second);
    }
  }

  void runScalarKeyClearTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys);

    // Insert some key/value pairs.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      TestHashPayload value(i);
      EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, value));
    }

    // Clear out the HashTable.
    hash_table_->clear();

    // Make sure entries are cleared out.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));

      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      EXPECT_TRUE(matches.empty());
    }

    // Also make sure that forEach() sees an empty HashTable.
    TestVisitor visitor(test_key_type_id);
    EXPECT_EQ(0u, hash_table_->forEach(&visitor));
    EXPECT_EQ(0u, visitor.internal_map().size());
  }

  void runScalarKeyResizeTest(const TypeID test_key_type_id) {
    // Try to trigger a resize by substantially under-provisioning storage.
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createResizableHashTable(key_types, 1);

    const block_id original_blob_id = hash_table_->getBlobId();

    // Insert at least enough values to exhaust the space in the smallest
    // possible StorageBlob.
    for (std::int64_t i = 0;
         i < static_cast<std::int64_t>(
                 kSlotSizeBytes / (sizeof(std::size_t) + sizeof(TestHashPayload)));
         ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      TestHashPayload value(i);
      EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, value));
    }

    // If a resize occured, the block ID should be different now.
    EXPECT_NE(original_blob_id, hash_table_->getBlobId());

    // Read out the values.
    for (std::int64_t i = 0; i < 2 * kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));

      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(i, matches.front()->loadInternalInt());
    }
  }

  void runScalarKeyExhaustSpaceTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);

    // Under-provision storage and insert entries until we run out of space.
    const std::size_t buffer_size
        = kNumSampleKeys * (key_types.front()->maximumByteLength() + sizeof(typename HashTableImpl::value_type))
          / 4;
    createNonresizableHashTable(key_types, buffer_size, 0);

    std::int64_t i;
    for (i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      TestHashPayload value(i);
      HashTablePutResult result = hash_table_->put(key, value);
      if (result != HashTablePutResult::kOK) {
        EXPECT_EQ(HashTablePutResult::kOutOfSpace, result);
        break;
      }
    }

    EXPECT_LT(i, kNumSampleKeys);

    // Check the entries that we were able to insert.
    for (std::int64_t j = 0; j < i; ++j) {
      TypedValue key(createScalarKey(test_key_type_id, j * (j + 1)));

      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(j, matches.front()->loadInternalInt());
    }

    // Check that the entry we failed to insert is not present.
    TypedValue failed_key(createScalarKey(test_key_type_id, i * (i + 1)));
    std::vector<const TestHashPayload*> failed_matches;
    hash_table_->getAll(failed_key, &failed_matches);
    EXPECT_TRUE(failed_matches.empty());
  }

  void runScalarKeyUpsertTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys);

    // Upsert some key/value pairs.
    TestHashPayload initial_value(42);
    TestUpserter upserter;
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      EXPECT_TRUE(hash_table_->upsert(key, initial_value, &upserter));
    }
    EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys), upserter.call_count());

    // Visit every other value a second time.
    for (std::int64_t i = 0; i < kNumSampleKeys; i += 2) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      EXPECT_TRUE(hash_table_->upsert(key, initial_value, &upserter));
    }
    EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys + (kNumSampleKeys / 2)),
              upserter.call_count());

    // Read out the values and check that they are as expected (initial value
    // for each was set to 42, and each call to TestUpserter increments by 1).
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));

      const TestHashPayload *value = hash_table_->getSingle(key);
      ASSERT_NE(nullptr, value);
      EXPECT_EQ(44 - (i % 2), value->loadInternalInt());
    }
  }

  void runScalarKeyUpsertValueAccessorTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys);

    std::unique_ptr<ColumnVectorsValueAccessor> accessor(createSampleValueAccessor());

    attribute_id key_attr_id;
    switch (test_key_type_id) {
      case kLong:
        key_attr_id = 0;
        break;
      case kChar:
        key_attr_id = 1;
        break;
      case kVarChar:
        key_attr_id = 2;
        break;
      default:
        FATAL_ERROR("TypeID not covered\n");
    }

    // Vectorized upsert, skipping over null keys.
    TestHashPayload initial_value(42);
    TestUpserter upserter;
    EXPECT_TRUE(hash_table_->upsertValueAccessor(accessor.get(),
                                                 key_attr_id,
                                                 true,
                                                 initial_value,
                                                 &upserter));
    EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys), upserter.call_count());

    // Read values out and check that they are as expected.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(43, matches.front()->loadInternalInt());
    }
  }

  void runScalarKeySerializationTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    // Set up a shared memory buffer which will hold both the external keys
    // and the hash table.
    const std::size_t buffer_size
        = kNumSampleKeys * key_types.front()->maximumByteLength()
          + 8 * kNumSampleKeys * (key_types.front()->maximumByteLength() + sizeof(typename HashTableImpl::value_type));
    createNonresizableHashTable(key_types,
                                buffer_size,
                                kNumSampleKeys * key_types.front()->maximumByteLength());

    // Create external keys in the first part of the buffer.
    char *key_ptr = static_cast<char*>(memory_buffer_->get());
    std::vector<std::size_t> key_sizes;
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      key.copyInto(key_ptr);
      key_sizes.push_back(key.getDataSize());
      key_ptr += key.getDataSize();
    }

    // Now actually insert.
    key_ptr = static_cast<char*>(memory_buffer_->get());
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(key_types.front()->makeValue(key_ptr, key_sizes[i]));
      TestHashPayload value(i);
      EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, value));
      key_ptr += key_sizes[i];
    }

    // Destroy the HashTable object and copy the underlying memory.
    hash_table_.reset(nullptr);
    ScopedBuffer moved_buffer(buffer_size, kCacheLineBytes);
    std::memcpy(moved_buffer.get(), memory_buffer_->get(), buffer_size);
    memory_buffer_.reset(nullptr);

    // Recreate the HashTable at the new location.
    hash_table_.reset(new HashTableImpl(
        key_types,
        static_cast<char*>(moved_buffer.get()) + kNumSampleKeys * key_types.front()->maximumByteLength(),
        buffer_size - kNumSampleKeys * key_types.front()->maximumByteLength(),
        false,
        false));

    // If duplicate keys are not allowed, make sure we can't insert a
    // duplicate.
    if (!HashTableImpl::template_allow_duplicate_keys) {
      TypedValue key(key_types.front()->makeValue(moved_buffer.get(), key_sizes[0]));
      TestHashPayload value(123);
      EXPECT_EQ(HashTablePutResult::kDuplicateKey, hash_table_->put(key, value));
    }

    // Read the inserted values back out.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));

      // Test getAll() in all cases.
      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(i, matches.front()->loadInternalInt());
    }

    // Check a nonexistent key.
    TypedValue nonexistent_key(createScalarKey(test_key_type_id,
                                               kNumSampleKeys * kNumSampleKeys * kNumSampleKeys));
    std::vector<const TestHashPayload*> nonexistent_matches;
    hash_table_->getAll(nonexistent_key, &nonexistent_matches);
    EXPECT_TRUE(nonexistent_matches.empty());
  }

  void runScalarKeyThreadedPutTest(const TypeID test_key_type_id,
                                   const bool test_resize) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    if (HashTableImpl::template_allow_duplicate_keys) {
      if (test_resize) {
        createHashTableSimple(key_types, 1);
      } else {
        createHashTableSimple(key_types, kNumSampleKeys * kNumConcurrentThreads);
      }
    } else {
      if (test_resize) {
        createHashTableSimple(key_types, 1);
      } else {
        createHashTableSimple(key_types, kNumSampleKeys);
      }
    }

    // If testing multithreaded resize, record the original ID of the
    // underlying blob.
    block_id original_blob_id = 0;
    if (test_resize) {
      original_blob_id = hash_table_->getBlobId();
    }

    // Setup keys ahead of time.
    const std::size_t num_keys = test_resize
        ? (kSlotSizeBytes / (sizeof(std::size_t) + sizeof(TestHashPayload)))
            / (HashTableImpl::template_allow_duplicate_keys ? kNumConcurrentThreads : 1)
        : kNumSampleKeys;
    std::vector<TypedValue> keys;
    for (std::int64_t i = 0; i < static_cast<std::int64_t>(num_keys); ++i) {
      keys.emplace_back(createScalarKey(test_key_type_id, i * (i + 1)));
    }

    // Setup threads.
    std::vector<std::unique_ptr<InserterThread>> threads;
    for (std::size_t thread_num = 0; thread_num < kNumConcurrentThreads; ++thread_num) {
      threads.emplace_back(new InserterThread(thread_num, keys, hash_table_.get()));
    }

    // Run threads and join them.
    for (std::unique_ptr<InserterThread> &thread : threads) {
      thread->start();
    }
    for (std::unique_ptr<InserterThread> &thread : threads) {
      thread->join();
    }

    // If a resize occured, the block ID should be different now.
    if (test_resize) {
      EXPECT_NE(original_blob_id, hash_table_->getBlobId());
    }

    // Check that everything was inserted properly.
    for (std::int64_t i = 0; i < static_cast<std::int64_t>(num_keys); ++i) {
      std::size_t successful_inserts = 0;
      for (const std::unique_ptr<InserterThread> &thread : threads) {
        if (thread->insert_succeeded()[i]) {
          ++successful_inserts;
        }
      }
      if (HashTableImpl::template_allow_duplicate_keys) {
        EXPECT_EQ(kNumConcurrentThreads, successful_inserts);
      } else {
        EXPECT_EQ(1u, successful_inserts);
      }

      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));

      std::vector<const TestHashPayload*> matches;
      hash_table_->getAll(key, &matches);
      if (HashTableImpl::template_allow_duplicate_keys) {
        EXPECT_EQ(kNumConcurrentThreads, matches.size());
        std::vector<bool> found_value(kNumConcurrentThreads, false);
        for (const TestHashPayload *payload : matches) {
          const int payload_value = payload->loadInternalInt();
          ASSERT_GE(payload_value, i * kNumSampleKeys);
          ASSERT_LT(payload_value,
                    i * kNumSampleKeys + static_cast<std::int64_t>(kNumConcurrentThreads));
          EXPECT_FALSE(found_value[payload_value - i * kNumSampleKeys]);
          found_value[payload_value - i * kNumSampleKeys] = true;
        }
        for (const bool found : found_value) {
          EXPECT_TRUE(found);
        }
      } else {
        ASSERT_EQ(1u, matches.size());
        for (const std::unique_ptr<InserterThread> &thread : threads) {
          if (thread->insert_succeeded()[i]) {
            EXPECT_EQ(i * kNumSampleKeys + thread->getID(),
                      matches.front()->loadInternalInt());
          }
        }
      }
    }
  }

  void runCompositeKeyThreadedPutTest(const bool test_resize) {
    std::vector<const Type*> key_types = SetupCompositeKeyType();
    if (HashTableImpl::template_allow_duplicate_keys) {
      if (test_resize) {
        createHashTableSimple(key_types, 1);
      } else {
        createHashTableSimple(key_types, kNumSampleKeys * kNumConcurrentThreads);
      }
    } else {
      if (test_resize) {
        createHashTableSimple(key_types, 1);
      } else {
        createHashTableSimple(key_types, kNumSampleKeys);
      }
    }

    // If testing multithreaded resize, record the original ID of the
    // underlying blob.
    block_id original_blob_id = 0;
    if (test_resize) {
      original_blob_id = hash_table_->getBlobId();
    }

    // Setup keys ahead of time.
    const std::size_t num_keys = test_resize
        ? (kSlotSizeBytes / (sizeof(std::size_t) + sizeof(TestHashPayload)))
            / (HashTableImpl::template_allow_duplicate_keys ? kNumConcurrentThreads : 1)
        : kNumSampleKeys;
    std::vector<std::vector<TypedValue>> keys;
    for (std::int64_t i = 0; i < static_cast<std::int64_t>(num_keys); ++i) {
      keys.emplace_back(createCompositeKey(i * (i + 1)));
    }

    // Setup threads.
    std::vector<std::unique_ptr<CompositeKeyInserterThread>> threads;
    for (std::size_t thread_num = 0; thread_num < kNumConcurrentThreads; ++thread_num) {
      threads.emplace_back(new CompositeKeyInserterThread(thread_num, keys, hash_table_.get()));
    }

    // Run threads and join them.
    for (std::unique_ptr<CompositeKeyInserterThread> &thread : threads) {
      thread->start();
    }
    for (std::unique_ptr<CompositeKeyInserterThread> &thread : threads) {
      thread->join();
    }

    // If a resize occured, the block ID should be different now.
    if (test_resize) {
      EXPECT_NE(original_blob_id, hash_table_->getBlobId());
    }

    // Check that everything was inserted properly.
    for (std::int64_t i = 0; i < static_cast<std::int64_t>(num_keys); ++i) {
      std::size_t successful_inserts = 0;
      for (const std::unique_ptr<CompositeKeyInserterThread> &thread : threads) {
        if (thread->insert_succeeded()[i]) {
          ++successful_inserts;
        }
      }
      if (HashTableImpl::template_allow_duplicate_keys) {
        EXPECT_EQ(kNumConcurrentThreads, successful_inserts);
      } else {
        EXPECT_EQ(1u, successful_inserts);
      }

      std::vector<TypedValue> key(createCompositeKey(i * (i + 1)));

      std::vector<const TestHashPayload*> matches;
      hash_table_->getAllCompositeKey(key, &matches);
      if (HashTableImpl::template_allow_duplicate_keys) {
        EXPECT_EQ(kNumConcurrentThreads, matches.size());
        std::vector<bool> found_value(kNumConcurrentThreads, false);
        for (const TestHashPayload *payload : matches) {
          const int payload_value = payload->loadInternalInt();
          ASSERT_GE(payload_value, i * kNumSampleKeys);
          ASSERT_LT(payload_value,
                    i * kNumSampleKeys + static_cast<std::int64_t>(kNumConcurrentThreads));
          EXPECT_FALSE(found_value[payload_value - i * kNumSampleKeys]);
          found_value[payload_value - i * kNumSampleKeys] = true;
        }
        for (const bool found : found_value) {
          EXPECT_TRUE(found);
        }
      } else {
        ASSERT_EQ(1u, matches.size());
        for (const std::unique_ptr<CompositeKeyInserterThread> &thread : threads) {
          if (thread->insert_succeeded()[i]) {
            EXPECT_EQ(i * kNumSampleKeys + thread->getID(),
                      matches.front()->loadInternalInt());
          }
        }
      }
    }
  }

  std::unique_ptr<StorageManager> storage_manager_;
  std::unique_ptr<ScopedBuffer> memory_buffer_;
  std::unique_ptr<HashTableImpl> hash_table_;
  std::vector<ScopedBuffer> external_strings_;
};
TYPED_TEST_CASE_P(HashTableTest);

template <typename HashTableImpl> using HashTableTestLongOnly
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(HashTableTestLongOnly);

// Alias for tests which only apply to resizable hash tables.
template <typename HashTableImpl> using ResizableHashTableTest
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(ResizableHashTableTest);

template <typename HashTableImpl> using ResizableHashTableTestLongOnly
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(ResizableHashTableTestLongOnly);

// Alias for tests which only apply to non-resizable hash tables.
template <typename HashTableImpl> using NonResizableHashTableTest
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(NonResizableHashTableTest);

template <typename HashTableImpl> using NonResizableHashTableTestLongOnly
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(NonResizableHashTableTestLongOnly);

// Alias for tests which only apply to hash tables which do not allow duplicate
// keys.
template <typename HashTableImpl> using DuplicateKeysForbiddenHashTableTest
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(DuplicateKeysForbiddenHashTableTest);

template <typename HashTableImpl> using DuplicateKeysForbiddenHashTableTestLongOnly
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(DuplicateKeysForbiddenHashTableTestLongOnly);

// Alias for tests which only apply to hash tables which are fixed-size and
// serializable.
template <typename HashTableImpl> using FixedSizeSerializableHashTableTest
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(FixedSizeSerializableHashTableTest);

template <typename HashTableImpl> using FixedSizeSerializableHashTableTestLongOnly
    = HashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(FixedSizeSerializableHashTableTestLongOnly);

// We use a separate test fixture here, since the regular HashTableTest assumes
// that HashTableImpl::value_type is TestHashPayload.
template <typename HashTableImpl>
class NonTriviallyDestructibleValueHashTableTest : public ::testing::Test {
 protected:
  virtual void SetUp() {
    storage_manager_.reset(new StorageManager("./test_data/"));
  }

  static std::vector<const Type*> SetupScalarKeyType(const TypeID type_id) {
    std::vector<const Type*> key_type_vec;
    switch (type_id) {
      case kLong:
        key_type_vec.push_back(&TypeFactory::GetType(kLong, false));
        break;
      case kChar:
        key_type_vec.push_back(&TypeFactory::GetType(kChar, kStringLengthParam, false));
        break;
      case kVarChar:
        key_type_vec.push_back(&TypeFactory::GetType(kVarChar, kStringLengthParam, false));
        break;
      default:
        FATAL_ERROR("TypeID not covered\n");
    }
    return key_type_vec;
  }

  static std::vector<const Type*> SetupCompositeKeyType() {
    std::vector<const Type*> key_type_vec;
    key_type_vec.push_back(&TypeFactory::GetType(kLong, false));
    key_type_vec.push_back(&TypeFactory::GetType(kChar, kStringLengthParam, false));
    key_type_vec.push_back(&TypeFactory::GetType(kVarChar, kStringLengthParam, false));
    return key_type_vec;
  }

  void createResizableHashTable(const std::vector<const Type*> &key_types,
                                const std::size_t num_entries) {
    hash_table_.reset(new HashTableImpl(key_types,
                                        num_entries,
                                        storage_manager_.get()));
  }

  void createNonresizableHashTable(const std::vector<const Type*> &key_types,
                                   const std::size_t buffer_size,
                                   const std::size_t offset_in_buffer) {
    assert(offset_in_buffer < buffer_size);
    memory_buffer_.reset(new ScopedBuffer(buffer_size, kCacheLineBytes));
    hash_table_.reset(new HashTableImpl(
        key_types,
        static_cast<char*>(memory_buffer_->get()) + offset_in_buffer,
        buffer_size - offset_in_buffer,
        true,
        false));
  }

  void createHashTableSimple(const std::vector<const Type*> &key_types,
                             const std::size_t num_entries) {
    if (HashTableImpl::template_resizable) {
      createResizableHashTable(key_types, num_entries);
    } else {
      // Allocate space for 'num_entries' generously.
      std::size_t key_size = 0;
      for (const Type *type : key_types) {
        key_size += type->maximumByteLength();
      }
      createNonresizableHashTable(
          key_types,
          num_entries * 8 * (key_size + sizeof(typename HashTableImpl::value_type)),
          0);
    }
  }

  TypedValue createLongKey(const std::int64_t seed) const {
    return TypedValue(seed);
  }

  TypedValue createCharKey(const std::int64_t seed) {
    std::ostringstream stream;
    stream << seed;
    external_strings_.emplace_back(stream.str().size() + 1);
    std::memcpy(external_strings_.back().get(),
                stream.str().c_str(),
                stream.str().size() + 1);
    return TypeFactory::GetType(kChar, kStringLengthParam, false).makeValue(external_strings_.back().get(),
                                                                     stream.str().size() + 1);
  }

  TypedValue createVarCharKey(const std::int64_t seed) {
    std::ostringstream stream;
    stream << seed;
    external_strings_.emplace_back(stream.str().size() + 1);
    std::memcpy(external_strings_.back().get(),
                stream.str().c_str(),
                stream.str().size() + 1);
    return TypeFactory::GetType(kVarChar, kStringLengthParam, false).makeValue(external_strings_.back().get(),
                                                                        stream.str().size() + 1);
  }

  TypedValue createScalarKey(const TypeID test_key_type_id,
                             const std::int64_t seed) {
    switch (test_key_type_id) {
      case TypeID::kLong:
        return createLongKey(seed);
      case TypeID::kChar:
        return createCharKey(seed);
      case TypeID::kVarChar:
        return createVarCharKey(seed);
      default:
        FATAL_ERROR("TypeID not covered\n");
    }
  }

  std::vector<TypedValue> createCompositeKey(const std::int64_t seed) {
    std::vector<TypedValue> key;
    key.emplace_back(createLongKey(seed));
    key.emplace_back(createCharKey(seed));
    key.emplace_back(createVarCharKey(seed));
    return key;
  }

  void runScalarKeyDestroyValueTest(const TypeID test_key_type_id) {
    std::vector<const Type*> key_types = SetupScalarKeyType(test_key_type_id);
    createHashTableSimple(key_types, kNumSampleKeys);

    std::atomic<int> destruct_count(0);

    // Insert some key/value pairs.
    for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
      TypedValue key(createScalarKey(test_key_type_id, i * (i + 1)));
      NonTriviallyDestructibleTestHashPayload value(&destruct_count);
      EXPECT_EQ(HashTablePutResult::kOK, hash_table_->put(key, value));
      value.clearDestructCountPtr();
    }

    // Destroy the hash table and check that the destructors of inserted values
    // were invoked.
    hash_table_.reset(nullptr);
    EXPECT_EQ(kNumSampleKeys,
              destruct_count.load(std::memory_order_relaxed));
  }

  std::unique_ptr<StorageManager> storage_manager_;
  std::unique_ptr<ScopedBuffer> memory_buffer_;
  std::unique_ptr<HashTableImpl> hash_table_;
  std::vector<ScopedBuffer> external_strings_;
};
TYPED_TEST_CASE_P(NonTriviallyDestructibleValueHashTableTest);

template <typename HashTableImpl> using NonTriviallyDestructibleValueHashTableTestLongOnly
    = NonTriviallyDestructibleValueHashTableTest<HashTableImpl>;
TYPED_TEST_CASE_P(NonTriviallyDestructibleValueHashTableTestLongOnly);

TYPED_TEST_P(HashTableTestLongOnly, LongKeyPutAndGetTest) {
  this->runScalarKeyPutAndGetTest(TypeID::kLong);
}

TYPED_TEST_P(HashTableTest, CharKeyPutAndGetTest) {
  this->runScalarKeyPutAndGetTest(TypeID::kChar);
}

TYPED_TEST_P(HashTableTest, VarCharKeyPutAndGetTest) {
  this->runScalarKeyPutAndGetTest(TypeID::kVarChar);
}

TYPED_TEST_P(HashTableTest, CompositeKeyPutAndGetTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys);

  // Insert some key/value pairs.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    TestHashPayload value(i);
    EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->putCompositeKey(key, value));
  }

  // Read them back out.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    // Use getSingleCompositeKey() if duplicate keys are not allowed.
    if (!TypeParam::template_allow_duplicate_keys) {
      const TestHashPayload *value = this->hash_table_->getSingleCompositeKey(key);
      ASSERT_NE(nullptr, value);
      EXPECT_EQ(i, value->loadInternalInt());
    }

    // Test getAllCompositeKey() in all cases.
    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    ASSERT_EQ(1u, matches.size());
    EXPECT_EQ(i, matches.front()->loadInternalInt());
  }

  // Check a nonexistent key.
  std::vector<TypedValue> nonexistent_key(
      this->createCompositeKey(kNumSampleKeys * kNumSampleKeys * kNumSampleKeys));
  if (!TypeParam::template_allow_duplicate_keys) {
    const TestHashPayload *nonexistent_value
        = this->hash_table_->getSingleCompositeKey(nonexistent_key);
    EXPECT_EQ(nullptr, nonexistent_value);
  }
  std::vector<const TestHashPayload*> nonexistent_matches;
  this->hash_table_->getAllCompositeKey(nonexistent_key, &nonexistent_matches);
  EXPECT_TRUE(nonexistent_matches.empty());

  // Check a nonexistent key that only differs from an existing key in one
  // component.
  nonexistent_key.clear();
  nonexistent_key.emplace_back(this->createLongKey(0));
  nonexistent_key.emplace_back(this->createCharKey(0));
  nonexistent_key.emplace_back(this->createVarCharKey(1));
  if (!TypeParam::template_allow_duplicate_keys) {
    const TestHashPayload *nonexistent_value
        = this->hash_table_->getSingleCompositeKey(nonexistent_key);
    EXPECT_EQ(nullptr, nonexistent_value);
  }
  nonexistent_matches.clear();
  this->hash_table_->getAllCompositeKey(nonexistent_key, &nonexistent_matches);
  EXPECT_TRUE(nonexistent_matches.empty());

  // Also test forEach().
  TestVisitor visitor;
  EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys),
            this->hash_table_->forEachCompositeKey(&visitor));
  EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys),
            visitor.internal_map().size());
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    ASSERT_EQ(1u, visitor.internal_map().count(i * (i + 1)));
    EXPECT_EQ(i, visitor.internal_map().find(i * (i + 1))->second);
  }
}

TYPED_TEST_P(HashTableTest, SpecialHashesPutAndGetTest) {
  std::vector<const Type*> key_types = this->SetupScalarKeyType(kLong);
  this->createHashTableSimple(key_types, 4);

  // Insert Long values that hash to "special" reserved values in HashTable.
  TypedValue empty_hash_key(
      this->createScalarKey(kLong, static_cast<std::int64_t>(TypeParam::kEmptyHash)));
  TestHashPayload empty_hash_value(42);
  EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->put(empty_hash_key, empty_hash_value));

  TypedValue pending_hash_key(
      this->createScalarKey(kLong, static_cast<std::int64_t>(TypeParam::kPendingHash)));
  TestHashPayload pending_hash_value(85);
  EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->put(pending_hash_key, pending_hash_value));

  // Also try values whose natural hashes are the same as the adjusted hashes
  // of the values above (causing spurious hash collisions).
  TypedValue adjusted_empty_hash_key(
      this->createScalarKey(kLong, static_cast<std::int64_t>(TypeParam::kEmptyHash + 1)));
  TestHashPayload adjusted_empty_hash_value(123);
  EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->put(adjusted_empty_hash_key,
                                                            adjusted_empty_hash_value));

  TypedValue adjusted_pending_hash_key(
      this->createScalarKey(kLong, static_cast<std::int64_t>(TypeParam::kPendingHash - 1)));
  TestHashPayload adjusted_pending_hash_value(456);
  EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->put(adjusted_pending_hash_key,
                                                            adjusted_pending_hash_value));

  // Read values back out.
  std::vector<const TestHashPayload*> values;
  this->hash_table_->getAll(empty_hash_key, &values);
  ASSERT_EQ(1u, values.size());
  EXPECT_EQ(42, values.front()->loadInternalInt());
  values.clear();

  this->hash_table_->getAll(pending_hash_key, &values);
  ASSERT_EQ(1u, values.size());
  EXPECT_EQ(85, values.front()->loadInternalInt());
  values.clear();

  this->hash_table_->getAll(adjusted_empty_hash_key, &values);
  ASSERT_EQ(1u, values.size());
  EXPECT_EQ(123, values.front()->loadInternalInt());
  values.clear();

  this->hash_table_->getAll(adjusted_pending_hash_key, &values);
  ASSERT_EQ(1u, values.size());
  EXPECT_EQ(456, values.front()->loadInternalInt());
  values.clear();
}

TYPED_TEST_P(HashTableTestLongOnly, LongKeyPutDuplicateKeysTest) {
  this->runDuplicateScalarKeysPutAndGetTest(TypeID::kLong);
}

TYPED_TEST_P(HashTableTest, CharKeyPutDuplicateKeysTest) {
  this->runDuplicateScalarKeysPutAndGetTest(TypeID::kChar);
}

TYPED_TEST_P(HashTableTest, VarCharKeyPutDuplicateKeysTest) {
  this->runDuplicateScalarKeysPutAndGetTest(TypeID::kVarChar);
}

TYPED_TEST_P(HashTableTest, CompositeKeyPutDuplicateKeysTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys * 2);

  // Attempt to insert 1-3 values for each distinct key.
  std::size_t total_inserted = 0;
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    TestHashPayload first_value(i * kNumSampleKeys);
    EXPECT_EQ(HashTablePutResult::kOK,
              this->hash_table_->putCompositeKey(key, first_value));
    ++total_inserted;

    for (int extra_value_num = 1;
         extra_value_num <= i % 3;
         ++extra_value_num) {
      TestHashPayload additional_value(i * kNumSampleKeys + extra_value_num);
      if (TypeParam::template_allow_duplicate_keys) {
        EXPECT_EQ(HashTablePutResult::kOK,
                  this->hash_table_->putCompositeKey(key, additional_value));
        ++total_inserted;
      } else {
        EXPECT_EQ(HashTablePutResult::kDuplicateKey,
                  this->hash_table_->putCompositeKey(key, additional_value));
      }
    }
  }

  // Read them back out.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    if (TypeParam::template_allow_duplicate_keys) {
      EXPECT_EQ(static_cast<std::size_t>((i % 3) + 1), matches.size());
      std::bitset<3> value_found;
      for (const TestHashPayload *match : matches) {
        ASSERT_LE(match->loadInternalInt() - i * kNumSampleKeys, 3);
        EXPECT_FALSE(value_found[match->loadInternalInt() - i * kNumSampleKeys]);
        value_found.set(match->loadInternalInt() - i * kNumSampleKeys, true);
      }
      EXPECT_TRUE(value_found[0]);
      if (i % 3 > 0) {
        EXPECT_TRUE(value_found[1]);
      } else {
        EXPECT_FALSE(value_found[1]);
      }
      if (i % 3 > 1) {
        EXPECT_TRUE(value_found[2]);
      } else {
        EXPECT_FALSE(value_found[2]);
      }
    } else {
      ASSERT_EQ(1u, matches.size());
      EXPECT_EQ(i * kNumSampleKeys,
                matches.front()->loadInternalInt());
    }
  }

  // Check a nonexistent key.
  std::vector<TypedValue> nonexistent_key(
      this->createCompositeKey(kNumSampleKeys * kNumSampleKeys * kNumSampleKeys));
  std::vector<const TestHashPayload*> nonexistent_matches;
  this->hash_table_->getAllCompositeKey(nonexistent_key, &nonexistent_matches);
  EXPECT_TRUE(nonexistent_matches.empty());

  // Check a nonexistent key that only differs from an existing key in one
  // component.
  nonexistent_key.clear();
  nonexistent_key.emplace_back(this->createLongKey(0));
  nonexistent_key.emplace_back(this->createCharKey(0));
  nonexistent_key.emplace_back(this->createVarCharKey(1));
  if (!TypeParam::template_allow_duplicate_keys) {
    const TestHashPayload *nonexistent_value
        = this->hash_table_->getSingleCompositeKey(nonexistent_key);
    EXPECT_EQ(nullptr, nonexistent_value);
  }
  nonexistent_matches.clear();
  this->hash_table_->getAllCompositeKey(nonexistent_key, &nonexistent_matches);
  EXPECT_TRUE(nonexistent_matches.empty());

  // Also test forEach().
  TestVisitor visitor;
  EXPECT_EQ(total_inserted, this->hash_table_->forEachCompositeKey(&visitor));
  EXPECT_EQ(total_inserted, visitor.internal_map().size());
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    if (TypeParam::template_allow_duplicate_keys) {
      ASSERT_EQ(static_cast<std::size_t>(1 + (i % 3)),
                visitor.internal_map().count(i * (i + 1)));
      std::bitset<3> value_found;
      std::pair<std::unordered_multimap<std::int64_t, int>::const_iterator,
                std::unordered_multimap<std::int64_t, int>::const_iterator> match_range
          = visitor.internal_map().equal_range(i * (i + 1));
      for (std::unordered_multimap<std::int64_t, int>::const_iterator match_it = match_range.first;
           match_it != match_range.second;
           ++match_it) {
        ASSERT_LE(match_it->second - i * kNumSampleKeys, 3);
        EXPECT_FALSE(value_found[match_it->second - i * kNumSampleKeys]);
        value_found.set(match_it->second - i * kNumSampleKeys, true);
      }

      EXPECT_TRUE(value_found[0]);
      if (i % 3 > 0) {
        EXPECT_TRUE(value_found[1]);
      } else {
        EXPECT_FALSE(value_found[1]);
      }
      if (i % 3 > 1) {
        EXPECT_TRUE(value_found[2]);
      } else {
        EXPECT_FALSE(value_found[2]);
      }
    } else {
      ASSERT_EQ(1u, visitor.internal_map().count(i * (i + 1)));
      EXPECT_EQ(i * kNumSampleKeys,
                visitor.internal_map().find(i * (i + 1))->second);
    }
  }
}

TYPED_TEST_P(HashTableTestLongOnly, LongKeyPutAndGetFromValueAccessorTest) {
  this->runScalarKeyPutAndGetFromValueAccessorTest(TypeID::kLong);
}

TYPED_TEST_P(HashTableTest, CharKeyPutAndGetFromValueAccessorTest) {
  this->runScalarKeyPutAndGetFromValueAccessorTest(TypeID::kChar);
}

TYPED_TEST_P(HashTableTest, VarCharKeyPutAndGetFromValueAccessorTest) {
  this->runScalarKeyPutAndGetFromValueAccessorTest(TypeID::kVarChar);
}

TYPED_TEST_P(HashTableTest, CompositeKeyPutAndGetFromValueAccessorTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys);

  std::unique_ptr<ColumnVectorsValueAccessor> accessor(this->createSampleValueAccessor());

  std::vector<attribute_id> key_attr_ids;
  key_attr_ids.push_back(0);
  key_attr_ids.push_back(1);
  key_attr_ids.push_back(2);

  // Vectorized insert, skipping over null keys.
  TestInserter inserter;
  EXPECT_EQ(HashTablePutResult::kOK,
            this->hash_table_->putValueAccessorCompositeKey(accessor.get(),
                                                            key_attr_ids,
                                                            true,
                                                            &inserter));

  // Read values back out.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    ASSERT_EQ(1u, matches.size());
    EXPECT_EQ(i + (i >= kNumSampleKeys / 2),
              matches.front()->loadInternalInt());
  }

  // Also read the values out using the vectorized interface.
  accessor->beginIteration();
  TestVisitor visitor;
  this->hash_table_->getAllFromValueAccessorCompositeKey(accessor.get(),
                                                         key_attr_ids,
                                                         true,
                                                         &visitor);
  EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys), visitor.internal_map().size());
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    ASSERT_EQ(1u, visitor.internal_map().count(i * (i + 1)));
    EXPECT_EQ(i + (i >= kNumSampleKeys / 2),
              visitor.internal_map().find(i * (i + 1))->second);
  }
}

TYPED_TEST_P(HashTableTestLongOnly, LongKeyThreadedPutTest) {
  this->runScalarKeyThreadedPutTest(TypeID::kLong, false);
}

TYPED_TEST_P(HashTableTest, CharKeyThreadedPutTest) {
  this->runScalarKeyThreadedPutTest(TypeID::kChar, false);
}

TYPED_TEST_P(HashTableTest, VarCharKeyThreadedPutTest) {
  this->runScalarKeyThreadedPutTest(TypeID::kVarChar, false);
}

TYPED_TEST_P(HashTableTest, CompositeKeyThreadedPutTest) {
  this->runCompositeKeyThreadedPutTest(false);
}

TYPED_TEST_P(HashTableTestLongOnly, LongKeyClearTest) {
  this->runScalarKeyClearTest(TypeID::kLong);
}

TYPED_TEST_P(HashTableTest, CharKeyClearTest) {
  this->runScalarKeyClearTest(TypeID::kChar);
}

TYPED_TEST_P(HashTableTest, VarCharKeyClearTest) {
  this->runScalarKeyClearTest(TypeID::kVarChar);
}

TYPED_TEST_P(HashTableTest, CompositeKeyClearTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys);

  // Insert some key/value pairs.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    TestHashPayload value(i);
    EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->putCompositeKey(key, value));
  }

  // Clear out the HashTable.
  this->hash_table_->clear();

  // Make sure entries are cleared out.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));

    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    EXPECT_TRUE(matches.empty());
  }

  // Also make sure that forEach() sees an empty HashTable.
  TestVisitor visitor;
  EXPECT_EQ(0u, this->hash_table_->forEachCompositeKey(&visitor));
  EXPECT_EQ(0u, visitor.internal_map().size());
}

TYPED_TEST_P(ResizableHashTableTestLongOnly, LongKeyResizeTest) {
  this->runScalarKeyResizeTest(TypeID::kLong);
}

TYPED_TEST_P(ResizableHashTableTest, CharKeyResizeTest) {
  this->runScalarKeyResizeTest(TypeID::kChar);
}

TYPED_TEST_P(ResizableHashTableTest, VarCharKeyResizeTest) {
  this->runScalarKeyResizeTest(TypeID::kVarChar);
}

TYPED_TEST_P(ResizableHashTableTest, CompositeKeyResizeTest) {
  // Try to trigger a resize by substantially under-provisioning storage.
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createResizableHashTable(key_types, 1);

  const block_id original_blob_id = this->hash_table_->getBlobId();

  for (std::int64_t i = 0;
       i < static_cast<std::int64_t>(
               kSlotSizeBytes / (sizeof(std::size_t) + sizeof(TestHashPayload)));
       ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    TestHashPayload value(i);
    EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->putCompositeKey(key, value));
  }

  // If a resize occured, the block ID should be different now.
  EXPECT_NE(original_blob_id, this->hash_table_->getBlobId());

  // Read out the values.
  for (std::int64_t i = 0; i < 2 * kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));

    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    ASSERT_EQ(1u, matches.size());
    EXPECT_EQ(i, matches.front()->loadInternalInt());
  }
}

TYPED_TEST_P(ResizableHashTableTestLongOnly, LongKeyThreadedResizeTest) {
  this->runScalarKeyThreadedPutTest(TypeID::kLong, true);
}

TYPED_TEST_P(ResizableHashTableTest, CharKeyThreadedResizeTest) {
  this->runScalarKeyThreadedPutTest(TypeID::kChar, true);
}

TYPED_TEST_P(ResizableHashTableTest, VarCharKeyThreadedResizeTest) {
  this->runScalarKeyThreadedPutTest(TypeID::kVarChar, true);
}

TYPED_TEST_P(ResizableHashTableTest, CompositeKeyThreadedResizeTest) {
  this->runCompositeKeyThreadedPutTest(true);
}

TYPED_TEST_P(NonResizableHashTableTestLongOnly, LongKeyExhaustSpaceTest) {
  this->runScalarKeyExhaustSpaceTest(TypeID::kLong);
}

TYPED_TEST_P(NonResizableHashTableTest, CharKeyExhaustSpaceTest) {
  this->runScalarKeyExhaustSpaceTest(TypeID::kChar);
}

TYPED_TEST_P(NonResizableHashTableTest, VarCharKeyExhaustSpaceTest) {
  this->runScalarKeyExhaustSpaceTest(TypeID::kVarChar);
}

TYPED_TEST_P(NonResizableHashTableTest, CompositeKeyExhaustSpaceTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();

  // Under-provision storage and insert entries until we run out of space.
  const std::size_t buffer_size
      = kNumSampleKeys * (key_types.front()->maximumByteLength() + sizeof(typename TypeParam::value_type))
        / 4;
  this->createNonresizableHashTable(key_types, buffer_size, 0);

  std::int64_t i;
  for (i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    TestHashPayload value(i);
    HashTablePutResult result = this->hash_table_->putCompositeKey(key, value);
    if (result != HashTablePutResult::kOK) {
      EXPECT_EQ(HashTablePutResult::kOutOfSpace, result);
      break;
    }
  }

  EXPECT_LT(i, kNumSampleKeys);

  // Check the entries that we were able to insert.
  for (std::int64_t j = 0; j < i; ++j) {
    std::vector<TypedValue> key(this->createCompositeKey(j * (j + 1)));

    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    ASSERT_EQ(1u, matches.size());
    EXPECT_EQ(j, matches.front()->loadInternalInt());
  }

  // Check that the entry we failed to insert is not present.
  std::vector<TypedValue> failed_key(this->createCompositeKey(i * (i + 1)));
  std::vector<const TestHashPayload*> failed_matches;
  this->hash_table_->getAllCompositeKey(failed_key, &failed_matches);
  EXPECT_TRUE(failed_matches.empty());
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTestLongOnly, LongKeyUpsertTest) {
  this->runScalarKeyUpsertTest(TypeID::kLong);
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTest, CharKeyUpsertTest) {
  this->runScalarKeyUpsertTest(TypeID::kChar);
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTest, VarCharKeyUpsertTest) {
  this->runScalarKeyUpsertTest(TypeID::kVarChar);
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTest, CompositeKeyUpsertTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys);

  // Upsert some key/value pairs.
  TestHashPayload initial_value(42);
  TestUpserter upserter;
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    EXPECT_TRUE(this->hash_table_->upsertCompositeKey(key, initial_value, &upserter));
  }
  EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys), upserter.call_count());

  // Visit every other value a second time.
  for (std::int64_t i = 0; i < kNumSampleKeys; i += 2) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    EXPECT_TRUE(this->hash_table_->upsertCompositeKey(key, initial_value, &upserter));
  }
  EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys + (kNumSampleKeys / 2)),
            upserter.call_count());

  // Read out the values and check that they are as expected (initial value
  // for each was set to 42, and each call to TestUpserter increments by 1).
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));

    const TestHashPayload *value = this->hash_table_->getSingleCompositeKey(key);
    ASSERT_NE(nullptr, value);
    EXPECT_EQ(44 - (i % 2), value->loadInternalInt());
  }
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTestLongOnly, LongKeyUpsertValueAccessorTest) {
  this->runScalarKeyUpsertValueAccessorTest(TypeID::kLong);
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTest, CharKeyUpsertValueAccessorTest) {
  this->runScalarKeyUpsertValueAccessorTest(TypeID::kChar);
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTest, VarCharKeyUpsertValueAccessorTest) {
  this->runScalarKeyUpsertValueAccessorTest(TypeID::kVarChar);
}

TYPED_TEST_P(DuplicateKeysForbiddenHashTableTest, CompositeKeyUpsertValueAccessorTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys);

  std::unique_ptr<ColumnVectorsValueAccessor> accessor(this->createSampleValueAccessor());

  std::vector<attribute_id> key_attr_ids;
  key_attr_ids.push_back(0);
  key_attr_ids.push_back(1);
  key_attr_ids.push_back(2);

  // Vectorized upsert, skipping over null keys.
  TestHashPayload initial_value(42);
  TestUpserter upserter;
  EXPECT_TRUE(this->hash_table_->upsertValueAccessorCompositeKey(accessor.get(),
                                                                 key_attr_ids,
                                                                 true,
                                                                 initial_value,
                                                                 &upserter));
  EXPECT_EQ(static_cast<std::size_t>(kNumSampleKeys), upserter.call_count());

  // Read values out and check that they are as expected.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    ASSERT_EQ(1u, matches.size());
    EXPECT_EQ(43, matches.front()->loadInternalInt());
  }
}

TYPED_TEST_P(FixedSizeSerializableHashTableTestLongOnly, LongKeySerializationTest) {
  this->runScalarKeySerializationTest(TypeID::kLong);
}

TYPED_TEST_P(FixedSizeSerializableHashTableTest, CharKeySerializationTest) {
  this->runScalarKeySerializationTest(TypeID::kChar);
}

TYPED_TEST_P(FixedSizeSerializableHashTableTest, VarCharKeySerializationTest) {
  this->runScalarKeySerializationTest(TypeID::kVarChar);
}

TYPED_TEST_P(FixedSizeSerializableHashTableTest, CompositeKeySerializationTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  std::size_t maximum_key_size = 0;
  for (const Type *type : key_types) {
    maximum_key_size += type->maximumByteLength();
  }
  // Set up a shared memory buffer which will hold both the external keys and
  // the hash table.
  const std::size_t buffer_size
      = kNumSampleKeys * maximum_key_size
        + 8 * kNumSampleKeys * (maximum_key_size + sizeof(typename TypeParam::value_type));
  this->createNonresizableHashTable(key_types,
                                    buffer_size,
                                    kNumSampleKeys * maximum_key_size);

  // Create external keys in the first part of the buffer.
  char *key_ptr = static_cast<char*>(this->memory_buffer_->get());
  std::vector<std::vector<std::size_t>> key_sizes;
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    std::vector<std::size_t> component_sizes;
    for (const TypedValue &key_component : key) {
      key_component.copyInto(key_ptr);
      component_sizes.push_back(key_component.getDataSize());
      key_ptr += key_component.getDataSize();
    }
    key_sizes.emplace_back(component_sizes);
  }

  // Now actually insert.
  key_ptr = static_cast<char*>(this->memory_buffer_->get());
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key;
    for (std::size_t component_idx = 0;
         component_idx < key_types.size();
         ++component_idx) {
      key.emplace_back(key_types[component_idx]->makeValue(key_ptr, key_sizes[i][component_idx]));
      key_ptr += key_sizes[i][component_idx];
    }
    TestHashPayload value(i);
    EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->putCompositeKey(key, value));
  }

  // Destroy the HashTable object and copy the underlying memory.
  this->hash_table_.reset(nullptr);
  ScopedBuffer moved_buffer(buffer_size, kCacheLineBytes);
  std::memcpy(moved_buffer.get(), this->memory_buffer_->get(), buffer_size);
  this->memory_buffer_.reset(nullptr);

  // Recreate the HashTable at the new location.
  this->hash_table_.reset(new TypeParam(
      key_types,
      static_cast<char*>(moved_buffer.get()) + kNumSampleKeys * maximum_key_size,
      buffer_size - kNumSampleKeys * maximum_key_size,
      false,
      false));

  // If duplicate keys are not allowed, make sure we can't insert a
  // duplicate.
  if (!TypeParam::template_allow_duplicate_keys) {
    std::vector<TypedValue> key;
    key_ptr = static_cast<char*>(moved_buffer.get());
    for (std::size_t component_idx = 0;
         component_idx < key_types.size();
         ++component_idx) {
      key.emplace_back(key_types[component_idx]->makeValue(key_ptr, key_sizes[0][component_idx]));
      key_ptr += key_sizes[0][component_idx];
    }
    TestHashPayload value(123);
    EXPECT_EQ(HashTablePutResult::kDuplicateKey, this->hash_table_->putCompositeKey(key, value));
  }

  // Read the inserted values back out.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));

    // Test getAll() in all cases.
    std::vector<const TestHashPayload*> matches;
    this->hash_table_->getAllCompositeKey(key, &matches);
    ASSERT_EQ(1u, matches.size());
    EXPECT_EQ(i, matches.front()->loadInternalInt());
  }

  // Check a nonexistent key.
  std::vector<TypedValue> nonexistent_key(
      this->createCompositeKey(kNumSampleKeys * kNumSampleKeys * kNumSampleKeys));
  std::vector<const TestHashPayload*> nonexistent_matches;
  this->hash_table_->getAllCompositeKey(nonexistent_key, &nonexistent_matches);
  EXPECT_TRUE(nonexistent_matches.empty());
}

TYPED_TEST_P(NonTriviallyDestructibleValueHashTableTestLongOnly, LongKeyDestroyValueTest) {
  this->runScalarKeyDestroyValueTest(TypeID::kLong);
}

TYPED_TEST_P(NonTriviallyDestructibleValueHashTableTest, CharKeyDestroyValueTest) {
  this->runScalarKeyDestroyValueTest(TypeID::kChar);
}

TYPED_TEST_P(NonTriviallyDestructibleValueHashTableTest, VarCharKeyDestroyValueTest) {
  this->runScalarKeyDestroyValueTest(TypeID::kVarChar);
}

TYPED_TEST_P(NonTriviallyDestructibleValueHashTableTest, CompositeKeyDestroyValueTest) {
  std::vector<const Type*> key_types = this->SetupCompositeKeyType();
  this->createHashTableSimple(key_types, kNumSampleKeys);

  std::atomic<int> destruct_count(0);

  // Insert some key/value pairs.
  for (std::int64_t i = 0; i < kNumSampleKeys; ++i) {
    std::vector<TypedValue> key(this->createCompositeKey(i * (i + 1)));
    NonTriviallyDestructibleTestHashPayload value(&destruct_count);
    EXPECT_EQ(HashTablePutResult::kOK, this->hash_table_->putCompositeKey(key, value));
    value.clearDestructCountPtr();
  }

  // Destroy the hash table and check that the destructors of inserted values
  // were invoked.
  this->hash_table_.reset(nullptr);
  EXPECT_EQ(kNumSampleKeys, destruct_count.load(std::memory_order_relaxed));
}

REGISTER_TYPED_TEST_CASE_P(HashTableTestLongOnly,
                           LongKeyPutAndGetTest,
                           LongKeyPutDuplicateKeysTest,
                           LongKeyPutAndGetFromValueAccessorTest,
                           LongKeyThreadedPutTest,
                           LongKeyClearTest);

REGISTER_TYPED_TEST_CASE_P(HashTableTest,
                           CharKeyPutAndGetTest,
                           VarCharKeyPutAndGetTest,
                           CompositeKeyPutAndGetTest,
                           SpecialHashesPutAndGetTest,
                           CharKeyPutDuplicateKeysTest,
                           VarCharKeyPutDuplicateKeysTest,
                           CompositeKeyPutDuplicateKeysTest,
                           CharKeyPutAndGetFromValueAccessorTest,
                           VarCharKeyPutAndGetFromValueAccessorTest,
                           CompositeKeyPutAndGetFromValueAccessorTest,
                           CharKeyThreadedPutTest,
                           VarCharKeyThreadedPutTest,
                           CompositeKeyThreadedPutTest,
                           CharKeyClearTest,
                           VarCharKeyClearTest,
                           CompositeKeyClearTest);

REGISTER_TYPED_TEST_CASE_P(ResizableHashTableTestLongOnly,
                           LongKeyResizeTest,
                           LongKeyThreadedResizeTest);

REGISTER_TYPED_TEST_CASE_P(ResizableHashTableTest,
                           CharKeyResizeTest,
                           VarCharKeyResizeTest,
                           CompositeKeyResizeTest,
                           CharKeyThreadedResizeTest,
                           VarCharKeyThreadedResizeTest,
                           CompositeKeyThreadedResizeTest);

REGISTER_TYPED_TEST_CASE_P(NonResizableHashTableTestLongOnly,
                           LongKeyExhaustSpaceTest);

REGISTER_TYPED_TEST_CASE_P(NonResizableHashTableTest,
                           CharKeyExhaustSpaceTest,
                           VarCharKeyExhaustSpaceTest,
                           CompositeKeyExhaustSpaceTest);

REGISTER_TYPED_TEST_CASE_P(DuplicateKeysForbiddenHashTableTestLongOnly,
                           LongKeyUpsertTest,
                           LongKeyUpsertValueAccessorTest);

REGISTER_TYPED_TEST_CASE_P(DuplicateKeysForbiddenHashTableTest,
                           CharKeyUpsertTest,
                           VarCharKeyUpsertTest,
                           CompositeKeyUpsertTest,
                           CharKeyUpsertValueAccessorTest,
                           VarCharKeyUpsertValueAccessorTest,
                           CompositeKeyUpsertValueAccessorTest);

REGISTER_TYPED_TEST_CASE_P(FixedSizeSerializableHashTableTestLongOnly,
                           LongKeySerializationTest);

REGISTER_TYPED_TEST_CASE_P(FixedSizeSerializableHashTableTest,
                           CharKeySerializationTest,
                           VarCharKeySerializationTest,
                           CompositeKeySerializationTest);

REGISTER_TYPED_TEST_CASE_P(NonTriviallyDestructibleValueHashTableTestLongOnly,
                           LongKeyDestroyValueTest);

REGISTER_TYPED_TEST_CASE_P(NonTriviallyDestructibleValueHashTableTest,
                           CharKeyDestroyValueTest,
                           VarCharKeyDestroyValueTest,
                           CompositeKeyDestroyValueTest);

}  // namespace quickstep

// Macro to automatically instantiate tests for all the different flavors of
// the specificied HashTable implementation template.
#define QUICKSTEP_TEST_HASHTABLE_IMPL(HashTableImpl)                        \
namespace quickstep {                                                       \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, false, false, false>,             \
    HashTableImpl<TestHashPayload, false, false, false, true>,              \
    HashTableImpl<TestHashPayload, false, false, true, false>,              \
    HashTableImpl<TestHashPayload, false, false, true, true>,               \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, true>,               \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, false, true, true, true>,                \
    HashTableImpl<TestHashPayload, true, false, false, false>,              \
    HashTableImpl<TestHashPayload, true, false, false, true>,               \
    HashTableImpl<TestHashPayload, true, false, true, false>,               \
    HashTableImpl<TestHashPayload, true, false, true, true>,                \
    HashTableImpl<TestHashPayload, true, true, true, false>,                \
    HashTableImpl<TestHashPayload, true, true, true, true>>                 \
        _CommonTestTypes;                                                   \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              HashTableTestLongOnly,                        \
                              _CommonTestTypes);                            \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              HashTableTest,                                \
                              _CommonTestTypes);                            \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, true, false, false, false>,              \
    HashTableImpl<TestHashPayload, true, false, false, true>,               \
    HashTableImpl<TestHashPayload, true, false, true, false>,               \
    HashTableImpl<TestHashPayload, true, false, true, true>,                \
    HashTableImpl<TestHashPayload, true, true, true, false>,                \
    HashTableImpl<TestHashPayload, true, true, true, true>>                 \
        _ResizableTestTypes;                                                \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              ResizableHashTableTestLongOnly,               \
                              _ResizableTestTypes);                         \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              ResizableHashTableTest,                       \
                              _ResizableTestTypes);                         \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, false, false, false>,             \
    HashTableImpl<TestHashPayload, false, false, false, true>,              \
    HashTableImpl<TestHashPayload, false, false, true, false>,              \
    HashTableImpl<TestHashPayload, false, false, true, true>,               \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, true>,               \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, false, true, true, true>>                \
        _NonResizableTestTypes;                                             \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              NonResizableHashTableTestLongOnly,            \
                              _NonResizableTestTypes);                      \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              NonResizableHashTableTest,                    \
                              _NonResizableTestTypes);                      \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, false, false, false>,             \
    HashTableImpl<TestHashPayload, false, false, true, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, true, false, false, false>,              \
    HashTableImpl<TestHashPayload, true, false, true, false>,               \
    HashTableImpl<TestHashPayload, true, true, true, false>>                \
        _DuplicateKeysForbiddenTypes;                                       \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              DuplicateKeysForbiddenHashTableTestLongOnly,  \
                              _DuplicateKeysForbiddenTypes);                \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              DuplicateKeysForbiddenHashTableTest,          \
                              _DuplicateKeysForbiddenTypes);                \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, true>,               \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, false, true, true, true>>                \
        _FixedSizeSerializableTestTypes;                                    \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              FixedSizeSerializableHashTableTestLongOnly,   \
                              _FixedSizeSerializableTestTypes);             \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              FixedSizeSerializableHashTableTest,           \
                              _FixedSizeSerializableTestTypes);             \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, false, false>,                              \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, false, true>,                               \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, true, false>,                               \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, true, true>,                                \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, false, false>,                               \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, false, true>,                                \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, true, false>,                                \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, true, true>>                                 \
        _NonTriviallyDestructibleNonSerializableTestTypes;                  \
INSTANTIATE_TYPED_TEST_CASE_P(                                              \
    HashTableImpl,                                                          \
    NonTriviallyDestructibleValueHashTableTestLongOnly,                     \
    _NonTriviallyDestructibleNonSerializableTestTypes);                     \
INSTANTIATE_TYPED_TEST_CASE_P(                                              \
    HashTableImpl,                                                          \
    NonTriviallyDestructibleValueHashTableTest,                             \
    _NonTriviallyDestructibleNonSerializableTestTypes);                     \
                                                                            \
}  /* namespace quickstep */                                                \
struct quickstep_hashtable_test_dummy  /* NOLINT(build/class) */

// Similar to QUICKSTEP_TEST_HASHTABLE_IMPL(), but only instantiates test cases
// that use LONG keys.
#define QUICKSTEP_TEST_HASHTABLE_IMPL_LONG_ONLY(HashTableImpl)              \
namespace quickstep {                                                       \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, false, false, false>,             \
    HashTableImpl<TestHashPayload, false, false, false, true>,              \
    HashTableImpl<TestHashPayload, false, false, true, false>,              \
    HashTableImpl<TestHashPayload, false, false, true, true>,               \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, true>,               \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, false, true, true, true>,                \
    HashTableImpl<TestHashPayload, true, false, false, false>,              \
    HashTableImpl<TestHashPayload, true, false, false, true>,               \
    HashTableImpl<TestHashPayload, true, false, true, false>,               \
    HashTableImpl<TestHashPayload, true, false, true, true>,                \
    HashTableImpl<TestHashPayload, true, true, true, false>,                \
    HashTableImpl<TestHashPayload, true, true, true, true>>                 \
        _CommonTestTypes;                                                   \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              HashTableTestLongOnly,                        \
                              _CommonTestTypes);                            \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, true, false, false, false>,              \
    HashTableImpl<TestHashPayload, true, false, false, true>,               \
    HashTableImpl<TestHashPayload, true, false, true, false>,               \
    HashTableImpl<TestHashPayload, true, false, true, true>,                \
    HashTableImpl<TestHashPayload, true, true, true, false>,                \
    HashTableImpl<TestHashPayload, true, true, true, true>>                 \
        _ResizableTestTypes;                                                \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              ResizableHashTableTestLongOnly,               \
                              _ResizableTestTypes);                         \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, false, false, false>,             \
    HashTableImpl<TestHashPayload, false, false, false, true>,              \
    HashTableImpl<TestHashPayload, false, false, true, false>,              \
    HashTableImpl<TestHashPayload, false, false, true, true>,               \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, true>,               \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, false, true, true, true>>                \
        _NonResizableTestTypes;                                             \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              NonResizableHashTableTestLongOnly,            \
                              _NonResizableTestTypes);                      \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, false, false, false>,             \
    HashTableImpl<TestHashPayload, false, false, true, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, true, false, false, false>,              \
    HashTableImpl<TestHashPayload, true, false, true, false>,               \
    HashTableImpl<TestHashPayload, true, true, true, false>>                \
        _DuplicateKeysForbiddenTypes;                                       \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              DuplicateKeysForbiddenHashTableTestLongOnly,  \
                              _DuplicateKeysForbiddenTypes);                \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<TestHashPayload, false, true, false, false>,              \
    HashTableImpl<TestHashPayload, false, true, false, true>,               \
    HashTableImpl<TestHashPayload, false, true, true, false>,               \
    HashTableImpl<TestHashPayload, false, true, true, true>>                \
        _FixedSizeSerializableTestTypes;                                    \
INSTANTIATE_TYPED_TEST_CASE_P(HashTableImpl,                                \
                              FixedSizeSerializableHashTableTestLongOnly,   \
                              _FixedSizeSerializableTestTypes);             \
                                                                            \
typedef ::testing::Types<                                                   \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, false, false>,                              \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, false, true>,                               \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, true, false>,                               \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  false, false, true, true>,                                \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, false, false>,                               \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, false, true>,                                \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, true, false>,                                \
    HashTableImpl<NonTriviallyDestructibleTestHashPayload,                  \
                  true, false, true, true>>                                 \
        _NonTriviallyDestructibleNonSerializableTestTypes;                  \
INSTANTIATE_TYPED_TEST_CASE_P(                                              \
    HashTableImpl,                                                          \
    NonTriviallyDestructibleValueHashTableTestLongOnly,                     \
    _NonTriviallyDestructibleNonSerializableTestTypes);                     \
                                                                            \
}  /* namespace quickstep */                                                \
struct quickstep_hashtable_test_dummy  /* NOLINT(build/class) */

#endif  // QUICKSTEP_STORAGE_TESTS_HASHTABLE_UNITTEST_COMMON_HPP_