Index/include / boost / corosio / detail / intrusive.hpp

include/boost/corosio/detail/intrusive.hpp

67.2% Lines (39/58) 97.1% Functions (33/34) 60.0% Branches (12/20)
include/boost/corosio/detail/intrusive.hpp
Prev Index Next
Line Branch TLA 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 1852 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 3 bool empty() const noexcept
62 {
63 3 return head_ == nullptr;
64 }
65
66 13360 void push_back(T* w) noexcept
67 {
68 13360 w->next_ = nullptr;
69 13360 w->prev_ = tail_;
70
2/2
✓ Branch 2 → 3 taken 5144 times.
✓ Branch 2 → 4 taken 8216 times.
 13360 if (tail_)
71 5144 tail_->next_ = w;
72 else
73 8216 head_ = w;
74 13360 tail_ = w;
75 13360 }
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 8830 T* pop_front() noexcept
97 {
98
2/2
✓ Branch 2 → 3 taken 5279 times.
✓ Branch 2 → 4 taken 3551 times.
 8830 if (!head_)
99 5279 return nullptr;
100 3551 T* w = head_;
101 3551 head_ = head_->next_;
102
2/2
✓ Branch 4 → 5 taken 24 times.
✓ Branch 4 → 6 taken 3527 times.
 3551 if (head_)
103 24 head_->prev_ = nullptr;
104 else
105 3527 tail_ = nullptr;
106 // Defensive: clear stale linkage so remove() on a
107 // popped node cannot corrupt the list.
108 3551 w->next_ = nullptr;
109 3551 w->prev_ = nullptr;
110 3551 return w;
111 }
112
113 9809 void remove(T* w) noexcept
114 {
115
2/2
✓ Branch 2 → 3 taken 161 times.
✓ Branch 2 → 4 taken 9648 times.
 9809 if (w->prev_)
116 161 w->prev_->next_ = w->next_;
117 else
118 9648 head_ = w->next_;
119
2/2
✓ Branch 5 → 6 taken 5077 times.
✓ Branch 5 → 7 taken 4732 times.
 9809 if (w->next_)
120 5077 w->next_->prev_ = w->prev_;
121 else
122 4732 tail_ = w->prev_;
123 9809 }
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 290 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 1326 bool empty() const noexcept
176 {
177 1326 return head_ == nullptr;
178 }
179
180 ✗ void push(T* w) noexcept
181 {
182 ✗ w->next_ = nullptr;
183 ✗ if (tail_)
184 ✗ tail_->next_ = w;
185 else
186 ✗ head_ = w;
187 ✗ tail_ = w;
188 ✗ }
189
190 1326 void splice(intrusive_queue& other) noexcept
191 {
192
1/2
✓ Branch 3 → 4 taken 1326 times.
✗ Branch 3 → 5 not taken.
 1326 if (other.empty())
193 1326 return;
194 ✗ if (tail_)
195 ✗ tail_->next_ = other.head_;
196 else
197 ✗ head_ = other.head_;
198 ✗ tail_ = other.tail_;
199 ✗ other.head_ = nullptr;
200 ✗ other.tail_ = nullptr;
201 }
202
203 1326 T* pop() noexcept
204 {
205
1/2
✓ Branch 2 → 3 taken 1326 times.
✗ Branch 2 → 4 not taken.
 1326 if (!head_)
206 1326 return nullptr;
207 ✗ T* w = head_;
208 ✗ head_ = head_->next_;
209 ✗ if (!head_)
210 ✗ tail_ = nullptr;
211 // Defensive: clear stale linkage on popped node.
212 ✗ w->next_ = nullptr;
213 ✗ return w;
214 }
215 };
216
217 } // namespace boost::corosio::detail
218
219 #endif
220