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" 164bb87cbac50098acc6816390c00fad419d3434fcBenjamin Kramer#include "llvm/ADT/DenseMapInfo.h" 1791f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner#include "llvm/Support/MathExtras.h" 182945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer#include <algorithm> 19845b31de0c58e1f667063170191262079d311052Reid Spencer#include <cstdlib> 20845b31de0c58e1f667063170191262079d311052Reid Spencer 21c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattnerusing namespace llvm; 22c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 2342e4bdf2577946380ce1529d5716e48b33d4186dChris Lattnervoid SmallPtrSetImpl::shrink_and_clear() { 2442e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner assert(!isSmall() && "Can't shrink a small set!"); 2542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner free(CurArray); 2642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 2742e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // Reduce the number of buckets. 2842e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; 2942e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner NumElements = NumTombstones = 0; 3042e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 3142e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // Install the new array. Clear all the buckets to empty. 32e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); 3342e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner assert(CurArray && "Failed to allocate memory?"); 3442e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner memset(CurArray, -1, CurArraySize*sizeof(void*)); 3542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner} 3642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 37373a733be031f52cebbbcdb15ab5997d9b5f9f17Chris Lattnerbool SmallPtrSetImpl::insert_imp(const void * Ptr) { 38c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (isSmall()) { 39c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Check to see if it is already in the set. 40e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 41c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner APtr != E; ++APtr) 42c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (*APtr == Ptr) 43c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return false; 44c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 45c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Nope, there isn't. If we stay small, just 'pushback' now. 46c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (NumElements < CurArraySize-1) { 47c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner SmallArray[NumElements++] = Ptr; 48c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return true; 49c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 50c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Otherwise, hit the big set case, which will call grow. 51c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 52c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 53e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen if (NumElements*4 >= CurArraySize*3) { 54e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // If more than 3/4 of the array is full, grow. 55e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen Grow(CurArraySize < 64 ? 128 : CurArraySize*2); 56e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) { 57e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // If fewer of 1/8 of the array is empty (meaning that many are filled with 58e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // tombstones), rehash. 59e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen Grow(CurArraySize); 60e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen } 61c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 62c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Okay, we know we have space. Find a hash bucket. 63430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 64c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (*Bucket == Ptr) return false; // Already inserted, good. 65c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 66c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Otherwise, insert it! 67e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner if (*Bucket == getTombstoneMarker()) 68e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner --NumTombstones; 69430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman *Bucket = Ptr; 70c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner ++NumElements; // Track density. 71c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return true; 72c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 73c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 74373a733be031f52cebbbcdb15ab5997d9b5f9f17Chris Lattnerbool SmallPtrSetImpl::erase_imp(const void * Ptr) { 750b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (isSmall()) { 760b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Check to see if it is in the set. 77e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **APtr = SmallArray, **E = SmallArray+NumElements; 780b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner APtr != E; ++APtr) 790b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (*APtr == Ptr) { 8061766cae0b635f6a65d4491aa063c5fc12745566Chris Lattner // If it is in the set, replace this element. 8161766cae0b635f6a65d4491aa063c5fc12745566Chris Lattner *APtr = E[-1]; 820b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner E[-1] = getEmptyMarker(); 830b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner --NumElements; 847ef856dfad10615cac37eb0eb7932cd1fbdcf9e8Chris Lattner return true; 850b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner } 860b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 870b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner return false; 880b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner } 890b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 900b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Okay, we know we have space. Find a hash bucket. 910b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 920b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (*Bucket != Ptr) return false; // Not in the set? 930b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 940b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Set this as a tombstone. 950b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner *Bucket = getTombstoneMarker(); 960b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner --NumElements; 97e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner ++NumTombstones; 980b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner return true; 990b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner} 1000b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 101e992a56ae93140171f5044079e8d317f784c8cc1Owen Andersonconst void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { 1024bb87cbac50098acc6816390c00fad419d3434fcBenjamin Kramer unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1); 103c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned ArraySize = CurArraySize; 104c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned ProbeAmt = 1; 105e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *const *Array = CurArray; 106e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *const *Tombstone = 0; 107c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner while (1) { 108c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Found Ptr's bucket? 109c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == Ptr) 110c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return Array+Bucket; 111c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 112c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // If we found an empty bucket, the pointer doesn't exist in the set. 113c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Return a tombstone if we've seen one so far, or the empty bucket if 114c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // not. 115c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == getEmptyMarker()) 116c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return Tombstone ? Tombstone : Array+Bucket; 117c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 118c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // If this is a tombstone, remember it. If Ptr ends up not in the set, we 119c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // prefer to return it than something that would require more probing. 120c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 121c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner Tombstone = Array+Bucket; // Remember the first tombstone found. 122c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 123c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // It's a hash collision or a tombstone. Reprobe. 124c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 125c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 126c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 127c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 128c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner/// Grow - Allocate a larger backing store for the buckets and move it over. 129c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner/// 130e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesenvoid SmallPtrSetImpl::Grow(unsigned NewSize) { 131c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Allocate at twice as many buckets, but at least 128. 132c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned OldSize = CurArraySize; 133c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 134e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void **OldBuckets = CurArray; 135c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner bool WasSmall = isSmall(); 136c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 137c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Install the new array. Clear all the buckets to empty. 138e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * NewSize); 1391629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 140c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner CurArraySize = NewSize; 141c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner memset(CurArray, -1, NewSize*sizeof(void*)); 142c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 143c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Copy over all the elements. 144c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (WasSmall) { 145c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Small sets store their elements in order. 146e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; 147c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner BucketPtr != E; ++BucketPtr) { 148e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *Elt = *BucketPtr; 149e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 150c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 151c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } else { 152c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Copy over all valid entries. 153e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; 154c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner BucketPtr != E; ++BucketPtr) { 155c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Copy over the element if it is valid. 156e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *Elt = *BucketPtr; 157c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 158e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 159c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 160c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 1611629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson free(OldBuckets); 162ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen NumTombstones = 0; 163ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen } 164ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen} 165ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen 1662a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan SandsSmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, 1672a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands const SmallPtrSetImpl& that) { 1682a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands SmallArray = SmallStorage; 1692a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands 170bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // If we're becoming small, prepare to insert into our stack space 171ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen if (that.isSmall()) { 1722a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands CurArray = SmallArray; 173bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Otherwise, allocate new heap space (unless we were the same size) 174ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen } else { 175e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); 1761629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 177c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 178bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 179bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Copy over the new array size 180bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson CurArraySize = that.CurArraySize; 181bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 182bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Copy over the contents from the other set 183e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); 184bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 185bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson NumElements = that.NumElements; 186bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson NumTombstones = that.NumTombstones; 187c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 18891f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner 18991f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner/// CopyFrom - implement operator= from a smallptrset that has the same pointer 19091f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner/// type, but may have a different small size. 19191f0158d4d1b16b8615126b05582d421cfb14089Chris Lattnervoid SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { 19269b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson if (isSmall() && RHS.isSmall()) 19369b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson assert(CurArraySize == RHS.CurArraySize && 19469b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson "Cannot assign sets with different small sizes"); 195e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat 19669b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // If we're becoming small, prepare to insert into our stack space 19771a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson if (RHS.isSmall()) { 19871a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson if (!isSmall()) 19971a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson free(CurArray); 2002a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands CurArray = SmallArray; 20169b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Otherwise, allocate new heap space (unless we were the same size) 20271a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson } else if (CurArraySize != RHS.CurArraySize) { 203b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson if (isSmall()) 204e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); 205b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson else 206e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); 2071629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 2081629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson } 209da8ebc6b43cbc587bb072c7fbd9b6fed4baa7644Owen Anderson 21069b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Copy over the new array size 21169b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson CurArraySize = RHS.CurArraySize; 21269b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson 21369b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Copy over the contents from the other set 214e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); 215b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson 216b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson NumElements = RHS.NumElements; 217b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson NumTombstones = RHS.NumTombstones; 21891f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner} 219845b31de0c58e1f667063170191262079d311052Reid Spencer 2202945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramervoid SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) { 2212945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (this == &RHS) return; 2222945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2232945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // We can only avoid copying elements if neither set is small. 2242945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (!this->isSmall() && !RHS.isSmall()) { 2252945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArray, RHS.CurArray); 2262945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArraySize, RHS.CurArraySize); 2272945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumElements, RHS.NumElements); 2282945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumTombstones, RHS.NumTombstones); 2292945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2302945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2312945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2322945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // FIXME: From here on we assume that both sets have the same small size. 2332945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2342945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // If only RHS is small, copy the small elements into LHS and move the pointer 2352945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // from LHS to RHS. 2362945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (!this->isSmall() && RHS.isSmall()) { 237f03e62a8008a8ad279a6ed157fb507095177d17aBenjamin Kramer std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize, 238f03e62a8008a8ad279a6ed157fb507095177d17aBenjamin Kramer this->SmallArray); 2392945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumElements, RHS.NumElements); 2402945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArraySize, RHS.CurArraySize); 2412945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.CurArray = this->CurArray; 2422945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.NumTombstones = this->NumTombstones; 2432945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->CurArray = this->SmallArray; 2442945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->NumTombstones = 0; 2452945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2462945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2472945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2482945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // If only LHS is small, copy the small elements into RHS and move the pointer 2492945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // from RHS to LHS. 2502945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (this->isSmall() && !RHS.isSmall()) { 251f03e62a8008a8ad279a6ed157fb507095177d17aBenjamin Kramer std::copy(this->SmallArray, this->SmallArray+this->CurArraySize, 252f03e62a8008a8ad279a6ed157fb507095177d17aBenjamin Kramer RHS.SmallArray); 2532945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(RHS.NumElements, this->NumElements); 2542945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(RHS.CurArraySize, this->CurArraySize); 2552945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->CurArray = RHS.CurArray; 2562945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->NumTombstones = RHS.NumTombstones; 2572945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.CurArray = RHS.SmallArray; 2582945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.NumTombstones = 0; 2592945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2602945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2612945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2622945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // Both a small, just swap the small elements. 2632945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer assert(this->isSmall() && RHS.isSmall()); 2642945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer assert(this->CurArraySize == RHS.CurArraySize); 265f03e62a8008a8ad279a6ed157fb507095177d17aBenjamin Kramer std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize, 26624e0e7c11fef4dd05fa72faf53846a323eb16bb5Benjamin Kramer RHS.SmallArray); 2672945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumElements, RHS.NumElements); 2682945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer} 2692945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 270845b31de0c58e1f667063170191262079d311052Reid SpencerSmallPtrSetImpl::~SmallPtrSetImpl() { 271845b31de0c58e1f667063170191262079d311052Reid Spencer if (!isSmall()) 272845b31de0c58e1f667063170191262079d311052Reid Spencer free(CurArray); 273845b31de0c58e1f667063170191262079d311052Reid Spencer} 274