include/boost/capy/detail/intrusive.hpp

100.0% Lines (81/81) 100.0% List of functions (21/21)

[ ] prev/next file

intrusive.hpp

f(x) Functions (21)

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/capy
8		//
9
10		#ifndef BOOST_CAPY_DETAIL_INTRUSIVE_HPP
11		#define BOOST_CAPY_DETAIL_INTRUSIVE_HPP
12
13		namespace boost {
14		namespace capy {
15		namespace detail {
16
17		//------------------------------------------------
18
19		/** An intrusive doubly linked list.
20
21		This container provides O(1) push and pop operations for
22		elements that derive from @ref node. Elements are not
23		copied or moved; they are linked directly into the list.
24
25		@tparam T The element type. Must derive from `intrusive_list<T>::node`.
26		*/
27		template<class T>
28		class intrusive_list
29		{
30		public:
31		/** Base class for list elements.
32
33		Derive from this class to make a type usable with
34		@ref intrusive_list. The `next_` and `prev_` pointers
35		are private and accessible only to the list.
36		*/
37		class node
38		{
39		friend class intrusive_list;
40
41		private:
42		T* next_;
43		T* prev_;
44		bool linked_ = false;
45		};
46
47		private:
48		T* head_ = nullptr;
49		T* tail_ = nullptr;
50
51		public:
52	31x	intrusive_list() = default;
53
54	2x	intrusive_list(intrusive_list&& other) noexcept
55	2x	: head_(other.head_)
56	2x	, tail_(other.tail_)
57		{
58	2x	other.head_ = nullptr;
59	2x	other.tail_ = nullptr;
60	2x	}
61
62		intrusive_list(intrusive_list const&) = delete;
63		intrusive_list& operator=(intrusive_list const&) = delete;
64		intrusive_list& operator=(intrusive_list&&) = delete;
65
66		bool
67	36x	empty() const noexcept
68		{
69	36x	return head_ == nullptr;
70		}
71
72		void
73	11512x	push_back(T* w) noexcept
74		{
75	11512x	w->next_ = nullptr;
76	11512x	w->prev_ = tail_;
77	11512x	if(tail_)
78	11441x	tail_->next_ = w;
79		else
80	71x	head_ = w;
81	11512x	tail_ = w;
82	11512x	w->linked_ = true;
83	11512x	}
84
85		void
86	4x	splice_back(intrusive_list& other) noexcept
87		{
88	4x	if(other.empty())
89	2x	return;
90	2x	if(tail_)
91		{
92	1x	tail_->next_ = other.head_;
93	1x	other.head_->prev_ = tail_;
94	1x	tail_ = other.tail_;
95		}
96		else
97		{
98	1x	head_ = other.head_;
99	1x	tail_ = other.tail_;
100		}
101	2x	other.head_ = nullptr;
102	2x	other.tail_ = nullptr;
103		}
104
105		T*
106	121x	pop_front() noexcept
107		{
108	121x	if(!head_)
109	69x	return nullptr;
110	52x	T* w = head_;
111	52x	head_ = head_->next_;
112	52x	if(head_)
113	22x	head_->prev_ = nullptr;
114		else
115	30x	tail_ = nullptr;
116	52x	w->linked_ = false;
117	52x	return w;
118		}
119
120		void
121	11461x	remove(T* w) noexcept
122		{
123	11461x	if(!w->linked_)
124	1x	return;
125	11460x	if(w->prev_)
126	7x	w->prev_->next_ = w->next_;
127		else
128	11453x	head_ = w->next_;
129	11460x	if(w->next_)
130	11415x	w->next_->prev_ = w->prev_;
131		else
132	45x	tail_ = w->prev_;
133	11460x	w->linked_ = false;
134		}
135		};
136
137		//------------------------------------------------
138
139		/** An intrusive singly linked FIFO queue.
140
141		This container provides O(1) push and pop operations for
142		elements that derive from @ref node. Elements are not
143		copied or moved; they are linked directly into the queue.
144
145		Unlike @ref intrusive_list, this uses only a single `next_`
146		pointer per node, saving memory at the cost of not supporting
147		O(1) removal of arbitrary elements.
148
149		@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
150		*/
151		template<class T>
152		class intrusive_queue
153		{
154		public:
155		/** Base class for queue elements.
156
157		Derive from this class to make a type usable with
158		@ref intrusive_queue. The `next_` pointer is private
159		and accessible only to the queue.
160		*/
161		class node
162		{
163		friend class intrusive_queue;
164
165		private:
166		T* next_;
167		};
168
169		private:
170		T* head_ = nullptr;
171		T* tail_ = nullptr;
172
173		public:
174		intrusive_queue() = default;
175
176	2x	intrusive_queue(intrusive_queue&& other) noexcept
177	2x	: head_(other.head_)
178	2x	, tail_(other.tail_)
179		{
180	2x	other.head_ = nullptr;
181	2x	other.tail_ = nullptr;
182	2x	}
183
184		intrusive_queue(intrusive_queue const&) = delete;
185		intrusive_queue& operator=(intrusive_queue const&) = delete;
186		intrusive_queue& operator=(intrusive_queue&&) = delete;
187
188		bool
189	27x	empty() const noexcept
190		{
191	27x	return head_ == nullptr;
192		}
193
194		void
195	18x	push(T* w) noexcept
196		{
197	18x	w->next_ = nullptr;
198	18x	if(tail_)
199	8x	tail_->next_ = w;
200		else
201	10x	head_ = w;
202	18x	tail_ = w;
203	18x	}
204
205		void
206	4x	splice(intrusive_queue& other) noexcept
207		{
208	4x	if(other.empty())
209	2x	return;
210	2x	if(tail_)
211	1x	tail_->next_ = other.head_;
212		else
213	1x	head_ = other.head_;
214	2x	tail_ = other.tail_;
215	2x	other.head_ = nullptr;
216	2x	other.tail_ = nullptr;
217		}
218
219		T*
220	21x	pop() noexcept
221		{
222	21x	if(!head_)
223	3x	return nullptr;
224	18x	T* w = head_;
225	18x	head_ = head_->next_;
226	18x	if(!head_)
227	9x	tail_ = nullptr;
228	18x	return w;
229		}
230		};
231
232		} // detail
233		} // capy
234		} // boost
235
236		#endif
237