1218885Sdim//===--- ArrayRef.h - Array Reference Wrapper -------------------*- C++ -*-===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim 10218885Sdim#ifndef LLVM_ADT_ARRAYREF_H 11218885Sdim#define LLVM_ADT_ARRAYREF_H 12218885Sdim 13251662Sdim#include "llvm/ADT/None.h" 14218885Sdim#include "llvm/ADT/SmallVector.h" 15218885Sdim#include <vector> 16218885Sdim 17218885Sdimnamespace llvm { 18234353Sdim 19218885Sdim /// ArrayRef - Represent a constant reference to an array (0 or more elements 20218885Sdim /// consecutively in memory), i.e. a start pointer and a length. It allows 21218885Sdim /// various APIs to take consecutive elements easily and conveniently. 22218885Sdim /// 23218885Sdim /// This class does not own the underlying data, it is expected to be used in 24218885Sdim /// situations where the data resides in some other buffer, whose lifetime 25221345Sdim /// extends past that of the ArrayRef. For this reason, it is not in general 26221345Sdim /// safe to store an ArrayRef. 27218885Sdim /// 28218885Sdim /// This is intended to be trivially copyable, so it should be passed by 29218885Sdim /// value. 30218885Sdim template<typename T> 31218885Sdim class ArrayRef { 32218885Sdim public: 33218885Sdim typedef const T *iterator; 34218885Sdim typedef const T *const_iterator; 35218885Sdim typedef size_t size_type; 36234353Sdim 37249423Sdim typedef std::reverse_iterator<iterator> reverse_iterator; 38249423Sdim 39218885Sdim private: 40218885Sdim /// The start of the array, in an external buffer. 41218885Sdim const T *Data; 42234353Sdim 43218885Sdim /// The number of elements. 44224145Sdim size_type Length; 45234353Sdim 46218885Sdim public: 47218885Sdim /// @name Constructors 48218885Sdim /// @{ 49234353Sdim 50218885Sdim /// Construct an empty ArrayRef. 51218885Sdim /*implicit*/ ArrayRef() : Data(0), Length(0) {} 52234353Sdim 53251662Sdim /// Construct an empty ArrayRef from None. 54251662Sdim /*implicit*/ ArrayRef(NoneType) : Data(0), Length(0) {} 55251662Sdim 56218885Sdim /// Construct an ArrayRef from a single element. 57218885Sdim /*implicit*/ ArrayRef(const T &OneElt) 58218885Sdim : Data(&OneElt), Length(1) {} 59234353Sdim 60218885Sdim /// Construct an ArrayRef from a pointer and length. 61218885Sdim /*implicit*/ ArrayRef(const T *data, size_t length) 62218885Sdim : Data(data), Length(length) {} 63234353Sdim 64224145Sdim /// Construct an ArrayRef from a range. 65224145Sdim ArrayRef(const T *begin, const T *end) 66224145Sdim : Data(begin), Length(end - begin) {} 67234353Sdim 68243830Sdim /// Construct an ArrayRef from a SmallVector. This is templated in order to 69243830Sdim /// avoid instantiating SmallVectorTemplateCommon<T> whenever we 70243830Sdim /// copy-construct an ArrayRef. 71243830Sdim template<typename U> 72243830Sdim /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec) 73243830Sdim : Data(Vec.data()), Length(Vec.size()) { 74243830Sdim } 75218885Sdim 76218885Sdim /// Construct an ArrayRef from a std::vector. 77243830Sdim template<typename A> 78243830Sdim /*implicit*/ ArrayRef(const std::vector<T, A> &Vec) 79218885Sdim : Data(Vec.empty() ? (T*)0 : &Vec[0]), Length(Vec.size()) {} 80234353Sdim 81219077Sdim /// Construct an ArrayRef from a C array. 82219077Sdim template <size_t N> 83263508Sdim /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N]) 84219077Sdim : Data(Arr), Length(N) {} 85234353Sdim 86263508Sdim#if LLVM_HAS_INITIALIZER_LISTS 87263508Sdim /// Construct an ArrayRef from a std::initializer_list. 88263508Sdim /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec) 89263508Sdim : Data(Vec.begin() == Vec.end() ? (T*)0 : Vec.begin()), 90263508Sdim Length(Vec.size()) {} 91263508Sdim#endif 92263508Sdim 93218885Sdim /// @} 94218885Sdim /// @name Simple Operations 95218885Sdim /// @{ 96218885Sdim 97218885Sdim iterator begin() const { return Data; } 98218885Sdim iterator end() const { return Data + Length; } 99234353Sdim 100249423Sdim reverse_iterator rbegin() const { return reverse_iterator(end()); } 101249423Sdim reverse_iterator rend() const { return reverse_iterator(begin()); } 102249423Sdim 103218885Sdim /// empty - Check if the array is empty. 104218885Sdim bool empty() const { return Length == 0; } 105234353Sdim 106221345Sdim const T *data() const { return Data; } 107234353Sdim 108218885Sdim /// size - Get the array size. 109218885Sdim size_t size() const { return Length; } 110234353Sdim 111218885Sdim /// front - Get the first element. 112218885Sdim const T &front() const { 113218885Sdim assert(!empty()); 114218885Sdim return Data[0]; 115218885Sdim } 116234353Sdim 117218885Sdim /// back - Get the last element. 118218885Sdim const T &back() const { 119218885Sdim assert(!empty()); 120218885Sdim return Data[Length-1]; 121218885Sdim } 122234353Sdim 123224145Sdim /// equals - Check for element-wise equality. 124224145Sdim bool equals(ArrayRef RHS) const { 125224145Sdim if (Length != RHS.Length) 126224145Sdim return false; 127224145Sdim for (size_type i = 0; i != Length; i++) 128224145Sdim if (Data[i] != RHS.Data[i]) 129224145Sdim return false; 130224145Sdim return true; 131224145Sdim } 132224145Sdim 133221345Sdim /// slice(n) - Chop off the first N elements of the array. 134234353Sdim ArrayRef<T> slice(unsigned N) const { 135221345Sdim assert(N <= size() && "Invalid specifier"); 136221345Sdim return ArrayRef<T>(data()+N, size()-N); 137221345Sdim } 138221345Sdim 139221345Sdim /// slice(n, m) - Chop off the first N elements of the array, and keep M 140221345Sdim /// elements in the array. 141234353Sdim ArrayRef<T> slice(unsigned N, unsigned M) const { 142221345Sdim assert(N+M <= size() && "Invalid specifier"); 143221345Sdim return ArrayRef<T>(data()+N, M); 144221345Sdim } 145234353Sdim 146218885Sdim /// @} 147218885Sdim /// @name Operator Overloads 148218885Sdim /// @{ 149218885Sdim const T &operator[](size_t Index) const { 150218885Sdim assert(Index < Length && "Invalid index!"); 151218885Sdim return Data[Index]; 152218885Sdim } 153234353Sdim 154218885Sdim /// @} 155218885Sdim /// @name Expensive Operations 156218885Sdim /// @{ 157218885Sdim std::vector<T> vec() const { 158218885Sdim return std::vector<T>(Data, Data+Length); 159218885Sdim } 160234353Sdim 161218885Sdim /// @} 162224145Sdim /// @name Conversion operators 163224145Sdim /// @{ 164224145Sdim operator std::vector<T>() const { 165224145Sdim return std::vector<T>(Data, Data+Length); 166224145Sdim } 167234353Sdim 168234353Sdim /// @} 169234353Sdim }; 170234353Sdim 171234353Sdim /// MutableArrayRef - Represent a mutable reference to an array (0 or more 172234353Sdim /// elements consecutively in memory), i.e. a start pointer and a length. It 173234353Sdim /// allows various APIs to take and modify consecutive elements easily and 174234353Sdim /// conveniently. 175234353Sdim /// 176234353Sdim /// This class does not own the underlying data, it is expected to be used in 177234353Sdim /// situations where the data resides in some other buffer, whose lifetime 178234353Sdim /// extends past that of the MutableArrayRef. For this reason, it is not in 179234353Sdim /// general safe to store a MutableArrayRef. 180234353Sdim /// 181234353Sdim /// This is intended to be trivially copyable, so it should be passed by 182234353Sdim /// value. 183234353Sdim template<typename T> 184234353Sdim class MutableArrayRef : public ArrayRef<T> { 185234353Sdim public: 186234353Sdim typedef T *iterator; 187234353Sdim 188263508Sdim typedef std::reverse_iterator<iterator> reverse_iterator; 189263508Sdim 190251662Sdim /// Construct an empty MutableArrayRef. 191234353Sdim /*implicit*/ MutableArrayRef() : ArrayRef<T>() {} 192249423Sdim 193251662Sdim /// Construct an empty MutableArrayRef from None. 194251662Sdim /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {} 195251662Sdim 196234353Sdim /// Construct an MutableArrayRef from a single element. 197234353Sdim /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {} 198249423Sdim 199234353Sdim /// Construct an MutableArrayRef from a pointer and length. 200234353Sdim /*implicit*/ MutableArrayRef(T *data, size_t length) 201234353Sdim : ArrayRef<T>(data, length) {} 202249423Sdim 203234353Sdim /// Construct an MutableArrayRef from a range. 204234353Sdim MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {} 205249423Sdim 206234353Sdim /// Construct an MutableArrayRef from a SmallVector. 207234353Sdim /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec) 208234353Sdim : ArrayRef<T>(Vec) {} 209249423Sdim 210234353Sdim /// Construct a MutableArrayRef from a std::vector. 211234353Sdim /*implicit*/ MutableArrayRef(std::vector<T> &Vec) 212234353Sdim : ArrayRef<T>(Vec) {} 213249423Sdim 214234353Sdim /// Construct an MutableArrayRef from a C array. 215234353Sdim template <size_t N> 216234353Sdim /*implicit*/ MutableArrayRef(T (&Arr)[N]) 217234353Sdim : ArrayRef<T>(Arr) {} 218249423Sdim 219234353Sdim T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } 220234353Sdim 221234353Sdim iterator begin() const { return data(); } 222234353Sdim iterator end() const { return data() + this->size(); } 223249423Sdim 224263508Sdim reverse_iterator rbegin() const { return reverse_iterator(end()); } 225263508Sdim reverse_iterator rend() const { return reverse_iterator(begin()); } 226263508Sdim 227234353Sdim /// front - Get the first element. 228234353Sdim T &front() const { 229234353Sdim assert(!this->empty()); 230234353Sdim return data()[0]; 231234353Sdim } 232249423Sdim 233234353Sdim /// back - Get the last element. 234234353Sdim T &back() const { 235234353Sdim assert(!this->empty()); 236234353Sdim return data()[this->size()-1]; 237234353Sdim } 238234353Sdim 239234353Sdim /// slice(n) - Chop off the first N elements of the array. 240234353Sdim MutableArrayRef<T> slice(unsigned N) const { 241234353Sdim assert(N <= this->size() && "Invalid specifier"); 242234353Sdim return MutableArrayRef<T>(data()+N, this->size()-N); 243234353Sdim } 244249423Sdim 245234353Sdim /// slice(n, m) - Chop off the first N elements of the array, and keep M 246234353Sdim /// elements in the array. 247234353Sdim MutableArrayRef<T> slice(unsigned N, unsigned M) const { 248234353Sdim assert(N+M <= this->size() && "Invalid specifier"); 249234353Sdim return MutableArrayRef<T>(data()+N, M); 250234353Sdim } 251249423Sdim 252224145Sdim /// @} 253234353Sdim /// @name Operator Overloads 254234353Sdim /// @{ 255234353Sdim T &operator[](size_t Index) const { 256234353Sdim assert(Index < this->size() && "Invalid index!"); 257234353Sdim return data()[Index]; 258234353Sdim } 259218885Sdim }; 260226633Sdim 261226633Sdim /// @name ArrayRef Convenience constructors 262226633Sdim /// @{ 263226633Sdim 264226633Sdim /// Construct an ArrayRef from a single element. 265226633Sdim template<typename T> 266226633Sdim ArrayRef<T> makeArrayRef(const T &OneElt) { 267226633Sdim return OneElt; 268226633Sdim } 269226633Sdim 270226633Sdim /// Construct an ArrayRef from a pointer and length. 271226633Sdim template<typename T> 272226633Sdim ArrayRef<T> makeArrayRef(const T *data, size_t length) { 273226633Sdim return ArrayRef<T>(data, length); 274226633Sdim } 275226633Sdim 276226633Sdim /// Construct an ArrayRef from a range. 277226633Sdim template<typename T> 278226633Sdim ArrayRef<T> makeArrayRef(const T *begin, const T *end) { 279226633Sdim return ArrayRef<T>(begin, end); 280226633Sdim } 281226633Sdim 282226633Sdim /// Construct an ArrayRef from a SmallVector. 283226633Sdim template <typename T> 284226633Sdim ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) { 285226633Sdim return Vec; 286226633Sdim } 287226633Sdim 288226633Sdim /// Construct an ArrayRef from a SmallVector. 289226633Sdim template <typename T, unsigned N> 290226633Sdim ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) { 291226633Sdim return Vec; 292226633Sdim } 293226633Sdim 294226633Sdim /// Construct an ArrayRef from a std::vector. 295226633Sdim template<typename T> 296226633Sdim ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) { 297226633Sdim return Vec; 298226633Sdim } 299226633Sdim 300226633Sdim /// Construct an ArrayRef from a C array. 301226633Sdim template<typename T, size_t N> 302226633Sdim ArrayRef<T> makeArrayRef(const T (&Arr)[N]) { 303226633Sdim return ArrayRef<T>(Arr); 304226633Sdim } 305226633Sdim 306226633Sdim /// @} 307224145Sdim /// @name ArrayRef Comparison Operators 308224145Sdim /// @{ 309224145Sdim 310224145Sdim template<typename T> 311224145Sdim inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) { 312224145Sdim return LHS.equals(RHS); 313224145Sdim } 314224145Sdim 315224145Sdim template<typename T> 316224145Sdim inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) { 317224145Sdim return !(LHS == RHS); 318224145Sdim } 319224145Sdim 320224145Sdim /// @} 321224145Sdim 322218885Sdim // ArrayRefs can be treated like a POD type. 323218885Sdim template <typename T> struct isPodLike; 324218885Sdim template <typename T> struct isPodLike<ArrayRef<T> > { 325218885Sdim static const bool value = true; 326218885Sdim }; 327218885Sdim} 328249423Sdim 329218885Sdim#endif 330