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