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 10606 : 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 38 : bool empty() const noexcept
62 : {
63 38 : return head_ == nullptr;
64 : }
65 :
66 : /// Peek at the head element without removing it.
67 : T* front() const noexcept
68 : {
69 : return head_;
70 : }
71 :
72 11901 : void push_back(T* w) noexcept
73 : {
74 11901 : auto* n = static_cast<node*>(w);
75 11901 : n->next_ = nullptr;
76 11901 : n->prev_ = tail_;
77 11901 : if (tail_)
78 6040 : static_cast<node*>(tail_)->next_ = w;
79 : else
80 5861 : head_ = w;
81 11901 : tail_ = w;
82 11901 : }
83 :
84 : void splice_back(intrusive_list& other) noexcept
85 : {
86 : if (other.empty())
87 : return;
88 : if (tail_)
89 : {
90 : static_cast<node*>(tail_)->next_ = other.head_;
91 : static_cast<node*>(other.head_)->prev_ = tail_;
92 : tail_ = other.tail_;
93 : }
94 : else
95 : {
96 : head_ = other.head_;
97 : tail_ = other.tail_;
98 : }
99 : other.head_ = nullptr;
100 : other.tail_ = nullptr;
101 : }
102 :
103 209939 : T* pop_front() noexcept
104 : {
105 209939 : if (!head_)
106 205129 : return nullptr;
107 4810 : T* w = head_;
108 4810 : head_ = static_cast<node*>(head_)->next_;
109 4810 : if (head_)
110 41 : static_cast<node*>(head_)->prev_ = nullptr;
111 : else
112 4769 : tail_ = nullptr;
113 : // Defensive: clear stale linkage so remove() on a
114 : // popped node cannot corrupt the list.
115 4810 : auto* n = static_cast<node*>(w);
116 4810 : n->next_ = nullptr;
117 4810 : n->prev_ = nullptr;
118 4810 : return w;
119 : }
120 :
121 7091 : void remove(T* w) noexcept
122 : {
123 7091 : auto* n = static_cast<node*>(w);
124 : // Already detached — nothing to do.
125 7091 : if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
126 MIS 0 : return;
127 HIT 7091 : if (n->prev_)
128 2003 : static_cast<node*>(n->prev_)->next_ = n->next_;
129 : else
130 5088 : head_ = n->next_;
131 7091 : if (n->next_)
132 4043 : static_cast<node*>(n->next_)->prev_ = n->prev_;
133 : else
134 3048 : tail_ = n->prev_;
135 7091 : n->next_ = nullptr;
136 7091 : n->prev_ = nullptr;
137 : }
138 :
139 : /// Invoke @p f for each element in the list.
140 : template<class F>
141 122 : void for_each(F f)
142 : {
143 122 : for (T* p = head_; p; p = static_cast<node*>(p)->next_)
144 MIS 0 : f(p);
145 HIT 122 : }
146 : };
147 :
148 : /** An intrusive singly linked FIFO queue.
149 :
150 : This container provides O(1) push and pop operations for
151 : elements that derive from @ref node. Elements are not
152 : copied or moved; they are linked directly into the queue.
153 :
154 : Unlike @ref intrusive_list, this uses only a single `next_`
155 : pointer per node, saving memory at the cost of not supporting
156 : O(1) removal of arbitrary elements.
157 :
158 : @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
159 : */
160 : template<class T>
161 : class intrusive_queue
162 : {
163 : public:
164 : /** Base class for queue elements.
165 :
166 : Derive from this class to make a type usable with
167 : @ref intrusive_queue. The `next_` pointer is private
168 : and accessible only to the queue.
169 : */
170 : class node
171 : {
172 : friend class intrusive_queue;
173 :
174 : private:
175 : T* next_;
176 : };
177 :
178 : private:
179 : T* head_ = nullptr;
180 : T* tail_ = nullptr;
181 :
182 : public:
183 2734 : intrusive_queue() = default;
184 :
185 : intrusive_queue(intrusive_queue&& other) noexcept
186 : : head_(other.head_)
187 : , tail_(other.tail_)
188 : {
189 : other.head_ = nullptr;
190 : other.tail_ = nullptr;
191 : }
192 :
193 : intrusive_queue(intrusive_queue const&) = delete;
194 : intrusive_queue& operator=(intrusive_queue const&) = delete;
195 : intrusive_queue& operator=(intrusive_queue&&) = delete;
196 :
197 1715865 : bool empty() const noexcept
198 : {
199 1715865 : return head_ == nullptr;
200 : }
201 :
202 522573 : void push(T* w) noexcept
203 : {
204 522573 : w->next_ = nullptr;
205 522573 : if (tail_)
206 227507 : tail_->next_ = w;
207 : else
208 295066 : head_ = w;
209 522573 : tail_ = w;
210 522573 : }
211 :
212 288499 : void splice(intrusive_queue& other) noexcept
213 : {
214 288499 : if (other.empty())
215 MIS 0 : return;
216 HIT 288499 : if (tail_)
217 117377 : tail_->next_ = other.head_;
218 : else
219 171122 : head_ = other.head_;
220 288499 : tail_ = other.tail_;
221 288499 : other.head_ = nullptr;
222 288499 : other.tail_ = nullptr;
223 : }
224 :
225 728645 : T* pop() noexcept
226 : {
227 728645 : if (!head_)
228 206072 : return nullptr;
229 522573 : T* w = head_;
230 522573 : head_ = head_->next_;
231 522573 : if (!head_)
232 177689 : tail_ = nullptr;
233 : // Defensive: clear stale linkage on popped node.
234 522573 : w->next_ = nullptr;
235 522573 : return w;
236 : }
237 : };
238 :
239 : } // namespace boost::corosio::detail
240 :
241 : #endif
|
