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 17namespace 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 340