include/boost/corosio/detail/intrusive.hpp

100.0% Lines (93 / 93) 100.0% Functions (95 / 95)

[ ] prev/next file

intrusive.hpp

f(x) Functions (95)

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	2937x	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	12x	bool empty() const noexcept
62		{
63	12x	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	33359x	void push_back(T* w) noexcept
73		{
74	33359x	auto* n = static_cast<node*>(w);
75	33359x	n->next_ = nullptr;
76	33359x	n->prev_ = tail_;
77	33359x	if (tail_)
78	21055x	static_cast<node*>(tail_)->next_ = w;
79		else
80	12304x	head_ = w;
81	33359x	tail_ = w;
82	33359x	}
83
84	3x	void splice_back(intrusive_list& other) noexcept
85		{
86	3x	if (other.empty())
87	1x	return;
88	2x	if (tail_)
89		{
90	1x	static_cast<node*>(tail_)->next_ = other.head_;
91	1x	static_cast<node*>(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	359380x	T* pop_front() noexcept
104		{
105	359380x	if (!head_)
106	342743x	return nullptr;
107	16637x	T* w = head_;
108	16637x	head_ = static_cast<node*>(head_)->next_;
109	16637x	if (head_)
110	7156x	static_cast<node*>(head_)->prev_ = nullptr;
111		else
112	9481x	tail_ = nullptr;
113		// Defensive: clear stale linkage so remove() on a
114		// popped node cannot corrupt the list.
115	16637x	auto* n = static_cast<node*>(w);
116	16637x	n->next_ = nullptr;
117	16637x	n->prev_ = nullptr;
118	16637x	return w;
119		}
120
121	16720x	void remove(T* w) noexcept
122		{
123	16720x	auto* n = static_cast<node*>(w);
124		// Already detached — nothing to do.
125	16720x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
126	1x	return;
127	16719x	if (n->prev_)
128	4761x	static_cast<node*>(n->prev_)->next_ = n->next_;
129		else
130	11958x	head_ = n->next_;
131	16719x	if (n->next_)
132	9262x	static_cast<node*>(n->next_)->prev_ = n->prev_;
133		else
134	7457x	tail_ = n->prev_;
135	16719x	n->next_ = nullptr;
136	16719x	n->prev_ = nullptr;
137		}
138
139		/// Invoke @p f for each element in the list.
140		template<class F>
141	646x	void for_each(F f)
142		{
143	657x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
144	11x	f(p);
145	646x	}
146		};
147
148		/** An intrusive singly linked FIFO queue.
149
150		This container provides O(1) push and pop operations for
151		elements that derive from @ref node. Elements are not
152		copied or moved; they are linked directly into the queue.
153
154		Unlike @ref intrusive_list, this uses only a single `next_`
155		pointer per node, saving memory at the cost of not supporting
156		O(1) removal of arbitrary elements.
157
158		@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
159		*/
160		template<class T>
161		class intrusive_queue
162		{
163		public:
164		/** Base class for queue elements.
165
166		Derive from this class to make a type usable with
167		@ref intrusive_queue. The `next_` pointer is private
168		and accessible only to the queue.
169		*/
170		class node
171		{
172		friend class intrusive_queue;
173
174		private:
175		T* next_ = nullptr;
176		};
177
178		private:
179		T* head_ = nullptr;
180		T* tail_ = nullptr;
181
182		public:
183	2313x	intrusive_queue() = default;
184
185	1x	intrusive_queue(intrusive_queue&& other) noexcept
186	1x	: head_(other.head_)
187	1x	, tail_(other.tail_)
188		{
189	1x	other.head_ = nullptr;
190	1x	other.tail_ = nullptr;
191	1x	}
192
193		intrusive_queue(intrusive_queue const&) = delete;
194		intrusive_queue& operator=(intrusive_queue const&) = delete;
195		intrusive_queue& operator=(intrusive_queue&&) = delete;
196
197	1135x	bool empty() const noexcept
198		{
199	1135x	return head_ == nullptr;
200		}
201
202	727x	void push(T* w) noexcept
203		{
204	727x	w->next_ = nullptr;
205	727x	if (tail_)
206	265x	tail_->next_ = w;
207		else
208	462x	head_ = w;
209	727x	tail_ = w;
210	727x	}
211
212	3x	void splice(intrusive_queue& other) noexcept
213		{
214	3x	if (other.empty())
215	1x	return;
216	2x	if (tail_)
217	1x	tail_->next_ = other.head_;
218		else
219	1x	head_ = other.head_;
220	2x	tail_ = other.tail_;
221	2x	other.head_ = nullptr;
222	2x	other.tail_ = nullptr;
223		}
224
225	3330x	T* pop() noexcept
226		{
227	3330x	if (!head_)
228	2603x	return nullptr;
229	727x	T* w = head_;
230	727x	head_ = head_->next_;
231	727x	if (!head_)
232	461x	tail_ = nullptr;
233		// Defensive: clear stale linkage on popped node.
234	727x	w->next_ = nullptr;
235	727x	return w;
236		}
237		};
238
239		} // namespace boost::corosio::detail
240
241		#endif
242