xref: /freebsd/contrib/llvm-project/llvm/include/llvm/ADT/DenseSet.h (revision a0409676120c1e558d0ade943019934e0f15118d)
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 // This file defines the DenseSet and SmallDenseSet classes.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_DENSESET_H
14 #define LLVM_ADT_DENSESET_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseMapInfo.h"
18 #include "llvm/Support/MathExtras.h"
19 #include "llvm/Support/type_traits.h"
20 #include <algorithm>
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   KeyT &getFirst() { return key; }
39   const KeyT &getFirst() const { return key; }
40   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   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     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     bool operator==(const ConstIterator& X) const { return I == X.I; }
134     bool operator!=(const ConstIterator& X) const { return I != X.I; }
135   };
136 
137   class ConstIterator {
138     typename MapTy::const_iterator I;
139     friend class DenseSetImpl;
140     friend class Iterator;
141 
142   public:
143     using difference_type = typename MapTy::const_iterator::difference_type;
144     using value_type = ValueT;
145     using pointer = const value_type *;
146     using reference = const value_type &;
147     using iterator_category = std::forward_iterator_tag;
148 
149     ConstIterator() = default;
150     ConstIterator(const Iterator &B) : I(B.I) {}
151     ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
152 
153     const ValueT &operator*() const { return I->getFirst(); }
154     const ValueT *operator->() const { return &I->getFirst(); }
155 
156     ConstIterator& operator++() { ++I; return *this; }
157     ConstIterator operator++(int) { auto T = *this; ++I; return T; }
158     bool operator==(const ConstIterator& X) const { return I == X.I; }
159     bool operator!=(const ConstIterator& X) const { return I != X.I; }
160   };
161 
162   using iterator = Iterator;
163   using const_iterator = ConstIterator;
164 
165   iterator begin() { return Iterator(TheMap.begin()); }
166   iterator end() { return Iterator(TheMap.end()); }
167 
168   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
169   const_iterator end() const { return ConstIterator(TheMap.end()); }
170 
171   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
172   const_iterator find(const_arg_type_t<ValueT> V) const {
173     return ConstIterator(TheMap.find(V));
174   }
175 
176   /// Alternative version of find() which allows a different, and possibly less
177   /// expensive, key type.
178   /// The DenseMapInfo is responsible for supplying methods
179   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
180   /// used.
181   template <class LookupKeyT>
182   iterator find_as(const LookupKeyT &Val) {
183     return Iterator(TheMap.find_as(Val));
184   }
185   template <class LookupKeyT>
186   const_iterator find_as(const LookupKeyT &Val) const {
187     return ConstIterator(TheMap.find_as(Val));
188   }
189 
190   void erase(Iterator I) { return TheMap.erase(I.I); }
191   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
192 
193   std::pair<iterator, bool> insert(const ValueT &V) {
194     detail::DenseSetEmpty Empty;
195     return TheMap.try_emplace(V, Empty);
196   }
197 
198   std::pair<iterator, bool> insert(ValueT &&V) {
199     detail::DenseSetEmpty Empty;
200     return TheMap.try_emplace(std::move(V), Empty);
201   }
202 
203   /// Alternative version of insert that uses a different (and possibly less
204   /// expensive) key type.
205   template <typename LookupKeyT>
206   std::pair<iterator, bool> insert_as(const ValueT &V,
207                                       const LookupKeyT &LookupKey) {
208     return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
209   }
210   template <typename LookupKeyT>
211   std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
212     return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
213   }
214 
215   // Range insertion of values.
216   template<typename InputIt>
217   void insert(InputIt I, InputIt E) {
218     for (; I != E; ++I)
219       insert(*I);
220   }
221 };
222 
223 /// Equality comparison for DenseSet.
224 ///
225 /// Iterates over elements of LHS confirming that each element is also a member
226 /// of RHS, and that RHS contains no additional values.
227 /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
228 /// case is O(N^2) (if every hash collides).
229 template <typename ValueT, typename MapTy, typename ValueInfoT>
230 bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
231                 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
232   if (LHS.size() != RHS.size())
233     return false;
234 
235   for (auto &E : LHS)
236     if (!RHS.count(E))
237       return false;
238 
239   return true;
240 }
241 
242 /// Inequality comparison for DenseSet.
243 ///
244 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
245 template <typename ValueT, typename MapTy, typename ValueInfoT>
246 bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
247                 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
248   return !(LHS == RHS);
249 }
250 
251 } // end namespace detail
252 
253 /// Implements a dense probed hash-table based set.
254 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
255 class DenseSet : public detail::DenseSetImpl<
256                      ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
257                                       detail::DenseSetPair<ValueT>>,
258                      ValueInfoT> {
259   using BaseT =
260       detail::DenseSetImpl<ValueT,
261                            DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
262                                     detail::DenseSetPair<ValueT>>,
263                            ValueInfoT>;
264 
265 public:
266   using BaseT::BaseT;
267 };
268 
269 /// Implements a dense probed hash-table based set with some number of buckets
270 /// stored inline.
271 template <typename ValueT, unsigned InlineBuckets = 4,
272           typename ValueInfoT = DenseMapInfo<ValueT>>
273 class SmallDenseSet
274     : public detail::DenseSetImpl<
275           ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
276                                 ValueInfoT, detail::DenseSetPair<ValueT>>,
277           ValueInfoT> {
278   using BaseT = detail::DenseSetImpl<
279       ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
280                             ValueInfoT, detail::DenseSetPair<ValueT>>,
281       ValueInfoT>;
282 
283 public:
284   using BaseT::BaseT;
285 };
286 
287 } // end namespace llvm
288 
289 #endif // LLVM_ADT_DENSESET_H
290