GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 94 / 0 / 94
Functions: 100.0% 15 / 0 / 15
Branches: 100.0% 30 / 0 / 30
libs/capy/include/boost/capy/detail/intrusive.hpp
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_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
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 16 times.
 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
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
 4 if(other.empty())
87 2 return;
88
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
 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
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 25 times.
 29 if(!head_)
107 4 return nullptr;
108 25 T* w = head_;
109 25 head_ = head_->next_;
110
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 13 times.
 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
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 5 if(w->prev_)
121 2 w->prev_->next_ = w->next_;
122 else
123 3 head_ = w->next_;
124
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 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 249 empty() const noexcept
184 {
185 249 return head_ == nullptr;
186 }
187
188 void
189 142 push(T* w) noexcept
190 {
191 142 w->next_ = nullptr;
192
4/4
boost::capy::detail::intrusive_queue<boost::capy::detail::queue_item>::push(boost::capy::detail::queue_item*):
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 10 times.
boost::capy::detail::intrusive_queue<boost::capy::thread_pool::impl::work>::push(boost::capy::thread_pool::impl::work*):
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 44 times.
 142 if(tail_)
193 88 tail_->next_ = w;
194 else
195 54 head_ = w;
196 142 tail_ = w;
197 142 }
198
199 void
200 4 splice(intrusive_queue& other) noexcept
201 {
202
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
 4 if(other.empty())
203 2 return;
204
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
 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 201 pop() noexcept
215 {
216
4/4
boost::capy::detail::intrusive_queue<boost::capy::detail::queue_item>::pop():
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 18 times.
boost::capy::detail::intrusive_queue<boost::capy::thread_pool::impl::work>::pop():
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 124 times.
 201 if(!head_)
217 59 return nullptr;
218 142 T* w = head_;
219 142 head_ = head_->next_;
220
4/4
boost::capy::detail::intrusive_queue<boost::capy::detail::queue_item>::pop():
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
boost::capy::detail::intrusive_queue<boost::capy::thread_pool::impl::work>::pop():
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 80 times.
 142 if(!head_)
221 53 tail_ = nullptr;
222 142 return w;
223 }
224 };
225
226 } // detail
227 } // capy
228 } // boost
229
230 #endif
231