include/boost/corosio/detail/timer_service.hpp

91.0% Lines (244/268) 100.0% List of functions (27/28) 66.4% Branches (93/140)

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

timer_service.hpp

f(x) Functions (28)

Function Calls Lines Branches Blocks

Line	Branch	Hits	Source Code
1			//
2			// Copyright (c) 2025 Vinnie Falco ([email protected])
3			// Copyright (c) 2026 Steve Gerbino
4			//
5			// Distributed under the Boost Software License, Version 1.0. (See accompanying
6			// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7			//
8			// Official repository: https://github.com/cppalliance/corosio
9			//
10
11			#ifndef BOOST_COROSIO_DETAIL_TIMER_SERVICE_HPP
12			#define BOOST_COROSIO_DETAIL_TIMER_SERVICE_HPP
13
14			#include <boost/corosio/detail/timer.hpp>
15			#include <boost/corosio/detail/scheduler.hpp>
16			#include <boost/corosio/detail/scheduler_op.hpp>
17			#include <boost/corosio/detail/intrusive.hpp>
18			#include <boost/corosio/detail/thread_local_ptr.hpp>
19			#include <boost/capy/error.hpp>
20			#include <boost/capy/ex/execution_context.hpp>
21			#include <boost/capy/ex/executor_ref.hpp>
22			#include <system_error>
23
24			#include <atomic>
25			#include <chrono>
26			#include <coroutine>
27			#include <cstddef>
28			#include <limits>
29			#include <mutex>
30			#include <stop_token>
31			#include <utility>
32			#include <vector>
33
34			namespace boost::corosio::detail {
35
36			struct scheduler;
37
38			/*
39			Timer Service
40			=============
41
42			Data Structures
43			---------------
44			waiter_node (defined in timer.hpp) holds per-waiter state:
45			coroutine handle, executor, error output, embedded
46			completion_op. Each concurrent co_await t.wait() embeds one
47			waiter_node in the awaitable on the suspended coroutine's
48			frame — waits perform no allocation.
49
50			timer::implementation holds per-timer state: expiry, heap
51			index, and the single published waiter. Each timer holds
52			at most one waiter; process_expired's local cross-timer drain
53			list still threads waiters through their intrusive hooks when
54			collecting several timers' waiters past the lock.
55
56			timer_service owns a min-heap of active timers and a free list
57			of recycled impls. The heap is ordered by expiry time; the
58			scheduler queries nearest_expiry() to set the epoll/timerfd
59			timeout.
60
61			Optimization Strategy
62			---------------------
63			1. Deferred heap insertion — expires_after() stores the expiry
64			but does not insert into the heap. Insertion happens in wait().
65			2. Thread-local impl cache — single-slot per-thread cache.
66			3. Frame-resident waiter_node with embedded completion_op —
67			eliminates heap allocation per wait/fire/cancel.
68			4. Cached nearest expiry — atomic avoids mutex in nearest_expiry().
69			5. might_have_pending_waits_ flag — skips lock when no wait issued.
70
71			Concurrency
72			-----------
73			stop_token callbacks can fire from any thread. The impl_
74			pointer on waiter_node is used as a "still in list" marker.
75			A waiter_node's storage is the suspended coroutine's frame:
76			every completion path must finish touching the node before
77			posting the continuation or destroying the handle.
78			*/
79
80			inline void timer_service_invalidate_cache() noexcept;
81
82			// timer_service class body — member function definitions are
83			// out-of-class (after implementation and waiter_node are complete)
84			class BOOST_COROSIO_DECL timer_service final
85			: public capy::execution_context::service
86			, public io_object::io_service
87			{
88			public:
89			using clock_type = std::chrono::steady_clock;
90			using time_point = clock_type::time_point;
91
92			/// Type-erased callback for earliest-expiry-changed notifications.
93			class callback
94			{
95		1944x	void* ctx_ = nullptr;
96		1944x	void (fn_)(void) = nullptr;
97
98			public:
99			/// Construct an empty callback.
100		5832x	callback() = default;
101
102			/// Construct a callback with the given context and function.
103		3888x	callback(void* ctx, void (fn)(void)) noexcept : ctx_(ctx), fn_(fn) {}
104
105			/// Return true if the callback is non-empty.
106			explicit operator bool() const noexcept
107			{
108			return fn_ != nullptr;
109			}
110
111			/// Invoke the callback.
112		8557x	void operator()() const
113			{
114	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 8557 times.	8557x	if (fn_)
115		8557x	fn_(ctx_);
116		8557x	}
117			};
118
119			private:
120			struct heap_entry
121			{
122			time_point time_;
123			timer::implementation* timer_;
124			};
125
126			scheduler* sched_ = nullptr;
127			BOOST_COROSIO_MSVC_WARNING_PUSH
128			BOOST_COROSIO_MSVC_WARNING_DISABLE(4251) // std:: members, dll-interface
129			mutable std::mutex mutex_;
130			std::vector<heap_entry> heap_;
131		1944x	timer::implementation* free_list_ = nullptr;
132			callback on_earliest_changed_;
133		1944x	bool shutting_down_ = false;
134			// Avoids mutex in nearest_expiry() and empty()
135		3888x	mutable std::atomic<std::int64_t> cached_nearest_ns_{
136		1944x	(std::numeric_limits<std::int64_t>::max)()};
137			BOOST_COROSIO_MSVC_WARNING_POP
138
139			public:
140			/// Construct the timer service bound to a scheduler.
141		9720x	inline timer_service(capy::execution_context&, scheduler& sched)
142		1944x	: sched_(&sched)
143		5832x	{
144		3888x	}
145
146			/// Return the associated scheduler.
147		17295x	inline scheduler& get_scheduler() noexcept
148			{
149		17295x	return *sched_;
150			}
151
152			/// Destroy the timer service.
153		5832x	~timer_service() override = default;
154
155			timer_service(timer_service const&) = delete;
156			timer_service& operator=(timer_service const&) = delete;
157
158			/// Register a callback invoked when the earliest expiry changes.
159		1944x	inline void set_on_earliest_changed(callback cb)
160			{
161		1944x	on_earliest_changed_ = cb;
162		1944x	}
163
164			/// Return true if no timers are in the heap.
165			inline bool empty() const noexcept
166			{
167			return cached_nearest_ns_.load(std::memory_order_acquire) ==
168			(std::numeric_limits<std::int64_t>::max)();
169			}
170
171			/// Return the nearest timer expiry without acquiring the mutex.
172		1568033x	inline time_point nearest_expiry() const noexcept
173			{
174		1568033x	auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
175	2/4 ✓ Branch 0 taken 1568033 times. ✗ Branch 1 not taken. ✓ Branch 2 taken 1568033 times. ✗ Branch 3 not taken.	1568033x	return time_point(time_point::duration(ns));
176			}
177
178			/// Cancel all pending timers and free cached resources.
179			inline void shutdown() override;
180
181			/// Construct a new timer implementation.
182			inline io_object::implementation* construct() override;
183
184			/// Destroy a timer implementation, cancelling pending waiters.
185			inline void destroy(io_object::implementation* p) override;
186
187			/// Cancel and recycle a timer implementation.
188			inline void destroy_impl(timer::implementation& impl);
189
190			/// Publish the timer's waiter and insert the timer into the heap.
191			inline void insert_waiter(timer::implementation& impl, waiter_node* w);
192
193			/// Cancel the timer's published waiter, if any.
194			inline void cancel_timer(timer::implementation& impl);
195
196			/// Cancel one specific waiter ( stop_token callback path ).
197			inline void cancel_waiter(waiter_node* w);
198
199			/// Complete all waiters whose timers have expired.
200			inline std::size_t process_expired();
201
202			private:
203		1649625x	inline void refresh_cached_nearest() noexcept
204			{
205	2/2 ✓ Branch 0 taken 17993 times. ✓ Branch 1 taken 1631632 times.	1649625x	auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
206		1631632x	: heap_[0].time_.time_since_epoch().count();
207		1649625x	cached_nearest_ns_.store(ns, std::memory_order_release);
208		1649625x	}
209
210			inline void remove_timer_impl(timer::implementation& impl);
211			inline void up_heap(std::size_t index);
212			inline void down_heap(std::size_t index);
213			inline void swap_heap(std::size_t i1, std::size_t i2);
214			};
215
216			// Thread-local cache avoids hot-path mutex acquisitions:
217			// single-slot impl cache, validated by comparing svc_. Cleared by
218			// timer_service_invalidate_cache() during shutdown.
219
220			inline thread_local_ptr<timer::implementation> tl_cached_impl;
221
222			// The POD TLS slot above never runs destructors, so a short-lived
223			// run() thread would leak its cached impl. Each push arms this
224			// owner, whose destructor frees the slot at thread exit. A cached
225			// entry is a quiescent heap object (nothing in the heap or free
226			// list) and deletion touches no service state, so it is safe after
227			// the owning service is gone (the stale-entry path in
228			// try_pop_tl_cache deletes the same way).
229			struct tl_cache_owner
230			{
231		134x	~tl_cache_owner()
232		67x	{
233	2/2 ✓ Branch 0 taken 46 times. ✓ Branch 1 taken 21 times.	67x	delete tl_cached_impl.get();
234		67x	tl_cached_impl.set(nullptr);
235		134x	}
236			};
237
238			inline void
239		9260x	arm_tl_cache_cleanup() noexcept
240			{
241	2/2 ✓ Branch 0 taken 9193 times. ✓ Branch 1 taken 67 times.	9260x	[[maybe_unused]] thread_local tl_cache_owner owner;
242		9260x	}
243
244			inline timer::implementation*
245		9342x	try_pop_tl_cache(timer_service* svc) noexcept
246			{
247		9342x	auto* impl = tl_cached_impl.get();
248	2/2 ✓ Branch 0 taken 398 times. ✓ Branch 1 taken 8944 times.	9342x	if (impl)
249			{
250		8944x	tl_cached_impl.set(nullptr);
251	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 8944 times.	8944x	if (impl->svc_ == svc)
252		8944x	return impl;
253			// Stale impl from a destroyed service
254		✗	delete impl;
255		✗	}
256		398x	return nullptr;
257		9342x	}
258
259			inline bool
260		9313x	try_push_tl_cache(timer::implementation* impl) noexcept
261			{
262	2/2 ✓ Branch 0 taken 54 times. ✓ Branch 1 taken 9259 times.	9313x	if (!tl_cached_impl.get())
263			{
264		9259x	arm_tl_cache_cleanup();
265		9259x	tl_cached_impl.set(impl);
266		9259x	return true;
267			}
268		54x	return false;
269		9313x	}
270
271			inline void
272		1944x	timer_service_invalidate_cache() noexcept
273			{
274	2/2 ✓ Branch 0 taken 1649 times. ✓ Branch 1 taken 295 times.	1944x	delete tl_cached_impl.get();
275		1944x	tl_cached_impl.set(nullptr);
276		1944x	}
277
278			// timer_service out-of-class member function definitions
279
280			inline void
281		1944x	timer_service::shutdown()
282			{
283		1944x	timer_service_invalidate_cache();
284		1944x	shutting_down_ = true;
285
286			// Snapshot impls and detach them from the heap so that
287			// coroutine-owned timer destructors (triggered by h.destroy()
288			// below) cannot re-enter remove_timer_impl() and mutate the
289			// vector during iteration.
290		1944x	std::vector<timer::implementation*> impls;
291	1/2 ✓ Branch 0 taken 1944 times. ✗ Branch 1 not taken.	1944x	impls.reserve(heap_.size());
292	2/2 ✓ Branch 0 taken 1944 times. ✓ Branch 1 taken 28 times.	1972x	for (auto& entry : heap_)
293			{
294		56x	entry.timer_->heap_index_.store(
295		28x	(std::numeric_limits<std::size_t>::max)(),
296			std::memory_order_relaxed);
297	1/2 ✓ Branch 0 taken 28 times. ✗ Branch 1 not taken.	28x	impls.push_back(entry.timer_);
298			}
299		1944x	heap_.clear();
300		3888x	cached_nearest_ns_.store(
301		1944x	(std::numeric_limits<std::int64_t>::max)(), std::memory_order_release);
302
303			// Cancel waiting timers. Each waiter called work_started()
304			// in implementation::wait(). On IOCP the scheduler shutdown
305			// loop exits when outstanding_work_ reaches zero, so we must
306			// call work_finished() here to balance it. On other backends
307			// this is harmless.
308	2/2 ✓ Branch 0 taken 28 times. ✓ Branch 1 taken 1944 times.	1972x	for (auto* impl : impls)
309			{
310	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 28 times.	28x	if (auto* w = std::exchange(impl->waiter_, nullptr))
311			{
312		28x	w->reset_stop_cb();
313		28x	auto h = std::exchange(w->h_, {});
314		28x	sched_->work_finished();
315			// Destroying the frame also ends the node's storage
316	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 28 times.	28x	if (h)
317	1/2 ✓ Branch 0 taken 28 times. ✗ Branch 1 not taken.	28x	h.destroy();
318		28x	}
319	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 28 times.	28x	delete impl;
320			}
321
322			// Delete free-listed impls
323	2/2 ✓ Branch 0 taken 52 times. ✓ Branch 1 taken 1944 times.	1996x	while (free_list_)
324			{
325		52x	auto* next = free_list_->next_free_;
326	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 52 times.	52x	delete free_list_;
327		52x	free_list_ = next;
328			}
329		1944x	}
330
331			inline io_object::implementation*
332		9340x	timer_service::construct()
333			{
334		9340x	timer::implementation* impl = try_pop_tl_cache(this);
335	2/2 ✓ Branch 0 taken 8942 times. ✓ Branch 1 taken 398 times.	9340x	if (impl)
336			{
337		8942x	impl->svc_ = this;
338			// Reset expiry_ too: a recycled impl must behave like a fresh
339			// one, whose default expiry reads as already elapsed
340		8942x	impl->expiry_ = {};
341		17884x	impl->heap_index_.store(
342		8942x	(std::numeric_limits<std::size_t>::max)(),
343			std::memory_order_relaxed);
344		8942x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
345	1/2 ✓ Branch 0 taken 8942 times. ✗ Branch 1 not taken.	8942x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
346		8942x	return impl;
347			}
348
349		398x	std::lock_guard lock(mutex_);
350	2/2 ✓ Branch 0 taken 396 times. ✓ Branch 1 taken 2 times.	398x	if (free_list_)
351			{
352		2x	impl = free_list_;
353		2x	free_list_ = impl->next_free_;
354		2x	impl->next_free_ = nullptr;
355		2x	impl->svc_ = this;
356	1/2 ✓ Branch 0 taken 2 times. ✗ Branch 1 not taken.	2x	impl->expiry_ = {};
357		4x	impl->heap_index_.store(
358		2x	(std::numeric_limits<std::size_t>::max)(),
359			std::memory_order_relaxed);
360		2x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
361	1/4 ✗ Branch 0 not taken. ✓ Branch 1 taken 2 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken.	2x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
362		2x	}
363			else
364			{
365	1/2 ✓ Branch 0 taken 396 times. ✗ Branch 1 not taken.	396x	impl = new timer::implementation(*this);
366			}
367		398x	return impl;
368		9340x	}
369
370			inline void
371		9340x	timer_service::destroy(io_object::implementation* p)
372			{
373			// During shutdown the drain loop owns every impl and deletes
374			// them directly. A frame destroyed by that loop can unwind a
375			// handle whose impl was freed in an earlier iteration (a
376			// timeout's parent frame owns the timeout timer while
377			// suspended on the inner delay's timer), so bail out before
378			// even downcasting the pointer.
379	2/2 ✓ Branch 0 taken 28 times. ✓ Branch 1 taken 9312 times.	9340x	if (shutting_down_)
380		28x	return;
381		9312x	destroy_impl(static_cast<timer::implementation&>(*p));
382		9340x	}
383
384			inline void
385		9314x	timer_service::destroy_impl(timer::implementation& impl)
386			{
387			// During shutdown the impl is owned by the shutdown loop.
388			// Re-entering here (from a coroutine-owned timer destructor
389			// triggered by h.destroy()) must not modify the heap or
390			// recycle the impl — shutdown deletes it directly.
391	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 9314 times.	9314x	if (shutting_down_)
392		✗	return;
393
394		9314x	cancel_timer(impl);
395
396	2/4 ✓ Branch 0 taken 9314 times. ✗ Branch 1 not taken. ✓ Branch 2 taken 9314 times. ✗ Branch 3 not taken.	18628x	if (impl.heap_index_.load(std::memory_order_relaxed) !=
397		9314x	(std::numeric_limits<std::size_t>::max)())
398			{
399		✗	std::lock_guard lock(mutex_);
400		✗	remove_timer_impl(impl);
401		✗	refresh_cached_nearest();
402		✗	}
403
404	2/2 ✓ Branch 0 taken 9260 times. ✓ Branch 1 taken 54 times.	9314x	if (try_push_tl_cache(&impl))
405		9260x	return;
406
407		54x	std::lock_guard lock(mutex_);
408		54x	impl.next_free_ = free_list_;
409		54x	free_list_ = &impl;
410		9314x	}
411
412			inline void
413		8672x	timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
414			{
415		8672x	bool notify = false;
416		8672x	bool lost_cancel = false;
417			{
418		8672x	std::lock_guard lock(mutex_);
419			// Grow before publishing anything, so the push_back below
420			// cannot throw: a failure here leaves the waiter untouched,
421			// the strong guarantee rearm_wait's recovery relies on.
422	2/2 ✓ Branch 0 taken 8356 times. ✓ Branch 1 taken 318 times.	17344x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
423	4/4 ✓ Branch 0 taken 8674 times. ✓ Branch 1 taken 2 times. ✓ Branch 2 taken 8674 times. ✓ Branch 3 taken 2 times.	17344x	(std::numeric_limits<std::size_t>::max)() &&
424		8674x	heap_.size() == heap_.capacity())
425	1/2 ✓ Branch 0 taken 318 times. ✗ Branch 1 not taken.	636x	heap_.reserve(
426	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 318 times.	318x	heap_.capacity() == 0 ? 16 : 2 * heap_.capacity());
427			// Publish: from here the waiter is visible to the fire path and
428			// to its own stop callback (impl_ non-null enables cancel_waiter).
429		8676x	w->impl_ = &impl;
430	4/4 ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 8674 times. ✓ Branch 2 taken 2 times. ✓ Branch 3 taken 8674 times.	17352x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
431		8676x	(std::numeric_limits<std::size_t>::max)())
432			{
433		8674x	impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
434	1/2 ✓ Branch 0 taken 8674 times. ✗ Branch 1 not taken.	8674x	heap_.push_back({impl.expiry_, &impl});
435	1/2 ✓ Branch 0 taken 8674 times. ✗ Branch 1 not taken.	8674x	up_heap(heap_.size() - 1);
436		8674x	notify =
437		8674x	(impl.heap_index_.load(std::memory_order_relaxed) == 0);
438		8674x	refresh_cached_nearest();
439		8674x	}
440	1/4 ✗ Branch 0 not taken. ✓ Branch 1 taken 8676 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken.	8676x	BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
441		8676x	impl.waiter_ = w;
442
443			// Lost-cancel re-check: a stop requested after the canceller was
444			// armed in wait() but before this publication found impl_ null
445			// and returned a no-op. Observe it now and undo the insertion.
446	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 8676 times.	8676x	if (w->token_->stop_requested())
447			{
448		✗	w->impl_ = nullptr;
449		✗	impl.waiter_ = nullptr;
450		✗	remove_timer_impl(impl);
451		✗	impl.might_have_pending_waits_.store(
452			false, std::memory_order_relaxed);
453		✗	refresh_cached_nearest();
454		✗	lost_cancel = true;
455		✗	notify = false; // insertion undone; nearest unchanged
456		✗	}
457		8676x	}
458	2/2 ✓ Branch 0 taken 119 times. ✓ Branch 1 taken 8557 times.	8676x	if (notify)
459		8557x	on_earliest_changed_();
460	1/2 ✓ Branch 0 taken 8676 times. ✗ Branch 1 not taken.	8676x	if (lost_cancel)
461			{
462		✗	w->ec_ = make_error_code(capy::error::canceled);
463		✗	sched_->post(&w->op_);
464		✗	}
465		8676x	}
466
467			inline void
468		9312x	timer_service::cancel_timer(timer::implementation& impl)
469			{
470	2/2 ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 9310 times.	9312x	if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
471		9310x	return;
472
473			// No unlocked already-done fast-out here: it would need the
474			// non-atomic waiter_ (a race with concurrent drains), and an
475			// index-only check is lifetime-unsafe because npos is stored
476			// before the drain finishes touching the impl. A stale-true
477			// flag is rare with the stateless API; the locked path below
478			// re-validates.
479
480		2x	waiter_node* canceled = nullptr;
481
482			{
483		2x	std::lock_guard lock(mutex_);
484	1/2 ✓ Branch 0 taken 2 times. ✗ Branch 1 not taken.	2x	remove_timer_impl(impl);
485		2x	canceled = std::exchange(impl.waiter_, nullptr);
486	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 2 times.	2x	if (canceled)
487		2x	canceled->impl_ = nullptr;
488			// Store false as the final touch of the impl under the lock so
489			// a pre-lock false-flag check trusts it unqualified.
490		2x	impl.might_have_pending_waits_.store(false, std::memory_order_relaxed);
491		2x	refresh_cached_nearest();
492		2x	}
493
494	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 2 times.	2x	if (canceled)
495			{
496		2x	canceled->ec_ = make_error_code(capy::error::canceled);
497		2x	sched_->post(&canceled->op_);
498		2x	}
499		9312x	}
500
501			inline void
502		2283x	timer_service::cancel_waiter(waiter_node* w)
503			{
504			{
505		2283x	std::lock_guard lock(mutex_);
506			// Already removed by another drain: cancel_timer,
507			// process_expired, or insert_waiter's lost-cancel recheck
508	1/2 ✓ Branch 0 taken 2283 times. ✗ Branch 1 not taken.	2283x	if (!w->impl_)
509		✗	return;
510		2283x	auto* impl = w->impl_;
511		2283x	w->impl_ = nullptr;
512		2283x	impl->waiter_ = nullptr;
513	1/2 ✓ Branch 0 taken 2283 times. ✗ Branch 1 not taken.	2283x	remove_timer_impl(*impl);
514		2283x	impl->might_have_pending_waits_.store(
515			false, std::memory_order_relaxed);
516		2283x	refresh_cached_nearest();
517		2283x	}
518
519		2283x	w->ec_ = make_error_code(capy::error::canceled);
520		2283x	sched_->post(&w->op_);
521		2283x	}
522
523			inline std::size_t
524		1638666x	timer_service::process_expired()
525			{
526		1638666x	intrusive_list<waiter_node> expired;
527
528			{
529		1638666x	std::lock_guard lock(mutex_);
530		1638666x	auto now = clock_type::now();
531
532	4/4 ✓ Branch 0 taken 15809 times. ✓ Branch 1 taken 1629218 times. ✓ Branch 2 taken 1638666 times. ✓ Branch 3 taken 6361 times.	1645027x	while (!heap_.empty() && heap_[0].time_ <= now)
533			{
534		6361x	timer::implementation* t = heap_[0].timer_;
535	1/2 ✓ Branch 0 taken 6361 times. ✗ Branch 1 not taken.	6361x	remove_timer_impl(*t);
536	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 6361 times.	6361x	if (auto* w = std::exchange(t->waiter_, nullptr))
537			{
538		6361x	w->impl_ = nullptr;
539		6361x	w->ec_ = {};
540		6361x	expired.push_back(w);
541		6361x	}
542		6361x	t->might_have_pending_waits_.store(
543			false, std::memory_order_relaxed);
544			}
545
546		1638666x	refresh_cached_nearest();
547		1638666x	}
548
549		1638666x	std::size_t count = 0;
550	2/2 ✓ Branch 0 taken 6361 times. ✓ Branch 1 taken 1638666 times.	1645027x	while (auto* w = expired.pop_front())
551			{
552		6361x	sched_->post(&w->op_);
553		6361x	++count;
554			}
555
556		1638666x	return count;
557		✗	}
558
559			inline void
560		8646x	timer_service::remove_timer_impl(timer::implementation& impl)
561			{
562		8646x	std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
563	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 8646 times.	8646x	if (index >= heap_.size())
564		✗	return; // Not in heap
565
566	2/2 ✓ Branch 0 taken 2560 times. ✓ Branch 1 taken 6086 times.	8646x	if (index == heap_.size() - 1)
567			{
568			// Last element, just pop
569		5120x	impl.heap_index_.store(
570		2560x	(std::numeric_limits<std::size_t>::max)(),
571			std::memory_order_relaxed);
572		2560x	heap_.pop_back();
573		2560x	}
574			else
575			{
576			// Swap with last and reheapify
577		6086x	swap_heap(index, heap_.size() - 1);
578		12172x	impl.heap_index_.store(
579		6086x	(std::numeric_limits<std::size_t>::max)(),
580			std::memory_order_relaxed);
581		6086x	heap_.pop_back();
582
583	3/4 ✓ Branch 0 taken 4 times. ✓ Branch 1 taken 6082 times. ✓ Branch 2 taken 4 times. ✗ Branch 3 not taken.	6086x	if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
584		✗	up_heap(index);
585			else
586		6086x	down_heap(index);
587			}
588		8646x	}
589
590			inline void
591		8674x	timer_service::up_heap(std::size_t index)
592			{
593	2/2 ✓ Branch 0 taken 8557 times. ✓ Branch 1 taken 6173 times.	14730x	while (index > 0)
594			{
595		6173x	std::size_t parent = (index - 1) / 2;
596	2/2 ✓ Branch 0 taken 117 times. ✓ Branch 1 taken 6056 times.	6173x	if (!(heap_[index].time_ < heap_[parent].time_))
597		117x	break;
598		6056x	swap_heap(index, parent);
599		6056x	index = parent;
600			}
601		8674x	}
602
603			inline void
604		6086x	timer_service::down_heap(std::size_t index)
605			{
606		6086x	std::size_t child = index * 2 + 1;
607	2/2 ✓ Branch 0 taken 6084 times. ✓ Branch 1 taken 6 times.	6090x	while (child < heap_.size())
608			{
609	1/4 ✗ Branch 0 not taken. ✓ Branch 1 taken 6 times. ✗ Branch 2 not taken. ✗ Branch 3 not taken.	6x	std::size_t min_child = (child + 1 == heap_.size() \|\|
610		✗	heap_[child].time_ < heap_[child + 1].time_)
611		6x	? child
612		✗	: child + 1;
613
614	2/2 ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 4 times.	6x	if (heap_[index].time_ < heap_[min_child].time_)
615		2x	break;
616
617		4x	swap_heap(index, min_child);
618		4x	index = min_child;
619		4x	child = index * 2 + 1;
620			}
621		6086x	}
622
623			inline void
624		12146x	timer_service::swap_heap(std::size_t i1, std::size_t i2)
625			{
626		12146x	heap_entry tmp = heap_[i1];
627		12146x	heap_[i1] = heap_[i2];
628		12146x	heap_[i2] = tmp;
629		12146x	heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
630		12146x	heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
631		12146x	}
632
633			// waiter_node's completion_op and canceller members are defined in
634			// timer.cpp alongside implementation::wait(), for the same reason
635			// wait() lives there (see below).
636
637			// timer::implementation::wait() is defined in timer.cpp, not here.
638			// It must be a non-inline definition in a translation unit that is
639			// always pulled into the link whenever detail::timer is used (every
640			// consumer needs timer's constructors from that same object file).
641			// An inline definition in this header would only be emitted in
642			// translation units that happen to also include this header, which
643			// is not guaranteed for every caller of wait_awaitable::await_suspend
644			// in timer.hpp (e.g. code that only reaches timer.hpp through
645			// delay.hpp, without transitively including a scheduler header).
646
647			// Free functions
648
649			inline timer_service&
650		1944x	get_timer_service(capy::execution_context& ctx, scheduler& sched)
651			{
652		1944x	return ctx.make_service<timer_service>(sched);
653			}
654
655			} // namespace boost::corosio::detail
656
657			#endif
658