include/boost/corosio/detail/ready_queue.hpp

100.0% Lines (49 / 49) 100.0% 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 <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	3337851x	ready_is_continuation(void* e) noexcept
34		{
35	3337851x	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	1967542x	ready_as_op(void* e) noexcept
41		{
42		// NOLINTNEXTLINE(performance-no-int-to-ptr)
43		return reinterpret_cast<scheduler_op*>(
44	1967542x	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	1005534x	ready_as_cont(void* e) noexcept
50		{
51		// NOLINTNEXTLINE(performance-no-int-to-ptr)
52		return reinterpret_cast<capy::continuation*>(
53	1005534x	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		void* head_ = nullptr; // tagged first entry, nullptr when empty
71		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	748425x	static void* next_of(void* e) noexcept
82		{
83	748425x	if (ready_is_continuation(e))
84	251907x	return ready_as_cont(e)->reserved;
85	496518x	return ready_as_op(e)->q_next_;
86		}
87
88	1437358x	static void set_next(void* e, void* nxt) noexcept
89		{
90	1437358x	if (ready_is_continuation(e))
91	501720x	ready_as_cont(e)->reserved = nxt;
92		else
93	935638x	ready_as_op(e)->q_next_ = nxt;
94	1437358x	}
95		BOOST_COROSIO_GCC_WARNING_POP
96
97	748425x	void push_entry(void* e) noexcept
98		{
99	748425x	set_next(e, nullptr);
100	748425x	if (tail_)
101	346951x	set_next(tail_, e);
102		else
103	401474x	head_ = e;
104	748425x	tail_ = e;
105	748425x	}
106
107		public:
108	17160x	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	2079247x	bool empty() const noexcept
122		{
123	2079247x	return head_ == nullptr;
124		}
125
126		/// Append a scheduler_op to the back of the queue.
127	496518x	void push(scheduler_op* op) noexcept
128		{
129	496518x	push_entry(reinterpret_cast<void*>(op));
130	496518x	}
131
132		/// Append a continuation to the back of the queue.
133	251907x	void push(capy::continuation& c) noexcept
134		{
135	251907x	push_entry(
136		// NOLINTNEXTLINE(performance-no-int-to-ptr)
137		reinterpret_cast<void*>(
138	251907x	reinterpret_cast<std::uintptr_t>(&c) \| ready_cont_bit));
139	251907x	}
140
141		/// Move all entries of @p other to the back in O(1); @p other is emptied.
142	626496x	void splice(ready_queue& other) noexcept
143		{
144	626496x	if (other.empty())
145	262727x	return;
146	363769x	if (tail_)
147	341982x	set_next(tail_, other.head_);
148		else
149	21787x	head_ = other.head_;
150	363769x	tail_ = other.tail_;
151	363769x	other.head_ = nullptr;
152	363769x	other.tail_ = nullptr;
153		}
154
155		/// Remove and return the front entry as a tagged value, or nullptr when empty.
156	796137x	void* pop() noexcept
157		{
158	796137x	auto e = head_;
159	796137x	if (!e)
160	47712x	return nullptr;
161	748425x	head_ = next_of(e);
162	748425x	if (!head_)
163	59492x	tail_ = nullptr;
164	748425x	return e;
165		}
166		};
167
168		} // namespace boost::corosio::detail
169
170		#endif
171