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 class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_DENSESET_H 15 #define LLVM_ADT_DENSESET_H 16 17 #include "llvm/ADT/DenseMap.h" 18 19 namespace llvm { 20 21 namespace detail { 22 struct DenseSetEmpty {}; 23 24 // Use the empty base class trick so we can create a DenseMap where the buckets 25 // contain only a single item. 26 template <typename KeyT> class DenseSetPair : public DenseSetEmpty { 27 KeyT key; 28 29 public: getFirst()30 KeyT &getFirst() { return key; } getFirst()31 const KeyT &getFirst() const { return key; } getSecond()32 DenseSetEmpty &getSecond() { return *this; } getSecond()33 const DenseSetEmpty &getSecond() const { return *this; } 34 }; 35 } 36 37 /// DenseSet - This implements a dense probed hash-table based set. 38 template<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> > 39 class DenseSet { 40 typedef DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 41 detail::DenseSetPair<ValueT>> MapTy; 42 static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), 43 "DenseMap buckets unexpectedly large!"); 44 MapTy TheMap; 45 46 public: 47 typedef ValueT key_type; 48 typedef ValueT value_type; 49 typedef unsigned size_type; 50 TheMap(NumInitBuckets)51 explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {} 52 empty()53 bool empty() const { return TheMap.empty(); } size()54 size_type size() const { return TheMap.size(); } getMemorySize()55 size_t getMemorySize() const { return TheMap.getMemorySize(); } 56 57 /// Grow the DenseSet so that it has at least Size buckets. Will not shrink 58 /// the Size of the set. resize(size_t Size)59 void resize(size_t Size) { TheMap.resize(Size); } 60 clear()61 void clear() { 62 TheMap.clear(); 63 } 64 65 /// Return 1 if the specified key is in the set, 0 otherwise. count(const ValueT & V)66 size_type count(const ValueT &V) const { 67 return TheMap.count(V); 68 } 69 erase(const ValueT & V)70 bool erase(const ValueT &V) { 71 return TheMap.erase(V); 72 } 73 swap(DenseSet & RHS)74 void swap(DenseSet& RHS) { 75 TheMap.swap(RHS.TheMap); 76 } 77 78 // Iterators. 79 80 class Iterator { 81 typename MapTy::iterator I; 82 friend class DenseSet; 83 84 public: 85 typedef typename MapTy::iterator::difference_type difference_type; 86 typedef ValueT value_type; 87 typedef value_type *pointer; 88 typedef value_type &reference; 89 typedef std::forward_iterator_tag iterator_category; 90 Iterator(const typename MapTy::iterator & i)91 Iterator(const typename MapTy::iterator &i) : I(i) {} 92 93 ValueT &operator*() { return I->getFirst(); } 94 ValueT *operator->() { return &I->getFirst(); } 95 96 Iterator& operator++() { ++I; return *this; } 97 Iterator operator++(int) { auto T = *this; ++I; return T; } 98 bool operator==(const Iterator& X) const { return I == X.I; } 99 bool operator!=(const Iterator& X) const { return I != X.I; } 100 }; 101 102 class ConstIterator { 103 typename MapTy::const_iterator I; 104 friend class DenseSet; 105 106 public: 107 typedef typename MapTy::const_iterator::difference_type difference_type; 108 typedef ValueT value_type; 109 typedef value_type *pointer; 110 typedef value_type &reference; 111 typedef std::forward_iterator_tag iterator_category; 112 ConstIterator(const typename MapTy::const_iterator & i)113 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 114 115 const ValueT &operator*() { return I->getFirst(); } 116 const ValueT *operator->() { return &I->getFirst(); } 117 118 ConstIterator& operator++() { ++I; return *this; } 119 ConstIterator operator++(int) { auto T = *this; ++I; return T; } 120 bool operator==(const ConstIterator& X) const { return I == X.I; } 121 bool operator!=(const ConstIterator& X) const { return I != X.I; } 122 }; 123 124 typedef Iterator iterator; 125 typedef ConstIterator const_iterator; 126 begin()127 iterator begin() { return Iterator(TheMap.begin()); } end()128 iterator end() { return Iterator(TheMap.end()); } 129 begin()130 const_iterator begin() const { return ConstIterator(TheMap.begin()); } end()131 const_iterator end() const { return ConstIterator(TheMap.end()); } 132 find(const ValueT & V)133 iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } 134 135 /// Alternative version of find() which allows a different, and possibly less 136 /// expensive, key type. 137 /// The DenseMapInfo is responsible for supplying methods 138 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type 139 /// used. 140 template <class LookupKeyT> find_as(const LookupKeyT & Val)141 iterator find_as(const LookupKeyT &Val) { 142 return Iterator(TheMap.find_as(Val)); 143 } 144 template <class LookupKeyT> find_as(const LookupKeyT & Val)145 const_iterator find_as(const LookupKeyT &Val) const { 146 return ConstIterator(TheMap.find_as(Val)); 147 } 148 erase(Iterator I)149 void erase(Iterator I) { return TheMap.erase(I.I); } erase(ConstIterator CI)150 void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 151 insert(const ValueT & V)152 std::pair<iterator, bool> insert(const ValueT &V) { 153 detail::DenseSetEmpty Empty; 154 return TheMap.insert(std::make_pair(V, Empty)); 155 } 156 157 /// Alternative version of insert that uses a different (and possibly less 158 /// expensive) key type. 159 template <typename LookupKeyT> insert_as(const ValueT & V,const LookupKeyT & LookupKey)160 std::pair<iterator, bool> insert_as(const ValueT &V, 161 const LookupKeyT &LookupKey) { 162 return insert_as(ValueT(V), LookupKey); 163 } 164 template <typename LookupKeyT> insert_as(ValueT && V,const LookupKeyT & LookupKey)165 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) { 166 detail::DenseSetEmpty Empty; 167 return TheMap.insert_as(std::make_pair(std::move(V), Empty), LookupKey); 168 } 169 170 // Range insertion of values. 171 template<typename InputIt> insert(InputIt I,InputIt E)172 void insert(InputIt I, InputIt E) { 173 for (; I != E; ++I) 174 insert(*I); 175 } 176 }; 177 178 } // end namespace llvm 179 180 #endif 181