0fff505d8d012e8b49a5e31bba55ebbe9736b807
[oota-llvm.git] / include / llvm / ADT / ArrayRef.h
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/None.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include <vector>
16
17 namespace llvm {
18
19   /// ArrayRef - Represent a constant reference to an array (0 or more elements
20   /// consecutively in memory), i.e. a start pointer and a length.  It allows
21   /// various APIs to take consecutive elements easily and conveniently.
22   ///
23   /// This class does not own the underlying data, it is expected to be used in
24   /// situations where the data resides in some other buffer, whose lifetime
25   /// extends past that of the ArrayRef. For this reason, it is not in general
26   /// safe to store an ArrayRef.
27   ///
28   /// This is intended to be trivially copyable, so it should be passed by
29   /// value.
30   template<typename T>
31   class ArrayRef {
32   public:
33     typedef const T *iterator;
34     typedef const T *const_iterator;
35     typedef size_t size_type;
36
37     typedef std::reverse_iterator<iterator> reverse_iterator;
38
39   private:
40     /// The start of the array, in an external buffer.
41     const T *Data;
42
43     /// The number of elements.
44     size_type Length;
45
46   public:
47     /// @name Constructors
48     /// @{
49
50     /// Construct an empty ArrayRef.
51     /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {}
52
53     /// Construct an empty ArrayRef from None.
54     /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {}
55
56     /// Construct an ArrayRef from a single element.
57     /*implicit*/ ArrayRef(const T &OneElt)
58       : Data(&OneElt), Length(1) {}
59
60     /// Construct an ArrayRef from a pointer and length.
61     /*implicit*/ ArrayRef(const T *data, size_t length)
62       : Data(data), Length(length) {}
63
64     /// Construct an ArrayRef from a range.
65     ArrayRef(const T *begin, const T *end)
66       : Data(begin), Length(end - begin) {}
67
68     /// Construct an ArrayRef from a SmallVector. This is templated in order to
69     /// avoid instantiating SmallVectorTemplateCommon<T> whenever we
70     /// copy-construct an ArrayRef.
71     template<typename U>
72     /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
73       : Data(Vec.data()), Length(Vec.size()) {
74     }
75
76     /// Construct an ArrayRef from a std::vector.
77     template<typename A>
78     /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
79       : Data(Vec.data()), Length(Vec.size()) {}
80
81     /// Construct an ArrayRef from a C array.
82     template <size_t N>
83     /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N])
84       : Data(Arr), Length(N) {}
85
86 #if LLVM_HAS_INITIALIZER_LISTS
87     /// Construct an ArrayRef from a std::initializer_list.
88     /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
89     : Data(Vec.begin() == Vec.end() ? (T*)0 : Vec.begin()),
90       Length(Vec.size()) {}
91 #endif
92
93     /// @}
94     /// @name Simple Operations
95     /// @{
96
97     iterator begin() const { return Data; }
98     iterator end() const { return Data + Length; }
99
100     reverse_iterator rbegin() const { return reverse_iterator(end()); }
101     reverse_iterator rend() const { return reverse_iterator(begin()); }
102
103     /// empty - Check if the array is empty.
104     bool empty() const { return Length == 0; }
105
106     const T *data() const { return Data; }
107
108     /// size - Get the array size.
109     size_t size() const { return Length; }
110
111     /// front - Get the first element.
112     const T &front() const {
113       assert(!empty());
114       return Data[0];
115     }
116
117     /// back - Get the last element.
118     const T &back() const {
119       assert(!empty());
120       return Data[Length-1];
121     }
122
123     // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
124     template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
125       T *Buff = A.template Allocate<T>(Length);
126       std::copy(begin(), end(), Buff);
127       return ArrayRef<T>(Buff, Length);
128     }
129
130     /// equals - Check for element-wise equality.
131     bool equals(ArrayRef RHS) const {
132       if (Length != RHS.Length)
133         return false;
134       return std::equal(begin(), end(), RHS.begin());
135     }
136
137     /// slice(n) - Chop off the first N elements of the array.
138     ArrayRef<T> slice(unsigned N) const {
139       assert(N <= size() && "Invalid specifier");
140       return ArrayRef<T>(data()+N, size()-N);
141     }
142
143     /// slice(n, m) - Chop off the first N elements of the array, and keep M
144     /// elements in the array.
145     ArrayRef<T> slice(unsigned N, unsigned M) const {
146       assert(N+M <= size() && "Invalid specifier");
147       return ArrayRef<T>(data()+N, M);
148     }
149
150     // \brief Drop the last \p N elements of the array.
151     ArrayRef<T> drop_back(unsigned N = 1) const {
152       assert(size() >= N && "Dropping more elements than exist");
153       return slice(0, size() - N);
154     }
155
156     /// @}
157     /// @name Operator Overloads
158     /// @{
159     const T &operator[](size_t Index) const {
160       assert(Index < Length && "Invalid index!");
161       return Data[Index];
162     }
163
164     /// @}
165     /// @name Expensive Operations
166     /// @{
167     std::vector<T> vec() const {
168       return std::vector<T>(Data, Data+Length);
169     }
170
171     /// @}
172     /// @name Conversion operators
173     /// @{
174     operator std::vector<T>() const {
175       return std::vector<T>(Data, Data+Length);
176     }
177
178     /// @}
179   };
180
181   /// MutableArrayRef - Represent a mutable reference to an array (0 or more
182   /// elements consecutively in memory), i.e. a start pointer and a length.  It
183   /// allows various APIs to take and modify consecutive elements easily and
184   /// conveniently.
185   ///
186   /// This class does not own the underlying data, it is expected to be used in
187   /// situations where the data resides in some other buffer, whose lifetime
188   /// extends past that of the MutableArrayRef. For this reason, it is not in
189   /// general safe to store a MutableArrayRef.
190   ///
191   /// This is intended to be trivially copyable, so it should be passed by
192   /// value.
193   template<typename T>
194   class MutableArrayRef : public ArrayRef<T> {
195   public:
196     typedef T *iterator;
197
198     typedef std::reverse_iterator<iterator> reverse_iterator;
199
200     /// Construct an empty MutableArrayRef.
201     /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
202
203     /// Construct an empty MutableArrayRef from None.
204     /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
205
206     /// Construct an MutableArrayRef from a single element.
207     /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
208
209     /// Construct an MutableArrayRef from a pointer and length.
210     /*implicit*/ MutableArrayRef(T *data, size_t length)
211       : ArrayRef<T>(data, length) {}
212
213     /// Construct an MutableArrayRef from a range.
214     MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
215
216     /// Construct an MutableArrayRef from a SmallVector.
217     /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
218     : ArrayRef<T>(Vec) {}
219
220     /// Construct a MutableArrayRef from a std::vector.
221     /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
222     : ArrayRef<T>(Vec) {}
223
224     /// Construct an MutableArrayRef from a C array.
225     template <size_t N>
226     /*implicit*/ LLVM_CONSTEXPR MutableArrayRef(T (&Arr)[N])
227       : ArrayRef<T>(Arr) {}
228
229     T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
230
231     iterator begin() const { return data(); }
232     iterator end() const { return data() + this->size(); }
233
234     reverse_iterator rbegin() const { return reverse_iterator(end()); }
235     reverse_iterator rend() const { return reverse_iterator(begin()); }
236
237     /// front - Get the first element.
238     T &front() const {
239       assert(!this->empty());
240       return data()[0];
241     }
242
243     /// back - Get the last element.
244     T &back() const {
245       assert(!this->empty());
246       return data()[this->size()-1];
247     }
248
249     /// slice(n) - Chop off the first N elements of the array.
250     MutableArrayRef<T> slice(unsigned N) const {
251       assert(N <= this->size() && "Invalid specifier");
252       return MutableArrayRef<T>(data()+N, this->size()-N);
253     }
254
255     /// slice(n, m) - Chop off the first N elements of the array, and keep M
256     /// elements in the array.
257     MutableArrayRef<T> slice(unsigned N, unsigned M) const {
258       assert(N+M <= this->size() && "Invalid specifier");
259       return MutableArrayRef<T>(data()+N, M);
260     }
261
262     /// @}
263     /// @name Operator Overloads
264     /// @{
265     T &operator[](size_t Index) const {
266       assert(Index < this->size() && "Invalid index!");
267       return data()[Index];
268     }
269   };
270
271   /// @name ArrayRef Convenience constructors
272   /// @{
273
274   /// Construct an ArrayRef from a single element.
275   template<typename T>
276   ArrayRef<T> makeArrayRef(const T &OneElt) {
277     return OneElt;
278   }
279
280   /// Construct an ArrayRef from a pointer and length.
281   template<typename T>
282   ArrayRef<T> makeArrayRef(const T *data, size_t length) {
283     return ArrayRef<T>(data, length);
284   }
285
286   /// Construct an ArrayRef from a range.
287   template<typename T>
288   ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
289     return ArrayRef<T>(begin, end);
290   }
291
292   /// Construct an ArrayRef from a SmallVector.
293   template <typename T>
294   ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
295     return Vec;
296   }
297
298   /// Construct an ArrayRef from a SmallVector.
299   template <typename T, unsigned N>
300   ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
301     return Vec;
302   }
303
304   /// Construct an ArrayRef from a std::vector.
305   template<typename T>
306   ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
307     return Vec;
308   }
309
310   /// Construct an ArrayRef from a C array.
311   template<typename T, size_t N>
312   ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
313     return ArrayRef<T>(Arr);
314   }
315
316   /// @}
317   /// @name ArrayRef Comparison Operators
318   /// @{
319
320   template<typename T>
321   inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
322     return LHS.equals(RHS);
323   }
324
325   template<typename T>
326   inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
327     return !(LHS == RHS);
328   }
329
330   /// @}
331
332   // ArrayRefs can be treated like a POD type.
333   template <typename T> struct isPodLike;
334   template <typename T> struct isPodLike<ArrayRef<T> > {
335     static const bool value = true;
336   };
337 }
338
339 #endif