include/boost/corosio/detail/intrusive.hpp

100.0% Lines (103 / 103) 81.3% Branches (61 / 75) 90.2% Functions (148 / 164)

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

intrusive.hpp

f(x) Functions (164)

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_ = nullptr;
39			T* prev_ = nullptr;
40			};
41
42			private:
43			T* head_ = nullptr;
44			T* tail_ = nullptr;
45
46			public:
47		13020x	intrusive_list() = default;
48
49		1x	intrusive_list(intrusive_list&& other) noexcept
50		1x	: head_(other.head_)
51		1x	, tail_(other.tail_)
52			{
53		1x	other.head_ = nullptr;
54		1x	other.tail_ = nullptr;
55		1x	}
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		31x	bool empty() const noexcept
62			{
63		31x	return head_ == nullptr;
64			}
65
66			/// Peek at the head element without removing it.
67		6x	T* front() const noexcept
68			{
69		6x	return head_;
70			}
71
72		15010x	void push_front(T* w) noexcept
73			{
74	1/2 ✓ Branch 2 → 3 taken 15010 times. ✗ Branch 2 → 4 not taken.	15010x	auto* n = static_cast<node*>(w);
75		15010x	n->prev_ = nullptr;
76		15010x	n->next_ = head_;
77	2/2 ✓ Branch 5 → 6 taken 4960 times. ✓ Branch 5 → 10 taken 10050 times.	15010x	if (head_)
78	1/2 ✓ Branch 6 → 7 taken 4960 times. ✗ Branch 6 → 8 not taken.	4960x	static_cast<node*>(head_)->prev_ = w;
79			else
80		10050x	tail_ = w;
81		15010x	head_ = w;
82		15010x	}
83
84		23784x	void push_back(T* w) noexcept
85			{
86	1/2 ✓ Branch 2 → 3 taken 23346 times. ✗ Branch 2 → 4 not taken.	23784x	auto* n = static_cast<node*>(w);
87		23784x	n->next_ = nullptr;
88		23784x	n->prev_ = tail_;
89	4/4 ✓ Branch 2 → 3 taken 25 times. ✓ Branch 2 → 4 taken 413 times. ✓ Branch 5 → 6 taken 12076 times. ✓ Branch 5 → 10 taken 11270 times.	23784x	if (tail_)
90	1/2 ✓ Branch 6 → 7 taken 12076 times. ✗ Branch 6 → 8 not taken.	12101x	static_cast<node*>(tail_)->next_ = w;
91			else
92		11683x	head_ = w;
93		23784x	tail_ = w;
94		23784x	}
95
96		3x	void splice_back(intrusive_list& other) noexcept
97			{
98	2/2 ✓ Branch 3 → 4 taken 1 time. ✓ Branch 3 → 5 taken 2 times.	3x	if (other.empty())
99		1x	return;
100	2/2 ✓ Branch 5 → 6 taken 1 time. ✓ Branch 5 → 7 taken 1 time.	2x	if (tail_)
101			{
102		1x	static_cast<node*>(tail_)->next_ = other.head_;
103		1x	static_cast<node*>(other.head_)->prev_ = tail_;
104		1x	tail_ = other.tail_;
105			}
106			else
107			{
108		1x	head_ = other.head_;
109		1x	tail_ = other.tail_;
110			}
111		2x	other.head_ = nullptr;
112		2x	other.tail_ = nullptr;
113			}
114
115		41508x	T* pop_front() noexcept
116			{
117	2/2 ✓ Branch 2 → 3 taken 26062 times. ✓ Branch 2 → 4 taken 15446 times.	41508x	if (!head_)
118		26062x	return nullptr;
119		15446x	T* w = head_;
120	1/2 ✓ Branch 4 → 5 taken 15014 times. ✗ Branch 4 → 6 not taken.	15446x	head_ = static_cast<node*>(head_)->next_;
121	4/4 ✓ Branch 4 → 5 taken 22 times. ✓ Branch 4 → 6 taken 410 times. ✓ Branch 7 → 8 taken 4960 times. ✓ Branch 7 → 12 taken 10054 times.	15446x	if (head_)
122	1/2 ✓ Branch 8 → 9 taken 4960 times. ✗ Branch 8 → 10 not taken.	4982x	static_cast<node*>(head_)->prev_ = nullptr;
123			else
124		10464x	tail_ = nullptr;
125			// Defensive: clear stale linkage so remove() on a
126			// popped node cannot corrupt the list.
127	1/2 ✓ Branch 13 → 14 taken 15014 times. ✗ Branch 13 → 15 not taken.	15446x	auto* n = static_cast<node*>(w);
128		15446x	n->next_ = nullptr;
129		15446x	n->prev_ = nullptr;
130		15446x	return w;
131			}
132
133			/** Unlink @p w if it is a member of this list.
134
135			@pre @p w is either a genuine member of `*this` list, or is
136			fully detached (not linked in any `intrusive_list<T>`,
137			including a different instance over the same `T`). This is
138			not a membership test: `T::node` holds one shared `next_`/
139			`prev_` pair regardless of which list currently owns it, so a
140			node actually linked in a different list looks "not detached"
141			here and would be spliced out using this list's `head_`/
142			`tail_` for the boundary cases — corrupting both lists. A
143			caller that cannot rule that out needs its own bookkeeping
144			(e.g. a flag for which list currently owns the node) before
145			calling this.
146
147			@return True if @p w was linked in and has now been removed;
148			false if it was already detached (e.g. a reentrant call from
149			a self-referential keepalive dropping during the same
150			teardown that already popped it elsewhere). Callers that gate
151			a one-time action (recycling, deleting) on actually having
152			removed something rely on this to make that action idempotent.
153			*/
154		23347x	bool remove(T* w) noexcept
155			{
156	1/2 ✓ Branch 2 → 3 taken 23343 times. ✗ Branch 2 → 4 not taken.	23347x	auto* n = static_cast<node*>(w);
157			// Already detached — nothing to do.
158	12/15 ✓ Branch 2 → 3 taken 2 times. ✓ Branch 2 → 7 taken 2 times. ✓ Branch 3 → 4 taken 2 times. ✗ Branch 3 → 7 not taken. ✓ Branch 4 → 5 taken 1 time. ✓ Branch 4 → 7 taken 1 time. ✓ Branch 5 → 6 taken 15130 times. ✗ Branch 5 → 7 not taken. ✓ Branch 5 → 10 taken 8214 times. ✓ Branch 6 → 7 taken 11267 times. ✓ Branch 6 → 10 taken 3862 times. ✓ Branch 7 → 8 taken 1 time. ✓ Branch 7 → 10 taken 11266 times. ✓ Branch 8 → 9 taken 1 time. ✗ Branch 8 → 10 not taken.	23347x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
159		2x	return false;
160	4/4 ✓ Branch 7 → 8 taken 1 time. ✓ Branch 7 → 9 taken 2 times. ✓ Branch 10 → 11 taken 5333 times. ✓ Branch 10 → 15 taken 18009 times.	23345x	if (n->prev_)
161	1/2 ✓ Branch 11 → 12 taken 5333 times. ✗ Branch 11 → 13 not taken.	5334x	static_cast<node*>(n->prev_)->next_ = n->next_;
162			else
163		18011x	head_ = n->next_;
164	4/4 ✓ Branch 10 → 11 taken 2 times. ✓ Branch 10 → 12 taken 1 time. ✓ Branch 16 → 17 taken 8214 times. ✓ Branch 16 → 21 taken 15128 times.	23345x	if (n->next_)
165	1/2 ✓ Branch 17 → 18 taken 8214 times. ✗ Branch 17 → 19 not taken.	8216x	static_cast<node*>(n->next_)->prev_ = n->prev_;
166			else
167		15129x	tail_ = n->prev_;
168		23345x	n->next_ = nullptr;
169		23345x	n->prev_ = nullptr;
170		23345x	return true;
171			}
172
173			/// Invoke @p f for each element in the list.
174			template<class F>
175		12729x	void for_each(F f)
176			{
177	5/6 ✓ Branch 4 → 5 taken 9876 times. ✗ Branch 4 → 6 not taken. ✓ Branch 5 → 3 taken 3 times. ✓ Branch 5 → 6 taken 1 time. ✓ Branch 8 → 3 taken 9876 times. ✓ Branch 8 → 9 taken 12728 times.	22608x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
178		9879x	f(p);
179		12729x	}
180			};
181
182			/** An intrusive singly linked FIFO queue.
183
184			This container provides O(1) push and pop operations for
185			elements that derive from @ref node. Elements are not
186			copied or moved; they are linked directly into the queue.
187
188			Unlike @ref intrusive_list, this uses only a single `next_`
189			pointer per node, saving memory at the cost of not supporting
190			O(1) removal of arbitrary elements.
191
192			@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
193			*/
194			template<class T>
195			class intrusive_queue
196			{
197			public:
198			/** Base class for queue elements.
199
200			Derive from this class to make a type usable with
201			@ref intrusive_queue. The `next_` pointer is private
202			and accessible only to the queue.
203			*/
204			class node
205			{
206			friend class intrusive_queue;
207
208			private:
209			T* next_ = nullptr;
210			};
211
212			private:
213			T* head_ = nullptr;
214			T* tail_ = nullptr;
215
216			public:
217		10606x	intrusive_queue() = default;
218
219		1x	intrusive_queue(intrusive_queue&& other) noexcept
220		1x	: head_(other.head_)
221		1x	, tail_(other.tail_)
222			{
223		1x	other.head_ = nullptr;
224		1x	other.tail_ = nullptr;
225		1x	}
226
227			intrusive_queue(intrusive_queue const&) = delete;
228			intrusive_queue& operator=(intrusive_queue const&) = delete;
229			intrusive_queue& operator=(intrusive_queue&&) = delete;
230
231		25099x	bool empty() const noexcept
232			{
233		25099x	return head_ == nullptr;
234			}
235
236		479x	void push(T* w) noexcept
237			{
238		479x	w->next_ = nullptr;
239	2/2 ✓ Branch 2 → 3 taken 446 times. ✓ Branch 2 → 4 taken 33 times.	479x	if (tail_)
240		446x	tail_->next_ = w;
241			else
242		33x	head_ = w;
243		479x	tail_ = w;
244		479x	}
245
246		25051x	void splice(intrusive_queue& other) noexcept
247			{
248	2/2 ✓ Branch 3 → 4 taken 25039 times. ✓ Branch 3 → 5 taken 12 times.	25051x	if (other.empty())
249		25039x	return;
250	2/2 ✓ Branch 5 → 6 taken 1 time. ✓ Branch 5 → 7 taken 11 times.	12x	if (tail_)
251		1x	tail_->next_ = other.head_;
252			else
253		11x	head_ = other.head_;
254		12x	tail_ = other.tail_;
255		12x	other.head_ = nullptr;
256		12x	other.tail_ = nullptr;
257			}
258
259		25526x	T* pop() noexcept
260			{
261	2/2 ✓ Branch 2 → 3 taken 25047 times. ✓ Branch 2 → 4 taken 479 times.	25526x	if (!head_)
262		25047x	return nullptr;
263		479x	T* w = head_;
264		479x	head_ = head_->next_;
265	2/2 ✓ Branch 4 → 5 taken 32 times. ✓ Branch 4 → 6 taken 447 times.	479x	if (!head_)
266		32x	tail_ = nullptr;
267			// Defensive: clear stale linkage on popped node.
268		479x	w->next_ = nullptr;
269		479x	return w;
270			}
271			};
272
273			} // namespace boost::corosio::detail
274
275			#endif
276