include/boost/corosio/detail/ready_queue.hpp

95.7% Lines (44/46) 100.0% List of functions (11/11) 85.7% Branches (12/14)

[ ] prev/next file n p prev/next uncovered line

ready_queue.hpp

f(x) Functions (11)

Function Calls Lines Branches Blocks

Line	Branch	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		21x	ready_is_continuation(std::uintptr_t e) noexcept
35			{
36		21x	return (e & ready_cont_bit) != 0;
37			}
38
39			/// Recover the scheduler_op from an op-tagged entry.
40			inline scheduler_op*
41		21x	ready_as_op(std::uintptr_t e) noexcept
42			{
43		21x	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		4x	ready_as_cont(std::uintptr_t e) noexcept
49			{
50		4x	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			std::uintptr_t head_ = 0; // tagged first entry, 0 when empty
68			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			static std::uintptr_t
80		7x	next_of(std::uintptr_t e) noexcept
81			{
82	2/2 ✓ Branch 3 → 4 taken 1 time. ✓ Branch 3 → 6 taken 6 times.	7x	if (ready_is_continuation(e))
83		1x	return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved);
84		6x	return ready_as_op(e)->q_next_;
85			}
86
87			static void
88		11x	set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept
89			{
90	2/2 ✓ Branch 3 → 4 taken 2 times. ✓ Branch 3 → 7 taken 9 times.	11x	if (ready_is_continuation(e))
91		2x	ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt);
92			else
93		9x	ready_as_op(e)->q_next_ = nxt;
94		11x	}
95			BOOST_COROSIO_GCC_WARNING_POP
96
97			void
98		7x	push_entry(std::uintptr_t e) noexcept
99			{
100		7x	set_next(e, 0);
101	2/2 ✓ Branch 3 → 4 taken 3 times. ✓ Branch 3 → 5 taken 4 times.	7x	if (tail_)
102		3x	set_next(tail_, e);
103			else
104		4x	head_ = e;
105		7x	tail_ = e;
106		7x	}
107
108			public:
109			ready_queue() = default;
110
111			ready_queue(ready_queue&& o) noexcept
112			: head_(o.head_)
113			, tail_(o.tail_)
114			{
115			o.head_ = 0;
116			o.tail_ = 0;
117			}
118
119			ready_queue(ready_queue const&) = delete;
120			ready_queue& operator=(ready_queue const&) = delete;
121			ready_queue& operator=(ready_queue&&) = delete;
122
123			/// Return true if the queue holds no entries.
124		5x	bool empty() const noexcept { return head_ == 0; }
125
126			/// Append a scheduler_op to the back of the queue.
127		6x	void push(scheduler_op* op) noexcept
128			{
129		6x	push_entry(std::bit_cast<std::uintptr_t>(op));
130		6x	}
131
132			/// Append a continuation to the back of the queue.
133		1x	void push(capy::continuation& c) noexcept
134			{
135		1x	push_entry(std::bit_cast<std::uintptr_t>(&c) \| ready_cont_bit);
136		1x	}
137
138			/// Move all entries of @p other to the back in O(1); @p other is emptied.
139		1x	void splice(ready_queue& other) noexcept
140			{
141	1/2 ✗ Branch 3 → 4 not taken. ✓ Branch 3 → 5 taken 1 time.	1x	if (other.empty())
142		✗	return;
143	1/2 ✓ Branch 5 → 6 taken 1 time. ✗ Branch 5 → 7 not taken.	1x	if (tail_)
144		1x	set_next(tail_, other.head_);
145			else
146		✗	head_ = other.head_;
147		1x	tail_ = other.tail_;
148		1x	other.head_ = 0;
149		1x	other.tail_ = 0;
150			}
151
152			/// Remove and return the front entry as a tagged value, or 0 when empty.
153		9x	std::uintptr_t pop() noexcept
154			{
155		9x	auto e = head_;
156	2/2 ✓ Branch 2 → 3 taken 2 times. ✓ Branch 2 → 4 taken 7 times.	9x	if (!e)
157		2x	return 0;
158		7x	head_ = next_of(e);
159	2/2 ✓ Branch 5 → 6 taken 3 times. ✓ Branch 5 → 7 taken 4 times.	7x	if (!head_)
160		3x	tail_ = 0;
161		7x	return e;
162			}
163			};
164
165			} // namespace boost::corosio::detail
166
167			#endif
168