include/boost/capy/buffers/buffers_iterator.hpp

100.0% Lines (88 / 88) 96.3% Functions (79 / 82)

[ ] prev/next file

buffers_iterator.hpp

f(x) Functions (82)

Function Calls Lines Blocks

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