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