include/boost/corosio/detail/ready_queue.hpp

100.0% Lines (47/47) 100.0% List of functions (12/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	2704613x	ready_is_continuation(std::uintptr_t e) noexcept
35		{
36	2704613x	return (e & ready_cont_bit) != 0;
37		}
38
39		/// Recover the scheduler_op from an op-tagged entry.
40		inline scheduler_op*
41	2534226x	ready_as_op(std::uintptr_t e) noexcept
42		{
43	2534226x	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	60370x	ready_as_cont(std::uintptr_t e) noexcept
49		{
50	60370x	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	648368x	next_of(std::uintptr_t e) noexcept
81		{
82	648368x	if (ready_is_continuation(e))
83	15095x	return std::bit_cast<std::uintptr_t>(ready_as_cont(e)->reserved);
84	633273x	return ready_as_op(e)->q_next_;
85		}
86
87		static void
88	1058145x	set_next(std::uintptr_t e, std::uintptr_t nxt) noexcept
89		{
90	1058145x	if (ready_is_continuation(e))
91	30180x	ready_as_cont(e)->reserved = std::bit_cast<void*>(nxt);
92		else
93	1027965x	ready_as_op(e)->q_next_ = nxt;
94	1058145x	}
95		BOOST_COROSIO_GCC_WARNING_POP
96
97		void
98	648368x	push_entry(std::uintptr_t e) noexcept
99		{
100	648368x	set_next(e, 0);
101	648368x	if (tail_)
102	290955x	set_next(tail_, e);
103		else
104	357413x	head_ = e;
105	648368x	tail_ = e;
106	648368x	}
107
108		public:
109	2137x	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	1874001x	bool empty() const noexcept { return head_ == 0; }
125
126		/// Append a scheduler_op to the back of the queue.
127	633273x	void push(scheduler_op* op) noexcept
128		{
129	633273x	push_entry(std::bit_cast<std::uintptr_t>(op));
130	633273x	}
131
132		/// Append a continuation to the back of the queue.
133	15095x	void push(capy::continuation& c) noexcept
134		{
135	15095x	push_entry(std::bit_cast<std::uintptr_t>(&c) \| ready_cont_bit);
136	15095x	}
137
138		/// Move all entries of @p other to the back in O(1); @p other is emptied.
139	369790x	void splice(ready_queue& other) noexcept
140		{
141	369790x	if (other.empty())
142	30920x	return;
143	338870x	if (tail_)
144	118822x	set_next(tail_, other.head_);
145		else
146	220048x	head_ = other.head_;
147	338870x	tail_ = other.tail_;
148	338870x	other.head_ = 0;
149	338870x	other.tail_ = 0;
150		}
151
152		/// Remove and return the front entry as a tagged value, or 0 when empty.
153	889304x	std::uintptr_t pop() noexcept
154		{
155	889304x	auto e = head_;
156	889304x	if (!e)
157	240936x	return 0;
158	648368x	head_ = next_of(e);
159	648368x	if (!head_)
160	238591x	tail_ = 0;
161	648368x	return e;
162		}
163		};
164
165		} // namespace boost::corosio::detail
166
167		#endif
168