1 | //===- ArrayRef.h - Array Reference Wrapper ---------------------*- 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_ARRAYREF_H |

10 | #define LLVM_ADT_ARRAYREF_H |

11 | |

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

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

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

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

16 | #include <algorithm> |

17 | #include <array> |

18 | #include <cassert> |

19 | #include <cstddef> |

20 | #include <initializer_list> |

21 | #include <iterator> |

22 | #include <memory> |

23 | #include <type_traits> |

24 | #include <vector> |

25 | |

26 | namespace llvm { |

27 | template<typename T> class [[nodiscard]] MutableArrayRef; |

28 | |

29 | /// ArrayRef - Represent a constant reference to an array (0 or more elements |

30 | /// consecutively in memory), i.e. a start pointer and a length. It allows |

31 | /// various APIs to take consecutive elements easily and conveniently. |

32 | /// |

33 | /// This class does not own the underlying data, it is expected to be used in |

34 | /// situations where the data resides in some other buffer, whose lifetime |

35 | /// extends past that of the ArrayRef. For this reason, it is not in general |

36 | /// safe to store an ArrayRef. |

37 | /// |

38 | /// This is intended to be trivially copyable, so it should be passed by |

39 | /// value. |

40 | template<typename T> |

41 | class LLVM_GSL_POINTER [[nodiscard]] ArrayRef { |

42 | public: |

43 | using value_type = T; |

44 | using pointer = value_type *; |

45 | using const_pointer = const value_type *; |

46 | using reference = value_type &; |

47 | using const_reference = const value_type &; |

48 | using iterator = const_pointer; |

49 | using const_iterator = const_pointer; |

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

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

52 | using size_type = size_t; |

53 | using difference_type = ptrdiff_t; |

54 | |

55 | private: |

56 | /// The start of the array, in an external buffer. |

57 | const T *Data = nullptr; |

58 | |

59 | /// The number of elements. |

60 | size_type Length = 0; |

61 | |

62 | public: |

63 | /// @name Constructors |

64 | /// @{ |

65 | |

66 | /// Construct an empty ArrayRef. |

67 | /*implicit*/ ArrayRef() = default; |

68 | |

69 | /// Construct an empty ArrayRef from std::nullopt. |

70 | /*implicit*/ ArrayRef(std::nullopt_t) {} |

71 | |

72 | /// Construct an ArrayRef from a single element. |

73 | /*implicit*/ ArrayRef(const T &OneElt) |

74 | : Data(&OneElt), Length(1) {} |

75 | |

76 | /// Construct an ArrayRef from a pointer and length. |

77 | constexpr /*implicit*/ ArrayRef(const T *data, size_t length) |

78 | : Data(data), Length(length) {} |

79 | |

80 | /// Construct an ArrayRef from a range. |

81 | constexpr ArrayRef(const T *begin, const T *end) |

82 | : Data(begin), Length(end - begin) { |

83 | assert(begin <= end); |

84 | } |

85 | |

86 | /// Construct an ArrayRef from a SmallVector. This is templated in order to |

87 | /// avoid instantiating SmallVectorTemplateCommon<T> whenever we |

88 | /// copy-construct an ArrayRef. |

89 | template<typename U> |

90 | /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec) |

91 | : Data(Vec.data()), Length(Vec.size()) { |

92 | } |

93 | |

94 | /// Construct an ArrayRef from a std::vector. |

95 | template<typename A> |

96 | /*implicit*/ ArrayRef(const std::vector<T, A> &Vec) |

97 | : Data(Vec.data()), Length(Vec.size()) {} |

98 | |

99 | /// Construct an ArrayRef from a std::array |

100 | template <size_t N> |

101 | /*implicit*/ constexpr ArrayRef(const std::array<T, N> &Arr) |

102 | : Data(Arr.data()), Length(N) {} |

103 | |

104 | /// Construct an ArrayRef from a C array. |

105 | template <size_t N> |

106 | /*implicit*/ constexpr ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {} |

107 | |

108 | /// Construct an ArrayRef from a std::initializer_list. |

109 | #if LLVM_GNUC_PREREQ(9, 0, 0) |

110 | // Disable gcc's warning in this constructor as it generates an enormous amount |

111 | // of messages. Anyone using ArrayRef should already be aware of the fact that |

112 | // it does not do lifetime extension. |

113 | #pragma GCC diagnostic push |

114 | #pragma GCC diagnostic ignored "-Winit-list-lifetime" |

115 | #endif |

116 | constexpr /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec) |

117 | : Data(Vec.begin() == Vec.end() ? (T *)nullptr : Vec.begin()), |

118 | Length(Vec.size()) {} |

119 | #if LLVM_GNUC_PREREQ(9, 0, 0) |

120 | #pragma GCC diagnostic pop |

121 | #endif |

122 | |

123 | /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to |

124 | /// ensure that only ArrayRefs of pointers can be converted. |

125 | template <typename U> |

126 | ArrayRef(const ArrayRef<U *> &A, |

127 | std::enable_if_t<std::is_convertible<U *const *, T const *>::value> |

128 | * = nullptr) |

129 | : Data(A.data()), Length(A.size()) {} |

130 | |

131 | /// Construct an ArrayRef<const T*> from a SmallVector<T*>. This is |

132 | /// templated in order to avoid instantiating SmallVectorTemplateCommon<T> |

133 | /// whenever we copy-construct an ArrayRef. |

134 | template <typename U, typename DummyT> |

135 | /*implicit*/ ArrayRef( |

136 | const SmallVectorTemplateCommon<U *, DummyT> &Vec, |

137 | std::enable_if_t<std::is_convertible<U *const *, T const *>::value> * = |

138 | nullptr) |

139 | : Data(Vec.data()), Length(Vec.size()) {} |

140 | |

141 | /// Construct an ArrayRef<const T*> from std::vector<T*>. This uses SFINAE |

142 | /// to ensure that only vectors of pointers can be converted. |

143 | template <typename U, typename A> |

144 | ArrayRef(const std::vector<U *, A> &Vec, |

145 | std::enable_if_t<std::is_convertible<U *const *, T const *>::value> |

146 | * = nullptr) |

147 | : Data(Vec.data()), Length(Vec.size()) {} |

148 | |

149 | /// @} |

150 | /// @name Simple Operations |

151 | /// @{ |

152 | |

153 | iterator begin() const { return Data; } |

154 | iterator end() const { return Data + Length; } |

155 | |

156 | reverse_iterator rbegin() const { return reverse_iterator(end()); } |

157 | reverse_iterator rend() const { return reverse_iterator(begin()); } |

158 | |

159 | /// empty - Check if the array is empty. |

160 | bool empty() const { return Length == 0; } |

161 | |

162 | const T *data() const { return Data; } |

163 | |

164 | /// size - Get the array size. |

165 | size_t size() const { return Length; } |

166 | |

167 | /// front - Get the first element. |

168 | const T &front() const { |

169 | assert(!empty()); |

170 | return Data[0]; |

171 | } |

172 | |

173 | /// back - Get the last element. |

174 | const T &back() const { |

175 | assert(!empty()); |

176 | return Data[Length-1]; |

177 | } |

178 | |

179 | // copy - Allocate copy in Allocator and return ArrayRef<T> to it. |

180 | template <typename Allocator> MutableArrayRef<T> copy(Allocator &A) { |

181 | T *Buff = A.template Allocate<T>(Length); |

182 | std::uninitialized_copy(begin(), end(), Buff); |

183 | return MutableArrayRef<T>(Buff, Length); |

184 | } |

185 | |

186 | /// equals - Check for element-wise equality. |

187 | bool equals(ArrayRef RHS) const { |

188 | if (Length != RHS.Length) |

189 | return false; |

190 | return std::equal(begin(), end(), RHS.begin()); |

191 | } |

192 | |

193 | /// slice(n, m) - Chop off the first N elements of the array, and keep M |

194 | /// elements in the array. |

195 | ArrayRef<T> slice(size_t N, size_t M) const { |

196 | assert(N+M <= size() && "Invalid specifier"); |

197 | return ArrayRef<T>(data()+N, M); |

198 | } |

199 | |

200 | /// slice(n) - Chop off the first N elements of the array. |

201 | ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); } |

202 | |

203 | /// Drop the first \p N elements of the array. |

204 | ArrayRef<T> drop_front(size_t N = 1) const { |

205 | assert(size() >= N && "Dropping more elements than exist"); |

206 | return slice(N, size() - N); |

207 | } |

208 | |

209 | /// Drop the last \p N elements of the array. |

210 | ArrayRef<T> drop_back(size_t N = 1) const { |

211 | assert(size() >= N && "Dropping more elements than exist"); |

212 | return slice(0, size() - N); |

213 | } |

214 | |

215 | /// Return a copy of *this with the first N elements satisfying the |

216 | /// given predicate removed. |

217 | template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const { |

218 | return ArrayRef<T>(find_if_not(*this, Pred), end()); |

219 | } |

220 | |

221 | /// Return a copy of *this with the first N elements not satisfying |

222 | /// the given predicate removed. |

223 | template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const { |

224 | return ArrayRef<T>(find_if(*this, Pred), end()); |

225 | } |

226 | |

227 | /// Return a copy of *this with only the first \p N elements. |

228 | ArrayRef<T> take_front(size_t N = 1) const { |

229 | if (N >= size()) |

230 | return *this; |

231 | return drop_back(N: size() - N); |

232 | } |

233 | |

234 | /// Return a copy of *this with only the last \p N elements. |

235 | ArrayRef<T> take_back(size_t N = 1) const { |

236 | if (N >= size()) |

237 | return *this; |

238 | return drop_front(N: size() - N); |

239 | } |

240 | |

241 | /// Return the first N elements of this Array that satisfy the given |

242 | /// predicate. |

243 | template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const { |

244 | return ArrayRef<T>(begin(), find_if_not(*this, Pred)); |

245 | } |

246 | |

247 | /// Return the first N elements of this Array that don't satisfy the |

248 | /// given predicate. |

249 | template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const { |

250 | return ArrayRef<T>(begin(), find_if(*this, Pred)); |

251 | } |

252 | |

253 | /// @} |

254 | /// @name Operator Overloads |

255 | /// @{ |

256 | const T &operator[](size_t Index) const { |

257 | assert(Index < Length && "Invalid index!"); |

258 | return Data[Index]; |

259 | } |

260 | |

261 | /// Disallow accidental assignment from a temporary. |

262 | /// |

263 | /// The declaration here is extra complicated so that "arrayRef = {}" |

264 | /// continues to select the move assignment operator. |

265 | template <typename U> |

266 | std::enable_if_t<std::is_same<U, T>::value, ArrayRef<T>> & |

267 | operator=(U &&Temporary) = delete; |

268 | |

269 | /// Disallow accidental assignment from a temporary. |

270 | /// |

271 | /// The declaration here is extra complicated so that "arrayRef = {}" |

272 | /// continues to select the move assignment operator. |

273 | template <typename U> |

274 | std::enable_if_t<std::is_same<U, T>::value, ArrayRef<T>> & |

275 | operator=(std::initializer_list<U>) = delete; |

276 | |

277 | /// @} |

278 | /// @name Expensive Operations |

279 | /// @{ |

280 | std::vector<T> vec() const { |

281 | return std::vector<T>(Data, Data+Length); |

282 | } |

283 | |

284 | /// @} |

285 | /// @name Conversion operators |

286 | /// @{ |

287 | operator std::vector<T>() const { |

288 | return std::vector<T>(Data, Data+Length); |

289 | } |

290 | |

291 | /// @} |

292 | }; |

293 | |

294 | /// MutableArrayRef - Represent a mutable reference to an array (0 or more |

295 | /// elements consecutively in memory), i.e. a start pointer and a length. It |

296 | /// allows various APIs to take and modify consecutive elements easily and |

297 | /// conveniently. |

298 | /// |

299 | /// This class does not own the underlying data, it is expected to be used in |

300 | /// situations where the data resides in some other buffer, whose lifetime |

301 | /// extends past that of the MutableArrayRef. For this reason, it is not in |

302 | /// general safe to store a MutableArrayRef. |

303 | /// |

304 | /// This is intended to be trivially copyable, so it should be passed by |

305 | /// value. |

306 | template<typename T> |

307 | class [[nodiscard]] MutableArrayRef : public ArrayRef<T> { |

308 | public: |

309 | using value_type = T; |

310 | using pointer = value_type *; |

311 | using const_pointer = const value_type *; |

312 | using reference = value_type &; |

313 | using const_reference = const value_type &; |

314 | using iterator = pointer; |

315 | using const_iterator = const_pointer; |

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

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

318 | using size_type = size_t; |

319 | using difference_type = ptrdiff_t; |

320 | |

321 | /// Construct an empty MutableArrayRef. |

322 | /*implicit*/ MutableArrayRef() = default; |

323 | |

324 | /// Construct an empty MutableArrayRef from std::nullopt. |

325 | /*implicit*/ MutableArrayRef(std::nullopt_t) : ArrayRef<T>() {} |

326 | |

327 | /// Construct a MutableArrayRef from a single element. |

328 | /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {} |

329 | |

330 | /// Construct a MutableArrayRef from a pointer and length. |

331 | /*implicit*/ MutableArrayRef(T *data, size_t length) |

332 | : ArrayRef<T>(data, length) {} |

333 | |

334 | /// Construct a MutableArrayRef from a range. |

335 | MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {} |

336 | |

337 | /// Construct a MutableArrayRef from a SmallVector. |

338 | /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec) |

339 | : ArrayRef<T>(Vec) {} |

340 | |

341 | /// Construct a MutableArrayRef from a std::vector. |

342 | /*implicit*/ MutableArrayRef(std::vector<T> &Vec) |

343 | : ArrayRef<T>(Vec) {} |

344 | |

345 | /// Construct a MutableArrayRef from a std::array |

346 | template <size_t N> |

347 | /*implicit*/ constexpr MutableArrayRef(std::array<T, N> &Arr) |

348 | : ArrayRef<T>(Arr) {} |

349 | |

350 | /// Construct a MutableArrayRef from a C array. |

351 | template <size_t N> |

352 | /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {} |

353 | |

354 | T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } |

355 | |

356 | iterator begin() const { return data(); } |

357 | iterator end() const { return data() + this->size(); } |

358 | |

359 | reverse_iterator rbegin() const { return reverse_iterator(end()); } |

360 | reverse_iterator rend() const { return reverse_iterator(begin()); } |

361 | |

362 | /// front - Get the first element. |

363 | T &front() const { |

364 | assert(!this->empty()); |

365 | return data()[0]; |

366 | } |

367 | |

368 | /// back - Get the last element. |

369 | T &back() const { |

370 | assert(!this->empty()); |

371 | return data()[this->size()-1]; |

372 | } |

373 | |

374 | /// slice(n, m) - Chop off the first N elements of the array, and keep M |

375 | /// elements in the array. |

376 | MutableArrayRef<T> slice(size_t N, size_t M) const { |

377 | assert(N + M <= this->size() && "Invalid specifier"); |

378 | return MutableArrayRef<T>(this->data() + N, M); |

379 | } |

380 | |

381 | /// slice(n) - Chop off the first N elements of the array. |

382 | MutableArrayRef<T> slice(size_t N) const { |

383 | return slice(N, this->size() - N); |

384 | } |

385 | |

386 | /// Drop the first \p N elements of the array. |

387 | MutableArrayRef<T> drop_front(size_t N = 1) const { |

388 | assert(this->size() >= N && "Dropping more elements than exist"); |

389 | return slice(N, this->size() - N); |

390 | } |

391 | |

392 | MutableArrayRef<T> drop_back(size_t N = 1) const { |

393 | assert(this->size() >= N && "Dropping more elements than exist"); |

394 | return slice(0, this->size() - N); |

395 | } |

396 | |

397 | /// Return a copy of *this with the first N elements satisfying the |

398 | /// given predicate removed. |

399 | template <class PredicateT> |

400 | MutableArrayRef<T> drop_while(PredicateT Pred) const { |

401 | return MutableArrayRef<T>(find_if_not(*this, Pred), end()); |

402 | } |

403 | |

404 | /// Return a copy of *this with the first N elements not satisfying |

405 | /// the given predicate removed. |

406 | template <class PredicateT> |

407 | MutableArrayRef<T> drop_until(PredicateT Pred) const { |

408 | return MutableArrayRef<T>(find_if(*this, Pred), end()); |

409 | } |

410 | |

411 | /// Return a copy of *this with only the first \p N elements. |

412 | MutableArrayRef<T> take_front(size_t N = 1) const { |

413 | if (N >= this->size()) |

414 | return *this; |

415 | return drop_back(N: this->size() - N); |

416 | } |

417 | |

418 | /// Return a copy of *this with only the last \p N elements. |

419 | MutableArrayRef<T> take_back(size_t N = 1) const { |

420 | if (N >= this->size()) |

421 | return *this; |

422 | return drop_front(N: this->size() - N); |

423 | } |

424 | |

425 | /// Return the first N elements of this Array that satisfy the given |

426 | /// predicate. |

427 | template <class PredicateT> |

428 | MutableArrayRef<T> take_while(PredicateT Pred) const { |

429 | return MutableArrayRef<T>(begin(), find_if_not(*this, Pred)); |

430 | } |

431 | |

432 | /// Return the first N elements of this Array that don't satisfy the |

433 | /// given predicate. |

434 | template <class PredicateT> |

435 | MutableArrayRef<T> take_until(PredicateT Pred) const { |

436 | return MutableArrayRef<T>(begin(), find_if(*this, Pred)); |

437 | } |

438 | |

439 | /// @} |

440 | /// @name Operator Overloads |

441 | /// @{ |

442 | T &operator[](size_t Index) const { |

443 | assert(Index < this->size() && "Invalid index!"); |

444 | return data()[Index]; |

445 | } |

446 | }; |

447 | |

448 | /// This is a MutableArrayRef that owns its array. |

449 | template <typename T> class OwningArrayRef : public MutableArrayRef<T> { |

450 | public: |

451 | OwningArrayRef() = default; |

452 | OwningArrayRef(size_t Size) : MutableArrayRef<T>(new T[Size], Size) {} |

453 | |

454 | OwningArrayRef(ArrayRef<T> Data) |

455 | : MutableArrayRef<T>(new T[Data.size()], Data.size()) { |

456 | std::copy(Data.begin(), Data.end(), this->begin()); |

457 | } |

458 | |

459 | OwningArrayRef(OwningArrayRef &&Other) { *this = std::move(Other); } |

460 | |

461 | OwningArrayRef &operator=(OwningArrayRef &&Other) { |

462 | delete[] this->data(); |

463 | this->MutableArrayRef<T>::operator=(Other); |

464 | Other.MutableArrayRef<T>::operator=(MutableArrayRef<T>()); |

465 | return *this; |

466 | } |

467 | |

468 | ~OwningArrayRef() { delete[] this->data(); } |

469 | }; |

470 | |

471 | /// @name ArrayRef Deduction guides |

472 | /// @{ |

473 | /// Deduction guide to construct an ArrayRef from a single element. |

474 | template <typename T> ArrayRef(const T &OneElt) -> ArrayRef<T>; |

475 | |

476 | /// Deduction guide to construct an ArrayRef from a pointer and length |

477 | template <typename T> ArrayRef(const T *data, size_t length) -> ArrayRef<T>; |

478 | |

479 | /// Deduction guide to construct an ArrayRef from a range |

480 | template <typename T> ArrayRef(const T *data, const T *end) -> ArrayRef<T>; |

481 | |

482 | /// Deduction guide to construct an ArrayRef from a SmallVector |

483 | template <typename T> ArrayRef(const SmallVectorImpl<T> &Vec) -> ArrayRef<T>; |

484 | |

485 | /// Deduction guide to construct an ArrayRef from a SmallVector |

486 | template <typename T, unsigned N> |

487 | ArrayRef(const SmallVector<T, N> &Vec) -> ArrayRef<T>; |

488 | |

489 | /// Deduction guide to construct an ArrayRef from a std::vector |

490 | template <typename T> ArrayRef(const std::vector<T> &Vec) -> ArrayRef<T>; |

491 | |

492 | /// Deduction guide to construct an ArrayRef from a std::array |

493 | template <typename T, std::size_t N> |

494 | ArrayRef(const std::array<T, N> &Vec) -> ArrayRef<T>; |

495 | |

496 | /// Deduction guide to construct an ArrayRef from an ArrayRef (const) |

497 | template <typename T> ArrayRef(const ArrayRef<T> &Vec) -> ArrayRef<T>; |

498 | |

499 | /// Deduction guide to construct an ArrayRef from an ArrayRef |

500 | template <typename T> ArrayRef(ArrayRef<T> &Vec) -> ArrayRef<T>; |

501 | |

502 | /// Deduction guide to construct an ArrayRef from a C array. |

503 | template <typename T, size_t N> ArrayRef(const T (&Arr)[N]) -> ArrayRef<T>; |

504 | |

505 | /// @} |

506 | |

507 | /// @name MutableArrayRef Deduction guides |

508 | /// @{ |

509 | /// Deduction guide to construct a `MutableArrayRef` from a single element |

510 | template <class T> MutableArrayRef(T &OneElt) -> MutableArrayRef<T>; |

511 | |

512 | /// Deduction guide to construct a `MutableArrayRef` from a pointer and |

513 | /// length. |

514 | template <class T> |

515 | MutableArrayRef(T *data, size_t length) -> MutableArrayRef<T>; |

516 | |

517 | /// Deduction guide to construct a `MutableArrayRef` from a `SmallVector`. |

518 | template <class T> |

519 | MutableArrayRef(SmallVectorImpl<T> &Vec) -> MutableArrayRef<T>; |

520 | |

521 | template <class T, unsigned N> |

522 | MutableArrayRef(SmallVector<T, N> &Vec) -> MutableArrayRef<T>; |

523 | |

524 | /// Deduction guide to construct a `MutableArrayRef` from a `std::vector`. |

525 | template <class T> MutableArrayRef(std::vector<T> &Vec) -> MutableArrayRef<T>; |

526 | |

527 | /// Deduction guide to construct a `MutableArrayRef` from a `std::array`. |

528 | template <class T, std::size_t N> |

529 | MutableArrayRef(std::array<T, N> &Vec) -> MutableArrayRef<T>; |

530 | |

531 | /// Deduction guide to construct a `MutableArrayRef` from a C array. |

532 | template <typename T, size_t N> |

533 | MutableArrayRef(T (&Arr)[N]) -> MutableArrayRef<T>; |

534 | |

535 | /// @} |

536 | /// @name ArrayRef Comparison Operators |

537 | /// @{ |

538 | |

539 | template<typename T> |

540 | inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) { |

541 | return LHS.equals(RHS); |

542 | } |

543 | |

544 | template <typename T> |

545 | inline bool operator==(SmallVectorImpl<T> &LHS, ArrayRef<T> RHS) { |

546 | return ArrayRef<T>(LHS).equals(RHS); |

547 | } |

548 | |

549 | template <typename T> |

550 | inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) { |

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

552 | } |

553 | |

554 | template <typename T> |

555 | inline bool operator!=(SmallVectorImpl<T> &LHS, ArrayRef<T> RHS) { |

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

557 | } |

558 | |

559 | /// @} |

560 | |

561 | template <typename T> hash_code hash_value(ArrayRef<T> S) { |

562 | return hash_combine_range(S.begin(), S.end()); |

563 | } |

564 | |

565 | // Provide DenseMapInfo for ArrayRefs. |

566 | template <typename T> struct DenseMapInfo<ArrayRef<T>, void> { |

567 | static inline ArrayRef<T> getEmptyKey() { |

568 | return ArrayRef<T>( |

569 | reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)), size_t(0)); |

570 | } |

571 | |

572 | static inline ArrayRef<T> getTombstoneKey() { |

573 | return ArrayRef<T>( |

574 | reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)), size_t(0)); |

575 | } |

576 | |

577 | static unsigned getHashValue(ArrayRef<T> Val) { |

578 | assert(Val.data() != getEmptyKey().data() && |

579 | "Cannot hash the empty key!"); |

580 | assert(Val.data() != getTombstoneKey().data() && |

581 | "Cannot hash the tombstone key!"); |

582 | return (unsigned)(hash_value(Val)); |

583 | } |

584 | |

585 | static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) { |

586 | if (RHS.data() == getEmptyKey().data()) |

587 | return LHS.data() == getEmptyKey().data(); |

588 | if (RHS.data() == getTombstoneKey().data()) |

589 | return LHS.data() == getTombstoneKey().data(); |

590 | return LHS == RHS; |

591 | } |

592 | }; |

593 | |

594 | } // end namespace llvm |

595 | |

596 | #endif // LLVM_ADT_ARRAYREF_H |

597 |