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:
getFirst()30   KeyT &getFirst() { return key; }
getFirst()31   const KeyT &getFirst() const { return key; }
getSecond()32   DenseSetEmpty &getSecond() { return *this; }
getSecond()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 public:
46   typedef ValueT key_type;
47   typedef ValueT value_type;
48   typedef unsigned size_type;
49 
TheMap(NumInitBuckets)50   explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
51 
empty()52   bool empty() const { return TheMap.empty(); }
size()53   size_type size() const { return TheMap.size(); }
getMemorySize()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.
resize(size_t Size)58   void resize(size_t Size) { TheMap.resize(Size); }
59 
clear()60   void clear() {
61     TheMap.clear();
62   }
63 
64   /// Return 1 if the specified key is in the set, 0 otherwise.
count(const ValueT & V)65   size_type count(const ValueT &V) const {
66     return TheMap.count(V);
67   }
68 
erase(const ValueT & V)69   bool erase(const ValueT &V) {
70     return TheMap.erase(V);
71   }
72 
swap(DenseSet & RHS)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 
Iterator(const typename MapTy::iterator & i)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 
ConstIterator(const typename MapTy::const_iterator & i)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 
begin()122   iterator begin() { return Iterator(TheMap.begin()); }
end()123   iterator end() { return Iterator(TheMap.end()); }
124 
begin()125   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
end()126   const_iterator end() const { return ConstIterator(TheMap.end()); }
127 
find(const ValueT & V)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>
find_as(const LookupKeyT & Val)136   iterator find_as(const LookupKeyT &Val) {
137     return Iterator(TheMap.find_as(Val));
138   }
139   template <class LookupKeyT>
find_as(const LookupKeyT & Val)140   const_iterator find_as(const LookupKeyT &Val) const {
141     return ConstIterator(TheMap.find_as(Val));
142   }
143 
erase(Iterator I)144   void erase(Iterator I) { return TheMap.erase(I.I); }
erase(ConstIterator CI)145   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
146 
insert(const ValueT & V)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>
insert(InputIt I,InputIt E)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
163