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

include/boost/corosio/detail/intrusive.hpp

98.3% Lines (57/58) 100.0% Functions (34/34)
include/boost/corosio/detail/intrusive.hpp
Prev Index Next
Line TLA 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 43739 void push_back(T* w) noexcept
67 {
68 43739 w->next_ = nullptr;
69 43739 w->prev_ = tail_;
70 43739 if (tail_)
71 25533 tail_->next_ = w;
72 else
73 18206 head_ = w;
74 43739 tail_ = w;
75 43739 }
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 121860 T* pop_front() noexcept
97 {
98 121860 if (!head_)
99 103948 return nullptr;
100 17912 T* w = head_;
101 17912 head_ = head_->next_;
102 17912 if (head_)
103 41 head_->prev_ = nullptr;
104 else
105 17871 tail_ = nullptr;
106 // Defensive: clear stale linkage so remove() on a
107 // popped node cannot corrupt the list.
108 17912 w->next_ = nullptr;
109 17912 w->prev_ = nullptr;
110 17912 return w;
111 }
112
113 25827 void remove(T* w) noexcept
114 {
115 25827 if (w->prev_)
116 8472 w->prev_->next_ = w->next_;
117 else
118 17355 head_ = w->next_;
119 25827 if (w->next_)
120 17042 w->next_->prev_ = w->prev_;
121 else
122 8785 tail_ = w->prev_;
123 25827 }
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 485619 bool empty() const noexcept
176 {
177 485619 return head_ == nullptr;
178 }
179
180 404645 void push(T* w) noexcept
181 {
182 404645 w->next_ = nullptr;
183 404645 if (tail_)
184 301903 tail_->next_ = w;
185 else
186 102742 head_ = w;
187 404645 tail_ = w;
188 404645 }
189
190 81626 void splice(intrusive_queue& other) noexcept
191 {
192 81626 if (other.empty())
193 ✗ return;
194 81626 if (tail_)
195 71462 tail_->next_ = other.head_;
196 else
197 10164 head_ = other.head_;
198 81626 tail_ = other.tail_;
199 81626 other.head_ = nullptr;
200 81626 other.tail_ = nullptr;
201 }
202
203 436120 T* pop() noexcept
204 {
205 436120 if (!head_)
206 31475 return nullptr;
207 404645 T* w = head_;
208 404645 head_ = head_->next_;
209 404645 if (!head_)
210 31280 tail_ = nullptr;
211 // Defensive: clear stale linkage on popped node.
212 404645 w->next_ = nullptr;
213 404645 return w;
214 }
215 };
216
217 } // namespace boost::corosio::detail
218
219 #endif
220