1//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===// 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 implements the SmallPtrSet class. See SmallPtrSet.h for an 11// overview of the algorithm. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/ADT/SmallPtrSet.h" 16#include "llvm/ADT/DenseMapInfo.h" 17#include "llvm/Support/MathExtras.h" 18#include <algorithm> 19#include <cstdlib> 20 21using namespace llvm; 22 23void SmallPtrSetImpl::shrink_and_clear() { 24 assert(!isSmall() && "Can't shrink a small set!"); 25 free(CurArray); 26 27 // Reduce the number of buckets. 28 CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; 29 NumElements = NumTombstones = 0; 30 31 // Install the new array. Clear all the buckets to empty. 32 CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); 33 assert(CurArray && "Failed to allocate memory?"); 34 memset(CurArray, -1, CurArraySize*sizeof(void*)); 35} 36 37bool SmallPtrSetImpl::insert_imp(const void * Ptr) { 38 if (isSmall()) { 39 // Check to see if it is already in the set. 40 for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 41 APtr != E; ++APtr) 42 if (*APtr == Ptr) 43 return false; 44 45 // Nope, there isn't. If we stay small, just 'pushback' now. 46 if (NumElements < CurArraySize-1) { 47 SmallArray[NumElements++] = Ptr; 48 return true; 49 } 50 // Otherwise, hit the big set case, which will call grow. 51 } 52 53 if (NumElements*4 >= CurArraySize*3) { 54 // If more than 3/4 of the array is full, grow. 55 Grow(CurArraySize < 64 ? 128 : CurArraySize*2); 56 } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) { 57 // If fewer of 1/8 of the array is empty (meaning that many are filled with 58 // tombstones), rehash. 59 Grow(CurArraySize); 60 } 61 62 // Okay, we know we have space. Find a hash bucket. 63 const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 64 if (*Bucket == Ptr) return false; // Already inserted, good. 65 66 // Otherwise, insert it! 67 if (*Bucket == getTombstoneMarker()) 68 --NumTombstones; 69 *Bucket = Ptr; 70 ++NumElements; // Track density. 71 return true; 72} 73 74bool SmallPtrSetImpl::erase_imp(const void * Ptr) { 75 if (isSmall()) { 76 // Check to see if it is in the set. 77 for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 78 APtr != E; ++APtr) 79 if (*APtr == Ptr) { 80 // If it is in the set, replace this element. 81 *APtr = E[-1]; 82 E[-1] = getEmptyMarker(); 83 --NumElements; 84 return true; 85 } 86 87 return false; 88 } 89 90 // Okay, we know we have space. Find a hash bucket. 91 void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 92 if (*Bucket != Ptr) return false; // Not in the set? 93 94 // Set this as a tombstone. 95 *Bucket = getTombstoneMarker(); 96 --NumElements; 97 ++NumTombstones; 98 return true; 99} 100 101const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { 102 unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1); 103 unsigned ArraySize = CurArraySize; 104 unsigned ProbeAmt = 1; 105 const void *const *Array = CurArray; 106 const void *const *Tombstone = 0; 107 while (1) { 108 // Found Ptr's bucket? 109 if (Array[Bucket] == Ptr) 110 return Array+Bucket; 111 112 // If we found an empty bucket, the pointer doesn't exist in the set. 113 // Return a tombstone if we've seen one so far, or the empty bucket if 114 // not. 115 if (Array[Bucket] == getEmptyMarker()) 116 return Tombstone ? Tombstone : Array+Bucket; 117 118 // If this is a tombstone, remember it. If Ptr ends up not in the set, we 119 // prefer to return it than something that would require more probing. 120 if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 121 Tombstone = Array+Bucket; // Remember the first tombstone found. 122 123 // It's a hash collision or a tombstone. Reprobe. 124 Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 125 } 126} 127 128/// Grow - Allocate a larger backing store for the buckets and move it over. 129/// 130void SmallPtrSetImpl::Grow(unsigned NewSize) { 131 // Allocate at twice as many buckets, but at least 128. 132 unsigned OldSize = CurArraySize; 133 134 const void **OldBuckets = CurArray; 135 bool WasSmall = isSmall(); 136 137 // Install the new array. Clear all the buckets to empty. 138 CurArray = (const void**)malloc(sizeof(void*) * NewSize); 139 assert(CurArray && "Failed to allocate memory?"); 140 CurArraySize = NewSize; 141 memset(CurArray, -1, NewSize*sizeof(void*)); 142 143 // Copy over all the elements. 144 if (WasSmall) { 145 // Small sets store their elements in order. 146 for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 147 BucketPtr != E; ++BucketPtr) { 148 const void *Elt = *BucketPtr; 149 *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 150 } 151 } else { 152 // Copy over all valid entries. 153 for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 154 BucketPtr != E; ++BucketPtr) { 155 // Copy over the element if it is valid. 156 const void *Elt = *BucketPtr; 157 if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 158 *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 159 } 160 161 free(OldBuckets); 162 NumTombstones = 0; 163 } 164} 165 166SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, 167 const SmallPtrSetImpl& that) { 168 SmallArray = SmallStorage; 169 170 // If we're becoming small, prepare to insert into our stack space 171 if (that.isSmall()) { 172 CurArray = SmallArray; 173 // Otherwise, allocate new heap space (unless we were the same size) 174 } else { 175 CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); 176 assert(CurArray && "Failed to allocate memory?"); 177 } 178 179 // Copy over the new array size 180 CurArraySize = that.CurArraySize; 181 182 // Copy over the contents from the other set 183 memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); 184 185 NumElements = that.NumElements; 186 NumTombstones = that.NumTombstones; 187} 188 189/// CopyFrom - implement operator= from a smallptrset that has the same pointer 190/// type, but may have a different small size. 191void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { 192 if (isSmall() && RHS.isSmall()) 193 assert(CurArraySize == RHS.CurArraySize && 194 "Cannot assign sets with different small sizes"); 195 196 // If we're becoming small, prepare to insert into our stack space 197 if (RHS.isSmall()) { 198 if (!isSmall()) 199 free(CurArray); 200 CurArray = SmallArray; 201 // Otherwise, allocate new heap space (unless we were the same size) 202 } else if (CurArraySize != RHS.CurArraySize) { 203 if (isSmall()) 204 CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); 205 else 206 CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); 207 assert(CurArray && "Failed to allocate memory?"); 208 } 209 210 // Copy over the new array size 211 CurArraySize = RHS.CurArraySize; 212 213 // Copy over the contents from the other set 214 memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); 215 216 NumElements = RHS.NumElements; 217 NumTombstones = RHS.NumTombstones; 218} 219 220void SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) { 221 if (this == &RHS) return; 222 223 // We can only avoid copying elements if neither set is small. 224 if (!this->isSmall() && !RHS.isSmall()) { 225 std::swap(this->CurArray, RHS.CurArray); 226 std::swap(this->CurArraySize, RHS.CurArraySize); 227 std::swap(this->NumElements, RHS.NumElements); 228 std::swap(this->NumTombstones, RHS.NumTombstones); 229 return; 230 } 231 232 // FIXME: From here on we assume that both sets have the same small size. 233 234 // If only RHS is small, copy the small elements into LHS and move the pointer 235 // from LHS to RHS. 236 if (!this->isSmall() && RHS.isSmall()) { 237 std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize, 238 this->SmallArray); 239 std::swap(this->NumElements, RHS.NumElements); 240 std::swap(this->CurArraySize, RHS.CurArraySize); 241 RHS.CurArray = this->CurArray; 242 RHS.NumTombstones = this->NumTombstones; 243 this->CurArray = this->SmallArray; 244 this->NumTombstones = 0; 245 return; 246 } 247 248 // If only LHS is small, copy the small elements into RHS and move the pointer 249 // from RHS to LHS. 250 if (this->isSmall() && !RHS.isSmall()) { 251 std::copy(this->SmallArray, this->SmallArray+this->CurArraySize, 252 RHS.SmallArray); 253 std::swap(RHS.NumElements, this->NumElements); 254 std::swap(RHS.CurArraySize, this->CurArraySize); 255 this->CurArray = RHS.CurArray; 256 this->NumTombstones = RHS.NumTombstones; 257 RHS.CurArray = RHS.SmallArray; 258 RHS.NumTombstones = 0; 259 return; 260 } 261 262 // Both a small, just swap the small elements. 263 assert(this->isSmall() && RHS.isSmall()); 264 assert(this->CurArraySize == RHS.CurArraySize); 265 std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize, 266 RHS.SmallArray); 267 std::swap(this->NumElements, RHS.NumElements); 268} 269 270SmallPtrSetImpl::~SmallPtrSetImpl() { 271 if (!isSmall()) 272 free(CurArray); 273} 274