Branch data 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 : 0 : KeyT &getFirst() { return key; }
39 : 0 : const KeyT &getFirst() const { return key; }
40 : 0 : 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 : 0 : 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 : 0 : 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 : 0 : std::pair<iterator, bool> insert(const ValueT &V) {
207 : : detail::DenseSetEmpty Empty;
208 [ # # # # ]: 0 : 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
|
