SmallPtrSet.cpp Source File (original) (raw)

19#include

20#include

21#include

23using namespace llvm;

25void SmallPtrSetImplBase::shrink_and_clear() {

26 assert( isSmall () && "Can't shrink a small set!");

38}

40std::pair<const void *const *, bool>

41SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {

50 }

53 const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));

54 if (*Bucket == Ptr)

55 return {Bucket, false};

61 *Bucket = Ptr;

63 return {Bucket, true};

64}

66const void *const *SmallPtrSetImplBase::doFind(const void *Ptr) const {

67 unsigned BucketNo =

68 DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize - 1);

69 unsigned ProbeAmt = 1;

70 while (true) {

71 const void *const *Bucket = CurArray + BucketNo;

73 return Bucket;

75 return nullptr;

79 BucketNo += ProbeAmt++;

81 }

82}

84const void *const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {

87 unsigned ProbeAmt = 1;

88 const void *const *Array = CurArray;

89 const void *const *Tombstone = nullptr;

90 while (true) {

99 return Array+Bucket;

100

101

102

104 Tombstone = Array+Bucket;

105

106

107 Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);

108 }

109}

110

111

112

113void SmallPtrSetImplBase::Grow(unsigned NewSize) {

114 auto OldBuckets = buckets();

115 bool WasSmall = isSmall();

116

117

118 const void **NewBuckets = (const void**) safe_malloc(sizeof(void*) * NewSize);

119

120

123 memset(CurArray, -1, NewSize*sizeof(void*));

124

125

126 for (const void *&Bucket : OldBuckets) {

127

129 *const_cast<void **>(FindBucketFor(Bucket)) = const_cast<void *>(Bucket);

130 }

131

132 if (!WasSmall)

133 free(OldBuckets.begin());

136}

137

142

144 } else {

145

147 }

148

149

150 copyHelper(that);

151}

152

154 unsigned SmallSize,

155 const void **RHSSmallStorage,

157 moveHelper(SmallStorage, SmallSize, RHSSmallStorage, std::move(that));

158}

159

162 assert(&RHS != this && "Self-copy should be handled by the caller.");

163

164 if (isSmall() && RHS.isSmall())

166 "Cannot assign sets with different small sizes");

167

168

169 if (RHS.isSmall()) {

174

175 } else if (CurArraySize != RHS.CurArraySize) {

178 else {

180 sizeof(void*) * RHS.CurArraySize);

182 }

184 }

185

186 copyHelper(RHS);

187}

188

190

192

193

195

198}

199

201 unsigned SmallSize,

202 const void **RHSSmallStorage,

206 moveHelper(SmallStorage, SmallSize, RHSSmallStorage, std::move(RHS));

207}

208

209void SmallPtrSetImplBase::moveHelper(const void **SmallStorage,

210 unsigned SmallSize,

211 const void **RHSSmallStorage,

213 assert(&RHS != this && "Self-move should be handled by the caller.");

214

215 if (RHS.isSmall()) {

216

219 } else {

221 RHS.CurArray = RHSSmallStorage;

222 }

223

224

229

230

231 RHS.CurArraySize = SmallSize;

232 RHS.NumEntries = 0;

233 RHS.NumTombstones = 0;

234 RHS.IsSmall = true;

235}

236

238 const void **RHSSmallStorage,

240 if (this == &RHS) return;

241

242

245 std::swap(this->CurArraySize, RHS.CurArraySize);

248 return;

249 }

250

251

252

253

255 unsigned MinEntries = std::min(this->NumEntries, RHS.NumEntries);

256 std::swap_ranges(this->CurArray, this->CurArray + MinEntries, RHS.CurArray);

259 RHS.CurArray + MinEntries);

260 } else {

261 std::copy(RHS.CurArray + MinEntries, RHS.CurArray + RHS.NumEntries,

262 this->CurArray + MinEntries);

263 }

264 assert(this->CurArraySize == RHS.CurArraySize);

267 return;

268 }

269

270

271

274 const void **LargeSideInlineStorage =

275 this->isSmall() ? RHSSmallStorage : SmallStorage;

281 SmallSide.IsSmall = false;

282 LargeSide.CurArray = LargeSideInlineStorage;

283 LargeSide.IsSmall = true;

284}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

#define LLVM_UNLIKELY(EXPR)

#define LLVM_LIKELY(EXPR)

This file defines DenseMapInfo traits for DenseMap.

This file defines counterparts of C library allocation functions defined in the namespace 'std'.

This file defines the SmallPtrSet class.

LocallyHashedType DenseMapInfo< LocallyHashedType >::Tombstone

SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...

iterator_range< const void ** > buckets()

unsigned NumTombstones

Number of tombstones in CurArray.

LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)

Definition SmallPtrSet.cpp:138

unsigned NumEntries

Number of elements in CurArray that contain a value.

const void ** CurArray

The current set of buckets, in either small or big representation.

bool IsSmall

Whether the set is in small representation.

LLVM_ABI void copyFrom(const void **SmallStorage, const SmallPtrSetImplBase &RHS)

Definition SmallPtrSet.cpp:160

LLVM_ABI void moveFrom(const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS)

Definition SmallPtrSet.cpp:200

iterator_range< const void ** > small_buckets()

unsigned CurArraySize

CurArraySize - The allocated size of CurArray, always a power of two.

static void * getEmptyMarker()

static void * getTombstoneMarker()

LLVM_ABI void swap(const void **SmallStorage, const void **RHSSmallStorage, SmallPtrSetImplBase &RHS)

swap - Swaps the elements of two sets.

Definition SmallPtrSet.cpp:237

This is an optimization pass for GlobalISel generic memory operations.

unsigned Log2_32_Ceil(uint32_t Value)

Return the ceil log base 2 of the specified value, 32 if the value is zero.

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_realloc(void *Ptr, size_t Sz)

OutputIt copy(R &&Range, OutputIt Out)

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

An information struct used to provide DenseMap with the various necessary components for a given valu...