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