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