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/type_traits.h"
20#include <algorithm>
21#include <cstddef>
22#include <initializer_list>
23#include <iterator>
24#include <utility>
25
26namespace llvm {
27
28namespace detail {
29
30struct DenseSetEmpty {};
31
32// Use the empty base class trick so we can create a DenseMap where the buckets
33// contain only a single item.
34template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
35  KeyT key;
36
37public:
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".
53template <typename ValueT, typename MapTy, typename ValueInfoT>
54class 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
62public:
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  DenseSetImpl(std::initializer_list<ValueT> Elems)
70      : DenseSetImpl(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;
112    using value_type = ValueT;
113    using pointer = value_type *;
114    using reference = 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
131  class ConstIterator {
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;
138    using value_type = ValueT;
139    using pointer = value_type *;
140    using reference = 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) {
188    detail::DenseSetEmpty Empty;
189    return TheMap.try_emplace(V, Empty);
190  }
191
192  std::pair<iterator, bool> insert(ValueT &&V) {
193    detail::DenseSetEmpty Empty;
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} // end namespace detail
218
219/// Implements a dense probed hash-table based set.
220template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
221class DenseSet : public detail::DenseSetImpl<
222                     ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
223                                      detail::DenseSetPair<ValueT>>,
224                     ValueInfoT> {
225  using BaseT =
226      detail::DenseSetImpl<ValueT,
227                           DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
228                                    detail::DenseSetPair<ValueT>>,
229                           ValueInfoT>;
230
231public:
232  using BaseT::BaseT;
233};
234
235/// Implements a dense probed hash-table based set with some number of buckets
236/// stored inline.
237template <typename ValueT, unsigned InlineBuckets = 4,
238          typename ValueInfoT = DenseMapInfo<ValueT>>
239class SmallDenseSet
240    : public detail::DenseSetImpl<
241          ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
242                                ValueInfoT, detail::DenseSetPair<ValueT>>,
243          ValueInfoT> {
244  using BaseT = detail::DenseSetImpl<
245      ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
246                            ValueInfoT, detail::DenseSetPair<ValueT>>,
247      ValueInfoT>;
248
249public:
250  using BaseT::BaseT;
251};
252
253} // end namespace llvm
254
255#endif // LLVM_ADT_DENSESET_H
256