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