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_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 183 : empty() const noexcept
105 : {
106 183 : 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 101 : if(tail_)
120 44 : tail_->next_ = w;
121 : else
122 57 : 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 4 : if(other.empty())
139 2 : return;
140 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 118 : if(!head_)
158 17 : return nullptr;
159 101 : T* w = head_;
160 101 : head_ = head_->next_;
161 101 : if(!head_)
162 56 : tail_ = nullptr;
163 101 : return w;
164 : }
165 : };
166 :
167 : } // capy
168 : } // boost
169 :
170 : #endif
|
