Line data Source code
1 : //
2 : // Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot 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 : //------------------------------------------------
16 :
17 : /** An intrusive doubly linked list.
18 :
19 : This container provides O(1) push and pop operations for
20 : elements that derive from @ref node. Elements are not
21 : copied or moved; they are linked directly into the list.
22 :
23 : @tparam T The element type. Must derive from `intrusive_list<T>::node`.
24 : */
25 : template<class T>
26 : class intrusive_list
27 : {
28 : public:
29 : /** Base class for list elements.
30 :
31 : Derive from this class to make a type usable with
32 : @ref intrusive_list. The `next_` and `prev_` pointers
33 : are private and accessible only to the list.
34 : */
35 : class node
36 : {
37 : friend class intrusive_list;
38 :
39 : private:
40 : T* next_;
41 : T* prev_;
42 : };
43 :
44 : private:
45 : T* head_ = nullptr;
46 : T* tail_ = nullptr;
47 :
48 : public:
49 1854 : intrusive_list() = default;
50 :
51 : intrusive_list(intrusive_list&& other) noexcept
52 : : head_(other.head_)
53 : , tail_(other.tail_)
54 : {
55 : other.head_ = nullptr;
56 : other.tail_ = nullptr;
57 : }
58 :
59 : intrusive_list(intrusive_list const&) = delete;
60 : intrusive_list& operator=(intrusive_list const&) = delete;
61 : intrusive_list& operator=(intrusive_list&&) = delete;
62 :
63 : bool
64 : empty() const noexcept
65 : {
66 : return head_ == nullptr;
67 : }
68 :
69 : void
70 36675 : push_back(T* w) noexcept
71 : {
72 36675 : w->next_ = nullptr;
73 36675 : w->prev_ = tail_;
74 36675 : if(tail_)
75 9380 : tail_->next_ = w;
76 : else
77 27295 : head_ = w;
78 36675 : tail_ = w;
79 36675 : }
80 :
81 : void
82 : splice_back(intrusive_list& other) noexcept
83 : {
84 : if(other.empty())
85 : return;
86 : if(tail_)
87 : {
88 : tail_->next_ = other.head_;
89 : other.head_->prev_ = tail_;
90 : tail_ = other.tail_;
91 : }
92 : else
93 : {
94 : head_ = other.head_;
95 : tail_ = other.tail_;
96 : }
97 : other.head_ = nullptr;
98 : other.tail_ = nullptr;
99 : }
100 :
101 : T*
102 11337 : pop_front() noexcept
103 : {
104 11337 : if(!head_)
105 1983 : return nullptr;
106 9354 : T* w = head_;
107 9354 : head_ = head_->next_;
108 9354 : if(head_)
109 28 : head_->prev_ = nullptr;
110 : else
111 9326 : tail_ = nullptr;
112 9354 : return w;
113 : }
114 :
115 : void
116 27321 : remove(T* w) noexcept
117 : {
118 27321 : if(w->prev_)
119 9323 : w->prev_->next_ = w->next_;
120 : else
121 17998 : head_ = w->next_;
122 27321 : if(w->next_)
123 35 : w->next_->prev_ = w->prev_;
124 : else
125 27286 : tail_ = w->prev_;
126 27321 : }
127 : };
128 :
129 : //------------------------------------------------
130 :
131 : /** An intrusive singly linked FIFO queue.
132 :
133 : This container provides O(1) push and pop operations for
134 : elements that derive from @ref node. Elements are not
135 : copied or moved; they are linked directly into the queue.
136 :
137 : Unlike @ref intrusive_list, this uses only a single `next_`
138 : pointer per node, saving memory at the cost of not supporting
139 : O(1) removal of arbitrary elements.
140 :
141 : @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
142 : */
143 : template<class T>
144 : class intrusive_queue
145 : {
146 : public:
147 : /** Base class for queue elements.
148 :
149 : Derive from this class to make a type usable with
150 : @ref intrusive_queue. The `next_` pointer is private
151 : and accessible only to the queue.
152 : */
153 : class node
154 : {
155 : friend class intrusive_queue;
156 :
157 : private:
158 : T* next_;
159 : };
160 :
161 : private:
162 : T* head_ = nullptr;
163 : T* tail_ = nullptr;
164 :
165 : public:
166 477 : intrusive_queue() = default;
167 :
168 : intrusive_queue(intrusive_queue&& other) noexcept
169 : : head_(other.head_)
170 : , tail_(other.tail_)
171 : {
172 : other.head_ = nullptr;
173 : other.tail_ = nullptr;
174 : }
175 :
176 : intrusive_queue(intrusive_queue const&) = delete;
177 : intrusive_queue& operator=(intrusive_queue const&) = delete;
178 : intrusive_queue& operator=(intrusive_queue&&) = delete;
179 :
180 : bool
181 1621059 : empty() const noexcept
182 : {
183 1621059 : return head_ == nullptr;
184 : }
185 :
186 : void
187 899315 : push(T* w) noexcept
188 : {
189 899315 : w->next_ = nullptr;
190 899315 : if(tail_)
191 561965 : tail_->next_ = w;
192 : else
193 337350 : head_ = w;
194 899315 : tail_ = w;
195 899315 : }
196 :
197 : void
198 314923 : splice(intrusive_queue& other) noexcept
199 : {
200 314923 : if(other.empty())
201 0 : return;
202 314923 : if(tail_)
203 304663 : tail_->next_ = other.head_;
204 : else
205 10260 : head_ = other.head_;
206 314923 : tail_ = other.tail_;
207 314923 : other.head_ = nullptr;
208 314923 : other.tail_ = nullptr;
209 : }
210 :
211 : T*
212 1014712 : pop() noexcept
213 : {
214 1014712 : if(!head_)
215 115397 : return nullptr;
216 899315 : T* w = head_;
217 899315 : head_ = head_->next_;
218 899315 : if(!head_)
219 32687 : tail_ = nullptr;
220 899315 : return w;
221 : }
222 : };
223 :
224 : } // namespace boost::corosio::detail
225 :
226 : #endif
|
