include/boost/corosio/detail/intrusive.hpp

100.0% Lines (93/93) 100.0% List of functions (105/105) 81.2% Branches (56/69)

[ ] prev/next file n p prev/next uncovered line

intrusive.hpp

f(x) Functions (105)

Function Calls Lines Branches Blocks

Line	Branch	Hits	Source Code
1			//
2			// Copyright (c) 2025 Vinnie Falco ([email protected])
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/corosio
8			//
9
10			#ifndef BOOST_COROSIO_DETAIL_INTRUSIVE_HPP
11			#define BOOST_COROSIO_DETAIL_INTRUSIVE_HPP
12
13			namespace boost::corosio::detail {
14
15			/** An intrusive doubly linked list.
16
17			This container provides O(1) push and pop operations for
18			elements that derive from @ref node. Elements are not
19			copied or moved; they are linked directly into the list.
20
21			@tparam T The element type. Must derive from `intrusive_list<T>::node`.
22			*/
23			template<class T>
24			class intrusive_list
25			{
26			public:
27			/** Base class for list elements.
28
29			Derive from this class to make a type usable with
30			@ref intrusive_list. The `next_` and `prev_` pointers
31			are private and accessible only to the list.
32			*/
33			class node
34			{
35			friend class intrusive_list;
36
37			private:
38			T* next_ = nullptr;
39			T* prev_ = nullptr;
40			};
41
42			private:
43			T* head_ = nullptr;
44			T* tail_ = nullptr;
45
46			public:
47		10517x	intrusive_list() = default;
48
49		1x	intrusive_list(intrusive_list&& other) noexcept
50		1x	: head_(other.head_)
51		1x	, tail_(other.tail_)
52			{
53		1x	other.head_ = nullptr;
54		1x	other.tail_ = nullptr;
55		1x	}
56
57			intrusive_list(intrusive_list const&) = delete;
58			intrusive_list& operator=(intrusive_list const&) = delete;
59			intrusive_list& operator=(intrusive_list&&) = delete;
60
61		21x	bool empty() const noexcept
62			{
63		21x	return head_ == nullptr;
64			}
65
66			/// Peek at the head element without removing it.
67		6x	T* front() const noexcept
68			{
69		6x	return head_;
70			}
71
72		24724x	void push_back(T* w) noexcept
73			{
74	1/2 ✓ Branch 2 → 3 taken 12120 times. ✗ Branch 2 → 4 not taken.	24724x	auto* n = static_cast<node*>(w);
75		24724x	n->next_ = nullptr;
76		24724x	n->prev_ = tail_;
77	4/4 ✓ Branch 2 → 3 taken 4391 times. ✓ Branch 2 → 4 taken 8213 times. ✓ Branch 5 → 6 taken 4533 times. ✓ Branch 5 → 10 taken 7587 times.	24724x	if (tail_)
78	1/2 ✓ Branch 6 → 7 taken 4533 times. ✗ Branch 6 → 8 not taken.	8924x	static_cast<node*>(tail_)->next_ = w;
79			else
80		15800x	head_ = w;
81		24724x	tail_ = w;
82		24724x	}
83
84		3x	void splice_back(intrusive_list& other) noexcept
85			{
86	2/2 ✓ Branch 3 → 4 taken 1 time. ✓ Branch 3 → 5 taken 2 times.	3x	if (other.empty())
87		1x	return;
88	2/2 ✓ Branch 5 → 6 taken 1 time. ✓ Branch 5 → 7 taken 1 time.	2x	if (tail_)
89			{
90		1x	static_cast<node*>(tail_)->next_ = other.head_;
91		1x	static_cast<node*>(other.head_)->prev_ = tail_;
92		1x	tail_ = other.tail_;
93			}
94			else
95			{
96		1x	head_ = other.head_;
97		1x	tail_ = other.tail_;
98			}
99		2x	other.head_ = nullptr;
100		2x	other.tail_ = nullptr;
101			}
102
103		12309x	T* pop_front() noexcept
104			{
105	2/2 ✓ Branch 2 → 3 taken 11345 times. ✓ Branch 2 → 4 taken 964 times.	12309x	if (!head_)
106		11345x	return nullptr;
107		964x	T* w = head_;
108	1/2 ✓ Branch 4 → 5 taken 26 times. ✗ Branch 4 → 6 not taken.	964x	head_ = static_cast<node*>(head_)->next_;
109	4/4 ✓ Branch 4 → 5 taken 24 times. ✓ Branch 4 → 6 taken 914 times. ✓ Branch 7 → 8 taken 4 times. ✓ Branch 7 → 12 taken 22 times.	964x	if (head_)
110	1/2 ✓ Branch 8 → 9 taken 4 times. ✗ Branch 8 → 10 not taken.	28x	static_cast<node*>(head_)->prev_ = nullptr;
111			else
112		936x	tail_ = nullptr;
113			// Defensive: clear stale linkage so remove() on a
114			// popped node cannot corrupt the list.
115	1/2 ✓ Branch 13 → 14 taken 26 times. ✗ Branch 13 → 15 not taken.	964x	auto* n = static_cast<node*>(w);
116		964x	n->next_ = nullptr;
117		964x	n->prev_ = nullptr;
118		964x	return w;
119			}
120
121		23803x	void remove(T* w) noexcept
122			{
123	1/2 ✓ Branch 2 → 3 taken 12094 times. ✗ Branch 2 → 4 not taken.	23803x	auto* n = static_cast<node*>(w);
124			// Already detached — nothing to do.
125	11/15 ✓ Branch 2 → 3 taken 7643 times. ✓ Branch 2 → 7 taken 4066 times. ✓ Branch 3 → 4 taken 7343 times. ✓ Branch 3 → 7 taken 300 times. ✓ Branch 4 → 5 taken 46 times. ✓ Branch 4 → 7 taken 7297 times. ✓ Branch 5 → 6 taken 7938 times. ✗ Branch 5 → 7 not taken. ✓ Branch 5 → 10 taken 4202 times. ✓ Branch 6 → 7 taken 7565 times. ✓ Branch 6 → 10 taken 327 times. ✗ Branch 7 → 8 not taken. ✓ Branch 7 → 10 taken 7565 times. ✗ Branch 8 → 9 not taken. ✗ Branch 8 → 10 not taken.	23803x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
126		46x	return;
127	4/4 ✓ Branch 7 → 8 taken 700 times. ✓ Branch 7 → 9 taken 10963 times. ✓ Branch 10 → 11 taken 724 times. ✓ Branch 10 → 15 taken 11370 times.	23757x	if (n->prev_)
128	1/2 ✓ Branch 11 → 12 taken 724 times. ✗ Branch 11 → 13 not taken.	1424x	static_cast<node*>(n->prev_)->next_ = n->next_;
129			else
130		22333x	head_ = n->next_;
131	4/4 ✓ Branch 10 → 11 taken 4066 times. ✓ Branch 10 → 12 taken 7597 times. ✓ Branch 16 → 17 taken 4202 times. ✓ Branch 16 → 21 taken 7892 times.	23757x	if (n->next_)
132	1/2 ✓ Branch 17 → 18 taken 4202 times. ✗ Branch 17 → 19 not taken.	8268x	static_cast<node*>(n->next_)->prev_ = n->prev_;
133			else
134		15489x	tail_ = n->prev_;
135		23757x	n->next_ = nullptr;
136		23757x	n->prev_ = nullptr;
137			}
138
139			/// Invoke @p f for each element in the list.
140			template<class F>
141		13x	void for_each(F f)
142			{
143	5/6 ✓ Branch 4 → 5 taken 4 times. ✗ Branch 4 → 6 not taken. ✓ Branch 5 → 3 taken 3 times. ✓ Branch 5 → 6 taken 1 time. ✓ Branch 8 → 3 taken 4 times. ✓ Branch 8 → 9 taken 12 times.	20x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
144		7x	f(p);
145		13x	}
146			};
147
148			/** An intrusive singly linked FIFO queue.
149
150			This container provides O(1) push and pop operations for
151			elements that derive from @ref node. Elements are not
152			copied or moved; they are linked directly into the queue.
153
154			Unlike @ref intrusive_list, this uses only a single `next_`
155			pointer per node, saving memory at the cost of not supporting
156			O(1) removal of arbitrary elements.
157
158			@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
159			*/
160			template<class T>
161			class intrusive_queue
162			{
163			public:
164			/** Base class for queue elements.
165
166			Derive from this class to make a type usable with
167			@ref intrusive_queue. The `next_` pointer is private
168			and accessible only to the queue.
169			*/
170			class node
171			{
172			friend class intrusive_queue;
173
174			private:
175			T* next_ = nullptr;
176			};
177
178			private:
179			T* head_ = nullptr;
180			T* tail_ = nullptr;
181
182			public:
183		9013x	intrusive_queue() = default;
184
185		1x	intrusive_queue(intrusive_queue&& other) noexcept
186		1x	: head_(other.head_)
187		1x	, tail_(other.tail_)
188			{
189		1x	other.head_ = nullptr;
190		1x	other.tail_ = nullptr;
191		1x	}
192
193			intrusive_queue(intrusive_queue const&) = delete;
194			intrusive_queue& operator=(intrusive_queue const&) = delete;
195			intrusive_queue& operator=(intrusive_queue&&) = delete;
196
197		5425x	bool empty() const noexcept
198			{
199		5425x	return head_ == nullptr;
200			}
201
202		46x	void push(T* w) noexcept
203			{
204		46x	w->next_ = nullptr;
205	2/2 ✓ Branch 2 → 3 taken 15 times. ✓ Branch 2 → 4 taken 31 times.	46x	if (tail_)
206		15x	tail_->next_ = w;
207			else
208		31x	head_ = w;
209		46x	tail_ = w;
210		46x	}
211
212		5385x	void splice(intrusive_queue& other) noexcept
213			{
214	2/2 ✓ Branch 3 → 4 taken 5378 times. ✓ Branch 3 → 5 taken 7 times.	5385x	if (other.empty())
215		5378x	return;
216	2/2 ✓ Branch 5 → 6 taken 1 time. ✓ Branch 5 → 7 taken 6 times.	7x	if (tail_)
217		1x	tail_->next_ = other.head_;
218			else
219		6x	head_ = other.head_;
220		7x	tail_ = other.tail_;
221		7x	other.head_ = nullptr;
222		7x	other.tail_ = nullptr;
223			}
224
225		9883x	T* pop() noexcept
226			{
227	2/2 ✓ Branch 2 → 3 taken 9837 times. ✓ Branch 2 → 4 taken 46 times.	9883x	if (!head_)
228		9837x	return nullptr;
229		46x	T* w = head_;
230		46x	head_ = head_->next_;
231	2/2 ✓ Branch 4 → 5 taken 30 times. ✓ Branch 4 → 6 taken 16 times.	46x	if (!head_)
232		30x	tail_ = nullptr;
233			// Defensive: clear stale linkage on popped node.
234		46x	w->next_ = nullptr;
235		46x	return w;
236			}
237			};
238
239			} // namespace boost::corosio::detail
240
241			#endif
242