include/boost/corosio/detail/intrusive.hpp

88.2% Lines (60/68) 98.5% List of functions (65/66) 61.9% Branches (39/63)

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

intrusive.hpp

f(x) Functions (66)

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_;
39			T* prev_;
40			};
41
42			private:
43			T* head_ = nullptr;
44			T* tail_ = nullptr;
45
46			public:
47		5356x	intrusive_list() = default;
48
49			intrusive_list(intrusive_list&& other) noexcept
50			: head_(other.head_)
51			, tail_(other.tail_)
52			{
53			other.head_ = nullptr;
54			other.tail_ = nullptr;
55			}
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		19x	bool empty() const noexcept
62			{
63		19x	return head_ == nullptr;
64			}
65
66		13290x	void push_back(T* w) noexcept
67			{
68	1/2 ✓ Branch 2 → 3 taken 5049 times. ✗ Branch 2 → 4 not taken.	13290x	auto* n = static_cast<node*>(w);
69		13290x	n->next_ = nullptr;
70		13290x	n->prev_ = tail_;
71	4/4 ✓ Branch 2 → 3 taken 2538 times. ✓ Branch 2 → 4 taken 5703 times. ✓ Branch 5 → 6 taken 2622 times. ✓ Branch 5 → 10 taken 2427 times.	13290x	if (tail_)
72	1/2 ✓ Branch 6 → 7 taken 2622 times. ✗ Branch 6 → 8 not taken.	5160x	static_cast<node*>(tail_)->next_ = w;
73			else
74		8130x	head_ = w;
75		13290x	tail_ = w;
76		13290x	}
77
78			void splice_back(intrusive_list& other) noexcept
79			{
80			if (other.empty())
81			return;
82			if (tail_)
83			{
84			static_cast<node*>(tail_)->next_ = other.head_;
85			static_cast<node*>(other.head_)->prev_ = tail_;
86			tail_ = other.tail_;
87			}
88			else
89			{
90			head_ = other.head_;
91			tail_ = other.tail_;
92			}
93			other.head_ = nullptr;
94			other.tail_ = nullptr;
95			}
96
97		11902x	T* pop_front() noexcept
98			{
99	2/2 ✓ Branch 2 → 3 taken 8535 times. ✓ Branch 2 → 4 taken 3367 times.	11902x	if (!head_)
100		8535x	return nullptr;
101		3367x	T* w = head_;
102	0/2 ✗ Branch 4 → 5 not taken. ✗ Branch 4 → 6 not taken.	3367x	head_ = static_cast<node*>(head_)->next_;
103	2/4 ✓ Branch 4 → 5 taken 24 times. ✓ Branch 4 → 6 taken 3343 times. ✗ Branch 7 → 8 not taken. ✗ Branch 7 → 12 not taken.	3367x	if (head_)
104	0/2 ✗ Branch 8 → 9 not taken. ✗ Branch 8 → 10 not taken.	24x	static_cast<node*>(head_)->prev_ = nullptr;
105			else
106		3343x	tail_ = nullptr;
107			// Defensive: clear stale linkage so remove() on a
108			// popped node cannot corrupt the list.
109	0/2 ✗ Branch 13 → 14 not taken. ✗ Branch 13 → 15 not taken.	3367x	auto* n = static_cast<node*>(w);
110		3367x	n->next_ = nullptr;
111		3367x	n->prev_ = nullptr;
112		3367x	return w;
113			}
114
115		9923x	void remove(T* w) noexcept
116			{
117	1/2 ✓ Branch 2 → 3 taken 5049 times. ✗ Branch 2 → 4 not taken.	9923x	auto* n = static_cast<node*>(w);
118			// Already detached — nothing to do.
119	10/15 ✓ Branch 2 → 3 taken 2399 times. ✓ Branch 2 → 7 taken 2475 times. ✓ Branch 3 → 4 taken 2360 times. ✓ Branch 3 → 7 taken 39 times. ✗ Branch 4 → 5 not taken. ✓ Branch 4 → 7 taken 2360 times. ✓ Branch 5 → 6 taken 2469 times. ✗ Branch 5 → 7 not taken. ✓ Branch 5 → 10 taken 2580 times. ✓ Branch 6 → 7 taken 2427 times. ✓ Branch 6 → 10 taken 42 times. ✗ Branch 7 → 8 not taken. ✓ Branch 7 → 10 taken 2427 times. ✗ Branch 8 → 9 not taken. ✗ Branch 8 → 10 not taken.	9923x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
120		✗	return;
121	4/4 ✓ Branch 7 → 8 taken 99 times. ✓ Branch 7 → 9 taken 4775 times. ✓ Branch 10 → 11 taken 102 times. ✓ Branch 10 → 15 taken 4947 times.	9923x	if (n->prev_)
122	1/2 ✓ Branch 11 → 12 taken 102 times. ✗ Branch 11 → 13 not taken.	201x	static_cast<node*>(n->prev_)->next_ = n->next_;
123			else
124		9722x	head_ = n->next_;
125	4/4 ✓ Branch 10 → 11 taken 2475 times. ✓ Branch 10 → 12 taken 2399 times. ✓ Branch 16 → 17 taken 2580 times. ✓ Branch 16 → 21 taken 2469 times.	9923x	if (n->next_)
126	1/2 ✓ Branch 17 → 18 taken 2580 times. ✗ Branch 17 → 19 not taken.	5055x	static_cast<node*>(n->next_)->prev_ = n->prev_;
127			else
128		4868x	tail_ = n->prev_;
129		9923x	n->next_ = nullptr;
130		9923x	n->prev_ = nullptr;
131			}
132
133			/// Invoke @p f for each element in the list.
134			template<class F>
135		1x	void for_each(F f)
136			{
137	1/4 ✗ Branch 4 → 5 not taken. ✗ Branch 4 → 6 not taken. ✗ Branch 8 → 3 not taken. ✓ Branch 8 → 9 taken 1 time.	1x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
138		✗	f(p);
139		1x	}
140			};
141
142			/** An intrusive singly linked FIFO queue.
143
144			This container provides O(1) push and pop operations for
145			elements that derive from @ref node. Elements are not
146			copied or moved; they are linked directly into the queue.
147
148			Unlike @ref intrusive_list, this uses only a single `next_`
149			pointer per node, saving memory at the cost of not supporting
150			O(1) removal of arbitrary elements.
151
152			@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
153			*/
154			template<class T>
155			class intrusive_queue
156			{
157			public:
158			/** Base class for queue elements.
159
160			Derive from this class to make a type usable with
161			@ref intrusive_queue. The `next_` pointer is private
162			and accessible only to the queue.
163			*/
164			class node
165			{
166			friend class intrusive_queue;
167
168			private:
169			T* next_;
170			};
171
172			private:
173			T* head_ = nullptr;
174			T* tail_ = nullptr;
175
176			public:
177		864x	intrusive_queue() = default;
178
179			intrusive_queue(intrusive_queue&& other) noexcept
180			: head_(other.head_)
181			, tail_(other.tail_)
182			{
183			other.head_ = nullptr;
184			other.tail_ = nullptr;
185			}
186
187			intrusive_queue(intrusive_queue const&) = delete;
188			intrusive_queue& operator=(intrusive_queue const&) = delete;
189			intrusive_queue& operator=(intrusive_queue&&) = delete;
190
191		1459x	bool empty() const noexcept
192			{
193		1459x	return head_ == nullptr;
194			}
195
196		25x	void push(T* w) noexcept
197			{
198		25x	w->next_ = nullptr;
199	2/2 ✓ Branch 2 → 3 taken 12 times. ✓ Branch 2 → 4 taken 13 times.	25x	if (tail_)
200		12x	tail_->next_ = w;
201			else
202		13x	head_ = w;
203		25x	tail_ = w;
204		25x	}
205
206		989x	void splice(intrusive_queue& other) noexcept
207			{
208	1/2 ✓ Branch 3 → 4 taken 989 times. ✗ Branch 3 → 5 not taken.	989x	if (other.empty())
209		989x	return;
210		✗	if (tail_)
211		✗	tail_->next_ = other.head_;
212			else
213		✗	head_ = other.head_;
214		✗	tail_ = other.tail_;
215		✗	other.head_ = nullptr;
216		✗	other.tail_ = nullptr;
217			}
218
219		1870x	T* pop() noexcept
220			{
221	2/2 ✓ Branch 2 → 3 taken 1845 times. ✓ Branch 2 → 4 taken 25 times.	1870x	if (!head_)
222		1845x	return nullptr;
223		25x	T* w = head_;
224		25x	head_ = head_->next_;
225	2/2 ✓ Branch 4 → 5 taken 13 times. ✓ Branch 4 → 6 taken 12 times.	25x	if (!head_)
226		13x	tail_ = nullptr;
227			// Defensive: clear stale linkage on popped node.
228		25x	w->next_ = nullptr;
229		25x	return w;
230			}
231			};
232
233			} // namespace boost::corosio::detail
234
235			#endif
236