include/boost/corosio/detail/intrusive.hpp

89.7% Lines (52/58) 97.8% List of functions (45/46) 85.0% Branches (17/20)

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

f(x) Functions (46)

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		3112x	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		13946x	void push_back(T* w) noexcept
67			{
68		13946x	w->next_ = nullptr;
69		13946x	w->prev_ = tail_;
70	2/2 ✓ Branch 2 → 3 taken 5243 times. ✓ Branch 2 → 4 taken 8703 times.	13946x	if (tail_)
71		5243x	tail_->next_ = w;
72			else
73		8703x	head_ = w;
74		13946x	tail_ = w;
75		13946x	}
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		10666x	T* pop_front() noexcept
97			{
98	2/2 ✓ Branch 2 → 3 taken 6805 times. ✓ Branch 2 → 4 taken 3861 times.	10666x	if (!head_)
99		6805x	return nullptr;
100		3861x	T* w = head_;
101		3861x	head_ = head_->next_;
102	2/2 ✓ Branch 4 → 5 taken 23 times. ✓ Branch 4 → 6 taken 3838 times.	3861x	if (head_)
103		23x	head_->prev_ = nullptr;
104			else
105		3838x	tail_ = nullptr;
106			// Defensive: clear stale linkage so remove() on a
107			// popped node cannot corrupt the list.
108		3861x	w->next_ = nullptr;
109		3861x	w->prev_ = nullptr;
110		3861x	return w;
111			}
112
113		10085x	void remove(T* w) noexcept
114			{
115	2/2 ✓ Branch 2 → 3 taken 189 times. ✓ Branch 2 → 4 taken 9896 times.	10085x	if (w->prev_)
116		189x	w->prev_->next_ = w->next_;
117			else
118		9896x	head_ = w->next_;
119	2/2 ✓ Branch 5 → 6 taken 5149 times. ✓ Branch 5 → 7 taken 4936 times.	10085x	if (w->next_)
120		5149x	w->next_->prev_ = w->prev_;
121			else
122		4936x	tail_ = w->prev_;
123		10085x	}
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			T* head_ = nullptr;
158			T* tail_ = nullptr;
159
160			public:
161		740x	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		1586x	bool empty() const noexcept
176			{
177		1586x	return head_ == nullptr;
178			}
179
180		25x	void push(T* w) noexcept
181			{
182		25x	w->next_ = nullptr;
183	2/2 ✓ Branch 2 → 3 taken 11 times. ✓ Branch 2 → 4 taken 14 times.	25x	if (tail_)
184		11x	tail_->next_ = w;
185			else
186		14x	head_ = w;
187		25x	tail_ = w;
188		25x	}
189
190		1176x	void splice(intrusive_queue& other) noexcept
191			{
192	1/2 ✓ Branch 3 → 4 taken 1176 times. ✗ Branch 3 → 5 not taken.	1176x	if (other.empty())
193		1176x	return;
194		✗	if (tail_)
195		✗	tail_->next_ = other.head_;
196			else
197		✗	head_ = other.head_;
198		✗	tail_ = other.tail_;
199		✗	other.head_ = nullptr;
200		✗	other.tail_ = nullptr;
201			}
202
203		1933x	T* pop() noexcept
204			{
205	2/2 ✓ Branch 2 → 3 taken 1908 times. ✓ Branch 2 → 4 taken 25 times.	1933x	if (!head_)
206		1908x	return nullptr;
207		25x	T* w = head_;
208		25x	head_ = head_->next_;
209	2/2 ✓ Branch 4 → 5 taken 14 times. ✓ Branch 4 → 6 taken 11 times.	25x	if (!head_)
210		14x	tail_ = nullptr;
211			// Defensive: clear stale linkage on popped node.
212		25x	w->next_ = nullptr;
213		25x	return w;
214			}
215			};
216
217			} // namespace boost::corosio::detail
218
219			#endif
220