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

include/boost/corosio/detail/ready_queue.hpp

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