Line data Source code
1 : //===- ArrayRef.h - Array Reference Wrapper ---------------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #ifndef LLVM_ADT_ARRAYREF_H
11 : #define LLVM_ADT_ARRAYREF_H
12 :
13 : #include "llvm/ADT/Hashing.h"
14 : #include "llvm/ADT/None.h"
15 : #include "llvm/ADT/SmallVector.h"
16 : #include "llvm/ADT/STLExtras.h"
17 : #include "llvm/Support/Compiler.h"
18 : #include <algorithm>
19 : #include <array>
20 : #include <cassert>
21 : #include <cstddef>
22 : #include <initializer_list>
23 : #include <iterator>
24 : #include <memory>
25 : #include <type_traits>
26 : #include <vector>
27 :
28 : namespace llvm {
29 :
30 : /// ArrayRef - Represent a constant reference to an array (0 or more elements
31 : /// consecutively in memory), i.e. a start pointer and a length. It allows
32 : /// various APIs to take consecutive elements easily and conveniently.
33 : ///
34 : /// This class does not own the underlying data, it is expected to be used in
35 : /// situations where the data resides in some other buffer, whose lifetime
36 : /// extends past that of the ArrayRef. For this reason, it is not in general
37 : /// safe to store an ArrayRef.
38 : ///
39 : /// This is intended to be trivially copyable, so it should be passed by
40 : /// value.
41 : template<typename T>
42 : class LLVM_NODISCARD ArrayRef {
43 : public:
44 : using iterator = const T *;
45 : using const_iterator = const T *;
46 : using size_type = size_t;
47 : using reverse_iterator = std::reverse_iterator<iterator>;
48 :
49 : private:
50 : /// The start of the array, in an external buffer.
51 : const T *Data = nullptr;
52 :
53 : /// The number of elements.
54 : size_type Length = 0;
55 :
56 : public:
57 : /// @name Constructors
58 : /// @{
59 :
60 : /// Construct an empty ArrayRef.
61 364316799 : /*implicit*/ ArrayRef() = default;
62 :
63 : /// Construct an empty ArrayRef from None.
64 123240340 : /*implicit*/ ArrayRef(NoneType) {}
65 :
66 : /// Construct an ArrayRef from a single element.
67 644531575 : /*implicit*/ ArrayRef(const T &OneElt)
68 643162146 : : Data(&OneElt), Length(1) {}
69 :
70 : /// Construct an ArrayRef from a pointer and length.
71 64548178 : /*implicit*/ ArrayRef(const T *data, size_t length)
72 64526455 : : Data(data), Length(length) {}
73 :
74 : /// Construct an ArrayRef from a range.
75 492278 : ArrayRef(const T *begin, const T *end)
76 142103692 : : Data(begin), Length(end - begin) {}
77 :
78 : /// Construct an ArrayRef from a SmallVector. This is templated in order to
79 : /// avoid instantiating SmallVectorTemplateCommon<T> whenever we
80 : /// copy-construct an ArrayRef.
81 : template<typename U>
82 834665839 : /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
83 1960588341 : : Data(Vec.data()), Length(Vec.size()) {
84 : }
85 :
86 : /// Construct an ArrayRef from a std::vector.
87 : template<typename A>
88 24231064 : /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
89 76498375 : : Data(Vec.data()), Length(Vec.size()) {}
90 :
91 : /// Construct an ArrayRef from a std::array
92 : template <size_t N>
93 194 : /*implicit*/ constexpr ArrayRef(const std::array<T, N> &Arr)
94 130 : : Data(Arr.data()), Length(N) {}
95 :
96 : /// Construct an ArrayRef from a C array.
97 : template <size_t N>
98 66765409 : /*implicit*/ constexpr ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {}
99 :
100 : /// Construct an ArrayRef from a std::initializer_list.
101 9324920 : /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
102 12 : : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()),
103 9310515 : Length(Vec.size()) {}
104 :
105 : /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to
106 : /// ensure that only ArrayRefs of pointers can be converted.
107 : template <typename U>
108 10068448 : ArrayRef(
109 : const ArrayRef<U *> &A,
110 : typename std::enable_if<
111 : std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
112 10068448 : : Data(A.data()), Length(A.size()) {}
113 :
114 : /// Construct an ArrayRef<const T*> from a SmallVector<T*>. This is
115 : /// templated in order to avoid instantiating SmallVectorTemplateCommon<T>
116 : /// whenever we copy-construct an ArrayRef.
117 : template<typename U, typename DummyT>
118 206316 : /*implicit*/ ArrayRef(
119 : const SmallVectorTemplateCommon<U *, DummyT> &Vec,
120 : typename std::enable_if<
121 : std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
122 412638 : : Data(Vec.data()), Length(Vec.size()) {
123 : }
124 :
125 : /// Construct an ArrayRef<const T*> from std::vector<T*>. This uses SFINAE
126 : /// to ensure that only vectors of pointers can be converted.
127 : template<typename U, typename A>
128 3 : ArrayRef(const std::vector<U *, A> &Vec,
129 : typename std::enable_if<
130 : std::is_convertible<U *const *, T const *>::value>::type* = 0)
131 6 : : Data(Vec.data()), Length(Vec.size()) {}
132 :
133 : /// @}
134 : /// @name Simple Operations
135 : /// @{
136 :
137 0 : iterator begin() const { return Data; }
138 2085264134 : iterator end() const { return Data + Length; }
139 :
140 28168366 : reverse_iterator rbegin() const { return reverse_iterator(end()); }
141 334793 : reverse_iterator rend() const { return reverse_iterator(begin()); }
142 :
143 : /// empty - Check if the array is empty.
144 13687507 : bool empty() const { return Length == 0; }
145 :
146 0 : const T *data() const { return Data; }
147 :
148 : /// size - Get the array size.
149 0 : size_t size() const { return Length; }
150 :
151 : /// front - Get the first element.
152 0 : const T &front() const {
153 : assert(!empty());
154 0 : return Data[0];
155 : }
156 0 :
157 : /// back - Get the last element.
158 0 : const T &back() const {
159 : assert(!empty());
160 30557580 : return Data[Length-1];
161 : }
162 0 :
163 : // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
164 5650149 : template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
165 5650149 : T *Buff = A.template Allocate<T>(Length);
166 5650149 : std::uninitialized_copy(begin(), end(), Buff);
167 5650149 : return ArrayRef<T>(Buff, Length);
168 10883 : }
169 1234 :
170 1234 : /// equals - Check for element-wise equality.
171 42350914 : bool equals(ArrayRef RHS) const {
172 42519733 : if (Length != RHS.Length)
173 : return false;
174 37725953 : return std::equal(begin(), end(), RHS.begin());
175 28 : }
176 198 :
177 198 : /// slice(n, m) - Chop off the first N elements of the array, and keep M
178 0 : /// elements in the array.
179 2606 : ArrayRef<T> slice(size_t N, size_t M) const {
180 2436 : assert(N+M <= size() && "Invalid specifier");
181 40643723 : return ArrayRef<T>(data()+N, M);
182 12212421 : }
183 :
184 9258135 : /// slice(n) - Chop off the first N elements of the array.
185 28107677 : ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); }
186 33 :
187 33 : /// Drop the first \p N elements of the array.
188 90 : ArrayRef<T> drop_front(size_t N = 1) const {
189 62290 : assert(size() >= N && "Dropping more elements than exist");
190 1963486 : return slice(N, size() - N);
191 12557 : }
192 31 :
193 67649 : /// Drop the last \p N elements of the array.
194 26 : ArrayRef<T> drop_back(size_t N = 1) const {
195 12436 : assert(size() >= N && "Dropping more elements than exist");
196 1018 : return slice(0, size() - N);
197 712457 : }
198 0 :
199 2 : /// Return a copy of *this with the first N elements satisfying the
200 : /// given predicate removed.
201 265331 : template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const {
202 : return ArrayRef<T>(find_if_not(*this, Pred), end());
203 : }
204 1452561 :
205 11 : /// Return a copy of *this with the first N elements not satisfying
206 1 : /// the given predicate removed.
207 : template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const {
208 : return ArrayRef<T>(find_if(*this, Pred), end());
209 : }
210 :
211 : /// Return a copy of *this with only the first \p N elements.
212 : ArrayRef<T> take_front(size_t N = 1) const {
213 1714956 : if (N >= size())
214 280 : return *this;
215 : return drop_back(size() - N);
216 : }
217 :
218 : /// Return a copy of *this with only the last \p N elements.
219 : ArrayRef<T> take_back(size_t N = 1) const {
220 245 : if (N >= size())
221 949877 : return *this;
222 245 : return drop_front(size() - N);
223 : }
224 :
225 6277 : /// Return the first N elements of this Array that satisfy the given
226 0 : /// predicate.
227 0 : template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const {
228 : return ArrayRef<T>(begin(), find_if_not(*this, Pred));
229 0 : }
230 0 :
231 : /// Return the first N elements of this Array that don't satisfy the
232 0 : /// given predicate.
233 0 : template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const {
234 : return ArrayRef<T>(begin(), find_if(*this, Pred));
235 0 : }
236 0 :
237 : /// @}
238 : /// @name Operator Overloads
239 : /// @{
240 0 : const T &operator[](size_t Index) const {
241 0 : assert(Index < Length && "Invalid index!");
242 2043507846 : return Data[Index];
243 : }
244 0 :
245 0 : /// Disallow accidental assignment from a temporary.
246 0 : ///
247 0 : /// The declaration here is extra complicated so that "arrayRef = {}"
248 0 : /// continues to select the move assignment operator.
249 : template <typename U>
250 7820169 : typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type &
251 0 : operator=(U &&Temporary) = delete;
252 0 :
253 : /// Disallow accidental assignment from a temporary.
254 46149425 : ///
255 : /// The declaration here is extra complicated so that "arrayRef = {}"
256 0 : /// continues to select the move assignment operator.
257 : template <typename U>
258 10971697 : typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type &
259 : operator=(std::initializer_list<U>) = delete;
260 0 :
261 : /// @}
262 142803737 : /// @name Expensive Operations
263 : /// @{
264 0 : std::vector<T> vec() const {
265 56191 : return std::vector<T>(Data, Data+Length);
266 761 : }
267 :
268 0 : /// @}
269 : /// @name Conversion operators
270 0 : /// @{
271 0 : operator std::vector<T>() const {
272 268559 : return std::vector<T>(Data, Data+Length);
273 0 : }
274 0 :
275 0 : /// @}
276 0 : };
277 0 :
278 0 : /// MutableArrayRef - Represent a mutable reference to an array (0 or more
279 0 : /// elements consecutively in memory), i.e. a start pointer and a length. It
280 130001 : /// allows various APIs to take and modify consecutive elements easily and
281 0 : /// conveniently.
282 20960 : ///
283 0 : /// This class does not own the underlying data, it is expected to be used in
284 93 : /// situations where the data resides in some other buffer, whose lifetime
285 0 : /// extends past that of the MutableArrayRef. For this reason, it is not in
286 0 : /// general safe to store a MutableArrayRef.
287 0 : ///
288 325 : /// This is intended to be trivially copyable, so it should be passed by
289 0 : /// value.
290 0 : template<typename T>
291 0 : class LLVM_NODISCARD MutableArrayRef : public ArrayRef<T> {
292 4 : public:
293 : using iterator = T *;
294 0 : using reverse_iterator = std::reverse_iterator<iterator>;
295 0 :
296 0 : /// Construct an empty MutableArrayRef.
297 : /*implicit*/ MutableArrayRef() = default;
298 0 :
299 : /// Construct an empty MutableArrayRef from None.
300 135698 : /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
301 0 :
302 0 : /// Construct an MutableArrayRef from a single element.
303 7 : /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
304 0 :
305 : /// Construct an MutableArrayRef from a pointer and length.
306 0 : /*implicit*/ MutableArrayRef(T *data, size_t length)
307 : : ArrayRef<T>(data, length) {}
308 9441131 :
309 : /// Construct an MutableArrayRef from a range.
310 0 : MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
311 :
312 0 : /// Construct an MutableArrayRef from a SmallVector.
313 : /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
314 0 : : ArrayRef<T>(Vec) {}
315 :
316 110484507 : /// Construct a MutableArrayRef from a std::vector.
317 : /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
318 0 : : ArrayRef<T>(Vec) {}
319 :
320 0 : /// Construct an ArrayRef from a std::array
321 : template <size_t N>
322 0 : /*implicit*/ constexpr MutableArrayRef(std::array<T, N> &Arr)
323 : : ArrayRef<T>(Arr) {}
324 209801 :
325 : /// Construct an MutableArrayRef from a C array.
326 0 : template <size_t N>
327 : /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {}
328 144850 :
329 336300308 : T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
330 0 :
331 : iterator begin() const { return data(); }
332 63381347 : iterator end() const { return data() + this->size(); }
333 :
334 0 : reverse_iterator rbegin() const { return reverse_iterator(end()); }
335 : reverse_iterator rend() const { return reverse_iterator(begin()); }
336 541696 :
337 4616767 : /// front - Get the first element.
338 0 : T &front() const {
339 : assert(!this->empty());
340 2606124 : return data()[0];
341 47999 : }
342 0 :
343 : /// back - Get the last element.
344 9337 : T &back() const {
345 11756147 : assert(!this->empty());
346 0 : return data()[this->size()-1];
347 0 : }
348 139330813 :
349 92693 : /// slice(n, m) - Chop off the first N elements of the array, and keep M
350 0 : /// elements in the array.
351 : MutableArrayRef<T> slice(size_t N, size_t M) const {
352 229 : assert(N + M <= this->size() && "Invalid specifier");
353 41782030 : return MutableArrayRef<T>(this->data() + N, M);
354 2 : }
355 :
356 40130 : /// slice(n) - Chop off the first N elements of the array.
357 2840831 : MutableArrayRef<T> slice(size_t N) const {
358 16499159 : return slice(N, this->size() - N);
359 : }
360 6751318 :
361 52500 : /// Drop the first \p N elements of the array.
362 0 : MutableArrayRef<T> drop_front(size_t N = 1) const {
363 : assert(this->size() >= N && "Dropping more elements than exist");
364 25113776 : return slice(N, this->size() - N);
365 2947637 : }
366 0 :
367 : MutableArrayRef<T> drop_back(size_t N = 1) const {
368 30728255 : assert(this->size() >= N && "Dropping more elements than exist");
369 1044301 : return slice(0, this->size() - N);
370 9 : }
371 :
372 52571 : /// Return a copy of *this with the first N elements satisfying the
373 17846 : /// given predicate removed.
374 0 : template <class PredicateT>
375 : MutableArrayRef<T> drop_while(PredicateT Pred) const {
376 6699 : return MutableArrayRef<T>(find_if_not(*this, Pred), end());
377 3544 : }
378 0 :
379 : /// Return a copy of *this with the first N elements not satisfying
380 1044297 : /// the given predicate removed.
381 0 : template <class PredicateT>
382 5135934 : MutableArrayRef<T> drop_until(PredicateT Pred) const {
383 : return MutableArrayRef<T>(find_if(*this, Pred), end());
384 0 : }
385 :
386 0 : /// Return a copy of *this with only the first \p N elements.
387 : MutableArrayRef<T> take_front(size_t N = 1) const {
388 128 : if (N >= this->size())
389 8 : return *this;
390 0 : return drop_back(this->size() - N);
391 : }
392 0 :
393 504 : /// Return a copy of *this with only the last \p N elements.
394 0 : MutableArrayRef<T> take_back(size_t N = 1) const {
395 4 : if (N >= this->size())
396 0 : return *this;
397 4 : return drop_front(this->size() - N);
398 0 : }
399 :
400 0 : /// Return the first N elements of this Array that satisfy the given
401 : /// predicate.
402 0 : template <class PredicateT>
403 : MutableArrayRef<T> take_while(PredicateT Pred) const {
404 0 : return MutableArrayRef<T>(begin(), find_if_not(*this, Pred));
405 862302 : }
406 0 :
407 : /// Return the first N elements of this Array that don't satisfy the
408 0 : /// given predicate.
409 : template <class PredicateT>
410 0 : MutableArrayRef<T> take_until(PredicateT Pred) const {
411 : return MutableArrayRef<T>(begin(), find_if(*this, Pred));
412 0 : }
413 :
414 0 : /// @}
415 : /// @name Operator Overloads
416 0 : /// @{
417 0 : T &operator[](size_t Index) const {
418 0 : assert(Index < this->size() && "Invalid index!");
419 2000214853 : return data()[Index];
420 0 : }
421 0 : };
422 0 :
423 : /// This is a MutableArrayRef that owns its array.
424 0 : template <typename T> class OwningArrayRef : public MutableArrayRef<T> {
425 : public:
426 0 : OwningArrayRef() = default;
427 47861110 : OwningArrayRef(size_t Size) : MutableArrayRef<T>(new T[Size], Size) {}
428 0 :
429 31874 : OwningArrayRef(ArrayRef<T> Data)
430 38639 : : MutableArrayRef<T>(new T[Data.size()], Data.size()) {
431 15387327 : std::copy(Data.begin(), Data.end(), this->begin());
432 31874 : }
433 2396 :
434 2396 : OwningArrayRef(OwningArrayRef &&Other) { *this = Other; }
435 932612271 :
436 2396 : OwningArrayRef &operator=(OwningArrayRef &&Other) {
437 14739 : delete[] this->data();
438 21504 : this->MutableArrayRef<T>::operator=(Other);
439 92693 : Other.MutableArrayRef<T>::operator=(MutableArrayRef<T>());
440 14739 : return *this;
441 14739 : }
442 14739 :
443 48770343 : ~OwningArrayRef() { delete[] this->data(); }
444 14739 : };
445 :
446 0 : /// @name ArrayRef Convenience constructors
447 29666125 : /// @{
448 0 :
449 2396 : /// Construct an ArrayRef from a single element.
450 2396 : template<typename T>
451 0 : ArrayRef<T> makeArrayRef(const T &OneElt) {
452 0 : return OneElt;
453 : }
454 0 :
455 41235520 : /// Construct an ArrayRef from a pointer and length.
456 0 : template<typename T>
457 : ArrayRef<T> makeArrayRef(const T *data, size_t length) {
458 0 : return ArrayRef<T>(data, length);
459 0 : }
460 0 :
461 : /// Construct an ArrayRef from a range.
462 0 : template<typename T>
463 0 : ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
464 0 : return ArrayRef<T>(begin, end);
465 : }
466 0 :
467 : /// Construct an ArrayRef from a SmallVector.
468 0 : template <typename T>
469 : ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
470 0 : return Vec;
471 : }
472 0 :
473 : /// Construct an ArrayRef from a SmallVector.
474 0 : template <typename T, unsigned N>
475 : ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
476 0 : return Vec;
477 : }
478 0 :
479 : /// Construct an ArrayRef from a std::vector.
480 0 : template<typename T>
481 : ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
482 0 : return Vec;
483 0 : }
484 0 :
485 : /// Construct an ArrayRef from an ArrayRef (no-op) (const)
486 0 : template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) {
487 0 : return Vec;
488 0 : }
489 :
490 0 : /// Construct an ArrayRef from an ArrayRef (no-op)
491 : template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) {
492 0 : return Vec;
493 : }
494 0 :
495 0 : /// Construct an ArrayRef from a C array.
496 0 : template<typename T, size_t N>
497 : ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
498 0 : return ArrayRef<T>(Arr);
499 0 : }
500 0 :
501 : /// Construct a MutableArrayRef from a single element.
502 0 : template<typename T>
503 : MutableArrayRef<T> makeMutableArrayRef(T &OneElt) {
504 0 : return OneElt;
505 : }
506 0 :
507 0 : /// Construct a MutableArrayRef from a pointer and length.
508 0 : template<typename T>
509 : MutableArrayRef<T> makeMutableArrayRef(T *data, size_t length) {
510 0 : return MutableArrayRef<T>(data, length);
511 0 : }
512 0 :
513 : /// @}
514 0 : /// @name ArrayRef Comparison Operators
515 : /// @{
516 0 :
517 : template<typename T>
518 0 : inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
519 195398 : return LHS.equals(RHS);
520 0 : }
521 :
522 0 : template<typename T>
523 : inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
524 10541299 : return !(LHS == RHS);
525 : }
526 0 :
527 19390736 : /// @}
528 0 :
529 : // ArrayRefs can be treated like a POD type.
530 0 : template <typename T> struct isPodLike;
531 : template <typename T> struct isPodLike<ArrayRef<T>> {
532 19366586 : static const bool value = true;
533 : };
534 0 :
535 9674896 : template <typename T> hash_code hash_value(ArrayRef<T> S) {
536 0 : return hash_combine_range(S.begin(), S.end());
537 : }
538 0 :
539 : } // end namespace llvm
540 170 :
541 : #endif // LLVM_ADT_ARRAYREF_H
|
