include/boost/corosio/detail/intrusive.hpp

100.0% Lines (103 / 103) 87.3% Functions (178 / 204)

[ ] prev/next file

intrusive.hpp

f(x) Functions (204)

Function Calls Lines Blocks

Line	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/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	18302x	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	17x	bool empty() const noexcept
62		{
63	17x	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	30656x	void push_front(T* w) noexcept
73		{
74	30656x	auto* n = static_cast<node*>(w);
75	30656x	n->prev_ = nullptr;
76	30656x	n->next_ = head_;
77	30656x	if (head_)
78	17329x	static_cast<node*>(head_)->prev_ = w;
79		else
80	13327x	tail_ = w;
81	30656x	head_ = w;
82	30656x	}
83
84	73793x	void push_back(T* w) noexcept
85		{
86	73793x	auto* n = static_cast<node*>(w);
87	73793x	n->next_ = nullptr;
88	73793x	n->prev_ = tail_;
89	73793x	if (tail_)
90	53046x	static_cast<node*>(tail_)->next_ = w;
91		else
92	20747x	head_ = w;
93	73793x	tail_ = w;
94	73793x	}
95
96	3x	void splice_back(intrusive_list& other) noexcept
97		{
98	3x	if (other.empty())
99	1x	return;
100	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	304258x	T* pop_front() noexcept
116		{
117	304258x	if (!head_)
118	254909x	return nullptr;
119	49349x	T* w = head_;
120	49349x	head_ = static_cast<node*>(head_)->next_;
121	49349x	if (head_)
122	25417x	static_cast<node*>(head_)->prev_ = nullptr;
123		else
124	23932x	tail_ = nullptr;
125		// Defensive: clear stale linkage so remove() on a
126		// popped node cannot corrupt the list.
127	49349x	auto* n = static_cast<node*>(w);
128	49349x	n->next_ = nullptr;
129	49349x	n->prev_ = nullptr;
130	49349x	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	55099x	bool remove(T* w) noexcept
155		{
156	55099x	auto* n = static_cast<node*>(w);
157		// Already detached — nothing to do.
158	55099x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
159	2x	return false;
160	55097x	if (n->prev_)
161	21688x	static_cast<node*>(n->prev_)->next_ = n->next_;
162		else
163	33409x	head_ = n->next_;
164	55097x	if (n->next_)
165	33804x	static_cast<node*>(n->next_)->prev_ = n->prev_;
166		else
167	21293x	tail_ = n->prev_;
168	55097x	n->next_ = nullptr;
169	55097x	n->prev_ = nullptr;
170	55097x	return true;
171		}
172
173		/// Invoke @p f for each element in the list.
174		template<class F>
175	27365x	void for_each(F f)
176		{
177	45791x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
178	18426x	f(p);
179	27365x	}
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	4417x	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	6664x	bool empty() const noexcept
232		{
233	6664x	return head_ == nullptr;
234		}
235
236	4733x	void push(T* w) noexcept
237		{
238	4733x	w->next_ = nullptr;
239	4733x	if (tail_)
240	3723x	tail_->next_ = w;
241		else
242	1010x	head_ = w;
243	4733x	tail_ = w;
244	4733x	}
245
246	4437x	void splice(intrusive_queue& other) noexcept
247		{
248	4437x	if (other.empty())
249	4416x	return;
250	21x	if (tail_)
251	1x	tail_->next_ = other.head_;
252		else
253	20x	head_ = other.head_;
254	21x	tail_ = other.tail_;
255	21x	other.head_ = nullptr;
256	21x	other.tail_ = nullptr;
257		}
258
259	9168x	T* pop() noexcept
260		{
261	9168x	if (!head_)
262	4435x	return nullptr;
263	4733x	T* w = head_;
264	4733x	head_ = head_->next_;
265	4733x	if (!head_)
266	1009x	tail_ = nullptr;
267		// Defensive: clear stale linkage on popped node.
268	4733x	w->next_ = nullptr;
269	4733x	return w;
270		}
271		};
272
273		} // namespace boost::corosio::detail
274
275		#endif
276