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 <initializer_list> 19 20 namespace llvm { 21 22 namespace detail { 23 struct DenseSetEmpty {}; 24 25 // Use the empty base class trick so we can create a DenseMap where the buckets 26 // contain only a single item. 27 template <typename KeyT> class DenseSetPair : public DenseSetEmpty { 28 KeyT key; 29 30 public: 31 KeyT &getFirst() { return key; } 32 const KeyT &getFirst() const { return key; } 33 DenseSetEmpty &getSecond() { return *this; } 34 const DenseSetEmpty &getSecond() const { return *this; } 35 }; 36 37 /// Base class for DenseSet and DenseSmallSet. 38 /// 39 /// MapTy should be either 40 /// 41 /// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 42 /// detail::DenseSetPair<ValueT>> 43 /// 44 /// or the equivalent SmallDenseMap type. ValueInfoT must implement the 45 /// DenseMapInfo "concept". 46 template <typename ValueT, typename MapTy, typename ValueInfoT> 47 class DenseSetImpl { 48 static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), 49 "DenseMap buckets unexpectedly large!"); 50 MapTy TheMap; 51 template <typename T> 52 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; 53 54 public: 55 typedef ValueT key_type; 56 typedef ValueT value_type; 57 typedef unsigned size_type; 58 59 explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {} 60 61 DenseSetImpl(std::initializer_list<ValueT> Elems) 62 : DenseSetImpl(Elems.size()) { 63 insert(Elems.begin(), Elems.end()); 64 } 65 66 bool empty() const { return TheMap.empty(); } 67 size_type size() const { return TheMap.size(); } 68 size_t getMemorySize() const { return TheMap.getMemorySize(); } 69 70 /// Grow the DenseSet so that it has at least Size buckets. Will not shrink 71 /// the Size of the set. 72 void resize(size_t Size) { TheMap.resize(Size); } 73 74 /// Grow the DenseSet so that it can contain at least \p NumEntries items 75 /// before resizing again. 76 void reserve(size_t Size) { TheMap.reserve(Size); } 77 78 void clear() { 79 TheMap.clear(); 80 } 81 82 /// Return 1 if the specified key is in the set, 0 otherwise. 83 size_type count(const_arg_type_t<ValueT> V) const { 84 return TheMap.count(V); 85 } 86 87 bool erase(const ValueT &V) { 88 return TheMap.erase(V); 89 } 90 91 void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); } 92 93 // Iterators. 94 95 class ConstIterator; 96 97 class Iterator { 98 typename MapTy::iterator I; 99 friend class DenseSetImpl; 100 friend class ConstIterator; 101 102 public: 103 typedef typename MapTy::iterator::difference_type difference_type; 104 typedef ValueT value_type; 105 typedef value_type *pointer; 106 typedef value_type &reference; 107 typedef std::forward_iterator_tag iterator_category; 108 109 Iterator() = default; 110 Iterator(const typename MapTy::iterator &i) : I(i) {} 111 112 ValueT &operator*() { return I->getFirst(); } 113 const ValueT &operator*() const { return I->getFirst(); } 114 ValueT *operator->() { return &I->getFirst(); } 115 const ValueT *operator->() const { return &I->getFirst(); } 116 117 Iterator& operator++() { ++I; return *this; } 118 Iterator operator++(int) { auto T = *this; ++I; return T; } 119 bool operator==(const ConstIterator& X) const { return I == X.I; } 120 bool operator!=(const ConstIterator& X) const { return I != X.I; } 121 }; 122 123 class ConstIterator { 124 typename MapTy::const_iterator I; 125 friend class DenseSet; 126 friend class Iterator; 127 128 public: 129 typedef typename MapTy::const_iterator::difference_type difference_type; 130 typedef ValueT value_type; 131 typedef value_type *pointer; 132 typedef value_type &reference; 133 typedef std::forward_iterator_tag iterator_category; 134 135 ConstIterator(const Iterator &B) : I(B.I) {} 136 137 ConstIterator() = default; 138 139 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 140 141 const ValueT &operator*() const { return I->getFirst(); } 142 const ValueT *operator->() const { return &I->getFirst(); } 143 144 ConstIterator& operator++() { ++I; return *this; } 145 ConstIterator operator++(int) { auto T = *this; ++I; return T; } 146 bool operator==(const ConstIterator& X) const { return I == X.I; } 147 bool operator!=(const ConstIterator& X) const { return I != X.I; } 148 }; 149 150 typedef Iterator iterator; 151 typedef ConstIterator const_iterator; 152 153 iterator begin() { return Iterator(TheMap.begin()); } 154 iterator end() { return Iterator(TheMap.end()); } 155 156 const_iterator begin() const { return ConstIterator(TheMap.begin()); } 157 const_iterator end() const { return ConstIterator(TheMap.end()); } 158 159 iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); } 160 const_iterator find(const_arg_type_t<ValueT> V) const { 161 return ConstIterator(TheMap.find(V)); 162 } 163 164 /// Alternative version of find() which allows a different, and possibly less 165 /// expensive, key type. 166 /// The DenseMapInfo is responsible for supplying methods 167 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type 168 /// used. 169 template <class LookupKeyT> 170 iterator find_as(const LookupKeyT &Val) { 171 return Iterator(TheMap.find_as(Val)); 172 } 173 template <class LookupKeyT> 174 const_iterator find_as(const LookupKeyT &Val) const { 175 return ConstIterator(TheMap.find_as(Val)); 176 } 177 178 void erase(Iterator I) { return TheMap.erase(I.I); } 179 void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 180 181 std::pair<iterator, bool> insert(const ValueT &V) { 182 detail::DenseSetEmpty Empty; 183 return TheMap.try_emplace(V, Empty); 184 } 185 186 std::pair<iterator, bool> insert(ValueT &&V) { 187 detail::DenseSetEmpty Empty; 188 return TheMap.try_emplace(std::move(V), Empty); 189 } 190 191 /// Alternative version of insert that uses a different (and possibly less 192 /// expensive) key type. 193 template <typename LookupKeyT> 194 std::pair<iterator, bool> insert_as(const ValueT &V, 195 const LookupKeyT &LookupKey) { 196 return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey); 197 } 198 template <typename LookupKeyT> 199 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) { 200 return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey); 201 } 202 203 // Range insertion of values. 204 template<typename InputIt> 205 void insert(InputIt I, InputIt E) { 206 for (; I != E; ++I) 207 insert(*I); 208 } 209 }; 210 211 } // namespace detail 212 213 /// Implements a dense probed hash-table based set. 214 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>> 215 class DenseSet : public detail::DenseSetImpl< 216 ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 217 detail::DenseSetPair<ValueT>>, 218 ValueInfoT> { 219 using BaseT = 220 detail::DenseSetImpl<ValueT, 221 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 222 detail::DenseSetPair<ValueT>>, 223 ValueInfoT>; 224 225 public: 226 using BaseT::BaseT; 227 }; 228 229 /// Implements a dense probed hash-table based set with some number of buckets 230 /// stored inline. 231 template <typename ValueT, unsigned InlineBuckets = 4, 232 typename ValueInfoT = DenseMapInfo<ValueT>> 233 class SmallDenseSet 234 : public detail::DenseSetImpl< 235 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, 236 ValueInfoT, detail::DenseSetPair<ValueT>>, 237 ValueInfoT> { 238 using BaseT = detail::DenseSetImpl< 239 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, 240 ValueInfoT, detail::DenseSetPair<ValueT>>, 241 ValueInfoT>; 242 243 public: 244 using BaseT::BaseT; 245 }; 246 247 } // end namespace llvm 248 249 #endif 250