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 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 40750 : void push_back(T* w) noexcept
67 : {
68 40750 : w->next_ = nullptr;
69 40750 : w->prev_ = tail_;
70 40750 : if (tail_)
71 23743 : tail_->next_ = w;
72 : else
73 17007 : head_ = w;
74 40750 : tail_ = w;
75 40750 : }
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 117712 : T* pop_front() noexcept
97 : {
98 117712 : if (!head_)
99 101000 : return nullptr;
100 16712 : T* w = head_;
101 16712 : head_ = head_->next_;
102 16712 : if (head_)
103 40 : head_->prev_ = nullptr;
104 : else
105 16672 : tail_ = nullptr;
106 : // Defensive: clear stale linkage so remove() on a
107 : // popped node cannot corrupt the list.
108 16712 : w->next_ = nullptr;
109 16712 : w->prev_ = nullptr;
110 16712 : return w;
111 : }
112 :
113 24038 : void remove(T* w) noexcept
114 : {
115 24038 : if (w->prev_)
116 7877 : w->prev_->next_ = w->next_;
117 : else
118 16161 : head_ = w->next_;
119 24038 : if (w->next_)
120 15848 : w->next_->prev_ = w->prev_;
121 : else
122 8190 : tail_ = w->prev_;
123 24038 : }
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 532 : 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 498456 : bool empty() const noexcept
176 : {
177 498456 : return head_ == nullptr;
178 : }
179 :
180 401002 : void push(T* w) noexcept
181 : {
182 401002 : w->next_ = nullptr;
183 401002 : if (tail_)
184 295956 : tail_->next_ = w;
185 : else
186 105046 : head_ = w;
187 401002 : tail_ = w;
188 401002 : }
189 :
190 85431 : void splice(intrusive_queue& other) noexcept
191 : {
192 85431 : if (other.empty())
193 MIS 0 : return;
194 HIT 85431 : if (tail_)
195 75912 : tail_->next_ = other.head_;
196 : else
197 9519 : head_ = other.head_;
198 85431 : tail_ = other.tail_;
199 85431 : other.head_ = nullptr;
200 85431 : other.tail_ = nullptr;
201 : }
202 :
203 434916 : T* pop() noexcept
204 : {
205 434916 : if (!head_)
206 33914 : return nullptr;
207 401002 : T* w = head_;
208 401002 : head_ = head_->next_;
209 401002 : if (!head_)
210 29134 : tail_ = nullptr;
211 : // Defensive: clear stale linkage on popped node.
212 401002 : w->next_ = nullptr;
213 401002 : return w;
214 : }
215 : };
216 :
217 : } // namespace boost::corosio::detail
218 :
219 : #endif
|
