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