protozero  1.6.3
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 
167  using iterator_category = std::random_access_iterator_tag;
168  using value_type = T;
169  using difference_type = std::ptrdiff_t;
170  using pointer = value_type*;
171  using reference = value_type&;
172 
173  const_fixed_iterator() noexcept = default;
174 
175  explicit const_fixed_iterator(const char* data) noexcept :
176  m_data(data) {
177  }
178 
179  const_fixed_iterator(const const_fixed_iterator&) noexcept = default;
180  const_fixed_iterator(const_fixed_iterator&&) noexcept = default;
181 
182  const_fixed_iterator& operator=(const const_fixed_iterator&) noexcept = default;
183  const_fixed_iterator& operator=(const_fixed_iterator&&) noexcept = default;
184 
185  ~const_fixed_iterator() noexcept = default;
186 
187  value_type operator*() const noexcept {
188  value_type result;
189  std::memcpy(&result, m_data, sizeof(value_type));
190 #if PROTOZERO_BYTE_ORDER != PROTOZERO_LITTLE_ENDIAN
191  byteswap_inplace(&result);
192 #endif
193  return result;
194  }
195 
196  const_fixed_iterator& operator++() noexcept {
197  m_data += sizeof(value_type);
198  return *this;
199  }
200 
201  const_fixed_iterator operator++(int) noexcept {
202  const const_fixed_iterator tmp{*this};
203  ++(*this);
204  return tmp;
205  }
206 
207  bool operator==(const_fixed_iterator rhs) const noexcept {
208  return m_data == rhs.m_data;
209  }
210 
211  bool operator!=(const_fixed_iterator rhs) const noexcept {
212  return !(*this == rhs);
213  }
214 
215  const_fixed_iterator& operator--() noexcept {
216  m_data -= sizeof(value_type);
217  return *this;
218  }
219 
220  const_fixed_iterator operator--(int) noexcept {
221  const const_fixed_iterator tmp{*this};
222  --(*this);
223  return tmp;
224  }
225 
226  friend bool operator<(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
227  return lhs.m_data < rhs.m_data;
228  }
229 
230  friend bool operator>(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
231  return rhs < lhs;
232  }
233 
234  friend bool operator<=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
235  return !(lhs > rhs);
236  }
237 
238  friend bool operator>=(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
239  return !(lhs < rhs);
240 
241  }
242 
243  const_fixed_iterator& operator+=(difference_type val) noexcept {
244  m_data += (sizeof(value_type) * val);
245  return *this;
246  }
247 
248  friend const_fixed_iterator operator+(const_fixed_iterator lhs, difference_type rhs) noexcept {
249  const_fixed_iterator tmp{lhs};
250  tmp.m_data += (sizeof(value_type) * rhs);
251  return tmp;
252  }
253 
254  friend const_fixed_iterator operator+(difference_type lhs, const_fixed_iterator rhs) noexcept {
255  const_fixed_iterator tmp{rhs};
256  tmp.m_data += (sizeof(value_type) * lhs);
257  return tmp;
258  }
259 
260  const_fixed_iterator& operator-=(difference_type val) noexcept {
261  m_data -= (sizeof(value_type) * val);
262  return *this;
263  }
264 
265  friend const_fixed_iterator operator-(const_fixed_iterator lhs, difference_type rhs) noexcept {
266  const_fixed_iterator tmp{lhs};
267  tmp.m_data -= (sizeof(value_type) * rhs);
268  return tmp;
269  }
270 
271  friend difference_type operator-(const_fixed_iterator lhs, const_fixed_iterator rhs) noexcept {
272  return static_cast<difference_type>(lhs.m_data - rhs.m_data) / static_cast<difference_type>(sizeof(T));
273  }
274 
275  value_type operator[](difference_type n) const noexcept {
276  return *(*this + n);
277  }
278 
279 }; // class const_fixed_iterator
280 
285 template <typename T>
287 
288 protected:
289 
291  const char* m_data = nullptr;
292 
294  const char* m_end = nullptr;
295 
296 public:
297 
298  using iterator_category = std::forward_iterator_tag;
299  using value_type = T;
300  using difference_type = std::ptrdiff_t;
301  using pointer = value_type*;
302  using reference = value_type&;
303 
304  static difference_type distance(const_varint_iterator begin, const_varint_iterator end) noexcept {
305  // The "distance" between default initialized const_varint_iterator's
306  // is always 0.
307  if (!begin.m_data) {
308  return 0;
309  }
310  // We know that each varint contains exactly one byte with the most
311  // significant bit not set. We can use this to quickly figure out
312  // how many varints there are without actually decoding the varints.
313  return std::count_if(begin.m_data, end.m_data, [](char c) noexcept {
314  return (static_cast<unsigned char>(c) & 0x80u) == 0;
315  });
316  }
317 
318  const_varint_iterator() noexcept = default;
319 
320  const_varint_iterator(const char* data, const char* end) noexcept :
321  m_data(data),
322  m_end(end) {
323  }
324 
325  const_varint_iterator(const const_varint_iterator&) noexcept = default;
326  const_varint_iterator(const_varint_iterator&&) noexcept = default;
327 
328  const_varint_iterator& operator=(const const_varint_iterator&) noexcept = default;
329  const_varint_iterator& operator=(const_varint_iterator&&) noexcept = default;
330 
331  ~const_varint_iterator() noexcept = default;
332 
333  value_type operator*() const {
334  protozero_assert(m_data);
335  const char* d = m_data; // will be thrown away
336  return static_cast<value_type>(decode_varint(&d, m_end));
337  }
338 
339  const_varint_iterator& operator++() {
340  protozero_assert(m_data);
342  return *this;
343  }
344 
345  const_varint_iterator operator++(int) {
346  protozero_assert(m_data);
347  const const_varint_iterator tmp{*this};
348  ++(*this);
349  return tmp;
350  }
351 
352  bool operator==(const const_varint_iterator& rhs) const noexcept {
353  return m_data == rhs.m_data && m_end == rhs.m_end;
354  }
355 
356  bool operator!=(const const_varint_iterator& rhs) const noexcept {
357  return !(*this == rhs);
358  }
359 
360 }; // class const_varint_iterator
361 
366 template <typename T>
368 
369 public:
370 
371  using iterator_category = std::forward_iterator_tag;
372  using value_type = T;
373  using difference_type = std::ptrdiff_t;
374  using pointer = value_type*;
375  using reference = value_type&;
376 
377  const_svarint_iterator() noexcept :
379  }
380 
381  const_svarint_iterator(const char* data, const char* end) noexcept :
382  const_varint_iterator<T>(data, end) {
383  }
384 
386  const_svarint_iterator(const_svarint_iterator&&) noexcept = default;
387 
388  const_svarint_iterator& operator=(const const_svarint_iterator&) = default;
389  const_svarint_iterator& operator=(const_svarint_iterator&&) noexcept = default;
390 
391  ~const_svarint_iterator() = default;
392 
393  value_type operator*() const {
394  protozero_assert(this->m_data);
395  const char* d = this->m_data; // will be thrown away
396  return static_cast<value_type>(decode_zigzag64(decode_varint(&d, this->m_end)));
397  }
398 
399  const_svarint_iterator& operator++() {
400  protozero_assert(this->m_data);
401  skip_varint(&this->m_data, this->m_end);
402  return *this;
403  }
404 
405  const_svarint_iterator operator++(int) {
406  protozero_assert(this->m_data);
407  const const_svarint_iterator tmp{*this};
408  ++(*this);
409  return tmp;
410  }
411 
412 }; // class const_svarint_iterator
413 
414 } // end namespace protozero
415 
416 namespace std {
417 
418  // Specialize std::distance for all the protozero iterators. Because
419  // functions can't be partially specialized, we have to do this for
420  // every value_type we are using.
421 
422  template <>
423  inline typename protozero::const_varint_iterator<int32_t>::difference_type
424  distance<protozero::const_varint_iterator<int32_t>>(protozero::const_varint_iterator<int32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
427  }
428 
429  template <>
430  inline typename protozero::const_varint_iterator<int64_t>::difference_type
431  distance<protozero::const_varint_iterator<int64_t>>(protozero::const_varint_iterator<int64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
434  }
435 
436  template <>
437  inline typename protozero::const_varint_iterator<uint32_t>::difference_type
438  distance<protozero::const_varint_iterator<uint32_t>>(protozero::const_varint_iterator<uint32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
441  }
442 
443  template <>
444  inline typename protozero::const_varint_iterator<uint64_t>::difference_type
445  distance<protozero::const_varint_iterator<uint64_t>>(protozero::const_varint_iterator<uint64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
448  }
449 
450  template <>
451  inline typename protozero::const_svarint_iterator<int32_t>::difference_type
452  distance<protozero::const_svarint_iterator<int32_t>>(protozero::const_svarint_iterator<int32_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
455  }
456 
457  template <>
458  inline typename protozero::const_svarint_iterator<int64_t>::difference_type
459  distance<protozero::const_svarint_iterator<int64_t>>(protozero::const_svarint_iterator<int64_t> first, // NOLINT(readability-inconsistent-declaration-parameter-name)
462  }
463 
464 } // end namespace std
465 
466 #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:182
Definition: iterators.hpp:160
void swap(iterator_range &other) noexcept
Definition: iterators.hpp:136
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:416
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
void skip_varint(const char **data, const char *end)
Definition: varint.hpp:112
void drop_front()
Definition: iterators.hpp:126
const char * m_end
Pointer to end iterator position.
Definition: iterators.hpp:294
std::size_t size() const noexcept
Definition: iterators.hpp:107
const char * m_data
Pointer to current iterator position.
Definition: iterators.hpp:291
Contains functions to swap bytes in values (for different endianness).
constexpr iterator_range()
Definition: iterators.hpp:58
Definition: iterators.hpp:367
Definition: iterators.hpp:286
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
void swap(data_view &lhs, data_view &rhs) noexcept
Definition: data_view.hpp:165