1 | //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | // |

7 | //===----------------------------------------------------------------------===// |

8 | // |

9 | // This file defines the SmallPtrSet class. See the doxygen comment for |

10 | // SmallPtrSetImplBase for more details on the algorithm used. |

11 | // |

12 | //===----------------------------------------------------------------------===// |

13 | |

14 | #ifndef LLVM_ADT_SMALLPTRSET_H |

15 | #define LLVM_ADT_SMALLPTRSET_H |

16 | |

17 | #include "llvm/ADT/EpochTracker.h" |

18 | #include "llvm/Support/Compiler.h" |

19 | #include "llvm/Support/ReverseIteration.h" |

20 | #include "llvm/Support/type_traits.h" |

21 | #include <cassert> |

22 | #include <cstddef> |

23 | #include <cstdlib> |

24 | #include <cstring> |

25 | #include <initializer_list> |

26 | #include <iterator> |

27 | #include <utility> |

28 | |

29 | namespace llvm { |

30 | |

31 | /// SmallPtrSetImplBase - This is the common code shared among all the |

32 | /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one |

33 | /// for small and one for large sets. |

34 | /// |

35 | /// Small sets use an array of pointers allocated in the SmallPtrSet object, |

36 | /// which is treated as a simple array of pointers. When a pointer is added to |

37 | /// the set, the array is scanned to see if the element already exists, if not |

38 | /// the element is 'pushed back' onto the array. If we run out of space in the |

39 | /// array, we grow into the 'large set' case. SmallSet should be used when the |

40 | /// sets are often small. In this case, no memory allocation is used, and only |

41 | /// light-weight and cache-efficient scanning is used. |

42 | /// |

43 | /// Large sets use a classic exponentially-probed hash table. Empty buckets are |

44 | /// represented with an illegal pointer value (-1) to allow null pointers to be |

45 | /// inserted. Tombstones are represented with another illegal pointer value |

46 | /// (-2), to allow deletion. The hash table is resized when the table is 3/4 or |

47 | /// more. When this happens, the table is doubled in size. |

48 | /// |

49 | class SmallPtrSetImplBase : public DebugEpochBase { |

50 | friend class SmallPtrSetIteratorImpl; |

51 | |

52 | protected: |

53 | /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. |

54 | const void **SmallArray; |

55 | /// CurArray - This is the current set of buckets. If equal to SmallArray, |

56 | /// then the set is in 'small mode'. |

57 | const void **CurArray; |

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

59 | unsigned CurArraySize; |

60 | |

61 | /// Number of elements in CurArray that contain a value or are a tombstone. |

62 | /// If small, all these elements are at the beginning of CurArray and the rest |

63 | /// is uninitialized. |

64 | unsigned NumNonEmpty; |

65 | /// Number of tombstones in CurArray. |

66 | unsigned NumTombstones; |

67 | |

68 | // Helpers to copy and move construct a SmallPtrSet. |

69 | SmallPtrSetImplBase(const void **SmallStorage, |

70 | const SmallPtrSetImplBase &that); |

71 | SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, |

72 | SmallPtrSetImplBase &&that); |

73 | |

74 | explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) |

75 | : SmallArray(SmallStorage), CurArray(SmallStorage), |

76 | CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) { |

77 | assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && |

78 | "Initial size must be a power of two!"); |

79 | } |

80 | |

81 | ~SmallPtrSetImplBase() { |

82 | if (!isSmall()) |

83 | free(CurArray); |

84 | } |

85 | |

86 | public: |

87 | using size_type = unsigned; |

88 | |

89 | SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete; |

90 | |

91 | LLVM_NODISCARD bool empty() const { return size() == 0; } |

92 | size_type size() const { return NumNonEmpty - NumTombstones; } |

93 | |

94 | void clear() { |

95 | incrementEpoch(); |

96 | // If the capacity of the array is huge, and the # elements used is small, |

97 | // shrink the array. |

98 | if (!isSmall()) { |

99 | if (size() * 4 < CurArraySize && CurArraySize > 32) |

100 | return shrink_and_clear(); |

101 | // Fill the array with empty markers. |

102 | memset(CurArray, -1, CurArraySize * sizeof(void *)); |

103 | } |

104 | |

105 | NumNonEmpty = 0; |

106 | NumTombstones = 0; |

107 | } |

108 | |

109 | protected: |

110 | static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); } |

111 | |

112 | static void *getEmptyMarker() { |

113 | // Note that -1 is chosen to make clear() efficiently implementable with |

114 | // memset and because it's not a valid pointer value. |

115 | return reinterpret_cast<void*>(-1); |

116 | } |

117 | |

118 | const void **EndPointer() const { |

119 | return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize; |

120 | } |

121 | |

122 | /// insert_imp - This returns true if the pointer was new to the set, false if |

123 | /// it was already in the set. This is hidden from the client so that the |

124 | /// derived class can check that the right type of pointer is passed in. |

125 | std::pair<const void *const *, bool> insert_imp(const void *Ptr) { |

126 | if (isSmall()) { |

127 | // Check to see if it is already in the set. |

128 | const void **LastTombstone = nullptr; |

129 | for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty; |

130 | APtr != E; ++APtr) { |

131 | const void *Value = *APtr; |

132 | if (Value == Ptr) |

133 | return std::make_pair(APtr, false); |

134 | if (Value == getTombstoneMarker()) |

135 | LastTombstone = APtr; |

136 | } |

137 | |

138 | // Did we find any tombstone marker? |

139 | if (LastTombstone != nullptr) { |

140 | *LastTombstone = Ptr; |

141 | --NumTombstones; |

142 | incrementEpoch(); |

143 | return std::make_pair(LastTombstone, true); |

144 | } |

145 | |

146 | // Nope, there isn't. If we stay small, just 'pushback' now. |

147 | if (NumNonEmpty < CurArraySize) { |

148 | SmallArray[NumNonEmpty++] = Ptr; |

149 | incrementEpoch(); |

150 | return std::make_pair(SmallArray + (NumNonEmpty - 1), true); |

151 | } |

152 | // Otherwise, hit the big set case, which will call grow. |

153 | } |

154 | return insert_imp_big(Ptr); |

155 | } |

156 | |

157 | /// erase_imp - If the set contains the specified pointer, remove it and |

158 | /// return true, otherwise return false. This is hidden from the client so |

159 | /// that the derived class can check that the right type of pointer is passed |

160 | /// in. |

161 | bool erase_imp(const void * Ptr) { |

162 | const void *const *P = find_imp(Ptr); |

163 | if (P == EndPointer()) |

164 | return false; |

165 | |

166 | const void **Loc = const_cast<const void **>(P); |

167 | assert(*Loc == Ptr && "broken find!"); |

168 | *Loc = getTombstoneMarker(); |

169 | NumTombstones++; |

170 | return true; |

171 | } |

172 | |

173 | /// Returns the raw pointer needed to construct an iterator. If element not |

174 | /// found, this will be EndPointer. Otherwise, it will be a pointer to the |

175 | /// slot which stores Ptr; |

176 | const void *const * find_imp(const void * Ptr) const { |

177 | if (isSmall()) { |

178 | // Linear search for the item. |

179 | for (const void *const *APtr = SmallArray, |

180 | *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr) |

181 | if (*APtr == Ptr) |

182 | return APtr; |

183 | return EndPointer(); |

184 | } |

185 | |

186 | // Big set case. |

187 | auto *Bucket = FindBucketFor(Ptr); |

188 | if (*Bucket == Ptr) |

189 | return Bucket; |

190 | return EndPointer(); |

191 | } |

192 | |

193 | private: |

194 | bool isSmall() const { return CurArray == SmallArray; } |

195 | |

196 | std::pair<const void *const *, bool> insert_imp_big(const void *Ptr); |

197 | |

198 | const void * const *FindBucketFor(const void *Ptr) const; |

199 | void shrink_and_clear(); |

200 | |

201 | /// Grow - Allocate a larger backing store for the buckets and move it over. |

202 | void Grow(unsigned NewSize); |

203 | |

204 | protected: |

205 | /// swap - Swaps the elements of two sets. |

206 | /// Note: This method assumes that both sets have the same small size. |

207 | void swap(SmallPtrSetImplBase &RHS); |

208 | |

209 | void CopyFrom(const SmallPtrSetImplBase &RHS); |

210 | void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); |

211 | |

212 | private: |

213 | /// Code shared by MoveFrom() and move constructor. |

214 | void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS); |

215 | /// Code shared by CopyFrom() and copy constructor. |

216 | void CopyHelper(const SmallPtrSetImplBase &RHS); |

217 | }; |

218 | |

219 | /// SmallPtrSetIteratorImpl - This is the common base class shared between all |

220 | /// instances of SmallPtrSetIterator. |

221 | class SmallPtrSetIteratorImpl { |

222 | protected: |

223 | const void *const *Bucket; |

224 | const void *const *End; |

225 | |

226 | public: |

227 | explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) |

228 | : Bucket(BP), End(E) { |

229 | if (shouldReverseIterate()) { |

230 | RetreatIfNotValid(); |

231 | return; |

232 | } |

233 | AdvanceIfNotValid(); |

234 | } |

235 | |

236 | bool operator==(const SmallPtrSetIteratorImpl &RHS) const { |

237 | return Bucket == RHS.Bucket; |

238 | } |

239 | bool operator!=(const SmallPtrSetIteratorImpl &RHS) const { |

240 | return Bucket != RHS.Bucket; |

241 | } |

242 | |

243 | protected: |

244 | /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket |

245 | /// that is. This is guaranteed to stop because the end() bucket is marked |

246 | /// valid. |

247 | void AdvanceIfNotValid() { |

248 | assert(Bucket <= End); |

249 | while (Bucket != End && |

250 | (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || |

251 | *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) |

252 | ++Bucket; |

253 | } |

254 | void RetreatIfNotValid() { |

255 | assert(Bucket >= End); |

256 | while (Bucket != End && |

257 | (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() || |

258 | Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) { |

259 | --Bucket; |

260 | } |

261 | } |

262 | }; |

263 | |

264 | /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. |

265 | template <typename PtrTy> |

266 | class SmallPtrSetIterator : public SmallPtrSetIteratorImpl, |

267 | DebugEpochBase::HandleBase { |

268 | using PtrTraits = PointerLikeTypeTraits<PtrTy>; |

269 | |

270 | public: |

271 | using value_type = PtrTy; |

272 | using reference = PtrTy; |

273 | using pointer = PtrTy; |

274 | using difference_type = std::ptrdiff_t; |

275 | using iterator_category = std::forward_iterator_tag; |

276 | |

277 | explicit SmallPtrSetIterator(const void *const *BP, const void *const *E, |

278 | const DebugEpochBase &Epoch) |

279 | : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {} |

280 | |

281 | // Most methods are provided by the base class. |

282 | |

283 | const PtrTy operator*() const { |

284 | assert(isHandleInSync() && "invalid iterator access!"); |

285 | if (shouldReverseIterate()) { |

286 | assert(Bucket > End); |

287 | return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1])); |

288 | } |

289 | assert(Bucket < End); |

290 | return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); |

291 | } |

292 | |

293 | inline SmallPtrSetIterator& operator++() { // Preincrement |

294 | assert(isHandleInSync() && "invalid iterator access!"); |

295 | if (shouldReverseIterate()) { |

296 | --Bucket; |

297 | RetreatIfNotValid(); |

298 | return *this; |

299 | } |

300 | ++Bucket; |

301 | AdvanceIfNotValid(); |

302 | return *this; |

303 | } |

304 | |

305 | SmallPtrSetIterator operator++(int) { // Postincrement |

306 | SmallPtrSetIterator tmp = *this; |

307 | ++*this; |

308 | return tmp; |

309 | } |

310 | }; |

311 | |

312 | /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next |

313 | /// power of two (which means N itself if N is already a power of two). |

314 | template<unsigned N> |

315 | struct RoundUpToPowerOfTwo; |

316 | |

317 | /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a |

318 | /// helper template used to implement RoundUpToPowerOfTwo. |

319 | template<unsigned N, bool isPowerTwo> |

320 | struct RoundUpToPowerOfTwoH { |

321 | enum { Val = N }; |

322 | }; |

323 | template<unsigned N> |

324 | struct RoundUpToPowerOfTwoH<N, false> { |

325 | enum { |

326 | // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets |

327 | // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111. |

328 | Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val |

329 | }; |

330 | }; |

331 | |

332 | template<unsigned N> |

333 | struct RoundUpToPowerOfTwo { |

334 | enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val }; |

335 | }; |

336 | |

337 | /// A templated base class for \c SmallPtrSet which provides the |

338 | /// typesafe interface that is common across all small sizes. |

339 | /// |

340 | /// This is particularly useful for passing around between interface boundaries |

341 | /// to avoid encoding a particular small size in the interface boundary. |

342 | template <typename PtrType> |

343 | class SmallPtrSetImpl : public SmallPtrSetImplBase { |

344 | using ConstPtrType = typename add_const_past_pointer<PtrType>::type; |

345 | using PtrTraits = PointerLikeTypeTraits<PtrType>; |

346 | using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>; |

347 | |

348 | protected: |

349 | // Forward constructors to the base. |

350 | using SmallPtrSetImplBase::SmallPtrSetImplBase; |

351 | |

352 | public: |

353 | using iterator = SmallPtrSetIterator<PtrType>; |

354 | using const_iterator = SmallPtrSetIterator<PtrType>; |

355 | using key_type = ConstPtrType; |

356 | using value_type = PtrType; |

357 | |

358 | SmallPtrSetImpl(const SmallPtrSetImpl &) = delete; |

359 | |

360 | /// Inserts Ptr if and only if there is no element in the container equal to |

361 | /// Ptr. The bool component of the returned pair is true if and only if the |

362 | /// insertion takes place, and the iterator component of the pair points to |

363 | /// the element equal to Ptr. |

364 | std::pair<iterator, bool> insert(PtrType Ptr) { |

365 | auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); |

366 | return std::make_pair(makeIterator(p.first), p.second); |

367 | } |

368 | |

369 | /// Insert the given pointer with an iterator hint that is ignored. This is |

370 | /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by |

371 | /// std::insert_iterator and std::inserter(). |

372 | iterator insert(iterator, PtrType Ptr) { |

373 | return insert(Ptr).first; |

374 | } |

375 | |

376 | /// erase - If the set contains the specified pointer, remove it and return |

377 | /// true, otherwise return false. |

378 | bool erase(PtrType Ptr) { |

379 | return erase_imp(PtrTraits::getAsVoidPointer(Ptr)); |

380 | } |

381 | /// count - Return 1 if the specified pointer is in the set, 0 otherwise. |

382 | size_type count(ConstPtrType Ptr) const { |

383 | return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer(); |

384 | } |

385 | iterator find(ConstPtrType Ptr) const { |

386 | return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr))); |

387 | } |

388 | bool contains(ConstPtrType Ptr) const { |

389 | return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer(); |

390 | } |

391 | |

392 | template <typename IterT> |

393 | void insert(IterT I, IterT E) { |

394 | for (; I != E; ++I) |

395 | insert(*I); |

396 | } |

397 | |

398 | void insert(std::initializer_list<PtrType> IL) { |

399 | insert(IL.begin(), IL.end()); |

400 | } |

401 | |

402 | iterator begin() const { |

403 | if (shouldReverseIterate()) |

404 | return makeIterator(EndPointer() - 1); |

405 | return makeIterator(CurArray); |

406 | } |

407 | iterator end() const { return makeIterator(EndPointer()); } |

408 | |

409 | private: |

410 | /// Create an iterator that dereferences to same place as the given pointer. |

411 | iterator makeIterator(const void *const *P) const { |

412 | if (shouldReverseIterate()) |

413 | return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this); |

414 | return iterator(P, EndPointer(), *this); |

415 | } |

416 | }; |

417 | |

418 | /// Equality comparison for SmallPtrSet. |

419 | /// |

420 | /// Iterates over elements of LHS confirming that each value from LHS is also in |

421 | /// RHS, and that no additional values are in RHS. |

422 | template <typename PtrType> |

423 | bool operator==(const SmallPtrSetImpl<PtrType> &LHS, |

424 | const SmallPtrSetImpl<PtrType> &RHS) { |

425 | if (LHS.size() != RHS.size()) |

426 | return false; |

427 | |

428 | for (const auto *KV : LHS) |

429 | if (!RHS.count(KV)) |

430 | return false; |

431 | |

432 | return true; |

433 | } |

434 | |

435 | /// Inequality comparison for SmallPtrSet. |

436 | /// |

437 | /// Equivalent to !(LHS == RHS). |

438 | template <typename PtrType> |

439 | bool operator!=(const SmallPtrSetImpl<PtrType> &LHS, |

440 | const SmallPtrSetImpl<PtrType> &RHS) { |

441 | return !(LHS == RHS); |

442 | } |

443 | |

444 | /// SmallPtrSet - This class implements a set which is optimized for holding |

445 | /// SmallSize or less elements. This internally rounds up SmallSize to the next |

446 | /// power of two if it is not already a power of two. See the comments above |

447 | /// SmallPtrSetImplBase for details of the algorithm. |

448 | template<class PtrType, unsigned SmallSize> |

449 | class SmallPtrSet : public SmallPtrSetImpl<PtrType> { |

450 | // In small mode SmallPtrSet uses linear search for the elements, so it is |

451 | // not a good idea to choose this value too high. You may consider using a |

452 | // DenseSet<> instead if you expect many elements in the set. |

453 | static_assert(SmallSize <= 32, "SmallSize should be small"); |

454 | |

455 | using BaseT = SmallPtrSetImpl<PtrType>; |

456 | |

457 | // Make sure that SmallSize is a power of two, round up if not. |

458 | enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val }; |

459 | /// SmallStorage - Fixed size storage used in 'small mode'. |

460 | const void *SmallStorage[SmallSizePowTwo]; |

461 | |

462 | public: |

463 | SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} |

464 | SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {} |

465 | SmallPtrSet(SmallPtrSet &&that) |

466 | : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {} |

467 | |

468 | template<typename It> |

469 | SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) { |

470 | this->insert(I, E); |

471 | } |

472 | |

473 | SmallPtrSet(std::initializer_list<PtrType> IL) |

474 | : BaseT(SmallStorage, SmallSizePowTwo) { |

475 | this->insert(IL.begin(), IL.end()); |

476 | } |

477 | |

478 | SmallPtrSet<PtrType, SmallSize> & |

479 | operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) { |

480 | if (&RHS != this) |

481 | this->CopyFrom(RHS); |

482 | return *this; |

483 | } |

484 | |

485 | SmallPtrSet<PtrType, SmallSize> & |

486 | operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) { |

487 | if (&RHS != this) |

488 | this->MoveFrom(SmallSizePowTwo, std::move(RHS)); |

489 | return *this; |

490 | } |

491 | |

492 | SmallPtrSet<PtrType, SmallSize> & |

493 | operator=(std::initializer_list<PtrType> IL) { |

494 | this->clear(); |

495 | this->insert(IL.begin(), IL.end()); |

496 | return *this; |

497 | } |

498 | |

499 | /// swap - Swaps the elements of two sets. |

500 | void swap(SmallPtrSet<PtrType, SmallSize> &RHS) { |

501 | SmallPtrSetImplBase::swap(RHS); |

502 | } |

503 | }; |

504 | |

505 | } // end namespace llvm |

506 | |

507 | namespace std { |

508 | |

509 | /// Implement std::swap in terms of SmallPtrSet swap. |

510 | template<class T, unsigned N> |

511 | inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { |

512 | LHS.swap(RHS); |

513 | } |

514 | |

515 | } // end namespace std |

516 | |

517 | #endif // LLVM_ADT_SMALLPTRSET_H |

518 |