1//===- llvm/ADT/FoldingSet.h - Uniquing Hash Set ----------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines a hash set that can be used to remove duplication of nodes
11// in a graph. This code was originally created by Chris Lattner for use with
12// SelectionDAGCSEMap, but was isolated to provide use across the llvm code set.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_ADT_FOLDINGSET_H
17#define LLVM_ADT_FOLDINGSET_H
18
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/iterator.h"
21#include "llvm/Support/Allocator.h"
22#include <cassert>
23#include <cstddef>
24#include <cstdint>
25#include <utility>
26
27namespace llvm {
28
29/// This folding set used for two purposes:
30/// 1. Given information about a node we want to create, look up the unique
31/// instance of the node in the set. If the node already exists, return
32/// it, otherwise return the bucket it should be inserted into.
33/// 2. Given a node that has already been created, remove it from the set.
34///
35/// This class is implemented as a single-link chained hash table, where the
36/// "buckets" are actually the nodes themselves (the next pointer is in the
37/// node). The last node points back to the bucket to simplify node removal.
38///
39/// Any node that is to be included in the folding set must be a subclass of
40/// FoldingSetNode. The node class must also define a Profile method used to
41/// establish the unique bits of data for the node. The Profile method is
42/// passed a FoldingSetNodeID object which is used to gather the bits. Just
43/// call one of the Add* functions defined in the FoldingSetBase::NodeID class.
44/// NOTE: That the folding set does not own the nodes and it is the
45/// responsibility of the user to dispose of the nodes.
46///
47/// Eg.
48/// class MyNode : public FoldingSetNode {
49/// private:
50/// std::string Name;
51/// unsigned Value;
52/// public:
53/// MyNode(const char *N, unsigned V) : Name(N), Value(V) {}
54/// ...
55/// void Profile(FoldingSetNodeID &ID) const {
56/// ID.AddString(Name);
57/// ID.AddInteger(Value);
58/// }
59/// ...
60/// };
61///
62/// To define the folding set itself use the FoldingSet template;
63///
64/// Eg.
65/// FoldingSet<MyNode> MyFoldingSet;
66///
67/// Four public methods are available to manipulate the folding set;
68///
69/// 1) If you have an existing node that you want add to the set but unsure
70/// that the node might already exist then call;
71///
72/// MyNode *M = MyFoldingSet.GetOrInsertNode(N);
73///
74/// If The result is equal to the input then the node has been inserted.
75/// Otherwise, the result is the node existing in the folding set, and the
76/// input can be discarded (use the result instead.)
77///
78/// 2) If you are ready to construct a node but want to check if it already
79/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to
80/// check;
81///
82/// FoldingSetNodeID ID;
83/// ID.AddString(Name);
84/// ID.AddInteger(Value);
85/// void *InsertPoint;
86///
87/// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint);
88///
89/// If found then M with be non-NULL, else InsertPoint will point to where it
90/// should be inserted using InsertNode.
91///
92/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new
93/// node with FindNodeOrInsertPos;
94///
95/// InsertNode(N, InsertPoint);
96///
97/// 4) Finally, if you want to remove a node from the folding set call;
98///
99/// bool WasRemoved = RemoveNode(N);
100///
101/// The result indicates whether the node existed in the folding set.
102
103class FoldingSetNodeID;
104class StringRef;
105
106//===----------------------------------------------------------------------===//
107/// FoldingSetBase - Implements the folding set functionality. The main
108/// structure is an array of buckets. Each bucket is indexed by the hash of
109/// the nodes it contains. The bucket itself points to the nodes contained
110/// in the bucket via a singly linked list. The last node in the list points
111/// back to the bucket to facilitate node removal.
112///
113class FoldingSetBase {
114 virtual void anchor(); // Out of line virtual method.
115
116protected:
117 /// Buckets - Array of bucket chains.
118 void **Buckets;
119
120 /// NumBuckets - Length of the Buckets array. Always a power of 2.
121 unsigned NumBuckets;
122
123 /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
124 /// is greater than twice the number of buckets.
125 unsigned NumNodes;
126
127 explicit FoldingSetBase(unsigned Log2InitSize = 6);
128 FoldingSetBase(FoldingSetBase &&Arg);
129 FoldingSetBase &operator=(FoldingSetBase &&RHS);
130 ~FoldingSetBase();
131
132public:
133 //===--------------------------------------------------------------------===//
134 /// Node - This class is used to maintain the singly linked bucket list in
135 /// a folding set.
136 class Node {
137 private:
138 // NextInFoldingSetBucket - next link in the bucket list.
139 void *NextInFoldingSetBucket = nullptr;
140
141 public:
142 Node() = default;
143
144 // Accessors
145 void *getNextInBucket() const { return NextInFoldingSetBucket; }
146 void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; }
147 };
148
149 /// clear - Remove all nodes from the folding set.
150 void clear();
151
152 /// size - Returns the number of nodes in the folding set.
153 unsigned size() const { return NumNodes; }
154
155 /// empty - Returns true if there are no nodes in the folding set.
156 bool empty() const { return NumNodes == 0; }
157
158 /// reserve - Increase the number of buckets such that adding the
159 /// EltCount-th node won't cause a rebucket operation. reserve is permitted
160 /// to allocate more space than requested by EltCount.
161 void reserve(unsigned EltCount);
162
163 /// capacity - Returns the number of nodes permitted in the folding set
164 /// before a rebucket operation is performed.
165 unsigned capacity() {
166 // We allow a load factor of up to 2.0,
167 // so that means our capacity is NumBuckets * 2
168 return NumBuckets * 2;
169 }
170
171private:
172 /// GrowHashTable - Double the size of the hash table and rehash everything.
173 void GrowHashTable();
174
175 /// GrowBucketCount - resize the hash table and rehash everything.
176 /// NewBucketCount must be a power of two, and must be greater than the old
177 /// bucket count.
178 void GrowBucketCount(unsigned NewBucketCount);
179
180protected:
181 /// GetNodeProfile - Instantiations of the FoldingSet template implement
182 /// this function to gather data bits for the given node.
183 virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
184
185 /// NodeEquals - Instantiations of the FoldingSet template implement
186 /// this function to compare the given node with the given ID.
187 virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
188 FoldingSetNodeID &TempID) const=0;
189
190 /// ComputeNodeHash - Instantiations of the FoldingSet template implement
191 /// this function to compute a hash value for the given node.
192 virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0;
193
194 // The below methods are protected to encourage subclasses to provide a more
195 // type-safe API.
196
197 /// RemoveNode - Remove a node from the folding set, returning true if one
198 /// was removed or false if the node was not in the folding set.
199 bool RemoveNode(Node *N);
200
201 /// GetOrInsertNode - If there is an existing simple Node exactly
202 /// equal to the specified node, return it. Otherwise, insert 'N' and return
203 /// it instead.
204 Node *GetOrInsertNode(Node *N);
205
206 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
207 /// return it. If not, return the insertion token that will make insertion
208 /// faster.
209 Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
210
211 /// InsertNode - Insert the specified node into the folding set, knowing that
212 /// it is not already in the folding set. InsertPos must be obtained from
213 /// FindNodeOrInsertPos.
214 void InsertNode(Node *N, void *InsertPos);
215};
216
217//===----------------------------------------------------------------------===//
218
219/// DefaultFoldingSetTrait - This class provides default implementations
220/// for FoldingSetTrait implementations.
221template<typename T> struct DefaultFoldingSetTrait {
222 static void Profile(const T &X, FoldingSetNodeID &ID) {
223 X.Profile(ID);
224 }
225 static void Profile(T &X, FoldingSetNodeID &ID) {
226 X.Profile(ID);
227 }
228
229 // Equals - Test if the profile for X would match ID, using TempID
230 // to compute a temporary ID if necessary. The default implementation
231 // just calls Profile and does a regular comparison. Implementations
232 // can override this to provide more efficient implementations.
233 static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
234 FoldingSetNodeID &TempID);
235
236 // ComputeHash - Compute a hash value for X, using TempID to
237 // compute a temporary ID if necessary. The default implementation
238 // just calls Profile and does a regular hash computation.
239 // Implementations can override this to provide more efficient
240 // implementations.
241 static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID);
242};
243
244/// FoldingSetTrait - This trait class is used to define behavior of how
245/// to "profile" (in the FoldingSet parlance) an object of a given type.
246/// The default behavior is to invoke a 'Profile' method on an object, but
247/// through template specialization the behavior can be tailored for specific
248/// types. Combined with the FoldingSetNodeWrapper class, one can add objects
249/// to FoldingSets that were not originally designed to have that behavior.
250template<typename T> struct FoldingSetTrait
251 : public DefaultFoldingSetTrait<T> {};
252
253/// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
254/// for ContextualFoldingSets.
255template<typename T, typename Ctx>
256struct DefaultContextualFoldingSetTrait {
257 static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) {
258 X.Profile(ID, Context);
259 }
260
261 static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
262 FoldingSetNodeID &TempID, Ctx Context);
263 static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID,
264 Ctx Context);
265};
266
267/// ContextualFoldingSetTrait - Like FoldingSetTrait, but for
268/// ContextualFoldingSets.
269template<typename T, typename Ctx> struct ContextualFoldingSetTrait
270 : public DefaultContextualFoldingSetTrait<T, Ctx> {};
271
272//===--------------------------------------------------------------------===//
273/// FoldingSetNodeIDRef - This class describes a reference to an interned
274/// FoldingSetNodeID, which can be a useful to store node id data rather
275/// than using plain FoldingSetNodeIDs, since the 32-element SmallVector
276/// is often much larger than necessary, and the possibility of heap
277/// allocation means it requires a non-trivial destructor call.
278class FoldingSetNodeIDRef {
279 const unsigned *Data = nullptr;
280 size_t Size = 0;
281
282public:
283 FoldingSetNodeIDRef() = default;
284 FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
285
286 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
287 /// used to lookup the node in the FoldingSetBase.
288 unsigned ComputeHash() const;
289
290 bool operator==(FoldingSetNodeIDRef) const;
291
292 bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
293
294 /// Used to compare the "ordering" of two nodes as defined by the
295 /// profiled bits and their ordering defined by memcmp().
296 bool operator<(FoldingSetNodeIDRef) const;
297
298 const unsigned *getData() const { return Data; }
299 size_t getSize() const { return Size; }
300};
301
302//===--------------------------------------------------------------------===//
303/// FoldingSetNodeID - This class is used to gather all the unique data bits of
304/// a node. When all the bits are gathered this class is used to produce a
305/// hash value for the node.
306class FoldingSetNodeID {
307 /// Bits - Vector of all the data bits that make the node unique.
308 /// Use a SmallVector to avoid a heap allocation in the common case.
309 SmallVector<unsigned, 32> Bits;
310
311public:
312 FoldingSetNodeID() = default;
313
314 FoldingSetNodeID(FoldingSetNodeIDRef Ref)
315 : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {}
316
317 /// Add* - Add various data types to Bit data.
318 void AddPointer(const void *Ptr);
319 void AddInteger(signed I);
320 void AddInteger(unsigned I);
321 void AddInteger(long I);
322 void AddInteger(unsigned long I);
323 void AddInteger(long long I);
324 void AddInteger(unsigned long long I);
325 void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
326 void AddString(StringRef String);
327 void AddNodeID(const FoldingSetNodeID &ID);
328
329 template <typename T>
330 inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
331
332 /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
333 /// object to be used to compute a new profile.
334 inline void clear() { Bits.clear(); }
335
336 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
337 /// to lookup the node in the FoldingSetBase.
338 unsigned ComputeHash() const;
339
340 /// operator== - Used to compare two nodes to each other.
341 bool operator==(const FoldingSetNodeID &RHS) const;
342 bool operator==(const FoldingSetNodeIDRef RHS) const;
343
344 bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
345 bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
346
347 /// Used to compare the "ordering" of two nodes as defined by the
348 /// profiled bits and their ordering defined by memcmp().
349 bool operator<(const FoldingSetNodeID &RHS) const;
350 bool operator<(const FoldingSetNodeIDRef RHS) const;
351
352 /// Intern - Copy this node's data to a memory region allocated from the
353 /// given allocator and return a FoldingSetNodeIDRef describing the
354 /// interned data.
355 FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const;
356};
357
358// Convenience type to hide the implementation of the folding set.
359using FoldingSetNode = FoldingSetBase::Node;
360template<class T> class FoldingSetIterator;
361template<class T> class FoldingSetBucketIterator;
362
363// Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which
364// require the definition of FoldingSetNodeID.
365template<typename T>
366inline bool
367DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID,
368 unsigned /*IDHash*/,
369 FoldingSetNodeID &TempID) {
370 FoldingSetTrait<T>::Profile(X, TempID);
371 return TempID == ID;
372}
373template<typename T>
374inline unsigned
375DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) {
376 FoldingSetTrait<T>::Profile(X, TempID);
377 return TempID.ComputeHash();
378}
379template<typename T, typename Ctx>
380inline bool
381DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X,
382 const FoldingSetNodeID &ID,
383 unsigned /*IDHash*/,
384 FoldingSetNodeID &TempID,
385 Ctx Context) {
386 ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
387 return TempID == ID;
388}
389template<typename T, typename Ctx>
390inline unsigned
391DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X,
392 FoldingSetNodeID &TempID,
393 Ctx Context) {
394 ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
395 return TempID.ComputeHash();
396}
397
398//===----------------------------------------------------------------------===//
399/// FoldingSetImpl - An implementation detail that lets us share code between
400/// FoldingSet and ContextualFoldingSet.
401template <class T> class FoldingSetImpl : public FoldingSetBase {
402protected:
403 explicit FoldingSetImpl(unsigned Log2InitSize)
404 : FoldingSetBase(Log2InitSize) {}
405
406 FoldingSetImpl(FoldingSetImpl &&Arg) = default;
407 FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default;
408 ~FoldingSetImpl() = default;
409
410public:
411 using iterator = FoldingSetIterator<T>;
412
413 iterator begin() { return iterator(Buckets); }
414 iterator end() { return iterator(Buckets+NumBuckets); }
415
416 using const_iterator = FoldingSetIterator<const T>;
417
418 const_iterator begin() const { return const_iterator(Buckets); }
419 const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
420
421 using bucket_iterator = FoldingSetBucketIterator<T>;
422
423 bucket_iterator bucket_begin(unsigned hash) {
424 return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
425 }
426
427 bucket_iterator bucket_end(unsigned hash) {
428 return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
429 }
430
431 /// RemoveNode - Remove a node from the folding set, returning true if one
432 /// was removed or false if the node was not in the folding set.
433 bool RemoveNode(T *N) { return FoldingSetBase::RemoveNode(N); }
434
435 /// GetOrInsertNode - If there is an existing simple Node exactly
436 /// equal to the specified node, return it. Otherwise, insert 'N' and
437 /// return it instead.
438 T *GetOrInsertNode(T *N) {
439 return static_cast<T *>(FoldingSetBase::GetOrInsertNode(N));
440 }
441
442 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
443 /// return it. If not, return the insertion token that will make insertion
444 /// faster.
445 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
446 return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos));
447 }
448
449 /// InsertNode - Insert the specified node into the folding set, knowing that
450 /// it is not already in the folding set. InsertPos must be obtained from
451 /// FindNodeOrInsertPos.
452 void InsertNode(T *N, void *InsertPos) {
453 FoldingSetBase::InsertNode(N, InsertPos);
454 }
455
456 /// InsertNode - Insert the specified node into the folding set, knowing that
457 /// it is not already in the folding set.
458 void InsertNode(T *N) {
459 T *Inserted = GetOrInsertNode(N);
460 (void)Inserted;
461 assert(Inserted == N && "Node already inserted!");
462 }
463};
464
465//===----------------------------------------------------------------------===//
466/// FoldingSet - This template class is used to instantiate a specialized
467/// implementation of the folding set to the node class T. T must be a
468/// subclass of FoldingSetNode and implement a Profile function.
469///
470/// Note that this set type is movable and move-assignable. However, its
471/// moved-from state is not a valid state for anything other than
472/// move-assigning and destroying. This is primarily to enable movable APIs
473/// that incorporate these objects.
474template <class T> class FoldingSet final : public FoldingSetImpl<T> {
475 using Super = FoldingSetImpl<T>;
476 using Node = typename Super::Node;
477
478 /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
479 /// way to convert nodes into a unique specifier.
480 void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
481 T *TN = static_cast<T *>(N);
482 FoldingSetTrait<T>::Profile(*TN, ID);
483 }
484
485 /// NodeEquals - Instantiations may optionally provide a way to compare a
486 /// node with a specified ID.
487 bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
488 FoldingSetNodeID &TempID) const override {
489 T *TN = static_cast<T *>(N);
490 return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID);
491 }
492
493 /// ComputeNodeHash - Instantiations may optionally provide a way to compute a
494 /// hash value directly from a node.
495 unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
496 T *TN = static_cast<T *>(N);
497 return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
498 }
499
500public:
501 explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
502 FoldingSet(FoldingSet &&Arg) = default;
503 FoldingSet &operator=(FoldingSet &&RHS) = default;
504};
505
506//===----------------------------------------------------------------------===//
507/// ContextualFoldingSet - This template class is a further refinement
508/// of FoldingSet which provides a context argument when calling
509/// Profile on its nodes. Currently, that argument is fixed at
510/// initialization time.
511///
512/// T must be a subclass of FoldingSetNode and implement a Profile
513/// function with signature
514/// void Profile(FoldingSetNodeID &, Ctx);
515template <class T, class Ctx>
516class ContextualFoldingSet final : public FoldingSetImpl<T> {
517 // Unfortunately, this can't derive from FoldingSet<T> because the
518 // construction of the vtable for FoldingSet<T> requires
519 // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
520 // requires a single-argument T::Profile().
521
522 using Super = FoldingSetImpl<T>;
523 using Node = typename Super::Node;
524
525 Ctx Context;
526
527 /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
528 /// way to convert nodes into a unique specifier.
529 void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
530 T *TN = static_cast<T *>(N);
531 ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context);
532 }
533
534 bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
535 FoldingSetNodeID &TempID) const override {
536 T *TN = static_cast<T *>(N);
537 return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
538 Context);
539 }
540
541 unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
542 T *TN = static_cast<T *>(N);
543 return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
544 }
545
546public:
547 explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
548 : Super(Log2InitSize), Context(Context) {}
549
550 Ctx getContext() const { return Context; }
551};
552
553//===----------------------------------------------------------------------===//
554/// FoldingSetVector - This template class combines a FoldingSet and a vector
555/// to provide the interface of FoldingSet but with deterministic iteration
556/// order based on the insertion order. T must be a subclass of FoldingSetNode
557/// and implement a Profile function.
558template <class T, class VectorT = SmallVector<T*, 8>>
559class FoldingSetVector {
560 FoldingSet<T> Set;
561 VectorT Vector;
562
563public:
564 explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
565
566 using iterator = pointee_iterator<typename VectorT::iterator>;
567
568 iterator begin() { return Vector.begin(); }
569 iterator end() { return Vector.end(); }
570
571 using const_iterator = pointee_iterator<typename VectorT::const_iterator>;
572
573 const_iterator begin() const { return Vector.begin(); }
574 const_iterator end() const { return Vector.end(); }
575
576 /// clear - Remove all nodes from the folding set.
577 void clear() { Set.clear(); Vector.clear(); }
578
579 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
580 /// return it. If not, return the insertion token that will make insertion
581 /// faster.
582 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
583 return Set.FindNodeOrInsertPos(ID, InsertPos);
584 }
585
586 /// GetOrInsertNode - If there is an existing simple Node exactly
587 /// equal to the specified node, return it. Otherwise, insert 'N' and
588 /// return it instead.
589 T *GetOrInsertNode(T *N) {
590 T *Result = Set.GetOrInsertNode(N);
591 if (Result == N) Vector.push_back(N);
592 return Result;
593 }
594
595 /// InsertNode - Insert the specified node into the folding set, knowing that
596 /// it is not already in the folding set. InsertPos must be obtained from
597 /// FindNodeOrInsertPos.
598 void InsertNode(T *N, void *InsertPos) {
599 Set.InsertNode(N, InsertPos);
600 Vector.push_back(N);
601 }
602
603 /// InsertNode - Insert the specified node into the folding set, knowing that
604 /// it is not already in the folding set.
605 void InsertNode(T *N) {
606 Set.InsertNode(N);
607 Vector.push_back(N);
608 }
609
610 /// size - Returns the number of nodes in the folding set.
611 unsigned size() const { return Set.size(); }
612
613 /// empty - Returns true if there are no nodes in the folding set.
614 bool empty() const { return Set.empty(); }
615};
616
617//===----------------------------------------------------------------------===//
618/// FoldingSetIteratorImpl - This is the common iterator support shared by all
619/// folding sets, which knows how to walk the folding set hash table.
620class FoldingSetIteratorImpl {
621protected:
622 FoldingSetNode *NodePtr;
623
624 FoldingSetIteratorImpl(void **Bucket);
625
626 void advance();
627
628public:
629 bool operator==(const FoldingSetIteratorImpl &RHS) const {
630 return NodePtr == RHS.NodePtr;
631 }
632 bool operator!=(const FoldingSetIteratorImpl &RHS) const {
633 return NodePtr != RHS.NodePtr;
634 }
635};
636
637template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
638public:
639 explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
640
641 T &operator*() const {
642 return *static_cast<T*>(NodePtr);
643 }
644
645 T *operator->() const {
646 return static_cast<T*>(NodePtr);
647 }
648
649 inline FoldingSetIterator &operator++() { // Preincrement
650 advance();
651 return *this;
652 }
653 FoldingSetIterator operator++(int) { // Postincrement
654 FoldingSetIterator tmp = *this; ++*this; return tmp;
655 }
656};
657
658//===----------------------------------------------------------------------===//
659/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
660/// shared by all folding sets, which knows how to walk a particular bucket
661/// of a folding set hash table.
662class FoldingSetBucketIteratorImpl {
663protected:
664 void *Ptr;
665
666 explicit FoldingSetBucketIteratorImpl(void **Bucket);
667
668 FoldingSetBucketIteratorImpl(void **Bucket, bool) : Ptr(Bucket) {}
669
670 void advance() {
671 void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
672 uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
673 Ptr = reinterpret_cast<void*>(x);
674 }
675
676public:
677 bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
678 return Ptr == RHS.Ptr;
679 }
680 bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
681 return Ptr != RHS.Ptr;
682 }
683};
684
685template <class T>
686class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
687public:
688 explicit FoldingSetBucketIterator(void **Bucket) :
689 FoldingSetBucketIteratorImpl(Bucket) {}
690
691 FoldingSetBucketIterator(void **Bucket, bool) :
692 FoldingSetBucketIteratorImpl(Bucket, true) {}
693
694 T &operator*() const { return *static_cast<T*>(Ptr); }
695 T *operator->() const { return static_cast<T*>(Ptr); }
696
697 inline FoldingSetBucketIterator &operator++() { // Preincrement
698 advance();
699 return *this;
700 }
701 FoldingSetBucketIterator operator++(int) { // Postincrement
702 FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
703 }
704};
705
706//===----------------------------------------------------------------------===//
707/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
708/// types in an enclosing object so that they can be inserted into FoldingSets.
709template <typename T>
710class FoldingSetNodeWrapper : public FoldingSetNode {
711 T data;
712
713public:
714 template <typename... Ts>
715 explicit FoldingSetNodeWrapper(Ts &&... Args)
716 : data(std::forward<Ts>(Args)...) {}
717
718 void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); }
719
720 T &getValue() { return data; }
721 const T &getValue() const { return data; }
722
723 operator T&() { return data; }
724 operator const T&() const { return data; }
725};
726
727//===----------------------------------------------------------------------===//
728/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores
729/// a FoldingSetNodeID value rather than requiring the node to recompute it
730/// each time it is needed. This trades space for speed (which can be
731/// significant if the ID is long), and it also permits nodes to drop
732/// information that would otherwise only be required for recomputing an ID.
733class FastFoldingSetNode : public FoldingSetNode {
734 FoldingSetNodeID FastID;
735
736protected:
737 explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
738
739public:
740 void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
741};
742
743//===----------------------------------------------------------------------===//
744// Partial specializations of FoldingSetTrait.
745
746template<typename T> struct FoldingSetTrait<T*> {
747 static inline void Profile(T *X, FoldingSetNodeID &ID) {
748 ID.AddPointer(X);
749 }
750};
751template <typename T1, typename T2>
752struct FoldingSetTrait<std::pair<T1, T2>> {
753 static inline void Profile(const std::pair<T1, T2> &P,
754 FoldingSetNodeID &ID) {
755 ID.Add(P.first);
756 ID.Add(P.second);
757 }
758};
759
760} // end namespace llvm
761
762#endif // LLVM_ADT_FOLDINGSET_H
763