FoldingSet.h revision c899b33b830c360e53eb35440a1371542925414f
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/ADT/SmallVector.h" 21#include <string> 22 23namespace llvm { 24 class APFloat; 25 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 simplified 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) { 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 100class 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/// 109class FoldingSetImpl { 110protected: 111 /// Buckets - Array of bucket chains. 112 /// 113 void **Buckets; 114 115 /// NumBuckets - Length of the Buckets array. Always a power of 2. 116 /// 117 unsigned NumBuckets; 118 119 /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 120 /// is greater than twice the number of buckets. 121 unsigned NumNodes; 122 123public: 124 explicit FoldingSetImpl(unsigned Log2InitSize = 6); 125 virtual ~FoldingSetImpl(); 126 127 //===--------------------------------------------------------------------===// 128 /// Node - This class is used to maintain the singly linked bucket list in 129 /// a folding set. 130 /// 131 class Node { 132 private: 133 // NextInFoldingSetBucket - next link in the bucket list. 134 void *NextInFoldingSetBucket; 135 136 public: 137 138 Node() : NextInFoldingSetBucket(0) {} 139 140 // Accessors 141 void *getNextInBucket() const { return NextInFoldingSetBucket; } 142 void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 143 }; 144 145 /// RemoveNode - Remove a node from the folding set, returning true if one 146 /// was removed or false if the node was not in the folding set. 147 bool RemoveNode(Node *N); 148 149 /// GetOrInsertNode - If there is an existing simple Node exactly 150 /// equal to the specified node, return it. Otherwise, insert 'N' and return 151 /// it instead. 152 Node *GetOrInsertNode(Node *N); 153 154 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 155 /// return it. If not, return the insertion token that will make insertion 156 /// faster. 157 Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 158 159 /// InsertNode - Insert the specified node into the folding set, knowing that 160 /// it is not already in the folding set. InsertPos must be obtained from 161 /// FindNodeOrInsertPos. 162 void InsertNode(Node *N, void *InsertPos); 163 164 /// size - Returns the number of nodes in the folding set. 165 unsigned size() const { return NumNodes; } 166 167private: 168 169 /// GrowHashTable - Double the size of the hash table and rehash everything. 170 /// 171 void GrowHashTable(); 172 173protected: 174 175 /// GetNodeProfile - Instantiations of the FoldingSet template implement 176 /// this function to gather data bits for the given node. 177 virtual void GetNodeProfile(FoldingSetNodeID &ID, Node *N) const = 0; 178}; 179 180//===--------------------------------------------------------------------===// 181/// FoldingSetNodeID - This class is used to gather all the unique data bits of 182/// a node. When all the bits are gathered this class is used to produce a 183/// hash value for the node. 184/// 185class FoldingSetNodeID { 186 /// Bits - Vector of all the data bits that make the node unique. 187 /// Use a SmallVector to avoid a heap allocation in the common case. 188 SmallVector<unsigned, 32> Bits; 189 190public: 191 FoldingSetNodeID() {} 192 193 /// getRawData - Return the ith entry in the Bits data. 194 /// 195 unsigned getRawData(unsigned i) const { 196 return Bits[i]; 197 } 198 199 /// Add* - Add various data types to Bit data. 200 /// 201 void AddPointer(const void *Ptr); 202 void AddInteger(signed I); 203 void AddInteger(unsigned I); 204 void AddInteger(int64_t I); 205 void AddInteger(uint64_t I); 206 void AddFloat(float F); 207 void AddDouble(double D); 208 void AddAPFloat(const APFloat& apf); 209 void AddString(const std::string &String); 210 211 /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID 212 /// object to be used to compute a new profile. 213 inline void clear() { Bits.clear(); } 214 215 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used 216 /// to lookup the node in the FoldingSetImpl. 217 unsigned ComputeHash() const; 218 219 /// operator== - Used to compare two nodes to each other. 220 /// 221 bool operator==(const FoldingSetNodeID &RHS) const; 222}; 223 224// Convenience type to hide the implementation of the folding set. 225typedef FoldingSetImpl::Node FoldingSetNode; 226template<class T> class FoldingSetIterator; 227 228//===----------------------------------------------------------------------===// 229/// FoldingSetTrait - This trait class is used to define behavior of how 230/// to "profile" (in the FoldingSet parlance) an object of a given type. 231/// The default behavior is to invoke a 'Profile' method on an object, but 232/// through template specialization the behavior can be tailored for specific 233/// types. Combined with the FoldingSetNodeWrapper classs, one can add objects 234/// to FoldingSets that were not originally designed to have that behavior. 235/// 236template<typename T> struct FoldingSetTrait { 237 static inline void Profile(const T& X, FoldingSetNodeID& ID) { X.Profile(ID);} 238 static inline void Profile(T& X, FoldingSetNodeID& ID) { X.Profile(ID); } 239}; 240 241//===----------------------------------------------------------------------===// 242/// FoldingSet - This template class is used to instantiate a specialized 243/// implementation of the folding set to the node class T. T must be a 244/// subclass of FoldingSetNode and implement a Profile function. 245/// 246template<class T> class FoldingSet : public FoldingSetImpl { 247private: 248 /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 249 /// way to convert nodes into a unique specifier. 250 virtual void GetNodeProfile(FoldingSetNodeID &ID, Node *N) const { 251 T *TN = static_cast<T *>(N); 252 FoldingSetTrait<T>::Profile(*TN,ID); 253 } 254 255public: 256 explicit FoldingSet(unsigned Log2InitSize = 6) 257 : FoldingSetImpl(Log2InitSize) 258 {} 259 260 typedef FoldingSetIterator<T> iterator; 261 iterator begin() { return iterator(Buckets); } 262 iterator end() { return iterator(Buckets+NumBuckets); } 263 264 typedef FoldingSetIterator<const T> const_iterator; 265 const_iterator begin() const { return const_iterator(Buckets); } 266 const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 267 268 /// GetOrInsertNode - If there is an existing simple Node exactly 269 /// equal to the specified node, return it. Otherwise, insert 'N' and 270 /// return it instead. 271 T *GetOrInsertNode(Node *N) { 272 return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 273 } 274 275 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 276 /// return it. If not, return the insertion token that will make insertion 277 /// faster. 278 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 279 return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 280 } 281}; 282 283//===----------------------------------------------------------------------===// 284/// FoldingSetIteratorImpl - This is the common iterator support shared by all 285/// folding sets, which knows how to walk the folding set hash table. 286class FoldingSetIteratorImpl { 287protected: 288 FoldingSetNode *NodePtr; 289 FoldingSetIteratorImpl(void **Bucket); 290 void advance(); 291 292public: 293 bool operator==(const FoldingSetIteratorImpl &RHS) const { 294 return NodePtr == RHS.NodePtr; 295 } 296 bool operator!=(const FoldingSetIteratorImpl &RHS) const { 297 return NodePtr != RHS.NodePtr; 298 } 299}; 300 301 302template<class T> 303class FoldingSetIterator : public FoldingSetIteratorImpl { 304public: 305 FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} 306 307 T &operator*() const { 308 return *static_cast<T*>(NodePtr); 309 } 310 311 T *operator->() const { 312 return static_cast<T*>(NodePtr); 313 } 314 315 inline FoldingSetIterator& operator++() { // Preincrement 316 advance(); 317 return *this; 318 } 319 FoldingSetIterator operator++(int) { // Postincrement 320 FoldingSetIterator tmp = *this; ++*this; return tmp; 321 } 322}; 323 324//===----------------------------------------------------------------------===// 325/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary 326/// types in an enclosing object so that they can be inserted into FoldingSets. 327template <typename T> 328class FoldingSetNodeWrapper : public FoldingSetNode { 329 T data; 330public: 331 FoldingSetNodeWrapper(const T& x) : data(x) {} 332 virtual ~FoldingSetNodeWrapper(); 333 334 template<typename A1> 335 explicit FoldingSetNodeWrapper(const A1& a1) 336 : data(a1) {} 337 338 template <typename A1, typename A2> 339 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2) 340 : data(a1,a2) {} 341 342 template <typename A1, typename A2, typename A3> 343 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3) 344 : data(a1,a2,a3) {} 345 346 template <typename A1, typename A2, typename A3, typename A4> 347 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3, 348 const A4& a4) 349 : data(a1,a2,a3,a4) {} 350 351 template <typename A1, typename A2, typename A3, typename A4, typename A5> 352 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3, 353 const A4& a4, const A5& a5) 354 : data(a1,a2,a3,a4,a5) {} 355 356 357 void Profile(FoldingSetNodeID& ID) { FoldingSetTrait<T>::Profile(data, ID); } 358 359 operator T&() { return data; } 360 operator const T&() const { return data; } 361}; 362 363} // End of namespace llvm. 364 365 366#endif 367 368