From 4d6bb2d89061da20e809f11c841a9ebcc25ae094 Mon Sep 17 00:00:00 2001 From: George Burgess IV Date: Mon, 12 Jun 2017 20:52:53 +0000 Subject: [PATCH] [ADT] Reduce duplication between {Contextual,}FoldingSet; NFC This is a precursor to another change (coming soon) that aims to make FoldingSet's API more type-safe. Without this, the type-safety change would just duplicate 4 more public methods between the already very similar classes. This renames FoldingSetImpl to FoldingSetBase so it's consistent with the FooBase -> FooImpl -> Foo convention we seem to have with other containers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@305231 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/FoldingSet.h | 165 +++++++++++++++------------------- lib/Support/FoldingSet.cpp | 42 ++++----- 2 files changed, 94 insertions(+), 113 deletions(-) diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index dab18297dd3..e20bdc8b9bf 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -40,7 +40,7 @@ namespace llvm { /// FoldingSetNode. The node class must also define a Profile method used to /// establish the unique bits of data for the node. The Profile method is /// passed a FoldingSetNodeID object which is used to gather the bits. Just -/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class. +/// call one of the Add* functions defined in the FoldingSetBase::NodeID class. /// NOTE: That the folding set does not own the nodes and it is the /// responsibility of the user to dispose of the nodes. /// @@ -104,13 +104,13 @@ class FoldingSetNodeID; class StringRef; //===----------------------------------------------------------------------===// -/// FoldingSetImpl - Implements the folding set functionality. The main +/// FoldingSetBase - Implements the folding set functionality. The main /// structure is an array of buckets. Each bucket is indexed by the hash of /// the nodes it contains. The bucket itself points to the nodes contained /// in the bucket via a singly linked list. The last node in the list points /// back to the bucket to facilitate node removal. /// -class FoldingSetImpl { +class FoldingSetBase { virtual void anchor(); // Out of line virtual method. protected: @@ -126,10 +126,10 @@ protected: /// is greater than twice the number of buckets. unsigned NumNodes; - explicit FoldingSetImpl(unsigned Log2InitSize = 6); - FoldingSetImpl(FoldingSetImpl &&Arg); - FoldingSetImpl &operator=(FoldingSetImpl &&RHS); - ~FoldingSetImpl(); + explicit FoldingSetBase(unsigned Log2InitSize = 6); + FoldingSetBase(FoldingSetBase &&Arg); + FoldingSetBase &operator=(FoldingSetBase &&RHS); + ~FoldingSetBase(); public: //===--------------------------------------------------------------------===// @@ -293,7 +293,7 @@ public: FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, - /// used to lookup the node in the FoldingSetImpl. + /// used to lookup the node in the FoldingSetBase. unsigned ComputeHash() const; bool operator==(FoldingSetNodeIDRef) const; @@ -345,7 +345,7 @@ public: inline void clear() { Bits.clear(); } /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used - /// to lookup the node in the FoldingSetImpl. + /// to lookup the node in the FoldingSetBase. unsigned ComputeHash() const; /// operator== - Used to compare two nodes to each other. @@ -368,7 +368,7 @@ public: }; // Convenience type to hide the implementation of the folding set. -typedef FoldingSetImpl::Node FoldingSetNode; +typedef FoldingSetBase::Node FoldingSetNode; template class FoldingSetIterator; template class FoldingSetBucketIterator; @@ -407,6 +407,52 @@ DefaultContextualFoldingSetTrait::ComputeHash(T &X, return TempID.ComputeHash(); } +//===----------------------------------------------------------------------===// +/// FoldingSetImpl - An implementation detail that lets us share code between +/// FoldingSet and ContextualFoldingSet. +template class FoldingSetImpl : public FoldingSetBase { +protected: + explicit FoldingSetImpl(unsigned Log2InitSize) + : FoldingSetBase(Log2InitSize) {} + + FoldingSetImpl(FoldingSetImpl &&Arg) = default; + FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default; + ~FoldingSetImpl() = default; + +public: + typedef FoldingSetIterator iterator; + iterator begin() { return iterator(Buckets); } + iterator end() { return iterator(Buckets+NumBuckets); } + + typedef FoldingSetIterator const_iterator; + const_iterator begin() const { return const_iterator(Buckets); } + const_iterator end() const { return const_iterator(Buckets+NumBuckets); } + + typedef FoldingSetBucketIterator bucket_iterator; + + bucket_iterator bucket_begin(unsigned hash) { + return bucket_iterator(Buckets + (hash & (NumBuckets-1))); + } + + bucket_iterator bucket_end(unsigned hash) { + return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); + } + + /// GetOrInsertNode - If there is an existing simple Node exactly + /// equal to the specified node, return it. Otherwise, insert 'N' and + /// return it instead. + T *GetOrInsertNode(Node *N) { + return static_cast(FoldingSetBase::GetOrInsertNode(N)); + } + + /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, + /// return it. If not, return the insertion token that will make insertion + /// faster. + T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { + return static_cast(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos)); + } +}; + //===----------------------------------------------------------------------===// /// FoldingSet - This template class is used to instantiate a specialized /// implementation of the folding set to the node class T. T must be a @@ -416,8 +462,10 @@ DefaultContextualFoldingSetTrait::ComputeHash(T &X, /// moved-from state is not a valid state for anything other than /// move-assigning and destroying. This is primarily to enable movable APIs /// that incorporate these objects. -template class FoldingSet final : public FoldingSetImpl { -private: +template class FoldingSet final : public FoldingSetImpl { + using Super = FoldingSetImpl; + using Node = typename Super::Node; + /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a /// way to convert nodes into a unique specifier. void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override { @@ -442,45 +490,10 @@ private: public: explicit FoldingSet(unsigned Log2InitSize = 6) - : FoldingSetImpl(Log2InitSize) {} - - FoldingSet(FoldingSet &&Arg) : FoldingSetImpl(std::move(Arg)) {} - FoldingSet &operator=(FoldingSet &&RHS) { - (void)FoldingSetImpl::operator=(std::move(RHS)); - return *this; - } - - typedef FoldingSetIterator iterator; - iterator begin() { return iterator(Buckets); } - iterator end() { return iterator(Buckets+NumBuckets); } - - typedef FoldingSetIterator const_iterator; - const_iterator begin() const { return const_iterator(Buckets); } - const_iterator end() const { return const_iterator(Buckets+NumBuckets); } - - typedef FoldingSetBucketIterator bucket_iterator; + : Super(Log2InitSize) {} - bucket_iterator bucket_begin(unsigned hash) { - return bucket_iterator(Buckets + (hash & (NumBuckets-1))); - } - - bucket_iterator bucket_end(unsigned hash) { - return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); - } - - /// GetOrInsertNode - If there is an existing simple Node exactly - /// equal to the specified node, return it. Otherwise, insert 'N' and - /// return it instead. - T *GetOrInsertNode(Node *N) { - return static_cast(FoldingSetImpl::GetOrInsertNode(N)); - } - - /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, - /// return it. If not, return the insertion token that will make insertion - /// faster. - T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { - return static_cast(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); - } + FoldingSet(FoldingSet &&Arg) = default; + FoldingSet &operator=(FoldingSet &&RHS) = default; }; //===----------------------------------------------------------------------===// @@ -493,74 +506,42 @@ public: /// function with signature /// void Profile(FoldingSetNodeID &, Ctx); template -class ContextualFoldingSet final : public FoldingSetImpl { +class ContextualFoldingSet final : public FoldingSetImpl { // Unfortunately, this can't derive from FoldingSet because the - // construction vtable for FoldingSet requires + // construction of the vtable for FoldingSet requires // FoldingSet::GetNodeProfile to be instantiated, which in turn // requires a single-argument T::Profile(). -private: + using Super = FoldingSetImpl; + using Node = typename Super::Node; + Ctx Context; /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a /// way to convert nodes into a unique specifier. - void GetNodeProfile(FoldingSetImpl::Node *N, - FoldingSetNodeID &ID) const override { + void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override { T *TN = static_cast(N); ContextualFoldingSetTrait::Profile(*TN, ID, Context); } - bool NodeEquals(FoldingSetImpl::Node *N, const FoldingSetNodeID &ID, - unsigned IDHash, FoldingSetNodeID &TempID) const override { + bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, + FoldingSetNodeID &TempID) const override { T *TN = static_cast(N); return ContextualFoldingSetTrait::Equals(*TN, ID, IDHash, TempID, Context); } - unsigned ComputeNodeHash(FoldingSetImpl::Node *N, - FoldingSetNodeID &TempID) const override { + unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override { T *TN = static_cast(N); return ContextualFoldingSetTrait::ComputeHash(*TN, TempID, Context); } public: explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) - : FoldingSetImpl(Log2InitSize), Context(Context) + : Super(Log2InitSize), Context(Context) {} Ctx getContext() const { return Context; } - - typedef FoldingSetIterator iterator; - iterator begin() { return iterator(Buckets); } - iterator end() { return iterator(Buckets+NumBuckets); } - - typedef FoldingSetIterator const_iterator; - const_iterator begin() const { return const_iterator(Buckets); } - const_iterator end() const { return const_iterator(Buckets+NumBuckets); } - - typedef FoldingSetBucketIterator bucket_iterator; - - bucket_iterator bucket_begin(unsigned hash) { - return bucket_iterator(Buckets + (hash & (NumBuckets-1))); - } - - bucket_iterator bucket_end(unsigned hash) { - return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); - } - - /// GetOrInsertNode - If there is an existing simple Node exactly - /// equal to the specified node, return it. Otherwise, insert 'N' - /// and return it instead. - T *GetOrInsertNode(Node *N) { - return static_cast(FoldingSetImpl::GetOrInsertNode(N)); - } - - /// FindNodeOrInsertPos - Look up the node specified by ID. If it - /// exists, return it. If not, return the insertion token that will - /// make insertion faster. - T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { - return static_cast(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); - } }; //===----------------------------------------------------------------------===// diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp index c9bca7f4c1a..4496d06a15f 100644 --- a/lib/Support/FoldingSet.cpp +++ b/lib/Support/FoldingSet.cpp @@ -26,7 +26,7 @@ using namespace llvm; // FoldingSetNodeIDRef Implementation /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, -/// used to lookup the node in the FoldingSetImpl. +/// used to lookup the node in the FoldingSetBase. unsigned FoldingSetNodeIDRef::ComputeHash() const { return static_cast(hash_combine_range(Data, Data+Size)); } @@ -142,7 +142,7 @@ void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { } /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to -/// lookup the node in the FoldingSetImpl. +/// lookup the node in the FoldingSetBase. unsigned FoldingSetNodeID::ComputeHash() const { return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); } @@ -180,7 +180,7 @@ FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { } //===----------------------------------------------------------------------===// -/// Helper functions for FoldingSetImpl. +/// Helper functions for FoldingSetBase. /// GetNextPtr - In order to save space, each bucket is a /// singly-linked-list. In order to make deletion more efficient, we make @@ -188,12 +188,12 @@ FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { /// The problem with this is that the start of the hash buckets are not /// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: /// use GetBucketPtr when this happens. -static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { +static FoldingSetBase::Node *GetNextPtr(void *NextInBucketPtr) { // The low bit is set if this is the pointer back to the bucket. if (reinterpret_cast(NextInBucketPtr) & 1) return nullptr; - return static_cast(NextInBucketPtr); + return static_cast(NextInBucketPtr); } @@ -221,11 +221,11 @@ static void **AllocateBuckets(unsigned NumBuckets) { } //===----------------------------------------------------------------------===// -// FoldingSetImpl Implementation +// FoldingSetBase Implementation -void FoldingSetImpl::anchor() {} +void FoldingSetBase::anchor() {} -FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { +FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) { assert(5 < Log2InitSize && Log2InitSize < 32 && "Initial hash table size out of range"); NumBuckets = 1 << Log2InitSize; @@ -233,14 +233,14 @@ FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { NumNodes = 0; } -FoldingSetImpl::FoldingSetImpl(FoldingSetImpl &&Arg) +FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg) : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) { Arg.Buckets = nullptr; Arg.NumBuckets = 0; Arg.NumNodes = 0; } -FoldingSetImpl &FoldingSetImpl::operator=(FoldingSetImpl &&RHS) { +FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) { free(Buckets); // This may be null if the set is in a moved-from state. Buckets = RHS.Buckets; NumBuckets = RHS.NumBuckets; @@ -251,11 +251,11 @@ FoldingSetImpl &FoldingSetImpl::operator=(FoldingSetImpl &&RHS) { return *this; } -FoldingSetImpl::~FoldingSetImpl() { +FoldingSetBase::~FoldingSetBase() { free(Buckets); } -void FoldingSetImpl::clear() { +void FoldingSetBase::clear() { // Set all but the last bucket to null pointers. memset(Buckets, 0, NumBuckets*sizeof(void*)); @@ -266,7 +266,7 @@ void FoldingSetImpl::clear() { NumNodes = 0; } -void FoldingSetImpl::GrowBucketCount(unsigned NewBucketCount) { +void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) { assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount"); assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!"); void **OldBuckets = Buckets; @@ -300,11 +300,11 @@ void FoldingSetImpl::GrowBucketCount(unsigned NewBucketCount) { /// GrowHashTable - Double the size of the hash table and rehash everything. /// -void FoldingSetImpl::GrowHashTable() { +void FoldingSetBase::GrowHashTable() { GrowBucketCount(NumBuckets * 2); } -void FoldingSetImpl::reserve(unsigned EltCount) { +void FoldingSetBase::reserve(unsigned EltCount) { // This will give us somewhere between EltCount / 2 and // EltCount buckets. This puts us in the load factor // range of 1.0 - 2.0. @@ -316,9 +316,9 @@ void FoldingSetImpl::reserve(unsigned EltCount) { /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, /// return it. If not, return the insertion token that will make insertion /// faster. -FoldingSetImpl::Node -*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, - void *&InsertPos) { +FoldingSetBase::Node * +FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID, + void *&InsertPos) { unsigned IDHash = ID.ComputeHash(); void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); void *Probe = *Bucket; @@ -342,7 +342,7 @@ FoldingSetImpl::Node /// 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 FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { +void FoldingSetBase::InsertNode(Node *N, void *InsertPos) { assert(!N->getNextInBucket()); // Do we need to grow the hashtable? if (NumNodes+1 > capacity()) { @@ -371,7 +371,7 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { /// RemoveNode - Remove a node from the folding set, returning true if one was /// removed or false if the node was not in the folding set. -bool FoldingSetImpl::RemoveNode(Node *N) { +bool FoldingSetBase::RemoveNode(Node *N) { // Because each bucket is a circular list, we don't need to compute N's hash // to remove it. void *Ptr = N->getNextInBucket(); @@ -412,7 +412,7 @@ bool FoldingSetImpl::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. -FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { +FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) { FoldingSetNodeID ID; GetNodeProfile(N, ID); void *IP; -- 2.40.0