Module Core__.Timing_wheel_float

A timing wheel in which time is represented by Time.t, i.e., by a floating-point number of seconds since the epoch. This is a wrapper around Timing_wheel_ns, which is preferable both because it has better performance and because it avoids issues having to do with floating point (im)precision.

The implementation uses Timing_wheel_ns and rounds all Time.t values to the nearest microsecond before feeding them to the underlying timing wheel. Thus, it is possible that Time.( < ) (Alarm.at t (add t ~at a)) at, with the alarm's at being up to a microsecond earlier than requested. However, because the alarm precision of the underlying timing wheel is an integer number of microseconds, we are still guaranteed when an alarm fires that at < now t, i.e., the timing-wheel's clock is beyond the time requested for the alarm to fire.

Due to floating-point arithmetic, the guarantee that alarms don't fire too late needs to be weakened slightly to use >= rather than > . For all alarms a in t:

      Alarm.at a >= now t - alarm_precision t
include Core_kernel.Timing_wheel_ns_intf.Timing_wheel with module Time = Core__.Import_time.Time
type 'a t
include sig ... end
val sexp_of_t : ('a ‑> Base.Sexp.t) ‑> 'a t ‑> Base.Sexp.t
type 'a timing_wheel = 'a t
type 'a t_now = 'a t

<:sexp_of< _ t_now >> displays only now t, not all the alarms.

include sig ... end
val sexp_of_t_now : ('a ‑> Base.Sexp.t) ‑> 'a t_now ‑> Base.Sexp.t
module Alarm : sig ... end
include Core_kernel__.Import.Invariant.S1 with type a t := a t
type 'a t
module Level_bits : sig ... end
module Config : sig ... end
val create : config:Config.t ‑> start:Time.t ‑> 'a t

create ~config ~start creates a new timing wheel with current time start. create raises if start < Time.epoch. For a fixed level_bits, a smaller (i.e. more precise) alarm_precision decreases the representable range of times/keys and increases the constant factor for advance_clock.

val alarm_precision : _ t ‑> Time.Span.t

Accessors

val now : _ t ‑> Time.t
val start : _ t ‑> Time.t

One can think of a timing wheel as a set of alarms. Here are various container functions along those lines.

val is_empty : _ t ‑> Core_kernel__.Import.bool
val length : _ t ‑> Core_kernel__.Import.int
val iter : 'a t ‑> f:('a Alarm.t ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit
val interval_num : _ t ‑> Time.t ‑> Interval_num.t

interval_num t time returns the number of the interval that time is in, where 0 is the interval that starts at Time.epoch. interval_num raises if Time.( < ) time Time.epoch.

now_interval_num t equals interval_num t (now t).

val now_interval_num : _ t ‑> Interval_num.t
val interval_num_start : _ t ‑> Interval_num.t ‑> Time.t

interval_num_start t n is the start of the n'th interval in t, i.e. n * alarm_precision t after the epoch.

interval_start t time is the start of the half-open interval containing time, i.e.:

        interval_num_start t (interval_num t time)

interval_start raises in the same cases that interval_num does.

val interval_start : _ t ‑> Time.t ‑> Time.t
val advance_clock : 'a t ‑> to_:Time.t ‑> handle_fired:('a Alarm.t ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit

advance_clock t ~to_ ~handle_fired advances t's clock to to_. It fires and removes all alarms a in t with Time.(<) (Alarm.at t a) (interval_start t to_), applying handle_fired to each such a.

If to_ <= now t, then advance_clock does nothing.

advance_clock fails if to_ is too far in the future to represent.

Behavior is unspecified if handle_fired accesses t in any way other than Alarm functions.

val fire_past_alarms : 'a t ‑> handle_fired:('a Alarm.t ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit

fire_past_alarms t ~handle_fired fires and removes all alarms a in t with Time.( <= ) (Alarm.at t a) (now t), applying handle_fired to each such a.

fire_past_alarms visits all alarms in interval now_interval_num, to check their Alarm.at.

Behavior is unspecified if handle_fired accesses t in any way other than Alarm functions.

val alarm_upper_bound : _ t ‑> Time.t

alarm_upper_bound t returns the upper bound on an at that can be supplied to add. alarm_upper_bound t is not constant; its value increases as now t increases.

val add : 'a t ‑> at:Time.t ‑> 'a ‑> 'a Alarm.t

add t ~at a adds a new value a to t and returns an alarm that can later be supplied to remove the alarm from t. add raises if interval_num t at < now_interval_num t || at >= alarm_upper_bound t.

add_at_interval_num t ~at a is equivalent to add t ~at:(interval_num_start t at) a.

val add_at_interval_num : 'a t ‑> at:Interval_num.t ‑> 'a ‑> 'a Alarm.t
val mem : 'a t ‑> 'a Alarm.t ‑> Core_kernel__.Import.bool
val remove : 'a t ‑> 'a Alarm.t ‑> Core_kernel__.Import.unit

remove t alarm removes alarm from t. remove raises if not (mem t alarm).

val reschedule : 'a t ‑> 'a Alarm.t ‑> at:Time.t ‑> Core_kernel__.Import.unit

reschedule t alarm ~at mutates alarm so that it will fire at at, i.e. so that Alarm.at t alarm = at. reschedule raises if not (mem t alarm) or if at is an invalid time for t, in the same situations that add raises.

reschedule_at_interval_num t alarm ~at is equivalent to:

        reschedule t alarm ~at:(interval_num_start t at)
val reschedule_at_interval_num : 'a t ‑> 'a Alarm.t ‑> at:Interval_num.t ‑> Core_kernel__.Import.unit
val clear : _ t ‑> Core_kernel__.Import.unit

clear t removes all alarms from t.

val min_alarm_interval_num : _ t ‑> Interval_num.t Core_kernel__.Import.option

min_alarm_interval_num t is the minimum Alarm.interval_num of all alarms in t. min_alarm_interval_num_exn t is the same, except it raises if is_empty t.

val min_alarm_interval_num_exn : _ t ‑> Interval_num.t
val max_alarm_time_in_min_interval : 'a t ‑> Time.t Core_kernel__.Import.option

max_alarm_time_in_min_interval t returns the maximum Alarm.at over all alarms in t whose Alarm.interval_num is min_alarm_interval_num t.

max_alarm_time_in_min_interval_exn t is the same as max_alarm_time_in_min_interval, except that it raises if is_empty t.

This function is useful for advancing to the min_alarm_interval_num of a timing wheel and then calling fire_past_alarms to fire the alarms in that interval. That is useful when simulating time, to ensure that alarms are processed in order.

val max_alarm_time_in_min_interval_exn : 'a t ‑> Time.t
val next_alarm_fires_at : _ t ‑> Time.t Core_kernel__.Import.option

next_alarm_fires_at t returns the minimum time to which the clock can be advanced such that an alarm will fire, or None if t has no alarms. If next_alarm_fires_at t = Some next, then for the minimum alarm time min that occurs in t, it is guaranteed that: next - alarm_precision t <= min < next.

next_alarm_fires_at_exn is the same as next_alarm_fires_at, except that it raises if is_empty t.

val next_alarm_fires_at_exn : _ t ‑> Time.t
Implementation details

The rest of this interface is not intended to be used with Timing_wheel, but is a separate data structure used to implement Timing_wheel, and may find use elsewhere.

module Priority_queue : sig ... end

Timing wheel is implemented as a priority queue in which the keys are non-negative integers corresponding to the intervals of time. The priority queue is unlike a typical priority queue in that rather than having a "delete min" operation, it has a nondecreasing minimum allowed key, which corresponds to the current time, and an increase_min_allowed_key operation, which implements advance_clock. increase_min_allowed_key as a side effect removes all elements from the timing wheel whose key is smaller than the new minimum, which implements firing the alarms whose time has expired.