Index/include / boost / corosio / detail / ready_queue.hpp

include/boost/corosio/detail/ready_queue.hpp

100.0% Lines (53/53) 100.0% List of functions (12/12) 100.0% Branches (14/14)
[ ] prev/next file
ready_queue.hpp
f(x) Functions (12)
Function Calls Lines Branches Blocks
boost::corosio::detail::ready_is_continuation(unsigned long) :34 9598062x 100.0% – 100.0% boost::corosio::detail::ready_as_op(unsigned long) :41 9286701x 100.0% – 100.0% boost::corosio::detail::ready_as_cont(unsigned long) :48 98483x 100.0% – 100.0% boost::corosio::detail::ready_queue::next_of(unsigned long) :79 2358647x 100.0% 100.0% 100.0% boost::corosio::detail::ready_queue::set_next(unsigned long, unsigned long) :86 3677113x 100.0% 100.0% 100.0% boost::corosio::detail::ready_queue::push_entry(unsigned long) :95 2358647x 100.0% 100.0% 100.0% boost::corosio::detail::ready_queue::ready_queue() :106 4156858x 100.0% – 100.0% boost::corosio::detail::ready_queue::empty() const :119 5843117x 100.0% – 100.0% boost::corosio::detail::ready_queue::push(boost::corosio::detail::scheduler_op*) :125 2334018x 100.0% – 100.0% boost::corosio::detail::ready_queue::push(boost::capy::continuation&) :131 24627x 100.0% – 100.0% boost::corosio::detail::ready_queue::splice(boost::corosio::detail::ready_queue&) :137 1202529x 100.0% 100.0% 100.0% boost::corosio::detail::ready_queue::pop() :151 3351724x 100.0% 100.0% 100.0%
Line Branch TLA Hits Source Code
1 //
2 // Copyright (c) 2026 Steve Gerbino
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/corosio
8 //
9
10 #ifndef BOOST_COROSIO_DETAIL_READY_QUEUE_HPP
11 #define BOOST_COROSIO_DETAIL_READY_QUEUE_HPP
12
13 #include <boost/corosio/detail/scheduler_op.hpp>
14 #include <boost/capy/continuation.hpp>
15
16 #include <bit>
17 #include <cstdint>
18
19 namespace boost::corosio::detail {
20
21 // A queue entry is a tagged pointer: low bit selects the node kind, the rest
22 // is the address. We steal a LOW bit (guaranteed zero by alignment), never a
23 // high bit (which would depend on a fragile platform canonical-address
24 // assumption). Both node types are >= 8-aligned, so the low 3 bits are free.
25 static_assert(alignof(scheduler_op) >= 2);
26 static_assert(alignof(capy::continuation) >= 2);
27 static_assert(sizeof(void*) == sizeof(std::uintptr_t));
28 static_assert(sizeof(capy::continuation::reserved) >= sizeof(void*));
29
30 inline constexpr std::uintptr_t ready_cont_bit = 1;
31
32 /// Return true if a queue entry refers to a continuation (vs a scheduler_op).
33 inline bool
34 9598062x ready_is_continuation(std::uintptr_t e) noexcept
35 {
36 9598062x return (e & ready_cont_bit) != 0;
37 }
38
39 /// Recover the scheduler_op from an op-tagged entry.
40 inline scheduler_op*
41 9286701x ready_as_op(std::uintptr_t e) noexcept
42 {
43 9286701x return std::bit_cast<scheduler_op*>(e & ~ready_cont_bit);
44 }
45
46 /// Recover the continuation from a continuation-tagged entry.
47 inline capy::continuation*
48 98483x ready_as_cont(std::uintptr_t e) noexcept
49 {
50 98483x return std::bit_cast<capy::continuation*>(e & ~ready_cont_bit);
51 }
52
53 /** A unified intrusive FIFO of scheduler_ops and continuations.
54
55 Carries both completion handlers (`scheduler_op`, dispatched via
56 `(*op)()`) and posted coroutine resumptions (`capy::continuation`,
57 dispatched via `h.resume()`) in one ordered queue, with no per-entry
58 allocation. The next-link lives in the node: `scheduler_op::q_next_`
59 for ops, `capy::continuation::reserved` for continuations.
60
61 @par Thread Safety
62 Not thread-safe; external synchronization required (the schedulers
63 hold their dispatch mutex while touching it).
64 */
65 class ready_queue
66 {
67 2078429x std::uintptr_t head_ = 0; // tagged first entry, 0 when empty
68 2078429x std::uintptr_t tail_ = 0; // tagged last entry, 0 when empty
69
70 // Read a node's next-link by value. A continuation's link lives in its
71 // void* `reserved` slot; bit_cast keeps us from forming a uintptr_t
72 // lvalue over that void* object (which would violate strict aliasing).
73 //
74 // GCC 12/13 false-positive: when inlining proves an entry refers to a
75 // continuation, -Warray-bounds still diagnoses the untaken scheduler_op
76 // branch against the smaller object. Fixed in GCC 14.
77 BOOST_COROSIO_GCC_WARNING_PUSH
78 BOOST_COROSIO_GCC_WARNING_DISABLE("-Warray-bounds")
79 2358647x static std::uintptr_t next_of(std::uintptr_t e) noexcept
80 {
81
2/2
✓ Branch 0 taken 24629 times.
✓ Branch 1 taken 2334018 times.
 2358647x if (ready_is_continuation(e))
82 24629x return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved);
83 2334018x return ready_as_op(e)->q_next_;
84 2358647x }
85
86 3677113x static void set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept
87 {
88
2/2
✓ Branch 0 taken 49231 times.
✓ Branch 1 taken 3627882 times.
 3677113x if (ready_is_continuation(e))
89 49231x ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt);
90 else
91 3627882x ready_as_op(e)->q_next_ = nxt;
92 3677113x }
93 BOOST_COROSIO_GCC_WARNING_POP
94
95 2358647x void push_entry(std::uintptr_t e) noexcept
96 {
97 2358647x set_next(e, 0);
98
2/2
✓ Branch 0 taken 1108992 times.
✓ Branch 1 taken 1249655 times.
 2358647x if (tail_)
99 1108992x set_next(tail_, e);
100 else
101 1249655x head_ = e;
102 2358647x tail_ = e;
103 2358647x }
104
105 public:
106 6235287x ready_queue() = default;
107
108 ready_queue(ready_queue&& o) noexcept : head_(o.head_), tail_(o.tail_)
109 {
110 o.head_ = 0;
111 o.tail_ = 0;
112 }
113
114 ready_queue(ready_queue const&) = delete;
115 ready_queue& operator=(ready_queue const&) = delete;
116 ready_queue& operator=(ready_queue&&) = delete;
117
118 /// Return true if the queue holds no entries.
119 5843117x bool empty() const noexcept
120 {
121 5843117x return head_ == 0;
122 }
123
124 /// Append a scheduler_op to the back of the queue.
125 2334018x void push(scheduler_op* op) noexcept
126 {
127 2334018x push_entry(std::bit_cast<std::uintptr_t>(op));
128 2334018x }
129
130 /// Append a continuation to the back of the queue.
131 24627x void push(capy::continuation& c) noexcept
132 {
133 24627x push_entry(std::bit_cast<std::uintptr_t>(&c) | ready_cont_bit);
134 24627x }
135
136 /// Move all entries of @p other to the back in O(1); @p other is emptied.
137 1202529x void splice(ready_queue& other) noexcept
138 {
139
2/2
✓ Branch 0 taken 33465 times.
✓ Branch 1 taken 1169064 times.
 1202529x if (other.empty())
140 33465x return;
141
2/2
✓ Branch 0 taken 209479 times.
✓ Branch 1 taken 959585 times.
 1169064x if (tail_)
142 209479x set_next(tail_, other.head_);
143 else
144 959585x head_ = other.head_;
145 1169064x tail_ = other.tail_;
146 1169064x other.head_ = 0;
147 1169064x other.tail_ = 0;
148 1202529x }
149
150 /// Remove and return the front entry as a tagged value, or 0 when empty.
151 3351724x std::uintptr_t pop() noexcept
152 {
153 3351724x auto e = head_;
154
2/2
✓ Branch 0 taken 2358647 times.
✓ Branch 1 taken 993077 times.
 3351724x if (!e)
155 993077x return 0;
156 2358647x head_ = next_of(e);
157
2/2
✓ Branch 0 taken 1318471 times.
✓ Branch 1 taken 1040176 times.
 2358647x if (!head_)
158 1040176x tail_ = 0;
159 2358647x return e;
160 3351724x }
161 };
162
163 } // namespace boost::corosio::detail
164
165 #endif
166