LLVM  9.0.0svn
DenseSet.h
Go to the documentation of this file.
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"
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;
66 
67  explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
68 
69  DenseSetImpl(std::initializer_list<ValueT> Elems)
70  : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
71  insert(Elems.begin(), Elems.end());
72  }
73 
74  bool empty() const { return TheMap.empty(); }
75  size_type size() const { return TheMap.size(); }
76  size_t getMemorySize() const { return TheMap.getMemorySize(); }
77 
78  /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
79  /// the Size of the set.
80  void resize(size_t Size) { TheMap.resize(Size); }
81 
82  /// Grow the DenseSet so that it can contain at least \p NumEntries items
83  /// before resizing again.
84  void reserve(size_t Size) { TheMap.reserve(Size); }
85 
86  void clear() {
87  TheMap.clear();
88  }
89 
90  /// Return 1 if the specified key is in the set, 0 otherwise.
91  size_type count(const_arg_type_t<ValueT> V) const {
92  return TheMap.count(V);
93  }
94 
95  bool erase(const ValueT &V) {
96  return TheMap.erase(V);
97  }
98 
99  void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
100 
101  // Iterators.
102 
103  class ConstIterator;
104 
105  class Iterator {
106  typename MapTy::iterator I;
107  friend class DenseSetImpl;
108  friend class ConstIterator;
109 
110  public:
111  using difference_type = typename MapTy::iterator::difference_type;
113  using pointer = value_type *;
115  using iterator_category = std::forward_iterator_tag;
116 
117  Iterator() = default;
118  Iterator(const typename MapTy::iterator &i) : I(i) {}
119 
120  ValueT &operator*() { return I->getFirst(); }
121  const ValueT &operator*() const { return I->getFirst(); }
122  ValueT *operator->() { return &I->getFirst(); }
123  const ValueT *operator->() const { return &I->getFirst(); }
124 
125  Iterator& operator++() { ++I; return *this; }
126  Iterator operator++(int) { auto T = *this; ++I; return T; }
127  bool operator==(const ConstIterator& X) const { return I == X.I; }
128  bool operator!=(const ConstIterator& X) const { return I != X.I; }
129  };
130 
132  typename MapTy::const_iterator I;
133  friend class DenseSet;
134  friend class Iterator;
135 
136  public:
137  using difference_type = typename MapTy::const_iterator::difference_type;
139  using pointer = const value_type *;
140  using reference = const value_type &;
141  using iterator_category = std::forward_iterator_tag;
142 
143  ConstIterator() = default;
144  ConstIterator(const Iterator &B) : I(B.I) {}
145  ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
146 
147  const ValueT &operator*() const { return I->getFirst(); }
148  const ValueT *operator->() const { return &I->getFirst(); }
149 
150  ConstIterator& operator++() { ++I; return *this; }
151  ConstIterator operator++(int) { auto T = *this; ++I; return T; }
152  bool operator==(const ConstIterator& X) const { return I == X.I; }
153  bool operator!=(const ConstIterator& X) const { return I != X.I; }
154  };
155 
156  using iterator = Iterator;
157  using const_iterator = ConstIterator;
158 
159  iterator begin() { return Iterator(TheMap.begin()); }
160  iterator end() { return Iterator(TheMap.end()); }
161 
162  const_iterator begin() const { return ConstIterator(TheMap.begin()); }
163  const_iterator end() const { return ConstIterator(TheMap.end()); }
164 
165  iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
166  const_iterator find(const_arg_type_t<ValueT> V) const {
167  return ConstIterator(TheMap.find(V));
168  }
169 
170  /// Alternative version of find() which allows a different, and possibly less
171  /// expensive, key type.
172  /// The DenseMapInfo is responsible for supplying methods
173  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
174  /// used.
175  template <class LookupKeyT>
176  iterator find_as(const LookupKeyT &Val) {
177  return Iterator(TheMap.find_as(Val));
178  }
179  template <class LookupKeyT>
180  const_iterator find_as(const LookupKeyT &Val) const {
181  return ConstIterator(TheMap.find_as(Val));
182  }
183 
184  void erase(Iterator I) { return TheMap.erase(I.I); }
185  void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
186 
187  std::pair<iterator, bool> insert(const ValueT &V) {
189  return TheMap.try_emplace(V, Empty);
190  }
191 
192  std::pair<iterator, bool> insert(ValueT &&V) {
194  return TheMap.try_emplace(std::move(V), Empty);
195  }
196 
197  /// Alternative version of insert that uses a different (and possibly less
198  /// expensive) key type.
199  template <typename LookupKeyT>
200  std::pair<iterator, bool> insert_as(const ValueT &V,
201  const LookupKeyT &LookupKey) {
202  return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
203  }
204  template <typename LookupKeyT>
205  std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
206  return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
207  }
208 
209  // Range insertion of values.
210  template<typename InputIt>
211  void insert(InputIt I, InputIt E) {
212  for (; I != E; ++I)
213  insert(*I);
214  }
215 };
216 
217 /// Equality comparison for DenseSet.
218 ///
219 /// Iterates over elements of LHS confirming that each element is also a member
220 /// of RHS, and that RHS contains no additional values.
221 /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
222 /// case is O(N^2) (if every hash collides).
223 template <typename ValueT, typename MapTy, typename ValueInfoT>
226  if (LHS.size() != RHS.size())
227  return false;
228 
229  for (auto &E : LHS)
230  if (!RHS.count(E))
231  return false;
232 
233  return true;
234 }
235 
236 /// Inequality comparison for DenseSet.
237 ///
238 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
239 template <typename ValueT, typename MapTy, typename ValueInfoT>
242  return !(LHS == RHS);
243 }
244 
245 } // end namespace detail
246 
247 /// Implements a dense probed hash-table based set.
248 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
250  ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
251  detail::DenseSetPair<ValueT>>,
252  ValueInfoT> {
253  using BaseT =
254  detail::DenseSetImpl<ValueT,
255  DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
257  ValueInfoT>;
258 
259 public:
260  using BaseT::BaseT;
261 };
262 
263 /// Implements a dense probed hash-table based set with some number of buckets
264 /// stored inline.
265 template <typename ValueT, unsigned InlineBuckets = 4,
266  typename ValueInfoT = DenseMapInfo<ValueT>>
268  : public detail::DenseSetImpl<
269  ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
270  ValueInfoT, detail::DenseSetPair<ValueT>>,
271  ValueInfoT> {
272  using BaseT = detail::DenseSetImpl<
273  ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
274  ValueInfoT, detail::DenseSetPair<ValueT>>,
275  ValueInfoT>;
276 
277 public:
278  using BaseT::BaseT;
279 };
280 
281 } // end namespace llvm
282 
283 #endif // LLVM_ADT_DENSESET_H
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool operator!=(const ConstIterator &X) const
Definition: DenseSet.h:153
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const KeyT & getFirst() const
Definition: DenseSet.h:39
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
bool erase(const ValueT &V)
Definition: DenseSet.h:95
std::pair< iterator, bool > insert_as(ValueT &&V, const LookupKeyT &LookupKey)
Definition: DenseSet.h:205
bool operator!=(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Inequality comparison for DenseSet.
Definition: DenseSet.h:240
bool operator==(const ConstIterator &X) const
Definition: DenseSet.h:152
bool operator==(const ConstIterator &X) const
Definition: DenseSet.h:127
#define T
DenseSetEmpty & getSecond()
Definition: DenseSet.h:40
Iterator(const typename MapTy::iterator &i)
Definition: DenseSet.h:118
bool operator==(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Equality comparison for DenseSet.
Definition: DenseSet.h:224
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
std::pair< iterator, bool > insert_as(const ValueT &V, const LookupKeyT &LookupKey)
Alternative version of insert that uses a different (and possibly less expensive) key type...
Definition: DenseSet.h:200
bool operator!=(const ConstIterator &X) const
Definition: DenseSet.h:128
const ValueT & operator*() const
Definition: DenseSet.h:121
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
const_iterator begin() const
Definition: DenseSet.h:162
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseSet.h:176
std::pair< iterator, bool > insert(ValueT &&V)
Definition: DenseSet.h:192
void erase(Iterator I)
Definition: DenseSet.h:184
void insert(InputIt I, InputIt E)
Definition: DenseSet.h:211
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:141
void swap(DenseSetImpl &RHS)
Definition: DenseSet.h:99
DenseSetImpl(std::initializer_list< ValueT > Elems)
Definition: DenseSet.h:69
DenseSetImpl(unsigned InitialReserve=0)
Definition: DenseSet.h:67
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1166
size_type size() const
Definition: DenseSet.h:75
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:267
typename MapTy::const_iterator::difference_type difference_type
Definition: DenseSet.h:137
const ValueT * operator->() const
Definition: DenseSet.h:123
void erase(ConstIterator CI)
Definition: DenseSet.h:185
void resize(size_t Size)
Grow the DenseSet so that it has at least Size buckets.
Definition: DenseSet.h:80
ConstIterator(const typename MapTy::const_iterator &i)
Definition: DenseSet.h:145
#define I(x, y, z)
Definition: MD5.cpp:58
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:165
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again...
Definition: DenseSet.h:84
uint32_t Size
Definition: Profile.cpp:46
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
const ValueT & operator*() const
Definition: DenseSet.h:147
const ValueT * operator->() const
Definition: DenseSet.h:148
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:115
typename MapTy::iterator::difference_type difference_type
Definition: DenseSet.h:111
const_iterator find_as(const LookupKeyT &Val) const
Definition: DenseSet.h:180
const_iterator find(const_arg_type_t< ValueT > V) const
Definition: DenseSet.h:166
size_t getMemorySize() const
Definition: DenseSet.h:76
const DenseSetEmpty & getSecond() const
Definition: DenseSet.h:41
const_iterator end() const
Definition: DenseSet.h:163
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:658
Base class for DenseSet and DenseSmallSet.
Definition: DenseSet.h:54