LLVM API Documentation

ArrayRef.h
Go to the documentation of this file.
00001 //===--- ArrayRef.h - Array Reference Wrapper -------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 
00010 #ifndef LLVM_ADT_ARRAYREF_H
00011 #define LLVM_ADT_ARRAYREF_H
00012 
00013 #include "llvm/ADT/None.h"
00014 #include "llvm/ADT/STLExtras.h"
00015 #include "llvm/ADT/SmallVector.h"
00016 #include <vector>
00017 
00018 namespace llvm {
00019 
00020   /// ArrayRef - Represent a constant reference to an array (0 or more elements
00021   /// consecutively in memory), i.e. a start pointer and a length.  It allows
00022   /// various APIs to take consecutive elements easily and conveniently.
00023   ///
00024   /// This class does not own the underlying data, it is expected to be used in
00025   /// situations where the data resides in some other buffer, whose lifetime
00026   /// extends past that of the ArrayRef. For this reason, it is not in general
00027   /// safe to store an ArrayRef.
00028   ///
00029   /// This is intended to be trivially copyable, so it should be passed by
00030   /// value.
00031   template<typename T>
00032   class ArrayRef {
00033   public:
00034     typedef const T *iterator;
00035     typedef const T *const_iterator;
00036     typedef size_t size_type;
00037 
00038     typedef std::reverse_iterator<iterator> reverse_iterator;
00039 
00040   private:
00041     /// The start of the array, in an external buffer.
00042     const T *Data;
00043 
00044     /// The number of elements.
00045     size_type Length;
00046 
00047     /// \brief A dummy "optional" type that is only created by implicit
00048     /// conversion from a reference to T.
00049     ///
00050     /// This type must *only* be used in a function argument or as a copy of
00051     /// a function argument, as otherwise it will hold a pointer to a temporary
00052     /// past that temporaries' lifetime.
00053     struct TRefOrNothing {
00054       const T *TPtr;
00055 
00056       TRefOrNothing() : TPtr(nullptr) {}
00057       TRefOrNothing(const T &TRef) : TPtr(&TRef) {}
00058     };
00059 
00060   public:
00061     /// @name Constructors
00062     /// @{
00063 
00064     /// Construct an empty ArrayRef.
00065     /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {}
00066 
00067     /// Construct an empty ArrayRef from None.
00068     /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {}
00069 
00070     /// Construct an ArrayRef from a single element.
00071     /*implicit*/ ArrayRef(const T &OneElt)
00072       : Data(&OneElt), Length(1) {}
00073 
00074     /// Construct an ArrayRef from a pointer and length.
00075     /*implicit*/ ArrayRef(const T *data, size_t length)
00076       : Data(data), Length(length) {}
00077 
00078     /// Construct an ArrayRef from a range.
00079     ArrayRef(const T *begin, const T *end)
00080       : Data(begin), Length(end - begin) {}
00081 
00082     /// Construct an ArrayRef from a SmallVector. This is templated in order to
00083     /// avoid instantiating SmallVectorTemplateCommon<T> whenever we
00084     /// copy-construct an ArrayRef.
00085     template<typename U>
00086     /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
00087       : Data(Vec.data()), Length(Vec.size()) {
00088     }
00089 
00090     /// Construct an ArrayRef from a std::vector.
00091     template<typename A>
00092     /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
00093       : Data(Vec.data()), Length(Vec.size()) {}
00094 
00095     /// Construct an ArrayRef from a C array.
00096     template <size_t N>
00097     /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N])
00098       : Data(Arr), Length(N) {}
00099 
00100 #if LLVM_HAS_INITIALIZER_LISTS
00101     /// Construct an ArrayRef from a std::initializer_list.
00102     /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
00103     : Data(Vec.begin() == Vec.end() ? (T*)0 : Vec.begin()),
00104       Length(Vec.size()) {}
00105 #endif
00106 
00107     /// @}
00108     /// @name Simple Operations
00109     /// @{
00110 
00111     iterator begin() const { return Data; }
00112     iterator end() const { return Data + Length; }
00113 
00114     reverse_iterator rbegin() const { return reverse_iterator(end()); }
00115     reverse_iterator rend() const { return reverse_iterator(begin()); }
00116 
00117     /// empty - Check if the array is empty.
00118     bool empty() const { return Length == 0; }
00119 
00120     const T *data() const { return Data; }
00121 
00122     /// size - Get the array size.
00123     size_t size() const { return Length; }
00124 
00125     /// front - Get the first element.
00126     const T &front() const {
00127       assert(!empty());
00128       return Data[0];
00129     }
00130 
00131     /// back - Get the last element.
00132     const T &back() const {
00133       assert(!empty());
00134       return Data[Length-1];
00135     }
00136 
00137     // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
00138     template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
00139       T *Buff = A.template Allocate<T>(Length);
00140       std::copy(begin(), end(), Buff);
00141       return ArrayRef<T>(Buff, Length);
00142     }
00143 
00144     /// equals - Check for element-wise equality.
00145     bool equals(ArrayRef RHS) const {
00146       if (Length != RHS.Length)
00147         return false;
00148       return std::equal(begin(), end(), RHS.begin());
00149     }
00150 
00151     /// slice(n) - Chop off the first N elements of the array.
00152     ArrayRef<T> slice(unsigned N) const {
00153       assert(N <= size() && "Invalid specifier");
00154       return ArrayRef<T>(data()+N, size()-N);
00155     }
00156 
00157     /// slice(n, m) - Chop off the first N elements of the array, and keep M
00158     /// elements in the array.
00159     ArrayRef<T> slice(unsigned N, unsigned M) const {
00160       assert(N+M <= size() && "Invalid specifier");
00161       return ArrayRef<T>(data()+N, M);
00162     }
00163 
00164     // \brief Drop the last \p N elements of the array.
00165     ArrayRef<T> drop_back(unsigned N = 1) const {
00166       assert(size() >= N && "Dropping more elements than exist");
00167       return slice(0, size() - N);
00168     }
00169 
00170     /// @}
00171     /// @name Operator Overloads
00172     /// @{
00173     const T &operator[](size_t Index) const {
00174       assert(Index < Length && "Invalid index!");
00175       return Data[Index];
00176     }
00177 
00178     /// @}
00179     /// @name Expensive Operations
00180     /// @{
00181     std::vector<T> vec() const {
00182       return std::vector<T>(Data, Data+Length);
00183     }
00184 
00185     /// @}
00186     /// @name Conversion operators
00187     /// @{
00188     operator std::vector<T>() const {
00189       return std::vector<T>(Data, Data+Length);
00190     }
00191 
00192     /// @}
00193     /// @{
00194     /// @name Convenience methods
00195 
00196     /// @brief Predicate for testing that the array equals the exact sequence of
00197     /// arguments.
00198     ///
00199     /// Will return false if the size is not equal to the exact number of
00200     /// arguments given or if the array elements don't equal the argument
00201     /// elements in order. Currently supports up to 16 arguments, but can
00202     /// easily be extended.
00203     bool equals(TRefOrNothing Arg0 = TRefOrNothing(),
00204                 TRefOrNothing Arg1 = TRefOrNothing(),
00205                 TRefOrNothing Arg2 = TRefOrNothing(),
00206                 TRefOrNothing Arg3 = TRefOrNothing(),
00207                 TRefOrNothing Arg4 = TRefOrNothing(),
00208                 TRefOrNothing Arg5 = TRefOrNothing(),
00209                 TRefOrNothing Arg6 = TRefOrNothing(),
00210                 TRefOrNothing Arg7 = TRefOrNothing(),
00211                 TRefOrNothing Arg8 = TRefOrNothing(),
00212                 TRefOrNothing Arg9 = TRefOrNothing(),
00213                 TRefOrNothing Arg10 = TRefOrNothing(),
00214                 TRefOrNothing Arg11 = TRefOrNothing(),
00215                 TRefOrNothing Arg12 = TRefOrNothing(),
00216                 TRefOrNothing Arg13 = TRefOrNothing(),
00217                 TRefOrNothing Arg14 = TRefOrNothing(),
00218                 TRefOrNothing Arg15 = TRefOrNothing()) {
00219       TRefOrNothing Args[] = {Arg0,  Arg1,  Arg2,  Arg3, Arg4,  Arg5,
00220                               Arg6,  Arg7,  Arg8,  Arg9, Arg10, Arg11,
00221                               Arg12, Arg13, Arg14, Arg15};
00222       if (size() > array_lengthof(Args))
00223         return false;
00224 
00225       for (unsigned i = 0, e = size(); i != e; ++i)
00226         if (Args[i].TPtr == nullptr || (*this)[i] != *Args[i].TPtr)
00227           return false;
00228 
00229       // Either the size is exactly as many args, or the next arg must be null.
00230       return size() == array_lengthof(Args) || Args[size()].TPtr == nullptr;
00231     }
00232 
00233     /// @}
00234   };
00235 
00236   /// MutableArrayRef - Represent a mutable reference to an array (0 or more
00237   /// elements consecutively in memory), i.e. a start pointer and a length.  It
00238   /// allows various APIs to take and modify consecutive elements easily and
00239   /// conveniently.
00240   ///
00241   /// This class does not own the underlying data, it is expected to be used in
00242   /// situations where the data resides in some other buffer, whose lifetime
00243   /// extends past that of the MutableArrayRef. For this reason, it is not in
00244   /// general safe to store a MutableArrayRef.
00245   ///
00246   /// This is intended to be trivially copyable, so it should be passed by
00247   /// value.
00248   template<typename T>
00249   class MutableArrayRef : public ArrayRef<T> {
00250   public:
00251     typedef T *iterator;
00252 
00253     typedef std::reverse_iterator<iterator> reverse_iterator;
00254 
00255     /// Construct an empty MutableArrayRef.
00256     /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
00257 
00258     /// Construct an empty MutableArrayRef from None.
00259     /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
00260 
00261     /// Construct an MutableArrayRef from a single element.
00262     /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
00263 
00264     /// Construct an MutableArrayRef from a pointer and length.
00265     /*implicit*/ MutableArrayRef(T *data, size_t length)
00266       : ArrayRef<T>(data, length) {}
00267 
00268     /// Construct an MutableArrayRef from a range.
00269     MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
00270 
00271     /// Construct an MutableArrayRef from a SmallVector.
00272     /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
00273     : ArrayRef<T>(Vec) {}
00274 
00275     /// Construct a MutableArrayRef from a std::vector.
00276     /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
00277     : ArrayRef<T>(Vec) {}
00278 
00279     /// Construct an MutableArrayRef from a C array.
00280     template <size_t N>
00281     /*implicit*/ LLVM_CONSTEXPR MutableArrayRef(T (&Arr)[N])
00282       : ArrayRef<T>(Arr) {}
00283 
00284     T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
00285 
00286     iterator begin() const { return data(); }
00287     iterator end() const { return data() + this->size(); }
00288 
00289     reverse_iterator rbegin() const { return reverse_iterator(end()); }
00290     reverse_iterator rend() const { return reverse_iterator(begin()); }
00291 
00292     /// front - Get the first element.
00293     T &front() const {
00294       assert(!this->empty());
00295       return data()[0];
00296     }
00297 
00298     /// back - Get the last element.
00299     T &back() const {
00300       assert(!this->empty());
00301       return data()[this->size()-1];
00302     }
00303 
00304     /// slice(n) - Chop off the first N elements of the array.
00305     MutableArrayRef<T> slice(unsigned N) const {
00306       assert(N <= this->size() && "Invalid specifier");
00307       return MutableArrayRef<T>(data()+N, this->size()-N);
00308     }
00309 
00310     /// slice(n, m) - Chop off the first N elements of the array, and keep M
00311     /// elements in the array.
00312     MutableArrayRef<T> slice(unsigned N, unsigned M) const {
00313       assert(N+M <= this->size() && "Invalid specifier");
00314       return MutableArrayRef<T>(data()+N, M);
00315     }
00316 
00317     /// @}
00318     /// @name Operator Overloads
00319     /// @{
00320     T &operator[](size_t Index) const {
00321       assert(Index < this->size() && "Invalid index!");
00322       return data()[Index];
00323     }
00324   };
00325 
00326   /// @name ArrayRef Convenience constructors
00327   /// @{
00328 
00329   /// Construct an ArrayRef from a single element.
00330   template<typename T>
00331   ArrayRef<T> makeArrayRef(const T &OneElt) {
00332     return OneElt;
00333   }
00334 
00335   /// Construct an ArrayRef from a pointer and length.
00336   template<typename T>
00337   ArrayRef<T> makeArrayRef(const T *data, size_t length) {
00338     return ArrayRef<T>(data, length);
00339   }
00340 
00341   /// Construct an ArrayRef from a range.
00342   template<typename T>
00343   ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
00344     return ArrayRef<T>(begin, end);
00345   }
00346 
00347   /// Construct an ArrayRef from a SmallVector.
00348   template <typename T>
00349   ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
00350     return Vec;
00351   }
00352 
00353   /// Construct an ArrayRef from a SmallVector.
00354   template <typename T, unsigned N>
00355   ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
00356     return Vec;
00357   }
00358 
00359   /// Construct an ArrayRef from a std::vector.
00360   template<typename T>
00361   ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
00362     return Vec;
00363   }
00364 
00365   /// Construct an ArrayRef from a C array.
00366   template<typename T, size_t N>
00367   ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
00368     return ArrayRef<T>(Arr);
00369   }
00370 
00371   /// @}
00372   /// @name ArrayRef Comparison Operators
00373   /// @{
00374 
00375   template<typename T>
00376   inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
00377     return LHS.equals(RHS);
00378   }
00379 
00380   template<typename T>
00381   inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
00382     return !(LHS == RHS);
00383   }
00384 
00385   /// @}
00386 
00387   // ArrayRefs can be treated like a POD type.
00388   template <typename T> struct isPodLike;
00389   template <typename T> struct isPodLike<ArrayRef<T> > {
00390     static const bool value = true;
00391   };
00392 }
00393 
00394 #endif