//===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// /// \file /// This file defines the SmallPtrSet class. See the doxygen comment for /// SmallPtrSetImplBase for more details on the algorithm used. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_SMALLPTRSET_H #define LLVM_ADT_SMALLPTRSET_H #include "llvm/ADT/EpochTracker.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/ReverseIteration.h" #include "llvm/Support/type_traits.h" #include <algorithm> #include <cassert> #include <cstddef> #include <cstdlib> #include <cstring> #include <initializer_list> #include <iterator> #include <limits> #include <utility> namespace llvm { /// SmallPtrSetImplBase - This is the common code shared among all the /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one /// for small and one for large sets. /// /// Small sets use an array of pointers allocated in the SmallPtrSet object, /// which is treated as a simple array of pointers. When a pointer is added to /// the set, the array is scanned to see if the element already exists, if not /// the element is 'pushed back' onto the array. If we run out of space in the /// array, we grow into the 'large set' case. SmallSet should be used when the /// sets are often small. In this case, no memory allocation is used, and only /// light-weight and cache-efficient scanning is used. /// /// Large sets use a classic exponentially-probed hash table. Empty buckets are /// represented with an illegal pointer value (-1) to allow null pointers to be /// inserted. Tombstones are represented with another illegal pointer value /// (-2), to allow deletion. The hash table is resized when the table is 3/4 or /// more. When this happens, the table is doubled in size. /// class SmallPtrSetImplBase : public DebugEpochBase { … }; /// SmallPtrSetIteratorImpl - This is the common base class shared between all /// instances of SmallPtrSetIterator. class SmallPtrSetIteratorImpl { … }; /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. template <typename PtrTy> class LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE SmallPtrSetIterator : public SmallPtrSetIteratorImpl, DebugEpochBase::HandleBase { … }; /// A templated base class for \c SmallPtrSet which provides the /// typesafe interface that is common across all small sizes. /// /// This is particularly useful for passing around between interface boundaries /// to avoid encoding a particular small size in the interface boundary. template <typename PtrType> class SmallPtrSetImpl : public SmallPtrSetImplBase { … }; /// Equality comparison for SmallPtrSet. /// /// Iterates over elements of LHS confirming that each value from LHS is also in /// RHS, and that no additional values are in RHS. template <typename PtrType> bool operator==(const SmallPtrSetImpl<PtrType> &LHS, const SmallPtrSetImpl<PtrType> &RHS) { … } /// Inequality comparison for SmallPtrSet. /// /// Equivalent to !(LHS == RHS). template <typename PtrType> bool operator!=(const SmallPtrSetImpl<PtrType> &LHS, const SmallPtrSetImpl<PtrType> &RHS) { … } /// SmallPtrSet - This class implements a set which is optimized for holding /// SmallSize or less elements. This internally rounds up SmallSize to the next /// power of two if it is not already a power of two. See the comments above /// SmallPtrSetImplBase for details of the algorithm. template<class PtrType, unsigned SmallSize> class SmallPtrSet : public SmallPtrSetImpl<PtrType> { … }; } // end namespace llvm namespace std { /// Implement std::swap in terms of SmallPtrSet swap. template<class T, unsigned N> inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { … } } // end namespace std #endif // LLVM_ADT_SMALLPTRSET_H