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