. /include/boost/capy /buffers /buffers_iterator.hpp
100.00% Lines (88/88) 100.00% Functions (19/19)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
  1 + //
  2 + // Copyright (c) 2026 Steve Gerbino
  3 + //
  4 + // Distributed under the Boost Software License, Version 1.0. (See accompanying
  5 + // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  6 + //
  7 + // Official repository: https://github.com/cppalliance/capy
  8 + //
  9 +
  10 + #ifndef BOOST_CAPY_BUFFERS_BUFFERS_ITERATOR_HPP
  11 + #define BOOST_CAPY_BUFFERS_BUFFERS_ITERATOR_HPP
  12 +
  13 + #include <boost/capy/detail/config.hpp>
  14 + #include <boost/capy/buffers.hpp>
  15 +
  16 + #include <compare>
  17 + #include <cstddef>
  18 + #include <iterator>
  19 + #include <ranges>
  20 + #include <type_traits>
  21 + #include <utility>
  22 +
  23 + namespace boost {
  24 + namespace capy {
  25 +
  26 + namespace detail {
  27 +
  28 + // Walking back from the end needs an end iterator, not a sentinel
  29 + template<class T>
  30 + concept common_buffer_sequence =
  31 + ConstBufferSequence<T> &&
  32 + (ConstBuffer<T> || std::ranges::common_range<T const>);
  33 +
  34 + } // detail
  35 +
  36 + /** A random access iterator over the bytes in a buffer sequence.
  37 +
  38 + A buffer sequence stores its bytes in several separate regions.
  39 + This iterator presents them as one run of bytes, so standard
  40 + algorithms such as `std::search` can scan across the boundaries
  41 + between buffers without first copying the data into contiguous
  42 + storage. Empty buffers in the sequence are skipped.
  43 +
  44 + The iterator dereferences to `ByteType&` for a
  45 + @ref MutableBufferSequence and to `ByteType const&` otherwise.
  46 +
  47 + Moving by `n` bytes walks the underlying buffers, so `operator+=`,
  48 + `operator-=`, `operator+`, `operator-` with an integer, and
  49 + `operator[]` are linear in the number of buffers crossed. Comparison
  50 + and the difference of two iterators are constant time.
  51 +
  52 + @par Preconditions
  53 + The buffer sequence and the memory it refers to outlive every
  54 + iterator obtained from it. Iterators from different sequences are
  55 + not comparable.
  56 +
  57 + @par Example
  58 + @code
  59 + std::array<capy::const_buffer, 2> bufs{
  60 + capy::make_buffer(std::string_view("GET / HTTP/1.1\r")),
  61 + capy::make_buffer(std::string_view("\n\r\nbody")) };
  62 +
  63 + // Find the end of the header, which spans both buffers
  64 + char const crlfcrlf[] = "\r\n\r\n";
  65 + auto it = std::search(
  66 + capy::buffers_begin(bufs), capy::buffers_end(bufs),
  67 + crlfcrlf, crlfcrlf + 4);
  68 + std::size_t header_size = it - capy::buffers_begin(bufs) + 4;
  69 + @endcode
  70 +
  71 + @tparam BufferSequence The buffer sequence type. It must be a single
  72 + buffer, or a range of buffers whose begin and end have the same type.
  73 +
  74 + @tparam ByteType The byte type presented by the iterator. Its size
  75 + must be 1.
  76 +
  77 + @see @ref buffers_begin, @ref buffers_end,
  78 + @ref buffer_sequence_begin
  79 + */
  80 + template<class BufferSequence, class ByteType = char>
  81 + requires detail::common_buffer_sequence<BufferSequence>
  82 + class buffers_iterator
  83 + {
  84 + static_assert(sizeof(ByteType) == 1, "ByteType must be a byte");
  85 +
  86 + using sequence_iterator = decltype(
  87 + buffer_sequence_begin(std::declval<BufferSequence const&>()));
  88 + using buffer_type = capy::buffer_type<BufferSequence>;
  89 + using byte_type = std::conditional_t<
  90 + MutableBufferSequence<BufferSequence>,
  91 + ByteType,
  92 + ByteType const>;
  93 +
  94 + buffer_type current_buffer_{};
  95 + std::size_t current_buffer_position_ = 0;
  96 + sequence_iterator current_{};
  97 + sequence_iterator end_{};
  98 + std::size_t position_ = 0;
  99 +
  100 + // Move to the next non-empty buffer, or to the end of the sequence
  101 + void
HITGNC   102 + 202 skip_forward() noexcept
  103 + {
HITGNC   104 + 363 while(current_ != end_)
  105 + {
HITGNC   106 + 334 current_buffer_ = buffer_type(*current_);
HITGNC   107 + 334 if(current_buffer_.size() > 0)
HITGNC   108 + 173 return;
HITGNC   109 + 161 ++current_;
  110 + }
HITGNC   111 + 29 current_buffer_ = {};
  112 + }
  113 +
  114 + // Move to the previous non-empty buffer, positioned past its last byte
  115 + void
HITGNC   116 + 155 skip_backward() noexcept
  117 + {
  118 + do
  119 + {
HITGNC   120 + 277 --current_;
HITGNC   121 + 277 current_buffer_ = buffer_type(*current_);
  122 + }
HITGNC   123 + 277 while(current_buffer_.size() == 0);
HITGNC   124 + 155 current_buffer_position_ = current_buffer_.size();
HITGNC   125 + 155 }
  126 +
  127 + void
HITGNC   128 + 318 advance(std::ptrdiff_t n) noexcept
  129 + {
HITGNC   130 + 318 if(n >= 0)
  131 + {
HITGNC   132 + 177 auto left = static_cast<std::size_t>(n);
HITGNC   133 + 349 while(left > 0)
  134 + {
HITGNC   135 + 269 std::size_t const avail =
HITGNC   136 + 269 current_buffer_.size() - current_buffer_position_;
HITGNC   137 + 269 if(left < avail)
  138 + {
HITGNC   139 + 97 current_buffer_position_ += left;
HITGNC   140 + 97 position_ += left;
HITGNC   141 + 97 return;
  142 + }
HITGNC   143 + 172 left -= avail;
HITGNC   144 + 172 position_ += avail;
HITGNC   145 + 172 ++current_;
HITGNC   146 + 172 current_buffer_position_ = 0;
HITGNC   147 + 172 skip_forward();
  148 + }
  149 + }
  150 + else
  151 + {
HITGNC   152 + 141 auto left = static_cast<std::size_t>(-n);
HITGNC   153 + 296 while(left > 0)
  154 + {
HITGNC   155 + 296 if(left <= current_buffer_position_)
  156 + {
HITGNC   157 + 141 current_buffer_position_ -= left;
HITGNC   158 + 141 position_ -= left;
HITGNC   159 + 141 return;
  160 + }
HITGNC   161 + 155 left -= current_buffer_position_;
HITGNC   162 + 155 position_ -= current_buffer_position_;
HITGNC   163 + 155 skip_backward();
  164 + }
  165 + }
  166 + }
  167 +
  168 + public:
  169 + /// The signed type of the distance between two iterators.
  170 + using difference_type = std::ptrdiff_t;
  171 +
  172 + /// The type of the bytes the iterator visits.
  173 + using value_type = ByteType;
  174 +
  175 + /// The type returned by `operator->`.
  176 + using pointer = byte_type*;
  177 +
  178 + /// The type returned by `operator*`.
  179 + using reference = byte_type&;
  180 +
  181 + /// The iterator category.
  182 + using iterator_category = std::random_access_iterator_tag;
  183 +
  184 + /// Construct a singular iterator.
HITGNC   185 + 14 buffers_iterator() = default;
  186 +
  187 + /** Return an iterator to the first byte of a buffer sequence.
  188 +
  189 + @param bs The buffer sequence. It must outlive the iterator.
  190 +
  191 + @return An iterator to the first byte, or the end iterator if
  192 + the sequence holds no bytes.
  193 + */
  194 + static
  195 + buffers_iterator
HITGNC   196 + 18 begin(BufferSequence const& bs) noexcept
  197 + {
HITGNC   198 + 18 buffers_iterator it;
HITGNC   199 + 18 it.current_ = buffer_sequence_begin(bs);
HITGNC   200 + 18 it.end_ = buffer_sequence_end(bs);
HITGNC   201 + 18 it.skip_forward();
HITGNC   202 + 18 return it;
  203 + }
  204 +
  205 + /** Return an iterator past the last byte of a buffer sequence.
  206 +
  207 + @param bs The buffer sequence. It must outlive the iterator.
  208 +
  209 + @return The end iterator.
  210 + */
  211 + static
  212 + buffers_iterator
HITGNC   213 + 24 end(BufferSequence const& bs) noexcept
  214 + {
HITGNC   215 + 24 buffers_iterator it;
HITGNC   216 + 24 it.current_ = buffer_sequence_end(bs);
HITGNC   217 + 24 it.end_ = it.current_;
HITGNC   218 + 24 it.position_ = buffer_size(bs);
HITGNC   219 + 24 return it;
  220 + }
  221 +
  222 + /** Return a reference to the current byte.
  223 +
  224 + @par Preconditions
  225 + The iterator is not the end iterator.
  226 + */
  227 + reference
HITGNC   228 + 125 operator*() const noexcept
  229 + {
  230 + return static_cast<pointer>(
HITGNC   231 + 125 current_buffer_.data())[current_buffer_position_];
  232 + }
  233 +
  234 + /** Return a pointer to the current byte.
  235 +
  236 + @par Preconditions
  237 + The iterator is not the end iterator.
  238 + */
  239 + pointer
  240 + operator->() const noexcept
  241 + {
  242 + return &**this;
  243 + }
  244 +
  245 + /** Return a reference to the byte `n` positions away.
  246 +
  247 + @par Complexity
  248 + Linear in the number of buffers crossed.
  249 +
  250 + @param n The offset from this iterator, in bytes.
  251 + */
  252 + reference
HITGNC   253 + 33 operator[](difference_type n) const noexcept
  254 + {
HITGNC   255 + 33 return *(*this + n);
  256 + }
  257 +
  258 + /// Advance to the next byte.
  259 + buffers_iterator&
HITGNC   260 + 59 operator++() noexcept
  261 + {
HITGNC   262 + 59 ++position_;
HITGNC   263 + 59 if(++current_buffer_position_ < current_buffer_.size())
HITGNC   264 + 47 return *this;
HITGNC   265 + 12 ++current_;
HITGNC   266 + 12 current_buffer_position_ = 0;
HITGNC   267 + 12 skip_forward();
HITGNC   268 + 12 return *this;
  269 + }
  270 +
  271 + /// Advance to the next byte, returning the previous position.
  272 + buffers_iterator
  273 + operator++(int) noexcept
  274 + {
  275 + auto tmp = *this;
  276 + ++*this;
  277 + return tmp;
  278 + }
  279 +
  280 + /// Move back to the previous byte.
  281 + buffers_iterator&
HITGNC   282 + 20 operator--() noexcept
  283 + {
HITGNC   284 + 20 advance(-1);
HITGNC   285 + 20 return *this;
  286 + }
  287 +
  288 + /// Move back to the previous byte, returning the previous position.
  289 + buffers_iterator
  290 + operator--(int) noexcept
  291 + {
  292 + auto tmp = *this;
  293 + --*this;
  294 + return tmp;
  295 + }
  296 +
  297 + /** Move by `n` bytes.
  298 +
  299 + @par Complexity
  300 + Linear in the number of buffers crossed.
  301 +
  302 + @param n The number of bytes to move; negative moves backward.
  303 +
  304 + @return A reference to `*this`.
  305 + */
  306 + buffers_iterator&
HITGNC   307 + 166 operator+=(difference_type n) noexcept
  308 + {
HITGNC   309 + 166 advance(n);
HITGNC   310 + 166 return *this;
  311 + }
  312 +
  313 + /** Move back by `n` bytes.
  314 +
  315 + @par Complexity
  316 + Linear in the number of buffers crossed.
  317 +
  318 + @param n The number of bytes to move back.
  319 +
  320 + @return A reference to `*this`.
  321 + */
  322 + buffers_iterator&
HITGNC   323 + 132 operator-=(difference_type n) noexcept
  324 + {
HITGNC   325 + 132 advance(-n);
HITGNC   326 + 132 return *this;
  327 + }
  328 +
  329 + /// Return an iterator `n` bytes after `it`.
  330 + friend
  331 + buffers_iterator
HITGNC   332 + 166 operator+(buffers_iterator it, difference_type n) noexcept
  333 + {
HITGNC   334 + 166 it += n;
HITGNC   335 + 166 return it;
  336 + }
  337 +
  338 + /// Return an iterator `n` bytes after `it`.
  339 + friend
  340 + buffers_iterator
  341 + operator+(difference_type n, buffers_iterator it) noexcept
  342 + {
  343 + it += n;
  344 + return it;
  345 + }
  346 +
  347 + /// Return an iterator `n` bytes before `it`.
  348 + friend
  349 + buffers_iterator
HITGNC   350 + 11 operator-(buffers_iterator it, difference_type n) noexcept
  351 + {
HITGNC   352 + 11 it -= n;
HITGNC   353 + 11 return it;
  354 + }
  355 +
  356 + /// Return the number of bytes from `b` to `a`.
  357 + friend
  358 + difference_type
HITGNC   359 + 264 operator-(
  360 + buffers_iterator const& a,
  361 + buffers_iterator const& b) noexcept
  362 + {
HITGNC   363 + 264 return static_cast<difference_type>(a.position_) -
HITGNC   364 + 264 static_cast<difference_type>(b.position_);
  365 + }
  366 +
  367 + /// Test whether two iterators refer to the same byte.
  368 + friend
  369 + bool
HITGNC   370 + 312 operator==(
  371 + buffers_iterator const& a,
  372 + buffers_iterator const& b) noexcept
  373 + {
HITGNC   374 + 312 return a.position_ == b.position_;
  375 + }
  376 +
  377 + /// Order two iterators by byte position.
  378 + friend
  379 + std::strong_ordering
HITGNC   380 + 121 operator<=>(
  381 + buffers_iterator const& a,
  382 + buffers_iterator const& b) noexcept
  383 + {
HITGNC   384 + 121 return a.position_ <=> b.position_;
  385 + }
  386 + };
  387 +
  388 + /** Return an iterator to the first byte of a buffer sequence.
  389 +
  390 + @param bs The buffer sequence. It must outlive the iterator.
  391 +
  392 + @return `buffers_iterator<BufferSequence>::begin(bs)`.
  393 +
  394 + @see @ref buffers_iterator, @ref buffers_end
  395 + */
  396 + template<detail::common_buffer_sequence BufferSequence>
  397 + buffers_iterator<BufferSequence>
HITGNC   398 + 17 buffers_begin(BufferSequence const& bs) noexcept
  399 + {
HITGNC   400 + 17 return buffers_iterator<BufferSequence>::begin(bs);
  401 + }
  402 +
  403 + /// Rejects a temporary sequence, since the iterator would dangle.
  404 + template<detail::common_buffer_sequence BufferSequence>
  405 + buffers_iterator<BufferSequence>
  406 + buffers_begin(BufferSequence const&& bs) = delete;
  407 +
  408 + /** Return an iterator past the last byte of a buffer sequence.
  409 +
  410 + @param bs The buffer sequence. It must outlive the iterator.
  411 +
  412 + @return `buffers_iterator<BufferSequence>::end(bs)`.
  413 +
  414 + @see @ref buffers_iterator, @ref buffers_begin
  415 + */
  416 + template<detail::common_buffer_sequence BufferSequence>
  417 + buffers_iterator<BufferSequence>
HITGNC   418 + 24 buffers_end(BufferSequence const& bs) noexcept
  419 + {
HITGNC   420 + 24 return buffers_iterator<BufferSequence>::end(bs);
  421 + }
  422 +
  423 + /// Rejects a temporary sequence, since the iterator would dangle.
  424 + template<detail::common_buffer_sequence BufferSequence>
  425 + buffers_iterator<BufferSequence>
  426 + buffers_end(BufferSequence const&& bs) = delete;
  427 +
  428 + } // capy
  429 + } // boost
  430 +
  431 + #endif