1 | //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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 implements a set that has insertion order iteration |

10 | // characteristics. This is useful for keeping a set of things that need to be |

11 | // visited later but in a deterministic order (insertion order). The interface |

12 | // is purposefully minimal. |

13 | // |

14 | // This file defines SetVector and SmallSetVector, which performs no allocations |

15 | // if the SetVector has less than a certain number of elements. |

16 | // |

17 | //===----------------------------------------------------------------------===// |

18 | |

19 | #ifndef LLVM_ADT_SETVECTOR_H |

20 | #define LLVM_ADT_SETVECTOR_H |

21 | |

22 | #include "llvm/ADT/ArrayRef.h" |

23 | #include "llvm/ADT/DenseSet.h" |

24 | #include "llvm/ADT/STLExtras.h" |

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

26 | #include <algorithm> |

27 | #include <cassert> |

28 | #include <iterator> |

29 | #include <vector> |

30 | |

31 | namespace llvm { |

32 | |

33 | /// A vector that has set insertion semantics. |

34 | /// |

35 | /// This adapter class provides a way to keep a set of things that also has the |

36 | /// property of a deterministic iteration order. The order of iteration is the |

37 | /// order of insertion. |

38 | template <typename T, typename Vector = std::vector<T>, |

39 | typename Set = DenseSet<T>> |

40 | class SetVector { |

41 | public: |

42 | using value_type = T; |

43 | using key_type = T; |

44 | using reference = T&; |

45 | using const_reference = const T&; |

46 | using set_type = Set; |

47 | using vector_type = Vector; |

48 | using iterator = typename vector_type::const_iterator; |

49 | using const_iterator = typename vector_type::const_iterator; |

50 | using reverse_iterator = typename vector_type::const_reverse_iterator; |

51 | using const_reverse_iterator = typename vector_type::const_reverse_iterator; |

52 | using size_type = typename vector_type::size_type; |

53 | |

54 | /// Construct an empty SetVector |

55 | SetVector() = default; |

56 | |

57 | /// Initialize a SetVector with a range of elements |

58 | template<typename It> |

59 | SetVector(It Start, It End) { |

60 | insert(Start, End); |

61 | } |

62 | |

63 | ArrayRef<T> getArrayRef() const { return vector_; } |

64 | |

65 | /// Clear the SetVector and return the underlying vector. |

66 | Vector takeVector() { |

67 | set_.clear(); |

68 | return std::move(vector_); |

69 | } |

70 | |

71 | /// Determine if the SetVector is empty or not. |

72 | bool empty() const { |

73 | return vector_.empty(); |

74 | } |

75 | |

76 | /// Determine the number of elements in the SetVector. |

77 | size_type size() const { |

78 | return vector_.size(); |

79 | } |

80 | |

81 | /// Get an iterator to the beginning of the SetVector. |

82 | iterator begin() { |

83 | return vector_.begin(); |

84 | } |

85 | |

86 | /// Get a const_iterator to the beginning of the SetVector. |

87 | const_iterator begin() const { |

88 | return vector_.begin(); |

89 | } |

90 | |

91 | /// Get an iterator to the end of the SetVector. |

92 | iterator end() { |

93 | return vector_.end(); |

94 | } |

95 | |

96 | /// Get a const_iterator to the end of the SetVector. |

97 | const_iterator end() const { |

98 | return vector_.end(); |

99 | } |

100 | |

101 | /// Get an reverse_iterator to the end of the SetVector. |

102 | reverse_iterator rbegin() { |

103 | return vector_.rbegin(); |

104 | } |

105 | |

106 | /// Get a const_reverse_iterator to the end of the SetVector. |

107 | const_reverse_iterator rbegin() const { |

108 | return vector_.rbegin(); |

109 | } |

110 | |

111 | /// Get a reverse_iterator to the beginning of the SetVector. |

112 | reverse_iterator rend() { |

113 | return vector_.rend(); |

114 | } |

115 | |

116 | /// Get a const_reverse_iterator to the beginning of the SetVector. |

117 | const_reverse_iterator rend() const { |

118 | return vector_.rend(); |

119 | } |

120 | |

121 | /// Return the first element of the SetVector. |

122 | const T &front() const { |

123 | assert(!empty() && "Cannot call front() on empty SetVector!"); |

124 | return vector_.front(); |

125 | } |

126 | |

127 | /// Return the last element of the SetVector. |

128 | const T &back() const { |

129 | assert(!empty() && "Cannot call back() on empty SetVector!"); |

130 | return vector_.back(); |

131 | } |

132 | |

133 | /// Index into the SetVector. |

134 | const_reference operator[](size_type n) const { |

135 | assert(n < vector_.size() && "SetVector access out of range!"); |

136 | return vector_[n]; |

137 | } |

138 | |

139 | /// Insert a new element into the SetVector. |

140 | /// \returns true if the element was inserted into the SetVector. |

141 | bool insert(const value_type &X) { |

142 | bool result = set_.insert(X).second; |

143 | if (result) |

144 | vector_.push_back(X); |

145 | return result; |

146 | } |

147 | |

148 | /// Insert a range of elements into the SetVector. |

149 | template<typename It> |

150 | void insert(It Start, It End) { |

151 | for (; Start != End; ++Start) |

152 | if (set_.insert(*Start).second) |

153 | vector_.push_back(*Start); |

154 | } |

155 | |

156 | /// Remove an item from the set vector. |

157 | bool remove(const value_type& X) { |

158 | if (set_.erase(X)) { |

159 | typename vector_type::iterator I = find(vector_, X); |

160 | assert(I != vector_.end() && "Corrupted SetVector instances!"); |

161 | vector_.erase(I); |

162 | return true; |

163 | } |

164 | return false; |

165 | } |

166 | |

167 | /// Erase a single element from the set vector. |

168 | /// \returns an iterator pointing to the next element that followed the |

169 | /// element erased. This is the end of the SetVector if the last element is |

170 | /// erased. |

171 | iterator erase(iterator I) { |

172 | const key_type &V = *I; |

173 | assert(set_.count(V) && "Corrupted SetVector instances!"); |

174 | set_.erase(V); |

175 | |

176 | // FIXME: No need to use the non-const iterator when built with |

177 | // std:vector.erase(const_iterator) as defined in C++11. This is for |

178 | // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). |

179 | auto NI = vector_.begin(); |

180 | std::advance(NI, std::distance<iterator>(NI, I)); |

181 | |

182 | return vector_.erase(NI); |

183 | } |

184 | |

185 | /// Remove items from the set vector based on a predicate function. |

186 | /// |

187 | /// This is intended to be equivalent to the following code, if we could |

188 | /// write it: |

189 | /// |

190 | /// \code |

191 | /// V.erase(remove_if(V, P), V.end()); |

192 | /// \endcode |

193 | /// |

194 | /// However, SetVector doesn't expose non-const iterators, making any |

195 | /// algorithm like remove_if impossible to use. |

196 | /// |

197 | /// \returns true if any element is removed. |

198 | template <typename UnaryPredicate> |

199 | bool remove_if(UnaryPredicate P) { |

200 | typename vector_type::iterator I = |

201 | llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_)); |

202 | if (I == vector_.end()) |

203 | return false; |

204 | vector_.erase(I, vector_.end()); |

205 | return true; |

206 | } |

207 | |

208 | /// Count the number of elements of a given key in the SetVector. |

209 | /// \returns 0 if the element is not in the SetVector, 1 if it is. |

210 | size_type count(const key_type &key) const { |

211 | return set_.count(key); |

212 | } |

213 | |

214 | /// Completely clear the SetVector |

215 | void clear() { |

216 | set_.clear(); |

217 | vector_.clear(); |

218 | } |

219 | |

220 | /// Remove the last element of the SetVector. |

221 | void pop_back() { |

222 | assert(!empty() && "Cannot remove an element from an empty SetVector!"); |

223 | set_.erase(back()); |

224 | vector_.pop_back(); |

225 | } |

226 | |

227 | LLVM_NODISCARD T pop_back_val() { |

228 | T Ret = back(); |

229 | pop_back(); |

230 | return Ret; |

231 | } |

232 | |

233 | bool operator==(const SetVector &that) const { |

234 | return vector_ == that.vector_; |

235 | } |

236 | |

237 | bool operator!=(const SetVector &that) const { |

238 | return vector_ != that.vector_; |

239 | } |

240 | |

241 | /// Compute This := This u S, return whether 'This' changed. |

242 | /// TODO: We should be able to use set_union from SetOperations.h, but |

243 | /// SetVector interface is inconsistent with DenseSet. |

244 | template <class STy> |

245 | bool set_union(const STy &S) { |

246 | bool Changed = false; |

247 | |

248 | for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; |

249 | ++SI) |

250 | if (insert(*SI)) |

251 | Changed = true; |

252 | |

253 | return Changed; |

254 | } |

255 | |

256 | /// Compute This := This - B |

257 | /// TODO: We should be able to use set_subtract from SetOperations.h, but |

258 | /// SetVector interface is inconsistent with DenseSet. |

259 | template <class STy> |

260 | void set_subtract(const STy &S) { |

261 | for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; |

262 | ++SI) |

263 | remove(*SI); |

264 | } |

265 | |

266 | private: |

267 | /// A wrapper predicate designed for use with std::remove_if. |

268 | /// |

269 | /// This predicate wraps a predicate suitable for use with std::remove_if to |

270 | /// call set_.erase(x) on each element which is slated for removal. |

271 | template <typename UnaryPredicate> |

272 | class TestAndEraseFromSet { |

273 | UnaryPredicate P; |

274 | set_type &set_; |

275 | |

276 | public: |

277 | TestAndEraseFromSet(UnaryPredicate P, set_type &set_) |

278 | : P(std::move(P)), set_(set_) {} |

279 | |

280 | template <typename ArgumentT> |

281 | bool operator()(const ArgumentT &Arg) { |

282 | if (P(Arg)) { |

283 | set_.erase(Arg); |

284 | return true; |

285 | } |

286 | return false; |

287 | } |

288 | }; |

289 | |

290 | set_type set_; ///< The set. |

291 | vector_type vector_; ///< The vector. |

292 | }; |

293 | |

294 | /// A SetVector that performs no allocations if smaller than |

295 | /// a certain size. |

296 | template <typename T, unsigned N> |

297 | class SmallSetVector |

298 | : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> { |

299 | public: |

300 | SmallSetVector() = default; |

301 | |

302 | /// Initialize a SmallSetVector with a range of elements |

303 | template<typename It> |

304 | SmallSetVector(It Start, It End) { |

305 | this->insert(Start, End); |

306 | } |

307 | }; |

308 | |

309 | } // end namespace llvm |

310 | |

311 | #endif // LLVM_ADT_SETVECTOR_H |

312 |