1193323Sed//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements the SmallPtrSet class. See SmallPtrSet.h for an 10193323Sed// overview of the algorithm. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#include "llvm/ADT/SmallPtrSet.h" 15234982Sdim#include "llvm/ADT/DenseMapInfo.h" 16193323Sed#include "llvm/Support/MathExtras.h" 17327952Sdim#include "llvm/Support/ErrorHandling.h" 18234353Sdim#include <algorithm> 19314564Sdim#include <cassert> 20193323Sed#include <cstdlib> 21193323Sed 22193323Sedusing namespace llvm; 23193323Sed 24276479Sdimvoid SmallPtrSetImplBase::shrink_and_clear() { 25193323Sed assert(!isSmall() && "Can't shrink a small set!"); 26193323Sed free(CurArray); 27193323Sed 28193323Sed // Reduce the number of buckets. 29309124Sdim unsigned Size = size(); 30309124Sdim CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32; 31309124Sdim NumNonEmpty = NumTombstones = 0; 32193323Sed 33193323Sed // Install the new array. Clear all the buckets to empty. 34341825Sdim CurArray = (const void**)safe_malloc(sizeof(void*) * CurArraySize); 35327952Sdim 36193323Sed memset(CurArray, -1, CurArraySize*sizeof(void*)); 37193323Sed} 38193323Sed 39280031Sdimstd::pair<const void *const *, bool> 40309124SdimSmallPtrSetImplBase::insert_imp_big(const void *Ptr) { 41309124Sdim if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) { 42221345Sdim // If more than 3/4 of the array is full, grow. 43309124Sdim Grow(CurArraySize < 64 ? 128 : CurArraySize * 2); 44309124Sdim } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) { 45221345Sdim // If fewer of 1/8 of the array is empty (meaning that many are filled with 46221345Sdim // tombstones), rehash. 47221345Sdim Grow(CurArraySize); 48221345Sdim } 49309124Sdim 50193323Sed // Okay, we know we have space. Find a hash bucket. 51193323Sed const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 52280031Sdim if (*Bucket == Ptr) 53280031Sdim return std::make_pair(Bucket, false); // Already inserted, good. 54280031Sdim 55193323Sed // Otherwise, insert it! 56193323Sed if (*Bucket == getTombstoneMarker()) 57193323Sed --NumTombstones; 58309124Sdim else 59309124Sdim ++NumNonEmpty; // Track density. 60193323Sed *Bucket = Ptr; 61327952Sdim incrementEpoch(); 62280031Sdim return std::make_pair(Bucket, true); 63193323Sed} 64193323Sed 65276479Sdimconst void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const { 66234982Sdim unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1); 67193323Sed unsigned ArraySize = CurArraySize; 68193323Sed unsigned ProbeAmt = 1; 69193323Sed const void *const *Array = CurArray; 70276479Sdim const void *const *Tombstone = nullptr; 71314564Sdim while (true) { 72193323Sed // If we found an empty bucket, the pointer doesn't exist in the set. 73193323Sed // Return a tombstone if we've seen one so far, or the empty bucket if 74193323Sed // not. 75288943Sdim if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker())) 76193323Sed return Tombstone ? Tombstone : Array+Bucket; 77288943Sdim 78288943Sdim // Found Ptr's bucket? 79288943Sdim if (LLVM_LIKELY(Array[Bucket] == Ptr)) 80288943Sdim return Array+Bucket; 81288943Sdim 82193323Sed // If this is a tombstone, remember it. If Ptr ends up not in the set, we 83193323Sed // prefer to return it than something that would require more probing. 84193323Sed if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 85193323Sed Tombstone = Array+Bucket; // Remember the first tombstone found. 86309124Sdim 87193323Sed // It's a hash collision or a tombstone. Reprobe. 88193323Sed Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 89193323Sed } 90193323Sed} 91193323Sed 92193323Sed/// Grow - Allocate a larger backing store for the buckets and move it over. 93193323Sed/// 94276479Sdimvoid SmallPtrSetImplBase::Grow(unsigned NewSize) { 95193323Sed const void **OldBuckets = CurArray; 96309124Sdim const void **OldEnd = EndPointer(); 97193323Sed bool WasSmall = isSmall(); 98309124Sdim 99193323Sed // Install the new array. Clear all the buckets to empty. 100341825Sdim const void **NewBuckets = (const void**) safe_malloc(sizeof(void*) * NewSize); 101327952Sdim 102327952Sdim // Reset member only if memory was allocated successfully 103327952Sdim CurArray = NewBuckets; 104193323Sed CurArraySize = NewSize; 105193323Sed memset(CurArray, -1, NewSize*sizeof(void*)); 106309124Sdim 107309124Sdim // Copy over all valid entries. 108309124Sdim for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) { 109309124Sdim // Copy over the element if it is valid. 110309124Sdim const void *Elt = *BucketPtr; 111309124Sdim if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 112193323Sed *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 113309124Sdim } 114309124Sdim 115309124Sdim if (!WasSmall) 116193323Sed free(OldBuckets); 117309124Sdim NumNonEmpty -= NumTombstones; 118309124Sdim NumTombstones = 0; 119193323Sed} 120193323Sed 121276479SdimSmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, 122309124Sdim const SmallPtrSetImplBase &that) { 123210299Sed SmallArray = SmallStorage; 124210299Sed 125193323Sed // If we're becoming small, prepare to insert into our stack space 126193323Sed if (that.isSmall()) { 127210299Sed CurArray = SmallArray; 128193323Sed // Otherwise, allocate new heap space (unless we were the same size) 129193323Sed } else { 130341825Sdim CurArray = (const void**)safe_malloc(sizeof(void*) * that.CurArraySize); 131193323Sed } 132193323Sed 133309124Sdim // Copy over the that array. 134309124Sdim CopyHelper(that); 135193323Sed} 136193323Sed 137276479SdimSmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, 138276479Sdim unsigned SmallSize, 139276479Sdim SmallPtrSetImplBase &&that) { 140276479Sdim SmallArray = SmallStorage; 141309124Sdim MoveHelper(SmallSize, std::move(that)); 142276479Sdim} 143276479Sdim 144276479Sdimvoid SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) { 145276479Sdim assert(&RHS != this && "Self-copy should be handled by the caller."); 146276479Sdim 147193323Sed if (isSmall() && RHS.isSmall()) 148193323Sed assert(CurArraySize == RHS.CurArraySize && 149193323Sed "Cannot assign sets with different small sizes"); 150249423Sdim 151193323Sed // If we're becoming small, prepare to insert into our stack space 152193323Sed if (RHS.isSmall()) { 153193323Sed if (!isSmall()) 154193323Sed free(CurArray); 155210299Sed CurArray = SmallArray; 156193323Sed // Otherwise, allocate new heap space (unless we were the same size) 157193323Sed } else if (CurArraySize != RHS.CurArraySize) { 158193323Sed if (isSmall()) 159341825Sdim CurArray = (const void**)safe_malloc(sizeof(void*) * RHS.CurArraySize); 160261991Sdim else { 161341825Sdim const void **T = (const void**)safe_realloc(CurArray, 162261991Sdim sizeof(void*) * RHS.CurArraySize); 163261991Sdim CurArray = T; 164261991Sdim } 165193323Sed } 166309124Sdim 167309124Sdim CopyHelper(RHS); 168309124Sdim} 169309124Sdim 170309124Sdimvoid SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) { 171193323Sed // Copy over the new array size 172193323Sed CurArraySize = RHS.CurArraySize; 173193323Sed 174193323Sed // Copy over the contents from the other set 175309124Sdim std::copy(RHS.CurArray, RHS.EndPointer(), CurArray); 176309124Sdim 177309124Sdim NumNonEmpty = RHS.NumNonEmpty; 178193323Sed NumTombstones = RHS.NumTombstones; 179193323Sed} 180193323Sed 181276479Sdimvoid SmallPtrSetImplBase::MoveFrom(unsigned SmallSize, 182276479Sdim SmallPtrSetImplBase &&RHS) { 183276479Sdim if (!isSmall()) 184276479Sdim free(CurArray); 185309124Sdim MoveHelper(SmallSize, std::move(RHS)); 186309124Sdim} 187276479Sdim 188309124Sdimvoid SmallPtrSetImplBase::MoveHelper(unsigned SmallSize, 189309124Sdim SmallPtrSetImplBase &&RHS) { 190309124Sdim assert(&RHS != this && "Self-move should be handled by the caller."); 191309124Sdim 192276479Sdim if (RHS.isSmall()) { 193276479Sdim // Copy a small RHS rather than moving. 194276479Sdim CurArray = SmallArray; 195309124Sdim std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray); 196276479Sdim } else { 197276479Sdim CurArray = RHS.CurArray; 198276479Sdim RHS.CurArray = RHS.SmallArray; 199276479Sdim } 200276479Sdim 201276479Sdim // Copy the rest of the trivial members. 202276479Sdim CurArraySize = RHS.CurArraySize; 203309124Sdim NumNonEmpty = RHS.NumNonEmpty; 204276479Sdim NumTombstones = RHS.NumTombstones; 205276479Sdim 206276479Sdim // Make the RHS small and empty. 207276479Sdim RHS.CurArraySize = SmallSize; 208276479Sdim assert(RHS.CurArray == RHS.SmallArray); 209309124Sdim RHS.NumNonEmpty = 0; 210276479Sdim RHS.NumTombstones = 0; 211276479Sdim} 212276479Sdim 213276479Sdimvoid SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) { 214234353Sdim if (this == &RHS) return; 215234353Sdim 216234353Sdim // We can only avoid copying elements if neither set is small. 217234353Sdim if (!this->isSmall() && !RHS.isSmall()) { 218234353Sdim std::swap(this->CurArray, RHS.CurArray); 219234353Sdim std::swap(this->CurArraySize, RHS.CurArraySize); 220309124Sdim std::swap(this->NumNonEmpty, RHS.NumNonEmpty); 221234353Sdim std::swap(this->NumTombstones, RHS.NumTombstones); 222234353Sdim return; 223234353Sdim } 224234353Sdim 225234353Sdim // FIXME: From here on we assume that both sets have the same small size. 226234353Sdim 227234353Sdim // If only RHS is small, copy the small elements into LHS and move the pointer 228234353Sdim // from LHS to RHS. 229234353Sdim if (!this->isSmall() && RHS.isSmall()) { 230309124Sdim assert(RHS.CurArray == RHS.SmallArray); 231309124Sdim std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray); 232309124Sdim std::swap(RHS.CurArraySize, this->CurArraySize); 233309124Sdim std::swap(this->NumNonEmpty, RHS.NumNonEmpty); 234309124Sdim std::swap(this->NumTombstones, RHS.NumTombstones); 235234353Sdim RHS.CurArray = this->CurArray; 236234353Sdim this->CurArray = this->SmallArray; 237234353Sdim return; 238234353Sdim } 239234353Sdim 240234353Sdim // If only LHS is small, copy the small elements into RHS and move the pointer 241234353Sdim // from RHS to LHS. 242234353Sdim if (this->isSmall() && !RHS.isSmall()) { 243309124Sdim assert(this->CurArray == this->SmallArray); 244309124Sdim std::copy(this->CurArray, this->CurArray + this->NumNonEmpty, 245234353Sdim RHS.SmallArray); 246234353Sdim std::swap(RHS.CurArraySize, this->CurArraySize); 247309124Sdim std::swap(RHS.NumNonEmpty, this->NumNonEmpty); 248309124Sdim std::swap(RHS.NumTombstones, this->NumTombstones); 249234353Sdim this->CurArray = RHS.CurArray; 250234353Sdim RHS.CurArray = RHS.SmallArray; 251234353Sdim return; 252234353Sdim } 253234353Sdim 254234353Sdim // Both a small, just swap the small elements. 255234353Sdim assert(this->isSmall() && RHS.isSmall()); 256309124Sdim unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty); 257309124Sdim std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty, 258309124Sdim RHS.SmallArray); 259309124Sdim if (this->NumNonEmpty > MinNonEmpty) { 260309124Sdim std::copy(this->SmallArray + MinNonEmpty, 261309124Sdim this->SmallArray + this->NumNonEmpty, 262309124Sdim RHS.SmallArray + MinNonEmpty); 263309124Sdim } else { 264309124Sdim std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty, 265309124Sdim this->SmallArray + MinNonEmpty); 266309124Sdim } 267234353Sdim assert(this->CurArraySize == RHS.CurArraySize); 268309124Sdim std::swap(this->NumNonEmpty, RHS.NumNonEmpty); 269309124Sdim std::swap(this->NumTombstones, RHS.NumTombstones); 270234353Sdim} 271