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