1193323Sed//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the SmallPtrSet class. See SmallPtrSet.h for an 11193323Sed// overview of the algorithm. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/ADT/SmallPtrSet.h" 16235633Sdim#include "llvm/ADT/DenseMapInfo.h" 17193323Sed#include "llvm/Support/MathExtras.h" 18235633Sdim#include <algorithm> 19193323Sed#include <cstdlib> 20193323Sed 21193323Sedusing namespace llvm; 22193323Sed 23193323Sedvoid SmallPtrSetImpl::shrink_and_clear() { 24193323Sed assert(!isSmall() && "Can't shrink a small set!"); 25193323Sed free(CurArray); 26193323Sed 27193323Sed // Reduce the number of buckets. 28193323Sed CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; 29193323Sed NumElements = NumTombstones = 0; 30193323Sed 31193323Sed // Install the new array. Clear all the buckets to empty. 32252723Sdim CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); 33193323Sed assert(CurArray && "Failed to allocate memory?"); 34193323Sed memset(CurArray, -1, CurArraySize*sizeof(void*)); 35193323Sed} 36193323Sed 37193323Sedbool SmallPtrSetImpl::insert_imp(const void * Ptr) { 38193323Sed if (isSmall()) { 39193323Sed // Check to see if it is already in the set. 40193323Sed for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 41193323Sed APtr != E; ++APtr) 42193323Sed if (*APtr == Ptr) 43193323Sed return false; 44193323Sed 45193323Sed // Nope, there isn't. If we stay small, just 'pushback' now. 46193323Sed if (NumElements < CurArraySize-1) { 47193323Sed SmallArray[NumElements++] = Ptr; 48193323Sed return true; 49193323Sed } 50193323Sed // Otherwise, hit the big set case, which will call grow. 51193323Sed } 52193323Sed 53221345Sdim if (NumElements*4 >= CurArraySize*3) { 54221345Sdim // If more than 3/4 of the array is full, grow. 55221345Sdim Grow(CurArraySize < 64 ? 128 : CurArraySize*2); 56221345Sdim } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) { 57221345Sdim // If fewer of 1/8 of the array is empty (meaning that many are filled with 58221345Sdim // tombstones), rehash. 59221345Sdim Grow(CurArraySize); 60221345Sdim } 61193323Sed 62193323Sed // Okay, we know we have space. Find a hash bucket. 63193323Sed const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 64193323Sed if (*Bucket == Ptr) return false; // Already inserted, good. 65193323Sed 66193323Sed // Otherwise, insert it! 67193323Sed if (*Bucket == getTombstoneMarker()) 68193323Sed --NumTombstones; 69193323Sed *Bucket = Ptr; 70193323Sed ++NumElements; // Track density. 71193323Sed return true; 72193323Sed} 73193323Sed 74193323Sedbool SmallPtrSetImpl::erase_imp(const void * Ptr) { 75193323Sed if (isSmall()) { 76193323Sed // Check to see if it is in the set. 77193323Sed for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 78193323Sed APtr != E; ++APtr) 79193323Sed if (*APtr == Ptr) { 80193323Sed // If it is in the set, replace this element. 81193323Sed *APtr = E[-1]; 82193323Sed E[-1] = getEmptyMarker(); 83193323Sed --NumElements; 84193323Sed return true; 85193323Sed } 86193323Sed 87193323Sed return false; 88193323Sed } 89193323Sed 90193323Sed // Okay, we know we have space. Find a hash bucket. 91193323Sed void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 92193323Sed if (*Bucket != Ptr) return false; // Not in the set? 93193323Sed 94193323Sed // Set this as a tombstone. 95193323Sed *Bucket = getTombstoneMarker(); 96193323Sed --NumElements; 97193323Sed ++NumTombstones; 98193323Sed return true; 99193323Sed} 100193323Sed 101193323Sedconst void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { 102235633Sdim unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1); 103193323Sed unsigned ArraySize = CurArraySize; 104193323Sed unsigned ProbeAmt = 1; 105193323Sed const void *const *Array = CurArray; 106193323Sed const void *const *Tombstone = 0; 107193323Sed while (1) { 108193323Sed // Found Ptr's bucket? 109193323Sed if (Array[Bucket] == Ptr) 110193323Sed return Array+Bucket; 111193323Sed 112193323Sed // If we found an empty bucket, the pointer doesn't exist in the set. 113193323Sed // Return a tombstone if we've seen one so far, or the empty bucket if 114193323Sed // not. 115193323Sed if (Array[Bucket] == getEmptyMarker()) 116193323Sed return Tombstone ? Tombstone : Array+Bucket; 117193323Sed 118193323Sed // If this is a tombstone, remember it. If Ptr ends up not in the set, we 119193323Sed // prefer to return it than something that would require more probing. 120193323Sed if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 121193323Sed Tombstone = Array+Bucket; // Remember the first tombstone found. 122193323Sed 123193323Sed // It's a hash collision or a tombstone. Reprobe. 124193323Sed Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 125193323Sed } 126193323Sed} 127193323Sed 128193323Sed/// Grow - Allocate a larger backing store for the buckets and move it over. 129193323Sed/// 130221345Sdimvoid SmallPtrSetImpl::Grow(unsigned NewSize) { 131193323Sed // Allocate at twice as many buckets, but at least 128. 132193323Sed unsigned OldSize = CurArraySize; 133193323Sed 134193323Sed const void **OldBuckets = CurArray; 135193323Sed bool WasSmall = isSmall(); 136193323Sed 137193323Sed // Install the new array. Clear all the buckets to empty. 138252723Sdim CurArray = (const void**)malloc(sizeof(void*) * NewSize); 139193323Sed assert(CurArray && "Failed to allocate memory?"); 140193323Sed CurArraySize = NewSize; 141193323Sed memset(CurArray, -1, NewSize*sizeof(void*)); 142193323Sed 143193323Sed // Copy over all the elements. 144193323Sed if (WasSmall) { 145193323Sed // Small sets store their elements in order. 146193323Sed for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 147193323Sed BucketPtr != E; ++BucketPtr) { 148193323Sed const void *Elt = *BucketPtr; 149193323Sed *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 150193323Sed } 151193323Sed } else { 152193323Sed // Copy over all valid entries. 153193323Sed for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 154193323Sed BucketPtr != E; ++BucketPtr) { 155193323Sed // Copy over the element if it is valid. 156193323Sed const void *Elt = *BucketPtr; 157193323Sed if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 158193323Sed *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 159193323Sed } 160193323Sed 161193323Sed free(OldBuckets); 162193323Sed NumTombstones = 0; 163193323Sed } 164193323Sed} 165193323Sed 166210299SedSmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, 167210299Sed const SmallPtrSetImpl& that) { 168210299Sed SmallArray = SmallStorage; 169210299Sed 170193323Sed // If we're becoming small, prepare to insert into our stack space 171193323Sed if (that.isSmall()) { 172210299Sed CurArray = SmallArray; 173193323Sed // Otherwise, allocate new heap space (unless we were the same size) 174193323Sed } else { 175252723Sdim CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); 176193323Sed assert(CurArray && "Failed to allocate memory?"); 177193323Sed } 178193323Sed 179193323Sed // Copy over the new array size 180193323Sed CurArraySize = that.CurArraySize; 181193323Sed 182193323Sed // Copy over the contents from the other set 183252723Sdim memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); 184193323Sed 185193323Sed NumElements = that.NumElements; 186193323Sed NumTombstones = that.NumTombstones; 187193323Sed} 188193323Sed 189193323Sed/// CopyFrom - implement operator= from a smallptrset that has the same pointer 190193323Sed/// type, but may have a different small size. 191193323Sedvoid SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { 192193323Sed if (isSmall() && RHS.isSmall()) 193193323Sed assert(CurArraySize == RHS.CurArraySize && 194193323Sed "Cannot assign sets with different small sizes"); 195252723Sdim 196193323Sed // If we're becoming small, prepare to insert into our stack space 197193323Sed if (RHS.isSmall()) { 198193323Sed if (!isSmall()) 199193323Sed free(CurArray); 200210299Sed CurArray = SmallArray; 201193323Sed // Otherwise, allocate new heap space (unless we were the same size) 202193323Sed } else if (CurArraySize != RHS.CurArraySize) { 203193323Sed if (isSmall()) 204252723Sdim CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); 205263509Sdim else { 206263509Sdim const void **T = (const void**)realloc(CurArray, 207263509Sdim sizeof(void*) * RHS.CurArraySize); 208263509Sdim if (!T) 209263509Sdim free(CurArray); 210263509Sdim CurArray = T; 211263509Sdim } 212193323Sed assert(CurArray && "Failed to allocate memory?"); 213193323Sed } 214193323Sed 215193323Sed // Copy over the new array size 216193323Sed CurArraySize = RHS.CurArraySize; 217193323Sed 218193323Sed // Copy over the contents from the other set 219252723Sdim memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); 220193323Sed 221193323Sed NumElements = RHS.NumElements; 222193323Sed NumTombstones = RHS.NumTombstones; 223193323Sed} 224193323Sed 225235633Sdimvoid SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) { 226235633Sdim if (this == &RHS) return; 227235633Sdim 228235633Sdim // We can only avoid copying elements if neither set is small. 229235633Sdim if (!this->isSmall() && !RHS.isSmall()) { 230235633Sdim std::swap(this->CurArray, RHS.CurArray); 231235633Sdim std::swap(this->CurArraySize, RHS.CurArraySize); 232235633Sdim std::swap(this->NumElements, RHS.NumElements); 233235633Sdim std::swap(this->NumTombstones, RHS.NumTombstones); 234235633Sdim return; 235235633Sdim } 236235633Sdim 237235633Sdim // FIXME: From here on we assume that both sets have the same small size. 238235633Sdim 239235633Sdim // If only RHS is small, copy the small elements into LHS and move the pointer 240235633Sdim // from LHS to RHS. 241235633Sdim if (!this->isSmall() && RHS.isSmall()) { 242235633Sdim std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize, 243235633Sdim this->SmallArray); 244235633Sdim std::swap(this->NumElements, RHS.NumElements); 245235633Sdim std::swap(this->CurArraySize, RHS.CurArraySize); 246235633Sdim RHS.CurArray = this->CurArray; 247235633Sdim RHS.NumTombstones = this->NumTombstones; 248235633Sdim this->CurArray = this->SmallArray; 249235633Sdim this->NumTombstones = 0; 250235633Sdim return; 251235633Sdim } 252235633Sdim 253235633Sdim // If only LHS is small, copy the small elements into RHS and move the pointer 254235633Sdim // from RHS to LHS. 255235633Sdim if (this->isSmall() && !RHS.isSmall()) { 256235633Sdim std::copy(this->SmallArray, this->SmallArray+this->CurArraySize, 257235633Sdim RHS.SmallArray); 258235633Sdim std::swap(RHS.NumElements, this->NumElements); 259235633Sdim std::swap(RHS.CurArraySize, this->CurArraySize); 260235633Sdim this->CurArray = RHS.CurArray; 261235633Sdim this->NumTombstones = RHS.NumTombstones; 262235633Sdim RHS.CurArray = RHS.SmallArray; 263235633Sdim RHS.NumTombstones = 0; 264235633Sdim return; 265235633Sdim } 266235633Sdim 267235633Sdim // Both a small, just swap the small elements. 268235633Sdim assert(this->isSmall() && RHS.isSmall()); 269235633Sdim assert(this->CurArraySize == RHS.CurArraySize); 270235633Sdim std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize, 271235633Sdim RHS.SmallArray); 272235633Sdim std::swap(this->NumElements, RHS.NumElements); 273235633Sdim} 274235633Sdim 275193323SedSmallPtrSetImpl::~SmallPtrSetImpl() { 276193323Sed if (!isSmall()) 277193323Sed free(CurArray); 278193323Sed} 279