SmallPtrSet.cpp revision e992a56ae93140171f5044079e8d317f784c8cc1
1//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source 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/Support/MathExtras.h" 17#include <cstdlib> 18 19using namespace llvm; 20 21bool SmallPtrSetImpl::insert(const void * Ptr) { 22 if (isSmall()) { 23 // Check to see if it is already in the set. 24 for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 25 APtr != E; ++APtr) 26 if (*APtr == Ptr) 27 return false; 28 29 // Nope, there isn't. If we stay small, just 'pushback' now. 30 if (NumElements < CurArraySize-1) { 31 SmallArray[NumElements++] = Ptr; 32 return true; 33 } 34 // Otherwise, hit the big set case, which will call grow. 35 } 36 37 // If more than 3/4 of the array is full, grow. 38 if (NumElements*4 >= CurArraySize*3 || 39 CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) 40 Grow(); 41 42 // Okay, we know we have space. Find a hash bucket. 43 void **Bucket = const_cast<void**>(FindBucketFor((void*)Ptr)); 44 if (*Bucket == Ptr) return false; // Already inserted, good. 45 46 // Otherwise, insert it! 47 if (*Bucket == getTombstoneMarker()) 48 --NumTombstones; 49 *Bucket = (void*)Ptr; 50 ++NumElements; // Track density. 51 return true; 52} 53 54bool SmallPtrSetImpl::erase(void * const Ptr) { 55 if (isSmall()) { 56 // Check to see if it is in the set. 57 for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 58 APtr != E; ++APtr) 59 if (*APtr == Ptr) { 60 // If it is in the set, replace this element. 61 *APtr = E[-1]; 62 E[-1] = getEmptyMarker(); 63 --NumElements; 64 return true; 65 } 66 67 return false; 68 } 69 70 // Okay, we know we have space. Find a hash bucket. 71 void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 72 if (*Bucket != Ptr) return false; // Not in the set? 73 74 // Set this as a tombstone. 75 *Bucket = getTombstoneMarker(); 76 --NumElements; 77 ++NumTombstones; 78 return true; 79} 80 81const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { 82 unsigned Bucket = Hash(Ptr); 83 unsigned ArraySize = CurArraySize; 84 unsigned ProbeAmt = 1; 85 const void *const *Array = CurArray; 86 const void *const *Tombstone = 0; 87 while (1) { 88 // Found Ptr's bucket? 89 if (Array[Bucket] == Ptr) 90 return Array+Bucket; 91 92 // If we found an empty bucket, the pointer doesn't exist in the set. 93 // Return a tombstone if we've seen one so far, or the empty bucket if 94 // not. 95 if (Array[Bucket] == getEmptyMarker()) 96 return Tombstone ? Tombstone : Array+Bucket; 97 98 // If this is a tombstone, remember it. If Ptr ends up not in the set, we 99 // prefer to return it than something that would require more probing. 100 if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 101 Tombstone = Array+Bucket; // Remember the first tombstone found. 102 103 // It's a hash collision or a tombstone. Reprobe. 104 Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 105 } 106} 107 108/// Grow - Allocate a larger backing store for the buckets and move it over. 109/// 110void SmallPtrSetImpl::Grow() { 111 // Allocate at twice as many buckets, but at least 128. 112 unsigned OldSize = CurArraySize; 113 unsigned NewSize = OldSize < 64 ? 128 : OldSize*2; 114 115 const void **OldBuckets = CurArray; 116 bool WasSmall = isSmall(); 117 118 // Install the new array. Clear all the buckets to empty. 119 CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); 120 assert(CurArray && "Failed to allocate memory?"); 121 CurArraySize = NewSize; 122 memset(CurArray, -1, NewSize*sizeof(void*)); 123 124 // The end pointer, always valid, is set to a valid element to help the 125 // iterator. 126 CurArray[NewSize] = 0; 127 128 // Copy over all the elements. 129 if (WasSmall) { 130 // Small sets store their elements in order. 131 for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 132 BucketPtr != E; ++BucketPtr) { 133 const void *Elt = *BucketPtr; 134 *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 135 } 136 } else { 137 // Copy over all valid entries. 138 for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 139 BucketPtr != E; ++BucketPtr) { 140 // Copy over the element if it is valid. 141 const void *Elt = *BucketPtr; 142 if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 143 *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 144 } 145 146 free(OldBuckets); 147 NumTombstones = 0; 148 } 149} 150 151SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) { 152 // If we're becoming small, prepare to insert into our stack space 153 if (that.isSmall()) { 154 CurArray = &SmallArray[0]; 155 // Otherwise, allocate new heap space (unless we were the same size) 156 } else { 157 CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); 158 assert(CurArray && "Failed to allocate memory?"); 159 } 160 161 // Copy over the new array size 162 CurArraySize = that.CurArraySize; 163 164 // Copy over the contents from the other set 165 memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); 166 167 NumElements = that.NumElements; 168 NumTombstones = that.NumTombstones; 169} 170 171/// CopyFrom - implement operator= from a smallptrset that has the same pointer 172/// type, but may have a different small size. 173void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { 174 if (isSmall() && RHS.isSmall()) 175 assert(CurArraySize == RHS.CurArraySize && 176 "Cannot assign sets with different small sizes"); 177 178 // If we're becoming small, prepare to insert into our stack space 179 if (RHS.isSmall()) { 180 if (!isSmall()) 181 free(CurArray); 182 CurArray = &SmallArray[0]; 183 // Otherwise, allocate new heap space (unless we were the same size) 184 } else if (CurArraySize != RHS.CurArraySize) { 185 if (isSmall()) 186 CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); 187 else 188 CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); 189 assert(CurArray && "Failed to allocate memory?"); 190 } 191 192 // Copy over the new array size 193 CurArraySize = RHS.CurArraySize; 194 195 // Copy over the contents from the other set 196 memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); 197 198 NumElements = RHS.NumElements; 199 NumTombstones = RHS.NumTombstones; 200} 201 202SmallPtrSetImpl::~SmallPtrSetImpl() { 203 if (!isSmall()) 204 free(CurArray); 205} 206