diff --git a/llvm/include/llvm/ADT/ConcurrentHashTable.h b/llvm/include/llvm/ADT/ConcurrentHashTable.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/ConcurrentHashTable.h @@ -0,0 +1,413 @@ +//===- ConcurrentHashTable.h ------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_CONCURRENTHASHTABLE_H +#define LLVM_ADT_CONCURRENTHASHTABLE_H + +#include "llvm/ADT/Hashing.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/NativeFormatting.h" +#include "llvm/Support/WithColor.h" +#include +#include + +namespace llvm { + +/// ConcurrentHashTable - is a partially resizeable lock-free hashtable. +/// +/// A concurrent hash table for global type hashing. It is based on this paper: +/// Concurrent Hash Tables: Fast and General(?)! +/// https://dl.acm.org/doi/10.1145/3309206 +/// +/// This hash table is meant to be used in two phases: +/// 1. concurrent insertions +/// 2. concurrent reads +/// It does not support lookup, deletion, or rehashing. It uses linear probing. +/// +/// The paper describes storing a key-value pair in two machine words. +/// ConcurrentHashTable: keeps a KeyDataTy(which is a key-value pair). +/// ConcurrentHashTableExtAlloc: keeps a pointer to the KeyDataTy class +/// (which is a key-value pair), whose data are allocated and kept by the +/// external allocator. + +template class ConcurrentHashTableBase { +public: + /// Initialize the table with the given size. + void init(size_t InitialSize) { + TableSize = NextPowerOf2(InitialSize); + TableSize = std::max(TableSize, (size_t)4096); + HashMask = TableSize - 1; + CurSlabNum = 0; + FirstSlab = allocateNextSlab(); + } + + /// Print information about current state of hash table structures. + void printStatistic(raw_ostream &OS) { + OS << "\nConcurrentHashTable:\n"; + OS << "\nNumber of slabs: " << CurSlabNum; + OS << "\nNumber of elements per slab: " << TableSize; + OS << "\nFull size of hash table: " + << CurSlabNum * TableSize * sizeof(MapEntryTy) << " bytes \n"; + + size_t OverallNumberOfUsedEntries = 0; + for (Slab *CurSlab = FirstSlab; CurSlab != nullptr; + CurSlab = CurSlab->NextSlab) { + std::pair Statistic = getNumberOfEntriesForSlab(CurSlab); + OS << "\n Slab depth: " << CurSlab->SlabDepth; + OS << "\n Slab fullness: "; + llvm::write_double(OS, ((float)Statistic.first / (float)TableSize), + FloatStyle::Percent); + OS << "\n Slab longest bucket: " << Statistic.second; + OS << "\n"; + + OverallNumberOfUsedEntries += Statistic.first; + } + + OS << "\nOverall number of used elements: " << OverallNumberOfUsedEntries; + OS << "\nOverall fullness of hash table: "; + llvm::write_double( + OS, + ((float)OverallNumberOfUsedEntries / ((float)CurSlabNum * TableSize)), + FloatStyle::Percent); + } + + bool IsInSuboptimalState() const { + return HasFullSlab || CurSlabNum > MaxNumberOfSlabs; + } + +protected: + struct Slab { + std::atomic *Table = nullptr; + std::atomic NextSlab = nullptr; + size_t SlabDepth = 0; + }; + + // \returns next available slab, allocate a new one if necessary. + Slab *getNextSlab(Slab *CurSlab) { + if (CurSlab->NextSlab.load(std::memory_order_relaxed) == nullptr) { + const std::lock_guard lock(SlabsMutex); + + if (CurSlab->NextSlab.load(std::memory_order_relaxed) == nullptr) + CurSlab->NextSlab = allocateNextSlab(); + } + + return CurSlab->NextSlab; + } + + // Allocate new slab. + Slab *allocateNextSlab() { + Slab *NewSlab = Allocator.template Allocate(); + + NewSlab->Table = + Allocator.template Allocate>(TableSize); + memset(NewSlab->Table, 0, TableSize * sizeof(MapEntryTy)); + NewSlab->NextSlab = nullptr; + + NewSlab->SlabDepth = CurSlabNum++; + + if (CurSlabNum > (MaxNumberOfSlabs + 2)) + report_fatal_error("Hash table is full."); + + return NewSlab; + } + + // \returns number of used elements inside slab and the length of the longest + // bucket inside slab. + std::pair getNumberOfEntriesForSlab(Slab *CurSlab) { + size_t NumberOfElements = 0; + size_t MaxBucketLength = 0; + size_t CurBucketLength = 0; + bool prevEntryIsNull = true; + for (size_t CurIdx = 0; CurIdx < TableSize; CurIdx++) { + if (!isNull(CurSlab->Table[CurIdx].load(std::memory_order_relaxed))) { + NumberOfElements++; + + if (prevEntryIsNull) + CurBucketLength = 0; + else + CurBucketLength++; + prevEntryIsNull = false; + } else { + if (!prevEntryIsNull) + MaxBucketLength = std::max(MaxBucketLength, CurBucketLength); + prevEntryIsNull = true; + } + } + + return std::make_pair(NumberOfElements, MaxBucketLength); + } + + template + typename std::enable_if_t::value, bool> isNull(T Data) { + return Data == nullptr; + } + + template + typename std::enable_if_t::value, bool> isNull(T Data) { + return Data.isNull(); + } + + // This allocator is used to allocate space for the hash table entries. + BumpPtrAllocator Allocator; + + // Size of single slab. + size_t TableSize = 0; + + // Mask, used to convert hash_code into the hash table index. + size_t HashMask = 0; + + // Max length of the continuous sequence of non-null entries. + // If length of bucket exceeds MaxBucketLength then new slab would be + // allocated. + const size_t MaxBucketLength = 100; + + // If number of slabs exceeds (MaxNumberOfSlabs + 2) the fatal error will be + // raised. + const size_t MaxNumberOfSlabs = 3; + + // Guard for slabs. + std::mutex SlabsMutex; + + // Pointer to the first slab. + Slab *FirstSlab = nullptr; + + // Number of allocated slabs. + size_t CurSlabNum = 0; + + // Set if hash table has 100% full slab. + bool HasFullSlab = false; +}; + +/// ConcurrentHashTable: +/// +/// It is recommended to use ConcurrentHashTable if sizeof(KeyDataTy) <= +/// sizeof(pointer). +/// +/// KeyTy requirements: +/// +/// --------------------------------------------------------------------------- +/// | Expression | Return type | Semantic | +/// --------------------------------------------------------------------------- +/// | hash_value(KeyTy) | llvm::hash_code | Returns hash code for specified | +/// | | | KeyTy | +/// | | | | +/// | a == b | bool | Compares two KeyTy for | +/// | | | equivalence. | +/// --------------------------------------------------------------------------- +/// +/// KeyDataTy requirements: +/// +/// --------------------------------------------------------------------------- +/// | Expression | Return type | Semantic | +/// --------------------------------------------------------------------------- +/// | a.key() | KeyTy | Returns KeyTy for KeyDataTy | +/// | | | | +/// | a.isNull() | bool | Checks that all data bits are zero| +/// | | | | +/// | a.lessThan(b) | bool | (Optional) Returns true if a is | +/// | | | less than b. Used if hash table | +/// | | | should have deterministic data and| +/// | | | so smaller value would always | +/// | | | overwrite a bigger one. | +/// --------------------------------------------------------------------------- +/// +/// KeyDataTy should match with requirements of atomic types(size and +/// alignment). + +template +class ConcurrentHashTable : public ConcurrentHashTableBase { +public: + /// Insert new entry \p Data or return already existing entry. + /// + /// \returns entry and "true" if an entry is just inserted or + /// "false" if an entry already exists. + std::pair insert(KeyDataTy NewData) { + assert((!this->isNull(NewData)) && "Null entry is inserted."); + assert(this->TableSize > 0 && "hashtable is not initialised"); + return insert(this->FirstSlab, hash_value(NewData.key()) & this->HashMask, + NewData); + } + +protected: + template + using haslessThan = + decltype(std::declval().lessThan(std::declval())); + + template + typename std::enable_if_t::value, bool> + needToOverwriteEntry(T NewData, T Candidate) { + return NewData.lessThan(Candidate); + } + + template + constexpr typename std::enable_if_t::value, bool> + needToOverwriteEntry(T, T) { + return false; + } + + // Insert \p NewData into the specified \p CurSlab. Start probing from + // the \p StartIdx. Allocate new slab if specified slab \p CurSlab is full. + std::pair + insert(typename ConcurrentHashTableBase::Slab *CurSlab, + uint32_t StartIdx, KeyDataTy NewData) { + // Do a linear probe starting at startIdx. + uint32_t Idx = StartIdx; + uint32_t CurBucketSize = 0; + + while (true) { + // Run a compare and swap loop. There are three cases: + // - cell is empty: CAS into place and return + // - cell has matching key, return cell`s data + // - cell has non-matching key: hash collision, probe next cell + KeyDataTy Candidate = CurSlab->Table[Idx].load(std::memory_order_relaxed); + if (ConcurrentHashTableBase::isNull(Candidate)) { + if (CurBucketSize >= this->MaxBucketLength) + // insert data into the new slab. + return insert( + ConcurrentHashTableBase::getNextSlab(CurSlab), + StartIdx, NewData); + + if (CurSlab->Table[Idx].compare_exchange_weak(Candidate, NewData)) + return std::make_pair(NewData, true); + continue; + } + + if (Candidate.key() == NewData.key()) { + // Check order and overwrite entry if necessary. + if (needToOverwriteEntry(NewData, Candidate)) { + if (CurSlab->Table[Idx].compare_exchange_weak(Candidate, NewData)) + return std::make_pair(NewData, true); + + continue; + } + + return std::make_pair(Candidate, false); + } + + ++CurBucketSize; + // Advance the probe. Wrap around to the beginning if we run off the end. + ++Idx; + + Idx = Idx == this->TableSize ? 0 : Idx; + if (Idx == StartIdx) { + ConcurrentHashTableBase::HasFullSlab = true; + + return insert(ConcurrentHashTableBase::getNextSlab(CurSlab), + StartIdx, NewData); + } + } + llvm_unreachable("left infloop"); + } +}; + +/// ConcurrentHashTableExtAlloc: +/// +/// It is recommended to use ConcurrentHashTableExtAlloc if sizeof(KeyDataTy) > +/// sizeof(pointer). +/// +/// Insertions into the internal hash table are lock-free, and +/// allocations are done using an external non-mt-safe data pool. +/// +/// KeyTy requirements: +/// +/// --------------------------------------------------------------------------- +/// | Expression | Return type | Semantic | +/// --------------------------------------------------------------------------- +/// | hash_value(KeyTy) | llvm::hash_code | Returns hash code for | +/// | | | specified KeyTy | +/// | | | | +/// | a == b | bool | Compares two KeyTy for | +/// | | | equivalence. | +/// --------------------------------------------------------------------------- +/// +/// KeyDataTy requirements: +/// +/// --------------------------------------------------------------------------- +/// | Expression | Return type | Semantic | +/// --------------------------------------------------------------------------- +/// | a.key() | KeyTy |Returns KeyTy for KeyDataTy | +/// | | | | +/// | KeyDataTy::create | | | +/// | (KeyTy, AllocatorTy*) | KeyDataTy* |static function returning | +/// | | |newly created KeyDataTy | +/// --------------------------------------------------------------------------- + +template +class ConcurrentHashTableExtAlloc + : public ConcurrentHashTableBase { +public: + /// Insert new entry allocated by \p Allocator for specified \p Key or + /// return already existing entry which key matched with specified \p Key. + /// + /// \returns entry and "true" if an entry is just inserted or + /// "false" if an entry already exists. + std::pair insert(AllocatorTy &Allocator, KeyTy Key) { + assert(this->TableSize > 0 && "hashtable is not initialised"); + return insert(Allocator, this->FirstSlab, hash_value(Key) & this->HashMask, + Key, nullptr); + } + +protected: + // Insert \p NewData into the specified \p CurSlab. Start probing from + // the \p StartIdx. Allocate new slab if specified slab \p CurSlab is full. + std::pair + insert(AllocatorTy &Allocator, + typename ConcurrentHashTableBase::Slab *CurSlab, + uint32_t StartIdx, KeyTy Key, KeyDataTy *NewData) { + // Do a linear probe starting at startIdx. + uint32_t Idx = StartIdx; + uint32_t CurBucketSize = 0; + + while (true) { + // Run a compare and swap loop. There are three cases: + // - cell is empty: CAS into place and return + // - cell has matching key, return cell`s data + // - cell has non-matching key: hash collision, probe next cell + KeyDataTy *Candidate = + CurSlab->Table[Idx].load(std::memory_order_relaxed); + if (ConcurrentHashTableBase::isNull(Candidate)) { + if (CurBucketSize >= this->MaxBucketLength) + // insert data into the new slab. + return insert( + Allocator, + ConcurrentHashTableBase::getNextSlab(CurSlab), + StartIdx, Key, NewData); + + if (ConcurrentHashTableBase::isNull(NewData)) + NewData = KeyDataTy::create(Key, Allocator); + + if (CurSlab->Table[Idx].compare_exchange_weak(Candidate, NewData)) + return std::make_pair(NewData, true); + continue; + } + + if (Candidate->key() == Key) + return std::make_pair(Candidate, false); + + ++CurBucketSize; + // Advance the probe. Wrap around to the beginning if we run off the end. + ++Idx; + + Idx = Idx == this->TableSize ? 0 : Idx; + if (Idx == StartIdx) { + ConcurrentHashTableBase::HasFullSlab = true; + + return insert( + Allocator, + ConcurrentHashTableBase::getNextSlab(CurSlab), + StartIdx, Key, NewData); + } + } + llvm_unreachable("left infloop"); + } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_CONCURRENTHASHTABLE_H diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -15,6 +15,7 @@ BreadthFirstIteratorTest.cpp BumpPtrListTest.cpp CoalescingBitVectorTest.cpp + ConcurrentHashTableTest.cpp CombinationGeneratorTest.cpp DAGDeltaAlgorithmTest.cpp DeltaAlgorithmTest.cpp diff --git a/llvm/unittests/ADT/ConcurrentHashTableTest.cpp b/llvm/unittests/ADT/ConcurrentHashTableTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/ADT/ConcurrentHashTableTest.cpp @@ -0,0 +1,302 @@ +//===- ConcurrentHashTableTest.cpp - ConcurrentHashTable unit tests -------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/ConcurrentHashTable.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/Parallel.h" +#include "gtest/gtest.h" +#include +#include +using namespace llvm; + +namespace { + +class Int { +public: + Int(uint32_t Data) : Data(Data | 0x80000000) {} + + uint32_t key() { return Data & 0x7FFFFFFF; } + + bool isNull() const { return Data == 0; } + + friend bool operator==(const Int &LHS, const Int &RHS) { + return LHS.Data == RHS.Data; + } + +protected: + uint32_t Data; +}; + +class OrderedInt { +public: + OrderedInt(uint16_t Data, uint16_t Order) + : Data(Data | 0x8000), Order(Order) {} + + uint16_t key() { return Data & 0x7FFF; } + + bool isNull() const { return Data == 0 && Order == 0; } + + friend bool operator==(const OrderedInt &LHS, const OrderedInt &RHS) { + return std::tie(LHS.Data, LHS.Order) == std::tie(RHS.Data, RHS.Order); + } + + bool lessThan(const OrderedInt &Other) const { return Order < Other.Order; } + +protected: + uint16_t Data; + uint16_t Order; +}; + +class String { +public: + static String *create(StringRef Key, BumpPtrAllocator &Allocator) { + return new (Allocator) String(Key); + } + + StringRef key() { return Data; } + +protected: + String(StringRef Data) : Data(Data) {} + std::string Data; +}; + +TEST(ConcurrentHashTableTest, AddIntEntries) { + ConcurrentHashTable HashTable; + + HashTable.init(10); + + std::pair res1 = HashTable.insert(Int(1)); + // Check entry is inserted. + EXPECT_TRUE(res1.first.key() == 1); + EXPECT_TRUE(res1.second); + + std::pair res2 = HashTable.insert(Int(2)); + // Check old entry is still valid. + EXPECT_TRUE(res1.first.key() == 1); + // Check new entry is inserted. + EXPECT_TRUE(res2.first.key() == 2); + EXPECT_TRUE(res2.second); + // Check new and old entries are not the equal. + EXPECT_FALSE(res1.first == res2.first); + + std::pair res3 = HashTable.insert(Int(3)); + // Check one more entry is inserted. + EXPECT_TRUE(res3.first.key() == 3); + EXPECT_TRUE(res3.second); + + std::pair res4 = HashTable.insert(Int(1)); + // Check duplicated entry is inserted. + EXPECT_TRUE(res4.first.key() == 1); + EXPECT_FALSE(res4.second); + // Check duplicated entry matches with the first one. + EXPECT_TRUE(res1.first == res4.first); + + // Check first entry is still valid. + EXPECT_TRUE(res1.first.key() == 1); + + // Check hashtable is in optimal state. + EXPECT_FALSE(HashTable.IsInSuboptimalState()); + + // Check statistic. + std::string StatisticString; + raw_string_ostream StatisticStream(StatisticString); + HashTable.printStatistic(StatisticStream); + + EXPECT_TRUE(StatisticString.find("ConcurrentHashTable:") != + std::string::npos); + EXPECT_TRUE(StatisticString.find("Number of slabs: 1") != std::string::npos); + EXPECT_TRUE(StatisticString.find("Slab depth: 0") != std::string::npos); + EXPECT_TRUE(StatisticString.find("Slab fullness: 0.07%") != + std::string::npos); + EXPECT_TRUE(StatisticString.find("Overall number of used elements: 3") != + std::string::npos); + EXPECT_TRUE(StatisticString.find("Overall fullness of hash table: 0.07%") != + std::string::npos); +} + +TEST(ConcurrentHashTableTest, AddIntEntriesSuboptimal) { + ConcurrentHashTable HashTable; + + HashTable.init(4096); + + for (size_t I = 0; I < 30000; I++) + HashTable.insert(Int(I)); + + EXPECT_TRUE(HashTable.IsInSuboptimalState()); +} + +TEST(ConcurrentHashTableTest, AddOrderedIntEntries) { + ConcurrentHashTable HashTable; + + HashTable.init(10); + + std::pair res = HashTable.insert(OrderedInt(1, 2)); + // Check entry is inserted. + EXPECT_TRUE(res.first == OrderedInt(1, 2)); + EXPECT_TRUE(res.second); + + res = HashTable.insert(OrderedInt(1, 3)); + // Check entry is unchanged. + EXPECT_TRUE(res.first == OrderedInt(1, 2)); + EXPECT_FALSE(res.second); + + res = HashTable.insert(OrderedInt(1, 2)); + // Check entry is unchanged. + EXPECT_TRUE(res.first == OrderedInt(1, 2)); + EXPECT_FALSE(res.second); + + res = HashTable.insert(OrderedInt(1, 1)); + // Check entry is overwritten. + EXPECT_TRUE(res.first == OrderedInt(1, 1)); + EXPECT_TRUE(res.second); + + // Check hashtable is in optimal state. + EXPECT_FALSE(HashTable.IsInSuboptimalState()); +} + +TEST(ConcurrentHashTableTest, AddIntEntriesParallel) { + ConcurrentHashTable HashTable; + + HashTable.init(5000); + + // Number of elements exceeds original size, thus hashtable + // should be resized. + const size_t NumElements = 10000; + + // Check parallel insertion. + parallelForEachN(0, NumElements, [&](size_t I) { + std::pair Entry = HashTable.insert(Int(I)); + EXPECT_TRUE(Entry.second); + EXPECT_TRUE(Entry.first.key() == I); + }); + + // Check parallel insertion of duplicates. + parallelForEachN(0, NumElements, [&](size_t I) { + std::pair Entry = HashTable.insert(Int(I)); + EXPECT_FALSE(Entry.second); + EXPECT_TRUE(Entry.first.key() == I); + }); + + // Check hashtable is in suboptimal state. + EXPECT_TRUE(HashTable.IsInSuboptimalState()); + + // Check statistic. + std::string StatisticString; + raw_string_ostream StatisticStream(StatisticString); + HashTable.printStatistic(StatisticStream); + + EXPECT_TRUE(StatisticString.find("Number of slabs: 2") != std::string::npos); + EXPECT_TRUE(StatisticString.find("Overall number of used elements: 10000") != + std::string::npos); +} + +TEST(ConcurrentHashTableTest, AddStringEntries) { + BumpPtrAllocator Allocator; + ConcurrentHashTableExtAlloc HashTable; + + HashTable.init(10); + + std::pair res1 = HashTable.insert(Allocator, "1"); + // Check entry is inserted. + EXPECT_TRUE(res1.first->key() == "1"); + EXPECT_TRUE(res1.second); + + std::pair res2 = HashTable.insert(Allocator, "2"); + // Check old entry is still valid. + EXPECT_TRUE(res1.first->key() == "1"); + // Check new entry is inserted. + EXPECT_TRUE(res2.first->key() == "2"); + EXPECT_TRUE(res2.second); + // Check new and old entries use different memory. + EXPECT_TRUE(res1.first != res2.first); + + std::pair res3 = HashTable.insert(Allocator, "3"); + // Check one more entry is inserted. + EXPECT_TRUE(res3.first->key() == "3"); + EXPECT_TRUE(res3.second); + + std::pair res4 = HashTable.insert(Allocator, "1"); + // Check duplicated entry is inserted. + EXPECT_TRUE(res4.first->key() == "1"); + EXPECT_FALSE(res4.second); + // Check duplicated entry matches with the first one. + EXPECT_TRUE(res1.first == res4.first); + + // Check first entry is still valid. + EXPECT_TRUE(res1.first->key() == "1"); + + // Check data was allocated by allocator. + EXPECT_TRUE(Allocator.getBytesAllocated() > 0); + + // Check hashtable is in optimal state. + EXPECT_FALSE(HashTable.IsInSuboptimalState()); + + // Check statistic. + std::string StatisticString; + raw_string_ostream StatisticStream(StatisticString); + HashTable.printStatistic(StatisticStream); + + EXPECT_TRUE(StatisticString.find("ConcurrentHashTable:") != + std::string::npos); + EXPECT_TRUE(StatisticString.find("Number of slabs: 1") != std::string::npos); + EXPECT_TRUE(StatisticString.find("Slab depth: 0") != std::string::npos); + EXPECT_TRUE(StatisticString.find("Slab fullness: 0.07%") != + std::string::npos); + EXPECT_TRUE(StatisticString.find("Overall number of used elements: 3") != + std::string::npos); + EXPECT_TRUE(StatisticString.find("Overall fullness of hash table: 0.07%") != + std::string::npos); +} + +TEST(ConcurrentHashTableTest, AddStringEntriesParallel) { + ConcurrentHashTableExtAlloc HashTable; + + HashTable.init(5000); + + // Number of elements exceeds original size, thus hashtable + // should be resized. + const size_t NumElements = 10000; + BumpPtrAllocator Allocators[NumElements]; + + // Check parallel insertion. + parallelForEachN(0, NumElements, [&](size_t I) { + std::string StringForElement = formatv("{0}", I); + std::pair Entry = + HashTable.insert(Allocators[I], StringForElement); + EXPECT_TRUE(Entry.second); + EXPECT_TRUE(Entry.first->key() == StringForElement); + EXPECT_TRUE(Allocators[I].getBytesAllocated() > 0); + }); + + // Check parallel insertion of duplicates. + parallelForEachN(0, NumElements, [&](size_t I) { + size_t BytesAllocated = Allocators[I].getBytesAllocated(); + std::string StringForElement = formatv("{0}", I); + std::pair Entry = + HashTable.insert(Allocators[I], StringForElement); + EXPECT_FALSE(Entry.second); + EXPECT_TRUE(Entry.first->key() == StringForElement); + // Check no additional bytes were allocated for duplicate. + EXPECT_TRUE(Allocators[I].getBytesAllocated() == BytesAllocated); + }); + + // Check hashtable is in suboptimal state. + EXPECT_TRUE(HashTable.IsInSuboptimalState()); + + // Check statistic. + std::string StatisticString; + raw_string_ostream StatisticStream(StatisticString); + HashTable.printStatistic(StatisticStream); + + EXPECT_TRUE(StatisticString.find("Number of slabs: 2") != std::string::npos); + EXPECT_TRUE(StatisticString.find("Overall number of used elements: 10000") != + std::string::npos); +} + +} // end anonymous namespace