diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2020-07-26 19:36:28 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2020-07-26 19:36:28 +0000 |
commit | cfca06d7963fa0909f90483b42a6d7d194d01e08 (patch) | |
tree | 209fb2a2d68f8f277793fc8df46c753d31bc853b /llvm/lib/Support/FoldingSet.cpp | |
parent | 706b4fc47bbc608932d3b491ae19a3b9cde9497b (diff) | |
download | src-cfca06d7963fa0909f90483b42a6d7d194d01e08.tar.gz src-cfca06d7963fa0909f90483b42a6d7d194d01e08.zip |
Vendor import of llvm-project master 2e10b7a39b9, the last commit beforevendor/llvm-project/llvmorg-11-init-20887-g2e10b7a39b9vendor/llvm-project/master
the llvmorg-12-init tag, from which release/11.x was branched.
Notes
Notes:
svn path=/vendor/llvm-project/master/; revision=363578
svn path=/vendor/llvm-project/llvmorg-11-init-20887-g2e10b7a39b9/; revision=363579; tag=vendor/llvm-project/llvmorg-11-init-20887-g2e10b7a39b9
Diffstat (limited to 'llvm/lib/Support/FoldingSet.cpp')
-rw-r--r-- | llvm/lib/Support/FoldingSet.cpp | 51 |
1 files changed, 30 insertions, 21 deletions
diff --git a/llvm/lib/Support/FoldingSet.cpp b/llvm/lib/Support/FoldingSet.cpp index ce6f196e1060..e3d7168305af 100644 --- a/llvm/lib/Support/FoldingSet.cpp +++ b/llvm/lib/Support/FoldingSet.cpp @@ -13,6 +13,7 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/Hashing.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/Host.h" @@ -85,6 +86,10 @@ void FoldingSetNodeID::AddInteger(unsigned long long I) { void FoldingSetNodeID::AddString(StringRef String) { unsigned Size = String.size(); + + unsigned NumInserts = 1 + divideCeil(Size, 4); + Bits.reserve(Bits.size() + NumInserts); + Bits.push_back(Size); if (!Size) return; @@ -223,8 +228,6 @@ static void **AllocateBuckets(unsigned NumBuckets) { //===----------------------------------------------------------------------===// // FoldingSetBase Implementation -void FoldingSetBase::anchor() {} - FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) { assert(5 < Log2InitSize && Log2InitSize < 32 && "Initial hash table size out of range"); @@ -266,8 +269,10 @@ void FoldingSetBase::clear() { NumNodes = 0; } -void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) { - assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount"); +void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount, + const FoldingSetInfo &Info) { + assert((NewBucketCount > NumBuckets) && + "Can't shrink a folding set with GrowBucketCount"); assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!"); void **OldBuckets = Buckets; unsigned OldNumBuckets = NumBuckets; @@ -290,8 +295,9 @@ void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) { // Insert the node into the new bucket, after recomputing the hash. InsertNode(NodeInBucket, - GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), - Buckets, NumBuckets)); + GetBucketFor(Info.ComputeNodeHash(this, NodeInBucket, TempID), + Buckets, NumBuckets), + Info); TempID.clear(); } } @@ -301,25 +307,24 @@ void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) { /// GrowHashTable - Double the size of the hash table and rehash everything. /// -void FoldingSetBase::GrowHashTable() { - GrowBucketCount(NumBuckets * 2); +void FoldingSetBase::GrowHashTable(const FoldingSetInfo &Info) { + GrowBucketCount(NumBuckets * 2, Info); } -void FoldingSetBase::reserve(unsigned EltCount) { +void FoldingSetBase::reserve(unsigned EltCount, const FoldingSetInfo &Info) { // This will give us somewhere between EltCount / 2 and // EltCount buckets. This puts us in the load factor // range of 1.0 - 2.0. if(EltCount < capacity()) return; - GrowBucketCount(PowerOf2Floor(EltCount)); + GrowBucketCount(PowerOf2Floor(EltCount), Info); } /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, /// return it. If not, return the insertion token that will make insertion /// faster. -FoldingSetBase::Node * -FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID, - void *&InsertPos) { +FoldingSetBase::Node *FoldingSetBase::FindNodeOrInsertPos( + const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info) { unsigned IDHash = ID.ComputeHash(); void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); void *Probe = *Bucket; @@ -328,7 +333,7 @@ FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID, FoldingSetNodeID TempID; while (Node *NodeInBucket = GetNextPtr(Probe)) { - if (NodeEquals(NodeInBucket, ID, IDHash, TempID)) + if (Info.NodeEquals(this, NodeInBucket, ID, IDHash, TempID)) return NodeInBucket; TempID.clear(); @@ -343,13 +348,15 @@ FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID, /// InsertNode - Insert the specified node into the folding set, knowing that it /// is not already in the map. InsertPos must be obtained from /// FindNodeOrInsertPos. -void FoldingSetBase::InsertNode(Node *N, void *InsertPos) { +void FoldingSetBase::InsertNode(Node *N, void *InsertPos, + const FoldingSetInfo &Info) { assert(!N->getNextInBucket()); // Do we need to grow the hashtable? if (NumNodes+1 > capacity()) { - GrowHashTable(); + GrowHashTable(Info); FoldingSetNodeID TempID; - InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); + InsertPos = GetBucketFor(Info.ComputeNodeHash(this, N, TempID), Buckets, + NumBuckets); } ++NumNodes; @@ -413,13 +420,15 @@ bool FoldingSetBase::RemoveNode(Node *N) { /// GetOrInsertNode - If there is an existing simple Node exactly /// equal to the specified node, return it. Otherwise, insert 'N' and it /// instead. -FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) { +FoldingSetBase::Node * +FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N, + const FoldingSetInfo &Info) { FoldingSetNodeID ID; - GetNodeProfile(N, ID); + Info.GetNodeProfile(this, N, ID); void *IP; - if (Node *E = FindNodeOrInsertPos(ID, IP)) + if (Node *E = FindNodeOrInsertPos(ID, IP, Info)) return E; - InsertNode(N, IP); + InsertNode(N, IP, Info); return N; } |