1 | //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | // |

7 | //===----------------------------------------------------------------------===// |

8 | // |

9 | // This file defines the SmallSet class. |

10 | // |

11 | //===----------------------------------------------------------------------===// |

12 | |

13 | #ifndef LLVM_ADT_SMALLSET_H |

14 | #define LLVM_ADT_SMALLSET_H |

15 | |

16 | #include "llvm/ADT/None.h" |

17 | #include "llvm/ADT/SmallPtrSet.h" |

18 | #include "llvm/ADT/SmallVector.h" |

19 | #include "llvm/ADT/iterator.h" |

20 | #include "llvm/Support/Compiler.h" |

21 | #include "llvm/Support/type_traits.h" |

22 | #include <cstddef> |

23 | #include <functional> |

24 | #include <set> |

25 | #include <type_traits> |

26 | #include <utility> |

27 | |

28 | namespace llvm { |

29 | |

30 | /// SmallSetIterator - This class implements a const_iterator for SmallSet by |

31 | /// delegating to the underlying SmallVector or Set iterators. |

32 | template <typename T, unsigned N, typename C> |

33 | class SmallSetIterator |

34 | : public iterator_facade_base<SmallSetIterator<T, N, C>, |

35 | std::forward_iterator_tag, T> { |

36 | private: |

37 | using SetIterTy = typename std::set<T, C>::const_iterator; |

38 | using VecIterTy = typename SmallVector<T, N>::const_iterator; |

39 | using SelfTy = SmallSetIterator<T, N, C>; |

40 | |

41 | /// Iterators to the parts of the SmallSet containing the data. They are set |

42 | /// depending on isSmall. |

43 | union { |

44 | SetIterTy SetIter; |

45 | VecIterTy VecIter; |

46 | }; |

47 | |

48 | bool isSmall; |

49 | |

50 | public: |

51 | SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {} |

52 | |

53 | SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {} |

54 | |

55 | // Spell out destructor, copy/move constructor and assignment operators for |

56 | // MSVC STL, where set<T>::const_iterator is not trivially copy constructible. |

57 | ~SmallSetIterator() { |

58 | if (isSmall) |

59 | VecIter.~VecIterTy(); |

60 | else |

61 | SetIter.~SetIterTy(); |

62 | } |

63 | |

64 | SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) { |

65 | if (isSmall) |

66 | VecIter = Other.VecIter; |

67 | else |

68 | // Use placement new, to make sure SetIter is properly constructed, even |

69 | // if it is not trivially copy-able (e.g. in MSVC). |

70 | new (&SetIter) SetIterTy(Other.SetIter); |

71 | } |

72 | |

73 | SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) { |

74 | if (isSmall) |

75 | VecIter = std::move(Other.VecIter); |

76 | else |

77 | // Use placement new, to make sure SetIter is properly constructed, even |

78 | // if it is not trivially copy-able (e.g. in MSVC). |

79 | new (&SetIter) SetIterTy(std::move(Other.SetIter)); |

80 | } |

81 | |

82 | SmallSetIterator& operator=(const SmallSetIterator& Other) { |

83 | // Call destructor for SetIter, so it gets properly destroyed if it is |

84 | // not trivially destructible in case we are setting VecIter. |

85 | if (!isSmall) |

86 | SetIter.~SetIterTy(); |

87 | |

88 | isSmall = Other.isSmall; |

89 | if (isSmall) |

90 | VecIter = Other.VecIter; |

91 | else |

92 | new (&SetIter) SetIterTy(Other.SetIter); |

93 | return *this; |

94 | } |

95 | |

96 | SmallSetIterator& operator=(SmallSetIterator&& Other) { |

97 | // Call destructor for SetIter, so it gets properly destroyed if it is |

98 | // not trivially destructible in case we are setting VecIter. |

99 | if (!isSmall) |

100 | SetIter.~SetIterTy(); |

101 | |

102 | isSmall = Other.isSmall; |

103 | if (isSmall) |

104 | VecIter = std::move(Other.VecIter); |

105 | else |

106 | new (&SetIter) SetIterTy(std::move(Other.SetIter)); |

107 | return *this; |

108 | } |

109 | |

110 | bool operator==(const SmallSetIterator &RHS) const { |

111 | if (isSmall != RHS.isSmall) |

112 | return false; |

113 | if (isSmall) |

114 | return VecIter == RHS.VecIter; |

115 | return SetIter == RHS.SetIter; |

116 | } |

117 | |

118 | SmallSetIterator &operator++() { // Preincrement |

119 | if (isSmall) |

120 | VecIter++; |

121 | else |

122 | SetIter++; |

123 | return *this; |

124 | } |

125 | |

126 | const T &operator*() const { return isSmall ? *VecIter : *SetIter; } |

127 | }; |

128 | |

129 | /// SmallSet - This maintains a set of unique values, optimizing for the case |

130 | /// when the set is small (less than N). In this case, the set can be |

131 | /// maintained with no mallocs. If the set gets large, we expand to using an |

132 | /// std::set to maintain reasonable lookup times. |

133 | template <typename T, unsigned N, typename C = std::less<T>> |

134 | class SmallSet { |

135 | /// Use a SmallVector to hold the elements here (even though it will never |

136 | /// reach its 'large' stage) to avoid calling the default ctors of elements |

137 | /// we will never use. |

138 | SmallVector<T, N> Vector; |

139 | std::set<T, C> Set; |

140 | |

141 | using VIterator = typename SmallVector<T, N>::const_iterator; |

142 | using mutable_iterator = typename SmallVector<T, N>::iterator; |

143 | |

144 | // In small mode SmallPtrSet uses linear search for the elements, so it is |

145 | // not a good idea to choose this value too high. You may consider using a |

146 | // DenseSet<> instead if you expect many elements in the set. |

147 | static_assert(N <= 32, "N should be small"); |

148 | |

149 | public: |

150 | using size_type = size_t; |

151 | using const_iterator = SmallSetIterator<T, N, C>; |

152 | |

153 | SmallSet() = default; |

154 | |

155 | LLVM_NODISCARD bool empty() const { |

156 | return Vector.empty() && Set.empty(); |

157 | } |

158 | |

159 | size_type size() const { |

160 | return isSmall() ? Vector.size() : Set.size(); |

161 | } |

162 | |

163 | /// count - Return 1 if the element is in the set, 0 otherwise. |

164 | size_type count(const T &V) const { |

165 | if (isSmall()) { |

166 | // Since the collection is small, just do a linear search. |

167 | return vfind(V) == Vector.end() ? 0 : 1; |

168 | } else { |

169 | return Set.count(V); |

170 | } |

171 | } |

172 | |

173 | /// insert - Insert an element into the set if it isn't already there. |

174 | /// Returns true if the element is inserted (it was not in the set before). |

175 | /// The first value of the returned pair is unused and provided for |

176 | /// partial compatibility with the standard library self-associative container |

177 | /// concept. |

178 | // FIXME: Add iterators that abstract over the small and large form, and then |

179 | // return those here. |

180 | std::pair<NoneType, bool> insert(const T &V) { |

181 | if (!isSmall()) |

182 | return std::make_pair(None, Set.insert(V).second); |

183 | |

184 | VIterator I = vfind(V); |

185 | if (I != Vector.end()) // Don't reinsert if it already exists. |

186 | return std::make_pair(None, false); |

187 | if (Vector.size() < N) { |

188 | Vector.push_back(V); |

189 | return std::make_pair(None, true); |

190 | } |

191 | |

192 | // Otherwise, grow from vector to set. |

193 | while (!Vector.empty()) { |

194 | Set.insert(Vector.back()); |

195 | Vector.pop_back(); |

196 | } |

197 | Set.insert(V); |

198 | return std::make_pair(None, true); |

199 | } |

200 | |

201 | template <typename IterT> |

202 | void insert(IterT I, IterT E) { |

203 | for (; I != E; ++I) |

204 | insert(*I); |

205 | } |

206 | |

207 | bool erase(const T &V) { |

208 | if (!isSmall()) |

209 | return Set.erase(V); |

210 | for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) |

211 | if (*I == V) { |

212 | Vector.erase(I); |

213 | return true; |

214 | } |

215 | return false; |

216 | } |

217 | |

218 | void clear() { |

219 | Vector.clear(); |

220 | Set.clear(); |

221 | } |

222 | |

223 | const_iterator begin() const { |

224 | if (isSmall()) |

225 | return {Vector.begin()}; |

226 | return {Set.begin()}; |

227 | } |

228 | |

229 | const_iterator end() const { |

230 | if (isSmall()) |

231 | return {Vector.end()}; |

232 | return {Set.end()}; |

233 | } |

234 | |

235 | /// Check if the SmallSet contains the given element. |

236 | bool contains(const T &V) const { |

237 | if (isSmall()) |

238 | return vfind(V) != Vector.end(); |

239 | return Set.find(V) != Set.end(); |

240 | } |

241 | |

242 | private: |

243 | bool isSmall() const { return Set.empty(); } |

244 | |

245 | VIterator vfind(const T &V) const { |

246 | for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) |

247 | if (*I == V) |

248 | return I; |

249 | return Vector.end(); |

250 | } |

251 | }; |

252 | |

253 | /// If this set is of pointer values, transparently switch over to using |

254 | /// SmallPtrSet for performance. |

255 | template <typename PointeeType, unsigned N> |

256 | class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; |

257 | |

258 | /// Equality comparison for SmallSet. |

259 | /// |

260 | /// Iterates over elements of LHS confirming that each element is also a member |

261 | /// of RHS, and that RHS contains no additional values. |

262 | /// Equivalent to N calls to RHS.count. |

263 | /// For small-set mode amortized complexity is O(N^2) |

264 | /// For large-set mode amortized complexity is linear, worst case is O(N^2) (if |

265 | /// every hash collides). |

266 | template <typename T, unsigned LN, unsigned RN, typename C> |

267 | bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { |

268 | if (LHS.size() != RHS.size()) |

269 | return false; |

270 | |

271 | // All elements in LHS must also be in RHS |

272 | return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); }); |

273 | } |

274 | |

275 | /// Inequality comparison for SmallSet. |

276 | /// |

277 | /// Equivalent to !(LHS == RHS). See operator== for performance notes. |

278 | template <typename T, unsigned LN, unsigned RN, typename C> |

279 | bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { |

280 | return !(LHS == RHS); |

281 | } |

282 | |

283 | } // end namespace llvm |

284 | |

285 | #endif // LLVM_ADT_SMALLSET_H |

286 |