1 //
2 // Copyright 2019 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef PXR_BASE_TF_SPAN_H
25 #define PXR_BASE_TF_SPAN_H
26
27 /// \file tf/span.h
28
29 #include "pxr/pxr.h"
30 #include "pxr/base/tf/api.h"
31 #include "pxr/base/tf/diagnostic.h"
32
33 #include <cstddef>
34 #include <iterator>
35 #include <type_traits>
36
37
38 PXR_NAMESPACE_OPEN_SCOPE
39
40
41 /// \class TfSpan
42 /// Represents a range of contiguous elements.
43 ///
44 /// This simply pairs a pointer with a size, while adding a common
45 /// array interface.
46 ///
47 /// A span allows ranges of elements to be referenced in a container-neutral
48 /// manner. While it is possible to achieve that effect by simply passing around
49 /// raw pointers, a span has the advantage of carrying around additional size
50 /// information, both enabling use of common array patterns, as well as
51 /// providing sufficient information to perform boundary tests.
52 ///
53 /// A TfSpan is implicitly convertible from common array types,
54 /// as well as from other spans, but preserves const-ness:
55 ///
56 /// \code
57 /// std::vector<int> data;
58 /// TfSpan<int> span(data); // Okay
59 ///
60 /// VtIntArray data;
61 /// TfSpan<int> span = data; // Okay
62 /// TfSpan<const int> cspan = span; // Okay
63 ///
64 /// const std::vector<int> data;
65 /// TfSpan<const int> span = data; // Okay
66 ///
67 /// const std::vector<int> data;
68 /// TfSpan<int> span = data; // Error! Discards cv-qualifier.
69 /// \endcode
70 ///
71 /// Helper methods TfMakeSpan and TfMakeConstSpan are also provided to enable
72 /// auto-typing when constructing spans:
73 /// \code
74 /// VtIntArray data;
75 /// auto readOnlySpan = TfMakeConstSpan(data); // TfSpan<const int>
76 /// auto readWriteSpan = TfMakeSpan(data); // TfSpan<int>
77 /// \endcode
78 ///
79 /// Spans do not own the data they reference. It is up to the user of the span
80 /// to ensure that the underlying data is not destructed while the span is in
81 /// use.
82 ///
83 /// This is modelled after std::span (C++20), but does not currently include
84 /// any specialization for static extents.
85 ///
86 template <typename T>
87 class TfSpan
88 {
89 public:
90 using element_type = T;
91 using value_type = typename std::remove_cv<T>::type;
92 using pointer = T*;
93 using reference = T&;
94 using index_type = std::size_t;
95 using difference_type = std::ptrdiff_t;
96
97 using iterator = T*;
98 using const_iterator = const T*;
99 using reverse_iterator = std::reverse_iterator<iterator>;
100 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
101
102 TfSpan() noexcept = default;
103
104 /// Construct a span over the range of [ptr, ptr+count).
105 /// In debug builds, a runtime assertion will fail if \p count > 0 and
106 /// \p ptr is null. The behavior is otherwise undefined for invalid ranges.
TfSpan(pointer ptr,index_type count)107 TfSpan(pointer ptr, index_type count)
108 : _data(ptr), _size(count)
109 {
110 TF_DEV_AXIOM(count == 0 || ptr);
111 }
112
113 /// Construct a span over the range [first, last).
TfSpan(pointer first,pointer last)114 TfSpan(pointer first, pointer last)
115 : TfSpan(first, index_type(last-first))
116 {
117 TF_DEV_AXIOM(last >= first);
118 }
119
120 /// Construct a span from a container.
121 /// The resulting span has a range of
122 /// [cont.data(), cont.data()+cont.size())
123 template <class Container>
124 TfSpan(Container& cont,
125 typename std::enable_if<
126 !std::is_const<element_type>::value &&
127 std::is_same<typename Container::value_type, value_type
128 >::value, Container
129 >::type* = 0)
130 : _data(cont.data()), _size(cont.size())
131 {
132 TF_DEV_AXIOM(_size == 0 || _data);
133 }
134
135 /// Construct a span from a container.
136 /// The resulting span has a range of
137 /// [cont.data(), cont.data()+cont.size())
138 template <class Container>
139 TfSpan(const Container& cont,
140 typename std::enable_if<
141 std::is_same<typename Container::value_type, value_type
142 >::value, Container
143 >::type* = 0)
144 : _data(cont.data()), _size(cont.size())
145 {
146 TF_DEV_AXIOM(_size == 0 || _data);
147 }
148
149 /// Return a pointer to the first element of the span.
data()150 pointer data() const noexcept { return _data; }
151
152 /// Return the total number of elements in the span.
size()153 index_type size() const noexcept { return _size; }
154
155 /// Returns true if this span contains no elements, false otherwise.
empty()156 bool empty() const noexcept { return _size == 0; }
157
158 /// Returns a reference to the \p idx'th element of the span.
159 /// In debug builds, a runtime assertion will fail if \p idx is out of
160 /// range. The behavior is otherwise undefined if \p idx is out of range.
161 reference operator[](index_type idx) const {
162 TF_DEV_AXIOM(idx < _size);
163 return _data[idx];
164 }
165
166 /// Return a reference to the first element in the span.
front()167 reference front() const {
168 TF_DEV_AXIOM(!empty());
169 return *begin();
170 }
171
172 /// Return a reference to the last element in the span.
back()173 reference back() const {
174 TF_DEV_AXIOM(!empty());
175 return *(end() - 1);
176 }
177
178 /// Returns a non-const iterator the start of the span.
begin()179 iterator begin() const noexcept { return _data; }
180
181 /// Returns a cons iterator to the start of the span.
cbegin()182 const_iterator cbegin() const noexcept { return _data; }
183
184 /// Returns a non-const iterator to the end of the span.
end()185 iterator end() const noexcept { return _data + _size; }
186
187 /// Returns a const iterator to the end of the span.
cend()188 const_iterator cend() const noexcept { return _data + _size; }
189
190 /// Returns a non-const reverse iterator the start of the span.
rbegin()191 reverse_iterator rbegin() const noexcept
192 { return reverse_iterator(end()); }
193
194 /// Returns a cons reverse iterator to the start of the span.
crbegin()195 const_reverse_iterator crbegin() const noexcept
196 { return const_reverse_iterator(cend()); }
197
198 /// Returns a non-const reverse iterator to the end of the span.
rend()199 reverse_iterator rend() const noexcept
200 { return reverse_iterator(begin()); }
201
202 /// Returns a const reverse iterator to the end of the span.
crend()203 const_reverse_iterator crend() const noexcept
204 { return const_reverse_iterator(cbegin()); }
205
206 /// Returns a new span referencing a sub-range of this span.
207 /// If \p count == -1 (or std::dynamic_extent in C++20), the new span
208 /// has a range of [data()+offset, data()+size()). Otherwise, the new
209 /// span has range [data()+offset, data()+offset+count).
210 TfSpan<T> subspan(difference_type offset, difference_type count=-1) const {
211 TF_DEV_AXIOM(offset >= 0 && (index_type)offset < _size);
212 if (count == -1) {
213 return TfSpan<T>(_data + offset, _size - offset);
214 } else {
215 TF_DEV_AXIOM(count >= 0);
216 TF_DEV_AXIOM(((index_type)offset+(index_type)count) <= _size);
217 return TfSpan<T>(_data + offset, count);
218 }
219 }
220
221 /// Return a subspan consisting of the first \p count elements of this span.
first(size_t count)222 TfSpan<T> first(size_t count) const {
223 return subspan(0, count);
224 }
225
226 /// Return a subspan consisting of the last \p count elements of this span.
last(size_t count)227 TfSpan<T> last(size_t count) const {
228 TF_DEV_AXIOM(_size >= count);
229 return TfSpan<T>(end() - count, count);
230 }
231
232 private:
233 pointer _data = nullptr;
234 index_type _size = 0;
235 };
236
237
238 /// Helper for constructing a non-const TfSpan from a container.
239 template <typename Container>
240 TfSpan<typename Container::value_type>
TfMakeSpan(Container & cont)241 TfMakeSpan(Container& cont)
242 {
243 return TfSpan<typename Container::value_type>(cont);
244 }
245
246
247 /// Helper for constructing a const TfSpan from a container.
248 template <typename Container>
249 TfSpan<const typename Container::value_type>
TfMakeConstSpan(const Container & cont)250 TfMakeConstSpan(const Container& cont)
251 {
252 return TfSpan<const typename Container::value_type>(cont);
253 }
254
255 PXR_NAMESPACE_CLOSE_SCOPE
256
257 #endif // PXR_BASE_TF_SPAN_H
258