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

libs/corosio/src/corosio/src/detail/intrusive.hpp

98.1% Lines (52/53) 100.0% Functions (33/33) 95.0% Branches (19/20)
libs/corosio/src/corosio/src/detail/intrusive.hpp
Line Branch Hits Source Code
1 //
2 // Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot 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 1854 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 empty() const noexcept
65 {
66 return head_ == nullptr;
67 }
68
69 void
70 36675 push_back(T* w) noexcept
71 {
72 36675 w->next_ = nullptr;
73 36675 w->prev_ = tail_;
74
2/2
✓ Branch 0 taken 9380 times.
✓ Branch 1 taken 27295 times.
 36675 if(tail_)
75 9380 tail_->next_ = w;
76 else
77 27295 head_ = w;
78 36675 tail_ = w;
79 36675 }
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 11337 pop_front() noexcept
103 {
104
2/2
✓ Branch 0 taken 1983 times.
✓ Branch 1 taken 9354 times.
 11337 if(!head_)
105 1983 return nullptr;
106 9354 T* w = head_;
107 9354 head_ = head_->next_;
108
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 9326 times.
 9354 if(head_)
109 28 head_->prev_ = nullptr;
110 else
111 9326 tail_ = nullptr;
112 9354 return w;
113 }
114
115 void
116 27321 remove(T* w) noexcept
117 {
118
2/2
✓ Branch 0 taken 9323 times.
✓ Branch 1 taken 17998 times.
 27321 if(w->prev_)
119 9323 w->prev_->next_ = w->next_;
120 else
121 17998 head_ = w->next_;
122
2/2
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 27286 times.
 27321 if(w->next_)
123 35 w->next_->prev_ = w->prev_;
124 else
125 27286 tail_ = w->prev_;
126 27321 }
127 };
128
129 //------------------------------------------------
130
131 /** An intrusive singly linked FIFO queue.
132
133 This container provides O(1) push and pop operations for
134 elements that derive from @ref node. Elements are not
135 copied or moved; they are linked directly into the queue.
136
137 Unlike @ref intrusive_list, this uses only a single `next_`
138 pointer per node, saving memory at the cost of not supporting
139 O(1) removal of arbitrary elements.
140
141 @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
142 */
143 template<class T>
144 class intrusive_queue
145 {
146 public:
147 /** Base class for queue elements.
148
149 Derive from this class to make a type usable with
150 @ref intrusive_queue. The `next_` pointer is private
151 and accessible only to the queue.
152 */
153 class node
154 {
155 friend class intrusive_queue;
156
157 private:
158 T* next_;
159 };
160
161 private:
162 T* head_ = nullptr;
163 T* tail_ = nullptr;
164
165 public:
166 477 intrusive_queue() = default;
167
168 intrusive_queue(intrusive_queue&& other) noexcept
169 : head_(other.head_)
170 , tail_(other.tail_)
171 {
172 other.head_ = nullptr;
173 other.tail_ = nullptr;
174 }
175
176 intrusive_queue(intrusive_queue const&) = delete;
177 intrusive_queue& operator=(intrusive_queue const&) = delete;
178 intrusive_queue& operator=(intrusive_queue&&) = delete;
179
180 bool
181 1621059 empty() const noexcept
182 {
183 1621059 return head_ == nullptr;
184 }
185
186 void
187 899315 push(T* w) noexcept
188 {
189 899315 w->next_ = nullptr;
190
2/2
✓ Branch 0 taken 561965 times.
✓ Branch 1 taken 337350 times.
 899315 if(tail_)
191 561965 tail_->next_ = w;
192 else
193 337350 head_ = w;
194 899315 tail_ = w;
195 899315 }
196
197 void
198 314923 splice(intrusive_queue& other) noexcept
199 {
200
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 314923 times.
 314923 if(other.empty())
201 ✗ return;
202
2/2
✓ Branch 0 taken 304663 times.
✓ Branch 1 taken 10260 times.
 314923 if(tail_)
203 304663 tail_->next_ = other.head_;
204 else
205 10260 head_ = other.head_;
206 314923 tail_ = other.tail_;
207 314923 other.head_ = nullptr;
208 314923 other.tail_ = nullptr;
209 }
210
211 T*
212 1014712 pop() noexcept
213 {
214
2/2
✓ Branch 0 taken 115397 times.
✓ Branch 1 taken 899315 times.
 1014712 if(!head_)
215 115397 return nullptr;
216 899315 T* w = head_;
217 899315 head_ = head_->next_;
218
2/2
✓ Branch 0 taken 32687 times.
✓ Branch 1 taken 866628 times.
 899315 if(!head_)
219 32687 tail_ = nullptr;
220 899315 return w;
221 }
222 };
223
224 } // namespace boost::corosio::detail
225
226 #endif
227