LLVM 17.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/// \file
10/// This file defines the DenseSet and SmallDenseSet classes.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_DENSESET_H
15#define LLVM_ADT_DENSESET_H
16
17#include "llvm/ADT/DenseMap.h"
21#include <cstddef>
22#include <initializer_list>
23#include <iterator>
24#include <utility>
25
26namespace llvm {
27
28namespace detail {
29
30struct DenseSetEmpty {};
31
32// Use the empty base class trick so we can create a DenseMap where the buckets
33// contain only a single item.
34template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
35 KeyT key;
36
37public:
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".
53template <typename ValueT, typename MapTy, typename ValueInfoT>
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
62public:
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;
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
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).
242template <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.
258template <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.
267template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
269 ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
270 detail::DenseSetPair<ValueT>>,
271 ValueInfoT> {
272 using BaseT =
276 ValueInfoT>;
277
278public:
279 using BaseT::BaseT;
280};
281
282/// Implements a dense probed hash-table based set with some number of buckets
283/// stored inline.
284template <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> {
293 ValueInfoT, detail::DenseSetPair<ValueT>>,
294 ValueInfoT>;
295
296public:
297 using BaseT::BaseT;
298};
299
300} // end namespace llvm
301
302#endif // LLVM_ADT_DENSESET_H
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
uint64_t Size
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define I(x, y, z)
Definition: MD5.cpp:58
#define T
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
Value * RHS
Value * LHS
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
const ValueT & operator*() const
Definition: DenseSet.h:157
friend bool operator!=(const ConstIterator &X, const ConstIterator &Y)
Definition: DenseSet.h:165
friend bool operator==(const ConstIterator &X, const ConstIterator &Y)
Definition: DenseSet.h:162
typename MapTy::const_iterator::difference_type difference_type
Definition: DenseSet.h:147
ConstIterator(const typename MapTy::const_iterator &i)
Definition: DenseSet.h:155
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:151
const ValueT * operator->() const
Definition: DenseSet.h:158
friend bool operator==(const Iterator &X, const Iterator &Y)
Definition: DenseSet.h:133
const ValueT & operator*() const
Definition: DenseSet.h:127
const ValueT * operator->() const
Definition: DenseSet.h:129
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:121
friend bool operator!=(const Iterator &X, const Iterator &Y)
Definition: DenseSet.h:136
typename MapTy::iterator::difference_type difference_type
Definition: DenseSet.h:117
Iterator(const typename MapTy::iterator &i)
Definition: DenseSet.h:124
Base class for DenseSet and DenseSmallSet.
Definition: DenseSet.h:54
const_iterator find(const_arg_type_t< ValueT > V) const
Definition: DenseSet.h:180
std::pair< iterator, bool > insert(ValueT &&V)
Definition: DenseSet.h:211
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_t getMemorySize() const
Definition: DenseSet.h:82
const_iterator end() const
Definition: DenseSet.h:177
const_iterator begin() const
Definition: DenseSet.h:176
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
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
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
Definition: DenseSet.h:90
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive,...
Definition: DenseSet.h:195
const_iterator find_as(const LookupKeyT &Val) const
Definition: DenseSet.h:199
size_type size() const
Definition: DenseSet.h:81
std::pair< iterator, bool > insert_as(ValueT &&V, const LookupKeyT &LookupKey)
Definition: DenseSet.h:224
void insert(InputIt I, InputIt E)
Definition: DenseSet.h:230
void swap(DenseSetImpl &RHS)
Definition: DenseSet.h:105
DenseSetImpl(unsigned InitialReserve=0)
Definition: DenseSet.h:67
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
DenseSetImpl(const InputIt &I, const InputIt &E)
Definition: DenseSet.h:70
void resize(size_t Size)
Grow the DenseSet so that it has at least Size buckets.
Definition: DenseSet.h:86
void erase(ConstIterator CI)
Definition: DenseSet.h:204
bool erase(const ValueT &V)
Definition: DenseSet.h:101
void erase(Iterator I)
Definition: DenseSet.h:203
DenseSetImpl(std::initializer_list< ValueT > Elems)
Definition: DenseSet.h:75
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
const DenseSetEmpty & getSecond() const
Definition: DenseSet.h:41
const KeyT & getFirst() const
Definition: DenseSet.h:39
DenseSetEmpty & getSecond()
Definition: DenseSet.h:40
bool operator!=(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Inequality comparison for DenseSet.
Definition: DenseSet.h:259
bool operator==(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Equality comparison for DenseSet.
Definition: DenseSet.h:243
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:455
Definition: BitVector.h:851
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51