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

include/boost/corosio/detail/intrusive.hpp

98.3% Lines (57/58) 100.0% Functions (34/34)
include/boost/corosio/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/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 1533 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 6 bool empty() const noexcept
62 {
63 6 return head_ == nullptr;
64 }
65
66 37471 void push_back(T* w) noexcept
67 {
68 37471 w->next_ = nullptr;
69 37471 w->prev_ = tail_;
70 37471 if (tail_)
71 21778 tail_->next_ = w;
72 else
73 15693 head_ = w;
74 37471 tail_ = w;
75 37471 }
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 110749 T* pop_front() noexcept
97 {
98 110749 if (!head_)
99 95351 return nullptr;
100 15398 T* w = head_;
101 15398 head_ = head_->next_;
102 15398 if (head_)
103 40 head_->prev_ = nullptr;
104 else
105 15358 tail_ = nullptr;
106 // Defensive: clear stale linkage so remove() on a
107 // popped node cannot corrupt the list.
108 15398 w->next_ = nullptr;
109 15398 w->prev_ = nullptr;
110 15398 return w;
111 }
112
113 22073 void remove(T* w) noexcept
114 {
115 22073 if (w->prev_)
116 7222 w->prev_->next_ = w->next_;
117 else
118 14851 head_ = w->next_;
119 22073 if (w->next_)
120 14538 w->next_->prev_ = w->prev_;
121 else
122 7535 tail_ = w->prev_;
123 22073 }
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 528 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 486652 bool empty() const noexcept
176 {
177 486652 return head_ == nullptr;
178 }
179
180 400248 void push(T* w) noexcept
181 {
182 400248 w->next_ = nullptr;
183 400248 if (tail_)
184 296765 tail_->next_ = w;
185 else
186 103483 head_ = w;
187 400248 tail_ = w;
188 400248 }
189
190 85258 void splice(intrusive_queue& other) noexcept
191 {
192 85258 if (other.empty())
193 ✗ return;
194 85258 if (tail_)
195 76819 tail_->next_ = other.head_;
196 else
197 8439 head_ = other.head_;
198 85258 tail_ = other.tail_;
199 85258 other.head_ = nullptr;
200 85258 other.tail_ = nullptr;
201 }
202
203 434667 T* pop() noexcept
204 {
205 434667 if (!head_)
206 34419 return nullptr;
207 400248 T* w = head_;
208 400248 head_ = head_->next_;
209 400248 if (!head_)
210 26664 tail_ = nullptr;
211 // Defensive: clear stale linkage on popped node.
212 400248 w->next_ = nullptr;
213 400248 return w;
214 }
215 };
216
217 } // namespace boost::corosio::detail
218
219 #endif
220