blob: d699ad51ada4906c6e693ad12b8cd503d07dcc00 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the DenseSet class.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_DENSESET_H
#define LLVM_ADT_DENSESET_H
#include "llvm/ADT/DenseMap.h"
namespace llvm {
/// DenseSet - This implements a dense probed hash-table based set.
///
/// FIXME: This is currently implemented directly in terms of DenseMap, this
/// should be optimized later if there is a need.
template<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> >
class DenseSet {
typedef DenseMap<ValueT, char, ValueInfoT> MapTy;
MapTy TheMap;
public:
DenseSet(const DenseSet &Other) : TheMap(Other.TheMap) {}
explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
bool empty() const { return TheMap.empty(); }
unsigned size() const { return TheMap.size(); }
size_t getMemorySize() const { return TheMap.getMemorySize(); }
/// Grow the DenseSet so that it has at least Size buckets. Will not shrink
/// the Size of the set.
void resize(size_t Size) { TheMap.resize(Size); }
void clear() {
TheMap.clear();
}
bool count(const ValueT &V) const {
return TheMap.count(V);
}
bool erase(const ValueT &V) {
return TheMap.erase(V);
}
void swap(DenseSet& RHS) {
TheMap.swap(RHS.TheMap);
}
DenseSet &operator=(const DenseSet &RHS) {
TheMap = RHS.TheMap;
return *this;
}
// Iterators.
class Iterator {
typename MapTy::iterator I;
friend class DenseSet;
public:
typedef typename MapTy::iterator::difference_type difference_type;
typedef ValueT value_type;
typedef value_type *pointer;
typedef value_type &reference;
typedef std::forward_iterator_tag iterator_category;
Iterator(const typename MapTy::iterator &i) : I(i) {}
ValueT& operator*() { return I->first; }
ValueT* operator->() { return &I->first; }
Iterator& operator++() { ++I; return *this; }
bool operator==(const Iterator& X) const { return I == X.I; }
bool operator!=(const Iterator& X) const { return I != X.I; }
};
class ConstIterator {
typename MapTy::const_iterator I;
friend class DenseSet;
public:
typedef typename MapTy::const_iterator::difference_type difference_type;
typedef ValueT value_type;
typedef value_type *pointer;
typedef value_type &reference;
typedef std::forward_iterator_tag iterator_category;
ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
const ValueT& operator*() { return I->first; }
const ValueT* operator->() { return &I->first; }
ConstIterator& operator++() { ++I; return *this; }
bool operator==(const ConstIterator& X) const { return I == X.I; }
bool operator!=(const ConstIterator& X) const { return I != X.I; }
};
typedef Iterator iterator;
typedef ConstIterator const_iterator;
iterator begin() { return Iterator(TheMap.begin()); }
iterator end() { return Iterator(TheMap.end()); }
const_iterator begin() const { return ConstIterator(TheMap.begin()); }
const_iterator end() const { return ConstIterator(TheMap.end()); }
iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); }
void erase(Iterator I) { return TheMap.erase(I.I); }
void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
std::pair<iterator, bool> insert(const ValueT &V) {
return TheMap.insert(std::make_pair(V, 0));
}
// Range insertion of values.
template<typename InputIt>
void insert(InputIt I, InputIt E) {
for (; I != E; ++I)
insert(*I);
}
};
} // end namespace llvm
#endif
|
