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_INTRUSIVE_LIST_HPP
11 : #define BOOST_CAPY_INTRUSIVE_LIST_HPP
12 :
13 : #include <boost/capy/detail/config.hpp>
14 :
15 : namespace boost {
16 : namespace capy {
17 :
18 : /** An intrusive doubly linked list.
19 :
20 : This container provides O(1) push and pop operations for
21 : elements that derive from @ref node. Elements are not
22 : copied or moved; they are linked directly into the list.
23 :
24 : @par Usage
25 : @code
26 : struct my_item : intrusive_list<my_item>::node
27 : {
28 : // user data
29 : };
30 :
31 : using item_list = intrusive_list<my_item>;
32 :
33 : my_item item;
34 : item_list q;
35 : q.push_back(&item);
36 : my_item* p = q.pop_front(); // p == &item
37 : @endcode
38 :
39 : @tparam T The element type. Must derive from `intrusive_list<T>::node`.
40 : */
41 : template<class T>
42 : class intrusive_list
43 : {
44 : public:
45 : /** Base class for list elements.
46 :
47 : Derive from this class to make a type usable with
48 : @ref intrusive_list. The `next_` and `prev_` pointers
49 : are private and accessible only to the list.
50 : */
51 : class node
52 : {
53 : friend class intrusive_list;
54 :
55 : private:
56 : T* next_;
57 : T* prev_;
58 : };
59 :
60 : private:
61 : T* head_ = nullptr;
62 : T* tail_ = nullptr;
63 :
64 : public:
65 : /** Default constructor.
66 :
67 : Creates an empty list.
68 :
69 : @post `empty() == true`
70 : */
71 : intrusive_list() = default;
72 :
73 : /** Move constructor.
74 :
75 : Takes ownership of all elements from `other`,
76 : leaving `other` empty.
77 :
78 : @param other The list to move from.
79 :
80 : @post `other.empty() == true`
81 : */
82 2 : intrusive_list(intrusive_list&& other) noexcept
83 2 : : head_(other.head_)
84 2 : , tail_(other.tail_)
85 : {
86 2 : other.head_ = nullptr;
87 2 : other.tail_ = nullptr;
88 2 : }
89 :
90 : intrusive_list(intrusive_list const&) = delete;
91 : intrusive_list& operator=(intrusive_list const&) = delete;
92 : intrusive_list& operator=(intrusive_list&&) = delete;
93 :
94 : /** Return true if the list is empty.
95 :
96 : @return `true` if the list contains no elements.
97 : */
98 : bool
99 36 : empty() const noexcept
100 : {
101 36 : return head_ == nullptr;
102 : }
103 :
104 : /** Add an element to the back of the list.
105 :
106 : @param w Pointer to the element to add.
107 :
108 : @pre `w` is not null and not already in a list.
109 : */
110 : void
111 30 : push_back(T* w) noexcept
112 : {
113 30 : w->next_ = nullptr;
114 30 : w->prev_ = tail_;
115 30 : if(tail_)
116 14 : tail_->next_ = w;
117 : else
118 16 : head_ = w;
119 30 : tail_ = w;
120 30 : }
121 :
122 : /** Splice all elements from another list to the back.
123 :
124 : All elements from `other` are moved to the back of this
125 : list. After this call, `other` is empty.
126 :
127 : @param other The list to splice from.
128 :
129 : @post `other.empty() == true`
130 : */
131 : void
132 4 : splice_back(intrusive_list& other) noexcept
133 : {
134 4 : if(other.empty())
135 2 : return;
136 2 : if(tail_)
137 : {
138 1 : tail_->next_ = other.head_;
139 1 : other.head_->prev_ = tail_;
140 1 : tail_ = other.tail_;
141 : }
142 : else
143 : {
144 1 : head_ = other.head_;
145 1 : tail_ = other.tail_;
146 : }
147 2 : other.head_ = nullptr;
148 2 : other.tail_ = nullptr;
149 : }
150 :
151 : /** Remove and return the front element.
152 :
153 : @return Pointer to the front element, or `nullptr`
154 : if the list is empty.
155 : */
156 : T*
157 29 : pop_front() noexcept
158 : {
159 29 : if(!head_)
160 4 : return nullptr;
161 25 : T* w = head_;
162 25 : head_ = head_->next_;
163 25 : if(head_)
164 12 : head_->prev_ = nullptr;
165 : else
166 13 : tail_ = nullptr;
167 25 : return w;
168 : }
169 :
170 : /** Remove a specific element from the list.
171 :
172 : Unlinks the given element from its current position
173 : in the list. The element must be a member of this list.
174 :
175 : @param w Pointer to the element to remove.
176 :
177 : @pre `w` is not null and is currently in this list.
178 : */
179 : void
180 5 : remove(T* w) noexcept
181 : {
182 5 : if(w->prev_)
183 2 : w->prev_->next_ = w->next_;
184 : else
185 3 : head_ = w->next_;
186 5 : if(w->next_)
187 2 : w->next_->prev_ = w->prev_;
188 : else
189 3 : tail_ = w->prev_;
190 5 : }
191 : };
192 :
193 : } // capy
194 : } // boost
195 :
196 : #endif
|
