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