include/boost/capy/detail/intrusive.hpp

99.3% Lines (144/145) 100.0% List of functions (22/22) 98.0% Branches (49/50)

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

f(x) Functions (22)

Function Calls Lines Branches Blocks

Line	Branch	Hits	Source Code
1			//
2			// Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
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/capy
8			//
9
10			#ifndef BOOST_CAPY_DETAIL_INTRUSIVE_HPP
11			#define BOOST_CAPY_DETAIL_INTRUSIVE_HPP
12
13			namespace boost {
14			namespace capy {
15			namespace detail {
16
17			//------------------------------------------------
18
19			/** An intrusive doubly linked list.
20
21			This container provides O(1) push and pop operations for
22			elements that derive from @ref node. Elements are not
23			copied or moved; they are linked directly into the list.
24
25			@tparam T The element type. Must derive from `intrusive_list<T>::node`.
26			*/
27			template<class T>
28			class intrusive_list
29			{
30			public:
31			/** Base class for list elements.
32
33			Derive from this class to make a type usable with
34			@ref intrusive_list. The `next_` and `prev_` pointers
35			are private and accessible only to the list.
36			*/
37			class node
38			{
39			friend class intrusive_list;
40
41			private:
42			T* next_;
43			T* prev_;
44			};
45
46			private:
47			T* head_ = nullptr;
48			T* tail_ = nullptr;
49
50			public:
51		20x	intrusive_list() = default;
52
53		2x	intrusive_list(intrusive_list&& other) noexcept
54		2x	: head_(other.head_)
55		2x	, tail_(other.tail_)
56			{
57		2x	other.head_ = nullptr;
58		2x	other.tail_ = nullptr;
59		2x	}
60
61			intrusive_list(intrusive_list const&) = delete;
62			intrusive_list& operator=(intrusive_list const&) = delete;
63			intrusive_list& operator=(intrusive_list&&) = delete;
64
65			bool
66		36x	empty() const noexcept
67			{
68		36x	return head_ == nullptr;
69			}
70
71			void
72		84x	push_back(T* w) noexcept
73			{
74		84x	w->next_ = nullptr;
75		84x	w->prev_ = tail_;
76	6/6 boost::capy::detail::intrusive_list<boost::capy::async_event::wait_awaiter>::push_back(boost::capy::async_event::wait_awaiter): ✓ Branch 0 taken 7 times. ✓ Branch 1 taken 30 times. boost::capy::detail::intrusive_list<boost::capy::async_mutex::lock_awaiter>::push_back(boost::capy::async_mutex::lock_awaiter): ✓ Branch 0 taken 7 times. ✓ Branch 1 taken 10 times. boost::capy::detail::intrusive_list<boost::capy::detail::list_item>::push_back(boost::capy::detail::list_item*): ✓ Branch 0 taken 14 times. ✓ Branch 1 taken 16 times.	84x	if(tail_)
77		28x	tail_->next_ = w;
78			else
79		56x	head_ = w;
80		84x	tail_ = w;
81		84x	}
82
83			void
84		4x	splice_back(intrusive_list& other) noexcept
85			{
86	2/2 ✓ Branch 1 taken 2 times. ✓ Branch 2 taken 2 times.	4x	if(other.empty())
87		2x	return;
88	2/2 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 1 time.	2x	if(tail_)
89			{
90		1x	tail_->next_ = other.head_;
91		1x	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			T*
104		92x	pop_front() noexcept
105			{
106	6/6 boost::capy::detail::intrusive_list<boost::capy::async_event::wait_awaiter>::pop_front(): ✓ Branch 0 taken 23 times. ✓ Branch 1 taken 16 times. boost::capy::detail::intrusive_list<boost::capy::async_mutex::lock_awaiter>::pop_front(): ✓ Branch 0 taken 16 times. ✓ Branch 1 taken 8 times. boost::capy::detail::intrusive_list<boost::capy::detail::list_item>::pop_front(): ✓ Branch 0 taken 4 times. ✓ Branch 1 taken 25 times.	92x	if(!head_)
107		43x	return nullptr;
108		49x	T* w = head_;
109		49x	head_ = head_->next_;
110	6/6 boost::capy::detail::intrusive_list<boost::capy::async_event::wait_awaiter>::pop_front(): ✓ Branch 0 taken 6 times. ✓ Branch 1 taken 10 times. boost::capy::detail::intrusive_list<boost::capy::async_mutex::lock_awaiter>::pop_front(): ✓ Branch 0 taken 3 times. ✓ Branch 1 taken 5 times. boost::capy::detail::intrusive_list<boost::capy::detail::list_item>::pop_front(): ✓ Branch 0 taken 12 times. ✓ Branch 1 taken 13 times.	49x	if(head_)
111		21x	head_->prev_ = nullptr;
112			else
113		28x	tail_ = nullptr;
114		49x	return w;
115			}
116
117			void
118		35x	remove(T* w) noexcept
119			{
120	5/6 boost::capy::detail::intrusive_list<boost::capy::async_event::wait_awaiter>::remove(boost::capy::async_event::wait_awaiter): ✗ Branch 0 not taken. ✓ Branch 1 taken 21 times. boost::capy::detail::intrusive_list<boost::capy::async_mutex::lock_awaiter>::remove(boost::capy::async_mutex::lock_awaiter): ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 8 times. boost::capy::detail::intrusive_list<boost::capy::detail::list_item>::remove(boost::capy::detail::list_item*): ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 3 times.	35x	if(w->prev_)
121		3x	w->prev_->next_ = w->next_;
122			else
123		32x	head_ = w->next_;
124	6/6 boost::capy::detail::intrusive_list<boost::capy::async_event::wait_awaiter>::remove(boost::capy::async_event::wait_awaiter): ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 20 times. boost::capy::detail::intrusive_list<boost::capy::async_mutex::lock_awaiter>::remove(boost::capy::async_mutex::lock_awaiter): ✓ Branch 0 taken 4 times. ✓ Branch 1 taken 5 times. boost::capy::detail::intrusive_list<boost::capy::detail::list_item>::remove(boost::capy::detail::list_item*): ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 3 times.	35x	if(w->next_)
125		7x	w->next_->prev_ = w->prev_;
126			else
127		28x	tail_ = w->prev_;
128		35x	}
129			};
130
131			//------------------------------------------------
132
133			/** An intrusive singly linked FIFO queue.
134
135			This container provides O(1) push and pop operations for
136			elements that derive from @ref node. Elements are not
137			copied or moved; they are linked directly into the queue.
138
139			Unlike @ref intrusive_list, this uses only a single `next_`
140			pointer per node, saving memory at the cost of not supporting
141			O(1) removal of arbitrary elements.
142
143			@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
144			*/
145			template<class T>
146			class intrusive_queue
147			{
148			public:
149			/** Base class for queue elements.
150
151			Derive from this class to make a type usable with
152			@ref intrusive_queue. The `next_` pointer is private
153			and accessible only to the queue.
154			*/
155			class node
156			{
157			friend class intrusive_queue;
158
159			private:
160			T* next_;
161			};
162
163			private:
164			T* head_ = nullptr;
165			T* tail_ = nullptr;
166
167			public:
168		149x	intrusive_queue() = default;
169
170		2x	intrusive_queue(intrusive_queue&& other) noexcept
171		2x	: head_(other.head_)
172		2x	, tail_(other.tail_)
173			{
174		2x	other.head_ = nullptr;
175		2x	other.tail_ = nullptr;
176		2x	}
177
178			intrusive_queue(intrusive_queue const&) = delete;
179			intrusive_queue& operator=(intrusive_queue const&) = delete;
180			intrusive_queue& operator=(intrusive_queue&&) = delete;
181
182			bool
183		907x	empty() const noexcept
184			{
185		907x	return head_ == nullptr;
186			}
187
188			void
189		806x	push(T* w) noexcept
190			{
191		806x	w->next_ = nullptr;
192	4/4 boost::capy::detail::intrusive_queue<boost::capy::detail::queue_item>::push(boost::capy::detail::queue_item): ✓ Branch 0 taken 8 times. ✓ Branch 1 taken 10 times. boost::capy::detail::intrusive_queue<boost::capy::thread_pool::impl::work>::push(boost::capy::thread_pool::impl::work): ✓ Branch 0 taken 598 times. ✓ Branch 1 taken 190 times.	806x	if(tail_)
193		606x	tail_->next_ = w;
194			else
195		200x	head_ = w;
196		806x	tail_ = w;
197		806x	}
198
199			void
200		4x	splice(intrusive_queue& other) noexcept
201			{
202	2/2 ✓ Branch 1 taken 2 times. ✓ Branch 2 taken 2 times.	4x	if(other.empty())
203		2x	return;
204	2/2 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 1 time.	2x	if(tail_)
205		1x	tail_->next_ = other.head_;
206			else
207		1x	head_ = other.head_;
208		2x	tail_ = other.tail_;
209		2x	other.head_ = nullptr;
210		2x	other.tail_ = nullptr;
211			}
212
213			T*
214		958x	pop() noexcept
215			{
216	4/4 boost::capy::detail::intrusive_queue<boost::capy::detail::queue_item>::pop(): ✓ Branch 0 taken 3 times. ✓ Branch 1 taken 18 times. boost::capy::detail::intrusive_queue<boost::capy::thread_pool::impl::work>::pop(): ✓ Branch 0 taken 149 times. ✓ Branch 1 taken 788 times.	958x	if(!head_)
217		152x	return nullptr;
218		806x	T* w = head_;
219		806x	head_ = head_->next_;
220	4/4 boost::capy::detail::intrusive_queue<boost::capy::detail::queue_item>::pop(): ✓ Branch 0 taken 9 times. ✓ Branch 1 taken 9 times. boost::capy::detail::intrusive_queue<boost::capy::thread_pool::impl::work>::pop(): ✓ Branch 0 taken 190 times. ✓ Branch 1 taken 598 times.	806x	if(!head_)
221		199x	tail_ = nullptr;
222		806x	return w;
223			}
224			};
225
226			} // detail
227			} // capy
228			} // boost
229
230			#endif
231