include/boost/corosio/detail/intrusive.hpp

76.1% Lines (229/301) 100.0% List of functions (45/45)

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

f(x) Functions (45)

Function Calls Lines Blocks

Line	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_;
39		T* prev_;
40		};
41
42		private:
43		T* head_ = nullptr;
44		T* tail_ = nullptr;
45
46		public:
47	2938x	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	52115x	void push_back(T* w) noexcept
67		{
68	52115x	w->next_ = nullptr;
69	52115x	w->prev_ = tail_;
70	52115x	if (tail_)
71	29176x	tail_->next_ = w;
72		else
73	22939x	head_ = w;
74	52115x	tail_ = w;
75	52115x	}
76
77		void splice_back(intrusive_list& other) noexcept
78		{
79		if (other.empty())
80		return;
81		if (tail_)
82		{
83		tail_->next_ = other.head_;
84		other.head_->prev_ = tail_;
85		tail_ = other.tail_;
86		}
87		else
88		{
89		head_ = other.head_;
90		tail_ = other.tail_;
91		}
92		other.head_ = nullptr;
93		other.tail_ = nullptr;
94		}
95
96	269269x	T* pop_front() noexcept
97		{
98	269269x	if (!head_)
99	248893x	return nullptr;
100	20376x	T* w = head_;
101	20376x	head_ = head_->next_;
102	20376x	if (head_)
103	40x	head_->prev_ = nullptr;
104		else
105	20336x	tail_ = nullptr;
106		// Defensive: clear stale linkage so remove() on a
107		// popped node cannot corrupt the list.
108	20376x	w->next_ = nullptr;
109	20376x	w->prev_ = nullptr;
110	20376x	return w;
111		}
112
113	31739x	void remove(T* w) noexcept
114		{
115	31739x	if (w->prev_)
116	9012x	w->prev_->next_ = w->next_;
117		else
118	22727x	head_ = w->next_;
119	31739x	if (w->next_)
120	20188x	w->next_->prev_ = w->prev_;
121		else
122	11551x	tail_ = w->prev_;
123	31739x	}
124		};
125
126		/** An intrusive singly linked FIFO queue.
127
128		This container provides O(1) push and pop operations for
129		elements that derive from @ref node. Elements are not
130		copied or moved; they are linked directly into the queue.
131
132		Unlike @ref intrusive_list, this uses only a single `next_`
133		pointer per node, saving memory at the cost of not supporting
134		O(1) removal of arbitrary elements.
135
136		@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
137		*/
138		template<class T>
139		class intrusive_queue
140		{
141		public:
142		/** Base class for queue elements.
143
144		Derive from this class to make a type usable with
145		@ref intrusive_queue. The `next_` pointer is private
146		and accessible only to the queue.
147		*/
148		class node
149		{
150		friend class intrusive_queue;
151
152		private:
153		T* next_;
154		};
155
156		private:
157		T* head_ = nullptr;
158		T* tail_ = nullptr;
159
160		public:
161	3945x	intrusive_queue() = default;
162
163		intrusive_queue(intrusive_queue&& other) noexcept
164		: head_(other.head_)
165		, tail_(other.tail_)
166		{
167		other.head_ = nullptr;
168		other.tail_ = nullptr;
169		}
170
171		intrusive_queue(intrusive_queue const&) = delete;
172		intrusive_queue& operator=(intrusive_queue const&) = delete;
173		intrusive_queue& operator=(intrusive_queue&&) = delete;
174
175	2218563x	bool empty() const noexcept
176		{
177	2218563x	return head_ == nullptr;
178		}
179
180	687298x	void push(T* w) noexcept
181		{
182	687298x	w->next_ = nullptr;
183	687298x	if (tail_)
184	303109x	tail_->next_ = w;
185		else
186	384189x	head_ = w;
187	687298x	tail_ = w;
188	687298x	}
189
190	353092x	void splice(intrusive_queue& other) noexcept
191		{
192	353092x	if (other.empty())
193	✗	return;
194	353092x	if (tail_)
195	134717x	tail_->next_ = other.head_;
196		else
197	218375x	head_ = other.head_;
198	353092x	tail_ = other.tail_;
199	353092x	other.head_ = nullptr;
200	353092x	other.tail_ = nullptr;
201		}
202
203	925572x	T* pop() noexcept
204		{
205	925572x	if (!head_)
206	238274x	return nullptr;
207	687298x	T* w = head_;
208	687298x	head_ = head_->next_;
209	687298x	if (!head_)
210	249472x	tail_ = nullptr;
211		// Defensive: clear stale linkage on popped node.
212	687298x	w->next_ = nullptr;
213	687298x	return w;
214		}
215		};
216
217		} // namespace boost::corosio::detail
218
219		#endif
220