1193323Sed//===-- llvm/ADT/FoldingSet.h - Uniquing Hash Set ---------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines a hash set that can be used to remove duplication of nodes 11193323Sed// in a graph. This code was originally created by Chris Lattner for use with 12193323Sed// SelectionDAGCSEMap, but was isolated to provide use across the llvm code set. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#ifndef LLVM_ADT_FOLDINGSET_H 17193323Sed#define LLVM_ADT_FOLDINGSET_H 18193323Sed 19193323Sed#include "llvm/ADT/SmallVector.h" 20198090Srdivacky#include "llvm/ADT/StringRef.h" 21252723Sdim#include "llvm/Support/DataTypes.h" 22193323Sed 23193323Sednamespace llvm { 24193323Sed class APFloat; 25193323Sed class APInt; 26205407Srdivacky class BumpPtrAllocator; 27193323Sed 28193323Sed/// This folding set used for two purposes: 29193323Sed/// 1. Given information about a node we want to create, look up the unique 30193323Sed/// instance of the node in the set. If the node already exists, return 31193323Sed/// it, otherwise return the bucket it should be inserted into. 32193323Sed/// 2. Given a node that has already been created, remove it from the set. 33193323Sed/// 34193323Sed/// This class is implemented as a single-link chained hash table, where the 35193323Sed/// "buckets" are actually the nodes themselves (the next pointer is in the 36193323Sed/// node). The last node points back to the bucket to simplify node removal. 37193323Sed/// 38193323Sed/// Any node that is to be included in the folding set must be a subclass of 39193323Sed/// FoldingSetNode. The node class must also define a Profile method used to 40193323Sed/// establish the unique bits of data for the node. The Profile method is 41193323Sed/// passed a FoldingSetNodeID object which is used to gather the bits. Just 42193323Sed/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class. 43193323Sed/// NOTE: That the folding set does not own the nodes and it is the 44193323Sed/// responsibility of the user to dispose of the nodes. 45193323Sed/// 46193323Sed/// Eg. 47193323Sed/// class MyNode : public FoldingSetNode { 48193323Sed/// private: 49193323Sed/// std::string Name; 50193323Sed/// unsigned Value; 51193323Sed/// public: 52193323Sed/// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} 53193323Sed/// ... 54195340Sed/// void Profile(FoldingSetNodeID &ID) const { 55193323Sed/// ID.AddString(Name); 56193323Sed/// ID.AddInteger(Value); 57212904Sdim/// } 58212904Sdim/// ... 59212904Sdim/// }; 60193323Sed/// 61193323Sed/// To define the folding set itself use the FoldingSet template; 62193323Sed/// 63193323Sed/// Eg. 64193323Sed/// FoldingSet<MyNode> MyFoldingSet; 65193323Sed/// 66193323Sed/// Four public methods are available to manipulate the folding set; 67193323Sed/// 68193323Sed/// 1) If you have an existing node that you want add to the set but unsure 69193323Sed/// that the node might already exist then call; 70193323Sed/// 71193323Sed/// MyNode *M = MyFoldingSet.GetOrInsertNode(N); 72193323Sed/// 73193323Sed/// If The result is equal to the input then the node has been inserted. 74193323Sed/// Otherwise, the result is the node existing in the folding set, and the 75193323Sed/// input can be discarded (use the result instead.) 76193323Sed/// 77193323Sed/// 2) If you are ready to construct a node but want to check if it already 78193323Sed/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to 79193323Sed/// check; 80193323Sed/// 81193323Sed/// FoldingSetNodeID ID; 82193323Sed/// ID.AddString(Name); 83193323Sed/// ID.AddInteger(Value); 84193323Sed/// void *InsertPoint; 85193323Sed/// 86193323Sed/// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); 87193323Sed/// 88193323Sed/// If found then M with be non-NULL, else InsertPoint will point to where it 89193323Sed/// should be inserted using InsertNode. 90193323Sed/// 91193323Sed/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new 92193323Sed/// node with FindNodeOrInsertPos; 93193323Sed/// 94193323Sed/// InsertNode(N, InsertPoint); 95193323Sed/// 96193323Sed/// 4) Finally, if you want to remove a node from the folding set call; 97193323Sed/// 98193323Sed/// bool WasRemoved = RemoveNode(N); 99193323Sed/// 100193323Sed/// The result indicates whether the node existed in the folding set. 101193323Sed 102193323Sedclass FoldingSetNodeID; 103193323Sed 104193323Sed//===----------------------------------------------------------------------===// 105193323Sed/// FoldingSetImpl - Implements the folding set functionality. The main 106193323Sed/// structure is an array of buckets. Each bucket is indexed by the hash of 107193323Sed/// the nodes it contains. The bucket itself points to the nodes contained 108193323Sed/// in the bucket via a singly linked list. The last node in the list points 109193323Sed/// back to the bucket to facilitate node removal. 110193323Sed/// 111193323Sedclass FoldingSetImpl { 112193323Sedprotected: 113193323Sed /// Buckets - Array of bucket chains. 114193323Sed /// 115193323Sed void **Buckets; 116193323Sed 117193323Sed /// NumBuckets - Length of the Buckets array. Always a power of 2. 118193323Sed /// 119193323Sed unsigned NumBuckets; 120193323Sed 121193323Sed /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 122193323Sed /// is greater than twice the number of buckets. 123193323Sed unsigned NumNodes; 124193323Sed 125193323Sedpublic: 126193323Sed explicit FoldingSetImpl(unsigned Log2InitSize = 6); 127193323Sed virtual ~FoldingSetImpl(); 128193323Sed 129193323Sed //===--------------------------------------------------------------------===// 130193323Sed /// Node - This class is used to maintain the singly linked bucket list in 131193323Sed /// a folding set. 132193323Sed /// 133193323Sed class Node { 134193323Sed private: 135193323Sed // NextInFoldingSetBucket - next link in the bucket list. 136193323Sed void *NextInFoldingSetBucket; 137193323Sed 138193323Sed public: 139193323Sed 140193323Sed Node() : NextInFoldingSetBucket(0) {} 141193323Sed 142193323Sed // Accessors 143193323Sed void *getNextInBucket() const { return NextInFoldingSetBucket; } 144193323Sed void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 145193323Sed }; 146193323Sed 147193323Sed /// clear - Remove all nodes from the folding set. 148193323Sed void clear(); 149193323Sed 150193323Sed /// RemoveNode - Remove a node from the folding set, returning true if one 151193323Sed /// was removed or false if the node was not in the folding set. 152193323Sed bool RemoveNode(Node *N); 153193323Sed 154193323Sed /// GetOrInsertNode - If there is an existing simple Node exactly 155193323Sed /// equal to the specified node, return it. Otherwise, insert 'N' and return 156193323Sed /// it instead. 157193323Sed Node *GetOrInsertNode(Node *N); 158193323Sed 159193323Sed /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 160193323Sed /// return it. If not, return the insertion token that will make insertion 161193323Sed /// faster. 162193323Sed Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 163193323Sed 164193323Sed /// InsertNode - Insert the specified node into the folding set, knowing that 165193323Sed /// it is not already in the folding set. InsertPos must be obtained from 166193323Sed /// FindNodeOrInsertPos. 167193323Sed void InsertNode(Node *N, void *InsertPos); 168193323Sed 169210299Sed /// InsertNode - Insert the specified node into the folding set, knowing that 170210299Sed /// it is not already in the folding set. 171210299Sed void InsertNode(Node *N) { 172210299Sed Node *Inserted = GetOrInsertNode(N); 173210299Sed (void)Inserted; 174210299Sed assert(Inserted == N && "Node already inserted!"); 175210299Sed } 176210299Sed 177193323Sed /// size - Returns the number of nodes in the folding set. 178193323Sed unsigned size() const { return NumNodes; } 179193323Sed 180193323Sed /// empty - Returns true if there are no nodes in the folding set. 181193323Sed bool empty() const { return NumNodes == 0; } 182193323Sed 183193323Sedprivate: 184193323Sed 185193323Sed /// GrowHashTable - Double the size of the hash table and rehash everything. 186193323Sed /// 187193323Sed void GrowHashTable(); 188193323Sed 189193323Sedprotected: 190193323Sed 191193323Sed /// GetNodeProfile - Instantiations of the FoldingSet template implement 192193323Sed /// this function to gather data bits for the given node. 193212904Sdim virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0; 194212904Sdim /// NodeEquals - Instantiations of the FoldingSet template implement 195212904Sdim /// this function to compare the given node with the given ID. 196235633Sdim virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, 197212904Sdim FoldingSetNodeID &TempID) const=0; 198235633Sdim /// ComputeNodeHash - Instantiations of the FoldingSet template implement 199212904Sdim /// this function to compute a hash value for the given node. 200235633Sdim virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0; 201193323Sed}; 202193323Sed 203193323Sed//===----------------------------------------------------------------------===// 204212904Sdim 205212904Sdimtemplate<typename T> struct FoldingSetTrait; 206212904Sdim 207212904Sdim/// DefaultFoldingSetTrait - This class provides default implementations 208212904Sdim/// for FoldingSetTrait implementations. 209212904Sdim/// 210212904Sdimtemplate<typename T> struct DefaultFoldingSetTrait { 211221345Sdim static void Profile(const T &X, FoldingSetNodeID &ID) { 212212904Sdim X.Profile(ID); 213212904Sdim } 214221345Sdim static void Profile(T &X, FoldingSetNodeID &ID) { 215212904Sdim X.Profile(ID); 216212904Sdim } 217212904Sdim 218212904Sdim // Equals - Test if the profile for X would match ID, using TempID 219212904Sdim // to compute a temporary ID if necessary. The default implementation 220212904Sdim // just calls Profile and does a regular comparison. Implementations 221212904Sdim // can override this to provide more efficient implementations. 222235633Sdim static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 223212904Sdim FoldingSetNodeID &TempID); 224212904Sdim 225212904Sdim // ComputeHash - Compute a hash value for X, using TempID to 226212904Sdim // compute a temporary ID if necessary. The default implementation 227212904Sdim // just calls Profile and does a regular hash computation. 228212904Sdim // Implementations can override this to provide more efficient 229212904Sdim // implementations. 230212904Sdim static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID); 231212904Sdim}; 232212904Sdim 233193323Sed/// FoldingSetTrait - This trait class is used to define behavior of how 234212904Sdim/// to "profile" (in the FoldingSet parlance) an object of a given type. 235212904Sdim/// The default behavior is to invoke a 'Profile' method on an object, but 236212904Sdim/// through template specialization the behavior can be tailored for specific 237212904Sdim/// types. Combined with the FoldingSetNodeWrapper class, one can add objects 238212904Sdim/// to FoldingSets that were not originally designed to have that behavior. 239212904Sdimtemplate<typename T> struct FoldingSetTrait 240212904Sdim : public DefaultFoldingSetTrait<T> {}; 241212904Sdim 242212904Sdimtemplate<typename T, typename Ctx> struct ContextualFoldingSetTrait; 243212904Sdim 244212904Sdim/// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but 245212904Sdim/// for ContextualFoldingSets. 246212904Sdimtemplate<typename T, typename Ctx> 247212904Sdimstruct DefaultContextualFoldingSetTrait { 248212904Sdim static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { 249210299Sed X.Profile(ID, Context); 250210299Sed } 251235633Sdim static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 252212904Sdim FoldingSetNodeID &TempID, Ctx Context); 253212904Sdim static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, 254212904Sdim Ctx Context); 255193323Sed}; 256193323Sed 257212904Sdim/// ContextualFoldingSetTrait - Like FoldingSetTrait, but for 258212904Sdim/// ContextualFoldingSets. 259212904Sdimtemplate<typename T, typename Ctx> struct ContextualFoldingSetTrait 260212904Sdim : public DefaultContextualFoldingSetTrait<T, Ctx> {}; 261212904Sdim 262193323Sed//===--------------------------------------------------------------------===// 263205407Srdivacky/// FoldingSetNodeIDRef - This class describes a reference to an interned 264205407Srdivacky/// FoldingSetNodeID, which can be a useful to store node id data rather 265205407Srdivacky/// than using plain FoldingSetNodeIDs, since the 32-element SmallVector 266205407Srdivacky/// is often much larger than necessary, and the possibility of heap 267205407Srdivacky/// allocation means it requires a non-trivial destructor call. 268205407Srdivackyclass FoldingSetNodeIDRef { 269221345Sdim const unsigned *Data; 270205407Srdivacky size_t Size; 271205407Srdivackypublic: 272205407Srdivacky FoldingSetNodeIDRef() : Data(0), Size(0) {} 273212904Sdim FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} 274205407Srdivacky 275212904Sdim /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 276212904Sdim /// used to lookup the node in the FoldingSetImpl. 277212904Sdim unsigned ComputeHash() const; 278212904Sdim 279212904Sdim bool operator==(FoldingSetNodeIDRef) const; 280212904Sdim 281245431Sdim /// Used to compare the "ordering" of two nodes as defined by the 282245431Sdim /// profiled bits and their ordering defined by memcmp(). 283245431Sdim bool operator<(FoldingSetNodeIDRef) const; 284245431Sdim 285212904Sdim const unsigned *getData() const { return Data; } 286205407Srdivacky size_t getSize() const { return Size; } 287205407Srdivacky}; 288205407Srdivacky 289205407Srdivacky//===--------------------------------------------------------------------===// 290193323Sed/// FoldingSetNodeID - This class is used to gather all the unique data bits of 291193323Sed/// a node. When all the bits are gathered this class is used to produce a 292193323Sed/// hash value for the node. 293193323Sed/// 294193323Sedclass FoldingSetNodeID { 295193323Sed /// Bits - Vector of all the data bits that make the node unique. 296193323Sed /// Use a SmallVector to avoid a heap allocation in the common case. 297193323Sed SmallVector<unsigned, 32> Bits; 298193323Sed 299193323Sedpublic: 300193323Sed FoldingSetNodeID() {} 301193323Sed 302205407Srdivacky FoldingSetNodeID(FoldingSetNodeIDRef Ref) 303205407Srdivacky : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {} 304193323Sed 305193323Sed /// Add* - Add various data types to Bit data. 306193323Sed /// 307193323Sed void AddPointer(const void *Ptr); 308193323Sed void AddInteger(signed I); 309193323Sed void AddInteger(unsigned I); 310193323Sed void AddInteger(long I); 311193323Sed void AddInteger(unsigned long I); 312193323Sed void AddInteger(long long I); 313193323Sed void AddInteger(unsigned long long I); 314193323Sed void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); } 315198090Srdivacky void AddString(StringRef String); 316221345Sdim void AddNodeID(const FoldingSetNodeID &ID); 317193323Sed 318193323Sed template <typename T> 319221345Sdim inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); } 320193323Sed 321193323Sed /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID 322212904Sdim /// object to be used to compute a new profile. 323193323Sed inline void clear() { Bits.clear(); } 324193323Sed 325193323Sed /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used 326212904Sdim /// to lookup the node in the FoldingSetImpl. 327193323Sed unsigned ComputeHash() const; 328193323Sed 329193323Sed /// operator== - Used to compare two nodes to each other. 330193323Sed /// 331193323Sed bool operator==(const FoldingSetNodeID &RHS) const; 332212904Sdim bool operator==(const FoldingSetNodeIDRef RHS) const; 333205407Srdivacky 334245431Sdim /// Used to compare the "ordering" of two nodes as defined by the 335245431Sdim /// profiled bits and their ordering defined by memcmp(). 336245431Sdim bool operator<(const FoldingSetNodeID &RHS) const; 337245431Sdim bool operator<(const FoldingSetNodeIDRef RHS) const; 338245431Sdim 339205407Srdivacky /// Intern - Copy this node's data to a memory region allocated from the 340205407Srdivacky /// given allocator and return a FoldingSetNodeIDRef describing the 341205407Srdivacky /// interned data. 342205407Srdivacky FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const; 343193323Sed}; 344193323Sed 345193323Sed// Convenience type to hide the implementation of the folding set. 346193323Sedtypedef FoldingSetImpl::Node FoldingSetNode; 347193323Sedtemplate<class T> class FoldingSetIterator; 348193323Sedtemplate<class T> class FoldingSetBucketIterator; 349193323Sed 350212904Sdim// Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which 351212904Sdim// require the definition of FoldingSetNodeID. 352212904Sdimtemplate<typename T> 353212904Sdiminline bool 354212904SdimDefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID, 355263509Sdim unsigned /*IDHash*/, 356263509Sdim FoldingSetNodeID &TempID) { 357212904Sdim FoldingSetTrait<T>::Profile(X, TempID); 358212904Sdim return TempID == ID; 359212904Sdim} 360212904Sdimtemplate<typename T> 361212904Sdiminline unsigned 362212904SdimDefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) { 363212904Sdim FoldingSetTrait<T>::Profile(X, TempID); 364212904Sdim return TempID.ComputeHash(); 365212904Sdim} 366212904Sdimtemplate<typename T, typename Ctx> 367212904Sdiminline bool 368212904SdimDefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X, 369212904Sdim const FoldingSetNodeID &ID, 370263509Sdim unsigned /*IDHash*/, 371212904Sdim FoldingSetNodeID &TempID, 372212904Sdim Ctx Context) { 373212904Sdim ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 374212904Sdim return TempID == ID; 375212904Sdim} 376212904Sdimtemplate<typename T, typename Ctx> 377212904Sdiminline unsigned 378212904SdimDefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X, 379212904Sdim FoldingSetNodeID &TempID, 380212904Sdim Ctx Context) { 381212904Sdim ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 382212904Sdim return TempID.ComputeHash(); 383212904Sdim} 384212904Sdim 385193323Sed//===----------------------------------------------------------------------===// 386193323Sed/// FoldingSet - This template class is used to instantiate a specialized 387193323Sed/// implementation of the folding set to the node class T. T must be a 388193323Sed/// subclass of FoldingSetNode and implement a Profile function. 389193323Sed/// 390193323Sedtemplate<class T> class FoldingSet : public FoldingSetImpl { 391193323Sedprivate: 392193323Sed /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 393193323Sed /// way to convert nodes into a unique specifier. 394212904Sdim virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const { 395193323Sed T *TN = static_cast<T *>(N); 396212904Sdim FoldingSetTrait<T>::Profile(*TN, ID); 397193323Sed } 398212904Sdim /// NodeEquals - Instantiations may optionally provide a way to compare a 399212904Sdim /// node with a specified ID. 400235633Sdim virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, 401212904Sdim FoldingSetNodeID &TempID) const { 402212904Sdim T *TN = static_cast<T *>(N); 403235633Sdim return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID); 404212904Sdim } 405235633Sdim /// ComputeNodeHash - Instantiations may optionally provide a way to compute a 406212904Sdim /// hash value directly from a node. 407235633Sdim virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const { 408212904Sdim T *TN = static_cast<T *>(N); 409212904Sdim return FoldingSetTrait<T>::ComputeHash(*TN, TempID); 410212904Sdim } 411193323Sed 412193323Sedpublic: 413193323Sed explicit FoldingSet(unsigned Log2InitSize = 6) 414193323Sed : FoldingSetImpl(Log2InitSize) 415193323Sed {} 416193323Sed 417193323Sed typedef FoldingSetIterator<T> iterator; 418193323Sed iterator begin() { return iterator(Buckets); } 419193323Sed iterator end() { return iterator(Buckets+NumBuckets); } 420193323Sed 421193323Sed typedef FoldingSetIterator<const T> const_iterator; 422193323Sed const_iterator begin() const { return const_iterator(Buckets); } 423193323Sed const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 424193323Sed 425193323Sed typedef FoldingSetBucketIterator<T> bucket_iterator; 426193323Sed 427193323Sed bucket_iterator bucket_begin(unsigned hash) { 428193323Sed return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 429193323Sed } 430193323Sed 431193323Sed bucket_iterator bucket_end(unsigned hash) { 432193323Sed return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 433193323Sed } 434193323Sed 435193323Sed /// GetOrInsertNode - If there is an existing simple Node exactly 436193323Sed /// equal to the specified node, return it. Otherwise, insert 'N' and 437193323Sed /// return it instead. 438193323Sed T *GetOrInsertNode(Node *N) { 439193323Sed return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 440193323Sed } 441193323Sed 442193323Sed /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 443193323Sed /// return it. If not, return the insertion token that will make insertion 444193323Sed /// faster. 445193323Sed T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 446193323Sed return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 447193323Sed } 448193323Sed}; 449193323Sed 450193323Sed//===----------------------------------------------------------------------===// 451210299Sed/// ContextualFoldingSet - This template class is a further refinement 452210299Sed/// of FoldingSet which provides a context argument when calling 453210299Sed/// Profile on its nodes. Currently, that argument is fixed at 454210299Sed/// initialization time. 455210299Sed/// 456210299Sed/// T must be a subclass of FoldingSetNode and implement a Profile 457210299Sed/// function with signature 458210299Sed/// void Profile(llvm::FoldingSetNodeID &, Ctx); 459210299Sedtemplate <class T, class Ctx> 460210299Sedclass ContextualFoldingSet : public FoldingSetImpl { 461210299Sed // Unfortunately, this can't derive from FoldingSet<T> because the 462210299Sed // construction vtable for FoldingSet<T> requires 463210299Sed // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn 464210299Sed // requires a single-argument T::Profile(). 465210299Sed 466210299Sedprivate: 467210299Sed Ctx Context; 468210299Sed 469210299Sed /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 470210299Sed /// way to convert nodes into a unique specifier. 471212904Sdim virtual void GetNodeProfile(FoldingSetImpl::Node *N, 472212904Sdim FoldingSetNodeID &ID) const { 473210299Sed T *TN = static_cast<T *>(N); 474212904Sdim ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context); 475210299Sed } 476212904Sdim virtual bool NodeEquals(FoldingSetImpl::Node *N, 477235633Sdim const FoldingSetNodeID &ID, unsigned IDHash, 478212904Sdim FoldingSetNodeID &TempID) const { 479212904Sdim T *TN = static_cast<T *>(N); 480235633Sdim return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID, 481235633Sdim Context); 482212904Sdim } 483212904Sdim virtual unsigned ComputeNodeHash(FoldingSetImpl::Node *N, 484212904Sdim FoldingSetNodeID &TempID) const { 485212904Sdim T *TN = static_cast<T *>(N); 486212904Sdim return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context); 487212904Sdim } 488210299Sed 489210299Sedpublic: 490210299Sed explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) 491210299Sed : FoldingSetImpl(Log2InitSize), Context(Context) 492210299Sed {} 493210299Sed 494210299Sed Ctx getContext() const { return Context; } 495210299Sed 496210299Sed 497210299Sed typedef FoldingSetIterator<T> iterator; 498210299Sed iterator begin() { return iterator(Buckets); } 499210299Sed iterator end() { return iterator(Buckets+NumBuckets); } 500210299Sed 501210299Sed typedef FoldingSetIterator<const T> const_iterator; 502210299Sed const_iterator begin() const { return const_iterator(Buckets); } 503210299Sed const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 504210299Sed 505210299Sed typedef FoldingSetBucketIterator<T> bucket_iterator; 506210299Sed 507210299Sed bucket_iterator bucket_begin(unsigned hash) { 508210299Sed return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 509210299Sed } 510210299Sed 511210299Sed bucket_iterator bucket_end(unsigned hash) { 512210299Sed return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 513210299Sed } 514210299Sed 515210299Sed /// GetOrInsertNode - If there is an existing simple Node exactly 516210299Sed /// equal to the specified node, return it. Otherwise, insert 'N' 517210299Sed /// and return it instead. 518210299Sed T *GetOrInsertNode(Node *N) { 519210299Sed return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 520210299Sed } 521210299Sed 522210299Sed /// FindNodeOrInsertPos - Look up the node specified by ID. If it 523210299Sed /// exists, return it. If not, return the insertion token that will 524210299Sed /// make insertion faster. 525210299Sed T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 526210299Sed return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 527210299Sed } 528210299Sed}; 529210299Sed 530210299Sed//===----------------------------------------------------------------------===// 531245431Sdim/// FoldingSetVectorIterator - This implements an iterator for 532245431Sdim/// FoldingSetVector. It is only necessary because FoldingSetIterator provides 533245431Sdim/// a value_type of T, while the vector in FoldingSetVector exposes 534245431Sdim/// a value_type of T*. Fortunately, FoldingSetIterator doesn't expose very 535245431Sdim/// much besides operator* and operator->, so we just wrap the inner vector 536245431Sdim/// iterator and perform the extra dereference. 537245431Sdimtemplate <class T, class VectorIteratorT> 538245431Sdimclass FoldingSetVectorIterator { 539245431Sdim // Provide a typedef to workaround the lack of correct injected class name 540245431Sdim // support in older GCCs. 541245431Sdim typedef FoldingSetVectorIterator<T, VectorIteratorT> SelfT; 542245431Sdim 543245431Sdim VectorIteratorT Iterator; 544245431Sdim 545245431Sdimpublic: 546245431Sdim FoldingSetVectorIterator(VectorIteratorT I) : Iterator(I) {} 547245431Sdim 548245431Sdim bool operator==(const SelfT &RHS) const { 549245431Sdim return Iterator == RHS.Iterator; 550245431Sdim } 551245431Sdim bool operator!=(const SelfT &RHS) const { 552245431Sdim return Iterator != RHS.Iterator; 553245431Sdim } 554245431Sdim 555245431Sdim T &operator*() const { return **Iterator; } 556245431Sdim 557245431Sdim T *operator->() const { return *Iterator; } 558245431Sdim 559245431Sdim inline SelfT &operator++() { 560245431Sdim ++Iterator; 561245431Sdim return *this; 562245431Sdim } 563245431Sdim SelfT operator++(int) { 564245431Sdim SelfT tmp = *this; 565245431Sdim ++*this; 566245431Sdim return tmp; 567245431Sdim } 568245431Sdim}; 569245431Sdim 570245431Sdim//===----------------------------------------------------------------------===// 571245431Sdim/// FoldingSetVector - This template class combines a FoldingSet and a vector 572245431Sdim/// to provide the interface of FoldingSet but with deterministic iteration 573245431Sdim/// order based on the insertion order. T must be a subclass of FoldingSetNode 574245431Sdim/// and implement a Profile function. 575245431Sdimtemplate <class T, class VectorT = SmallVector<T*, 8> > 576245431Sdimclass FoldingSetVector { 577245431Sdim FoldingSet<T> Set; 578245431Sdim VectorT Vector; 579245431Sdim 580245431Sdimpublic: 581245431Sdim explicit FoldingSetVector(unsigned Log2InitSize = 6) 582245431Sdim : Set(Log2InitSize) { 583245431Sdim } 584245431Sdim 585245431Sdim typedef FoldingSetVectorIterator<T, typename VectorT::iterator> iterator; 586245431Sdim iterator begin() { return Vector.begin(); } 587245431Sdim iterator end() { return Vector.end(); } 588245431Sdim 589245431Sdim typedef FoldingSetVectorIterator<const T, typename VectorT::const_iterator> 590245431Sdim const_iterator; 591245431Sdim const_iterator begin() const { return Vector.begin(); } 592245431Sdim const_iterator end() const { return Vector.end(); } 593245431Sdim 594245431Sdim /// clear - Remove all nodes from the folding set. 595245431Sdim void clear() { Set.clear(); Vector.clear(); } 596245431Sdim 597245431Sdim /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 598245431Sdim /// return it. If not, return the insertion token that will make insertion 599245431Sdim /// faster. 600245431Sdim T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 601245431Sdim return Set.FindNodeOrInsertPos(ID, InsertPos); 602245431Sdim } 603245431Sdim 604245431Sdim /// GetOrInsertNode - If there is an existing simple Node exactly 605245431Sdim /// equal to the specified node, return it. Otherwise, insert 'N' and 606245431Sdim /// return it instead. 607245431Sdim T *GetOrInsertNode(T *N) { 608245431Sdim T *Result = Set.GetOrInsertNode(N); 609245431Sdim if (Result == N) Vector.push_back(N); 610245431Sdim return Result; 611245431Sdim } 612245431Sdim 613245431Sdim /// InsertNode - Insert the specified node into the folding set, knowing that 614245431Sdim /// it is not already in the folding set. InsertPos must be obtained from 615245431Sdim /// FindNodeOrInsertPos. 616245431Sdim void InsertNode(T *N, void *InsertPos) { 617245431Sdim Set.InsertNode(N, InsertPos); 618245431Sdim Vector.push_back(N); 619245431Sdim } 620245431Sdim 621245431Sdim /// InsertNode - Insert the specified node into the folding set, knowing that 622245431Sdim /// it is not already in the folding set. 623245431Sdim void InsertNode(T *N) { 624245431Sdim Set.InsertNode(N); 625245431Sdim Vector.push_back(N); 626245431Sdim } 627245431Sdim 628245431Sdim /// size - Returns the number of nodes in the folding set. 629245431Sdim unsigned size() const { return Set.size(); } 630245431Sdim 631245431Sdim /// empty - Returns true if there are no nodes in the folding set. 632245431Sdim bool empty() const { return Set.empty(); } 633245431Sdim}; 634245431Sdim 635245431Sdim//===----------------------------------------------------------------------===// 636193323Sed/// FoldingSetIteratorImpl - This is the common iterator support shared by all 637193323Sed/// folding sets, which knows how to walk the folding set hash table. 638193323Sedclass FoldingSetIteratorImpl { 639193323Sedprotected: 640193323Sed FoldingSetNode *NodePtr; 641193323Sed FoldingSetIteratorImpl(void **Bucket); 642193323Sed void advance(); 643193323Sed 644193323Sedpublic: 645193323Sed bool operator==(const FoldingSetIteratorImpl &RHS) const { 646193323Sed return NodePtr == RHS.NodePtr; 647193323Sed } 648193323Sed bool operator!=(const FoldingSetIteratorImpl &RHS) const { 649193323Sed return NodePtr != RHS.NodePtr; 650193323Sed } 651193323Sed}; 652193323Sed 653193323Sed 654193323Sedtemplate<class T> 655193323Sedclass FoldingSetIterator : public FoldingSetIteratorImpl { 656193323Sedpublic: 657193323Sed explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} 658193323Sed 659193323Sed T &operator*() const { 660193323Sed return *static_cast<T*>(NodePtr); 661193323Sed } 662193323Sed 663193323Sed T *operator->() const { 664193323Sed return static_cast<T*>(NodePtr); 665193323Sed } 666193323Sed 667221345Sdim inline FoldingSetIterator &operator++() { // Preincrement 668193323Sed advance(); 669193323Sed return *this; 670193323Sed } 671193323Sed FoldingSetIterator operator++(int) { // Postincrement 672193323Sed FoldingSetIterator tmp = *this; ++*this; return tmp; 673193323Sed } 674193323Sed}; 675193323Sed 676193323Sed//===----------------------------------------------------------------------===// 677193323Sed/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support 678212904Sdim/// shared by all folding sets, which knows how to walk a particular bucket 679212904Sdim/// of a folding set hash table. 680193323Sed 681193323Sedclass FoldingSetBucketIteratorImpl { 682193323Sedprotected: 683193323Sed void *Ptr; 684193323Sed 685193323Sed explicit FoldingSetBucketIteratorImpl(void **Bucket); 686193323Sed 687193323Sed FoldingSetBucketIteratorImpl(void **Bucket, bool) 688193323Sed : Ptr(Bucket) {} 689193323Sed 690193323Sed void advance() { 691193323Sed void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket(); 692193323Sed uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1; 693193323Sed Ptr = reinterpret_cast<void*>(x); 694193323Sed } 695193323Sed 696193323Sedpublic: 697193323Sed bool operator==(const FoldingSetBucketIteratorImpl &RHS) const { 698193323Sed return Ptr == RHS.Ptr; 699193323Sed } 700193323Sed bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const { 701193323Sed return Ptr != RHS.Ptr; 702193323Sed } 703193323Sed}; 704193323Sed 705193323Sed 706193323Sedtemplate<class T> 707193323Sedclass FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { 708193323Sedpublic: 709193323Sed explicit FoldingSetBucketIterator(void **Bucket) : 710193323Sed FoldingSetBucketIteratorImpl(Bucket) {} 711193323Sed 712193323Sed FoldingSetBucketIterator(void **Bucket, bool) : 713193323Sed FoldingSetBucketIteratorImpl(Bucket, true) {} 714193323Sed 715221345Sdim T &operator*() const { return *static_cast<T*>(Ptr); } 716221345Sdim T *operator->() const { return static_cast<T*>(Ptr); } 717193323Sed 718221345Sdim inline FoldingSetBucketIterator &operator++() { // Preincrement 719193323Sed advance(); 720193323Sed return *this; 721193323Sed } 722193323Sed FoldingSetBucketIterator operator++(int) { // Postincrement 723193323Sed FoldingSetBucketIterator tmp = *this; ++*this; return tmp; 724193323Sed } 725193323Sed}; 726193323Sed 727193323Sed//===----------------------------------------------------------------------===// 728193323Sed/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary 729193323Sed/// types in an enclosing object so that they can be inserted into FoldingSets. 730193323Sedtemplate <typename T> 731193323Sedclass FoldingSetNodeWrapper : public FoldingSetNode { 732193323Sed T data; 733193323Sedpublic: 734221345Sdim explicit FoldingSetNodeWrapper(const T &x) : data(x) {} 735193323Sed virtual ~FoldingSetNodeWrapper() {} 736193323Sed 737193323Sed template<typename A1> 738221345Sdim explicit FoldingSetNodeWrapper(const A1 &a1) 739193323Sed : data(a1) {} 740193323Sed 741193323Sed template <typename A1, typename A2> 742221345Sdim explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2) 743193323Sed : data(a1,a2) {} 744193323Sed 745193323Sed template <typename A1, typename A2, typename A3> 746221345Sdim explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3) 747193323Sed : data(a1,a2,a3) {} 748193323Sed 749193323Sed template <typename A1, typename A2, typename A3, typename A4> 750221345Sdim explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, 751221345Sdim const A4 &a4) 752193323Sed : data(a1,a2,a3,a4) {} 753193323Sed 754193323Sed template <typename A1, typename A2, typename A3, typename A4, typename A5> 755221345Sdim explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, 756221345Sdim const A4 &a4, const A5 &a5) 757193323Sed : data(a1,a2,a3,a4,a5) {} 758193323Sed 759193323Sed 760221345Sdim void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); } 761193323Sed 762221345Sdim T &getValue() { return data; } 763221345Sdim const T &getValue() const { return data; } 764193323Sed 765193323Sed operator T&() { return data; } 766193323Sed operator const T&() const { return data; } 767193323Sed}; 768193323Sed 769193323Sed//===----------------------------------------------------------------------===// 770198090Srdivacky/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores 771198090Srdivacky/// a FoldingSetNodeID value rather than requiring the node to recompute it 772198090Srdivacky/// each time it is needed. This trades space for speed (which can be 773198090Srdivacky/// significant if the ID is long), and it also permits nodes to drop 774198090Srdivacky/// information that would otherwise only be required for recomputing an ID. 775198090Srdivackyclass FastFoldingSetNode : public FoldingSetNode { 776198090Srdivacky FoldingSetNodeID FastID; 777198090Srdivackyprotected: 778198090Srdivacky explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} 779198090Srdivackypublic: 780221345Sdim void Profile(FoldingSetNodeID &ID) const { 781221345Sdim ID.AddNodeID(FastID); 782221345Sdim } 783198090Srdivacky}; 784198090Srdivacky 785198090Srdivacky//===----------------------------------------------------------------------===// 786193323Sed// Partial specializations of FoldingSetTrait. 787193323Sed 788193323Sedtemplate<typename T> struct FoldingSetTrait<T*> { 789223017Sdim static inline void Profile(T *X, FoldingSetNodeID &ID) { 790193323Sed ID.AddPointer(X); 791193323Sed } 792193323Sed}; 793193323Sed} // End of namespace llvm. 794193323Sed 795193323Sed#endif 796