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/ADL.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/DenseMapInfo.h"
20#include "llvm/ADT/STLForwardCompat.h"
21#include "llvm/Support/MathExtras.h"
22#include "llvm/Support/type_traits.h"
23#include <cstddef>
24#include <initializer_list>
25#include <iterator>
26#include <utility>
27
28namespace llvm {
29
30namespace detail {
31
32struct DenseSetEmpty {};
33
34// Use the empty base class trick so we can create a DenseMap where the buckets
35// contain only a single item.
36template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
37 KeyT key;
38
39public:
40 KeyT &getFirst() { return key; }
41 const KeyT &getFirst() const { return key; }
42 DenseSetEmpty &getSecond() { return *this; }
43 const DenseSetEmpty &getSecond() const { return *this; }
44};
45
46/// Base class for DenseSet and DenseSmallSet.
47///
48/// MapTy should be either
49///
50/// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
51/// detail::DenseSetPair<ValueT>>
52///
53/// or the equivalent SmallDenseMap type. ValueInfoT must implement the
54/// DenseMapInfo "concept".
55template <typename ValueT, typename MapTy, typename ValueInfoT>
56class DenseSetImpl {
57 static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
58 "DenseMap buckets unexpectedly large!");
59 MapTy TheMap;
60
61 template <typename T>
62 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
63
64public:
65 using key_type = ValueT;
66 using value_type = ValueT;
67 using size_type = unsigned;
68
69 explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
70
71 template <typename InputIt>
72 DenseSetImpl(const InputIt &I, const InputIt &E)
73 : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) {
74 insert(I, E);
75 }
76
77 DenseSetImpl(std::initializer_list<ValueT> Elems)
78 : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
79 insert(Elems.begin(), Elems.end());
80 }
81
82 template <typename Range>
83 DenseSetImpl(llvm::from_range_t, Range &&R)
84 : DenseSetImpl(adl_begin(R), adl_end(R)) {}
85
86 bool empty() const { return TheMap.empty(); }
87 size_type size() const { return TheMap.size(); }
88 size_t getMemorySize() const { return TheMap.getMemorySize(); }
89
90 /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
91 /// the Size of the set.
92 void resize(size_t Size) { TheMap.resize(Size); }
93
94 /// Grow the DenseSet so that it can contain at least \p NumEntries items
95 /// before resizing again.
96 void reserve(size_t Size) { TheMap.reserve(Size); }
97
98 void clear() { TheMap.clear(); }
99
100 /// Return 1 if the specified key is in the set, 0 otherwise.
101 size_type count(const_arg_type_t<ValueT> V) const { return TheMap.count(V); }
102
103 bool erase(const ValueT &V) { return TheMap.erase(V); }
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;
118 using value_type = ValueT;
119 using pointer = value_type *;
120 using reference = 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++() {
132 ++I;
133 return *this;
134 }
135 Iterator operator++(int) {
136 auto T = *this;
137 ++I;
138 return T;
139 }
140 friend bool operator==(const Iterator &X, const Iterator &Y) {
141 return X.I == Y.I;
142 }
143 friend bool operator!=(const Iterator &X, const Iterator &Y) {
144 return X.I != Y.I;
145 }
146 };
147
148 class ConstIterator {
149 typename MapTy::const_iterator I;
150 friend class DenseSetImpl;
151 friend class Iterator;
152
153 public:
154 using difference_type = typename MapTy::const_iterator::difference_type;
155 using value_type = ValueT;
156 using pointer = const value_type *;
157 using reference = const value_type &;
158 using iterator_category = std::forward_iterator_tag;
159
160 ConstIterator() = default;
161 ConstIterator(const Iterator &B) : I(B.I) {}
162 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
163
164 const ValueT &operator*() const { return I->getFirst(); }
165 const ValueT *operator->() const { return &I->getFirst(); }
166
167 ConstIterator &operator++() {
168 ++I;
169 return *this;
170 }
171 ConstIterator operator++(int) {
172 auto T = *this;
173 ++I;
174 return T;
175 }
176 friend bool operator==(const ConstIterator &X, const ConstIterator &Y) {
177 return X.I == Y.I;
178 }
179 friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) {
180 return X.I != Y.I;
181 }
182 };
183
184 using iterator = Iterator;
185 using const_iterator = ConstIterator;
186
187 iterator begin() { return Iterator(TheMap.begin()); }
188 iterator end() { return Iterator(TheMap.end()); }
189
190 const_iterator begin() const { return ConstIterator(TheMap.begin()); }
191 const_iterator end() const { return ConstIterator(TheMap.end()); }
192
193 iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
194 const_iterator find(const_arg_type_t<ValueT> V) const {
195 return ConstIterator(TheMap.find(V));
196 }
197
198 /// Check if the set contains the given element.
199 bool contains(const_arg_type_t<ValueT> V) const {
200 return TheMap.find(V) != TheMap.end();
201 }
202
203 /// Alternative version of find() which allows a different, and possibly less
204 /// expensive, key type.
205 /// The DenseMapInfo is responsible for supplying methods
206 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
207 /// used.
208 template <class LookupKeyT> iterator find_as(const LookupKeyT &Val) {
209 return Iterator(TheMap.find_as(Val));
210 }
211 template <class LookupKeyT>
212 const_iterator find_as(const LookupKeyT &Val) const {
213 return ConstIterator(TheMap.find_as(Val));
214 }
215
216 void erase(Iterator I) { return TheMap.erase(I.I); }
217 void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
218
219 std::pair<iterator, bool> insert(const ValueT &V) {
220 detail::DenseSetEmpty Empty;
221 return TheMap.try_emplace(V, Empty);
222 }
223
224 std::pair<iterator, bool> insert(ValueT &&V) {
225 detail::DenseSetEmpty Empty;
226 return TheMap.try_emplace(std::move(V), Empty);
227 }
228
229 /// Alternative version of insert that uses a different (and possibly less
230 /// expensive) key type.
231 template <typename LookupKeyT>
232 std::pair<iterator, bool> insert_as(const ValueT &V,
233 const LookupKeyT &LookupKey) {
234 return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
235 }
236 template <typename LookupKeyT>
237 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
238 return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
239 }
240
241 // Range insertion of values.
242 template <typename InputIt> void insert(InputIt I, InputIt E) {
243 for (; I != E; ++I)
244 insert(*I);
245 }
246
247 template <typename Range> void insert_range(Range &&R) {
248 insert(adl_begin(R), adl_end(R));
249 }
250};
251
252/// Equality comparison for DenseSet.
253///
254/// Iterates over elements of LHS confirming that each element is also a member
255/// of RHS, and that RHS contains no additional values.
256/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
257/// case is O(N^2) (if every hash collides).
258template <typename ValueT, typename MapTy, typename ValueInfoT>
259bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
260 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
261 if (LHS.size() != RHS.size())
262 return false;
263
264 for (auto &E : LHS)
265 if (!RHS.count(E))
266 return false;
267
268 return true;
269}
270
271/// Inequality comparison for DenseSet.
272///
273/// Equivalent to !(LHS == RHS). See operator== for performance notes.
274template <typename ValueT, typename MapTy, typename ValueInfoT>
275bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
276 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
277 return !(LHS == RHS);
278}
279
280} // end namespace detail
281
282/// Implements a dense probed hash-table based set.
283template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
284class DenseSet : public detail::DenseSetImpl<
285 ValueT,
286 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
287 detail::DenseSetPair<ValueT>>,
288 ValueInfoT> {
289 using BaseT =
290 detail::DenseSetImpl<ValueT,
291 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
292 detail::DenseSetPair<ValueT>>,
293 ValueInfoT>;
294
295public:
296 using BaseT::BaseT;
297};
298
299/// Implements a dense probed hash-table based set with some number of buckets
300/// stored inline.
301template <typename ValueT, unsigned InlineBuckets = 4,
302 typename ValueInfoT = DenseMapInfo<ValueT>>
303class SmallDenseSet
304 : public detail::DenseSetImpl<
305 ValueT,
306 SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
307 ValueInfoT, detail::DenseSetPair<ValueT>>,
308 ValueInfoT> {
309 using BaseT = detail::DenseSetImpl<
310 ValueT,
311 SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT,
312 detail::DenseSetPair<ValueT>>,
313 ValueInfoT>;
314
315public:
316 using BaseT::BaseT;
317};
318
319} // end namespace llvm
320
321#endif // LLVM_ADT_DENSESET_H
322

source code of llvm/include/llvm/ADT/DenseSet.h