Deleted Added
sdiff udiff text old ( 208954 ) new ( 210299 )
full compact
FoldingSet.cpp (208954) FoldingSet.cpp (210299)
1//===-- Support/FoldingSet.cpp - 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//===----------------------------------------------------------------------===//

--- 161 unchanged lines hidden (view full) ---

170/// the specified ID.
171static void **GetBucketFor(const FoldingSetNodeID &ID,
172 void **Buckets, unsigned NumBuckets) {
173 // NumBuckets is always a power of 2.
174 unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
175 return Buckets + BucketNum;
176}
177
1//===-- Support/FoldingSet.cpp - 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//===----------------------------------------------------------------------===//

--- 161 unchanged lines hidden (view full) ---

170/// the specified ID.
171static void **GetBucketFor(const FoldingSetNodeID &ID,
172 void **Buckets, unsigned NumBuckets) {
173 // NumBuckets is always a power of 2.
174 unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
175 return Buckets + BucketNum;
176}
177
178/// AllocateBuckets - Allocated initialized bucket memory.
179static void **AllocateBuckets(unsigned NumBuckets) {
180 void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*)));
181 // Set the very last bucket to be a non-null "pointer".
182 Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
183 return Buckets;
184}
185
178//===----------------------------------------------------------------------===//
179// FoldingSetImpl Implementation
180
181FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) {
182 assert(5 < Log2InitSize && Log2InitSize < 32 &&
183 "Initial hash table size out of range");
184 NumBuckets = 1 << Log2InitSize;
186//===----------------------------------------------------------------------===//
187// FoldingSetImpl Implementation
188
189FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) {
190 assert(5 < Log2InitSize && Log2InitSize < 32 &&
191 "Initial hash table size out of range");
192 NumBuckets = 1 << Log2InitSize;
185 Buckets = new void*[NumBuckets+1];
186 clear();
193 Buckets = AllocateBuckets(NumBuckets);
194 NumNodes = 0;
187}
188FoldingSetImpl::~FoldingSetImpl() {
195}
196FoldingSetImpl::~FoldingSetImpl() {
189 delete [] Buckets;
197 free(Buckets);
190}
191void FoldingSetImpl::clear() {
192 // Set all but the last bucket to null pointers.
193 memset(Buckets, 0, NumBuckets*sizeof(void*));
194
195 // Set the very last bucket to be a non-null "pointer".
196 Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
197

--- 4 unchanged lines hidden (view full) ---

202/// GrowHashTable - Double the size of the hash table and rehash everything.
203///
204void FoldingSetImpl::GrowHashTable() {
205 void **OldBuckets = Buckets;
206 unsigned OldNumBuckets = NumBuckets;
207 NumBuckets <<= 1;
208
209 // Clear out new buckets.
198}
199void FoldingSetImpl::clear() {
200 // Set all but the last bucket to null pointers.
201 memset(Buckets, 0, NumBuckets*sizeof(void*));
202
203 // Set the very last bucket to be a non-null "pointer".
204 Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
205

--- 4 unchanged lines hidden (view full) ---

210/// GrowHashTable - Double the size of the hash table and rehash everything.
211///
212void FoldingSetImpl::GrowHashTable() {
213 void **OldBuckets = Buckets;
214 unsigned OldNumBuckets = NumBuckets;
215 NumBuckets <<= 1;
216
217 // Clear out new buckets.
210 Buckets = new void*[NumBuckets+1];
211 clear();
218 Buckets = AllocateBuckets(NumBuckets);
219 NumNodes = 0;
212
213 // Walk the old buckets, rehashing nodes into their new place.
214 FoldingSetNodeID ID;
215 for (unsigned i = 0; i != OldNumBuckets; ++i) {
216 void *Probe = OldBuckets[i];
217 if (!Probe) continue;
218 while (Node *NodeInBucket = GetNextPtr(Probe)) {
219 // Figure out the next link, remove NodeInBucket from the old link.
220 Probe = NodeInBucket->getNextInBucket();
221 NodeInBucket->SetNextInBucket(0);
222
223 // Insert the node into the new bucket, after recomputing the hash.
224 GetNodeProfile(ID, NodeInBucket);
225 InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets));
226 ID.clear();
227 }
228 }
229
220
221 // Walk the old buckets, rehashing nodes into their new place.
222 FoldingSetNodeID ID;
223 for (unsigned i = 0; i != OldNumBuckets; ++i) {
224 void *Probe = OldBuckets[i];
225 if (!Probe) continue;
226 while (Node *NodeInBucket = GetNextPtr(Probe)) {
227 // Figure out the next link, remove NodeInBucket from the old link.
228 Probe = NodeInBucket->getNextInBucket();
229 NodeInBucket->SetNextInBucket(0);
230
231 // Insert the node into the new bucket, after recomputing the hash.
232 GetNodeProfile(ID, NodeInBucket);
233 InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets));
234 ID.clear();
235 }
236 }
237
230 delete[] OldBuckets;
238 free(OldBuckets);
231}
232
233/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
234/// return it. If not, return the insertion token that will make insertion
235/// faster.
236FoldingSetImpl::Node
237*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
238 void *&InsertPos) {

--- 143 unchanged lines hidden --- 		239}
240
241/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
242/// return it. If not, return the insertion token that will make insertion
243/// faster.
244FoldingSetImpl::Node
245*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
246 void *&InsertPos) {

--- 143 unchanged lines hidden ---