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(0), Length(0) {}
52 
53     /// Construct an empty ArrayRef from None.
54     /*implicit*/ ArrayRef(NoneType) : Data(0), 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.empty() ? (T*)0 : &Vec[0]), 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     /// equals - Check for element-wise equality.
124     bool equals(ArrayRef RHS) const {
125       if (Length != RHS.Length)
126         return false;
127       for (size_type i = 0; i != Length; i++)
128         if (Data[i] != RHS.Data[i])
129           return false;
130       return true;
131     }
132 
133     /// slice(n) - Chop off the first N elements of the array.
134     ArrayRef<T> slice(unsigned N) const {
135       assert(N <= size() && "Invalid specifier");
136       return ArrayRef<T>(data()+N, size()-N);
137     }
138 
139     /// slice(n, m) - Chop off the first N elements of the array, and keep M
140     /// elements in the array.
141     ArrayRef<T> slice(unsigned N, unsigned M) const {
142       assert(N+M <= size() && "Invalid specifier");
143       return ArrayRef<T>(data()+N, M);
144     }
145 
146     /// @}
147     /// @name Operator Overloads
148     /// @{
149     const T &operator[](size_t Index) const {
150       assert(Index < Length && "Invalid index!");
151       return Data[Index];
152     }
153 
154     /// @}
155     /// @name Expensive Operations
156     /// @{
157     std::vector<T> vec() const {
158       return std::vector<T>(Data, Data+Length);
159     }
160 
161     /// @}
162     /// @name Conversion operators
163     /// @{
164     operator std::vector<T>() const {
165       return std::vector<T>(Data, Data+Length);
166     }
167 
168     /// @}
169   };
170 
171   /// MutableArrayRef - Represent a mutable reference to an array (0 or more
172   /// elements consecutively in memory), i.e. a start pointer and a length.  It
173   /// allows various APIs to take and modify consecutive elements easily and
174   /// conveniently.
175   ///
176   /// This class does not own the underlying data, it is expected to be used in
177   /// situations where the data resides in some other buffer, whose lifetime
178   /// extends past that of the MutableArrayRef. For this reason, it is not in
179   /// general safe to store a MutableArrayRef.
180   ///
181   /// This is intended to be trivially copyable, so it should be passed by
182   /// value.
183   template<typename T>
184   class MutableArrayRef : public ArrayRef<T> {
185   public:
186     typedef T *iterator;
187 
188     /// Construct an empty MutableArrayRef.
189     /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
190 
191     /// Construct an empty MutableArrayRef from None.
192     /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
193 
194     /// Construct an MutableArrayRef from a single element.
195     /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
196 
197     /// Construct an MutableArrayRef from a pointer and length.
198     /*implicit*/ MutableArrayRef(T *data, size_t length)
199       : ArrayRef<T>(data, length) {}
200 
201     /// Construct an MutableArrayRef from a range.
202     MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
203 
204     /// Construct an MutableArrayRef from a SmallVector.
205     /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
206     : ArrayRef<T>(Vec) {}
207 
208     /// Construct a MutableArrayRef from a std::vector.
209     /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
210     : ArrayRef<T>(Vec) {}
211 
212     /// Construct an MutableArrayRef from a C array.
213     template <size_t N>
214     /*implicit*/ MutableArrayRef(T (&Arr)[N])
215       : ArrayRef<T>(Arr) {}
216 
217     T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
218 
219     iterator begin() const { return data(); }
220     iterator end() const { return data() + this->size(); }
221 
222     /// front - Get the first element.
223     T &front() const {
224       assert(!this->empty());
225       return data()[0];
226     }
227 
228     /// back - Get the last element.
229     T &back() const {
230       assert(!this->empty());
231       return data()[this->size()-1];
232     }
233 
234     /// slice(n) - Chop off the first N elements of the array.
235     MutableArrayRef<T> slice(unsigned N) const {
236       assert(N <= this->size() && "Invalid specifier");
237       return MutableArrayRef<T>(data()+N, this->size()-N);
238     }
239 
240     /// slice(n, m) - Chop off the first N elements of the array, and keep M
241     /// elements in the array.
242     MutableArrayRef<T> slice(unsigned N, unsigned M) const {
243       assert(N+M <= this->size() && "Invalid specifier");
244       return MutableArrayRef<T>(data()+N, M);
245     }
246 
247     /// @}
248     /// @name Operator Overloads
249     /// @{
250     T &operator[](size_t Index) const {
251       assert(Index < this->size() && "Invalid index!");
252       return data()[Index];
253     }
254   };
255 
256   /// @name ArrayRef Convenience constructors
257   /// @{
258 
259   /// Construct an ArrayRef from a single element.
260   template<typename T>
261   ArrayRef<T> makeArrayRef(const T &OneElt) {
262     return OneElt;
263   }
264 
265   /// Construct an ArrayRef from a pointer and length.
266   template<typename T>
267   ArrayRef<T> makeArrayRef(const T *data, size_t length) {
268     return ArrayRef<T>(data, length);
269   }
270 
271   /// Construct an ArrayRef from a range.
272   template<typename T>
273   ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
274     return ArrayRef<T>(begin, end);
275   }
276 
277   /// Construct an ArrayRef from a SmallVector.
278   template <typename T>
279   ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
280     return Vec;
281   }
282 
283   /// Construct an ArrayRef from a SmallVector.
284   template <typename T, unsigned N>
285   ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
286     return Vec;
287   }
288 
289   /// Construct an ArrayRef from a std::vector.
290   template<typename T>
291   ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
292     return Vec;
293   }
294 
295   /// Construct an ArrayRef from a C array.
296   template<typename T, size_t N>
297   ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
298     return ArrayRef<T>(Arr);
299   }
300 
301   /// @}
302   /// @name ArrayRef Comparison Operators
303   /// @{
304 
305   template<typename T>
306   inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
307     return LHS.equals(RHS);
308   }
309 
310   template<typename T>
311   inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
312     return !(LHS == RHS);
313   }
314 
315   /// @}
316 
317   // ArrayRefs can be treated like a POD type.
318   template <typename T> struct isPodLike;
319   template <typename T> struct isPodLike<ArrayRef<T> > {
320     static const bool value = true;
321   };
322 }
323 
324 #endif
325