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

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