GCC Code Coverage Report

Directory: ./
File: libs/capy/include/boost/capy/core/intrusive_list.hpp
Date: 2026-01-15 23:24:40
Exec Total Coverage
Lines: 44 44 100.0%
Functions: 6 6 100.0%
Branches: 14 14 100.0%
Line Branch Exec Source
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
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 16 times.
 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
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
 4 if(other.empty())
135 2 return;
136
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 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
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 25 times.
 29 if(!head_)
160 4 return nullptr;
161 25 T* w = head_;
162 25 head_ = head_->next_;
163
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 13 times.
 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
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 5 if(w->prev_)
183 2 w->prev_->next_ = w->next_;
184 else
185 3 head_ = w->next_;
186
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 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
197