Index/include / boost / capy / detail / intrusive.hpp
Prev Index Next

include/boost/capy/detail/intrusive.hpp

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