protozero  1.6.7
Minimalistic protocol buffer decoder and encoder in C++.
iterators.hpp
Go to the documentation of this file.
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 
19 #include <protozero/config.hpp>
20 #include <protozero/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 
38 template <typename T, typename P = std::pair<T, T>>
40 #ifdef PROTOZERO_STRICT_API
41  protected
42 #else
43  public
44 #endif
45  P {
46 
47 public:
48 
50  using iterator = T;
51 
53  using value_type = typename std::iterator_traits<T>::value_type;
54 
58  constexpr iterator_range() :
59  P{iterator{}, iterator{}} {
60  }
61 
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 
74  constexpr iterator begin() const noexcept {
75  return this->first;
76  }
77 
79  constexpr iterator end() const noexcept {
80  return this->second;
81  }
82 
84  constexpr iterator cbegin() const noexcept {
85  return this->first;
86  }
87 
89  constexpr iterator cend() const noexcept {
90  return this->second;
91  }
92 
98  constexpr bool empty() const noexcept {
99  return begin() == end();
100  }
101 
107  std::size_t size() const noexcept {
108  return static_cast<size_t>(std::distance(begin(), end()));
109  }
110 
116  value_type front() const {
117  protozero_assert(!empty());
118  return *(this->first);
119  }
120 
126  void drop_front() {
127  protozero_assert(!empty());
128  ++this->first;
129  }
130 
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 
150 template <typename T>
151 inline void swap(iterator_range<T>& lhs, iterator_range<T>& rhs) noexcept {
152  lhs.swap(rhs);
153 }
154 
159 template <typename T>
161 
163  const char* m_data = nullptr;
164 
165 public:
166 
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 
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 
189  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 
198  const_fixed_iterator& operator++() noexcept {
199  m_data += sizeof(value_type);
200  return *this;
201  }
202 
203  const_fixed_iterator operator++(int) noexcept {
204  const const_fixed_iterator tmp{*this};
205  ++(*this);
206  return tmp;
207  }
208 
209  const_fixed_iterator& operator--() noexcept {
210  m_data -= sizeof(value_type);
211  return *this;
212  }
213 
214  const_fixed_iterator operator--(int) noexcept {
215  const const_fixed_iterator tmp{*this};
216  --(*this);
217  return tmp;
218  }
219 
220  friend bool operator==(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
221  return lhs.m_data == rhs.m_data;
222  }
223 
224  friend bool operator!=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
225  return !(lhs == rhs);
226  }
227 
228  friend bool operator<(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
229  return lhs.m_data < rhs.m_data;
230  }
231 
232  friend bool operator>(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
233  return rhs < lhs;
234  }
235 
236  friend bool operator<=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
237  return !(lhs > rhs);
238  }
239 
240  friend bool operator>=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
241  return !(lhs < rhs);
242  }
243 
244  const_fixed_iterator& operator+=(difference_type val) noexcept {
245  m_data += (sizeof(value_type) * val);
246  return *this;
247  }
248 
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 
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 
261  const_fixed_iterator& operator-=(difference_type val) noexcept {
262  m_data -= (sizeof(value_type) * val);
263  return *this;
264  }
265 
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 
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 
276  value_type operator[](difference_type n) const noexcept {
277  return *(*this + n);
278  }
279 
281 
282 }; // class const_fixed_iterator
283 
288 template <typename T>
290 
291 protected:
292 
294  const char* m_data = nullptr;
295 
297  const char* m_end = nullptr;
298 
299 public:
300 
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 
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 
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 
338  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 
344  const_varint_iterator& operator++() {
345  protozero_assert(m_data);
346  skip_varint(&m_data, m_end);
347  return *this;
348  }
349 
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 
357  bool operator==(const const_varint_iterator& rhs) const noexcept {
358  return m_data == rhs.m_data && m_end == rhs.m_end;
359  }
360 
361  bool operator!=(const const_varint_iterator& rhs) const noexcept {
362  return !(*this == rhs);
363  }
364 
366 
367 }; // class const_varint_iterator
368 
373 template <typename T>
375 
376 public:
377 
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 
386  const_svarint_iterator() noexcept :
388  }
389 
390  const_svarint_iterator(const char* data, const char* end) noexcept :
391  const_varint_iterator<T>{data, end} {
392  }
393 
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 
402  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 
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 
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 
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 
434 
435  template <>
437  distance<protozero::const_varint_iterator<int32_t>>(protozero::const_varint_iterator<int32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
440  }
441 
442  template <>
444  distance<protozero::const_varint_iterator<int64_t>>(protozero::const_varint_iterator<int64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
447  }
448 
449  template <>
451  distance<protozero::const_varint_iterator<uint32_t>>(protozero::const_varint_iterator<uint32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
454  }
455 
456  template <>
458  distance<protozero::const_varint_iterator<uint64_t>>(protozero::const_varint_iterator<uint64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
461  }
462 
463  template <>
465  distance<protozero::const_svarint_iterator<int32_t>>(protozero::const_svarint_iterator<int32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
468  }
469 
470  template <>
472  distance<protozero::const_svarint_iterator<int64_t>>(protozero::const_svarint_iterator<int64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
475  }
476 
478 
479 } // end namespace std
480 
481 #endif // PROTOZERO_ITERATORS_HPP
constexpr iterator cbegin() const noexcept
Return iterator to beginning of range.
Definition: iterators.hpp:84
typename std::iterator_traits< T >::value_type value_type
The value type of the underlying iterator.
Definition: iterators.hpp:53
constexpr int64_t decode_zigzag64(uint64_t value) noexcept
Definition: varint.hpp:199
Definition: iterators.hpp:160
void swap(iterator_range &other) noexcept
Definition: iterators.hpp:136
constexpr bool operator==(const data_view lhs, const data_view rhs) noexcept
Definition: data_view.hpp:176
constexpr iterator begin() const noexcept
Return iterator to beginning of range.
Definition: iterators.hpp:74
T iterator
The type of the iterators in this range.
Definition: iterators.hpp:50
constexpr iterator end() const noexcept
Return iterator to end of range.
Definition: iterators.hpp:79
Definition: iterators.hpp:427
Contains macro checks for different configurations.
constexpr iterator_range(iterator &&first_iterator, iterator &&last_iterator)
Definition: iterators.hpp:68
constexpr bool empty() const noexcept
Definition: iterators.hpp:98
void swap(iterator_range< T > &lhs, iterator_range< T > &rhs) noexcept
Definition: iterators.hpp:151
bool operator<=(const data_view lhs, const data_view rhs) noexcept
Definition: data_view.hpp:208
void skip_varint(const char **data, const char *end)
Definition: varint.hpp:112
bool operator>=(const data_view lhs, const data_view rhs) noexcept
Definition: data_view.hpp:228
void drop_front()
Definition: iterators.hpp:126
const char * m_end
Pointer to end iterator position.
Definition: iterators.hpp:297
std::size_t size() const noexcept
Definition: iterators.hpp:107
const char * m_data
Pointer to current iterator position.
Definition: iterators.hpp:294
bool operator<(const data_view lhs, const data_view rhs) noexcept
Definition: data_view.hpp:198
Contains functions to swap bytes in values (for different endianness).
bool operator>(const data_view lhs, const data_view rhs) noexcept
Definition: data_view.hpp:218
constexpr iterator_range()
Definition: iterators.hpp:58
Definition: iterators.hpp:374
constexpr bool operator!=(const data_view lhs, const data_view rhs) noexcept
Definition: data_view.hpp:188
void byteswap_inplace(uint32_t *ptr) noexcept
byteswap the data pointed to by ptr in-place.
Definition: byteswap.hpp:55
Definition: iterators.hpp:289
Definition: iterators.hpp:39
Contains low-level varint and zigzag encoding and decoding functions.
value_type front() const
Definition: iterators.hpp:116
uint64_t decode_varint(const char **data, const char *end)
Definition: varint.hpp:89
constexpr iterator cend() const noexcept
Return iterator to end of range.
Definition: iterators.hpp:89
All parts of the protozero header-only library are in this namespace.
Definition: byteswap.hpp:23