GCC Code Coverage Report

Directory: ./
File: libs/capy/include/boost/capy/core/intrusive_queue.hpp
Date: 2026-01-15 21:26:50
Exec Total Coverage
Lines: 33 33 100.0%
Functions: 9 9 100.0%
Branches: 10 10 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_QUEUE_HPP
11 #define BOOST_CAPY_INTRUSIVE_QUEUE_HPP
12
13 #include <boost/capy/detail/config.hpp>
14
15 namespace boost {
16 namespace capy {
17
18 /** An intrusive singly linked FIFO queue.
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 queue.
23
24 Unlike @ref intrusive_list, this uses only a single `next_`
25 pointer per node, saving memory at the cost of not supporting
26 O(1) removal of arbitrary elements.
27
28 @par Usage
29 @code
30 struct my_item : intrusive_queue<my_item>::node
31 {
32 // user data
33 };
34
35 using item_queue = intrusive_queue<my_item>;
36
37 my_item item;
38 item_queue q;
39 q.push(&item);
40 my_item* p = q.pop(); // p == &item
41 @endcode
42
43 @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
44
45 @see intrusive_list
46 */
47 template<class T>
48 class intrusive_queue
49 {
50 public:
51 /** Base class for queue elements.
52
53 Derive from this class to make a type usable with
54 @ref intrusive_queue. The `next_` pointer is private
55 and accessible only to the queue.
56 */
57 class node
58 {
59 friend class intrusive_queue;
60
61 private:
62 T* next_;
63 };
64
65 private:
66 T* head_ = nullptr;
67 T* tail_ = nullptr;
68
69 public:
70 /** Default constructor.
71
72 Creates an empty queue.
73
74 @post `empty() == true`
75 */
76 14 intrusive_queue() = default;
77
78 /** Move constructor.
79
80 Takes ownership of all elements from `other`,
81 leaving `other` empty.
82
83 @param other The queue to move from.
84
85 @post `other.empty() == true`
86 */
87 2 intrusive_queue(intrusive_queue&& other) noexcept
88 2 : head_(other.head_)
89 2 , tail_(other.tail_)
90 {
91 2 other.head_ = nullptr;
92 2 other.tail_ = nullptr;
93 2 }
94
95 intrusive_queue(intrusive_queue const&) = delete;
96 intrusive_queue& operator=(intrusive_queue const&) = delete;
97 intrusive_queue& operator=(intrusive_queue&&) = delete;
98
99 /** Return true if the queue is empty.
100
101 @return `true` if the queue contains no elements.
102 */
103 bool
104 161 empty() const noexcept
105 {
106 161 return head_ == nullptr;
107 }
108
109 /** Add an element to the back of the queue.
110
111 @param w Pointer to the element to add.
112
113 @pre `w` is not null and not already in a queue.
114 */
115 void
116 101 push(T* w) noexcept
117 {
118 101 w->next_ = nullptr;
119
2/2
✓ Branch 0 taken 71 times.
✓ Branch 1 taken 30 times.
 101 if(tail_)
120 71 tail_->next_ = w;
121 else
122 30 head_ = w;
123 101 tail_ = w;
124 101 }
125
126 /** Splice all elements from another queue to the back.
127
128 All elements from `other` are moved to the back of this
129 queue. After this call, `other` is empty.
130
131 @param other The queue to splice from.
132
133 @post `other.empty() == true`
134 */
135 void
136 4 splice(intrusive_queue& other) noexcept
137 {
138
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
 4 if(other.empty())
139 2 return;
140
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if(tail_)
141 1 tail_->next_ = other.head_;
142 else
143 1 head_ = other.head_;
144 2 tail_ = other.tail_;
145 2 other.head_ = nullptr;
146 2 other.tail_ = nullptr;
147 }
148
149 /** Remove and return the front element.
150
151 @return Pointer to the front element, or `nullptr`
152 if the queue is empty.
153 */
154 T*
155 118 pop() noexcept
156 {
157
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 101 times.
 118 if(!head_)
158 17 return nullptr;
159 101 T* w = head_;
160 101 head_ = head_->next_;
161
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 72 times.
 101 if(!head_)
162 29 tail_ = nullptr;
163 101 return w;
164 }
165 };
166
167 } // capy
168 } // boost
169
170 #endif
171