include/llvm/ADT/DenseSet.h

   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 } // namespace detail
  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
  50   explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
  51
  52   bool empty() const { return TheMap.empty(); }
  53   size_type size() const { return TheMap.size(); }
  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.
  58   void resize(size_t Size) { TheMap.resize(Size); }
  59
  60   void clear() {
  61     TheMap.clear();
  62   }
  63
  64   /// Return 1 if the specified key is in the set, 0 otherwise.
  65   size_type count(const ValueT &V) const {
  66     return TheMap.count(V);
  67   }
  68
  69   bool erase(const ValueT &V) {
  70     return TheMap.erase(V);
  71   }
  72
  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
  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
 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
 122   iterator begin() { return Iterator(TheMap.begin()); }
 123   iterator end() { return Iterator(TheMap.end()); }
 124
 125   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
 126   const_iterator end() const { return ConstIterator(TheMap.end()); }
 127
 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>
 136   iterator find_as(const LookupKeyT &Val) {
 137     return Iterator(TheMap.find_as(Val));
 138   }
 139   template <class LookupKeyT>
 140   const_iterator find_as(const LookupKeyT &Val) const {
 141     return ConstIterator(TheMap.find_as(Val));
 142   }
 143
 144   void erase(Iterator I) { return TheMap.erase(I.I); }
 145   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 146
 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>
 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