Index/src / corosio / src / detail / intrusive.hpp
Prev Index Next

src/corosio/src/detail/intrusive.hpp

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