1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
//! This crate provides a low-level event timer implementation //! based on hierarchical hash wheels. //! //! The APIs in the crate are offered at three different levels of abstraction, //! listed below from lowest to highest. //! //! # 1 – Single Wheel //! The fundamental abstraction of this crate a single hash wheel with 256 slots //! addressed with a single byte. Each slot stores a list of a generic event type. //! The whole wheel can be "ticked" causing entries in the slots that are being moved over //! to expire. With every tick, all expired event entries are returned for handling. //! For more details see the [byte_wheel](wheels::byte_wheel) module. //! //! # 2 – Hierachical Wheel //! Combining four byte wheels we get a hierachical timer that can represent timeouts //! up to [`u32::MAX`](std::u32::MAX) time units into the future. //! In order to support timeouts of up to [`u64::MAX`](std::u64::MAX) time units, //! our implementations also come with an overflow list, which stores all timers that didn't fit //! into any slot in the four wheels. Addition into this list happens in (amortised) constant time //! but movement from the list into the timer array is linear in the number of overflow items. //! Our design assumed that the vast majority of timers are going be scheduled less than //! [`u32::MAX`](std::u32::MAX) time units into the future. However, as movement from the overflow list //! still happens at a rate of over 6mio entries per second (on a 2019 16"MBP) for most applications //! there should be no large issues even if this assumption is not correct. //! //! This crate provides two variant implementations of this four level wheel structure: //! //! - The [quad_wheel::QuadWheelWithOverflow](wheels::quad_wheel::QuadWheelWithOverflow) corresponds directly to the implementation described above. //! - The [cancellable::QuadWheelWithOverflow](wheels::cancellable::QuadWheelWithOverflow) additionally supports the cancellation of outstanding timers //! before they expire. In order to do so, however, it requires the generic timer entry type to provide a unique identifier field. It also uses //! [Rc](std::rc::Rc) internally to avoid double storing the actual entry, which makes it (potentialy) unsuitable for situations where the timer must //! be able to move threads (since Rc](std::rc::Rc) is not `Send`). //! //! # 3 – High Level APIs //! This crate also provides two high levels APIs that can either be used directly or can be seen as examples //! of how to use the lower level APIs in an application. //! //! Bother higher level APIs also offer built-in support for periodically repeating timers, in addition to the normal timers //! which are schedulled once and discarded once expired. //! //! ## Simulation Timer //! The [simulation](simulation) module provides an implementation for an event timer used to drive a discrete event simulation. //! Its particular feature is that it can skip quickly through periods where no events are schedulled as it doesn't track real time, //! but rather provides the rate at which the simulation proceeds. //! //! ## Thread Timer //! The [thread_timer](thread_timer) module provides a timer for real-time event schedulling with millisecond accuracy. //! It runs on its own dedicated thread and uses a shareable handle called a `TimerRef` for communication with other threads. #![deny(missing_docs)] use std::{hash::Hash, time::Duration}; pub mod simulation; pub mod wheels; use wheels::{cancellable::CancellableTimerEntry, TimerEntryWithDelay}; mod timers; pub use self::timers::*; #[cfg(feature = "thread-timer")] pub mod thread_timer; #[cfg(feature = "uuid-extras")] mod uuid_extras; #[cfg(feature = "uuid-extras")] pub use self::uuid_extras::*; /// Errors encounted by a timer implementation #[derive(Debug)] pub enum TimerError<EntryType> { /// The timeout with the given id was not found NotFound, /// The timout has already expired Expired(EntryType), } /// A simple implementation of a timer entry that only stores its own unique id and the original delay #[derive(Debug)] pub struct IdOnlyTimerEntry<I> { /// The unique identifier part of the entry pub id: I, /// The delay that this entry is to be schedulled with (i.e., expire after) pub delay: Duration, } impl<I> IdOnlyTimerEntry<I> { /// Create a new timer entry from the id and the delay after which it should expire pub fn new(id: I, delay: Duration) -> Self { IdOnlyTimerEntry { id, delay } } } impl<I> CancellableTimerEntry for IdOnlyTimerEntry<I> where I: Hash + Clone + Eq + std::fmt::Debug, { type Id = I; fn id(&self) -> &Self::Id { &self.id } } impl<I> TimerEntryWithDelay for IdOnlyTimerEntry<I> where I: Hash + Clone + Eq + std::fmt::Debug, { fn delay(&self) -> Duration { self.delay } } /// A module with some convenince functions for writing timer tests #[cfg(test)] pub mod test_helpers { use std::time::Duration; /// Produce a duration corresponding to the i:th Fibonacci number /// /// Good for testing timer implementations at large a variety of timeout delays. pub fn fib_time(mut i: usize) -> Duration { if i == 0 { Duration::from_millis(0) } else if i == 1 { Duration::from_millis(1) } else { let mut fminus2: u64 = 0u64; let mut fminus1: u64 = 1u64; while i >= 2 { let fi = fminus2 + fminus1; i -= 1; fminus2 = fminus1; fminus1 = fi; } Duration::from_millis(fminus1) } } }