1//===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 10/// This file defines the SmallSet class. 12//===----------------------------------------------------------------------===// 14#ifndef LLVM_ADT_SMALLSET_H 15#define LLVM_ADT_SMALLSET_H 22#include <initializer_list> 28/// SmallSetIterator - This class implements a const_iterator for SmallSet by 29/// delegating to the underlying SmallVector or Set iterators. 30template <
typename T,
unsigned N,
typename C>
33 std::forward_iterator_tag, T> {
35usingSetIterTy =
typename std::set<T, C>::const_iterator;
39 /// Iterators to the parts of the SmallSet containing the data. They are set 40 /// depending on isSmall. 53// Spell out destructor, copy/move constructor and assignment operators for 54// MSVC STL, where set<T>::const_iterator is not trivially copy constructible. 66// Use placement new, to make sure SetIter is properly constructed, even 67// if it is not trivially copy-able (e.g. in MSVC). 75// Use placement new, to make sure SetIter is properly constructed, even 76// if it is not trivially copy-able (e.g. in MSVC). 81// Call destructor for SetIter, so it gets properly destroyed if it is 82// not trivially destructible in case we are setting VecIter. 86 IsSmall =
Other.IsSmall;
95// Call destructor for SetIter, so it gets properly destroyed if it is 96// not trivially destructible in case we are setting VecIter. 100 IsSmall =
Other.IsSmall;
109if (IsSmall !=
RHS.IsSmall)
127/// SmallSet - This maintains a set of unique values, optimizing for the case 128/// when the set is small (less than N). In this case, the set can be 129/// maintained with no mallocs. If the set gets large, we expand to using an 130/// std::set to maintain reasonable lookup times. 131template <
typename T,
unsigned N,
typename C = std::less<T>>
133 /// Use a SmallVector to hold the elements here (even though it will never 134 /// reach its 'large' stage) to avoid calling the default ctors of elements 135 /// we will never use. 139// In small mode SmallPtrSet uses linear search for the elements, so it is 140// not a good idea to choose this value too high. You may consider using a 141// DenseSet<> instead if you expect many elements in the set. 142static_assert(
N <= 32,
"N should be small");
158template <
typename RangeT>
160insert(R.begin(), R.end());
168 [[nodiscard]]
boolempty()
const{
return Vector.empty() && Set.empty(); }
171return isSmall() ? Vector.size() : Set.size();
174 /// count - Return 1 if the element is in the set, 0 otherwise. 177 /// insert - Insert an element into the set if it isn't already there. 178 /// Returns a pair. The first value of it is an iterator to the inserted 179 /// element or the existing element in the set. The second value is true 180 /// if the element is inserted (it was not in the set before). 181 std::pair<const_iterator, bool>
insert(
constT &V) {
return insertImpl(V); }
183 std::pair<const_iterator, bool>
insert(
T &&V) {
184return insertImpl(std::move(V));
187template <
typename IterT>
197if (
I != Vector.end()) {
211return {Vector.begin()};
217return {Vector.end()};
221 /// Check if the SmallSet contains the given element. 224return vfind(V) != Vector.end();
225return Set.find(V) != Set.end();
229bool isSmall()
const{
return Set.empty(); }
231template <
typename ArgType>
232 std::pair<const_iterator, bool> insertImpl(ArgType &&V) {
233static_assert(std::is_convertible_v<ArgType, T>,
234"ArgType must be convertible to T!");
236auto [
I, Inserted] = Set.insert(std::forward<ArgType>(V));
241if (
I !=
Vector.end())
// Don't reinsert if it already exists. 244Vector.push_back(std::forward<ArgType>(V));
247// Otherwise, grow from vector to set. 248Set.insert(std::make_move_iterator(
Vector.begin()),
249 std::make_move_iterator(
Vector.end()));
254// Handwritten linear search. The use of std::find might hurt performance as 255// its implementation may be optimized for larger containers. 256typename SmallVector<T, N>::const_iterator vfind(
constT &V)
const{
264/// If this set is of pointer values, transparently switch over to using 265/// SmallPtrSet for performance. 266template <
typename Po
inteeType,
unsigned N>
269/// Equality comparison for SmallSet. 271/// Iterates over elements of LHS confirming that each element is also a member 272/// of RHS, and that RHS contains no additional values. 273/// Equivalent to N calls to RHS.count. 274/// For small-set mode amortized complexity is O(N^2) 275/// For large-set mode amortized complexity is linear, worst case is O(N^2) (if 276/// every hash collides). 277template <
typename T,
unsigned LN,
unsigned RN,
typename C>
279if (
LHS.size() !=
RHS.size())
282// All elements in LHS must also be in RHS 286/// Inequality comparison for SmallSet. 288/// Equivalent to !(LHS == RHS). See operator== for performance notes. 289template <
typename T,
unsigned LN,
unsigned RN,
typename C>
294}
// end namespace llvm 296#endif// LLVM_ADT_SMALLSET_H static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSetIterator - This class implements a const_iterator for SmallSet by delegating to the underlyin...
SmallSetIterator & operator=(SmallSetIterator &&Other)
SmallSetIterator & operator++()
bool operator==(const SmallSetIterator &RHS) const
SmallSetIterator(SetIterTy SetIter)
SmallSetIterator & operator=(const SmallSetIterator &Other)
SmallSetIterator(const SmallSetIterator &Other)
const T & operator*() const
SmallSetIterator(VecIterTy VecIter)
SmallSetIterator(SmallSetIterator &&Other)
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
SmallSet(const iterator_range< RangeT > &R)
const_iterator begin() const
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
SmallSetIterator< T, N, C > const_iterator
void insert(IterT I, IterT E)
std::pair< const_iterator, bool > insert(T &&V)
SmallSet(std::initializer_list< T > L)
SmallSet & operator=(const SmallSet &)=default
SmallSet(SmallSet &&)=default
SmallSet(const SmallSet &)=default
const_iterator end() const
SmallSet(IterT Begin, IterT End)
bool contains(const T &V) const
Check if the SmallSet contains the given element.
SmallSet & operator=(SmallSet &&)=default
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
A range adaptor for a pair of iterators.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool operator!=(uint64_t V1, const APInt &V2)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
