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