1 | //===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- 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 | #ifndef LLVM_ADT_TINYPTRVECTOR_H |

10 | #define LLVM_ADT_TINYPTRVECTOR_H |

11 | |

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

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

14 | #include "llvm/ADT/PointerUnion.h" |

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

16 | #include <cassert> |

17 | #include <cstddef> |

18 | #include <iterator> |

19 | #include <type_traits> |

20 | |

21 | namespace llvm { |

22 | |

23 | /// TinyPtrVector - This class is specialized for cases where there are |

24 | /// normally 0 or 1 element in a vector, but is general enough to go beyond that |

25 | /// when required. |

26 | /// |

27 | /// NOTE: This container doesn't allow you to store a null pointer into it. |

28 | /// |

29 | template <typename EltTy> |

30 | class TinyPtrVector { |

31 | public: |

32 | using VecTy = SmallVector<EltTy, 4>; |

33 | using value_type = typename VecTy::value_type; |

34 | using PtrUnion = PointerUnion<EltTy, VecTy *>; |

35 | |

36 | private: |

37 | PtrUnion Val; |

38 | |

39 | public: |

40 | TinyPtrVector() = default; |

41 | |

42 | ~TinyPtrVector() { |

43 | if (VecTy *V = Val.template dyn_cast<VecTy*>()) |

44 | delete V; |

45 | } |

46 | |

47 | TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { |

48 | if (VecTy *V = Val.template dyn_cast<VecTy*>()) |

49 | Val = new VecTy(*V); |

50 | } |

51 | |

52 | TinyPtrVector &operator=(const TinyPtrVector &RHS) { |

53 | if (this == &RHS) |

54 | return *this; |

55 | if (RHS.empty()) { |

56 | this->clear(); |

57 | return *this; |

58 | } |

59 | |

60 | // Try to squeeze into the single slot. If it won't fit, allocate a copied |

61 | // vector. |

62 | if (Val.template is<EltTy>()) { |

63 | if (RHS.size() == 1) |

64 | Val = RHS.front(); |

65 | else |

66 | Val = new VecTy(*RHS.Val.template get<VecTy*>()); |

67 | return *this; |

68 | } |

69 | |

70 | // If we have a full vector allocated, try to re-use it. |

71 | if (RHS.Val.template is<EltTy>()) { |

72 | Val.template get<VecTy*>()->clear(); |

73 | Val.template get<VecTy*>()->push_back(RHS.front()); |

74 | } else { |

75 | *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>(); |

76 | } |

77 | return *this; |

78 | } |

79 | |

80 | TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { |

81 | RHS.Val = (EltTy)nullptr; |

82 | } |

83 | |

84 | TinyPtrVector &operator=(TinyPtrVector &&RHS) { |

85 | if (this == &RHS) |

86 | return *this; |

87 | if (RHS.empty()) { |

88 | this->clear(); |

89 | return *this; |

90 | } |

91 | |

92 | // If this vector has been allocated on the heap, re-use it if cheap. If it |

93 | // would require more copying, just delete it and we'll steal the other |

94 | // side. |

95 | if (VecTy *V = Val.template dyn_cast<VecTy*>()) { |

96 | if (RHS.Val.template is<EltTy>()) { |

97 | V->clear(); |

98 | V->push_back(RHS.front()); |

99 | RHS.Val = (EltTy)nullptr; |

100 | return *this; |

101 | } |

102 | delete V; |

103 | } |

104 | |

105 | Val = RHS.Val; |

106 | RHS.Val = (EltTy)nullptr; |

107 | return *this; |

108 | } |

109 | |

110 | TinyPtrVector(std::initializer_list<EltTy> IL) |

111 | : Val(IL.size() == 0 |

112 | ? PtrUnion() |

113 | : IL.size() == 1 ? PtrUnion(*IL.begin()) |

114 | : PtrUnion(new VecTy(IL.begin(), IL.end()))) {} |

115 | |

116 | /// Constructor from an ArrayRef. |

117 | /// |

118 | /// This also is a constructor for individual array elements due to the single |

119 | /// element constructor for ArrayRef. |

120 | explicit TinyPtrVector(ArrayRef<EltTy> Elts) |

121 | : Val(Elts.empty() |

122 | ? PtrUnion() |

123 | : Elts.size() == 1 |

124 | ? PtrUnion(Elts[0]) |

125 | : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} |

126 | |

127 | TinyPtrVector(size_t Count, EltTy Value) |

128 | : Val(Count == 0 ? PtrUnion() |

129 | : Count == 1 ? PtrUnion(Value) |

130 | : PtrUnion(new VecTy(Count, Value))) {} |

131 | |

132 | // implicit conversion operator to ArrayRef. |

133 | operator ArrayRef<EltTy>() const { |

134 | if (Val.isNull()) |

135 | return None; |

136 | if (Val.template is<EltTy>()) |

137 | return *Val.getAddrOfPtr1(); |

138 | return *Val.template get<VecTy*>(); |

139 | } |

140 | |

141 | // implicit conversion operator to MutableArrayRef. |

142 | operator MutableArrayRef<EltTy>() { |

143 | if (Val.isNull()) |

144 | return None; |

145 | if (Val.template is<EltTy>()) |

146 | return *Val.getAddrOfPtr1(); |

147 | return *Val.template get<VecTy*>(); |

148 | } |

149 | |

150 | // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*. |

151 | template<typename U, |

152 | typename std::enable_if< |

153 | std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value, |

154 | bool>::type = false> |

155 | operator ArrayRef<U>() const { |

156 | return operator ArrayRef<EltTy>(); |

157 | } |

158 | |

159 | bool empty() const { |

160 | // This vector can be empty if it contains no element, or if it |

161 | // contains a pointer to an empty vector. |

162 | if (Val.isNull()) return true; |

163 | if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) |

164 | return Vec->empty(); |

165 | return false; |

166 | } |

167 | |

168 | unsigned size() const { |

169 | if (empty()) |

170 | return 0; |

171 | if (Val.template is<EltTy>()) |

172 | return 1; |

173 | return Val.template get<VecTy*>()->size(); |

174 | } |

175 | |

176 | using iterator = EltTy *; |

177 | using const_iterator = const EltTy *; |

178 | using reverse_iterator = std::reverse_iterator<iterator>; |

179 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |

180 | |

181 | iterator begin() { |

182 | if (Val.template is<EltTy>()) |

183 | return Val.getAddrOfPtr1(); |

184 | |

185 | return Val.template get<VecTy *>()->begin(); |

186 | } |

187 | |

188 | iterator end() { |

189 | if (Val.template is<EltTy>()) |

190 | return begin() + (Val.isNull() ? 0 : 1); |

191 | |

192 | return Val.template get<VecTy *>()->end(); |

193 | } |

194 | |

195 | const_iterator begin() const { |

196 | return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); |

197 | } |

198 | |

199 | const_iterator end() const { |

200 | return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); |

201 | } |

202 | |

203 | reverse_iterator rbegin() { return reverse_iterator(end()); } |

204 | reverse_iterator rend() { return reverse_iterator(begin()); } |

205 | |

206 | const_reverse_iterator rbegin() const { |

207 | return const_reverse_iterator(end()); |

208 | } |

209 | |

210 | const_reverse_iterator rend() const { |

211 | return const_reverse_iterator(begin()); |

212 | } |

213 | |

214 | EltTy operator[](unsigned i) const { |

215 | assert(!Val.isNull() && "can't index into an empty vector"); |

216 | if (EltTy V = Val.template dyn_cast<EltTy>()) { |

217 | assert(i == 0 && "tinyvector index out of range"); |

218 | return V; |

219 | } |

220 | |

221 | assert(i < Val.template get<VecTy*>()->size() && |

222 | "tinyvector index out of range"); |

223 | return (*Val.template get<VecTy*>())[i]; |

224 | } |

225 | |

226 | EltTy front() const { |

227 | assert(!empty() && "vector empty"); |

228 | if (EltTy V = Val.template dyn_cast<EltTy>()) |

229 | return V; |

230 | return Val.template get<VecTy*>()->front(); |

231 | } |

232 | |

233 | EltTy back() const { |

234 | assert(!empty() && "vector empty"); |

235 | if (EltTy V = Val.template dyn_cast<EltTy>()) |

236 | return V; |

237 | return Val.template get<VecTy*>()->back(); |

238 | } |

239 | |

240 | void push_back(EltTy NewVal) { |

241 | assert(NewVal && "Can't add a null value"); |

242 | |

243 | // If we have nothing, add something. |

244 | if (Val.isNull()) { |

245 | Val = NewVal; |

246 | return; |

247 | } |

248 | |

249 | // If we have a single value, convert to a vector. |

250 | if (EltTy V = Val.template dyn_cast<EltTy>()) { |

251 | Val = new VecTy(); |

252 | Val.template get<VecTy*>()->push_back(V); |

253 | } |

254 | |

255 | // Add the new value, we know we have a vector. |

256 | Val.template get<VecTy*>()->push_back(NewVal); |

257 | } |

258 | |

259 | void pop_back() { |

260 | // If we have a single value, convert to empty. |

261 | if (Val.template is<EltTy>()) |

262 | Val = (EltTy)nullptr; |

263 | else if (VecTy *Vec = Val.template get<VecTy*>()) |

264 | Vec->pop_back(); |

265 | } |

266 | |

267 | void clear() { |

268 | // If we have a single value, convert to empty. |

269 | if (Val.template is<EltTy>()) { |

270 | Val = (EltTy)nullptr; |

271 | } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { |

272 | // If we have a vector form, just clear it. |

273 | Vec->clear(); |

274 | } |

275 | // Otherwise, we're already empty. |

276 | } |

277 | |

278 | iterator erase(iterator I) { |

279 | assert(I >= begin() && "Iterator to erase is out of bounds."); |

280 | assert(I < end() && "Erasing at past-the-end iterator."); |

281 | |

282 | // If we have a single value, convert to empty. |

283 | if (Val.template is<EltTy>()) { |

284 | if (I == begin()) |

285 | Val = (EltTy)nullptr; |

286 | } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { |

287 | // multiple items in a vector; just do the erase, there is no |

288 | // benefit to collapsing back to a pointer |

289 | return Vec->erase(I); |

290 | } |

291 | return end(); |

292 | } |

293 | |

294 | iterator erase(iterator S, iterator E) { |

295 | assert(S >= begin() && "Range to erase is out of bounds."); |

296 | assert(S <= E && "Trying to erase invalid range."); |

297 | assert(E <= end() && "Trying to erase past the end."); |

298 | |

299 | if (Val.template is<EltTy>()) { |

300 | if (S == begin() && S != E) |

301 | Val = (EltTy)nullptr; |

302 | } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { |

303 | return Vec->erase(S, E); |

304 | } |

305 | return end(); |

306 | } |

307 | |

308 | iterator insert(iterator I, const EltTy &Elt) { |

309 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); |

310 | assert(I <= this->end() && "Inserting past the end of the vector."); |

311 | if (I == end()) { |

312 | push_back(Elt); |

313 | return std::prev(end()); |

314 | } |

315 | assert(!Val.isNull() && "Null value with non-end insert iterator."); |

316 | if (EltTy V = Val.template dyn_cast<EltTy>()) { |

317 | assert(I == begin()); |

318 | Val = Elt; |

319 | push_back(V); |

320 | return begin(); |

321 | } |

322 | |

323 | return Val.template get<VecTy*>()->insert(I, Elt); |

324 | } |

325 | |

326 | template<typename ItTy> |

327 | iterator insert(iterator I, ItTy From, ItTy To) { |

328 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); |

329 | assert(I <= this->end() && "Inserting past the end of the vector."); |

330 | if (From == To) |

331 | return I; |

332 | |

333 | // If we have a single value, convert to a vector. |

334 | ptrdiff_t Offset = I - begin(); |

335 | if (Val.isNull()) { |

336 | if (std::next(From) == To) { |

337 | Val = *From; |

338 | return begin(); |

339 | } |

340 | |

341 | Val = new VecTy(); |

342 | } else if (EltTy V = Val.template dyn_cast<EltTy>()) { |

343 | Val = new VecTy(); |

344 | Val.template get<VecTy*>()->push_back(V); |

345 | } |

346 | return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); |

347 | } |

348 | }; |

349 | |

350 | } // end namespace llvm |

351 | |

352 | #endif // LLVM_ADT_TINYPTRVECTOR_H |

353 |