LLVM  14.0.0git
DenseSet.h
Go to the documentation of this file.
1 //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- 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 DenseSet and SmallDenseSet classes.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_DENSESET_H
14 #define LLVM_ADT_DENSESET_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseMapInfo.h"
20 #include <algorithm>
21 #include <cstddef>
22 #include <initializer_list>
23 #include <iterator>
24 #include <utility>
25 
26 namespace llvm {
27 
28 namespace detail {
29 
30 struct DenseSetEmpty {};
31 
32 // Use the empty base class trick so we can create a DenseMap where the buckets
33 // contain only a single item.
34 template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
35  KeyT key;
36 
37 public:
38  KeyT &getFirst() { return key; }
39  const KeyT &getFirst() const { return key; }
40  DenseSetEmpty &getSecond() { return *this; }
41  const DenseSetEmpty &getSecond() const { return *this; }
42 };
43 
44 /// Base class for DenseSet and DenseSmallSet.
45 ///
46 /// MapTy should be either
47 ///
48 /// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
49 /// detail::DenseSetPair<ValueT>>
50 ///
51 /// or the equivalent SmallDenseMap type. ValueInfoT must implement the
52 /// DenseMapInfo "concept".
53 template <typename ValueT, typename MapTy, typename ValueInfoT>
54 class DenseSetImpl {
55  static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
56  "DenseMap buckets unexpectedly large!");
57  MapTy TheMap;
58 
59  template <typename T>
60  using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
61 
62 public:
63  using key_type = ValueT;
64  using value_type = ValueT;
65  using size_type = unsigned;
66 
67  explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
68 
69  template <typename InputIt>
70  DenseSetImpl(const InputIt &I, const InputIt &E)
71  : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) {
72  insert(I, E);
73  }
74 
75  DenseSetImpl(std::initializer_list<ValueT> Elems)
76  : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
77  insert(Elems.begin(), Elems.end());
78  }
79 
80  bool empty() const { return TheMap.empty(); }
81  size_type size() const { return TheMap.size(); }
82  size_t getMemorySize() const { return TheMap.getMemorySize(); }
83 
84  /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
85  /// the Size of the set.
86  void resize(size_t Size) { TheMap.resize(Size); }
87 
88  /// Grow the DenseSet so that it can contain at least \p NumEntries items
89  /// before resizing again.
90  void reserve(size_t Size) { TheMap.reserve(Size); }
91 
92  void clear() {
93  TheMap.clear();
94  }
95 
96  /// Return 1 if the specified key is in the set, 0 otherwise.
97  size_type count(const_arg_type_t<ValueT> V) const {
98  return TheMap.count(V);
99  }
100 
101  bool erase(const ValueT &V) {
102  return TheMap.erase(V);
103  }
104 
105  void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
106 
107  // Iterators.
108 
109  class ConstIterator;
110 
111  class Iterator {
112  typename MapTy::iterator I;
113  friend class DenseSetImpl;
114  friend class ConstIterator;
115 
116  public:
117  using difference_type = typename MapTy::iterator::difference_type;
119  using pointer = value_type *;
121  using iterator_category = std::forward_iterator_tag;
122 
123  Iterator() = default;
124  Iterator(const typename MapTy::iterator &i) : I(i) {}
125 
126  ValueT &operator*() { return I->getFirst(); }
127  const ValueT &operator*() const { return I->getFirst(); }
128  ValueT *operator->() { return &I->getFirst(); }
129  const ValueT *operator->() const { return &I->getFirst(); }
130 
131  Iterator& operator++() { ++I; return *this; }
132  Iterator operator++(int) { auto T = *this; ++I; return T; }
133  friend bool operator==(const Iterator &X, const Iterator &Y) {
134  return X.I == Y.I;
135  }
136  friend bool operator!=(const Iterator &X, const Iterator &Y) {
137  return X.I != Y.I;
138  }
139  };
140 
142  typename MapTy::const_iterator I;
143  friend class DenseSetImpl;
144  friend class Iterator;
145 
146  public:
147  using difference_type = typename MapTy::const_iterator::difference_type;
149  using pointer = const value_type *;
150  using reference = const value_type &;
151  using iterator_category = std::forward_iterator_tag;
152 
153  ConstIterator() = default;
154  ConstIterator(const Iterator &B) : I(B.I) {}
155  ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
156 
157  const ValueT &operator*() const { return I->getFirst(); }
158  const ValueT *operator->() const { return &I->getFirst(); }
159 
160  ConstIterator& operator++() { ++I; return *this; }
161  ConstIterator operator++(int) { auto T = *this; ++I; return T; }
162  friend bool operator==(const ConstIterator &X, const ConstIterator &Y) {
163  return X.I == Y.I;
164  }
165  friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) {
166  return X.I != Y.I;
167  }
168  };
169 
170  using iterator = Iterator;
171  using const_iterator = ConstIterator;
172 
173  iterator begin() { return Iterator(TheMap.begin()); }
174  iterator end() { return Iterator(TheMap.end()); }
175 
176  const_iterator begin() const { return ConstIterator(TheMap.begin()); }
177  const_iterator end() const { return ConstIterator(TheMap.end()); }
178 
179  iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
180  const_iterator find(const_arg_type_t<ValueT> V) const {
181  return ConstIterator(TheMap.find(V));
182  }
183 
184  /// Check if the set contains the given element.
185  bool contains(const_arg_type_t<ValueT> V) const {
186  return TheMap.find(V) != TheMap.end();
187  }
188 
189  /// Alternative version of find() which allows a different, and possibly less
190  /// expensive, key type.
191  /// The DenseMapInfo is responsible for supplying methods
192  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
193  /// used.
194  template <class LookupKeyT>
195  iterator find_as(const LookupKeyT &Val) {
196  return Iterator(TheMap.find_as(Val));
197  }
198  template <class LookupKeyT>
199  const_iterator find_as(const LookupKeyT &Val) const {
200  return ConstIterator(TheMap.find_as(Val));
201  }
202 
203  void erase(Iterator I) { return TheMap.erase(I.I); }
204  void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
205 
206  std::pair<iterator, bool> insert(const ValueT &V) {
208  return TheMap.try_emplace(V, Empty);
209  }
210 
211  std::pair<iterator, bool> insert(ValueT &&V) {
213  return TheMap.try_emplace(std::move(V), Empty);
214  }
215 
216  /// Alternative version of insert that uses a different (and possibly less
217  /// expensive) key type.
218  template <typename LookupKeyT>
219  std::pair<iterator, bool> insert_as(const ValueT &V,
220  const LookupKeyT &LookupKey) {
221  return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
222  }
223  template <typename LookupKeyT>
224  std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
225  return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
226  }
227 
228  // Range insertion of values.
229  template<typename InputIt>
230  void insert(InputIt I, InputIt E) {
231  for (; I != E; ++I)
232  insert(*I);
233  }
234 };
235 
236 /// Equality comparison for DenseSet.
237 ///
238 /// Iterates over elements of LHS confirming that each element is also a member
239 /// of RHS, and that RHS contains no additional values.
240 /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
241 /// case is O(N^2) (if every hash collides).
242 template <typename ValueT, typename MapTy, typename ValueInfoT>
245  if (LHS.size() != RHS.size())
246  return false;
247 
248  for (auto &E : LHS)
249  if (!RHS.count(E))
250  return false;
251 
252  return true;
253 }
254 
255 /// Inequality comparison for DenseSet.
256 ///
257 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
258 template <typename ValueT, typename MapTy, typename ValueInfoT>
261  return !(LHS == RHS);
262 }
263 
264 } // end namespace detail
265 
266 /// Implements a dense probed hash-table based set.
267 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
269  ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
270  detail::DenseSetPair<ValueT>>,
271  ValueInfoT> {
272  using BaseT =
273  detail::DenseSetImpl<ValueT,
274  DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
276  ValueInfoT>;
277 
278 public:
279  using BaseT::BaseT;
280 };
281 
282 /// Implements a dense probed hash-table based set with some number of buckets
283 /// stored inline.
284 template <typename ValueT, unsigned InlineBuckets = 4,
285  typename ValueInfoT = DenseMapInfo<ValueT>>
287  : public detail::DenseSetImpl<
288  ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
289  ValueInfoT, detail::DenseSetPair<ValueT>>,
290  ValueInfoT> {
291  using BaseT = detail::DenseSetImpl<
293  ValueInfoT, detail::DenseSetPair<ValueT>>,
294  ValueInfoT>;
295 
296 public:
297  using BaseT::BaseT;
298 };
299 
300 } // end namespace llvm
301 
302 #endif // LLVM_ADT_DENSESET_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::orc::BaseT
RTTIExtends< ObjectLinkingLayer, ObjectLayer > BaseT
Definition: ObjectLinkingLayer.cpp:615
MathExtras.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
KeyT
llvm::detail::DenseSetImpl::reserve
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
Definition: DenseSet.h:90
llvm::detail::DenseSetImpl::ConstIterator::operator->
const ValueT * operator->() const
Definition: DenseSet.h:158
llvm::detail::DenseSetPair::getSecond
DenseSetEmpty & getSecond()
Definition: DenseSet.h:40
llvm::detail::DenseSetImpl::ConstIterator::operator++
ConstIterator operator++(int)
Definition: DenseSet.h:161
llvm::detail::operator!=
bool operator!=(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Inequality comparison for DenseSet.
Definition: DenseSet.h:259
llvm::detail::DenseSetImpl::ConstIterator::operator++
ConstIterator & operator++()
Definition: DenseSet.h:160
llvm::detail::DenseSetImpl::find
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::detail::DenseSetImpl::insert
void insert(InputIt I, InputIt E)
Definition: DenseSet.h:230
llvm::detail::DenseSetImpl::DenseSetImpl
DenseSetImpl(std::initializer_list< ValueT > Elems)
Definition: DenseSet.h:75
DenseMap.h
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::detail::DenseSetImpl::find
const_iterator find(const_arg_type_t< ValueT > V) const
Definition: DenseSet.h:180
llvm::detail::DenseSetImpl::ConstIterator::operator!=
friend bool operator!=(const ConstIterator &X, const ConstIterator &Y)
Definition: DenseSet.h:165
llvm::PowerOf2Ceil
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:702
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
llvm::detail::DenseSetImpl::Iterator::operator*
ValueT & operator*()
Definition: DenseSet.h:126
llvm::detail::DenseSetImpl::getMemorySize
size_t getMemorySize() const
Definition: DenseSet.h:82
llvm::detail::DenseSetImpl::end
const_iterator end() const
Definition: DenseSet.h:177
llvm::detail::DenseSetImpl::ConstIterator::operator*
const ValueT & operator*() const
Definition: DenseSet.h:157
llvm::detail::DenseSetImpl::end
iterator end()
Definition: DenseSet.h:174
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::detail::DenseSetImpl::insert_as
std::pair< iterator, bool > insert_as(ValueT &&V, const LookupKeyT &LookupKey)
Definition: DenseSet.h:224
llvm::const_pointer_or_const_ref::type
const T & type
Definition: type_traits.h:64
llvm::detail::DenseSetImpl::DenseSetImpl
DenseSetImpl(unsigned InitialReserve=0)
Definition: DenseSet.h:67
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::detail::DenseSetImpl::swap
void swap(DenseSetImpl &RHS)
Definition: DenseSet.h:105
llvm::detail::DenseSetImpl::Iterator::operator->
ValueT * operator->()
Definition: DenseSet.h:128
llvm::detail::DenseSetImpl::Iterator::operator*
const ValueT & operator*() const
Definition: DenseSet.h:127
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::detail::DenseSetImpl::Iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:121
llvm::detail::DenseSetImpl::Iterator::operator!=
friend bool operator!=(const Iterator &X, const Iterator &Y)
Definition: DenseSet.h:136
llvm::detail::DenseSetImpl::erase
void erase(ConstIterator CI)
Definition: DenseSet.h:204
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::detail::DenseSetImpl::erase
void erase(Iterator I)
Definition: DenseSet.h:203
llvm::detail::DenseSetImpl::resize
void resize(size_t Size)
Grow the DenseSet so that it has at least Size buckets.
Definition: DenseSet.h:86
llvm::detail::DenseSetImpl< ConstantStruct *, DenseMap< ConstantStruct *, detail::DenseSetEmpty, MapInfo, detail::DenseSetPair< ConstantStruct * > >, MapInfo >::size_type
unsigned size_type
Definition: DenseSet.h:65
llvm::detail::operator==
bool operator==(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Equality comparison for DenseSet.
Definition: DenseSet.h:243
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::detail::DenseSetImpl::ConstIterator::ConstIterator
ConstIterator()=default
llvm::detail::DenseSetImpl::Iterator::operator++
Iterator operator++(int)
Definition: DenseSet.h:132
llvm::detail::DenseSetImpl::insert_as
std::pair< iterator, bool > insert_as(const ValueT &V, const LookupKeyT &LookupKey)
Alternative version of insert that uses a different (and possibly less expensive) key type.
Definition: DenseSet.h:219
llvm::detail::DenseSetImpl< ConstantStruct *, DenseMap< ConstantStruct *, detail::DenseSetEmpty, MapInfo, detail::DenseSetPair< ConstantStruct * > >, MapInfo >::const_iterator
ConstIterator const_iterator
Definition: DenseSet.h:171
llvm::detail::DenseSetImpl::find_as
const_iterator find_as(const LookupKeyT &Val) const
Definition: DenseSet.h:199
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::detail::DenseSetImpl::ConstIterator::difference_type
typename MapTy::const_iterator::difference_type difference_type
Definition: DenseSet.h:147
llvm::DenseMap
Definition: DenseMap.h:714
llvm::detail::DenseSetImpl::Iterator::Iterator
Iterator(const typename MapTy::iterator &i)
Definition: DenseSet.h:124
llvm::detail::DenseSetImpl::Iterator
Definition: DenseSet.h:111
llvm::pdb::Empty
@ Empty
Definition: PDBTypes.h:394
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
llvm::detail::DenseSetPair::getFirst
KeyT & getFirst()
Definition: DenseSet.h:38
llvm::detail::DenseSetImpl::begin
iterator begin()
Definition: DenseSet.h:173
llvm::detail::DenseSetImpl::Iterator::operator==
friend bool operator==(const Iterator &X, const Iterator &Y)
Definition: DenseSet.h:133
llvm::detail::DenseSetEmpty
Definition: DenseSet.h:30
llvm::detail::DenseSetImpl::ConstIterator::operator==
friend bool operator==(const ConstIterator &X, const ConstIterator &Y)
Definition: DenseSet.h:162
llvm::detail::DenseSetImpl::ConstIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:151
llvm::detail::DenseSetPair
Definition: DenseSet.h:34
llvm::ConstantStruct
Definition: Constants.h:441
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::detail::DenseSetPair::getFirst
const KeyT & getFirst() const
Definition: DenseSet.h:39
llvm::detail::DenseSetImpl::contains
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
ValueT
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(ValueT &&V)
Definition: DenseSet.h:211
std
Definition: BitVector.h:838
type_traits.h
llvm::detail::DenseSetImpl::ConstIterator
Definition: DenseSet.h:141
llvm::detail::DenseSetImpl::ConstIterator::ConstIterator
ConstIterator(const typename MapTy::const_iterator &i)
Definition: DenseSet.h:155
llvm::detail::DenseSetImpl::find_as
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive,...
Definition: DenseSet.h:195
llvm::detail::DenseSetImpl::DenseSetImpl
DenseSetImpl(const InputIt &I, const InputIt &E)
Definition: DenseSet.h:70
llvm::detail::DenseSetPair::getSecond
const DenseSetEmpty & getSecond() const
Definition: DenseSet.h:41
llvm::detail::DenseSetImpl::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
llvm::detail::DenseSetImpl::Iterator::operator++
Iterator & operator++()
Definition: DenseSet.h:131
DenseMapInfo.h
llvm::detail::DenseSetImpl::Iterator::Iterator
Iterator()=default
llvm::detail::DenseSetImpl::ConstIterator::ConstIterator
ConstIterator(const Iterator &B)
Definition: DenseSet.h:154
llvm::detail::DenseSetImpl< ConstantStruct *, DenseMap< ConstantStruct *, detail::DenseSetEmpty, MapInfo, detail::DenseSetPair< ConstantStruct * > >, MapInfo >::iterator
Iterator iterator
Definition: DenseSet.h:170
llvm::detail::DenseSetImpl::begin
const_iterator begin() const
Definition: DenseSet.h:176
llvm::detail::DenseSetImpl::Iterator::difference_type
typename MapTy::iterator::difference_type difference_type
Definition: DenseSet.h:117
llvm::detail::DenseSetImpl::Iterator::operator->
const ValueT * operator->() const
Definition: DenseSet.h:129
llvm::detail::DenseSetImpl
Base class for DenseSet and DenseSmallSet.
Definition: DenseSet.h:54