ArrayRef.h revision f6275309994dea2ec852c1f539875ae643646ec5
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 { 172b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner class APInt; 182b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 192b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// ArrayRef - Represent a constant reference to an array (0 or more elements 2004df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /// consecutively in memory), i.e. a start pointer and a length. It allows 2104df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /// various APIs to take consecutive elements easily and conveniently. 222b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// 232b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// This class does not own the underlying data, it is expected to be used in 242b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// situations where the data resides in some other buffer, whose lifetime 25715c80a00b965f19ca2c7dacbc2f809221cc2730Jay Foad /// extends past that of the ArrayRef. For this reason, it is not in general 26715c80a00b965f19ca2c7dacbc2f809221cc2730Jay Foad /// safe to store an ArrayRef. 272b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// 282b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// This is intended to be trivially copyable, so it should be passed by 292b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// value. 302b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner template<typename T> 312b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner class ArrayRef { 322b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner public: 332b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner typedef const T *iterator; 342b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner typedef const T *const_iterator; 352b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner typedef size_t size_type; 362b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 372b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner private: 382b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// The start of the array, in an external buffer. 392b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner const T *Data; 402b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 412b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// The number of elements. 425d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad size_type Length; 432b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 442b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner public: 452b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Constructors 462b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 472b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 482b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an empty ArrayRef. 492b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef() : Data(0), Length(0) {} 502b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 512b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a single element. 522b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef(const T &OneElt) 532b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(&OneElt), Length(1) {} 542b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 552b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a pointer and length. 5604df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /*implicit*/ ArrayRef(const T *data, size_t length) 572b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(data), Length(length) {} 582b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 595d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// Construct an ArrayRef from a range. 605d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad ArrayRef(const T *begin, const T *end) 615d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad : Data(begin), Length(end - begin) {} 625d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 632b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a SmallVector. 642b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef(const SmallVectorImpl<T> &Vec) 652b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(Vec.data()), Length(Vec.size()) {} 662b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 672b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// Construct an ArrayRef from a std::vector. 682b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /*implicit*/ ArrayRef(const std::vector<T> &Vec) 692b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner : Data(Vec.empty() ? (T*)0 : &Vec[0]), Length(Vec.size()) {} 702b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 71438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel /// Construct an ArrayRef from a C array. 72438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel template <size_t N> 73438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel /*implicit*/ ArrayRef(const T (&Arr)[N]) 74438208e8cb29c67b2177619a339b84291729b6b7Frits van Bommel : Data(Arr), Length(N) {} 752b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 762b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 772b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Simple Operations 782b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 792b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 802b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner iterator begin() const { return Data; } 812b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner iterator end() const { return Data + Length; } 822b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 8304b2f0d99feb9cdf87eb8f35483816d757d170ddChris Lattner /// empty - Check if the array is empty. 842b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner bool empty() const { return Length == 0; } 852b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 86878ad7afa512ef300d5df4e7ca0189775342dfc2Chris Lattner const T *data() const { return Data; } 87878ad7afa512ef300d5df4e7ca0189775342dfc2Chris Lattner 8804b2f0d99feb9cdf87eb8f35483816d757d170ddChris Lattner /// size - Get the array size. 892b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner size_t size() const { return Length; } 902b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 912b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// front - Get the first element. 922b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner const T &front() const { 932b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner assert(!empty()); 942b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return Data[0]; 952b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 962b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 9704df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner /// back - Get the last element. 982b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner const T &back() const { 992b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner assert(!empty()); 1002b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return Data[Length-1]; 1012b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 1022b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 1035d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// equals - Check for element-wise equality. 1045d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad bool equals(ArrayRef RHS) const { 1055d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad if (Length != RHS.Length) 1065d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return false; 1075d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad for (size_type i = 0; i != Length; i++) 1085d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad if (Data[i] != RHS.Data[i]) 1095d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return false; 1105d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return true; 1115d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad } 1125d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 113fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner /// slice(n) - Chop off the first N elements of the array. 114fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner ArrayRef<T> slice(unsigned N) { 115fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner assert(N <= size() && "Invalid specifier"); 116fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner return ArrayRef<T>(data()+N, size()-N); 117fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner } 118fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner 119fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner /// slice(n, m) - Chop off the first N elements of the array, and keep M 120fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner /// elements in the array. 121fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner ArrayRef<T> slice(unsigned N, unsigned M) { 122fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner assert(N+M <= size() && "Invalid specifier"); 123fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner return ArrayRef<T>(data()+N, M); 124fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner } 125fa09685a9aa17dbdd4c72ad032684debb25feb0bChris Lattner 1262b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 1272b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Operator Overloads 1282b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 12904df049014396fe97a31bf3fa8951201b2ed8ffeChris Lattner const T &operator[](size_t Index) const { 1302b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner assert(Index < Length && "Invalid index!"); 1312b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return Data[Index]; 1322b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 1332b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 1342b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 1352b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @name Expensive Operations 1362b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @{ 1372b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner std::vector<T> vec() const { 1382b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner return std::vector<T>(Data, Data+Length); 1392b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner } 1402b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 1412b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner /// @} 1422a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad /// @name Conversion operators 1432a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad /// @{ 1442a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad operator std::vector<T>() const { 1452a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad return std::vector<T>(Data, Data+Length); 1462a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad } 1472a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad 1482a4a6fecf0b8c92223f8fdf19545b564b7d3fcdeJay Foad /// @} 1492b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner }; 150c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 151c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// @name ArrayRef Convenience constructors 152c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// @{ 153c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 154c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a single element. 155c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 156c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T &OneElt) { 157c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return OneElt; 158c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 159c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 160c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a pointer and length. 161c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 162c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T *data, size_t length) { 163c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return ArrayRef<T>(data, length); 164c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 165c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 166c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a range. 167c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 168c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T *begin, const T *end) { 169c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return ArrayRef<T>(begin, end); 170c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 171c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 172c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a SmallVector. 173c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template <typename T> 174c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) { 175c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return Vec; 176c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 177c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 178c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a SmallVector. 179c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template <typename T, unsigned N> 180c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) { 181c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return Vec; 182c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 183c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 184c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a std::vector. 185c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T> 186c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) { 187c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel return Vec; 188c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 189c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 190c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// Construct an ArrayRef from a C array. 191c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel template<typename T, size_t N> 192c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel ArrayRef<T> makeArrayRef(const T (&Arr)[N]) { 193f6275309994dea2ec852c1f539875ae643646ec5Frits van Bommel return ArrayRef<T>(Arr); 194c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel } 195c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel 196c48e1ef0e22b4113dd4dd48c5b170a19fe4d0188Frits van Bommel /// @} 1975d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// @name ArrayRef Comparison Operators 1985d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// @{ 1995d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2005d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad template<typename T> 2015d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) { 2025d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return LHS.equals(RHS); 2035d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad } 2045d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2055d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad template<typename T> 2065d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) { 2075d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad return !(LHS == RHS); 2085d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad } 2095d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2105d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad /// @} 2115d4f9909c49d28db9572acc4513c1a695b0c53daJay Foad 2122b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner // ArrayRefs can be treated like a POD type. 2132b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner template <typename T> struct isPodLike; 2142b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner template <typename T> struct isPodLike<ArrayRef<T> > { 2152b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner static const bool value = true; 2162b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner }; 2172b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner} 2182b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner 2192b9bc422a5e6840f5b925316bc06d5943deb610aChris Lattner#endif 220