DenseSet.h revision ea33c8fed681d103f159e7e80591437c726576ec
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) {} 31be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner explicit DenseSet(unsigned NumInitBuckets = 64) : TheMap(NumInitBuckets) {} 32be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 33be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner bool empty() const { return TheMap.empty(); } 34ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek unsigned size() const { return TheMap.size(); } 35be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 36be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner void clear() { 37be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner TheMap.clear(); 38be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 39be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 40bca98326b6fd311c917fc2407b4b05d7c90f31b2Chris Lattner bool count(const ValueT &V) const { 41be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner return TheMap.count(V); 42be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 43be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 44be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner void insert(const ValueT &V) { 45be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner TheMap[V] = 0; 46be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 47be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 48be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner void erase(const ValueT &V) { 49be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner TheMap.erase(V); 50be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 51be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 52be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner DenseSet &operator=(const DenseSet &RHS) { 53be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner TheMap = RHS.TheMap; 54be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner return *this; 55be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner } 56ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 57ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek // Iterators. 58ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 59ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek class Iterator { 60ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typename MapTy::iterator I; 61ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek public: 62ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek Iterator(const typename MapTy::iterator &i) : I(i) {} 63ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 64ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ValueT& operator*() { return I->first; } 65ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ValueT* operator->() { return &I->first; } 66ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 67ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek Iterator& operator++() { ++I; return *this; }; 68ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek bool operator==(const Iterator& X) const { return I == X.I; } 69ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek }; 70ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 71ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek class ConstIterator { 72ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typename MapTy::const_iterator I; 73ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek public: 74ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 75ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 76ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const ValueT& operator*() { return I->first; } 77ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const ValueT* operator->() { return &I->first; } 78ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 79ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek ConstIterator& operator++() { ++I; return *this; }; 80ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek bool operator==(const ConstIterator& X) const { return I == X.I; } 81ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek }; 82ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 83ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typedef Iterator iterator; 84ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek typedef ConstIterator const_iterator; 85ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 86ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek iterator begin() { return Iterator(TheMap.begin()); } 87ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek iterator end() { return Iterator(TheMap.end()); } 88ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek 89ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const_iterator begin() const { return ConstIterator(TheMap.begin()); } 90ea33c8fed681d103f159e7e80591437c726576ecTed Kremenek const_iterator end() const { return ConstIterator(TheMap.end()); } 91be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner}; 92be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 93be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner} // end namespace llvm 94be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner 95be207738d3b4bbfc9da11025ebbf10f4f12216b9Chris Lattner#endif 96