include/boost/corosio/detail/intrusive.hpp

98.5% Lines (64/65) 100.0% List of functions (46/48) 60.4% Branches (64/106)

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

f(x) Functions (48)

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		761558x	T* head_ = nullptr;
44		761558x	T* tail_ = nullptr;
45
46			public:
47		2284674x	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		38x	bool empty() const noexcept
62			{
63		38x	return head_ == nullptr;
64			}
65
66		38790x	void push_back(T* w) noexcept
67			{
68		38790x	w->next_ = nullptr;
69		38790x	w->prev_ = tail_;
70	14/18 ✓ Branch 0 taken 5365 times. ✓ Branch 1 taken 15004 times. ✓ Branch 2 taken 15783 times. ✓ Branch 3 taken 1208 times. ✓ Branch 4 taken 10 times. ✓ Branch 5 taken 84 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. ✓ Branch 8 taken 1 time. ✓ Branch 9 taken 66 times. ✓ Branch 10 taken 15 times. ✓ Branch 11 taken 33 times. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✓ Branch 14 taken 2 times. ✓ Branch 15 taken 1171 times. ✓ Branch 16 taken 15 times. ✓ Branch 17 taken 33 times.	38790x	if (tail_)
71		21191x	tail_->next_ = w;
72			else
73		17599x	head_ = w;
74		38790x	tail_ = w;
75		38790x	}
76
77			void splice_back(intrusive_list& other) noexcept
78			{
79			if (other.empty())
80			return;
81			if (tail_)
82			{
83			tail_->next_ = other.head_;
84			other.head_->prev_ = tail_;
85			tail_ = other.tail_;
86			}
87			else
88			{
89			head_ = other.head_;
90			tail_ = other.tail_;
91			}
92			other.head_ = nullptr;
93			other.tail_ = nullptr;
94			}
95
96		783667x	T* pop_front() noexcept
97			{
98	10/18 ✓ Branch 0 taken 14944 times. ✓ Branch 1 taken 765693 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 606 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 606 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 231 times. ✗ Branch 8 not taken. ✓ Branch 9 taken 231 times. ✗ Branch 10 not taken. ✓ Branch 11 taken 231 times. ✗ Branch 12 not taken. ✓ Branch 13 taken 375 times. ✗ Branch 14 not taken. ✓ Branch 15 taken 375 times. ✗ Branch 16 not taken. ✓ Branch 17 taken 375 times.	783667x	if (!head_)
99		768723x	return nullptr;
100		14944x	T* w = head_;
101		14944x	head_ = head_->next_;
102	2/18 ✓ Branch 0 taken 46 times. ✓ Branch 1 taken 14898 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✗ Branch 6 not taken. ✗ Branch 7 not taken. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken.	14944x	if (head_)
103		46x	head_->prev_ = nullptr;
104			else
105		14898x	tail_ = nullptr;
106			// Defensive: clear stale linkage so remove() on a
107			// popped node cannot corrupt the list.
108		14944x	w->next_ = nullptr;
109		14944x	w->prev_ = nullptr;
110		14944x	return w;
111		783667x	}
112
113		23846x	void remove(T* w) noexcept
114			{
115	17/18 ✗ Branch 0 not taken. ✓ Branch 1 taken 36 times. ✓ Branch 2 taken 1 time. ✓ Branch 3 taken 34 times. ✓ Branch 4 taken 10 times. ✓ Branch 5 taken 84 times. ✓ Branch 6 taken 1756 times. ✓ Branch 7 taken 3633 times. ✓ Branch 8 taken 1 time. ✓ Branch 9 taken 66 times. ✓ Branch 10 taken 15 times. ✓ Branch 11 taken 33 times. ✓ Branch 12 taken 4570 times. ✓ Branch 13 taken 12386 times. ✓ Branch 14 taken 2 times. ✓ Branch 15 taken 1171 times. ✓ Branch 16 taken 15 times. ✓ Branch 17 taken 33 times.	23846x	if (w->prev_)
116		6370x	w->prev_->next_ = w->next_;
117			else
118		17476x	head_ = w->next_;
119	12/18 ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 34 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 35 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 94 times. ✓ Branch 6 taken 3571 times. ✓ Branch 7 taken 1818 times. ✗ Branch 8 not taken. ✓ Branch 9 taken 67 times. ✗ Branch 10 not taken. ✓ Branch 11 taken 48 times. ✓ Branch 12 taken 11275 times. ✓ Branch 13 taken 5681 times. ✗ Branch 14 not taken. ✓ Branch 15 taken 1173 times. ✗ Branch 16 not taken. ✓ Branch 17 taken 48 times.	23846x	if (w->next_)
120		14848x	w->next_->prev_ = w->prev_;
121			else
122		8998x	tail_ = w->prev_;
123		23846x	}
124			};
125
126			/** An intrusive singly linked FIFO queue.
127
128			This container provides O(1) push and pop operations for
129			elements that derive from @ref node. Elements are not
130			copied or moved; they are linked directly into the queue.
131
132			Unlike @ref intrusive_list, this uses only a single `next_`
133			pointer per node, saving memory at the cost of not supporting
134			O(1) removal of arbitrary elements.
135
136			@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
137			*/
138			template<class T>
139			class intrusive_queue
140			{
141			public:
142			/** Base class for queue elements.
143
144			Derive from this class to make a type usable with
145			@ref intrusive_queue. The `next_` pointer is private
146			and accessible only to the queue.
147			*/
148			class node
149			{
150			friend class intrusive_queue;
151
152			private:
153			T* next_;
154			};
155
156			private:
157		1618744x	T* head_ = nullptr;
158		1618744x	T* tail_ = nullptr;
159
160			public:
161		4856232x	intrusive_queue() = default;
162
163			intrusive_queue(intrusive_queue&& other) noexcept
164			: head_(other.head_)
165			, tail_(other.tail_)
166			{
167			other.head_ = nullptr;
168			other.tail_ = nullptr;
169			}
170
171			intrusive_queue(intrusive_queue const&) = delete;
172			intrusive_queue& operator=(intrusive_queue const&) = delete;
173			intrusive_queue& operator=(intrusive_queue&&) = delete;
174
175		6553053x	bool empty() const noexcept
176			{
177		6553053x	return head_ == nullptr;
178			}
179
180		2088753x	void push(T* w) noexcept
181			{
182		2088753x	w->next_ = nullptr;
183	2/4 ✓ Branch 0 taken 895005 times. ✓ Branch 1 taken 1193748 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken.	2088753x	if (tail_)
184		895005x	tail_->next_ = w;
185			else
186		1193748x	head_ = w;
187		2088753x	tail_ = w;
188		2088753x	}
189
190		1057229x	void splice(intrusive_queue& other) noexcept
191			{
192	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 1057229 times.	1057229x	if (other.empty())
193		✗	return;
194	2/2 ✓ Branch 0 taken 378724 times. ✓ Branch 1 taken 678505 times.	1057229x	if (tail_)
195		378724x	tail_->next_ = other.head_;
196			else
197		678505x	head_ = other.head_;
198		1057229x	tail_ = other.tail_;
199		1057229x	other.head_ = nullptr;
200		1057229x	other.tail_ = nullptr;
201		1057229x	}
202
203		2819767x	T* pop() noexcept
204			{
205	2/4 ✓ Branch 0 taken 2088753 times. ✓ Branch 1 taken 731014 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken.	2819767x	if (!head_)
206		731014x	return nullptr;
207		2088753x	T* w = head_;
208		2088753x	head_ = head_->next_;
209	2/4 ✓ Branch 0 taken 1273729 times. ✓ Branch 1 taken 815024 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken.	2088753x	if (!head_)
210		815024x	tail_ = nullptr;
211			// Defensive: clear stale linkage on popped node.
212		2088753x	w->next_ = nullptr;
213		2088753x	return w;
214		2819767x	}
215			};
216
217			} // namespace boost::corosio::detail
218
219			#endif
220