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 21 using namespace llvm; 22 23 void SmallPtrSetImplBase::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 37 std::pair<const void *const *, bool> 38 SmallPtrSetImplBase::insert_imp(const void *Ptr) { 39 if (isSmall()) { 40 // Check to see if it is already in the set. 41 for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 42 APtr != E; ++APtr) 43 if (*APtr == Ptr) 44 return std::make_pair(APtr, false); 45 46 // Nope, there isn't. If we stay small, just 'pushback' now. 47 if (NumElements < CurArraySize) { 48 SmallArray[NumElements++] = Ptr; 49 return std::make_pair(SmallArray + (NumElements - 1), true); 50 } 51 // Otherwise, hit the big set case, which will call grow. 52 } 53 54 if (LLVM_UNLIKELY(NumElements * 4 >= CurArraySize * 3)) { 55 // If more than 3/4 of the array is full, grow. 56 Grow(CurArraySize < 64 ? 128 : CurArraySize*2); 57 } else if (LLVM_UNLIKELY(CurArraySize - (NumElements + NumTombstones) < 58 CurArraySize / 8)) { 59 // If fewer of 1/8 of the array is empty (meaning that many are filled with 60 // tombstones), rehash. 61 Grow(CurArraySize); 62 } 63 64 // Okay, we know we have space. Find a hash bucket. 65 const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 66 if (*Bucket == Ptr) 67 return std::make_pair(Bucket, false); // Already inserted, good. 68 69 // Otherwise, insert it! 70 if (*Bucket == getTombstoneMarker()) 71 --NumTombstones; 72 *Bucket = Ptr; 73 ++NumElements; // Track density. 74 return std::make_pair(Bucket, true); 75 } 76 77 bool SmallPtrSetImplBase::erase_imp(const void * Ptr) { 78 if (isSmall()) { 79 // Check to see if it is in the set. 80 for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 81 APtr != E; ++APtr) 82 if (*APtr == Ptr) { 83 // If it is in the set, replace this element. 84 *APtr = E[-1]; 85 E[-1] = getEmptyMarker(); 86 --NumElements; 87 return true; 88 } 89 90 return false; 91 } 92 93 // Okay, we know we have space. Find a hash bucket. 94 void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 95 if (*Bucket != Ptr) return false; // Not in the set? 96 97 // Set this as a tombstone. 98 *Bucket = getTombstoneMarker(); 99 --NumElements; 100 ++NumTombstones; 101 return true; 102 } 103 104 const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const { 105 unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1); 106 unsigned ArraySize = CurArraySize; 107 unsigned ProbeAmt = 1; 108 const void *const *Array = CurArray; 109 const void *const *Tombstone = nullptr; 110 while (1) { 111 // If we found an empty bucket, the pointer doesn't exist in the set. 112 // Return a tombstone if we've seen one so far, or the empty bucket if 113 // not. 114 if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker())) 115 return Tombstone ? Tombstone : Array+Bucket; 116 117 // Found Ptr's bucket? 118 if (LLVM_LIKELY(Array[Bucket] == Ptr)) 119 return Array+Bucket; 120 121 // If this is a tombstone, remember it. If Ptr ends up not in the set, we 122 // prefer to return it than something that would require more probing. 123 if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 124 Tombstone = Array+Bucket; // Remember the first tombstone found. 125 126 // It's a hash collision or a tombstone. Reprobe. 127 Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 128 } 129 } 130 131 /// Grow - Allocate a larger backing store for the buckets and move it over. 132 /// 133 void SmallPtrSetImplBase::Grow(unsigned NewSize) { 134 // Allocate at twice as many buckets, but at least 128. 135 unsigned OldSize = CurArraySize; 136 137 const void **OldBuckets = CurArray; 138 bool WasSmall = isSmall(); 139 140 // Install the new array. Clear all the buckets to empty. 141 CurArray = (const void**)malloc(sizeof(void*) * NewSize); 142 assert(CurArray && "Failed to allocate memory?"); 143 CurArraySize = NewSize; 144 memset(CurArray, -1, NewSize*sizeof(void*)); 145 146 // Copy over all the elements. 147 if (WasSmall) { 148 // Small sets store their elements in order. 149 for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 150 BucketPtr != E; ++BucketPtr) { 151 const void *Elt = *BucketPtr; 152 *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 153 } 154 } else { 155 // Copy over all valid entries. 156 for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 157 BucketPtr != E; ++BucketPtr) { 158 // Copy over the element if it is valid. 159 const void *Elt = *BucketPtr; 160 if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 161 *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 162 } 163 164 free(OldBuckets); 165 NumTombstones = 0; 166 } 167 } 168 169 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, 170 const SmallPtrSetImplBase& that) { 171 SmallArray = SmallStorage; 172 173 // If we're becoming small, prepare to insert into our stack space 174 if (that.isSmall()) { 175 CurArray = SmallArray; 176 // Otherwise, allocate new heap space (unless we were the same size) 177 } else { 178 CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); 179 assert(CurArray && "Failed to allocate memory?"); 180 } 181 182 // Copy over the new array size 183 CurArraySize = that.CurArraySize; 184 185 // Copy over the contents from the other set 186 memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); 187 188 NumElements = that.NumElements; 189 NumTombstones = that.NumTombstones; 190 } 191 192 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, 193 unsigned SmallSize, 194 SmallPtrSetImplBase &&that) { 195 SmallArray = SmallStorage; 196 197 // Copy over the basic members. 198 CurArraySize = that.CurArraySize; 199 NumElements = that.NumElements; 200 NumTombstones = that.NumTombstones; 201 202 // When small, just copy into our small buffer. 203 if (that.isSmall()) { 204 CurArray = SmallArray; 205 memcpy(CurArray, that.CurArray, sizeof(void *) * CurArraySize); 206 } else { 207 // Otherwise, we steal the large memory allocation and no copy is needed. 208 CurArray = that.CurArray; 209 that.CurArray = that.SmallArray; 210 } 211 212 // Make the "that" object small and empty. 213 that.CurArraySize = SmallSize; 214 assert(that.CurArray == that.SmallArray); 215 that.NumElements = 0; 216 that.NumTombstones = 0; 217 } 218 219 /// CopyFrom - implement operator= from a smallptrset that has the same pointer 220 /// type, but may have a different small size. 221 void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) { 222 assert(&RHS != this && "Self-copy should be handled by the caller."); 223 224 if (isSmall() && RHS.isSmall()) 225 assert(CurArraySize == RHS.CurArraySize && 226 "Cannot assign sets with different small sizes"); 227 228 // If we're becoming small, prepare to insert into our stack space 229 if (RHS.isSmall()) { 230 if (!isSmall()) 231 free(CurArray); 232 CurArray = SmallArray; 233 // Otherwise, allocate new heap space (unless we were the same size) 234 } else if (CurArraySize != RHS.CurArraySize) { 235 if (isSmall()) 236 CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); 237 else { 238 const void **T = (const void**)realloc(CurArray, 239 sizeof(void*) * RHS.CurArraySize); 240 if (!T) 241 free(CurArray); 242 CurArray = T; 243 } 244 assert(CurArray && "Failed to allocate memory?"); 245 } 246 247 // Copy over the new array size 248 CurArraySize = RHS.CurArraySize; 249 250 // Copy over the contents from the other set 251 memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); 252 253 NumElements = RHS.NumElements; 254 NumTombstones = RHS.NumTombstones; 255 } 256 257 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize, 258 SmallPtrSetImplBase &&RHS) { 259 assert(&RHS != this && "Self-move should be handled by the caller."); 260 261 if (!isSmall()) 262 free(CurArray); 263 264 if (RHS.isSmall()) { 265 // Copy a small RHS rather than moving. 266 CurArray = SmallArray; 267 memcpy(CurArray, RHS.CurArray, sizeof(void*)*RHS.CurArraySize); 268 } else { 269 CurArray = RHS.CurArray; 270 RHS.CurArray = RHS.SmallArray; 271 } 272 273 // Copy the rest of the trivial members. 274 CurArraySize = RHS.CurArraySize; 275 NumElements = RHS.NumElements; 276 NumTombstones = RHS.NumTombstones; 277 278 // Make the RHS small and empty. 279 RHS.CurArraySize = SmallSize; 280 assert(RHS.CurArray == RHS.SmallArray); 281 RHS.NumElements = 0; 282 RHS.NumTombstones = 0; 283 } 284 285 void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) { 286 if (this == &RHS) return; 287 288 // We can only avoid copying elements if neither set is small. 289 if (!this->isSmall() && !RHS.isSmall()) { 290 std::swap(this->CurArray, RHS.CurArray); 291 std::swap(this->CurArraySize, RHS.CurArraySize); 292 std::swap(this->NumElements, RHS.NumElements); 293 std::swap(this->NumTombstones, RHS.NumTombstones); 294 return; 295 } 296 297 // FIXME: From here on we assume that both sets have the same small size. 298 299 // If only RHS is small, copy the small elements into LHS and move the pointer 300 // from LHS to RHS. 301 if (!this->isSmall() && RHS.isSmall()) { 302 std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize, 303 this->SmallArray); 304 std::swap(this->NumElements, RHS.NumElements); 305 std::swap(this->CurArraySize, RHS.CurArraySize); 306 RHS.CurArray = this->CurArray; 307 RHS.NumTombstones = this->NumTombstones; 308 this->CurArray = this->SmallArray; 309 this->NumTombstones = 0; 310 return; 311 } 312 313 // If only LHS is small, copy the small elements into RHS and move the pointer 314 // from RHS to LHS. 315 if (this->isSmall() && !RHS.isSmall()) { 316 std::copy(this->SmallArray, this->SmallArray+this->CurArraySize, 317 RHS.SmallArray); 318 std::swap(RHS.NumElements, this->NumElements); 319 std::swap(RHS.CurArraySize, this->CurArraySize); 320 this->CurArray = RHS.CurArray; 321 this->NumTombstones = RHS.NumTombstones; 322 RHS.CurArray = RHS.SmallArray; 323 RHS.NumTombstones = 0; 324 return; 325 } 326 327 // Both a small, just swap the small elements. 328 assert(this->isSmall() && RHS.isSmall()); 329 assert(this->CurArraySize == RHS.CurArraySize); 330 std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize, 331 RHS.SmallArray); 332 std::swap(this->NumElements, RHS.NumElements); 333 } 334 335 SmallPtrSetImplBase::~SmallPtrSetImplBase() { 336 if (!isSmall()) 337 free(CurArray); 338 } 339