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