1 #ifndef PROTOZERO_ITERATORS_HPP
2 #define PROTOZERO_ITERATORS_HPP
3
4 /*****************************************************************************
5
6 protozero - Minimalistic protocol buffer decoder and encoder in C++.
7
8 This file is from https://github.com/mapbox/protozero where you can find more
9 documentation.
10
11 *****************************************************************************/
12
13 /**
14 * @file iterators.hpp
15 *
16 * @brief Contains the iterators for access to packed repeated fields.
17 */
18
19 #include "config.hpp"
20 #include "varint.hpp"
21
22 #if PROTOZERO_BYTE_ORDER != PROTOZERO_LITTLE_ENDIAN
23 # include <protozero/byteswap.hpp>
24 #endif
25
26 #include <algorithm>
27 #include <cstring>
28 #include <iterator>
29 #include <utility>
30
31 namespace protozero {
32
33 /**
34 * A range of iterators based on std::pair. Created from beginning and
35 * end iterators. Used as a return type from some pbf_reader methods
36 * that is easy to use with range-based for loops.
37 */
38 template <typename T, typename P = std::pair<T, T>>
39 class iterator_range :
40 #ifdef PROTOZERO_STRICT_API
41 protected
42 #else
43 public
44 #endif
45 P {
46
47 public:
48
49 /// The type of the iterators in this range.
50 using iterator = T;
51
52 /// The value type of the underlying iterator.
53 using value_type = typename std::iterator_traits<T>::value_type;
54
55 /**
56 * Default constructor. Create empty iterator_range.
57 */
iterator_range()58 constexpr iterator_range() :
59 P{iterator{}, iterator{}} {
60 }
61
62 /**
63 * Create iterator range from two iterators.
64 *
65 * @param first_iterator Iterator to beginning of range.
66 * @param last_iterator Iterator to end of range.
67 */
iterator_range(iterator && first_iterator,iterator && last_iterator)68 constexpr iterator_range(iterator&& first_iterator, iterator&& last_iterator) :
69 P{std::forward<iterator>(first_iterator),
70 std::forward<iterator>(last_iterator)} {
71 }
72
73 /// Return iterator to beginning of range.
begin() const74 constexpr iterator begin() const noexcept {
75 return this->first;
76 }
77
78 /// Return iterator to end of range.
end() const79 constexpr iterator end() const noexcept {
80 return this->second;
81 }
82
83 /// Return iterator to beginning of range.
cbegin() const84 constexpr iterator cbegin() const noexcept {
85 return this->first;
86 }
87
88 /// Return iterator to end of range.
cend() const89 constexpr iterator cend() const noexcept {
90 return this->second;
91 }
92
93 /**
94 * Return true if this range is empty.
95 *
96 * Complexity: Constant.
97 */
empty() const98 constexpr bool empty() const noexcept {
99 return begin() == end();
100 }
101
102 /**
103 * Get the size of the range, ie the number of elements it contains.
104 *
105 * Complexity: Constant or linear depending on the underlaying iterator.
106 */
size() const107 std::size_t size() const noexcept {
108 return static_cast<size_t>(std::distance(begin(), end()));
109 }
110
111 /**
112 * Get element at the beginning of the range.
113 *
114 * @pre Range must not be empty.
115 */
front() const116 value_type front() const {
117 protozero_assert(!empty());
118 return *(this->first);
119 }
120
121 /**
122 * Advance beginning of range by one.
123 *
124 * @pre Range must not be empty.
125 */
drop_front()126 void drop_front() {
127 protozero_assert(!empty());
128 ++this->first;
129 }
130
131 /**
132 * Swap the contents of this range with the other.
133 *
134 * @param other Other range to swap data with.
135 */
swap(iterator_range & other)136 void swap(iterator_range& other) noexcept {
137 using std::swap;
138 swap(this->first, other.first);
139 swap(this->second, other.second);
140 }
141
142 }; // struct iterator_range
143
144 /**
145 * Swap two iterator_ranges.
146 *
147 * @param lhs First range.
148 * @param rhs Second range.
149 */
150 template <typename T>
swap(iterator_range<T> & lhs,iterator_range<T> & rhs)151 inline void swap(iterator_range<T>& lhs, iterator_range<T>& rhs) noexcept {
152 lhs.swap(rhs);
153 }
154
155 /**
156 * A forward iterator used for accessing packed repeated fields of fixed
157 * length (fixed32, sfixed32, float, double).
158 */
159 template <typename T>
160 class const_fixed_iterator {
161
162 /// Pointer to current iterator position
163 const char* m_data = nullptr;
164
165 public:
166
167 /// @cond usual iterator functions not documented
168
169 using iterator_category = std::random_access_iterator_tag;
170 using value_type = T;
171 using difference_type = std::ptrdiff_t;
172 using pointer = value_type*;
173 using reference = value_type&;
174
175 const_fixed_iterator() noexcept = default;
176
const_fixed_iterator(const char * data)177 explicit const_fixed_iterator(const char* data) noexcept :
178 m_data{data} {
179 }
180
181 const_fixed_iterator(const const_fixed_iterator&) noexcept = default;
182 const_fixed_iterator(const_fixed_iterator&&) noexcept = default;
183
184 const_fixed_iterator& operator=(const const_fixed_iterator&) noexcept = default;
185 const_fixed_iterator& operator=(const_fixed_iterator&&) noexcept = default;
186
187 ~const_fixed_iterator() noexcept = default;
188
operator *() const189 value_type operator*() const noexcept {
190 value_type result;
191 std::memcpy(&result, m_data, sizeof(value_type));
192 #if PROTOZERO_BYTE_ORDER != PROTOZERO_LITTLE_ENDIAN
193 byteswap_inplace(&result);
194 #endif
195 return result;
196 }
197
operator ++()198 const_fixed_iterator& operator++() noexcept {
199 m_data += sizeof(value_type);
200 return *this;
201 }
202
operator ++(int)203 const_fixed_iterator operator++(int) noexcept {
204 const const_fixed_iterator tmp{*this};
205 ++(*this);
206 return tmp;
207 }
208
operator --()209 const_fixed_iterator& operator--() noexcept {
210 m_data -= sizeof(value_type);
211 return *this;
212 }
213
operator --(int)214 const_fixed_iterator operator--(int) noexcept {
215 const const_fixed_iterator tmp{*this};
216 --(*this);
217 return tmp;
218 }
219
operator ==(const_fixed_iterator lhs,const_fixed_iterator rhs)220 friend bool operator==(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
221 return lhs.m_data == rhs.m_data;
222 }
223
operator !=(const_fixed_iterator lhs,const_fixed_iterator rhs)224 friend bool operator!=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
225 return !(lhs == rhs);
226 }
227
operator <(const_fixed_iterator lhs,const_fixed_iterator rhs)228 friend bool operator<(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
229 return lhs.m_data < rhs.m_data;
230 }
231
operator >(const_fixed_iterator lhs,const_fixed_iterator rhs)232 friend bool operator>(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
233 return rhs < lhs;
234 }
235
operator <=(const_fixed_iterator lhs,const_fixed_iterator rhs)236 friend bool operator<=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
237 return !(lhs > rhs);
238 }
239
operator >=(const_fixed_iterator lhs,const_fixed_iterator rhs)240 friend bool operator>=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
241 return !(lhs < rhs);
242 }
243
operator +=(difference_type val)244 const_fixed_iterator& operator+=(difference_type val) noexcept {
245 m_data += (sizeof(value_type) * val);
246 return *this;
247 }
248
operator +(const_fixed_iterator lhs,difference_type rhs)249 friend const_fixed_iterator operator+(const_fixed_iterator lhs, difference_type rhs) noexcept {
250 const_fixed_iterator tmp{lhs};
251 tmp.m_data += (sizeof(value_type) * rhs);
252 return tmp;
253 }
254
operator +(difference_type lhs,const_fixed_iterator rhs)255 friend const_fixed_iterator operator+(difference_type lhs, const_fixed_iterator rhs) noexcept {
256 const_fixed_iterator tmp{rhs};
257 tmp.m_data += (sizeof(value_type) * lhs);
258 return tmp;
259 }
260
operator -=(difference_type val)261 const_fixed_iterator& operator-=(difference_type val) noexcept {
262 m_data -= (sizeof(value_type) * val);
263 return *this;
264 }
265
operator -(const_fixed_iterator lhs,difference_type rhs)266 friend const_fixed_iterator operator-(const_fixed_iterator lhs, difference_type rhs) noexcept {
267 const_fixed_iterator tmp{lhs};
268 tmp.m_data -= (sizeof(value_type) * rhs);
269 return tmp;
270 }
271
operator -(const_fixed_iterator lhs,const_fixed_iterator rhs)272 friend difference_type operator-(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
273 return static_cast<difference_type>(lhs.m_data - rhs.m_data) / static_cast<difference_type>(sizeof(T));
274 }
275
operator [](difference_type n) const276 value_type operator[](difference_type n) const noexcept {
277 return *(*this + n);
278 }
279
280 /// @endcond
281
282 }; // class const_fixed_iterator
283
284 /**
285 * A forward iterator used for accessing packed repeated varint fields
286 * (int32, uint32, int64, uint64, bool, enum).
287 */
288 template <typename T>
289 class const_varint_iterator {
290
291 protected:
292
293 /// Pointer to current iterator position
294 const char* m_data = nullptr; // NOLINT(misc-non-private-member-variables-in-classes, cppcoreguidelines-non-private-member-variables-in-classes,-warnings-as-errors)
295
296 /// Pointer to end iterator position
297 const char* m_end = nullptr; // NOLINT(misc-non-private-member-variables-in-classes, cppcoreguidelines-non-private-member-variables-in-classes,-warnings-as-errors)
298
299 public:
300
301 /// @cond usual iterator functions not documented
302
303 using iterator_category = std::forward_iterator_tag;
304 using value_type = T;
305 using difference_type = std::ptrdiff_t;
306 using pointer = value_type*;
307 using reference = value_type&;
308
distance(const_varint_iterator begin,const_varint_iterator end)309 static difference_type distance(const_varint_iterator begin, const_varint_iterator end) noexcept {
310 // The "distance" between default initialized const_varint_iterator's
311 // is always 0.
312 if (!begin.m_data) {
313 return 0;
314 }
315 // We know that each varint contains exactly one byte with the most
316 // significant bit not set. We can use this to quickly figure out
317 // how many varints there are without actually decoding the varints.
318 return std::count_if(begin.m_data, end.m_data, [](char c) noexcept {
319 return (static_cast<unsigned char>(c) & 0x80U) == 0;
320 });
321 }
322
323 const_varint_iterator() noexcept = default;
324
const_varint_iterator(const char * data,const char * end)325 const_varint_iterator(const char* data, const char* end) noexcept :
326 m_data{data},
327 m_end{end} {
328 }
329
330 const_varint_iterator(const const_varint_iterator&) noexcept = default;
331 const_varint_iterator(const_varint_iterator&&) noexcept = default;
332
333 const_varint_iterator& operator=(const const_varint_iterator&) noexcept = default;
334 const_varint_iterator& operator=(const_varint_iterator&&) noexcept = default;
335
336 ~const_varint_iterator() noexcept = default;
337
operator *() const338 value_type operator*() const {
339 protozero_assert(m_data);
340 const char* d = m_data; // will be thrown away
341 return static_cast<value_type>(decode_varint(&d, m_end));
342 }
343
operator ++()344 const_varint_iterator& operator++() {
345 protozero_assert(m_data);
346 skip_varint(&m_data, m_end);
347 return *this;
348 }
349
operator ++(int)350 const_varint_iterator operator++(int) {
351 protozero_assert(m_data);
352 const const_varint_iterator tmp{*this};
353 ++(*this);
354 return tmp;
355 }
356
operator ==(const const_varint_iterator & rhs) const357 bool operator==(const const_varint_iterator& rhs) const noexcept {
358 return m_data == rhs.m_data && m_end == rhs.m_end;
359 }
360
operator !=(const const_varint_iterator & rhs) const361 bool operator!=(const const_varint_iterator& rhs) const noexcept {
362 return !(*this == rhs);
363 }
364
365 /// @endcond
366
367 }; // class const_varint_iterator
368
369 /**
370 * A forward iterator used for accessing packed repeated svarint fields
371 * (sint32, sint64).
372 */
373 template <typename T>
374 class const_svarint_iterator : public const_varint_iterator<T> {
375
376 public:
377
378 /// @cond usual iterator functions not documented
379
380 using iterator_category = std::forward_iterator_tag;
381 using value_type = T;
382 using difference_type = std::ptrdiff_t;
383 using pointer = value_type*;
384 using reference = value_type&;
385
const_svarint_iterator()386 const_svarint_iterator() noexcept :
387 const_varint_iterator<T>{} {
388 }
389
const_svarint_iterator(const char * data,const char * end)390 const_svarint_iterator(const char* data, const char* end) noexcept :
391 const_varint_iterator<T>{data, end} {
392 }
393
394 const_svarint_iterator(const const_svarint_iterator&) = default;
395 const_svarint_iterator(const_svarint_iterator&&) noexcept = default;
396
397 const_svarint_iterator& operator=(const const_svarint_iterator&) = default;
398 const_svarint_iterator& operator=(const_svarint_iterator&&) noexcept = default;
399
400 ~const_svarint_iterator() = default;
401
operator *() const402 value_type operator*() const {
403 protozero_assert(this->m_data);
404 const char* d = this->m_data; // will be thrown away
405 return static_cast<value_type>(decode_zigzag64(decode_varint(&d, this->m_end)));
406 }
407
operator ++()408 const_svarint_iterator& operator++() {
409 protozero_assert(this->m_data);
410 skip_varint(&this->m_data, this->m_end);
411 return *this;
412 }
413
operator ++(int)414 const_svarint_iterator operator++(int) {
415 protozero_assert(this->m_data);
416 const const_svarint_iterator tmp{*this};
417 ++(*this);
418 return tmp;
419 }
420
421 /// @endcond
422
423 }; // class const_svarint_iterator
424
425 } // end namespace protozero
426
427 namespace std {
428
429 // Specialize std::distance for all the protozero iterators. Because
430 // functions can't be partially specialized, we have to do this for
431 // every value_type we are using.
432
433 /// @cond individual overloads do not need to be documented
434
435 template <>
436 inline typename protozero::const_varint_iterator<int32_t>::difference_type
distance(protozero::const_varint_iterator<int32_t> first,protozero::const_varint_iterator<int32_t> last)437 distance<protozero::const_varint_iterator<int32_t>>(protozero::const_varint_iterator<int32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
438 protozero::const_varint_iterator<int32_t> last) {
439 return protozero::const_varint_iterator<int32_t>::distance(first, last);
440 }
441
442 template <>
443 inline typename protozero::const_varint_iterator<int64_t>::difference_type
distance(protozero::const_varint_iterator<int64_t> first,protozero::const_varint_iterator<int64_t> last)444 distance<protozero::const_varint_iterator<int64_t>>(protozero::const_varint_iterator<int64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
445 protozero::const_varint_iterator<int64_t> last) {
446 return protozero::const_varint_iterator<int64_t>::distance(first, last);
447 }
448
449 template <>
450 inline typename protozero::const_varint_iterator<uint32_t>::difference_type
distance(protozero::const_varint_iterator<uint32_t> first,protozero::const_varint_iterator<uint32_t> last)451 distance<protozero::const_varint_iterator<uint32_t>>(protozero::const_varint_iterator<uint32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
452 protozero::const_varint_iterator<uint32_t> last) {
453 return protozero::const_varint_iterator<uint32_t>::distance(first, last);
454 }
455
456 template <>
457 inline typename protozero::const_varint_iterator<uint64_t>::difference_type
distance(protozero::const_varint_iterator<uint64_t> first,protozero::const_varint_iterator<uint64_t> last)458 distance<protozero::const_varint_iterator<uint64_t>>(protozero::const_varint_iterator<uint64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
459 protozero::const_varint_iterator<uint64_t> last) {
460 return protozero::const_varint_iterator<uint64_t>::distance(first, last);
461 }
462
463 template <>
464 inline typename protozero::const_svarint_iterator<int32_t>::difference_type
distance(protozero::const_svarint_iterator<int32_t> first,protozero::const_svarint_iterator<int32_t> last)465 distance<protozero::const_svarint_iterator<int32_t>>(protozero::const_svarint_iterator<int32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
466 protozero::const_svarint_iterator<int32_t> last) {
467 return protozero::const_svarint_iterator<int32_t>::distance(first, last);
468 }
469
470 template <>
471 inline typename protozero::const_svarint_iterator<int64_t>::difference_type
distance(protozero::const_svarint_iterator<int64_t> first,protozero::const_svarint_iterator<int64_t> last)472 distance<protozero::const_svarint_iterator<int64_t>>(protozero::const_svarint_iterator<int64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
473 protozero::const_svarint_iterator<int64_t> last) {
474 return protozero::const_svarint_iterator<int64_t>::distance(first, last);
475 }
476
477 /// @endcond
478
479 } // end namespace std
480
481 #endif // PROTOZERO_ITERATORS_HPP
482