include/boost/corosio/detail/intrusive.hpp

74.2% Lines (333/449) 100.0% List of functions (57/57)

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

intrusive.hpp

f(x) Functions (57)

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_;
39		T* prev_;
40		};
41
42		private:
43		T* head_ = nullptr;
44		T* tail_ = nullptr;
45
46		public:
47	3878x	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	32x	bool empty() const noexcept
62		{
63	32x	return head_ == nullptr;
64		}
65
66	41148x	void push_back(T* w) noexcept
67		{
68	41148x	auto* n = static_cast<node*>(w);
69	41148x	n->next_ = nullptr;
70	41148x	n->prev_ = tail_;
71	41148x	if (tail_)
72	23880x	static_cast<node*>(tail_)->next_ = w;
73		else
74	17268x	head_ = w;
75	41148x	tail_ = w;
76	41148x	}
77
78		void splice_back(intrusive_list& other) noexcept
79		{
80		if (other.empty())
81		return;
82		if (tail_)
83		{
84		static_cast<node*>(tail_)->next_ = other.head_;
85		static_cast<node*>(other.head_)->prev_ = tail_;
86		tail_ = other.tail_;
87		}
88		else
89		{
90		head_ = other.head_;
91		tail_ = other.tail_;
92		}
93		other.head_ = nullptr;
94		other.tail_ = nullptr;
95		}
96
97	193446x	T* pop_front() noexcept
98		{
99	193446x	if (!head_)
100	176678x	return nullptr;
101	16768x	T* w = head_;
102	16768x	head_ = static_cast<node*>(head_)->next_;
103	16768x	if (head_)
104	40x	static_cast<node*>(head_)->prev_ = nullptr;
105		else
106	16728x	tail_ = nullptr;
107		// Defensive: clear stale linkage so remove() on a
108		// popped node cannot corrupt the list.
109	16768x	auto* n = static_cast<node*>(w);
110	16768x	n->next_ = nullptr;
111	16768x	n->prev_ = nullptr;
112	16768x	return w;
113		}
114
115	24380x	void remove(T* w) noexcept
116		{
117	24380x	auto* n = static_cast<node*>(w);
118		// Already detached — nothing to do.
119	24380x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
120	✗	return;
121	24380x	if (n->prev_)
122	7892x	static_cast<node*>(n->prev_)->next_ = n->next_;
123		else
124	16488x	head_ = n->next_;
125	24380x	if (n->next_)
126	15970x	static_cast<node*>(n->next_)->prev_ = n->prev_;
127		else
128	8410x	tail_ = n->prev_;
129	24380x	n->next_ = nullptr;
130	24380x	n->prev_ = nullptr;
131		}
132
133		/// Invoke @p f for each element in the list.
134		template<class F>
135	67x	void for_each(F f)
136		{
137	67x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
138	✗	f(p);
139	67x	}
140		};
141
142		/** An intrusive singly linked FIFO queue.
143
144		This container provides O(1) push and pop operations for
145		elements that derive from @ref node. Elements are not
146		copied or moved; they are linked directly into the queue.
147
148		Unlike @ref intrusive_list, this uses only a single `next_`
149		pointer per node, saving memory at the cost of not supporting
150		O(1) removal of arbitrary elements.
151
152		@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
153		*/
154		template<class T>
155		class intrusive_queue
156		{
157		public:
158		/** Base class for queue elements.
159
160		Derive from this class to make a type usable with
161		@ref intrusive_queue. The `next_` pointer is private
162		and accessible only to the queue.
163		*/
164		class node
165		{
166		friend class intrusive_queue;
167
168		private:
169		T* next_;
170		};
171
172		private:
173		T* head_ = nullptr;
174		T* tail_ = nullptr;
175
176		public:
177	1447x	intrusive_queue() = default;
178
179		intrusive_queue(intrusive_queue&& other) noexcept
180		: head_(other.head_)
181		, tail_(other.tail_)
182		{
183		other.head_ = nullptr;
184		other.tail_ = nullptr;
185		}
186
187		intrusive_queue(intrusive_queue const&) = delete;
188		intrusive_queue& operator=(intrusive_queue const&) = delete;
189		intrusive_queue& operator=(intrusive_queue&&) = delete;
190
191	1571996x	bool empty() const noexcept
192		{
193	1571996x	return head_ == nullptr;
194		}
195
196	491756x	void push(T* w) noexcept
197		{
198	491756x	w->next_ = nullptr;
199	491756x	if (tail_)
200	207861x	tail_->next_ = w;
201		else
202	283895x	head_ = w;
203	491756x	tail_ = w;
204	491756x	}
205
206	259985x	void splice(intrusive_queue& other) noexcept
207		{
208	259985x	if (other.empty())
209	✗	return;
210	259985x	if (tail_)
211	118737x	tail_->next_ = other.head_;
212		else
213	141248x	head_ = other.head_;
214	259985x	tail_ = other.tail_;
215	259985x	other.head_ = nullptr;
216	259985x	other.tail_ = nullptr;
217		}
218
219	653715x	T* pop() noexcept
220		{
221	653715x	if (!head_)
222	161959x	return nullptr;
223	491756x	T* w = head_;
224	491756x	head_ = head_->next_;
225	491756x	if (!head_)
226	165158x	tail_ = nullptr;
227		// Defensive: clear stale linkage on popped node.
228	491756x	w->next_ = nullptr;
229	491756x	return w;
230		}
231		};
232
233		} // namespace boost::corosio::detail
234
235		#endif
236