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,879 @@
+//===- 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/DenseMap.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Parallel.h"
+#include "llvm/Support/WithColor.h"
+#include <atomic>
+#include <cstddef>
+#include <iomanip>
+#include <mutex>
+#include <sstream>
+#include <type_traits>
+
+namespace llvm {
+
+/// ConcurrentHashTable - is a resizeable concurrent hashtable.
+/// The range of resizings without noticable performance degradations
+/// is up to x100000. The hashtable allows only concurrent insertions.
+
+/// Data structure:
+///
+/// Value -> [------- 64-bit Hash value --------]
+/// [ ** ][ ChainIndex ][ Bucket Index ]
+/// | | |
+/// possibly points to points to
+/// unused the bucket the bucket.
+/// chains.
+///
+/// After initialization, all buckets consist of one chain(not inititalized
+/// at start). During insertions, buckets might be extended to contain more
+/// chains. The number of chains kept by bucket is called bucket width. The
+/// maximal bucket width is 32768. Each bucket can be independently resized
+/// and rehashed(no need to lock the whole table).
+///
+/// HashTables keeps chains of all buckets: HashTables[ChainIdx][BucketIdx]
+///
+/// Each chain keeps a list of array of entries:
+///
+/// ChainHead->[ entry1 ] keeps entry data
+/// [ entry2 ]
+/// [ ... ]
+/// [ last entry]
+/// [ next chain item] -> points to the next chain item
+///
+/// Pointer to the first bucket chain also keeps the width of the bucket.
+/// i.e. HashTables[0][BucketIdx] keeps both: pointer to the first chain
+/// and the width of the bucket BucketIdx.
+///
+/// ConcurrentHashTable: each entry keeps KeyDataTy in place or null.
+///
+/// ConcurrentHashTableExternalAlloc: each entry keeps a pair: hash value
+/// and the pointer to the KeyDataTy or null.
+
+template <typename KeyDataTy> struct HashedEntry {
+ uint64_t Hash;
+ KeyDataTy *Data = nullptr;
+};
+
+template <typename KeyDataTy, bool KeepDataInsideTable>
+class ConcurrentHashTableConstants {
+public:
+ static size_t constexpr MaxBucketWidthNum = 32768;
+ static size_t constexpr GrowthRate = 1;
+ static size_t constexpr ChainItemSize =
+ 128 * sizeof(typename std::conditional<KeepDataInsideTable, uint8_t,
+ uint32_t>::type);
+ static size_t constexpr MapEntrySize =
+ sizeof(typename std::conditional<KeepDataInsideTable, KeyDataTy,
+ HashedEntry<KeyDataTy>>::type);
+ static size_t constexpr EntriesPerChainItem =
+ (ChainItemSize - sizeof(uintptr_t)) / MapEntrySize;
+ static size_t constexpr MutexesInitialSize = 256;
+};
+
+template <typename KeyTy, typename KeyDataTy, typename AllocatorTy,
+ bool KeepDataInsideTable, typename Info,
+ typename Constants =
+ ConcurrentHashTableConstants<KeyDataTy, KeepDataInsideTable>>
+class ConcurrentHashTableBase {
+public:
+ static_assert((Constants::MaxBucketWidthNum >= 1) &
+ !(Constants::MaxBucketWidthNum &
+ (Constants::MaxBucketWidthNum - 1)),
+ "MaxBucketWidthNum must be a power of two.");
+ static_assert((Constants::MaxBucketWidthNum <= 32768),
+ "MaxBucketWidthNum must not be greater than 32768.");
+ static_assert((Constants::GrowthRate > 0),
+ "GrowthRate must be greater than 0.");
+ static_assert((Constants::GrowthRate < 16),
+ "GrowthRate must not be greater than 16.");
+ static_assert((Constants::MutexesInitialSize > 0),
+ "MutexesInitialSize must be greater than 0.");
+
+ using MapEntryTy = typename std::conditional<KeepDataInsideTable, KeyDataTy,
+ HashedEntry<KeyDataTy>>::type;
+ using InsertionTy =
+ typename std::conditional<KeepDataInsideTable, KeyDataTy, KeyTy>::type;
+
+ using InsertionResultTy =
+ typename std::conditional<KeepDataInsideTable, KeyDataTy,
+ KeyDataTy *>::type;
+
+ ConcurrentHashTableBase(
+ size_t EstimatedSize, AllocatorTy &Allocator,
+ size_t ThreadsNum = parallel::strategy.compute_thread_count())
+ : Allocator(Allocator) {
+ assert(ThreadsNum > 0);
+
+ // Calculate hashtable size.
+ HashTableSize = EstimatedSize / Constants::EntriesPerChainItem;
+ HashTableSize = NextPowerOf2(HashTableSize);
+ HashTableSize = std::max(HashTableSize, (size_t)2);
+ NumberOfHashTables = 0;
+
+ // Allocate first hashtable.
+ memset(&HashTables, 0, sizeof(HashTables));
+ allocateNewHashTables(1);
+
+ // Calculate number of mutexes.
+ BucketMutexesNum = NextPowerOf2(Constants::MutexesInitialSize * ThreadsNum);
+ BucketMutexesNum = std::min(BucketMutexesNum, HashTableSize);
+
+ // Allocate mutexes.
+ BucketMutexes = Allocator.template Allocate<std::mutex>(BucketMutexesNum);
+ for (size_t Idx = 0; Idx < BucketMutexesNum; Idx++)
+ new (&BucketMutexes[Idx]) std::mutex();
+
+ // Calculate masks.
+ size_t LeadingZerosNumber = countLeadingZeros(getHashMask());
+ HashBitsNum = sizeof(hash_code) * UINT8_WIDTH - LeadingZerosNumber;
+ MaxBucketWidth = std::min(Constants::MaxBucketWidthNum,
+ (size_t)(1 << LeadingZerosNumber));
+
+ ExtHashMask = ((HashTableSize * MaxBucketWidth) - 1) & ~getHashMask();
+ }
+
+ /// Insert new value \p NewValue or return already existing entry.
+ ///
+ /// \returns entry and "true" if an entry is just inserted or
+ /// "false" if an entry already exists.
+ std::pair<InsertionResultTy, bool> insert(const InsertionTy &NewValue,
+ AllocatorTy &ThreadLocalAllocator) {
+ // Calculate bucket index.
+ hash_code Hash = getHashCode(NewValue);
+ size_t BucketIdx = Hash & getHashMask();
+ size_t ExtHashBits = getExtHashBits(Hash);
+ MapEntryTy DataToInsert;
+
+ ValueInserter<InsertionResultTy> Handler(NewValue, ThreadLocalAllocator,
+ getBucketMutex(BucketIdx), Hash);
+ HashTableEntry &ZeroEntryRef = HashTables[0][BucketIdx];
+
+ // Lock bucket.
+ Handler.BucketMutex.lock();
+
+ while (true) {
+ // Get chain head.
+ ChainItem *ChainHead = ZeroEntryRef;
+ ExtBitsEntry ExtEntry = ExtBitsEntry::getFromOpaqueValue(ChainHead);
+ uint8_t BucketWidthValue = getBucketWidthValue(ExtEntry);
+ size_t BucketWidth = getBucketWidthFromValue(BucketWidthValue);
+ size_t ChainIdx = ExtHashBits & (BucketWidth - 1);
+ if (ChainIdx == 0) {
+ ChainHead = ExtEntry.getPointer();
+ if (ChainHead == nullptr) {
+ ChainHead = allocateItem(ThreadLocalAllocator);
+ ExtEntry.setPointer(ChainHead);
+ ZeroEntryRef = static_cast<ChainItem *>(ExtEntry.getOpaqueValue());
+ }
+ } else {
+ HashTableEntry &EntryRef = HashTables[ChainIdx][BucketIdx];
+ ChainHead = EntryRef;
+
+ if (ChainHead == nullptr) {
+ ChainHead = allocateItem(ThreadLocalAllocator);
+ EntryRef = ChainHead;
+ }
+ }
+
+ // For each chain entry...
+ if (forEachChainEntry<CreateNewChainItems,
+ ValueInserter<InsertionResultTy>>(
+ BucketIdx, BucketWidth, ChainHead, Handler, ThreadLocalAllocator))
+ break;
+ }
+
+ return Handler.Result;
+ }
+
+ /// Print information about current state of hash table structures.
+ void printStatistic(raw_ostream &OS) {
+ OS << "\n--- HashTable statistic:\n";
+ OS << "\nTable Size = " << HashTableSize;
+ OS << "\nNumber of tables = " << NumberOfHashTables;
+ OS << "\nEntries per chain item = " << (int)Constants::EntriesPerChainItem;
+ OS << "\nNumber of mutexes = " << (int)BucketMutexesNum;
+
+ uint64_t NumberOfBuckets = 0;
+ uint64_t LongestChainLength = 0;
+ uint64_t NumberOfEntries = 0;
+ uint64_t NumberOfEntriesPlusEmpty = 0;
+ uint64_t OverallSize =
+ sizeof(*this) + HashTableSize * NumberOfHashTables * sizeof(MapEntryTy);
+
+ class ChainLengthCounter {
+ public:
+ IterationStatus handleEntry(MapEntryTy &EntryData) {
+ if (!ConcurrentHashTableBase::isNull(EntryData))
+ ChainLength++;
+
+ return IterationStatus::Next;
+ }
+ uint64_t ChainLength = 0;
+ };
+ DenseMap<size_t, size_t> BucketWidthsMap;
+
+ // For each bucket...
+ for (uint64_t CurBucketIdx = 0; CurBucketIdx < HashTableSize;
+ CurBucketIdx++) {
+
+ NumberOfEntriesPlusEmpty +=
+ Constants::EntriesPerChainItem * NumberOfHashTables;
+
+ if (isEmptyBucket(CurBucketIdx))
+ continue;
+
+ NumberOfBuckets++;
+
+ size_t BucketWidth =
+ getBucketWidthFromValue(getBucketWidthValue(CurBucketIdx));
+ BucketWidthsMap[BucketWidth] = BucketWidthsMap.lookup(BucketWidth) + 1;
+
+ // For each chain...
+ for (size_t CurChainIdx = 0; CurChainIdx < BucketWidth; CurChainIdx++) {
+
+ ChainItem *ChainHead =
+ getChainHead<DoNotCreateChainHead>(CurBucketIdx, CurChainIdx);
+ if (ChainHead == nullptr)
+ continue;
+
+ ChainLengthCounter Handler;
+
+ // For each chain entry...
+ [[maybe_unused]] bool ForEachSuccessful =
+ forEachChainEntry<DoNotCreateNewChainItems, ChainLengthCounter>(
+ CurBucketIdx, BucketWidth, ChainHead, Handler);
+ assert(ForEachSuccessful);
+
+ LongestChainLength = std::max(LongestChainLength, Handler.ChainLength);
+ NumberOfEntries += Handler.ChainLength;
+
+ size_t ItemsInChain =
+ (Handler.ChainLength / Constants::EntriesPerChainItem) +
+ ((Handler.ChainLength % Constants::EntriesPerChainItem) > 0 ? 1
+ : 0);
+ assert(ItemsInChain > 0);
+
+ NumberOfEntriesPlusEmpty +=
+ Constants::EntriesPerChainItem * (ItemsInChain - 1);
+ OverallSize += sizeof(ChainItem) * ItemsInChain;
+ if constexpr (std::is_pointer<MapEntryTy>::value)
+ OverallSize += sizeof(KeyDataTy);
+ }
+ }
+
+ OS << "\nOverall number of entries = " << NumberOfEntries;
+ OS << "\nOverall number of buckets = " << NumberOfBuckets;
+ for (auto &Width : BucketWidthsMap)
+ OS << "\n Number of buckets with width " << Width.first << ": "
+ << Width.second;
+ OS << "\nLongest chain length = " << LongestChainLength;
+
+ std::stringstream stream;
+ stream << std::fixed << std::setprecision(2)
+ << ((float)NumberOfEntries / (float)NumberOfEntriesPlusEmpty);
+ std::string str = stream.str();
+
+ OS << "\nLoad factor = " << str;
+ OS << "\nOverall allocated size = " << OverallSize;
+ }
+
+protected:
+ enum IterationStatus : uint8_t { Stop, Next };
+
+ struct alignas(16) ChainItem {
+ ChainItem() = delete;
+ ChainItem(const ChainItem &) = delete;
+ ChainItem &operator=(const ChainItem &) = delete;
+
+ MapEntryTy Entries[Constants::EntriesPerChainItem];
+ ChainItem *Next;
+ };
+
+ static constexpr bool CreateChainHead = true;
+ static constexpr bool DoNotCreateChainHead = false;
+
+ static constexpr bool CreateNewChainItems = true;
+ static constexpr bool DoNotCreateNewChainItems = false;
+
+ using HashTableEntry = ChainItem *;
+ using HashTablePtr = HashTableEntry *;
+ using ExtBitsEntry = PointerIntPair<ChainItem *, 4, uint8_t>;
+
+ bool isEmptyBucket(size_t BucketIdx) {
+ return ExtBitsEntry::getFromOpaqueValue(HashTables[0][BucketIdx])
+ .getPointer() == nullptr;
+ }
+
+ uint8_t getBucketWidthValue(size_t BucketIdx) {
+ return ExtBitsEntry::getFromOpaqueValue(HashTables[0][BucketIdx]).getInt();
+ }
+
+ uint8_t getBucketWidthValue(ChainItem *Head) {
+ return getBucketWidthValue(ExtBitsEntry::getFromOpaqueValue(Head));
+ }
+
+ uint8_t getBucketWidthValue(ExtBitsEntry ExtEntry) {
+ return ExtEntry.getInt();
+ }
+
+ size_t getBucketWidthFromValue(uint8_t BucketWidthValue) {
+ return 1 << (BucketWidthValue);
+ }
+
+ void setBucketWidth(size_t BucketIdx, size_t NewBucketWidth) {
+ assert((NewBucketWidth >= 1) & !(NewBucketWidth & (NewBucketWidth - 1)));
+ assert(getBucketWidthFromValue(getBucketWidthValue(BucketIdx)) <
+ NewBucketWidth);
+
+ HashTableEntry &ExtEntryRef = HashTables[0][BucketIdx];
+ ExtBitsEntry ExtEntry = ExtBitsEntry::getFromOpaqueValue(ExtEntryRef);
+ ExtEntry.setInt(static_cast<uint8_t>(countTrailingZeros(NewBucketWidth)));
+
+ ExtEntryRef = static_cast<ChainItem *>(ExtEntry.getOpaqueValue());
+ }
+
+ size_t getExtHashBits(hash_code Hash) {
+ return (Hash & ExtHashMask) >> HashBitsNum;
+ }
+
+ size_t getChainIdx(hash_code Hash, size_t BucketWidth) {
+ assert(BucketWidth > 0);
+
+ return getExtHashBits(Hash) & (BucketWidth - 1);
+ }
+
+ // Return number of entries inside specified bucket.
+ size_t getNumberOfEntries(size_t BucketIdx, size_t BucketWidth) {
+ class EntriesCounter {
+ public:
+ IterationStatus handleEntry(MapEntryTy &EntryData) {
+ if (ConcurrentHashTableBase::isNull(EntryData))
+ return IterationStatus::Next;
+
+ EntriesNumber++;
+ return IterationStatus::Next;
+ }
+ size_t EntriesNumber = 0;
+ } Handler;
+
+ for (size_t CurChainIdx = 0; CurChainIdx < BucketWidth; CurChainIdx++) {
+ ChainItem *ChainHead =
+ getChainHead<DoNotCreateChainHead>(BucketIdx, CurChainIdx);
+ if (ChainHead == nullptr)
+ continue;
+
+ [[maybe_unused]] bool ForEachSuccessful =
+ forEachChainEntry<DoNotCreateNewChainItems, EntriesCounter>(
+ BucketIdx, BucketWidth, ChainHead, Handler);
+ assert(ForEachSuccessful);
+ }
+
+ return Handler.EntriesNumber;
+ }
+
+ // Allocate new chain intem.
+ ChainItem *allocateItem(AllocatorTy &ThreadLocalAllocator) {
+ ChainItem *ResultItem = ThreadLocalAllocator.template Allocate<ChainItem>();
+
+ assert(ResultItem != nullptr);
+ memset(ResultItem, 0x0, sizeof(ChainItem));
+
+ return ResultItem;
+ }
+
+ // Return chain head. Create new head if CreateChainHead is true.
+ template <bool CreateChainHead, typename... Types>
+ ChainItem *getChainHead(size_t BucketIdx, hash_code Hash, size_t BucketWidth,
+ Types &... ThreadLocalAllocator) {
+ size_t ChainIdx = getChainIdx(Hash, BucketWidth);
+ return getChainHead<CreateChainHead>(BucketIdx, ChainIdx,
+ ThreadLocalAllocator...);
+ }
+
+ // Return chain head. Create new head if CreateChainHead is true.
+ template <bool CreateChainHead, typename... Types>
+ ChainItem *getChainHead(size_t BucketIdx, size_t ChainIdx,
+ Types &... ThreadLocalAllocator) {
+ ChainItem *ChainHead = HashTables[ChainIdx][BucketIdx];
+
+ if (ChainIdx == 0) {
+ ExtBitsEntry ExtEntry = ExtBitsEntry::getFromOpaqueValue(ChainHead);
+ ChainHead = ExtEntry.getPointer();
+
+ if constexpr (CreateChainHead) {
+ if (ChainHead == nullptr) {
+ ChainHead = allocateItem(ThreadLocalAllocator...);
+ ExtEntry.setPointer(ChainHead);
+ HashTables[ChainIdx][BucketIdx] =
+ static_cast<ChainItem *>(ExtEntry.getOpaqueValue());
+ }
+ }
+
+ return ChainHead;
+ }
+
+ if constexpr (CreateChainHead) {
+ if (ChainHead == nullptr) {
+ ChainHead = allocateItem(ThreadLocalAllocator...);
+ HashTables[ChainIdx][BucketIdx] = ChainHead;
+ }
+ }
+
+ return ChainHead;
+ }
+
+ // Return next chain item. Create new item if necessary.
+ template <bool CreateNewChainItems = true, typename... Types,
+ typename std::enable_if<CreateNewChainItems>::type * = nullptr>
+ ChainItem *getNextChainItem(ChainItem *Item,
+ Types &... ThreadLocalAllocator) {
+ ChainItem *NextItem = Item->Next;
+
+ if (NextItem == nullptr) {
+ ChainItem *NewEntry = allocateItem(ThreadLocalAllocator...);
+
+ Item->Next = NewEntry;
+ return NewEntry;
+ }
+
+ return NextItem;
+ }
+
+ // Return next chain item.
+ template <bool CreateNewChainItems = false, typename... Types,
+ typename std::enable_if<!CreateNewChainItems>::type * = nullptr>
+ ChainItem *getNextChainItem(ChainItem *Item, Types &...) {
+ return Item->Next;
+ }
+
+ // Extend HashTables and rehash specified bucket.
+ template <bool AllowResizings = true, typename... Types,
+ typename std::enable_if<AllowResizings>::type * = nullptr>
+ bool extendTable(size_t BucketIdx, size_t BucketWidth,
+ Types &... ThreadLocalAllocator) {
+ assert(BucketWidth ==
+ getBucketWidthFromValue(getBucketWidthValue(BucketIdx)));
+ if (BucketWidth >= MaxBucketWidth)
+ return false;
+
+ ExtendAndRehashBucket(BucketIdx, BucketWidth, ThreadLocalAllocator...);
+ return true;
+ }
+
+ // Do nothing.
+ template <bool AllowResizings = false, typename... Types,
+ typename std::enable_if<!AllowResizings>::type * = nullptr>
+ constexpr bool extendTable(size_t, size_t, Types &...) {
+ return false;
+ }
+
+ // Enumerate all entries for the specified bucket and bucket`s chain.
+ template <bool CreateNewChainItems, typename EntryHandler, typename... Types>
+ inline __attribute__((always_inline)) bool
+ forEachChainEntry(size_t BucketIdx, size_t BucketWidth, ChainItem *ChainHead,
+ EntryHandler &Handler, Types &... ThreadLocalAllocator) {
+ assert(ChainHead != nullptr);
+
+ for (ChainItem *CurItem = ChainHead; CurItem != nullptr;
+ CurItem = getNextChainItem<CreateNewChainItems>(
+ CurItem, ThreadLocalAllocator...)) {
+ MapEntryTy *Entries = CurItem->Entries;
+ for (size_t EntryIdx = 0; EntryIdx < Constants::EntriesPerChainItem;) {
+ switch (Handler.handleEntry(Entries[EntryIdx])) {
+ case Stop:
+ return true;
+ case Next:
+ EntryIdx++;
+ }
+ }
+
+ if (extendTable<CreateNewChainItems>(BucketIdx, BucketWidth,
+ ThreadLocalAllocator...))
+ return false;
+ }
+
+ return true;
+ }
+
+ // Insert data into the chain item.
+ template <typename ReturnDataTy> class ValueInserter {
+ public:
+ ValueInserter(const InsertionTy &InsertionData,
+ AllocatorTy &ThreadLocalAllocator, std::mutex &BucketMutex,
+ hash_code Hash)
+ : InsertionData(InsertionData),
+ ThreadLocalAllocator(ThreadLocalAllocator), BucketMutex(BucketMutex),
+ Hash(Hash) {}
+
+ IterationStatus handleEntry(MapEntryTy &EntryData) {
+ MapEntryTy Value = EntryData;
+ if (ConcurrentHashTableBase::isNull(Value)) {
+ // Insert new value into the empty slot.
+ if constexpr (KeepDataInsideTable) {
+ Result.first = InsertionData;
+ EntryData = Result.first;
+ } else {
+ Result.first = Info::create(InsertionData, ThreadLocalAllocator);
+ EntryData = {Hash, Result.first};
+ }
+ assert(!(isNull(Result.first)));
+ BucketMutex.unlock();
+
+ Result.second = true;
+ return IterationStatus::Stop;
+ }
+
+ if constexpr (KeepDataInsideTable) {
+ if (ConcurrentHashTableBase::isEqual(Value, InsertionData)) {
+ // Already existed entry matched with inserted data
+ // is found.
+ BucketMutex.unlock();
+ Result.first = Value;
+ Result.second = false;
+ return IterationStatus::Stop;
+ }
+ } else {
+ if (ConcurrentHashTableBase::isEqual(Value, InsertionData, Hash)) {
+ // Already existed entry matched with inserted data
+ // is found.
+ BucketMutex.unlock();
+ Result.first = Value.Data;
+ Result.second = false;
+ return IterationStatus::Stop;
+ }
+ }
+
+ return IterationStatus::Next;
+ }
+ std::pair<ReturnDataTy, bool> Result;
+ const InsertionTy &InsertionData;
+ AllocatorTy &ThreadLocalAllocator;
+ std::mutex &BucketMutex;
+ hash_code Hash;
+ };
+
+ using CollectedValuesVector = SmallVector<MapEntryTy>;
+
+ // This function adds new chains to the bucket and rehash existing
+ // values to place them into the new chains.
+ void ExtendAndRehashBucket(size_t BucketIdx, size_t BucketWidth,
+ AllocatorTy &ThreadLocalAllocator) {
+ assert(BucketWidth < MaxBucketWidth);
+
+ assert(BucketWidth > 0);
+ size_t NewBucketsWidth =
+ std::min(static_cast<size_t>(BucketWidth << Constants::GrowthRate),
+ MaxBucketWidth);
+
+ // Check whether we need to create new hashtables.
+ if (NewBucketsWidth > NumberOfHashTables) {
+ std::unique_lock<std::mutex> Guard(HashTableMutex);
+
+ if (NewBucketsWidth > NumberOfHashTables)
+ allocateNewHashTables(NewBucketsWidth);
+ }
+
+ // Collect bucket values.
+ CollectedValuesVector Values;
+ collectValuesLocked(BucketIdx, BucketWidth, Values);
+
+ assert(getNumberOfEntries(BucketIdx, BucketWidth) == 0);
+
+ // Insert values into extended bucket.
+ insertValuesLocked(Values, BucketIdx, NewBucketsWidth,
+ ThreadLocalAllocator);
+
+ // Update bucket width.
+ setBucketWidth(BucketIdx, NewBucketsWidth);
+ }
+
+ // Collect all data into the specified vector Values.
+ // Erase data from all bucket's chains.
+ void collectValuesLocked(size_t BucketIdx, size_t BucketWidth,
+ CollectedValuesVector &Values) {
+ class ValueCollector {
+ public:
+ ValueCollector(CollectedValuesVector &Values) : Values(Values) {}
+
+ IterationStatus handleEntry(MapEntryTy &EntryData) {
+ MapEntryTy Value = EntryData;
+
+ if (ConcurrentHashTableBase::isNull(Value))
+ return IterationStatus::Stop;
+
+ Values.emplace_back(Value);
+ setToNull(&EntryData);
+
+ return IterationStatus::Next;
+ }
+
+ CollectedValuesVector &Values;
+ } Handler(Values);
+
+ // Collect bucket values.
+ for (size_t CurChainIdx = 0; CurChainIdx < BucketWidth; CurChainIdx++) {
+ ChainItem *ChainHead =
+ getChainHead<DoNotCreateChainHead>(BucketIdx, CurChainIdx);
+ if (ChainHead == nullptr)
+ continue;
+
+ [[maybe_unused]] bool ForEachSuccessful =
+ forEachChainEntry<DoNotCreateNewChainItems, ValueCollector>(
+ BucketIdx, BucketWidth, ChainHead, Handler);
+ assert(ForEachSuccessful);
+ }
+ }
+
+ // Insert data into the locked bucket.
+ void insertValuesLocked(CollectedValuesVector &Values, size_t BucketIdx,
+ size_t BucketWidth,
+ AllocatorTy &ThreadLocalAllocator) {
+ for (MapEntryTy &NewValue : Values) {
+ assert(!(ConcurrentHashTableBase::isNull(NewValue)));
+
+ hash_code Hash = ConcurrentHashTableBase::getHashCode(NewValue);
+ ChainItem *ChainHead = getChainHead<CreateChainHead>(
+ BucketIdx, Hash, BucketWidth, ThreadLocalAllocator);
+
+ class InsertEntry {
+ public:
+ InsertEntry(MapEntryTy NewValue) : NewValue(NewValue) {}
+
+ IterationStatus handleEntry(MapEntryTy &EntryData) {
+ if (ConcurrentHashTableBase::isNull(EntryData)) {
+ EntryData = NewValue;
+ return IterationStatus::Stop;
+ }
+
+ return IterationStatus::Next;
+ }
+
+ MapEntryTy NewValue;
+ } Handler(NewValue);
+
+ [[maybe_unused]] bool ForEachSuccessful =
+ forEachChainEntry<DoNotCreateNewChainItems, InsertEntry>(
+ BucketIdx, BucketWidth, ChainHead, Handler, ThreadLocalAllocator);
+
+ assert(ForEachSuccessful);
+ }
+ }
+
+ // Allocate new hashtables for specified NewBucketsWidth.
+ void allocateNewHashTables(size_t NewBucketsWidth) {
+ assert((NewBucketsWidth >= 1) & !(NewBucketsWidth & (NewBucketsWidth - 1)));
+ assert(NumberOfHashTables < NewBucketsWidth);
+
+ size_t Start = NumberOfHashTables;
+ size_t Stop = NewBucketsWidth;
+
+ // Allocate and initialize new tables.
+ for (size_t Idx = Start; Idx < Stop; Idx++) {
+ HashTablePtr NewTable =
+ Allocator.template Allocate<HashTableEntry>(HashTableSize);
+ memset(NewTable, 0, sizeof(HashTableEntry) * HashTableSize);
+ HashTables[Idx] = NewTable;
+ }
+
+ NumberOfHashTables = NewBucketsWidth;
+ }
+
+ // Return mutex for the specified BucketIdx.
+ std::mutex &getBucketMutex(size_t BucketIdx) {
+ return BucketMutexes[BucketIdx & (BucketMutexesNum - 1)];
+ }
+
+ template <typename MapEntryTy,
+ typename std::enable_if<
+ (std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value),
+ bool>::type = true>
+ static inline bool isNull(MapEntryTy Data) {
+ const uint64_t *DataPtr = reinterpret_cast<const uint64_t *>(&Data);
+ return *DataPtr == 0 && DataPtr[1] == 0;
+ }
+
+ template <typename MapEntryTy,
+ typename std::enable_if<
+ (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+ sizeof(MapEntryTy) == sizeof(uint8_t)),
+ bool>::type = true>
+ static inline bool isNull(const MapEntryTy &Data) {
+ return *reinterpret_cast<const uint8_t *>(&Data) == static_cast<uint8_t>(0);
+ }
+
+ template <typename MapEntryTy,
+ typename std::enable_if<
+ (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+ sizeof(MapEntryTy) == sizeof(uint16_t)),
+ bool>::type = true>
+ static inline bool isNull(const MapEntryTy &Data) {
+ return *reinterpret_cast<const uint16_t *>(&Data) ==
+ static_cast<uint16_t>(0);
+ }
+
+ template <typename MapEntryTy,
+ typename std::enable_if<
+ (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+ sizeof(MapEntryTy) == sizeof(uint32_t)),
+ bool>::type = true>
+ static inline bool isNull(const MapEntryTy &Data) {
+ return *reinterpret_cast<const uint32_t *>(&Data) ==
+ static_cast<uint32_t>(0);
+ }
+
+ template <typename MapEntryTy,
+ typename std::enable_if<
+ (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+ sizeof(MapEntryTy) == sizeof(uint64_t)),
+ bool>::type = true>
+ static inline bool isNull(const MapEntryTy &Data) {
+ return *reinterpret_cast<const uint64_t *>(&Data) ==
+ static_cast<uint64_t>(0);
+ }
+
+ static inline bool setToNull(MapEntryTy *Data) {
+ return memset(Data, 0, sizeof(MapEntryTy));
+ }
+
+ static inline bool isEqual(MapEntryTy LHS, const InsertionTy &RHS,
+ uint64_t Hash) {
+ return (LHS.Hash == Hash) && Info::isEqual(LHS.Data->key(), RHS);
+ }
+
+ static inline bool isEqual(const MapEntryTy &LHS, const InsertionTy &RHS) {
+ return Info::isEqual(LHS.key(), RHS.key());
+ }
+
+ static inline hash_code getHashCode(const KeyTy &Data) {
+ return Info::getHashValue(Data);
+ }
+
+ static inline hash_code getHashCode(const KeyDataTy &Data) {
+ return Info::getHashValue(Data.key());
+ }
+
+ static inline hash_code getHashCode(const HashedEntry<KeyDataTy> &Data) {
+ return Data.Hash;
+ }
+
+ size_t getHashMask() { return HashTableSize - 1; }
+
+ // Number of bits in hash mask.
+ uint64_t HashBitsNum = 0;
+
+ // Hash mask for the extended hash bits.
+ uint64_t ExtHashMask = 0;
+
+ // Array of mutexes.
+ std::mutex *BucketMutexes = nullptr;
+
+ // Number of used mutexes.
+ size_t BucketMutexesNum = 2;
+
+ // The maximal bucket width.
+ size_t MaxBucketWidth = 0;
+
+ // The size of single hashtable.
+ size_t HashTableSize = 0;
+
+ // The guard for HashTables array.
+ std::mutex HashTableMutex;
+
+ // The current number of HashTables.
+ std::atomic<size_t> NumberOfHashTables;
+
+ // HashTables keeping buckets chains.
+ HashTablePtr HashTables[Constants::MaxBucketWidthNum];
+
+ // This allocator is used to allocate space for the hash tables.
+ // The data are not explicitly deallocated by ConcurrentHashTableBase.
+ AllocatorTy &Allocator;
+};
+
+/// ConcurrentHashTable: keeps a KeyDataTy(which is a key-value pair).
+/// The state when all data bits of KeyDataTy are zero is reserved as
+/// a hashtable tombstone value.
+///
+
+template <typename KeyTy, typename KeyDataTy> class ConcurrentHashTableInfo {
+public:
+ /// \returns Hash value for the specified \p Key.
+ static inline hash_code getHashValue(const KeyTy &Key) {
+ return std::hash<KeyTy>()(Key);
+ }
+
+ /// \returns true if both \p LHS and \p RHS are equal.
+ static inline bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
+ return LHS == RHS;
+ }
+};
+
+template <typename KeyTy, typename KeyDataTy,
+ typename AllocatorTy = BumpPtrAllocator,
+ typename Info = ConcurrentHashTableInfo<KeyTy, KeyDataTy>,
+ typename Constants = ConcurrentHashTableConstants<KeyDataTy, true>>
+class ConcurrentHashTable
+ : public ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, true, Info,
+ Constants> {
+public:
+ ConcurrentHashTable(size_t InitialSize, AllocatorTy &Allocator)
+ : ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, true, Info,
+ Constants>(InitialSize, Allocator) {}
+};
+
+/// ConcurrentHashTableExternalAlloc: keeps a pointer to the KeyDataTy class
+/// (which is a key-value pair), whose data are allocated and kept by the
+/// external allocator.
+
+template <typename KeyTy, typename KeyDataTy, typename AllocatorTy>
+class ConcurrentHashTableInfoExternalAlloc {
+public:
+ /// \returns Hash value for the specified \p Key.
+ static inline hash_code getHashValue(const KeyTy &Key) {
+ return std::hash<KeyTy>()(Key);
+ }
+
+ /// \returns true if both \p LHS and \p RHS are equal.
+ static inline bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
+ return LHS == RHS;
+ }
+
+ /// \returns newly created object of KeyDataTy type.
+ static inline KeyDataTy *create(const KeyTy &Key, AllocatorTy &Allocator) {
+ return KeyDataTy::create(Key, Allocator);
+ }
+};
+
+template <
+ typename KeyTy, typename KeyDataTy, typename AllocatorTy = BumpPtrAllocator,
+ typename Info =
+ ConcurrentHashTableInfoExternalAlloc<KeyTy, KeyDataTy, AllocatorTy>,
+ typename Constants = ConcurrentHashTableConstants<KeyDataTy, false>>
+class ConcurrentHashTableExternalAlloc
+ : public ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, false, Info,
+ Constants> {
+public:
+ ConcurrentHashTableExternalAlloc(size_t InitialSize, AllocatorTy &Allocator)
+ : ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, false, Info,
+ Constants>(InitialSize, Allocator) {}
+};
+
+} // 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
@@ -16,6 +16,7 @@
BumpPtrListTest.cpp
CoalescingBitVectorTest.cpp
CombinationGeneratorTest.cpp
+ ConcurrentHashtableTest.cpp
DAGDeltaAlgorithmTest.cpp
DeltaAlgorithmTest.cpp
DenseMapTest.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,401 @@
+//===- ConcurrentHashtableTest.cpp ----------------------------------------===//
+//
+// 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 <experimental/random>
+#include <limits>
+#include <vector>
+using namespace llvm;
+
+namespace {
+class Int {
+public:
+ Int() : Data(0x0) {}
+ uint32_t key() const { return Data & 0x7FFFFFFF; }
+
+ friend bool operator==(const Int &LHS, const Int &RHS) {
+ return LHS.Data == RHS.Data;
+ }
+
+ static Int create(uint32_t Data) { return Int(Data | 0x80000000); }
+
+protected:
+ Int(uint32_t Data) : Data(Data) {}
+
+ uint32_t Data;
+};
+
+TEST(ConcurrentHashTableTest, AddIntEntries) {
+ BumpPtrAllocator Allocator;
+ ConcurrentHashTable<uint32_t, Int> HashTable(10, Allocator);
+
+ std::pair<Int, bool> res1 = HashTable.insert(Int::create(1), Allocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == 1);
+ EXPECT_TRUE(res1.second);
+
+ res1 = HashTable.insert(Int::create(1), Allocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == 1);
+ EXPECT_FALSE(res1.second);
+
+ std::pair<Int, bool> res2 = HashTable.insert(Int::create(2), Allocator);
+ // 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::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 2") !=
+ std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesWithResizing) {
+ BumpPtrAllocator Allocator;
+ ConcurrentHashTable<uint32_t, Int> HashTable(10, Allocator);
+
+ for (size_t Idx = 0; Idx < 10000; Idx++) {
+ std::pair<Int, bool> res1 = HashTable.insert(Int::create(Idx), Allocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_TRUE(res1.second);
+
+ res1 = HashTable.insert(Int::create(Idx), Allocator);
+ // Check entry is found.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ }
+
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+
+ for (size_t Idx = 0; Idx < 10000; Idx++) {
+ std::pair<Int, bool> res1 = HashTable.insert(Int::create(Idx), Allocator);
+ // Check entry is found.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ }
+
+ StatisticString.erase();
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesParralel) {
+ static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+ ConcurrentHashTable<uint32_t, Int> HashTable(1000000, DataAllocator);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 =
+ HashTable.insert(Int::create(Idx), DataAllocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_TRUE(res1.second);
+
+ res1 = HashTable.insert(Int::create(Idx), DataAllocator);
+ // Check entry is found.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ });
+
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 =
+ HashTable.insert(Int::create(Idx), DataAllocator);
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ });
+
+ StatisticString.erase();
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesWithResizingParralel1) {
+ static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+ ConcurrentHashTable<uint32_t, Int> HashTable(1000, DataAllocator);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 =
+ HashTable.insert(Int::create(Idx), DataAllocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_TRUE(res1.second);
+
+ res1 = HashTable.insert(Int::create(Idx), DataAllocator);
+ // Check entry is found.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ });
+
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 =
+ HashTable.insert(Int::create(Idx), DataAllocator);
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ });
+
+ StatisticString.erase();
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesWithResizingParralel2) {
+ static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+ ConcurrentHashTable<uint32_t, Int> HashTable(10, DataAllocator);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 =
+ HashTable.insert(Int::create(Idx), DataAllocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_TRUE(res1.second);
+
+ res1 = HashTable.insert(Int::create(Idx), DataAllocator);
+ // Check entry is found.
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ });
+
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 =
+ HashTable.insert(Int::create(Idx), DataAllocator);
+ EXPECT_TRUE(res1.first.key() == Idx);
+ EXPECT_FALSE(res1.second);
+ });
+
+ StatisticString.erase();
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddRandomEntriesParralel) {
+
+ std::vector<Int> Data;
+ std::set<size_t> UniqData;
+ std::srand(
+ std::time(nullptr)); // use current time as seed for random generator
+ for (size_t Idx = 0; Idx < 10000; Idx++) {
+ size_t RndNum = std::experimental::randint(0, 100);
+ Data.push_back(Int::create(RndNum));
+ UniqData.insert(RndNum);
+ }
+
+ static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+ ConcurrentHashTable<uint32_t, Int> HashTable(10, DataAllocator);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 = HashTable.insert(Data[Idx], DataAllocator);
+ //// Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == Data[Idx].key());
+
+ res1 = HashTable.insert(Data[Idx], DataAllocator);
+ //// Check entry is inserted.
+ EXPECT_TRUE(res1.first.key() == Data[Idx].key());
+ EXPECT_FALSE(res1.second);
+ });
+
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = " +
+ itostr(UniqData.size())) !=
+ std::string::npos);
+
+ parallelFor(0, 10000, [&](size_t Idx) {
+ std::pair<Int, bool> res1 = HashTable.insert(Data[Idx], DataAllocator);
+ EXPECT_TRUE(res1.first.key() == Data[Idx].key());
+ EXPECT_FALSE(res1.second);
+ });
+
+ StatisticString.erase();
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = " +
+ itostr(UniqData.size())) !=
+ std::string::npos);
+}
+
+using ExtraDataTy = std::array<char, 0x20>;
+
+class String {
+public:
+ String() {}
+ const std::string &key() const { return Data; }
+
+ static String *create(const std::string &Num, BumpPtrAllocator &Allocator) {
+ String *Result = Allocator.Allocate<String>();
+ new (Result) String(Num);
+ return Result;
+ }
+
+protected:
+ String(const std::string &Num) { Data += Num; }
+
+ std::string Data;
+ ExtraDataTy ExtraData;
+};
+
+TEST(ConcurrentHashTableTest, AddStringEntries) {
+ BumpPtrAllocator Allocator;
+ ConcurrentHashTableExternalAlloc<std::string, String> HashTable(10,
+ Allocator);
+
+ std::pair<String *, bool> res1 = HashTable.insert("1", Allocator);
+ // Check entry is inserted.
+ EXPECT_TRUE(res1.first->key() == "1");
+ EXPECT_TRUE(res1.second);
+
+ std::pair<String *, bool> res2 = HashTable.insert("2", Allocator);
+ // 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<String *, bool> res3 = HashTable.insert("3", Allocator);
+ // Check one more entry is inserted.
+ EXPECT_TRUE(res3.first->key() == "3");
+ EXPECT_TRUE(res3.second);
+
+ std::pair<String *, bool> res4 = HashTable.insert("1", Allocator);
+ // 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 statistic.
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 3") !=
+ std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddStringEntriesParallel) {
+ // Number of elements exceeds original size, thus hashtable
+ // should be resized.
+ const size_t NumElements = 10000;
+ static LLVM_THREAD_LOCAL BumpPtrAllocator Allocator;
+ ConcurrentHashTableExternalAlloc<std::string, String, BumpPtrAllocator>
+ HashTable(NumElements, Allocator);
+
+ // Check parallel insertion.
+ parallelFor(0, NumElements, [&](size_t I) {
+ std::string StringForElement = formatv("{0}", I);
+ std::pair<String *, bool> Entry =
+ HashTable.insert(StringForElement, Allocator);
+ EXPECT_TRUE(Entry.second);
+ EXPECT_TRUE(Entry.first->key() == StringForElement);
+ EXPECT_TRUE(Allocator.getBytesAllocated() > 0);
+ });
+
+ std::string StatisticString;
+ raw_string_ostream StatisticStream(StatisticString);
+ HashTable.printStatistic(StatisticStream);
+
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+
+ // Check parallel insertion of duplicates.
+ parallelFor(0, NumElements, [&](size_t I) {
+ size_t BytesAllocated = Allocator.getBytesAllocated();
+ std::string StringForElement = formatv("{0}", I);
+ std::pair<String *, bool> Entry =
+ HashTable.insert(StringForElement, Allocator);
+ EXPECT_FALSE(Entry.second);
+ EXPECT_TRUE(Entry.first->key() == StringForElement);
+ // Check no additional bytes were allocated for duplicate.
+ EXPECT_TRUE(Allocator.getBytesAllocated() == BytesAllocated);
+ });
+
+ // Check statistic.
+ // Verifying that the table contains exactly the number of elements we
+ // inserted.
+ EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+ std::string::npos);
+}
+
+} // namespace