1193323Sed//===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the DenseSet class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_DENSESET_H 15193323Sed#define LLVM_ADT_DENSESET_H 16193323Sed 17193323Sed#include "llvm/ADT/DenseMap.h" 18193323Sed 19193323Sednamespace llvm { 20193323Sed 21193323Sed/// DenseSet - This implements a dense probed hash-table based set. 22193323Sed/// 23193323Sed/// FIXME: This is currently implemented directly in terms of DenseMap, this 24193323Sed/// should be optimized later if there is a need. 25193323Sedtemplate<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> > 26193323Sedclass DenseSet { 27193323Sed typedef DenseMap<ValueT, char, ValueInfoT> MapTy; 28193323Sed MapTy TheMap; 29193323Sedpublic: 30193323Sed DenseSet(const DenseSet &Other) : TheMap(Other.TheMap) {} 31226633Sdim explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {} 32193323Sed 33193323Sed bool empty() const { return TheMap.empty(); } 34193323Sed unsigned size() const { return TheMap.size(); } 35249423Sdim size_t getMemorySize() const { return TheMap.getMemorySize(); } 36193323Sed 37249423Sdim /// Grow the DenseSet so that it has at least Size buckets. Will not shrink 38249423Sdim /// the Size of the set. 39218893Sdim void resize(size_t Size) { TheMap.resize(Size); } 40218893Sdim 41193323Sed void clear() { 42193323Sed TheMap.clear(); 43193323Sed } 44193323Sed 45193323Sed bool count(const ValueT &V) const { 46193323Sed return TheMap.count(V); 47193323Sed } 48193323Sed 49203954Srdivacky bool erase(const ValueT &V) { 50203954Srdivacky return TheMap.erase(V); 51193323Sed } 52193323Sed 53204961Srdivacky void swap(DenseSet& RHS) { 54204961Srdivacky TheMap.swap(RHS.TheMap); 55204961Srdivacky } 56204961Srdivacky 57193323Sed DenseSet &operator=(const DenseSet &RHS) { 58193323Sed TheMap = RHS.TheMap; 59193323Sed return *this; 60193323Sed } 61193323Sed 62193323Sed // Iterators. 63193323Sed 64193323Sed class Iterator { 65193323Sed typename MapTy::iterator I; 66212904Sdim friend class DenseSet; 67193323Sed public: 68204961Srdivacky typedef typename MapTy::iterator::difference_type difference_type; 69204961Srdivacky typedef ValueT value_type; 70204961Srdivacky typedef value_type *pointer; 71204961Srdivacky typedef value_type &reference; 72204961Srdivacky typedef std::forward_iterator_tag iterator_category; 73204961Srdivacky 74193323Sed Iterator(const typename MapTy::iterator &i) : I(i) {} 75193323Sed 76193323Sed ValueT& operator*() { return I->first; } 77193323Sed ValueT* operator->() { return &I->first; } 78193323Sed 79200581Srdivacky Iterator& operator++() { ++I; return *this; } 80193323Sed bool operator==(const Iterator& X) const { return I == X.I; } 81193323Sed bool operator!=(const Iterator& X) const { return I != X.I; } 82193323Sed }; 83193323Sed 84193323Sed class ConstIterator { 85193323Sed typename MapTy::const_iterator I; 86212904Sdim friend class DenseSet; 87193323Sed public: 88204961Srdivacky typedef typename MapTy::const_iterator::difference_type difference_type; 89204961Srdivacky typedef ValueT value_type; 90204961Srdivacky typedef value_type *pointer; 91204961Srdivacky typedef value_type &reference; 92204961Srdivacky typedef std::forward_iterator_tag iterator_category; 93204961Srdivacky 94193323Sed ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 95193323Sed 96193323Sed const ValueT& operator*() { return I->first; } 97193323Sed const ValueT* operator->() { return &I->first; } 98193323Sed 99200581Srdivacky ConstIterator& operator++() { ++I; return *this; } 100193323Sed bool operator==(const ConstIterator& X) const { return I == X.I; } 101193323Sed bool operator!=(const ConstIterator& X) const { return I != X.I; } 102193323Sed }; 103193323Sed 104193323Sed typedef Iterator iterator; 105193323Sed typedef ConstIterator const_iterator; 106193323Sed 107193323Sed iterator begin() { return Iterator(TheMap.begin()); } 108193323Sed iterator end() { return Iterator(TheMap.end()); } 109193323Sed 110193323Sed const_iterator begin() const { return ConstIterator(TheMap.begin()); } 111193323Sed const_iterator end() const { return ConstIterator(TheMap.end()); } 112193323Sed 113212904Sdim iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } 114212904Sdim void erase(Iterator I) { return TheMap.erase(I.I); } 115212904Sdim void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 116212904Sdim 117193323Sed std::pair<iterator, bool> insert(const ValueT &V) { 118193323Sed return TheMap.insert(std::make_pair(V, 0)); 119193323Sed } 120193323Sed 121193323Sed // Range insertion of values. 122193323Sed template<typename InputIt> 123193323Sed void insert(InputIt I, InputIt E) { 124193323Sed for (; I != E; ++I) 125193323Sed insert(*I); 126193323Sed } 127193323Sed}; 128193323Sed 129193323Sed} // end namespace llvm 130193323Sed 131193323Sed#endif 132