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 40577 void push_back(T* w) noexcept
67 {
68 40577 w->next_ = nullptr;
69 40577 w->prev_ = tail_;
70 40577 if (tail_)
71 23640 tail_->next_ = w;
72 else
73 16937 head_ = w;
74 40577 tail_ = w;
75 40577 }
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 115210 T* pop_front() noexcept
97 {
98 115210 if (!head_)
99 98566 return nullptr;
100 16644 T* w = head_;
101 16644 head_ = head_->next_;
102 16644 if (head_)
103 42 head_->prev_ = nullptr;
104 else
105 16602 tail_ = nullptr;
106 // Defensive: clear stale linkage so remove() on a
107 // popped node cannot corrupt the list.
108 16644 w->next_ = nullptr;
109 16644 w->prev_ = nullptr;
110 16644 return w;
111 }
112
113 23933 void remove(T* w) noexcept
114 {
115 23933 if (w->prev_)
116 7840 w->prev_->next_ = w->next_;
117 else
118 16093 head_ = w->next_;
119 23933 if (w->next_)
120 15780 w->next_->prev_ = w->prev_;
121 else
122 8153 tail_ = w->prev_;
123 23933 }
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 489231 bool empty() const noexcept
176 {
177 489231 return head_ == nullptr;
178 }
179
180 388105 void push(T* w) noexcept
181 {
182 388105 w->next_ = nullptr;
183 388105 if (tail_)
184 283952 tail_->next_ = w;
185 else
186 104153 head_ = w;
187 388105 tail_ = w;
188 388105 }
189
190 84400 void splice(intrusive_queue& other) noexcept
191 {
192 84400 if (other.empty())
193 ✗ return;
194 84400 if (tail_)
195 75335 tail_->next_ = other.head_;
196 else
197 9065 head_ = other.head_;
198 84400 tail_ = other.tail_;
199 84400 other.head_ = nullptr;
200 84400 other.tail_ = nullptr;
201 }
202
203 421790 T* pop() noexcept
204 {
205 421790 if (!head_)
206 33685 return nullptr;
207 388105 T* w = head_;
208 388105 head_ = head_->next_;
209 388105 if (!head_)
210 28818 tail_ = nullptr;
211 // Defensive: clear stale linkage on popped node.
212 388105 w->next_ = nullptr;
213 388105 return w;
214 }
215 };
216
217 } // namespace boost::corosio::detail
218
219 #endif
220