Line data Source code
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"
18 : #include "llvm/ADT/DenseMapInfo.h"
19 : #include "llvm/Support/MathExtras.h"
20 : #include "llvm/Support/type_traits.h"
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 213555 : KeyT &getFirst() { return key; }
39 4417 : const KeyT &getFirst() const { return key; }
40 5983 : 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 998 : 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;
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 2132 : 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 :
141 : class ConstIterator {
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;
148 : using value_type = ValueT;
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 2132 : std::pair<iterator, bool> insert(const ValueT &V) {
207 : detail::DenseSetEmpty Empty;
208 2132 : return TheMap.try_emplace(V, Empty);
209 : }
210 :
211 : std::pair<iterator, bool> insert(ValueT &&V) {
212 : detail::DenseSetEmpty Empty;
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>
243 : bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
244 : const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
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>
259 : bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
260 : const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
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>>
268 : class DenseSet : public detail::DenseSetImpl<
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,
275 : detail::DenseSetPair<ValueT>>,
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>>
286 : class SmallDenseSet
287 : : public detail::DenseSetImpl<
288 : ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
289 : ValueInfoT, detail::DenseSetPair<ValueT>>,
290 : ValueInfoT> {
291 : using BaseT = detail::DenseSetImpl<
292 : ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
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
|
