ArrayRef.h revision fced2945995b4fd8f28f7dec9fcb5a6ab2e2798d
12b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner//===--- ArrayRef.h - Array Reference Wrapper -------------------*- C++ -*-===// 22b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner// 32b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner// The LLVM Compiler Infrastructure 42b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner// 52b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner// This file is distributed under the University of Illinois Open Source 62b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner// License. See LICENSE.TXT for details. 72b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner// 82b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner//===----------------------------------------------------------------------===// 92b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 102b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner#ifndef LLVM_ADT_ARRAYREF_H 112b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner#define LLVM_ADT_ARRAYREF_H 122b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 132b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner#include "llvm/ADT/SmallVector.h" 142b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner#include <vector> 152b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 162b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattnernamespace llvm { 17fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 182b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// ArrayRef - Represent a constant reference to an array (0 or more elements 1904df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /// consecutively in memory), i.e. a start pointer and a length. It allows 2004df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /// various APIs to take consecutive elements easily and conveniently. 212b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// 222b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// This class does not own the underlying data, it is expected to be used in 232b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// situations where the data resides in some other buffer, whose lifetime 24715c80a00b965f19ca2c7dacbc2f809221cc2730Jay Foad /// extends past that of the ArrayRef. For this reason, it is not in general 25715c80a00b965f19ca2c7dacbc2f809221cc2730Jay Foad /// safe to store an ArrayRef. 262b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// 272b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// This is intended to be trivially copyable, so it should be passed by 282b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// value. 292b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner template<typename T> 302b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner class ArrayRef { 312b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner public: 322b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner typedef const T *iterator; 332b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner typedef const T *const_iterator; 342b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner typedef size_t size_type; 35fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 362b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner private: 372b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// The start of the array, in an external buffer. 382b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner const T *Data; 39fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 402b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// The number of elements. 415d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad size_type Length; 42fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 432b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner public: 442b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Constructors 452b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 46fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 472b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an empty ArrayRef. 482b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef() : Data(0), Length(0) {} 49fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 502b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a single element. 512b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef(const T &OneElt) 522b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(&OneElt), Length(1) {} 53fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 542b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a pointer and length. 5504df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /*implicit*/ ArrayRef(const T *data, size_t length) 562b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(data), Length(length) {} 57fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 585d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// Construct an ArrayRef from a range. 595d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad ArrayRef(const T *begin, const T *end) 605d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad : Data(begin), Length(end - begin) {} 61fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 622b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a SmallVector. 632b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef(const SmallVectorImpl<T> &Vec) 642b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(Vec.data()), Length(Vec.size()) {} 652b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 662b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a std::vector. 672b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef(const std::vector<T> &Vec) 682b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(Vec.empty() ? (T*)0 : &Vec[0]), Length(Vec.size()) {} 69fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 70438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel /// Construct an ArrayRef from a C array. 71438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel template <size_t N> 72438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel /*implicit*/ ArrayRef(const T (&Arr)[N]) 73438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel : Data(Arr), Length(N) {} 74fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 752b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 762b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Simple Operations 772b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 782b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 792b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner iterator begin() const { return Data; } 802b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner iterator end() const { return Data + Length; } 81fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 8204b2f0d99feb9cdf87eb8f35483816d757d170ddChris Lattner /// empty - Check if the array is empty. 832b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner bool empty() const { return Length == 0; } 84fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 85878ad7afa512ef300d5df4e7ca0189775342dfc2Chris Lattner const T *data() const { return Data; } 86fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 8704b2f0d99feb9cdf87eb8f35483816d757d170ddChris Lattner /// size - Get the array size. 882b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner size_t size() const { return Length; } 89fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 902b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// front - Get the first element. 912b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner const T &front() const { 922b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner assert(!empty()); 932b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return Data[0]; 942b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 95fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 9604df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /// back - Get the last element. 972b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner const T &back() const { 982b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner assert(!empty()); 992b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return Data[Length-1]; 1002b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 101fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 1025d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// equals - Check for element-wise equality. 1035d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad bool equals(ArrayRef RHS) const { 1045d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad if (Length != RHS.Length) 1055d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return false; 1065d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad for (size_type i = 0; i != Length; i++) 1075d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad if (Data[i] != RHS.Data[i]) 1085d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return false; 1095d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return true; 1105d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad } 1115d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 112fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner /// slice(n) - Chop off the first N elements of the array. 1131752e45de9914cb52d748c1052ecd2f1414bced4Chris Lattner ArrayRef<T> slice(unsigned N) const { 114fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner assert(N <= size() && "Invalid specifier"); 115fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner return ArrayRef<T>(data()+N, size()-N); 116fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner } 117fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner 118fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner /// slice(n, m) - Chop off the first N elements of the array, and keep M 119fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner /// elements in the array. 1201752e45de9914cb52d748c1052ecd2f1414bced4Chris Lattner ArrayRef<T> slice(unsigned N, unsigned M) const { 121fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner assert(N+M <= size() && "Invalid specifier"); 122fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner return ArrayRef<T>(data()+N, M); 123fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner } 124fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 1252b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 1262b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Operator Overloads 1272b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 12804df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner const T &operator[](size_t Index) const { 1292b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner assert(Index < Length && "Invalid index!"); 1302b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return Data[Index]; 1312b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 132fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 1332b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 1342b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Expensive Operations 1352b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 1362b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner std::vector<T> vec() const { 1372b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return std::vector<T>(Data, Data+Length); 1382b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 139fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 1402b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 1412a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad /// @name Conversion operators 1422a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad /// @{ 1432a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad operator std::vector<T>() const { 1442a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad return std::vector<T>(Data, Data+Length); 1452a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad } 146fced2945995b4fd8f28f7dec9fcb5a6ab2e2798dJakub Staszak 1472a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad /// @} 1482b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner }; 149c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 150c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// @name ArrayRef Convenience constructors 151c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// @{ 152c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 153c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a single element. 154c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 155c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T &OneElt) { 156c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return OneElt; 157c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 158c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 159c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a pointer and length. 160c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 161c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T *data, size_t length) { 162c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return ArrayRef<T>(data, length); 163c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 164c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 165c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a range. 166c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 167c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T *begin, const T *end) { 168c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return ArrayRef<T>(begin, end); 169c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 170c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 171c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a SmallVector. 172c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template <typename T> 173c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) { 174c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return Vec; 175c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 176c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 177c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a SmallVector. 178c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template <typename T, unsigned N> 179c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) { 180c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return Vec; 181c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 182c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 183c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a std::vector. 184c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 185c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) { 186c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return Vec; 187c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 188c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 189c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a C array. 190c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T, size_t N> 191c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T (&Arr)[N]) { 192f6275309994dea2ec852c1f539875ae643646ec5Frits van Bommel return ArrayRef<T>(Arr); 193c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 194c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 195c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// @} 1965d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// @name ArrayRef Comparison Operators 1975d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// @{ 1985d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 1995d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad template<typename T> 2005d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) { 2015d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return LHS.equals(RHS); 2025d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad } 2035d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2045d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad template<typename T> 2055d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) { 2065d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return !(LHS == RHS); 2075d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad } 2085d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2095d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// @} 2105d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2112b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner // ArrayRefs can be treated like a POD type. 2122b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner template <typename T> struct isPodLike; 2132b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner template <typename T> struct isPodLike<ArrayRef<T> > { 2142b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner static const bool value = true; 2152b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner }; 2162b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner} 2172b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 2182b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner#endif 219