Skip to content

Commit 6698f9b

Browse files
fhahnfhahn
committedJul 24, 2018
Recommit r334887: [SmallSet] Add SmallSetIterator.
Updated to make sure we properly construct/destroy SetIter if it has a non-trivial ctors/dtors, like in MSVC. llvm-svn: 337818
1 parent e95f4bf commit 6698f9b

File tree

2 files changed

+194
-3
lines changed

2 files changed

+194
-3
lines changed
 

‎llvm/include/llvm/ADT/SmallSet.h

Lines changed: 115 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -17,21 +17,120 @@
1717
#include "llvm/ADT/None.h"
1818
#include "llvm/ADT/SmallPtrSet.h"
1919
#include "llvm/ADT/SmallVector.h"
20+
#include "llvm/ADT/iterator.h"
2021
#include "llvm/Support/Compiler.h"
22+
#include "llvm/Support/type_traits.h"
2123
#include <cstddef>
2224
#include <functional>
2325
#include <set>
26+
#include <type_traits>
2427
#include <utility>
2528

2629
namespace llvm {
2730

31+
/// SmallSetIterator - This class implements a const_iterator for SmallSet by
32+
/// delegating to the underlying SmallVector or Set iterators.
33+
template <typename T, unsigned N, typename C>
34+
class SmallSetIterator
35+
: public iterator_facade_base<SmallSetIterator<T, N, C>,
36+
std::forward_iterator_tag, T> {
37+
private:
38+
using SetIterTy = typename std::set<T, C>::const_iterator;
39+
using VecIterTy = typename SmallVector<T, N>::const_iterator;
40+
using SelfTy = SmallSetIterator<T, N, C>;
41+
42+
/// Iterators to the parts of the SmallSet containing the data. They are set
43+
/// depending on isSmall.
44+
union {
45+
SetIterTy SetIter;
46+
VecIterTy VecIter;
47+
};
48+
49+
bool isSmall;
50+
51+
public:
52+
SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
53+
54+
SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {}
55+
56+
// Spell out destructor, copy/move constructor and assignment operators for
57+
// MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
58+
~SmallSetIterator() {
59+
if (isSmall)
60+
VecIter.~VecIterTy();
61+
else
62+
SetIter.~SetIterTy();
63+
}
64+
65+
SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) {
66+
if (isSmall)
67+
VecIter = Other.VecIter;
68+
else
69+
// Use placement new, to make sure SetIter is properly constructed, even
70+
// if it is not trivially copy-able (e.g. in MSVC).
71+
new (&SetIter) SetIterTy(Other.SetIter);
72+
}
73+
74+
SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) {
75+
if (isSmall)
76+
VecIter = std::move(Other.VecIter);
77+
else
78+
// Use placement new, to make sure SetIter is properly constructed, even
79+
// if it is not trivially copy-able (e.g. in MSVC).
80+
new (&SetIter) SetIterTy(std::move(Other.SetIter));
81+
}
82+
83+
SmallSetIterator& operator=(const SmallSetIterator& Other) {
84+
// Call destructor for SetIter, so it gets properly destroyed if it is
85+
// not trivially destructible in case we are setting VecIter.
86+
if (!isSmall)
87+
SetIter.~SetIterTy();
88+
89+
isSmall = Other.isSmall;
90+
if (isSmall)
91+
VecIter = Other.VecIter;
92+
else
93+
new (&SetIter) SetIterTy(Other.SetIter);
94+
return *this;
95+
}
96+
97+
SmallSetIterator& operator=(SmallSetIterator&& Other) {
98+
// Call destructor for SetIter, so it gets properly destroyed if it is
99+
// not trivially destructible in case we are setting VecIter.
100+
if (!isSmall)
101+
SetIter.~SetIterTy();
102+
103+
isSmall = Other.isSmall;
104+
if (isSmall)
105+
VecIter = std::move(Other.VecIter);
106+
else
107+
new (&SetIter) SetIterTy(std::move(Other.SetIter));
108+
return *this;
109+
}
110+
111+
bool operator==(const SmallSetIterator &RHS) const {
112+
if (isSmall != RHS.isSmall)
113+
return false;
114+
if (isSmall)
115+
return VecIter == RHS.VecIter;
116+
return SetIter == RHS.SetIter;
117+
}
118+
119+
SmallSetIterator &operator++() { // Preincrement
120+
if (isSmall)
121+
VecIter++;
122+
else
123+
SetIter++;
124+
return *this;
125+
}
126+
127+
const T &operator*() const { return isSmall ? *VecIter : *SetIter; }
128+
};
129+
28130
/// SmallSet - This maintains a set of unique values, optimizing for the case
29131
/// when the set is small (less than N). In this case, the set can be
30132
/// maintained with no mallocs. If the set gets large, we expand to using an
31133
/// std::set to maintain reasonable lookup times.
32-
///
33-
/// Note that this set does not provide a way to iterate over members in the
34-
/// set.
35134
template <typename T, unsigned N, typename C = std::less<T>>
36135
class SmallSet {
37136
/// Use a SmallVector to hold the elements here (even though it will never
@@ -50,6 +149,7 @@ class SmallSet {
50149

51150
public:
52151
using size_type = size_t;
152+
using const_iterator = SmallSetIterator<T, N, C>;
53153

54154
SmallSet() = default;
55155

@@ -121,6 +221,18 @@ class SmallSet {
121221
Set.clear();
122222
}
123223

224+
const_iterator begin() const {
225+
if (isSmall())
226+
return {Vector.begin()};
227+
return {Set.begin()};
228+
}
229+
230+
const_iterator end() const {
231+
if (isSmall())
232+
return {Vector.end()};
233+
return {Set.end()};
234+
}
235+
124236
private:
125237
bool isSmall() const { return Set.empty(); }
126238

‎llvm/unittests/ADT/SmallSetTest.cpp

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313

1414
#include "llvm/ADT/SmallSet.h"
1515
#include "gtest/gtest.h"
16+
#include <string>
1617

1718
using namespace llvm;
1819

@@ -68,3 +69,81 @@ TEST(SmallSetTest, Erase) {
6869

6970
EXPECT_EQ(0u, s1.count(8));
7071
}
72+
73+
TEST(SmallSetTest, IteratorInt) {
74+
SmallSet<int, 4> s1;
75+
76+
// Test the 'small' case.
77+
for (int i = 0; i < 3; i++)
78+
s1.insert(i);
79+
80+
std::vector<int> V(s1.begin(), s1.end());
81+
// Make sure the elements are in the expected order.
82+
std::sort(V.begin(), V.end());
83+
for (int i = 0; i < 3; i++)
84+
EXPECT_EQ(i, V[i]);
85+
86+
// Test the 'big' case by adding a few more elements to switch to std::set
87+
// internally.
88+
for (int i = 3; i < 6; i++)
89+
s1.insert(i);
90+
91+
V.assign(s1.begin(), s1.end());
92+
// Make sure the elements are in the expected order.
93+
std::sort(V.begin(), V.end());
94+
for (int i = 0; i < 6; i++)
95+
EXPECT_EQ(i, V[i]);
96+
}
97+
98+
TEST(SmallSetTest, IteratorString) {
99+
// Test SmallSetIterator for SmallSet with a type with non-trivial
100+
// ctors/dtors.
101+
SmallSet<std::string, 2> s1;
102+
103+
s1.insert("str 1");
104+
s1.insert("str 2");
105+
s1.insert("str 1");
106+
107+
std::vector<std::string> V(s1.begin(), s1.end());
108+
std::sort(V.begin(), V.end());
109+
EXPECT_EQ(2u, s1.size());
110+
EXPECT_EQ("str 1", V[0]);
111+
EXPECT_EQ("str 2", V[1]);
112+
113+
s1.insert("str 4");
114+
s1.insert("str 0");
115+
s1.insert("str 4");
116+
117+
V.assign(s1.begin(), s1.end());
118+
// Make sure the elements are in the expected order.
119+
std::sort(V.begin(), V.end());
120+
EXPECT_EQ(4u, s1.size());
121+
EXPECT_EQ("str 0", V[0]);
122+
EXPECT_EQ("str 1", V[1]);
123+
EXPECT_EQ("str 2", V[2]);
124+
EXPECT_EQ("str 4", V[3]);
125+
}
126+
127+
TEST(SmallSetTest, IteratorIncMoveCopy) {
128+
// Test SmallSetIterator for SmallSet with a type with non-trivial
129+
// ctors/dtors.
130+
SmallSet<std::string, 2> s1;
131+
132+
s1.insert("str 1");
133+
s1.insert("str 2");
134+
135+
auto Iter = s1.begin();
136+
EXPECT_EQ("str 1", *Iter);
137+
++Iter;
138+
EXPECT_EQ("str 2", *Iter);
139+
140+
s1.insert("str 4");
141+
s1.insert("str 0");
142+
auto Iter2 = s1.begin();
143+
Iter = std::move(Iter2);
144+
EXPECT_EQ("str 0", *Iter);
145+
146+
auto Iter3 = s1.end();
147+
Iter3 = Iter2;
148+
EXPECT_EQ(Iter3, Iter2);
149+
}

0 commit comments

Comments
 (0)