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 42152 void push_back(T* w) noexcept
67 {
68 42152 w->next_ = nullptr;
69 42152 w->prev_ = tail_;
70 42152 if (tail_)
71 24582 tail_->next_ = w;
72 else
73 17570 head_ = w;
74 42152 tail_ = w;
75 42152 }
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 112339 T* pop_front() noexcept
97 {
98 112339 if (!head_)
99 95063 return nullptr;
100 17276 T* w = head_;
101 17276 head_ = head_->next_;
102 17276 if (head_)
103 41 head_->prev_ = nullptr;
104 else
105 17235 tail_ = nullptr;
106 // Defensive: clear stale linkage so remove() on a
107 // popped node cannot corrupt the list.
108 17276 w->next_ = nullptr;
109 17276 w->prev_ = nullptr;
110 17276 return w;
111 }
112
113 24876 void remove(T* w) noexcept
114 {
115 24876 if (w->prev_)
116 8155 w->prev_->next_ = w->next_;
117 else
118 16721 head_ = w->next_;
119 24876 if (w->next_)
120 16408 w->next_->prev_ = w->prev_;
121 else
122 8468 tail_ = w->prev_;
123 24876 }
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 531 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 537634 bool empty() const noexcept
176 {
177 537634 return head_ == nullptr;
178 }
179
180 379917 void push(T* w) noexcept
181 {
182 379917 w->next_ = nullptr;
183 379917 if (tail_)
184 263409 tail_->next_ = w;
185 else
186 116508 head_ = w;
187 379917 tail_ = w;
188 379917 }
189
190 96081 void splice(intrusive_queue& other) noexcept
191 {
192 96081 if (other.empty())
193 ✗ return;
194 96081 if (tail_)
195 86411 tail_->next_ = other.head_;
196 else
197 9670 head_ = other.head_;
198 96081 tail_ = other.tail_;
199 96081 other.head_ = nullptr;
200 96081 other.tail_ = nullptr;
201 }
202
203 418700 T* pop() noexcept
204 {
205 418700 if (!head_)
206 38783 return nullptr;
207 379917 T* w = head_;
208 379917 head_ = head_->next_;
209 379917 if (!head_)
210 30097 tail_ = nullptr;
211 // Defensive: clear stale linkage on popped node.
212 379917 w->next_ = nullptr;
213 379917 return w;
214 }
215 };
216
217 } // namespace boost::corosio::detail
218
219 #endif
220