Up
# Module Timing_wheel_float

### Signature

##
include Core_kernel.Timing_wheel_intf.Timing_wheel with module Time = Time

##
include Core_kernel.Invariant.S1 with type
'a
t :=
'a
t

######
Implementation details

Timing wheel is implemented as a priority queue in which the keys are
non-negative integers corresponding to the intervals of time.

A timing wheel in which time is represented by `Time.t`

, i.e. a floating-point number
of seconds since the epoch.

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
```

type
'a
timing_wheel
=
'a t

type
'a
t_now
=
'a t

`<:sexp_of< _ t_now >>`

displays only `now t`

, not all the alarms.

module
Alarm
: sig .. end

module
Level_bits
: sig .. end

module
Config
: sig .. end

`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
is_empty : _ t -> bool

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

val
length : _ t -> int

`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)`

.

`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.

`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.

`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.

`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
```

.

`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
clear : _ t -> unit

`clear t`

removes all alarms from `t`

.

`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`

.

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