include/boost/corosio/detail/intrusive.hpp

98.5% Lines (64/65) 100.0% Functions (34/35) 63.7% Branches (51/80)

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		293704	T* head_ = nullptr;
44		293704	T* tail_ = nullptr;
45
46			public:
47		881112	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		6	bool empty() const noexcept
62			{
63		6	return head_ == nullptr;
64			}
65
66		37205	void push_back(T* w) noexcept
67			{
68		37205	w->next_ = nullptr;
69		37205	w->prev_ = tail_;
70	12/14 ✓ Branch 0 taken 15491 times. ✓ Branch 1 taken 15445 times. ✓ Branch 2 taken 1 time. ✓ Branch 3 taken 34 times. ✓ Branch 4 taken 10 times. ✓ Branch 5 taken 84 times. ✓ Branch 6 taken 5064 times. ✓ Branch 7 taken 58 times. ✓ Branch 8 taken 1 time. ✓ Branch 9 taken 51 times. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✓ Branch 12 taken 4 times. ✓ Branch 13 taken 962 times.	37205	if (tail_)
71		20571	tail_->next_ = w;
72			else
73		16634	head_ = w;
74		37205	tail_ = w;
75		37205	}
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		315272	T* pop_front() noexcept
97			{
98	8/14 ✓ Branch 0 taken 14522 times. ✓ Branch 1 taken 298910 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 460 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 460 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 161 times. ✗ Branch 8 not taken. ✓ Branch 9 taken 161 times. ✗ Branch 10 not taken. ✓ Branch 11 taken 299 times. ✗ Branch 12 not taken. ✓ Branch 13 taken 299 times.	315272	if (!head_)
99		300750	return nullptr;
100		14522	T* w = head_;
101		14522	head_ = head_->next_;
102	2/14 ✓ Branch 0 taken 45 times. ✓ Branch 1 taken 14477 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.	14522	if (head_)
103		45	head_->prev_ = nullptr;
104			else
105		14477	tail_ = nullptr;
106			// Defensive: clear stale linkage so remove() on a
107			// popped node cannot corrupt the list.
108		14522	w->next_ = nullptr;
109		14522	w->prev_ = nullptr;
110		14522	return w;
111		315272	}
112
113		22683	void remove(T* w) noexcept
114			{
115	12/14 ✓ Branch 0 taken 4593 times. ✓ Branch 1 taken 11821 times. ✓ Branch 2 taken 1 time. ✓ Branch 3 taken 34 times. ✓ Branch 4 taken 10 times. ✓ Branch 5 taken 84 times. ✓ Branch 6 taken 1677 times. ✓ Branch 7 taken 3445 times. ✓ Branch 8 taken 1 time. ✓ Branch 9 taken 51 times. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✓ Branch 12 taken 4 times. ✓ Branch 13 taken 962 times.	22683	if (w->prev_)
116		6286	w->prev_->next_ = w->next_;
117			else
118		16397	head_ = w->next_;
119	8/14 ✓ Branch 0 taken 10916 times. ✓ Branch 1 taken 5498 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 35 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 94 times. ✓ Branch 6 taken 3397 times. ✓ Branch 7 taken 1725 times. ✗ Branch 8 not taken. ✓ Branch 9 taken 52 times. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✓ Branch 13 taken 966 times.	22683	if (w->next_)
120		14313	w->next_->prev_ = w->prev_;
121			else
122		8370	tail_ = w->prev_;
123		22683	}
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		216397	T* head_ = nullptr;
158		216397	T* tail_ = nullptr;
159
160			public:
161		649191	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		1372544	bool empty() const noexcept
176			{
177		1372544	return head_ == nullptr;
178			}
179
180		1372476	void push(T* w) noexcept
181			{
182		1372476	w->next_ = nullptr;
183	2/2 ✓ Branch 0 taken 1024082 times. ✓ Branch 1 taken 348394 times.	1372476	if (tail_)
184		1024082	tail_->next_ = w;
185			else
186		348394	head_ = w;
187		1372476	tail_ = w;
188		1372476	}
189
190		217802	void splice(intrusive_queue& other) noexcept
191			{
192	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 217802 times.	217802	if (other.empty())
193		✗	return;
194	2/2 ✓ Branch 0 taken 168520 times. ✓ Branch 1 taken 49282 times.	217802	if (tail_)
195		168520	tail_->next_ = other.head_;
196			else
197		49282	head_ = other.head_;
198		217802	tail_ = other.tail_;
199		217802	other.head_ = nullptr;
200		217802	other.tail_ = nullptr;
201		217802	}
202
203		1434880	T* pop() noexcept
204			{
205	2/2 ✓ Branch 0 taken 1372476 times. ✓ Branch 1 taken 62404 times.	1434880	if (!head_)
206		62404	return nullptr;
207		1372476	T* w = head_;
208		1372476	head_ = head_->next_;
209	2/2 ✓ Branch 0 taken 1192602 times. ✓ Branch 1 taken 179874 times.	1372476	if (!head_)
210		179874	tail_ = nullptr;
211			// Defensive: clear stale linkage on popped node.
212		1372476	w->next_ = nullptr;
213		1372476	return w;
214		1434880	}
215			};
216
217			} // namespace boost::corosio::detail
218
219			#endif
220