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