TLA Line data 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_ = nullptr;
39 : T* prev_ = nullptr;
40 : };
41 :
42 : private:
43 : T* head_ = nullptr;
44 : T* tail_ = nullptr;
45 :
46 : public:
47 HIT 18302 : intrusive_list() = default;
48 :
49 1 : intrusive_list(intrusive_list&& other) noexcept
50 1 : : head_(other.head_)
51 1 : , tail_(other.tail_)
52 : {
53 1 : other.head_ = nullptr;
54 1 : other.tail_ = nullptr;
55 1 : }
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 17 : bool empty() const noexcept
62 : {
63 17 : return head_ == nullptr;
64 : }
65 :
66 : /// Peek at the head element without removing it.
67 6 : T* front() const noexcept
68 : {
69 6 : return head_;
70 : }
71 :
72 30656 : void push_front(T* w) noexcept
73 : {
74 30656 : auto* n = static_cast<node*>(w);
75 30656 : n->prev_ = nullptr;
76 30656 : n->next_ = head_;
77 30656 : if (head_)
78 17329 : static_cast<node*>(head_)->prev_ = w;
79 : else
80 13327 : tail_ = w;
81 30656 : head_ = w;
82 30656 : }
83 :
84 73793 : void push_back(T* w) noexcept
85 : {
86 73793 : auto* n = static_cast<node*>(w);
87 73793 : n->next_ = nullptr;
88 73793 : n->prev_ = tail_;
89 73793 : if (tail_)
90 53046 : static_cast<node*>(tail_)->next_ = w;
91 : else
92 20747 : head_ = w;
93 73793 : tail_ = w;
94 73793 : }
95 :
96 3 : void splice_back(intrusive_list& other) noexcept
97 : {
98 3 : if (other.empty())
99 1 : return;
100 2 : if (tail_)
101 : {
102 1 : static_cast<node*>(tail_)->next_ = other.head_;
103 1 : static_cast<node*>(other.head_)->prev_ = tail_;
104 1 : tail_ = other.tail_;
105 : }
106 : else
107 : {
108 1 : head_ = other.head_;
109 1 : tail_ = other.tail_;
110 : }
111 2 : other.head_ = nullptr;
112 2 : other.tail_ = nullptr;
113 : }
114 :
115 304258 : T* pop_front() noexcept
116 : {
117 304258 : if (!head_)
118 254909 : return nullptr;
119 49349 : T* w = head_;
120 49349 : head_ = static_cast<node*>(head_)->next_;
121 49349 : if (head_)
122 25417 : static_cast<node*>(head_)->prev_ = nullptr;
123 : else
124 23932 : tail_ = nullptr;
125 : // Defensive: clear stale linkage so remove() on a
126 : // popped node cannot corrupt the list.
127 49349 : auto* n = static_cast<node*>(w);
128 49349 : n->next_ = nullptr;
129 49349 : n->prev_ = nullptr;
130 49349 : return w;
131 : }
132 :
133 : /** Unlink @p w if it is a member of this list.
134 :
135 : @pre @p w is either a genuine member of `*this` list, or is
136 : fully detached (not linked in *any* `intrusive_list<T>`,
137 : including a different instance over the same `T`). This is
138 : not a membership test: `T::node` holds one shared `next_`/
139 : `prev_` pair regardless of which list currently owns it, so a
140 : node actually linked in a different list looks "not detached"
141 : here and would be spliced out using *this* list's `head_`/
142 : `tail_` for the boundary cases — corrupting both lists. A
143 : caller that cannot rule that out needs its own bookkeeping
144 : (e.g. a flag for which list currently owns the node) before
145 : calling this.
146 :
147 : @return True if @p w was linked in and has now been removed;
148 : false if it was already detached (e.g. a reentrant call from
149 : a self-referential keepalive dropping during the same
150 : teardown that already popped it elsewhere). Callers that gate
151 : a one-time action (recycling, deleting) on actually having
152 : removed something rely on this to make that action idempotent.
153 : */
154 55099 : bool remove(T* w) noexcept
155 : {
156 55099 : auto* n = static_cast<node*>(w);
157 : // Already detached — nothing to do.
158 55099 : if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
159 2 : return false;
160 55097 : if (n->prev_)
161 21688 : static_cast<node*>(n->prev_)->next_ = n->next_;
162 : else
163 33409 : head_ = n->next_;
164 55097 : if (n->next_)
165 33804 : static_cast<node*>(n->next_)->prev_ = n->prev_;
166 : else
167 21293 : tail_ = n->prev_;
168 55097 : n->next_ = nullptr;
169 55097 : n->prev_ = nullptr;
170 55097 : return true;
171 : }
172 :
173 : /// Invoke @p f for each element in the list.
174 : template<class F>
175 27365 : void for_each(F f)
176 : {
177 45791 : for (T* p = head_; p; p = static_cast<node*>(p)->next_)
178 18426 : f(p);
179 27365 : }
180 : };
181 :
182 : /** An intrusive singly linked FIFO queue.
183 :
184 : This container provides O(1) push and pop operations for
185 : elements that derive from @ref node. Elements are not
186 : copied or moved; they are linked directly into the queue.
187 :
188 : Unlike @ref intrusive_list, this uses only a single `next_`
189 : pointer per node, saving memory at the cost of not supporting
190 : O(1) removal of arbitrary elements.
191 :
192 : @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
193 : */
194 : template<class T>
195 : class intrusive_queue
196 : {
197 : public:
198 : /** Base class for queue elements.
199 :
200 : Derive from this class to make a type usable with
201 : @ref intrusive_queue. The `next_` pointer is private
202 : and accessible only to the queue.
203 : */
204 : class node
205 : {
206 : friend class intrusive_queue;
207 :
208 : private:
209 : T* next_ = nullptr;
210 : };
211 :
212 : private:
213 : T* head_ = nullptr;
214 : T* tail_ = nullptr;
215 :
216 : public:
217 4417 : intrusive_queue() = default;
218 :
219 1 : intrusive_queue(intrusive_queue&& other) noexcept
220 1 : : head_(other.head_)
221 1 : , tail_(other.tail_)
222 : {
223 1 : other.head_ = nullptr;
224 1 : other.tail_ = nullptr;
225 1 : }
226 :
227 : intrusive_queue(intrusive_queue const&) = delete;
228 : intrusive_queue& operator=(intrusive_queue const&) = delete;
229 : intrusive_queue& operator=(intrusive_queue&&) = delete;
230 :
231 6664 : bool empty() const noexcept
232 : {
233 6664 : return head_ == nullptr;
234 : }
235 :
236 4733 : void push(T* w) noexcept
237 : {
238 4733 : w->next_ = nullptr;
239 4733 : if (tail_)
240 3723 : tail_->next_ = w;
241 : else
242 1010 : head_ = w;
243 4733 : tail_ = w;
244 4733 : }
245 :
246 4437 : void splice(intrusive_queue& other) noexcept
247 : {
248 4437 : if (other.empty())
249 4416 : return;
250 21 : if (tail_)
251 1 : tail_->next_ = other.head_;
252 : else
253 20 : head_ = other.head_;
254 21 : tail_ = other.tail_;
255 21 : other.head_ = nullptr;
256 21 : other.tail_ = nullptr;
257 : }
258 :
259 9168 : T* pop() noexcept
260 : {
261 9168 : if (!head_)
262 4435 : return nullptr;
263 4733 : T* w = head_;
264 4733 : head_ = head_->next_;
265 4733 : if (!head_)
266 1009 : tail_ = nullptr;
267 : // Defensive: clear stale linkage on popped node.
268 4733 : w->next_ = nullptr;
269 4733 : return w;
270 : }
271 : };
272 :
273 : } // namespace boost::corosio::detail
274 :
275 : #endif
|
