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 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SmallPtrSetImplBase::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. 28de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Size = size(); 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32; 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumNonEmpty = NumTombstones = 0; 3142e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 3242e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // Install the new array. Clear all the buckets to empty. 33e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); 3442e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner assert(CurArray && "Failed to allocate memory?"); 3542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner memset(CurArray, -1, CurArraySize*sizeof(void*)); 3642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner} 3742e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner 3837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstd::pair<const void *const *, bool> 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSmallPtrSetImplBase::insert_imp_big(const void *Ptr) { 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) { 41e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // If more than 3/4 of the array is full, grow. 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Grow(CurArraySize < 64 ? 128 : CurArraySize * 2); 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) { 44e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // If fewer of 1/8 of the array is empty (meaning that many are filled with 45e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen // tombstones), rehash. 46e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen Grow(CurArraySize); 47e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0bJakob Stoklund Olesen } 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 49c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Okay, we know we have space. Find a hash bucket. 50430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr)); 5137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (*Bucket == Ptr) 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return std::make_pair(Bucket, false); // Already inserted, good. 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 54c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Otherwise, insert it! 55e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner if (*Bucket == getTombstoneMarker()) 56e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner --NumTombstones; 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumNonEmpty; // Track density. 59430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman *Bucket = Ptr; 6037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return std::make_pair(Bucket, true); 61c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 62c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool SmallPtrSetImplBase::erase_imp(const void * Ptr) { 640b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (isSmall()) { 650b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Check to see if it is in the set. 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const void **APtr = CurArray, **E = CurArray + NumNonEmpty; APtr != E; 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++APtr) 680b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (*APtr == Ptr) { 6961766cae0b635f6a65d4491aa063c5fc12745566Chris Lattner // If it is in the set, replace this element. 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar *APtr = getTombstoneMarker(); 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumTombstones; 727ef856dfad10615cac37eb0eb7932cd1fbdcf9e8Chris Lattner return true; 730b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner } 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 750b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner return false; 760b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner } 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 780b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Okay, we know we have space. Find a hash bucket. 790b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner void **Bucket = const_cast<void**>(FindBucketFor(Ptr)); 800b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner if (*Bucket != Ptr) return false; // Not in the set? 810b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 820b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner // Set this as a tombstone. 830b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner *Bucket = getTombstoneMarker(); 84e237cf934fcb8a25746e068f543fbd6db44eaa70Chris Lattner ++NumTombstones; 850b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner return true; 860b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner} 870b930852cf1a9899ae82dd6c31b43e754a77dcb0Chris Lattner 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesconst void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const { 894bb87cbac50098acc6816390c00fad419d3434fcBenjamin Kramer unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1); 90c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned ArraySize = CurArraySize; 91c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner unsigned ProbeAmt = 1; 92e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void *const *Array = CurArray; 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const void *const *Tombstone = nullptr; 94c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner while (1) { 95c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // If we found an empty bucket, the pointer doesn't exist in the set. 96c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Return a tombstone if we've seen one so far, or the empty bucket if 97c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // not. 98ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker())) 99c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner return Tombstone ? Tombstone : Array+Bucket; 100ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 101ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Found Ptr's bucket? 102ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LLVM_LIKELY(Array[Bucket] == Ptr)) 103ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Array+Bucket; 104ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 105c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // If this is a tombstone, remember it. If Ptr ends up not in the set, we 106c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // prefer to return it than something that would require more probing. 107c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner if (Array[Bucket] == getTombstoneMarker() && !Tombstone) 108c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner Tombstone = Array+Bucket; // Remember the first tombstone found. 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 110c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // It's a hash collision or a tombstone. Reprobe. 111c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner Bucket = (Bucket + ProbeAmt++) & (ArraySize-1); 112c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 113c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 114c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner 115c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner/// Grow - Allocate a larger backing store for the buckets and move it over. 116c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner/// 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SmallPtrSetImplBase::Grow(unsigned NewSize) { 118e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson const void **OldBuckets = CurArray; 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const void **OldEnd = EndPointer(); 120c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner bool WasSmall = isSmall(); 121de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 122c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner // Install the new array. Clear all the buckets to empty. 123e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * NewSize); 1241629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 125c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner CurArraySize = NewSize; 126c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner memset(CurArray, -1, NewSize*sizeof(void*)); 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Copy over all valid entries. 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) { 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Copy over the element if it is valid. 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const void *Elt = *BucketPtr; 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) 133e992a56ae93140171f5044079e8d317f784c8cc1Owen Anderson *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt); 134ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen } 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!WasSmall) 137de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar free(OldBuckets); 138de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumNonEmpty -= NumTombstones; 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumTombstones = 0; 140ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen} 141ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesSmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, 143de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SmallPtrSetImplBase &that) { 1442a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands SmallArray = SmallStorage; 1452a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands 146bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // If we're becoming small, prepare to insert into our stack space 147ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen if (that.isSmall()) { 1482a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands CurArray = SmallArray; 149bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson // Otherwise, allocate new heap space (unless we were the same size) 150ac58a16f8584f38198cc7800bd37a896125268b7Jeff Cohen } else { 151e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); 1521629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 153c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner } 154bf31b85ea2a3bf17f3934b7e139b7475a84429faOwen Anderson 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Copy over the that array. 156de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CopyHelper(that); 157c95dc987e9e369c1c63819dbc4f76ab9b913772cChris Lattner} 15891f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesSmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned SmallSize, 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallPtrSetImplBase &&that) { 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallArray = SmallStorage; 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MoveHelper(SmallSize, std::move(that)); 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) { 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(&RHS != this && "Self-copy should be handled by the caller."); 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16969b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson if (isSmall() && RHS.isSmall()) 17069b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson assert(CurArraySize == RHS.CurArraySize && 17169b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson "Cannot assign sets with different small sizes"); 172e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat 17369b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // If we're becoming small, prepare to insert into our stack space 17471a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson if (RHS.isSmall()) { 17571a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson if (!isSmall()) 17671a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson free(CurArray); 1772a8bf425bd0aff1a6406805c095d99089a1dfaaeDuncan Sands CurArray = SmallArray; 17869b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Otherwise, allocate new heap space (unless we were the same size) 17971a1e57d1887341dc3093c12c464f1bc839e7ab5Owen Anderson } else if (CurArraySize != RHS.CurArraySize) { 180b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson if (isSmall()) 181e1e9366281a98cd06b61d5d7e136ce2b1a433ba6Jean-Luc Duprat CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); 182eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman else { 183eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman const void **T = (const void**)realloc(CurArray, 184eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman sizeof(void*) * RHS.CurArraySize); 185eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman if (!T) 186eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman free(CurArray); 187eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman CurArray = T; 188eae6e546ec5339179b4c7401416fbf2d641a9e90Aaron Ballman } 1891629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson assert(CurArray && "Failed to allocate memory?"); 1901629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4fOwen Anderson } 191de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 192de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CopyHelper(RHS); 193de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 194de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 195de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) { 19669b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Copy over the new array size 19769b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson CurArraySize = RHS.CurArraySize; 19869b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson 19969b5d12676cfc57a3f8ba868f4f7ef5211749720Owen Anderson // Copy over the contents from the other set 200de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::copy(RHS.CurArray, RHS.EndPointer(), CurArray); 201de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 202de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumNonEmpty = RHS.NumNonEmpty; 203b54b315251848ddab87ef9f2aa9aac92e3c68357Owen Anderson NumTombstones = RHS.NumTombstones; 20491f0158d4d1b16b8615126b05582d421cfb14089Chris Lattner} 205845b31de0c58e1f667063170191262079d311052Reid Spencer 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SmallPtrSetImplBase::MoveFrom(unsigned SmallSize, 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallPtrSetImplBase &&RHS) { 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!isSmall()) 20936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines free(CurArray); 210de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MoveHelper(SmallSize, std::move(RHS)); 211de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 212de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 213de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid SmallPtrSetImplBase::MoveHelper(unsigned SmallSize, 214de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSetImplBase &&RHS) { 215de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(&RHS != this && "Self-move should be handled by the caller."); 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RHS.isSmall()) { 21836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Copy a small RHS rather than moving. 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CurArray = SmallArray; 220de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray); 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CurArray = RHS.CurArray; 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RHS.CurArray = RHS.SmallArray; 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Copy the rest of the trivial members. 22736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CurArraySize = RHS.CurArraySize; 228de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumNonEmpty = RHS.NumNonEmpty; 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NumTombstones = RHS.NumTombstones; 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Make the RHS small and empty. 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RHS.CurArraySize = SmallSize; 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(RHS.CurArray == RHS.SmallArray); 234de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RHS.NumNonEmpty = 0; 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RHS.NumTombstones = 0; 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) { 2392945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (this == &RHS) return; 2402945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2412945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // We can only avoid copying elements if neither set is small. 2422945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (!this->isSmall() && !RHS.isSmall()) { 2432945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArray, RHS.CurArray); 2442945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->CurArraySize, RHS.CurArraySize); 245de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(this->NumNonEmpty, RHS.NumNonEmpty); 2462945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(this->NumTombstones, RHS.NumTombstones); 2472945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2482945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2492945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2502945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // FIXME: From here on we assume that both sets have the same small size. 2512945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2522945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // If only RHS is small, copy the small elements into LHS and move the pointer 2532945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // from LHS to RHS. 2542945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (!this->isSmall() && RHS.isSmall()) { 255de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(RHS.CurArray == RHS.SmallArray); 256de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray); 257de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(RHS.CurArraySize, this->CurArraySize); 258de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(this->NumNonEmpty, RHS.NumNonEmpty); 259de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(this->NumTombstones, RHS.NumTombstones); 2602945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.CurArray = this->CurArray; 2612945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->CurArray = this->SmallArray; 2622945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2632945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2642945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2652945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // If only LHS is small, copy the small elements into RHS and move the pointer 2662945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // from RHS to LHS. 2672945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer if (this->isSmall() && !RHS.isSmall()) { 268de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(this->CurArray == this->SmallArray); 269de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::copy(this->CurArray, this->CurArray + this->NumNonEmpty, 270f03e62a8008a8ad279a6ed157fb507095177d17aBenjamin Kramer RHS.SmallArray); 2712945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer std::swap(RHS.CurArraySize, this->CurArraySize); 272de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(RHS.NumNonEmpty, this->NumNonEmpty); 273de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(RHS.NumTombstones, this->NumTombstones); 2742945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer this->CurArray = RHS.CurArray; 2752945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer RHS.CurArray = RHS.SmallArray; 2762945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer return; 2772945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer } 2782945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer 2792945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer // Both a small, just swap the small elements. 2802945a32ffd0bf079de1b23db12bc8a0de596a167Benjamin Kramer assert(this->isSmall() && RHS.isSmall()); 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty); 282de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty, 28324e0e7c11fef4dd05fa72faf53846a323eb16bb5Benjamin Kramer RHS.SmallArray); 284de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (this->NumNonEmpty > MinNonEmpty) { 285de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::copy(this->SmallArray + MinNonEmpty, 286de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar this->SmallArray + this->NumNonEmpty, 287de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RHS.SmallArray + MinNonEmpty); 288de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 289de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty, 290de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar this->SmallArray + MinNonEmpty); 291de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 292de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(this->CurArraySize == RHS.CurArraySize); 293de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(this->NumNonEmpty, RHS.NumNonEmpty); 294de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::swap(this->NumTombstones, RHS.NumTombstones); 295845b31de0c58e1f667063170191262079d311052Reid Spencer} 296