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

source code of llvm/include/llvm/ADT/FoldingSet.h