SmallPtrSet.cpp revision 2945a32ffd0bf079de1b23db12bc8a0de596a167
1c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===// 2c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner// 3c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner// The LLVM Compiler Infrastructure 4c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner// 8c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner//===----------------------------------------------------------------------===// 9c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner// 1024757decb83a4959969397ef8eec81f986b69daaChris Lattner// This file implements the SmallPtrSet class. See SmallPtrSet.h for an 1124757decb83a4959969397ef8eec81f986b69daaChris Lattner// overview of the algorithm. 12c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner// 13c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner//===----------------------------------------------------------------------===// 14c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 15c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner#include "llvm/ADT/SmallPtrSet.h" 1691f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner#include "llvm/Support/MathExtras.h" 172945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer#include <algorithm> 18845b31de0c58e1f667063170191262079d311052Reid Spencer#include <cstdlib> 19845b31de0c58e1f667063170191262079d311052Reid Spencer 20c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattnerusing namespace llvm; 21c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 2242e4bdf2577946380ce1529d5716e48b33d4186dChris Lattnervoid SmallPtrSetImpl::shrink_and_clear() { 2342e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner assert(!isSmall() && "Can't shrink a small set!"); 2442e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner free(CurArray); 2542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 2642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // Reduce the number of buckets. 2742e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; 2842e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner NumElements = NumTombstones = 0; 2942e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 3042e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // Install the new array. Clear all the buckets to empty. 3142e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); 3242e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner assert(CurArray && "Failed to allocate memory?"); 3342e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner memset(CurArray, -1, CurArraySize*sizeof(void*)); 3442e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 3542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // The end pointer, always valid, is set to a valid element to help the 3642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // iterator. 3742e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner CurArray[CurArraySize] = 0; 3842e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner} 3942e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 40373a733be031f52cebbbcdb15ab5997d9b5f9f17Chris Lattnerbool SmallPtrSetImpl::insert_imp(const void * Ptr) { 41c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (isSmall()) { 42c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Check to see if it is already in the set. 43e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 44c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner APtr != E; ++APtr) 45c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (*APtr == Ptr) 46c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return false; 47c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 48c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Nope, there isn't. If we stay small, just 'pushback' now. 49c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (NumElements < CurArraySize-1) { 50c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner SmallArray[NumElements++] = Ptr; 51c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return true; 52c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 53c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Otherwise, hit the big set case, which will call grow. 54c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 55c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 56e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen if (NumElements*4 >= CurArraySize*3) { 57e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // If more than 3/4 of the array is full, grow. 58e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen Grow(CurArraySize < 64 ? 128 : CurArraySize*2); 59e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) { 60e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // If fewer of 1/8 of the array is empty (meaning that many are filled with 61e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // tombstones), rehash. 62e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen Grow(CurArraySize); 63e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen } 64c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 65c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Okay, we know we have space. Find a hash bucket. 66430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 67c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (*Bucket == Ptr) return false; // Already inserted, good. 68c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 69c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Otherwise, insert it! 70e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner if (*Bucket == getTombstoneMarker()) 71e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner --NumTombstones; 72430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman *Bucket = Ptr; 73c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner ++NumElements; // Track density. 74c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return true; 75c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 76c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 77373a733be031f52cebbbcdb15ab5997d9b5f9f17Chris Lattnerbool SmallPtrSetImpl::erase_imp(const void * Ptr) { 780b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (isSmall()) { 790b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Check to see if it is in the set. 80e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 810b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner APtr != E; ++APtr) 820b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (*APtr == Ptr) { 8361766cae0b635f6a65d4491aa063c5fc12745566Chris Lattner // If it is in the set, replace this element. 8461766cae0b635f6a65d4491aa063c5fc12745566Chris Lattner *APtr = E[-1]; 850b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner E[-1] = getEmptyMarker(); 860b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner --NumElements; 877ef856dfad10615cac37eb0eb7932cd1fbdcf9e8Chris Lattner return true; 880b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner } 890b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 900b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner return false; 910b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner } 920b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 930b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Okay, we know we have space. Find a hash bucket. 940b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 950b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (*Bucket != Ptr) return false; // Not in the set? 960b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 970b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Set this as a tombstone. 980b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner *Bucket = getTombstoneMarker(); 990b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner --NumElements; 100e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner ++NumTombstones; 1010b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner return true; 1020b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner} 1030b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 104e992a56ae93140171f5044079e8d317f784c8cc1Owen Andersonconst void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { 105c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned Bucket = Hash(Ptr); 106c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned ArraySize = CurArraySize; 107c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned ProbeAmt = 1; 108e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *const *Array = CurArray; 109e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *const *Tombstone = 0; 110c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner while (1) { 111c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Found Ptr's bucket? 112c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == Ptr) 113c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return Array+Bucket; 114c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 115c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // If we found an empty bucket, the pointer doesn't exist in the set. 116c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Return a tombstone if we've seen one so far, or the empty bucket if 117c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // not. 118c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == getEmptyMarker()) 119c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return Tombstone ? Tombstone : Array+Bucket; 120c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 121c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // If this is a tombstone, remember it. If Ptr ends up not in the set, we 122c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // prefer to return it than something that would require more probing. 123c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 124c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner Tombstone = Array+Bucket; // Remember the first tombstone found. 125c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 126c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // It's a hash collision or a tombstone. Reprobe. 127c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 128c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 129c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 130c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 131c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner/// Grow - Allocate a larger backing store for the buckets and move it over. 132c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner/// 133e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesenvoid SmallPtrSetImpl::Grow(unsigned NewSize) { 134c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Allocate at twice as many buckets, but at least 128. 135c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned OldSize = CurArraySize; 136c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 137e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void **OldBuckets = CurArray; 138c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner bool WasSmall = isSmall(); 139c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 140c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Install the new array. Clear all the buckets to empty. 141e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); 1421629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 143c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner CurArraySize = NewSize; 144c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner memset(CurArray, -1, NewSize*sizeof(void*)); 145c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 146c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // The end pointer, always valid, is set to a valid element to help the 147c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // iterator. 148c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner CurArray[NewSize] = 0; 149c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 150c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Copy over all the elements. 151c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (WasSmall) { 152c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Small sets store their elements in order. 153e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 154c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner BucketPtr != E; ++BucketPtr) { 155e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *Elt = *BucketPtr; 156e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 157c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 158c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } else { 159c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Copy over all valid entries. 160e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 161c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner BucketPtr != E; ++BucketPtr) { 162c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Copy over the element if it is valid. 163e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *Elt = *BucketPtr; 164c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 165e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 166c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 167c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 1681629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson free(OldBuckets); 169ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen NumTombstones = 0; 170ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen } 171ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen} 172ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen 1732a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan SandsSmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, 1742a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands const SmallPtrSetImpl& that) { 1752a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands SmallArray = SmallStorage; 1762a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands 177bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // If we're becoming small, prepare to insert into our stack space 178ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen if (that.isSmall()) { 1792a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands CurArray = SmallArray; 180bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Otherwise, allocate new heap space (unless we were the same size) 181ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen } else { 182e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); 1831629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 184c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 185bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 186bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Copy over the new array size 187bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson CurArraySize = that.CurArraySize; 188bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 189bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Copy over the contents from the other set 190bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); 191bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 192bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson NumElements = that.NumElements; 193bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson NumTombstones = that.NumTombstones; 194c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 19591f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner 19691f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner/// CopyFrom - implement operator= from a smallptrset that has the same pointer 19791f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner/// type, but may have a different small size. 19891f0158d4d1b16b8615126b05582d421cfb14089Chris Lattnervoid SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { 19969b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson if (isSmall() && RHS.isSmall()) 20069b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson assert(CurArraySize == RHS.CurArraySize && 20169b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson "Cannot assign sets with different small sizes"); 202b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson 20369b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // If we're becoming small, prepare to insert into our stack space 20471a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson if (RHS.isSmall()) { 20571a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson if (!isSmall()) 20671a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson free(CurArray); 2072a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands CurArray = SmallArray; 20869b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Otherwise, allocate new heap space (unless we were the same size) 20971a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson } else if (CurArraySize != RHS.CurArraySize) { 210b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson if (isSmall()) 211e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); 212b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson else 213e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); 2141629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 2151629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson } 216da8ebc6b43cbc587bb072c7fbd9b6fed4baa7644Owen Anderson 21769b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Copy over the new array size 21869b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson CurArraySize = RHS.CurArraySize; 21969b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson 22069b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Copy over the contents from the other set 22169b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); 222b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson 223b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson NumElements = RHS.NumElements; 224b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson NumTombstones = RHS.NumTombstones; 22591f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner} 226845b31de0c58e1f667063170191262079d311052Reid Spencer 2272945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramervoid SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) { 2282945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (this == &RHS) return; 2292945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2302945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // We can only avoid copying elements if neither set is small. 2312945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (!this->isSmall() && !RHS.isSmall()) { 2322945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArray, RHS.CurArray); 2332945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArraySize, RHS.CurArraySize); 2342945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumElements, RHS.NumElements); 2352945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumTombstones, RHS.NumTombstones); 2362945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2372945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2382945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2392945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // FIXME: From here on we assume that both sets have the same small size. 2402945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2412945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // If only RHS is small, copy the small elements into LHS and move the pointer 2422945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // from LHS to RHS. 2432945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (!this->isSmall() && RHS.isSmall()) { 2442945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::copy(RHS.SmallArray, RHS.SmallArray+RHS.NumElements, this->SmallArray); 2452945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumElements, RHS.NumElements); 2462945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArraySize, RHS.CurArraySize); 2472945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.CurArray = this->CurArray; 2482945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.NumTombstones = this->NumTombstones; 2492945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->CurArray = this->SmallArray; 2502945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->NumTombstones = 0; 2512945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2522945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2532945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2542945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // If only LHS is small, copy the small elements into RHS and move the pointer 2552945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // from RHS to LHS. 2562945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (this->isSmall() && !RHS.isSmall()) { 2572945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::copy(this->SmallArray, this->SmallArray+this->NumElements, 2582945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.SmallArray); 2592945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(RHS.NumElements, this->NumElements); 2602945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(RHS.CurArraySize, this->CurArraySize); 2612945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->CurArray = RHS.CurArray; 2622945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->NumTombstones = RHS.NumTombstones; 2632945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.CurArray = RHS.SmallArray; 2642945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.NumTombstones = 0; 2652945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2662945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2672945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2682945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // Both a small, just swap the small elements. 2692945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer assert(this->isSmall() && RHS.isSmall()); 2702945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer assert(this->CurArraySize == RHS.CurArraySize); 2712945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer unsigned MaxElems = std::max(this->NumElements, RHS.NumElements); 2722945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap_ranges(this->SmallArray, this->SmallArray+MaxElems, RHS.SmallArray); 2732945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumElements, RHS.NumElements); 2742945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer} 2752945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 276845b31de0c58e1f667063170191262079d311052Reid SpencerSmallPtrSetImpl::~SmallPtrSetImpl() { 277845b31de0c58e1f667063170191262079d311052Reid Spencer if (!isSmall()) 278845b31de0c58e1f667063170191262079d311052Reid Spencer free(CurArray); 279845b31de0c58e1f667063170191262079d311052Reid Spencer} 280