1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the SmallPtrSet class. See SmallPtrSet.h for an 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// overview of the algorithm. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/MathExtras.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cstdlib> 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid SmallPtrSetImpl::shrink_and_clear() { 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!isSmall() && "Can't shrink a small set!"); 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman free(CurArray); 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Reduce the number of buckets. 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumElements = NumTombstones = 0; 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Install the new array. Clear all the buckets to empty. 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(CurArray && "Failed to allocate memory?"); 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman memset(CurArray, -1, CurArraySize*sizeof(void*)); 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The end pointer, always valid, is set to a valid element to help the 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // iterator. 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray[CurArraySize] = 0; 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool SmallPtrSetImpl::insert_imp(const void * Ptr) { 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isSmall()) { 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if it is already in the set. 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman APtr != E; ++APtr) 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*APtr == Ptr) 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Nope, there isn't. If we stay small, just 'pushback' now. 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumElements < CurArraySize-1) { 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallArray[NumElements++] = Ptr; 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, hit the big set case, which will call grow. 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumElements*4 >= CurArraySize*3) { 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If more than 3/4 of the array is full, grow. 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Grow(CurArraySize < 64 ? 128 : CurArraySize*2); 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) { 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If fewer of 1/8 of the array is empty (meaning that many are filled with 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // tombstones), rehash. 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Grow(CurArraySize); 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we know we have space. Find a hash bucket. 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*Bucket == Ptr) return false; // Already inserted, good. 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, insert it! 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*Bucket == getTombstoneMarker()) 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumTombstones; 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman *Bucket = Ptr; 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumElements; // Track density. 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool SmallPtrSetImpl::erase_imp(const void * Ptr) { 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isSmall()) { 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if it is in the set. 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman APtr != E; ++APtr) 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*APtr == Ptr) { 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it is in the set, replace this element. 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman *APtr = E[-1]; 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E[-1] = getEmptyMarker(); 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumElements; 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we know we have space. Find a hash bucket. 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*Bucket != Ptr) return false; // Not in the set? 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Set this as a tombstone. 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman *Bucket = getTombstoneMarker(); 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumElements; 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumTombstones; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanconst void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Bucket = Hash(Ptr); 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ArraySize = CurArraySize; 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ProbeAmt = 1; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void *const *Array = CurArray; 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void *const *Tombstone = 0; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (1) { 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Found Ptr's bucket? 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Array[Bucket] == Ptr) 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Array+Bucket; 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found an empty bucket, the pointer doesn't exist in the set. 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Return a tombstone if we've seen one so far, or the empty bucket if 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not. 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Array[Bucket] == getEmptyMarker()) 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Tombstone ? Tombstone : Array+Bucket; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a tombstone, remember it. If Ptr ends up not in the set, we 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // prefer to return it than something that would require more probing. 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Tombstone = Array+Bucket; // Remember the first tombstone found. 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It's a hash collision or a tombstone. Reprobe. 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Grow - Allocate a larger backing store for the buckets and move it over. 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SmallPtrSetImpl::Grow(unsigned NewSize) { 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Allocate at twice as many buckets, but at least 128. 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldSize = CurArraySize; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void **OldBuckets = CurArray; 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool WasSmall = isSmall(); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Install the new array. Clear all the buckets to empty. 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(CurArray && "Failed to allocate memory?"); 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArraySize = NewSize; 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman memset(CurArray, -1, NewSize*sizeof(void*)); 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The end pointer, always valid, is set to a valid element to help the 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // iterator. 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray[NewSize] = 0; 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over all the elements. 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (WasSmall) { 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Small sets store their elements in order. 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketPtr != E; ++BucketPtr) { 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void *Elt = *BucketPtr; 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over all valid entries. 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketPtr != E; ++BucketPtr) { 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over the element if it is valid. 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void *Elt = *BucketPtr; 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman free(OldBuckets); 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SmallPtrSetImpl& that) { 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallArray = SmallStorage; 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we're becoming small, prepare to insert into our stack space 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (that.isSmall()) { 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = SmallArray; 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, allocate new heap space (unless we were the same size) 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(CurArray && "Failed to allocate memory?"); 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over the new array size 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArraySize = that.CurArraySize; 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over the contents from the other set 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumElements = that.NumElements; 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = that.NumTombstones; 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// CopyFrom - implement operator= from a smallptrset that has the same pointer 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// type, but may have a different small size. 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isSmall() && RHS.isSmall()) 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(CurArraySize == RHS.CurArraySize && 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Cannot assign sets with different small sizes"); 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we're becoming small, prepare to insert into our stack space 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (RHS.isSmall()) { 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isSmall()) 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman free(CurArray); 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = SmallArray; 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, allocate new heap space (unless we were the same size) 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (CurArraySize != RHS.CurArraySize) { 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isSmall()) 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(CurArray && "Failed to allocate memory?"); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over the new array size 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurArraySize = RHS.CurArraySize; 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy over the contents from the other set 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumElements = RHS.NumElements; 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = RHS.NumTombstones; 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSmallPtrSetImpl::~SmallPtrSetImpl() { 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isSmall()) 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman free(CurArray); 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 230