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 /// \file 10 /// This file defines the SmallPtrSet class. See the doxygen comment for 11 /// SmallPtrSetImplBase for more details on the algorithm used. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ADT_SMALLPTRSET_H 16 #define LLVM_ADT_SMALLPTRSET_H 17 18 #include "llvm/ADT/EpochTracker.h" 19 #include "llvm/Support/Compiler.h" 20 #include "llvm/Support/ReverseIteration.h" 21 #include "llvm/Support/type_traits.h" 22 #include <cassert> 23 #include <cstddef> 24 #include <cstdlib> 25 #include <cstring> 26 #include <initializer_list> 27 #include <iterator> 28 #include <utility> 29 30 namespace llvm { 31 32 /// SmallPtrSetImplBase - This is the common code shared among all the 33 /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one 34 /// for small and one for large sets. 35 /// 36 /// Small sets use an array of pointers allocated in the SmallPtrSet object, 37 /// which is treated as a simple array of pointers. When a pointer is added to 38 /// the set, the array is scanned to see if the element already exists, if not 39 /// the element is 'pushed back' onto the array. If we run out of space in the 40 /// array, we grow into the 'large set' case. SmallSet should be used when the 41 /// sets are often small. In this case, no memory allocation is used, and only 42 /// light-weight and cache-efficient scanning is used. 43 /// 44 /// Large sets use a classic exponentially-probed hash table. Empty buckets are 45 /// represented with an illegal pointer value (-1) to allow null pointers to be 46 /// inserted. Tombstones are represented with another illegal pointer value 47 /// (-2), to allow deletion. The hash table is resized when the table is 3/4 or 48 /// more. When this happens, the table is doubled in size. 49 /// 50 class SmallPtrSetImplBase : public DebugEpochBase { 51 friend class SmallPtrSetIteratorImpl; 52 53 protected: 54 /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. 55 const void **SmallArray; 56 /// CurArray - This is the current set of buckets. If equal to SmallArray, 57 /// then the set is in 'small mode'. 58 const void **CurArray; 59 /// CurArraySize - The allocated size of CurArray, always a power of two. 60 unsigned CurArraySize; 61 62 /// Number of elements in CurArray that contain a value or are a tombstone. 63 /// If small, all these elements are at the beginning of CurArray and the rest 64 /// is uninitialized. 65 unsigned NumNonEmpty; 66 /// Number of tombstones in CurArray. 67 unsigned NumTombstones; 68 69 // Helpers to copy and move construct a SmallPtrSet. 70 SmallPtrSetImplBase(const void **SmallStorage, 71 const SmallPtrSetImplBase &that); 72 SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, 73 SmallPtrSetImplBase &&that); 74 75 explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) 76 : SmallArray(SmallStorage), CurArray(SmallStorage), 77 CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) { 78 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && 79 "Initial size must be a power of two!"); 80 } 81 82 ~SmallPtrSetImplBase() { 83 if (!isSmall()) 84 free(CurArray); 85 } 86 87 public: 88 using size_type = unsigned; 89 90 SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete; 91 92 [[nodiscard]] bool empty() const { return size() == 0; } 93 size_type size() const { return NumNonEmpty - NumTombstones; } 94 95 void clear() { 96 incrementEpoch(); 97 // If the capacity of the array is huge, and the # elements used is small, 98 // shrink the array. 99 if (!isSmall()) { 100 if (size() * 4 < CurArraySize && CurArraySize > 32) 101 return shrink_and_clear(); 102 // Fill the array with empty markers. 103 memset(CurArray, -1, CurArraySize * sizeof(void *)); 104 } 105 106 NumNonEmpty = 0; 107 NumTombstones = 0; 108 } 109 110 protected: 111 static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); } 112 113 static void *getEmptyMarker() { 114 // Note that -1 is chosen to make clear() efficiently implementable with 115 // memset and because it's not a valid pointer value. 116 return reinterpret_cast<void*>(-1); 117 } 118 119 const void **EndPointer() const { 120 return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize; 121 } 122 123 /// insert_imp - This returns true if the pointer was new to the set, false if 124 /// it was already in the set. This is hidden from the client so that the 125 /// derived class can check that the right type of pointer is passed in. 126 std::pair<const void *const *, bool> insert_imp(const void *Ptr) { 127 if (isSmall()) { 128 // Check to see if it is already in the set. 129 const void **LastTombstone = nullptr; 130 for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty; 131 APtr != E; ++APtr) { 132 const void *Value = *APtr; 133 if (Value == Ptr) 134 return std::make_pair(APtr, false); 135 if (Value == getTombstoneMarker()) 136 LastTombstone = APtr; 137 } 138 139 // Did we find any tombstone marker? 140 if (LastTombstone != nullptr) { 141 *LastTombstone = Ptr; 142 --NumTombstones; 143 incrementEpoch(); 144 return std::make_pair(LastTombstone, true); 145 } 146 147 // Nope, there isn't. If we stay small, just 'pushback' now. 148 if (NumNonEmpty < CurArraySize) { 149 SmallArray[NumNonEmpty++] = Ptr; 150 incrementEpoch(); 151 return std::make_pair(SmallArray + (NumNonEmpty - 1), true); 152 } 153 // Otherwise, hit the big set case, which will call grow. 154 } 155 return insert_imp_big(Ptr); 156 } 157 158 /// erase_imp - If the set contains the specified pointer, remove it and 159 /// return true, otherwise return false. This is hidden from the client so 160 /// that the derived class can check that the right type of pointer is passed 161 /// in. 162 bool erase_imp(const void * Ptr) { 163 const void *const *P = find_imp(Ptr); 164 if (P == EndPointer()) 165 return false; 166 167 const void **Loc = const_cast<const void **>(P); 168 assert(*Loc == Ptr && "broken find!"); 169 *Loc = getTombstoneMarker(); 170 NumTombstones++; 171 return true; 172 } 173 174 /// Returns the raw pointer needed to construct an iterator. If element not 175 /// found, this will be EndPointer. Otherwise, it will be a pointer to the 176 /// slot which stores Ptr; 177 const void *const * find_imp(const void * Ptr) const { 178 if (isSmall()) { 179 // Linear search for the item. 180 for (const void *const *APtr = SmallArray, 181 *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr) 182 if (*APtr == Ptr) 183 return APtr; 184 return EndPointer(); 185 } 186 187 // Big set case. 188 auto *Bucket = FindBucketFor(Ptr); 189 if (*Bucket == Ptr) 190 return Bucket; 191 return EndPointer(); 192 } 193 194 private: 195 bool isSmall() const { return CurArray == SmallArray; } 196 197 std::pair<const void *const *, bool> insert_imp_big(const void *Ptr); 198 199 const void * const *FindBucketFor(const void *Ptr) const; 200 void shrink_and_clear(); 201 202 /// Grow - Allocate a larger backing store for the buckets and move it over. 203 void Grow(unsigned NewSize); 204 205 protected: 206 /// swap - Swaps the elements of two sets. 207 /// Note: This method assumes that both sets have the same small size. 208 void swap(SmallPtrSetImplBase &RHS); 209 210 void CopyFrom(const SmallPtrSetImplBase &RHS); 211 void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); 212 213 private: 214 /// Code shared by MoveFrom() and move constructor. 215 void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS); 216 /// Code shared by CopyFrom() and copy constructor. 217 void CopyHelper(const SmallPtrSetImplBase &RHS); 218 }; 219 220 /// SmallPtrSetIteratorImpl - This is the common base class shared between all 221 /// instances of SmallPtrSetIterator. 222 class SmallPtrSetIteratorImpl { 223 protected: 224 const void *const *Bucket; 225 const void *const *End; 226 227 public: 228 explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) 229 : Bucket(BP), End(E) { 230 if (shouldReverseIterate()) { 231 RetreatIfNotValid(); 232 return; 233 } 234 AdvanceIfNotValid(); 235 } 236 237 bool operator==(const SmallPtrSetIteratorImpl &RHS) const { 238 return Bucket == RHS.Bucket; 239 } 240 bool operator!=(const SmallPtrSetIteratorImpl &RHS) const { 241 return Bucket != RHS.Bucket; 242 } 243 244 protected: 245 /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket 246 /// that is. This is guaranteed to stop because the end() bucket is marked 247 /// valid. 248 void AdvanceIfNotValid() { 249 assert(Bucket <= End); 250 while (Bucket != End && 251 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || 252 *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) 253 ++Bucket; 254 } 255 void RetreatIfNotValid() { 256 assert(Bucket >= End); 257 while (Bucket != End && 258 (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() || 259 Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) { 260 --Bucket; 261 } 262 } 263 }; 264 265 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. 266 template <typename PtrTy> 267 class LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE SmallPtrSetIterator 268 : public SmallPtrSetIteratorImpl, 269 DebugEpochBase::HandleBase { 270 using PtrTraits = PointerLikeTypeTraits<PtrTy>; 271 272 public: 273 using value_type = PtrTy; 274 using reference = PtrTy; 275 using pointer = PtrTy; 276 using difference_type = std::ptrdiff_t; 277 using iterator_category = std::forward_iterator_tag; 278 279 explicit SmallPtrSetIterator(const void *const *BP, const void *const *E, 280 const DebugEpochBase &Epoch) 281 : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {} 282 283 // Most methods are provided by the base class. 284 285 const PtrTy operator*() const { 286 assert(isHandleInSync() && "invalid iterator access!"); 287 if (shouldReverseIterate()) { 288 assert(Bucket > End); 289 return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1])); 290 } 291 assert(Bucket < End); 292 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); 293 } 294 295 inline SmallPtrSetIterator& operator++() { // Preincrement 296 assert(isHandleInSync() && "invalid iterator access!"); 297 if (shouldReverseIterate()) { 298 --Bucket; 299 RetreatIfNotValid(); 300 return *this; 301 } 302 ++Bucket; 303 AdvanceIfNotValid(); 304 return *this; 305 } 306 307 SmallPtrSetIterator operator++(int) { // Postincrement 308 SmallPtrSetIterator tmp = *this; 309 ++*this; 310 return tmp; 311 } 312 }; 313 314 /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next 315 /// power of two (which means N itself if N is already a power of two). 316 template<unsigned N> 317 struct RoundUpToPowerOfTwo; 318 319 /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a 320 /// helper template used to implement RoundUpToPowerOfTwo. 321 template<unsigned N, bool isPowerTwo> 322 struct RoundUpToPowerOfTwoH { 323 enum { Val = N }; 324 }; 325 template<unsigned N> 326 struct RoundUpToPowerOfTwoH<N, false> { 327 enum { 328 // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets 329 // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111. 330 Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val 331 }; 332 }; 333 334 template<unsigned N> 335 struct RoundUpToPowerOfTwo { 336 enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val }; 337 }; 338 339 /// A templated base class for \c SmallPtrSet which provides the 340 /// typesafe interface that is common across all small sizes. 341 /// 342 /// This is particularly useful for passing around between interface boundaries 343 /// to avoid encoding a particular small size in the interface boundary. 344 template <typename PtrType> 345 class SmallPtrSetImpl : public SmallPtrSetImplBase { 346 using ConstPtrType = typename add_const_past_pointer<PtrType>::type; 347 using PtrTraits = PointerLikeTypeTraits<PtrType>; 348 using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>; 349 350 protected: 351 // Forward constructors to the base. 352 using SmallPtrSetImplBase::SmallPtrSetImplBase; 353 354 public: 355 using iterator = SmallPtrSetIterator<PtrType>; 356 using const_iterator = SmallPtrSetIterator<PtrType>; 357 using key_type = ConstPtrType; 358 using value_type = PtrType; 359 360 SmallPtrSetImpl(const SmallPtrSetImpl &) = delete; 361 362 /// Inserts Ptr if and only if there is no element in the container equal to 363 /// Ptr. The bool component of the returned pair is true if and only if the 364 /// insertion takes place, and the iterator component of the pair points to 365 /// the element equal to Ptr. 366 std::pair<iterator, bool> insert(PtrType Ptr) { 367 auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); 368 return std::make_pair(makeIterator(p.first), p.second); 369 } 370 371 /// Insert the given pointer with an iterator hint that is ignored. This is 372 /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by 373 /// std::insert_iterator and std::inserter(). 374 iterator insert(iterator, PtrType Ptr) { 375 return insert(Ptr).first; 376 } 377 378 /// erase - If the set contains the specified pointer, remove it and return 379 /// true, otherwise return false. 380 bool erase(PtrType Ptr) { 381 return erase_imp(PtrTraits::getAsVoidPointer(Ptr)); 382 } 383 /// count - Return 1 if the specified pointer is in the set, 0 otherwise. 384 size_type count(ConstPtrType Ptr) const { 385 return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer(); 386 } 387 iterator find(ConstPtrType Ptr) const { 388 return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr))); 389 } 390 bool contains(ConstPtrType Ptr) const { 391 return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer(); 392 } 393 394 template <typename IterT> 395 void insert(IterT I, IterT E) { 396 for (; I != E; ++I) 397 insert(*I); 398 } 399 400 void insert(std::initializer_list<PtrType> IL) { 401 insert(IL.begin(), IL.end()); 402 } 403 404 iterator begin() const { 405 if (shouldReverseIterate()) 406 return makeIterator(EndPointer() - 1); 407 return makeIterator(CurArray); 408 } 409 iterator end() const { return makeIterator(EndPointer()); } 410 411 private: 412 /// Create an iterator that dereferences to same place as the given pointer. 413 iterator makeIterator(const void *const *P) const { 414 if (shouldReverseIterate()) 415 return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this); 416 return iterator(P, EndPointer(), *this); 417 } 418 }; 419 420 /// Equality comparison for SmallPtrSet. 421 /// 422 /// Iterates over elements of LHS confirming that each value from LHS is also in 423 /// RHS, and that no additional values are in RHS. 424 template <typename PtrType> 425 bool operator==(const SmallPtrSetImpl<PtrType> &LHS, 426 const SmallPtrSetImpl<PtrType> &RHS) { 427 if (LHS.size() != RHS.size()) 428 return false; 429 430 for (const auto *KV : LHS) 431 if (!RHS.count(KV)) 432 return false; 433 434 return true; 435 } 436 437 /// Inequality comparison for SmallPtrSet. 438 /// 439 /// Equivalent to !(LHS == RHS). 440 template <typename PtrType> 441 bool operator!=(const SmallPtrSetImpl<PtrType> &LHS, 442 const SmallPtrSetImpl<PtrType> &RHS) { 443 return !(LHS == RHS); 444 } 445 446 /// SmallPtrSet - This class implements a set which is optimized for holding 447 /// SmallSize or less elements. This internally rounds up SmallSize to the next 448 /// power of two if it is not already a power of two. See the comments above 449 /// SmallPtrSetImplBase for details of the algorithm. 450 template<class PtrType, unsigned SmallSize> 451 class SmallPtrSet : public SmallPtrSetImpl<PtrType> { 452 // In small mode SmallPtrSet uses linear search for the elements, so it is 453 // not a good idea to choose this value too high. You may consider using a 454 // DenseSet<> instead if you expect many elements in the set. 455 static_assert(SmallSize <= 32, "SmallSize should be small"); 456 457 using BaseT = SmallPtrSetImpl<PtrType>; 458 459 // Make sure that SmallSize is a power of two, round up if not. 460 enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val }; 461 /// SmallStorage - Fixed size storage used in 'small mode'. 462 const void *SmallStorage[SmallSizePowTwo]; 463 464 public: 465 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} 466 SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {} 467 SmallPtrSet(SmallPtrSet &&that) 468 : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {} 469 470 template<typename It> 471 SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) { 472 this->insert(I, E); 473 } 474 475 SmallPtrSet(std::initializer_list<PtrType> IL) 476 : BaseT(SmallStorage, SmallSizePowTwo) { 477 this->insert(IL.begin(), IL.end()); 478 } 479 480 SmallPtrSet<PtrType, SmallSize> & 481 operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) { 482 if (&RHS != this) 483 this->CopyFrom(RHS); 484 return *this; 485 } 486 487 SmallPtrSet<PtrType, SmallSize> & 488 operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) { 489 if (&RHS != this) 490 this->MoveFrom(SmallSizePowTwo, std::move(RHS)); 491 return *this; 492 } 493 494 SmallPtrSet<PtrType, SmallSize> & 495 operator=(std::initializer_list<PtrType> IL) { 496 this->clear(); 497 this->insert(IL.begin(), IL.end()); 498 return *this; 499 } 500 501 /// swap - Swaps the elements of two sets. 502 void swap(SmallPtrSet<PtrType, SmallSize> &RHS) { 503 SmallPtrSetImplBase::swap(RHS); 504 } 505 }; 506 507 } // end namespace llvm 508 509 namespace std { 510 511 /// Implement std::swap in terms of SmallPtrSet swap. 512 template<class T, unsigned N> 513 inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { 514 LHS.swap(RHS); 515 } 516 517 } // end namespace std 518 519 #endif // LLVM_ADT_SMALLPTRSET_H 520