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 public: 46 typedef ValueT key_type; 47 typedef ValueT value_type; 48 typedef unsigned size_type; 49 TheMap(NumInitBuckets)50 explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {} 51 empty()52 bool empty() const { return TheMap.empty(); } size()53 size_type size() const { return TheMap.size(); } getMemorySize()54 size_t getMemorySize() const { return TheMap.getMemorySize(); } 55 56 /// Grow the DenseSet so that it has at least Size buckets. Will not shrink 57 /// the Size of the set. resize(size_t Size)58 void resize(size_t Size) { TheMap.resize(Size); } 59 clear()60 void clear() { 61 TheMap.clear(); 62 } 63 64 /// Return 1 if the specified key is in the set, 0 otherwise. count(const ValueT & V)65 size_type count(const ValueT &V) const { 66 return TheMap.count(V); 67 } 68 erase(const ValueT & V)69 bool erase(const ValueT &V) { 70 return TheMap.erase(V); 71 } 72 swap(DenseSet & RHS)73 void swap(DenseSet& RHS) { 74 TheMap.swap(RHS.TheMap); 75 } 76 77 // Iterators. 78 79 class Iterator { 80 typename MapTy::iterator I; 81 friend class DenseSet; 82 public: 83 typedef typename MapTy::iterator::difference_type difference_type; 84 typedef ValueT value_type; 85 typedef value_type *pointer; 86 typedef value_type &reference; 87 typedef std::forward_iterator_tag iterator_category; 88 Iterator(const typename MapTy::iterator & i)89 Iterator(const typename MapTy::iterator &i) : I(i) {} 90 91 ValueT &operator*() { return I->getFirst(); } 92 ValueT *operator->() { return &I->getFirst(); } 93 94 Iterator& operator++() { ++I; return *this; } 95 bool operator==(const Iterator& X) const { return I == X.I; } 96 bool operator!=(const Iterator& X) const { return I != X.I; } 97 }; 98 99 class ConstIterator { 100 typename MapTy::const_iterator I; 101 friend class DenseSet; 102 public: 103 typedef typename MapTy::const_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 ConstIterator(const typename MapTy::const_iterator & i)109 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 110 111 const ValueT &operator*() { return I->getFirst(); } 112 const ValueT *operator->() { return &I->getFirst(); } 113 114 ConstIterator& operator++() { ++I; return *this; } 115 bool operator==(const ConstIterator& X) const { return I == X.I; } 116 bool operator!=(const ConstIterator& X) const { return I != X.I; } 117 }; 118 119 typedef Iterator iterator; 120 typedef ConstIterator const_iterator; 121 begin()122 iterator begin() { return Iterator(TheMap.begin()); } end()123 iterator end() { return Iterator(TheMap.end()); } 124 begin()125 const_iterator begin() const { return ConstIterator(TheMap.begin()); } end()126 const_iterator end() const { return ConstIterator(TheMap.end()); } 127 find(const ValueT & V)128 iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } 129 130 /// Alternative version of find() which allows a different, and possibly less 131 /// expensive, key type. 132 /// The DenseMapInfo is responsible for supplying methods 133 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type 134 /// used. 135 template <class LookupKeyT> find_as(const LookupKeyT & Val)136 iterator find_as(const LookupKeyT &Val) { 137 return Iterator(TheMap.find_as(Val)); 138 } 139 template <class LookupKeyT> find_as(const LookupKeyT & Val)140 const_iterator find_as(const LookupKeyT &Val) const { 141 return ConstIterator(TheMap.find_as(Val)); 142 } 143 erase(Iterator I)144 void erase(Iterator I) { return TheMap.erase(I.I); } erase(ConstIterator CI)145 void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 146 insert(const ValueT & V)147 std::pair<iterator, bool> insert(const ValueT &V) { 148 detail::DenseSetEmpty Empty; 149 return TheMap.insert(std::make_pair(V, Empty)); 150 } 151 152 // Range insertion of values. 153 template<typename InputIt> insert(InputIt I,InputIt E)154 void insert(InputIt I, InputIt E) { 155 for (; I != E; ++I) 156 insert(*I); 157 } 158 }; 159 160 } // end namespace llvm 161 162 #endif 163