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