Line data Source code
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 :
27 : namespace llvm {
28 :
29 : namespace detail {
30 :
31 : struct DenseSetEmpty {};
32 :
33 : // Use the empty base class trick so we can create a DenseMap where the buckets
34 : // contain only a single item.
35 : template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
36 : KeyT key;
37 :
38 : public:
39 228187966 : KeyT &getFirst() { return key; }
40 5868142 : 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".
54 : template <typename ValueT, typename MapTy, typename ValueInfoT>
55 2247795 : class 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 :
63 : public:
64 : using key_type = ValueT;
65 : using value_type = ValueT;
66 : using size_type = unsigned;
67 :
68 63342047 : explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
69 :
70 19743 : DenseSetImpl(std::initializer_list<ValueT> Elems)
71 19743 : : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
72 : insert(Elems.begin(), Elems.end());
73 19743 : }
74 7 :
75 7 : bool empty() const { return TheMap.empty(); }
76 : size_type size() const { return TheMap.size(); }
77 7 : size_t getMemorySize() const { return TheMap.getMemorySize(); }
78 7 :
79 7 : /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
80 : /// the Size of the set.
81 7 : void resize(size_t Size) { TheMap.resize(Size); }
82 14 :
83 14 : /// Grow the DenseSet so that it can contain at least \p NumEntries items
84 : /// before resizing again.
85 13450 : void reserve(size_t Size) { TheMap.reserve(Size); }
86 14 :
87 14 : void clear() {
88 14135589 : TheMap.clear();
89 14 : }
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 92069652 : return TheMap.count(V);
94 : }
95 :
96 : bool erase(const ValueT &V) {
97 98901601 : return TheMap.erase(V);
98 : }
99 :
100 : void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
101 4 :
102 : // Iterators.
103 :
104 : class ConstIterator;
105 :
106 : class Iterator {
107 : typename MapTy::iterator I;
108 : friend class DenseSetImpl;
109 50 : 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 45992447 : Iterator(const typename MapTy::iterator &i) : I(i) {}
120 :
121 169 : 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 25 : Iterator& operator++() { ++I; return *this; }
127 0 : Iterator operator++(int) { auto T = *this; ++I; return T; }
128 : bool operator==(const ConstIterator& X) const { return I == X.I; }
129 1041 : 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 42 : 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 8 : ConstIterator() = default;
145 10 : ConstIterator(const Iterator &B) : I(B.I) {}
146 1659131 : ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
147 :
148 4 : const ValueT &operator*() const { return I->getFirst(); }
149 : const ValueT *operator->() const { return &I->getFirst(); }
150 :
151 33 : ConstIterator& operator++() { ++I; return *this; }
152 : ConstIterator operator++(int) { auto T = *this; ++I; return T; }
153 766 : bool operator==(const ConstIterator& X) const { return I == X.I; }
154 820 : bool operator!=(const ConstIterator& X) const { return I != X.I; }
155 : };
156 :
157 : using iterator = Iterator;
158 : using const_iterator = ConstIterator;
159 :
160 9952130 : iterator begin() { return Iterator(TheMap.begin()); }
161 6 : iterator end() { return Iterator(TheMap.end()); }
162 44 :
163 1285518 : const_iterator begin() const { return ConstIterator(TheMap.begin()); }
164 : const_iterator end() const { return ConstIterator(TheMap.end()); }
165 :
166 356859 : 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 372493 : return ConstIterator(TheMap.find(V));
169 10 : }
170 4 :
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 8 : template <class LookupKeyT>
177 : iterator find_as(const LookupKeyT &Val) {
178 34821165 : return Iterator(TheMap.find_as(Val));
179 26 : }
180 : template <class LookupKeyT>
181 : const_iterator find_as(const LookupKeyT &Val) const {
182 1138 : return ConstIterator(TheMap.find_as(Val));
183 : }
184 8 :
185 6489 : 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 120320269 : return TheMap.try_emplace(V, Empty);
191 : }
192 :
193 : std::pair<iterator, bool> insert(ValueT &&V) {
194 16 : detail::DenseSetEmpty Empty;
195 105201285 : return TheMap.try_emplace(std::move(V), Empty);
196 : }
197 :
198 8 : /// Alternative version of insert that uses a different (and possibly less
199 : /// expensive) key type.
200 : template <typename LookupKeyT>
201 0 : std::pair<iterator, bool> insert_as(const ValueT &V,
202 : const LookupKeyT &LookupKey) {
203 1124137 : return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
204 : }
205 : template <typename LookupKeyT>
206 121 : 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 160 : template<typename InputIt>
212 29441 : void insert(InputIt I, InputIt E) {
213 149134 : for (; I != E; ++I)
214 53641 : insert(*I);
215 29441 : }
216 34 : };
217 84 :
218 : /// Equality comparison for DenseSet.
219 34 : ///
220 226 : /// Iterates over elements of LHS confirming that each element is also a member
221 446 : /// of RHS, and that RHS contains no additional values.
222 : /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
223 226 : /// case is O(N^2) (if every hash collides).
224 : template <typename ValueT, typename MapTy, typename ValueInfoT>
225 1 : bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
226 : const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
227 1 : if (LHS.size() != RHS.size())
228 : return false;
229 162 :
230 3 : for (auto &E : LHS)
231 : if (!RHS.count(E))
232 0 : return false;
233 :
234 1 : return true;
235 : }
236 :
237 : /// Inequality comparison for DenseSet.
238 : ///
239 : /// Equivalent to !(LHS == RHS). See operator== for performance notes.
240 : template <typename ValueT, typename MapTy, typename ValueInfoT>
241 12 : bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
242 : const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
243 12 : return !(LHS == RHS);
244 : }
245 :
246 48 : } // end namespace detail
247 :
248 : /// Implements a dense probed hash-table based set.
249 : template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
250 1030964 : class DenseSet : public detail::DenseSetImpl<
251 : ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
252 2 : detail::DenseSetPair<ValueT>>,
253 : ValueInfoT> {
254 2 : using BaseT =
255 : detail::DenseSetImpl<ValueT,
256 : DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
257 8 : detail::DenseSetPair<ValueT>>,
258 294 : ValueInfoT>;
259 :
260 : public:
261 19689 : using BaseT::BaseT;
262 : };
263 4 :
264 : /// Implements a dense probed hash-table based set with some number of buckets
265 4 : /// stored inline.
266 : template <typename ValueT, unsigned InlineBuckets = 4,
267 : typename ValueInfoT = DenseMapInfo<ValueT>>
268 578177 : class SmallDenseSet
269 : : public detail::DenseSetImpl<
270 : ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
271 : ValueInfoT, detail::DenseSetPair<ValueT>>,
272 2 : ValueInfoT> {
273 : using BaseT = detail::DenseSetImpl<
274 2 : ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
275 : ValueInfoT, detail::DenseSetPair<ValueT>>,
276 2 : ValueInfoT>;
277 :
278 : public:
279 8 : using BaseT::BaseT;
280 : };
281 :
282 : } // end namespace llvm
283 1 :
284 : #endif // LLVM_ADT_DENSESET_H
|
