TLA Line data Source 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
102 HIT 202 : skip_forward() noexcept
103 : {
104 363 : while(current_ != end_)
105 : {
106 334 : current_buffer_ = buffer_type(*current_);
107 334 : if(current_buffer_.size() > 0)
108 173 : return;
109 161 : ++current_;
110 : }
111 29 : current_buffer_ = {};
112 : }
113 :
114 : // Move to the previous non-empty buffer, positioned past its last byte
115 : void
116 155 : skip_backward() noexcept
117 : {
118 : do
119 : {
120 277 : --current_;
121 277 : current_buffer_ = buffer_type(*current_);
122 : }
123 277 : while(current_buffer_.size() == 0);
124 155 : current_buffer_position_ = current_buffer_.size();
125 155 : }
126 :
127 : void
128 318 : advance(std::ptrdiff_t n) noexcept
129 : {
130 318 : if(n >= 0)
131 : {
132 177 : auto left = static_cast<std::size_t>(n);
133 349 : while(left > 0)
134 : {
135 269 : std::size_t const avail =
136 269 : current_buffer_.size() - current_buffer_position_;
137 269 : if(left < avail)
138 : {
139 97 : current_buffer_position_ += left;
140 97 : position_ += left;
141 97 : return;
142 : }
143 172 : left -= avail;
144 172 : position_ += avail;
145 172 : ++current_;
146 172 : current_buffer_position_ = 0;
147 172 : skip_forward();
148 : }
149 : }
150 : else
151 : {
152 141 : auto left = static_cast<std::size_t>(-n);
153 296 : while(left > 0)
154 : {
155 296 : if(left <= current_buffer_position_)
156 : {
157 141 : current_buffer_position_ -= left;
158 141 : position_ -= left;
159 141 : return;
160 : }
161 155 : left -= current_buffer_position_;
162 155 : position_ -= current_buffer_position_;
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.
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
196 18 : begin(BufferSequence const& bs) noexcept
197 : {
198 18 : buffers_iterator it;
199 18 : it.current_ = buffer_sequence_begin(bs);
200 18 : it.end_ = buffer_sequence_end(bs);
201 18 : it.skip_forward();
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
213 24 : end(BufferSequence const& bs) noexcept
214 : {
215 24 : buffers_iterator it;
216 24 : it.current_ = buffer_sequence_end(bs);
217 24 : it.end_ = it.current_;
218 24 : it.position_ = buffer_size(bs);
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
228 125 : operator*() const noexcept
229 : {
230 : return static_cast<pointer>(
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
253 33 : operator[](difference_type n) const noexcept
254 : {
255 33 : return *(*this + n);
256 : }
257 :
258 : /// Advance to the next byte.
259 : buffers_iterator&
260 59 : operator++() noexcept
261 : {
262 59 : ++position_;
263 59 : if(++current_buffer_position_ < current_buffer_.size())
264 47 : return *this;
265 12 : ++current_;
266 12 : current_buffer_position_ = 0;
267 12 : skip_forward();
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&
282 20 : operator--() noexcept
283 : {
284 20 : advance(-1);
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&
307 166 : operator+=(difference_type n) noexcept
308 : {
309 166 : advance(n);
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&
323 132 : operator-=(difference_type n) noexcept
324 : {
325 132 : advance(-n);
326 132 : return *this;
327 : }
328 :
329 : /// Return an iterator `n` bytes after `it`.
330 : friend
331 : buffers_iterator
332 166 : operator+(buffers_iterator it, difference_type n) noexcept
333 : {
334 166 : it += n;
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
350 11 : operator-(buffers_iterator it, difference_type n) noexcept
351 : {
352 11 : it -= n;
353 11 : return it;
354 : }
355 :
356 : /// Return the number of bytes from `b` to `a`.
357 : friend
358 : difference_type
359 264 : operator-(
360 : buffers_iterator const& a,
361 : buffers_iterator const& b) noexcept
362 : {
363 264 : return static_cast<difference_type>(a.position_) -
364 264 : static_cast<difference_type>(b.position_);
365 : }
366 :
367 : /// Test whether two iterators refer to the same byte.
368 : friend
369 : bool
370 312 : operator==(
371 : buffers_iterator const& a,
372 : buffers_iterator const& b) noexcept
373 : {
374 312 : return a.position_ == b.position_;
375 : }
376 :
377 : /// Order two iterators by byte position.
378 : friend
379 : std::strong_ordering
380 121 : operator<=>(
381 : buffers_iterator const& a,
382 : buffers_iterator const& b) noexcept
383 : {
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>
398 17 : buffers_begin(BufferSequence const& bs) noexcept
399 : {
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>
418 24 : buffers_end(BufferSequence const& bs) noexcept
419 : {
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
|
