1be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner//===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===// 2be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// 3be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// The LLVM Compiler Infrastructure 4be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// 8be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner//===----------------------------------------------------------------------===// 9be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// 10be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// This file defines the DenseSet class. 11be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner// 12be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner//===----------------------------------------------------------------------===// 13be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 14be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner#ifndef LLVM_ADT_DENSESET_H 15be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner#define LLVM_ADT_DENSESET_H 16be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 17be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner#include "llvm/ADT/DenseMap.h" 18be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 19be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattnernamespace llvm { 20be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 21be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner/// DenseSet - This implements a dense probed hash-table based set. 22be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner/// 23be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner/// FIXME: This is currently implemented directly in terms of DenseMap, this 24be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner/// should be optimized later if there is a need. 25be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattnertemplate<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> > 26be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattnerclass DenseSet { 27ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typedef DenseMap<ValueT, char, ValueInfoT> MapTy; 28ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek MapTy TheMap; 29be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattnerpublic: 30be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner DenseSet(const DenseSet &Other) : TheMap(Other.TheMap) {} 315333658df7acba70664417c3916c003d0c5fa59fBenjamin Kramer explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {} 323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 33be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner bool empty() const { return TheMap.empty(); } 343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman unsigned size() const { return TheMap.size(); } 353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 36989e7c4d0f042e8ed4f1cc4b0c1fa59b8a1e7d59Nick Lewycky /// Grow the denseset so that it has at least Size buckets. Does not shrink 37989e7c4d0f042e8ed4f1cc4b0c1fa59b8a1e7d59Nick Lewycky void resize(size_t Size) { TheMap.resize(Size); } 38989e7c4d0f042e8ed4f1cc4b0c1fa59b8a1e7d59Nick Lewycky 39be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner void clear() { 40be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner TheMap.clear(); 41be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43bca98326b6fd311c917fc2407b4b05d7c90f31b2Chris Lattner bool count(const ValueT &V) const { 44be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner return TheMap.count(V); 45be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4700f488012c6c44bc6ee35a3078a0063e10f152e3Dan Gohman bool erase(const ValueT &V) { 4800f488012c6c44bc6ee35a3078a0063e10f152e3Dan Gohman return TheMap.erase(V); 49be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 51ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth void swap(DenseSet& RHS) { 52ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth TheMap.swap(RHS.TheMap); 53ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth } 54ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth 55be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner DenseSet &operator=(const DenseSet &RHS) { 56be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner TheMap = RHS.TheMap; 57be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner return *this; 58be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 60ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek // Iterators. 613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 62ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek class Iterator { 63ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typename MapTy::iterator I; 64cf85c9612959e7326ddba9d4fb0a997c155b74c1Owen Anderson friend class DenseSet; 65ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek public: 66ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef typename MapTy::iterator::difference_type difference_type; 67ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef ValueT value_type; 68ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef value_type *pointer; 69ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef value_type &reference; 70ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef std::forward_iterator_tag iterator_category; 71ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth 72ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek Iterator(const typename MapTy::iterator &i) : I(i) {} 733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 74ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ValueT& operator*() { return I->first; } 75ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ValueT* operator->() { return &I->first; } 763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 779000242cca4431a8dd09c83459d56f164294582cChris Lattner Iterator& operator++() { ++I; return *this; } 78ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek bool operator==(const Iterator& X) const { return I == X.I; } 7913f7a405082ad154394b2f85e297668cf4ec8292Ted Kremenek bool operator!=(const Iterator& X) const { return I != X.I; } 80ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek }; 813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 82ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek class ConstIterator { 83ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typename MapTy::const_iterator I; 84cf85c9612959e7326ddba9d4fb0a997c155b74c1Owen Anderson friend class DenseSet; 85ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek public: 86ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef typename MapTy::const_iterator::difference_type difference_type; 87ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef ValueT value_type; 88ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef value_type *pointer; 89ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef value_type &reference; 90ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth typedef std::forward_iterator_tag iterator_category; 91ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth 92ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 94ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const ValueT& operator*() { return I->first; } 95ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const ValueT* operator->() { return &I->first; } 963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 97e854273892a5fed9a797ed58e472cca2e95fcc33Daniel Dunbar ConstIterator& operator++() { ++I; return *this; } 98ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek bool operator==(const ConstIterator& X) const { return I == X.I; } 9913f7a405082ad154394b2f85e297668cf4ec8292Ted Kremenek bool operator!=(const ConstIterator& X) const { return I != X.I; } 100ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek }; 1013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 102ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typedef Iterator iterator; 103ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typedef ConstIterator const_iterator; 1043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 105ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek iterator begin() { return Iterator(TheMap.begin()); } 106ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek iterator end() { return Iterator(TheMap.end()); } 1073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 108ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const_iterator begin() const { return ConstIterator(TheMap.begin()); } 109ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const_iterator end() const { return ConstIterator(TheMap.end()); } 1106b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman 111cf85c9612959e7326ddba9d4fb0a997c155b74c1Owen Anderson iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } 112e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(Iterator I) { return TheMap.erase(I.I); } 113e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 114cf85c9612959e7326ddba9d4fb0a997c155b74c1Owen Anderson 1156b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const ValueT &V) { 1166b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return TheMap.insert(std::make_pair(V, 0)); 1176b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman } 118dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner 119dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner // Range insertion of values. 120dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner template<typename InputIt> 121dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner void insert(InputIt I, InputIt E) { 122dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner for (; I != E; ++I) 123dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner insert(*I); 124dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner } 125be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner}; 126be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 127be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner} // end namespace llvm 128be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 129be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner#endif 130