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: 30 KeyT &getFirst() { return key; } 31 const KeyT &getFirst() const { return key; } 32 DenseSetEmpty &getSecond() { return *this; } 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 51 explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {} 52 53 bool empty() const { return TheMap.empty(); } 54 size_type size() const { return TheMap.size(); } 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. 59 void resize(size_t Size) { TheMap.resize(Size); } 60 61 void clear() { 62 TheMap.clear(); 63 } 64 65 /// Return 1 if the specified key is in the set, 0 otherwise. 66 size_type count(const ValueT &V) const { 67 return TheMap.count(V); 68 } 69 70 bool erase(const ValueT &V) { 71 return TheMap.erase(V); 72 } 73 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 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 bool operator==(const Iterator& X) const { return I == X.I; } 98 bool operator!=(const Iterator& X) const { return I != X.I; } 99 }; 100 101 class ConstIterator { 102 typename MapTy::const_iterator I; 103 friend class DenseSet; 104 105 public: 106 typedef typename MapTy::const_iterator::difference_type difference_type; 107 typedef ValueT value_type; 108 typedef value_type *pointer; 109 typedef value_type &reference; 110 typedef std::forward_iterator_tag iterator_category; 111 112 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 113 114 const ValueT &operator*() { return I->getFirst(); } 115 const ValueT *operator->() { return &I->getFirst(); } 116 117 ConstIterator& operator++() { ++I; return *this; } 118 bool operator==(const ConstIterator& X) const { return I == X.I; } 119 bool operator!=(const ConstIterator& X) const { return I != X.I; } 120 }; 121 122 typedef Iterator iterator; 123 typedef ConstIterator const_iterator; 124 125 iterator begin() { return Iterator(TheMap.begin()); } 126 iterator end() { return Iterator(TheMap.end()); } 127 128 const_iterator begin() const { return ConstIterator(TheMap.begin()); } 129 const_iterator end() const { return ConstIterator(TheMap.end()); } 130 131 iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } 132 133 /// Alternative version of find() which allows a different, and possibly less 134 /// expensive, key type. 135 /// The DenseMapInfo is responsible for supplying methods 136 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type 137 /// used. 138 template <class LookupKeyT> 139 iterator find_as(const LookupKeyT &Val) { 140 return Iterator(TheMap.find_as(Val)); 141 } 142 template <class LookupKeyT> 143 const_iterator find_as(const LookupKeyT &Val) const { 144 return ConstIterator(TheMap.find_as(Val)); 145 } 146 147 void erase(Iterator I) { return TheMap.erase(I.I); } 148 void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 149 150 std::pair<iterator, bool> insert(const ValueT &V) { 151 detail::DenseSetEmpty Empty; 152 return TheMap.insert(std::make_pair(V, Empty)); 153 } 154 155 // Range insertion of values. 156 template<typename InputIt> 157 void insert(InputIt I, InputIt E) { 158 for (; I != E; ++I) 159 insert(*I); 160 } 161 }; 162 163 } // end namespace llvm 164 165 #endif 166
