FoldingSet.h revision 2f6d4c9766e920602326cfe26f5985077156d890
1//===-- llvm/ADT/FoldingSet.h - Uniquing Hash Set ---------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by James M. Laskey and is distributed under 6// the University of Illinois Open Source 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 21namespace llvm { 22 23/// This folding set used for two purposes: 24/// 1. Given information about a node we want to create, look up the unique 25/// instance of the node in the set. If the node already exists, return 26/// it, otherwise return the bucket it should be inserted into. 27/// 2. Given a node that has already been created, remove it from the set. 28/// 29/// This class is implemented as a single-link chained hash table, where the 30/// "buckets" are actually the nodes themselves (the next pointer is in the 31/// node). The last node points back to the bucket to simplified node removal. 32/// 33/// Any node that is to be included in the folding set must be a subclass of 34/// FoldingSetNode. The node class must also define a Profile method used to 35/// establish the unique bits of data for the node. The Profile method is 36/// passed a FoldingSetNodeID object which is used to gather the bits. Just 37/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class. 38/// NOTE: That the folding set does not own the nodes and it is the 39/// responsibility of the user to dispose of the nodes. 40/// 41/// Eg. 42/// class MyNode : public FoldingSetNode { 43/// private: 44/// std::string Name; 45/// unsigned Value; 46/// public: 47/// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} 48/// ... 49/// void Profile(FoldingSetNodeID &ID) { 50/// ID.AddString(Name); 51/// ID.AddInteger(Value); 52/// } 53/// ... 54/// }; 55/// 56/// To define the folding set itself use the FoldingSet template; 57/// 58/// Eg. 59/// FoldingSet<MyNode> MyFoldingSet; 60/// 61/// Four public methods are available to manipulate the folding set; 62/// 63/// 1) If you have an existing node that you want add to the set but unsure 64/// that the node might already exist then call; 65/// 66/// MyNode *M = MyFoldingSet.GetOrInsertNode(N); 67/// 68/// If The result is equal to the input then the node has been inserted. 69/// Otherwise, the result is the node existing in the folding set, and the 70/// input can be discarded (use the result instead.) 71/// 72/// 2) If you are ready to construct a node but want to check if it already 73/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to 74/// check; 75/// 76/// FoldingSetNodeID ID; 77/// ID.AddString(Name); 78/// ID.AddInteger(Value); 79/// void *InsertPoint; 80/// 81/// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); 82/// 83/// If found then M with be non-NULL, else InsertPoint will point to where it 84/// should be inserted using InsertNode. 85/// 86/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new 87/// node with FindNodeOrInsertPos; 88/// 89/// InsertNode(N, InsertPoint); 90/// 91/// 4) Finally, if you want to remove a node from the folding set call; 92/// 93/// bool WasRemoved = RemoveNode(N); 94/// 95/// The result indicates whether the node existed in the folding set. 96 97 98//===----------------------------------------------------------------------===// 99/// FoldingSetImpl - Implements the folding set functionality. The main 100/// structure is an array of buckets. Each bucket is indexed by the hash of 101/// the nodes it contains. The bucket itself points to the nodes contained 102/// in the bucket via a singly linked list. The last node in the list points 103/// back to the bucket to facilitate node removal. 104/// 105class FoldingSetImpl { 106private: 107 /// Buckets - Array of bucket chains. 108 /// 109 void **Buckets; 110 111 /// NumBuckets - Length of the Buckets array. Always a power of 2. 112 /// 113 unsigned NumBuckets; 114 115 /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 116 /// is greater than twice the number of buckets. 117 unsigned NumNodes; 118 119public: 120 FoldingSetImpl(); 121 virtual ~FoldingSetImpl(); 122 123 // Forward declaration. 124 class Node; 125 126 //===--------------------------------------------------------------------===// 127 /// NodeID - This class is used to gather all the unique data bits of a 128 /// node. When all the bits are gathered this class is used to produce a 129 /// hash value for the node. 130 /// 131 class NodeID { 132 /// Bits - Vector of all the data bits that make the node unique. 133 /// Use a SmallVector to avoid a heap allocation in the common case. 134 SmallVector<unsigned, 32> Bits; 135 136 public: 137 NodeID() {} 138 139 /// getRawData - Return the ith entry in the Bits data. 140 /// 141 unsigned getRawData(unsigned i) const { 142 return Bits[i]; 143 } 144 145 /// Add* - Add various data types to Bit data. 146 /// 147 void AddPointer(const void *Ptr); 148 void AddInteger(signed I); 149 void AddInteger(unsigned I); 150 void AddInteger(uint64_t I); 151 void AddFloat(float F); 152 void AddDouble(double D); 153 void AddString(const std::string &String); 154 155 /// ComputeHash - Compute a strong hash value for this NodeID, used to 156 /// lookup the node in the FoldingSetImpl. 157 unsigned ComputeHash() const; 158 159 /// operator== - Used to compare two nodes to each other. 160 /// 161 bool operator==(const NodeID &RHS) const; 162 }; 163 164 //===--------------------------------------------------------------------===// 165 /// Node - This class is used to maintain the singly linked bucket list in 166 /// a folding set. 167 /// 168 class Node { 169 private: 170 // NextInFoldingSetBucket - next link in the bucket list. 171 void *NextInFoldingSetBucket; 172 173 public: 174 175 Node() : NextInFoldingSetBucket(0) {} 176 177 // Accessors 178 void *getNextInBucket() const { return NextInFoldingSetBucket; } 179 void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 180 }; 181 182 /// RemoveNode - Remove a node from the folding set, returning true if one 183 /// was removed or false if the node was not in the folding set. 184 bool RemoveNode(Node *N); 185 186 /// GetOrInsertNode - If there is an existing simple Node exactly 187 /// equal to the specified node, return it. Otherwise, insert 'N' and return 188 /// it instead. 189 Node *GetOrInsertNode(Node *N); 190 191 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 192 /// return it. If not, return the insertion token that will make insertion 193 /// faster. 194 Node *FindNodeOrInsertPos(const NodeID &ID, void *&InsertPos); 195 196 /// InsertNode - Insert the specified node into the folding set, knowing that 197 /// it is not already in the folding set. InsertPos must be obtained from 198 /// FindNodeOrInsertPos. 199 void InsertNode(Node *N, void *InsertPos); 200 201private: 202 203 /// GrowHashTable - Double the size of the hash table and rehash everything. 204 /// 205 void GrowHashTable(); 206 207protected: 208 209 /// GetNodeProfile - Instantiations of the FoldingSet template implement 210 /// this function to gather data bits for the given node. 211 virtual void GetNodeProfile(NodeID &ID, Node *N) const = 0; 212}; 213 214// Convenience types to hide the implementation of the folding set. 215typedef FoldingSetImpl::Node FoldingSetNode; 216typedef FoldingSetImpl::NodeID FoldingSetNodeID; 217 218//===--------------------------------------------------------------------===// 219/// FoldingSet - This template class is used to instantiate a specialized 220/// implementation of the folding set to the node class T. T must be a 221/// subclass of FoldingSetNode and implement a Profile function. 222/// 223template<class T> class FoldingSet : public FoldingSetImpl { 224private: 225 /// GetNodeProfile - Each instantiatation of the FoldingSet 226 virtual void GetNodeProfile(NodeID &ID, Node *N) const { 227 T *TN = static_cast<T *>(N); 228 TN->Profile(ID); 229 } 230 231public: 232 /// GetOrInsertNode - If there is an existing simple Node exactly 233 /// equal to the specified node, return it. Otherwise, insert 'N' and 234 /// return it instead. 235 T *GetOrInsertNode(Node *N) { 236 return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 237 } 238 239 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 240 /// return it. If not, return the insertion token that will make insertion 241 /// faster. 242 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 243 return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, 244 InsertPos)); 245 } 246}; 247 248} // End of namespace llvm. 249 250 251#endif 252 253