1 //===- ArrayRef.h - Array Reference Wrapper ---------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_ADT_ARRAYREF_H
11 #define LLVM_ADT_ARRAYREF_H
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"
22 #include <initializer_list>
25 #include <type_traits>
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.
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.
39 /// This is intended to be trivially copyable, so it should be passed by
42 class LLVM_NODISCARD ArrayRef {
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>;
50 /// The start of the array, in an external buffer.
51 const T *Data = nullptr;
53 /// The number of elements.
57 /// @name Constructors
60 /// Construct an empty ArrayRef.
61 /*implicit*/ ArrayRef() = default;
63 /// Construct an empty ArrayRef from None.
64 /*implicit*/ ArrayRef(NoneType) {}
66 /// Construct an ArrayRef from a single element.
67 /*implicit*/ ArrayRef(const T &OneElt)
68 : Data(&OneElt), Length(1) {}
70 /// Construct an ArrayRef from a pointer and length.
71 /*implicit*/ ArrayRef(const T *data, size_t length)
72 : Data(data), Length(length) {}
74 /// Construct an ArrayRef from a range.
75 ArrayRef(const T *begin, const T *end)
76 : Data(begin), Length(end - begin) {}
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.
82 /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
83 : Data(Vec.data()), Length(Vec.size()) {
86 /// Construct an ArrayRef from a std::vector.
88 /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
89 : Data(Vec.data()), Length(Vec.size()) {}
91 /// Construct an ArrayRef from a std::array
93 /*implicit*/ constexpr ArrayRef(const std::array<T, N> &Arr)
94 : Data(Arr.data()), Length(N) {}
96 /// Construct an ArrayRef from a C array.
98 /*implicit*/ constexpr ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {}
100 /// Construct an ArrayRef from a std::initializer_list.
101 /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
102 : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()),
103 Length(Vec.size()) {}
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>
109 const ArrayRef<U *> &A,
110 typename std::enable_if<
111 std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
112 : Data(A.data()), Length(A.size()) {}
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 /*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 : Data(Vec.data()), Length(Vec.size()) {
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 ArrayRef(const std::vector<U *, A> &Vec,
129 typename std::enable_if<
130 std::is_convertible<U *const *, T const *>::value>::type* = 0)
131 : Data(Vec.data()), Length(Vec.size()) {}
134 /// @name Simple Operations
137 iterator begin() const { return Data; }
138 iterator end() const { return Data + Length; }
140 reverse_iterator rbegin() const { return reverse_iterator(end()); }
141 reverse_iterator rend() const { return reverse_iterator(begin()); }
143 /// empty - Check if the array is empty.
144 bool empty() const { return Length == 0; }
146 const T *data() const { return Data; }
148 /// size - Get the array size.
149 size_t size() const { return Length; }
151 /// front - Get the first element.
152 const T &front() const {
157 /// back - Get the last element.
158 const T &back() const {
160 return Data[Length-1];
163 // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
164 template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
165 T *Buff = A.template Allocate<T>(Length);
166 std::uninitialized_copy(begin(), end(), Buff);
167 return ArrayRef<T>(Buff, Length);
170 /// equals - Check for element-wise equality.
171 bool equals(ArrayRef RHS) const {
172 if (Length != RHS.Length)
174 return std::equal(begin(), end(), RHS.begin());
177 /// slice(n, m) - Chop off the first N elements of the array, and keep M
178 /// elements in the array.
179 ArrayRef<T> slice(size_t N, size_t M) const {
180 assert(N+M <= size() && "Invalid specifier");
181 return ArrayRef<T>(data()+N, M);
184 /// slice(n) - Chop off the first N elements of the array.
185 ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); }
187 /// \brief Drop the first \p N elements of the array.
188 ArrayRef<T> drop_front(size_t N = 1) const {
189 assert(size() >= N && "Dropping more elements than exist");
190 return slice(N, size() - N);
193 /// \brief Drop the last \p N elements of the array.
194 ArrayRef<T> drop_back(size_t N = 1) const {
195 assert(size() >= N && "Dropping more elements than exist");
196 return slice(0, size() - N);
199 /// \brief Return a copy of *this with the first N elements satisfying the
200 /// given predicate removed.
201 template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const {
202 return ArrayRef<T>(find_if_not(*this, Pred), end());
205 /// \brief Return a copy of *this with the first N elements not satisfying
206 /// the given predicate removed.
207 template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const {
208 return ArrayRef<T>(find_if(*this, Pred), end());
211 /// \brief Return a copy of *this with only the first \p N elements.
212 ArrayRef<T> take_front(size_t N = 1) const {
215 return drop_back(size() - N);
218 /// \brief Return a copy of *this with only the last \p N elements.
219 ArrayRef<T> take_back(size_t N = 1) const {
222 return drop_front(size() - N);
225 /// \brief Return the first N elements of this Array that satisfy the given
227 template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const {
228 return ArrayRef<T>(begin(), find_if_not(*this, Pred));
231 /// \brief Return the first N elements of this Array that don't satisfy the
233 template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const {
234 return ArrayRef<T>(begin(), find_if(*this, Pred));
238 /// @name Operator Overloads
240 const T &operator[](size_t Index) const {
241 assert(Index < Length && "Invalid index!");
245 /// Disallow accidental assignment from a temporary.
247 /// The declaration here is extra complicated so that "arrayRef = {}"
248 /// continues to select the move assignment operator.
249 template <typename U>
250 typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type &
251 operator=(U &&Temporary) = delete;
253 /// Disallow accidental assignment from a temporary.
255 /// The declaration here is extra complicated so that "arrayRef = {}"
256 /// continues to select the move assignment operator.
257 template <typename U>
258 typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type &
259 operator=(std::initializer_list<U>) = delete;
262 /// @name Expensive Operations
264 std::vector<T> vec() const {
265 return std::vector<T>(Data, Data+Length);
269 /// @name Conversion operators
271 operator std::vector<T>() const {
272 return std::vector<T>(Data, Data+Length);
278 /// MutableArrayRef - Represent a mutable reference to an array (0 or more
279 /// elements consecutively in memory), i.e. a start pointer and a length. It
280 /// allows various APIs to take and modify consecutive elements easily and
283 /// This class does not own the underlying data, it is expected to be used in
284 /// situations where the data resides in some other buffer, whose lifetime
285 /// extends past that of the MutableArrayRef. For this reason, it is not in
286 /// general safe to store a MutableArrayRef.
288 /// This is intended to be trivially copyable, so it should be passed by
291 class LLVM_NODISCARD MutableArrayRef : public ArrayRef<T> {
293 using iterator = T *;
294 using reverse_iterator = std::reverse_iterator<iterator>;
296 /// Construct an empty MutableArrayRef.
297 /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
299 /// Construct an empty MutableArrayRef from None.
300 /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
302 /// Construct an MutableArrayRef from a single element.
303 /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
305 /// Construct an MutableArrayRef from a pointer and length.
306 /*implicit*/ MutableArrayRef(T *data, size_t length)
307 : ArrayRef<T>(data, length) {}
309 /// Construct an MutableArrayRef from a range.
310 MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
312 /// Construct an MutableArrayRef from a SmallVector.
313 /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
314 : ArrayRef<T>(Vec) {}
316 /// Construct a MutableArrayRef from a std::vector.
317 /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
318 : ArrayRef<T>(Vec) {}
320 /// Construct an ArrayRef from a std::array
322 /*implicit*/ constexpr MutableArrayRef(std::array<T, N> &Arr)
323 : ArrayRef<T>(Arr) {}
325 /// Construct an MutableArrayRef from a C array.
327 /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {}
329 T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
331 iterator begin() const { return data(); }
332 iterator end() const { return data() + this->size(); }
334 reverse_iterator rbegin() const { return reverse_iterator(end()); }
335 reverse_iterator rend() const { return reverse_iterator(begin()); }
337 /// front - Get the first element.
339 assert(!this->empty());
343 /// back - Get the last element.
345 assert(!this->empty());
346 return data()[this->size()-1];
349 /// slice(n, m) - Chop off the first N elements of the array, and keep M
350 /// elements in the array.
351 MutableArrayRef<T> slice(size_t N, size_t M) const {
352 assert(N + M <= this->size() && "Invalid specifier");
353 return MutableArrayRef<T>(this->data() + N, M);
356 /// slice(n) - Chop off the first N elements of the array.
357 MutableArrayRef<T> slice(size_t N) const {
358 return slice(N, this->size() - N);
361 /// \brief Drop the first \p N elements of the array.
362 MutableArrayRef<T> drop_front(size_t N = 1) const {
363 assert(this->size() >= N && "Dropping more elements than exist");
364 return slice(N, this->size() - N);
367 MutableArrayRef<T> drop_back(size_t N = 1) const {
368 assert(this->size() >= N && "Dropping more elements than exist");
369 return slice(0, this->size() - N);
372 /// \brief Return a copy of *this with the first N elements satisfying the
373 /// given predicate removed.
374 template <class PredicateT>
375 MutableArrayRef<T> drop_while(PredicateT Pred) const {
376 return MutableArrayRef<T>(find_if_not(*this, Pred), end());
379 /// \brief Return a copy of *this with the first N elements not satisfying
380 /// the given predicate removed.
381 template <class PredicateT>
382 MutableArrayRef<T> drop_until(PredicateT Pred) const {
383 return MutableArrayRef<T>(find_if(*this, Pred), end());
386 /// \brief Return a copy of *this with only the first \p N elements.
387 MutableArrayRef<T> take_front(size_t N = 1) const {
388 if (N >= this->size())
390 return drop_back(this->size() - N);
393 /// \brief Return a copy of *this with only the last \p N elements.
394 MutableArrayRef<T> take_back(size_t N = 1) const {
395 if (N >= this->size())
397 return drop_front(this->size() - N);
400 /// \brief Return the first N elements of this Array that satisfy the given
402 template <class PredicateT>
403 MutableArrayRef<T> take_while(PredicateT Pred) const {
404 return MutableArrayRef<T>(begin(), find_if_not(*this, Pred));
407 /// \brief Return the first N elements of this Array that don't satisfy the
409 template <class PredicateT>
410 MutableArrayRef<T> take_until(PredicateT Pred) const {
411 return MutableArrayRef<T>(begin(), find_if(*this, Pred));
415 /// @name Operator Overloads
417 T &operator[](size_t Index) const {
418 assert(Index < this->size() && "Invalid index!");
419 return data()[Index];
423 /// This is a MutableArrayRef that owns its array.
424 template <typename T> class OwningArrayRef : public MutableArrayRef<T> {
426 OwningArrayRef() = default;
427 OwningArrayRef(size_t Size) : MutableArrayRef<T>(new T[Size], Size) {}
429 OwningArrayRef(ArrayRef<T> Data)
430 : MutableArrayRef<T>(new T[Data.size()], Data.size()) {
431 std::copy(Data.begin(), Data.end(), this->begin());
434 OwningArrayRef(OwningArrayRef &&Other) { *this = Other; }
436 OwningArrayRef &operator=(OwningArrayRef &&Other) {
437 delete[] this->data();
438 this->MutableArrayRef<T>::operator=(Other);
439 Other.MutableArrayRef<T>::operator=(MutableArrayRef<T>());
443 ~OwningArrayRef() { delete[] this->data(); }
446 /// @name ArrayRef Convenience constructors
449 /// Construct an ArrayRef from a single element.
451 ArrayRef<T> makeArrayRef(const T &OneElt) {
455 /// Construct an ArrayRef from a pointer and length.
457 ArrayRef<T> makeArrayRef(const T *data, size_t length) {
458 return ArrayRef<T>(data, length);
461 /// Construct an ArrayRef from a range.
463 ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
464 return ArrayRef<T>(begin, end);
467 /// Construct an ArrayRef from a SmallVector.
468 template <typename T>
469 ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
473 /// Construct an ArrayRef from a SmallVector.
474 template <typename T, unsigned N>
475 ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
479 /// Construct an ArrayRef from a std::vector.
481 ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
485 /// Construct an ArrayRef from an ArrayRef (no-op) (const)
486 template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) {
490 /// Construct an ArrayRef from an ArrayRef (no-op)
491 template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) {
495 /// Construct an ArrayRef from a C array.
496 template<typename T, size_t N>
497 ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
498 return ArrayRef<T>(Arr);
501 /// Construct a MutableArrayRef from a single element.
503 MutableArrayRef<T> makeMutableArrayRef(T &OneElt) {
507 /// Construct a MutableArrayRef from a pointer and length.
509 MutableArrayRef<T> makeMutableArrayRef(T *data, size_t length) {
510 return MutableArrayRef<T>(data, length);
514 /// @name ArrayRef Comparison Operators
518 inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
519 return LHS.equals(RHS);
523 inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
524 return !(LHS == RHS);
529 // ArrayRefs can be treated like a POD type.
530 template <typename T> struct isPodLike;
531 template <typename T> struct isPodLike<ArrayRef<T>> {
532 static const bool value = true;
535 template <typename T> hash_code hash_value(ArrayRef<T> S) {
536 return hash_combine_range(S.begin(), S.end());
539 } // end namespace llvm
541 #endif // LLVM_ADT_ARRAYREF_H