include/boost/corosio/detail/ready_queue.hpp

100.0% Lines (48/0/48) 100.0% List of functions (12/0/12)

[ ] prev/next file

ready_queue.hpp

f(x) Functions (12)

Function Calls Lines Blocks

Line	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	3467393x	ready_is_continuation(std::uintptr_t e) noexcept
35		{
36	3467393x	return (e & ready_cont_bit) != 0;
37		}
38
39		/// Recover the scheduler_op from an op-tagged entry.
40		inline scheduler_op*
41	3242902x	ready_as_op(std::uintptr_t e) noexcept
42		{
43	3242902x	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	95725x	ready_as_cont(std::uintptr_t e) noexcept
49		{
50	95725x	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	831860x	static std::uintptr_t next_of(std::uintptr_t e) noexcept
80		{
81	831860x	if (ready_is_continuation(e))
82	23940x	return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved);
83	807920x	return ready_as_op(e)->q_next_;
84		}
85
86	1348920x	static void set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept
87		{
88	1348920x	if (ready_is_continuation(e))
89	47845x	ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt);
90		else
91	1301075x	ready_as_op(e)->q_next_ = nxt;
92	1348920x	}
93		BOOST_COROSIO_GCC_WARNING_POP
94
95	831860x	void push_entry(std::uintptr_t e) noexcept
96		{
97	831860x	set_next(e, 0);
98	831860x	if (tail_)
99	385775x	set_next(tail_, e);
100		else
101	446085x	head_ = e;
102	831860x	tail_ = e;
103	831860x	}
104
105		public:
106	4100x	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	2112863x	bool empty() const noexcept
120		{
121	2112863x	return head_ == 0;
122		}
123
124		/// Append a scheduler_op to the back of the queue.
125	807920x	void push(scheduler_op* op) noexcept
126		{
127	807920x	push_entry(std::bit_cast<std::uintptr_t>(op));
128	807920x	}
129
130		/// Append a continuation to the back of the queue.
131	23940x	void push(capy::continuation& c) noexcept
132		{
133	23940x	push_entry(std::bit_cast<std::uintptr_t>(&c) \| ready_cont_bit);
134	23940x	}
135
136		/// Move all entries of @p other to the back in O(1); @p other is emptied.
137	463887x	void splice(ready_queue& other) noexcept
138		{
139	463887x	if (other.empty())
140	34292x	return;
141	429595x	if (tail_)
142	131285x	set_next(tail_, other.head_);
143		else
144	298310x	head_ = other.head_;
145	429595x	tail_ = other.tail_;
146	429595x	other.head_ = 0;
147	429595x	other.tail_ = 0;
148		}
149
150		/// Remove and return the front entry as a tagged value, or 0 when empty.
151	1159955x	std::uintptr_t pop() noexcept
152		{
153	1159955x	auto e = head_;
154	1159955x	if (!e)
155	328095x	return 0;
156	831860x	head_ = next_of(e);
157	831860x	if (!head_)
158	314800x	tail_ = 0;
159	831860x	return e;
160		}
161		};
162
163		} // namespace boost::corosio::detail
164
165		#endif
166