FoldingSet.h revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
1a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)//===-- llvm/ADT/FoldingSet.h - Uniquing Hash Set ---------------*- C++ -*-===// 2a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 3a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// The LLVM Compiler Infrastructure 4a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 51320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// This file is distributed under the University of Illinois Open Source 6a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch// License. See LICENSE.TXT for details. 7a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 8a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)//===----------------------------------------------------------------------===// 9a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 10a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// This file defines a hash set that can be used to remove duplication of nodes 111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// in a graph. This code was originally created by Chris Lattner for use with 12a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// SelectionDAGCSEMap, but was isolated to provide use across the llvm code set. 13a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 14a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)//===----------------------------------------------------------------------===// 15a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 16a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)#ifndef LLVM_ADT_FOLDINGSET_H 17a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)#define LLVM_ADT_FOLDINGSET_H 18a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 19a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 20a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)#include "llvm/ADT/StringRef.h" 21a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)#include "llvm/Support/Allocator.h" 22a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)#include "llvm/Support/DataTypes.h" 23a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 24a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)namespace llvm { 25a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) class APFloat; 26a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) class APInt; 27a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 28a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// This folding set used for two purposes: 291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// 1. Given information about a node we want to create, look up the unique 30a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// instance of the node in the set. If the node already exists, return 311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// it, otherwise return the bucket it should be inserted into. 321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// 2. Given a node that has already been created, remove it from the set. 33a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 34a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// This class is implemented as a single-link chained hash table, where the 35a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// "buckets" are actually the nodes themselves (the next pointer is in the 361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// node). The last node points back to the bucket to simplify node removal. 37a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 38a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// Any node that is to be included in the folding set must be a subclass of 39a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// FoldingSetNode. The node class must also define a Profile method used to 40a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// establish the unique bits of data for the node. The Profile method is 41a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// passed a FoldingSetNodeID object which is used to gather the bits. Just 42a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class. 43a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// NOTE: That the folding set does not own the nodes and it is the 44a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// responsibility of the user to dispose of the nodes. 45a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 46a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// Eg. 47a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// class MyNode : public FoldingSetNode { 48a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// private: 49a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// std::string Name; 50a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// unsigned Value; 51a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// public: 52a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} 53a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// ... 54a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// void Profile(FoldingSetNodeID &ID) const { 55a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// ID.AddString(Name); 56a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// ID.AddInteger(Value); 57a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// } 58a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// ... 59a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// }; 60a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 61a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// To define the folding set itself use the FoldingSet template; 62a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 63a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// Eg. 64a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// FoldingSet<MyNode> MyFoldingSet; 65a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 66a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// Four public methods are available to manipulate the folding set; 67a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 68a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 1) If you have an existing node that you want add to the set but unsure 69a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// that the node might already exist then call; 70a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 71a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// MyNode *M = MyFoldingSet.GetOrInsertNode(N); 72a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 73a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// If The result is equal to the input then the node has been inserted. 74a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// Otherwise, the result is the node existing in the folding set, and the 75a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// input can be discarded (use the result instead.) 76a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 77a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 2) If you are ready to construct a node but want to check if it already 78a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to 79a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// check; 80a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 81a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// FoldingSetNodeID ID; 82a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// ID.AddString(Name); 83a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// ID.AddInteger(Value); 84a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// void *InsertPoint; 85a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 86a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); 87a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 88a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// If found then M with be non-NULL, else InsertPoint will point to where it 89a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// should be inserted using InsertNode. 90a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 91a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new 92a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// node with FindNodeOrInsertPos; 93a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 94a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// InsertNode(N, InsertPoint); 95a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 96a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 4) Finally, if you want to remove a node from the folding set call; 97a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 985c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// bool WasRemoved = RemoveNode(N); 995c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// 1005c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// The result indicates whether the node existed in the folding set. 1015c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 1025c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuclass FoldingSetNodeID; 1035c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 1045c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu//===----------------------------------------------------------------------===// 1055c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// FoldingSetImpl - Implements the folding set functionality. The main 1065c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// structure is an array of buckets. Each bucket is indexed by the hash of 1075c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// the nodes it contains. The bucket itself points to the nodes contained 1085c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// in the bucket via a singly linked list. The last node in the list points 1095c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// back to the bucket to facilitate node removal. 1105c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// 111a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochclass FoldingSetImpl { 112a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochprotected: 113a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// Buckets - Array of bucket chains. 1141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// 1151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void **Buckets; 1161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// NumBuckets - Length of the Buckets array. Always a power of 2. 1181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// 1191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned NumBuckets; 1201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 1221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// is greater than twice the number of buckets. 1231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned NumNodes; 1241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccipublic: 126a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) explicit FoldingSetImpl(unsigned Log2InitSize = 6); 127a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) virtual ~FoldingSetImpl(); 128a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 129a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) //===--------------------------------------------------------------------===// 130a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// Node - This class is used to maintain the singly linked bucket list in 131a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// a folding set. 132a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// 133a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) class Node { 134a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) private: 135a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // NextInFoldingSetBucket - next link in the bucket list. 136a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void *NextInFoldingSetBucket; 137a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 138a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) public: 139a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 140a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Node() : NextInFoldingSetBucket(nullptr) {} 141a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 142a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // Accessors 143a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void *getNextInBucket() const { return NextInFoldingSetBucket; } 144a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 145a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) }; 146a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 147a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// clear - Remove all nodes from the folding set. 148a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch void clear(); 149a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 1501320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// RemoveNode - Remove a node from the folding set, returning true if one 1511320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// was removed or false if the node was not in the folding set. 152a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch bool RemoveNode(Node *N); 153a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 154a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// GetOrInsertNode - If there is an existing simple Node exactly 155a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// equal to the specified node, return it. Otherwise, insert 'N' and return 1561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// it instead. 1571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Node *GetOrInsertNode(Node *N); 1581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 1601320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// return it. If not, return the insertion token that will make insertion 1611320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// faster. 1621320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 1631320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1641320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// InsertNode - Insert the specified node into the folding set, knowing that 1651320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// it is not already in the folding set. InsertPos must be obtained from 1661320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// FindNodeOrInsertPos. 1671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void InsertNode(Node *N, void *InsertPos); 1681320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1691320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// InsertNode - Insert the specified node into the folding set, knowing that 1701320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// it is not already in the folding set. 171a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch void InsertNode(Node *N) { 172a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Node *Inserted = GetOrInsertNode(N); 173a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) (void)Inserted; 174a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) assert(Inserted == N && "Node already inserted!"); 175a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 176a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 177a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// size - Returns the number of nodes in the folding set. 178a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) unsigned size() const { return NumNodes; } 179a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 180a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// empty - Returns true if there are no nodes in the folding set. 181a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bool empty() const { return NumNodes == 0; } 182a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 183a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)private: 184a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 1851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// GrowHashTable - Double the size of the hash table and rehash everything. 1861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// 1871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void GrowHashTable(); 1881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 189a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)protected: 190a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 191a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// GetNodeProfile - Instantiations of the FoldingSet template implement 1921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// this function to gather data bits for the given node. 1931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0; 194a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// NodeEquals - Instantiations of the FoldingSet template implement 195a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// this function to compare the given node with the given ID. 196a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, 197a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID &TempID) const=0; 198a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// ComputeNodeHash - Instantiations of the FoldingSet template implement 199a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// this function to compute a hash value for the given node. 200a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0; 201a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)}; 202a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 203a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)//===----------------------------------------------------------------------===// 204a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 205a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)template<typename T> struct FoldingSetTrait; 206a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 207a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// DefaultFoldingSetTrait - This class provides default implementations 208a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// for FoldingSetTrait implementations. 209a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 210a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)template<typename T> struct DefaultFoldingSetTrait { 211a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) static void Profile(const T &X, FoldingSetNodeID &ID) { 212a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) X.Profile(ID); 213a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 214a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) static void Profile(T &X, FoldingSetNodeID &ID) { 215a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) X.Profile(ID); 216a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 217a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 218a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // Equals - Test if the profile for X would match ID, using TempID 219a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // to compute a temporary ID if necessary. The default implementation 220a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // just calls Profile and does a regular comparison. Implementations 221a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // can override this to provide more efficient implementations. 222a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 223a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID &TempID); 224a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 225a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // ComputeHash - Compute a hash value for X, using TempID to 226a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // compute a temporary ID if necessary. The default implementation 227a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // just calls Profile and does a regular hash computation. 228a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // Implementations can override this to provide more efficient 229a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // implementations. 230a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID); 231a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch}; 232a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 2331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// FoldingSetTrait - This trait class is used to define behavior of how 2341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// to "profile" (in the FoldingSet parlance) an object of a given type. 2351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// The default behavior is to invoke a 'Profile' method on an object, but 2361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// through template specialization the behavior can be tailored for specific 2371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// types. Combined with the FoldingSetNodeWrapper class, one can add objects 238a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// to FoldingSets that were not originally designed to have that behavior. 2391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccitemplate<typename T> struct FoldingSetTrait 240a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) : public DefaultFoldingSetTrait<T> {}; 241a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 242a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochtemplate<typename T, typename Ctx> struct ContextualFoldingSetTrait; 243a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 244a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but 245a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// for ContextualFoldingSets. 246a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)template<typename T, typename Ctx> 247a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)struct DefaultContextualFoldingSetTrait { 2481320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { 2491320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci X.Profile(ID, Context); 250cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 251cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 252cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) FoldingSetNodeID &TempID, Ctx Context); 253cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, 254cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) Ctx Context); 255cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)}; 256cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 257cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// ContextualFoldingSetTrait - Like FoldingSetTrait, but for 258cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// ContextualFoldingSets. 259cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<typename T, typename Ctx> struct ContextualFoldingSetTrait 260cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) : public DefaultContextualFoldingSetTrait<T, Ctx> {}; 261cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 262cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)//===--------------------------------------------------------------------===// 263cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// FoldingSetNodeIDRef - This class describes a reference to an interned 264cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// FoldingSetNodeID, which can be a useful to store node id data rather 265cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// than using plain FoldingSetNodeIDs, since the 32-element SmallVector 266a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// is often much larger than necessary, and the possibility of heap 267a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// allocation means it requires a non-trivial destructor call. 268a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)class FoldingSetNodeIDRef { 269a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) const unsigned *Data; 270a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) size_t Size; 271a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochpublic: 272a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch FoldingSetNodeIDRef() : Data(nullptr), Size(0) {} 273a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} 274a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 275a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 276a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// used to lookup the node in the FoldingSetImpl. 277a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch unsigned ComputeHash() const; 278a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 279a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bool operator==(FoldingSetNodeIDRef) const; 280a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 281a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); } 282a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 283a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// Used to compare the "ordering" of two nodes as defined by the 284a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// profiled bits and their ordering defined by memcmp(). 285a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bool operator<(FoldingSetNodeIDRef) const; 286a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 287a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) const unsigned *getData() const { return Data; } 288a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) size_t getSize() const { return Size; } 289a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)}; 2901e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) 291a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)//===--------------------------------------------------------------------===// 292a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// FoldingSetNodeID - This class is used to gather all the unique data bits of 293a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// a node. When all the bits are gathered this class is used to produce a 294a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// hash value for the node. 295a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// 296a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)class FoldingSetNodeID { 297a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// Bits - Vector of all the data bits that make the node unique. 298a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// Use a SmallVector to avoid a heap allocation in the common case. 299a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) SmallVector<unsigned, 32> Bits; 300a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 301a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)public: 302a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID() {} 3036e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 304a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID(FoldingSetNodeIDRef Ref) 305a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {} 306a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 307a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// Add* - Add various data types to Bit data. 308a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// 309a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void AddPointer(const void *Ptr); 310cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddInteger(signed I); 311cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddInteger(unsigned I); 312cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddInteger(long I); 313cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddInteger(unsigned long I); 314cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddInteger(long long I); 315cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddInteger(unsigned long long I); 316cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); } 317cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddString(StringRef String); 318cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void AddNodeID(const FoldingSetNodeID &ID); 319cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 320cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) template <typename T> 321cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); } 322cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 323cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID 324cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// object to be used to compute a new profile. 325cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) inline void clear() { Bits.clear(); } 326cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 327cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used 328cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// to lookup the node in the FoldingSetImpl. 329cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) unsigned ComputeHash() const; 330cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 3316e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) /// operator== - Used to compare two nodes to each other. 332cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// 333cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool operator==(const FoldingSetNodeID &RHS) const; 334cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool operator==(const FoldingSetNodeIDRef RHS) const; 335cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 336cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); } 337cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);} 338cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 339cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// Used to compare the "ordering" of two nodes as defined by the 340cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// profiled bits and their ordering defined by memcmp(). 341cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool operator<(const FoldingSetNodeID &RHS) const; 342cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool operator<(const FoldingSetNodeIDRef RHS) const; 343cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 344cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// Intern - Copy this node's data to a memory region allocated from the 345cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// given allocator and return a FoldingSetNodeIDRef describing the 346cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// interned data. 347cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const; 348cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)}; 349cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 350cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)// Convenience type to hide the implementation of the folding set. 351cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)typedef FoldingSetImpl::Node FoldingSetNode; 352cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<class T> class FoldingSetIterator; 353cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<class T> class FoldingSetBucketIterator; 354cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 355cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)// Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which 356cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)// require the definition of FoldingSetNodeID. 357cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<typename T> 358cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)inline bool 359cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID, 360cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) unsigned /*IDHash*/, 361cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) FoldingSetNodeID &TempID) { 362cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) FoldingSetTrait<T>::Profile(X, TempID); 363cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return TempID == ID; 364cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)} 365cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<typename T> 366cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)inline unsigned 367cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) { 368cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) FoldingSetTrait<T>::Profile(X, TempID); 369cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return TempID.ComputeHash(); 370cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)} 371cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<typename T, typename Ctx> 372cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)inline bool 373cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X, 374cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const FoldingSetNodeID &ID, 375a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) unsigned /*IDHash*/, 376a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID &TempID, 377a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Ctx Context) { 378a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 379a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return TempID == ID; 380a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)} 381a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)template<typename T, typename Ctx> 382a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)inline unsigned 383a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X, 384a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID &TempID, 385a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Ctx Context) { 386a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 387a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch return TempID.ComputeHash(); 388a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)} 389a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 390a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)//===----------------------------------------------------------------------===// 391a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// FoldingSet - This template class is used to instantiate a specialized 392cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// implementation of the folding set to the node class T. T must be a 393cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// subclass of FoldingSetNode and implement a Profile function. 394cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)/// 395cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)template<class T> class FoldingSet : public FoldingSetImpl { 396cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)private: 397cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 398cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// way to convert nodes into a unique specifier. 399cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override { 400cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T *TN = static_cast<T *>(N); 401cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) FoldingSetTrait<T>::Profile(*TN, ID); 402cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 403cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// NodeEquals - Instantiations may optionally provide a way to compare a 404cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// node with a specified ID. 405a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, 406a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNodeID &TempID) const override { 407a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) T *TN = static_cast<T *>(N); 408a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID); 409a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 410a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// ComputeNodeHash - Instantiations may optionally provide a way to compute a 411a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// hash value directly from a node. 412a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override { 413a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) T *TN = static_cast<T *>(N); 414a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return FoldingSetTrait<T>::ComputeHash(*TN, TempID); 415a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 416a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 417a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)public: 418a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) explicit FoldingSet(unsigned Log2InitSize = 6) 419a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) : FoldingSetImpl(Log2InitSize) 420a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) {} 421a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 422a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) typedef FoldingSetIterator<T> iterator; 423a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) iterator begin() { return iterator(Buckets); } 424a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) iterator end() { return iterator(Buckets+NumBuckets); } 425a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 426a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) typedef FoldingSetIterator<const T> const_iterator; 427a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) const_iterator begin() const { return const_iterator(Buckets); } 428a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 429a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 430a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) typedef FoldingSetBucketIterator<T> bucket_iterator; 431a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 432a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bucket_iterator bucket_begin(unsigned hash) { 433a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 434a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 435a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 436a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bucket_iterator bucket_end(unsigned hash) { 437a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 438a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 439a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 440a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// GetOrInsertNode - If there is an existing simple Node exactly 441a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// equal to the specified node, return it. Otherwise, insert 'N' and 442a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// return it instead. 443a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch T *GetOrInsertNode(Node *N) { 444a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 445a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 446a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 447a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 4481320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// return it. If not, return the insertion token that will make insertion 449a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// faster. 450a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 451a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 452a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 4535c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}; 454a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 455a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch//===----------------------------------------------------------------------===// 456a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// ContextualFoldingSet - This template class is a further refinement 457a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// of FoldingSet which provides a context argument when calling 458a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// Profile on its nodes. Currently, that argument is fixed at 459a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// initialization time. 460a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// 461a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// T must be a subclass of FoldingSetNode and implement a Profile 4625c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu/// function with signature 463a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// void Profile(llvm::FoldingSetNodeID &, Ctx); 4645c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liutemplate <class T, class Ctx> 4655c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuclass ContextualFoldingSet : public FoldingSetImpl { 466a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // Unfortunately, this can't derive from FoldingSet<T> because the 467a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // construction vtable for FoldingSet<T> requires 4681320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn 469a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // requires a single-argument T::Profile(). 4701320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 4711320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciprivate: 4721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Ctx Context; 4731320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 4741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 4751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// way to convert nodes into a unique specifier. 4761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void GetNodeProfile(FoldingSetImpl::Node *N, 4771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci FoldingSetNodeID &ID) const override { 4781320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci T *TN = static_cast<T *>(N); 4791320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context); 4801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 4811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool NodeEquals(FoldingSetImpl::Node *N, const FoldingSetNodeID &ID, 4821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned IDHash, FoldingSetNodeID &TempID) const override { 4831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci T *TN = static_cast<T *>(N); 4841320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID, 4851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Context); 4861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 4871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned ComputeNodeHash(FoldingSetImpl::Node *N, 4881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci FoldingSetNodeID &TempID) const override { 4891320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci T *TN = static_cast<T *>(N); 4901320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context); 4911320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 4921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 4931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccipublic: 4941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) 4951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci : FoldingSetImpl(Log2InitSize), Context(Context) 4961320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci {} 4971320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 4981320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Ctx getContext() const { return Context; } 4991320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5001320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5011320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef FoldingSetIterator<T> iterator; 5021320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci iterator begin() { return iterator(Buckets); } 5031320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci iterator end() { return iterator(Buckets+NumBuckets); } 5041320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 505a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) typedef FoldingSetIterator<const T> const_iterator; 5061320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const_iterator begin() const { return const_iterator(Buckets); } 5071320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 5081320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5091320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef FoldingSetBucketIterator<T> bucket_iterator; 5101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bucket_iterator bucket_begin(unsigned hash) { 5121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 5131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 5141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bucket_iterator bucket_end(unsigned hash) { 5161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 5171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 5181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// GetOrInsertNode - If there is an existing simple Node exactly 5201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// equal to the specified node, return it. Otherwise, insert 'N' 5211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// and return it instead. 5221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci T *GetOrInsertNode(Node *N) { 5231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 5241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 5251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// FindNodeOrInsertPos - Look up the node specified by ID. If it 5271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// exists, return it. If not, return the insertion token that will 5281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// make insertion faster. 5291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 5301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 5311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 5321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci}; 5331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 5351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// FoldingSetVectorIterator - This implements an iterator for 5361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// FoldingSetVector. It is only necessary because FoldingSetIterator provides 5371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// a value_type of T, while the vector in FoldingSetVector exposes 5381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// a value_type of T*. Fortunately, FoldingSetIterator doesn't expose very 5391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// much besides operator* and operator->, so we just wrap the inner vector 5401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// iterator and perform the extra dereference. 5411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccitemplate <class T, class VectorIteratorT> 5421320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciclass FoldingSetVectorIterator { 5431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Provide a typedef to workaround the lack of correct injected class name 5441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // support in older GCCs. 5451320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef FoldingSetVectorIterator<T, VectorIteratorT> SelfT; 5461320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5471320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci VectorIteratorT Iterator; 548a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 549a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)public: 5501320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci FoldingSetVectorIterator(VectorIteratorT I) : Iterator(I) {} 551a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 5521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool operator==(const SelfT &RHS) const { 5531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return Iterator == RHS.Iterator; 5541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 5551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool operator!=(const SelfT &RHS) const { 5561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return Iterator != RHS.Iterator; 5571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 5581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 5591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci T &operator*() const { return **Iterator; } 5601320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 561a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) T *operator->() const { return *Iterator; } 562a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 5631320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci inline SelfT &operator++() { 5641320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ++Iterator; 565a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return *this; 566a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 567a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) SelfT operator++(int) { 568a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) SelfT tmp = *this; 569a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) ++*this; 570a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return tmp; 571a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 5721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci}; 573a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 5741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 575a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// FoldingSetVector - This template class combines a FoldingSet and a vector 576a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch/// to provide the interface of FoldingSet but with deterministic iteration 577a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// order based on the insertion order. T must be a subclass of FoldingSetNode 578a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/// and implement a Profile function. 579a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)template <class T, class VectorT = SmallVector<T*, 8> > 580a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)class FoldingSetVector { 581a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSet<T> Set; 582a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) VectorT Vector; 583a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 584a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)public: 585a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) explicit FoldingSetVector(unsigned Log2InitSize = 6) 586a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) : Set(Log2InitSize) { 587a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 588a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 589a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) typedef FoldingSetVectorIterator<T, typename VectorT::iterator> iterator; 590a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) iterator begin() { return Vector.begin(); } 591a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch iterator end() { return Vector.end(); } 592a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 593a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch typedef FoldingSetVectorIterator<const T, typename VectorT::const_iterator> 594a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const_iterator; 595a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const_iterator begin() const { return Vector.begin(); } 5961320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const_iterator end() const { return Vector.end(); } 597a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 598a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// clear - Remove all nodes from the folding set. 599a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void clear() { Set.clear(); Vector.clear(); } 600a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 601a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 602a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// return it. If not, return the insertion token that will make insertion 603a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// faster. 604a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 605a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch return Set.FindNodeOrInsertPos(ID, InsertPos); 606a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 6071320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 608a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// GetOrInsertNode - If there is an existing simple Node exactly 609a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// equal to the specified node, return it. Otherwise, insert 'N' and 610a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// return it instead. 611a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) T *GetOrInsertNode(T *N) { 612a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch T *Result = Set.GetOrInsertNode(N); 613a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (Result == N) Vector.push_back(N); 614a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch return Result; 615a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 616a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 6171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// InsertNode - Insert the specified node into the folding set, knowing that 618a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// it is not already in the folding set. InsertPos must be obtained from 619a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch /// FindNodeOrInsertPos. 620a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void InsertNode(T *N, void *InsertPos) { 621a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Set.InsertNode(N, InsertPos); 6221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Vector.push_back(N); 6231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 6241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 6251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// InsertNode - Insert the specified node into the folding set, knowing that 6261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// it is not already in the folding set. 6271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void InsertNode(T *N) { 6281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Set.InsertNode(N); 6291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Vector.push_back(N); 6301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 6311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 6321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// size - Returns the number of nodes in the folding set. 6331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned size() const { return Set.size(); } 6341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 6351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// empty - Returns true if there are no nodes in the folding set. 6361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool empty() const { return Set.empty(); } 6371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci}; 6381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 6391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 6401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// FoldingSetIteratorImpl - This is the common iterator support shared by all 6411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// folding sets, which knows how to walk the folding set hash table. 6421320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciclass FoldingSetIteratorImpl { 6431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciprotected: 644a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) FoldingSetNode *NodePtr; 645 FoldingSetIteratorImpl(void **Bucket); 646 void advance(); 647 648public: 649 bool operator==(const FoldingSetIteratorImpl &RHS) const { 650 return NodePtr == RHS.NodePtr; 651 } 652 bool operator!=(const FoldingSetIteratorImpl &RHS) const { 653 return NodePtr != RHS.NodePtr; 654 } 655}; 656 657 658template<class T> 659class FoldingSetIterator : public FoldingSetIteratorImpl { 660public: 661 explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} 662 663 T &operator*() const { 664 return *static_cast<T*>(NodePtr); 665 } 666 667 T *operator->() const { 668 return static_cast<T*>(NodePtr); 669 } 670 671 inline FoldingSetIterator &operator++() { // Preincrement 672 advance(); 673 return *this; 674 } 675 FoldingSetIterator operator++(int) { // Postincrement 676 FoldingSetIterator tmp = *this; ++*this; return tmp; 677 } 678}; 679 680//===----------------------------------------------------------------------===// 681/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support 682/// shared by all folding sets, which knows how to walk a particular bucket 683/// of a folding set hash table. 684 685class FoldingSetBucketIteratorImpl { 686protected: 687 void *Ptr; 688 689 explicit FoldingSetBucketIteratorImpl(void **Bucket); 690 691 FoldingSetBucketIteratorImpl(void **Bucket, bool) 692 : Ptr(Bucket) {} 693 694 void advance() { 695 void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket(); 696 uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1; 697 Ptr = reinterpret_cast<void*>(x); 698 } 699 700public: 701 bool operator==(const FoldingSetBucketIteratorImpl &RHS) const { 702 return Ptr == RHS.Ptr; 703 } 704 bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const { 705 return Ptr != RHS.Ptr; 706 } 707}; 708 709 710template<class T> 711class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { 712public: 713 explicit FoldingSetBucketIterator(void **Bucket) : 714 FoldingSetBucketIteratorImpl(Bucket) {} 715 716 FoldingSetBucketIterator(void **Bucket, bool) : 717 FoldingSetBucketIteratorImpl(Bucket, true) {} 718 719 T &operator*() const { return *static_cast<T*>(Ptr); } 720 T *operator->() const { return static_cast<T*>(Ptr); } 721 722 inline FoldingSetBucketIterator &operator++() { // Preincrement 723 advance(); 724 return *this; 725 } 726 FoldingSetBucketIterator operator++(int) { // Postincrement 727 FoldingSetBucketIterator tmp = *this; ++*this; return tmp; 728 } 729}; 730 731//===----------------------------------------------------------------------===// 732/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary 733/// types in an enclosing object so that they can be inserted into FoldingSets. 734template <typename T> 735class FoldingSetNodeWrapper : public FoldingSetNode { 736 T data; 737public: 738 explicit FoldingSetNodeWrapper(const T &x) : data(x) {} 739 virtual ~FoldingSetNodeWrapper() {} 740 741 template<typename A1> 742 explicit FoldingSetNodeWrapper(const A1 &a1) 743 : data(a1) {} 744 745 template <typename A1, typename A2> 746 explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2) 747 : data(a1,a2) {} 748 749 template <typename A1, typename A2, typename A3> 750 explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3) 751 : data(a1,a2,a3) {} 752 753 template <typename A1, typename A2, typename A3, typename A4> 754 explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, 755 const A4 &a4) 756 : data(a1,a2,a3,a4) {} 757 758 template <typename A1, typename A2, typename A3, typename A4, typename A5> 759 explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, 760 const A4 &a4, const A5 &a5) 761 : data(a1,a2,a3,a4,a5) {} 762 763 764 void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); } 765 766 T &getValue() { return data; } 767 const T &getValue() const { return data; } 768 769 operator T&() { return data; } 770 operator const T&() const { return data; } 771}; 772 773//===----------------------------------------------------------------------===// 774/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores 775/// a FoldingSetNodeID value rather than requiring the node to recompute it 776/// each time it is needed. This trades space for speed (which can be 777/// significant if the ID is long), and it also permits nodes to drop 778/// information that would otherwise only be required for recomputing an ID. 779class FastFoldingSetNode : public FoldingSetNode { 780 FoldingSetNodeID FastID; 781protected: 782 explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} 783public: 784 void Profile(FoldingSetNodeID &ID) const { 785 ID.AddNodeID(FastID); 786 } 787}; 788 789//===----------------------------------------------------------------------===// 790// Partial specializations of FoldingSetTrait. 791 792template<typename T> struct FoldingSetTrait<T*> { 793 static inline void Profile(T *X, FoldingSetNodeID &ID) { 794 ID.AddPointer(X); 795 } 796}; 797} // End of namespace llvm. 798 799#endif 800