1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_LIBARTBASE_BASE_ARRAY_SLICE_H_
18 #define ART_LIBARTBASE_BASE_ARRAY_SLICE_H_
19 
20 #include "bit_utils.h"
21 #include "casts.h"
22 #include "iteration_range.h"
23 #include "length_prefixed_array.h"
24 #include "stride_iterator.h"
25 
26 namespace art {
27 
28 // An ArraySlice is an abstraction over an array or a part of an array of a particular type. It does
29 // bounds checking and can be made from several common array-like structures in Art.
30 template <typename T>
31 class ArraySlice {
32  public:
33   using value_type = T;
34   using reference = T&;
35   using const_reference = const T&;
36   using pointer = T*;
37   using const_pointer = const T*;
38   using iterator = StrideIterator<T>;
39   using const_iterator = StrideIterator<const T>;
40   using reverse_iterator = std::reverse_iterator<iterator>;
41   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
42   using difference_type = ptrdiff_t;
43   using size_type = size_t;
44 
45   // Create an empty array slice.
ArraySlice()46   ArraySlice() : array_(nullptr), size_(0), element_size_(0) {}
47 
48   // Create an array slice of the first 'length' elements of the array, with each element being
49   // element_size bytes long.
50   ArraySlice(T* array,
51              size_t length,
52              size_t element_size = sizeof(T))
array_(array)53       : array_(array),
54         size_(dchecked_integral_cast<uint32_t>(length)),
55         element_size_(element_size) {
56     DCHECK(array_ != nullptr || length == 0);
57   }
58 
59   ArraySlice(LengthPrefixedArray<T>* lpa,
60              size_t element_size = sizeof(T),
61              size_t alignment = alignof(T))
62       : ArraySlice(
63             lpa != nullptr && lpa->size() != 0 ? &lpa->At(0, element_size, alignment) : nullptr,
64             lpa != nullptr ? lpa->size() : 0,
65             element_size) {}
66 
67   // Iterators.
begin()68   iterator begin() { return iterator(&AtUnchecked(0), element_size_); }
begin()69   const_iterator begin() const { return const_iterator(&AtUnchecked(0), element_size_); }
cbegin()70   const_iterator cbegin() const { return const_iterator(&AtUnchecked(0), element_size_); }
end()71   StrideIterator<T> end() { return StrideIterator<T>(&AtUnchecked(size_), element_size_); }
end()72   const_iterator end() const { return const_iterator(&AtUnchecked(size_), element_size_); }
cend()73   const_iterator cend() const { return const_iterator(&AtUnchecked(size_), element_size_); }
rbegin()74   reverse_iterator rbegin() { return reverse_iterator(end()); }
rbegin()75   const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
crbegin()76   const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); }
rend()77   reverse_iterator rend() { return reverse_iterator(begin()); }
rend()78   const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
crend()79   const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); }
80 
81   // Size.
size()82   size_type size() const { return size_; }
empty()83   bool empty() const { return size() == 0u; }
84 
85   // Element access. NOTE: Not providing at() and data().
86 
87   reference operator[](size_t index) {
88     DCHECK_LT(index, size_);
89     return AtUnchecked(index);
90   }
91 
92   const_reference operator[](size_t index) const {
93     DCHECK_LT(index, size_);
94     return AtUnchecked(index);
95   }
96 
front()97   reference front() {
98     DCHECK(!empty());
99     return (*this)[0];
100   }
101 
front()102   const_reference front() const {
103     DCHECK(!empty());
104     return (*this)[0];
105   }
106 
back()107   reference back() {
108     DCHECK(!empty());
109     return (*this)[size_ - 1u];
110   }
111 
back()112   const_reference back() const {
113     DCHECK(!empty());
114     return (*this)[size_ - 1u];
115   }
116 
SubArray(size_type pos)117   ArraySlice<T> SubArray(size_type pos) {
118     return SubArray(pos, size() - pos);
119   }
120 
SubArray(size_type pos)121   ArraySlice<const T> SubArray(size_type pos) const {
122     return SubArray(pos, size() - pos);
123   }
124 
SubArray(size_type pos,size_type length)125   ArraySlice<T> SubArray(size_type pos, size_type length) {
126     DCHECK_LE(pos, size());
127     DCHECK_LE(length, size() - pos);
128     return ArraySlice<T>(&AtUnchecked(pos), length, element_size_);
129   }
130 
SubArray(size_type pos,size_type length)131   ArraySlice<const T> SubArray(size_type pos, size_type length) const {
132     DCHECK_LE(pos, size());
133     DCHECK_LE(length, size() - pos);
134     return ArraySlice<const T>(&AtUnchecked(pos), length, element_size_);
135   }
136 
ElementSize()137   size_t ElementSize() const {
138     return element_size_;
139   }
140 
Contains(const T * element)141   bool Contains(const T* element) const {
142     return &AtUnchecked(0) <= element && element < &AtUnchecked(size_) &&
143           ((reinterpret_cast<uintptr_t>(element) -
144             reinterpret_cast<uintptr_t>(&AtUnchecked(0))) % element_size_) == 0;
145   }
146 
OffsetOf(const T * element)147   size_t OffsetOf(const T* element) const {
148     DCHECK(Contains(element));
149     // Since it's possible element_size_ != sizeof(T) we cannot just use pointer arithmatic
150     uintptr_t base_ptr = reinterpret_cast<uintptr_t>(&AtUnchecked(0));
151     uintptr_t obj_ptr = reinterpret_cast<uintptr_t>(element);
152     return (obj_ptr - base_ptr) / element_size_;
153   }
154 
155  private:
AtUnchecked(size_t index)156   T& AtUnchecked(size_t index) {
157     return *reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(array_) + index * element_size_);
158   }
159 
AtUnchecked(size_t index)160   const T& AtUnchecked(size_t index) const {
161     return *reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(array_) + index * element_size_);
162   }
163 
164   T* array_;
165   size_t size_;
166   size_t element_size_;
167 };
168 
169 }  // namespace art
170 
171 #endif  // ART_LIBARTBASE_BASE_ARRAY_SLICE_H_
172