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_;
39 : T* prev_;
40 : };
41 :
42 : private:
43 : T* head_ = nullptr;
44 : T* tail_ = nullptr;
45 :
46 : public:
47 HIT 3878 : 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 32 : bool empty() const noexcept
62 : {
63 32 : return head_ == nullptr;
64 : }
65 :
66 41148 : void push_back(T* w) noexcept
67 : {
68 41148 : auto* n = static_cast<node*>(w);
69 41148 : n->next_ = nullptr;
70 41148 : n->prev_ = tail_;
71 41148 : if (tail_)
72 23880 : static_cast<node*>(tail_)->next_ = w;
73 : else
74 17268 : head_ = w;
75 41148 : tail_ = w;
76 41148 : }
77 :
78 : void splice_back(intrusive_list& other) noexcept
79 : {
80 : if (other.empty())
81 : return;
82 : if (tail_)
83 : {
84 : static_cast<node*>(tail_)->next_ = other.head_;
85 : static_cast<node*>(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 193446 : T* pop_front() noexcept
98 : {
99 193446 : if (!head_)
100 176678 : return nullptr;
101 16768 : T* w = head_;
102 16768 : head_ = static_cast<node*>(head_)->next_;
103 16768 : if (head_)
104 40 : static_cast<node*>(head_)->prev_ = nullptr;
105 : else
106 16728 : tail_ = nullptr;
107 : // Defensive: clear stale linkage so remove() on a
108 : // popped node cannot corrupt the list.
109 16768 : auto* n = static_cast<node*>(w);
110 16768 : n->next_ = nullptr;
111 16768 : n->prev_ = nullptr;
112 16768 : return w;
113 : }
114 :
115 24380 : void remove(T* w) noexcept
116 : {
117 24380 : auto* n = static_cast<node*>(w);
118 : // Already detached — nothing to do.
119 24380 : if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
120 MIS 0 : return;
121 HIT 24380 : if (n->prev_)
122 7892 : static_cast<node*>(n->prev_)->next_ = n->next_;
123 : else
124 16488 : head_ = n->next_;
125 24380 : if (n->next_)
126 15970 : static_cast<node*>(n->next_)->prev_ = n->prev_;
127 : else
128 8410 : tail_ = n->prev_;
129 24380 : n->next_ = nullptr;
130 24380 : n->prev_ = nullptr;
131 : }
132 :
133 : /// Invoke @p f for each element in the list.
134 : template<class F>
135 67 : void for_each(F f)
136 : {
137 67 : for (T* p = head_; p; p = static_cast<node*>(p)->next_)
138 MIS 0 : f(p);
139 HIT 67 : }
140 : };
141 :
142 : /** An intrusive singly linked FIFO queue.
143 :
144 : This container provides O(1) push and pop operations for
145 : elements that derive from @ref node. Elements are not
146 : copied or moved; they are linked directly into the queue.
147 :
148 : Unlike @ref intrusive_list, this uses only a single `next_`
149 : pointer per node, saving memory at the cost of not supporting
150 : O(1) removal of arbitrary elements.
151 :
152 : @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
153 : */
154 : template<class T>
155 : class intrusive_queue
156 : {
157 : public:
158 : /** Base class for queue elements.
159 :
160 : Derive from this class to make a type usable with
161 : @ref intrusive_queue. The `next_` pointer is private
162 : and accessible only to the queue.
163 : */
164 : class node
165 : {
166 : friend class intrusive_queue;
167 :
168 : private:
169 : T* next_;
170 : };
171 :
172 : private:
173 : T* head_ = nullptr;
174 : T* tail_ = nullptr;
175 :
176 : public:
177 1447 : intrusive_queue() = default;
178 :
179 : intrusive_queue(intrusive_queue&& other) noexcept
180 : : head_(other.head_)
181 : , tail_(other.tail_)
182 : {
183 : other.head_ = nullptr;
184 : other.tail_ = nullptr;
185 : }
186 :
187 : intrusive_queue(intrusive_queue const&) = delete;
188 : intrusive_queue& operator=(intrusive_queue const&) = delete;
189 : intrusive_queue& operator=(intrusive_queue&&) = delete;
190 :
191 1571996 : bool empty() const noexcept
192 : {
193 1571996 : return head_ == nullptr;
194 : }
195 :
196 491756 : void push(T* w) noexcept
197 : {
198 491756 : w->next_ = nullptr;
199 491756 : if (tail_)
200 207861 : tail_->next_ = w;
201 : else
202 283895 : head_ = w;
203 491756 : tail_ = w;
204 491756 : }
205 :
206 259985 : void splice(intrusive_queue& other) noexcept
207 : {
208 259985 : if (other.empty())
209 MIS 0 : return;
210 HIT 259985 : if (tail_)
211 118737 : tail_->next_ = other.head_;
212 : else
213 141248 : head_ = other.head_;
214 259985 : tail_ = other.tail_;
215 259985 : other.head_ = nullptr;
216 259985 : other.tail_ = nullptr;
217 : }
218 :
219 653715 : T* pop() noexcept
220 : {
221 653715 : if (!head_)
222 161959 : return nullptr;
223 491756 : T* w = head_;
224 491756 : head_ = head_->next_;
225 491756 : if (!head_)
226 165158 : tail_ = nullptr;
227 : // Defensive: clear stale linkage on popped node.
228 491756 : w->next_ = nullptr;
229 491756 : return w;
230 : }
231 : };
232 :
233 : } // namespace boost::corosio::detail
234 :
235 : #endif
|
