# Module type Timing_wheel_intf.Timing_wheel

    module type Timing_wheel = sig .. end

    module Time: Timing_wheel_intf.Timing_wheel_time

    type 'a 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 Interval_num: Timing_wheel_intf.Interval_num

    module Alarm: sig .. end

    include Invariant.S1

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

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 : 'a t -> Time.Span.t

Accessors

    val now : 'a t -> Time.t

    val start : 'a t -> Time.t

    val is_empty : 'a t -> bool

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

    val length : 'a t -> int

    val iter : 'a t ->
           f:('a Alarm.t -> unit) -> unit

    val interval_num : 'a t ->
           Time.t -> Timing_wheel_intf.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 `start`. `interval_num` raises if `time` is too far in the past or future to represent.

`now_interval_num t` equals `interval_num t (now t)`.

    val now_interval_num : 'a t -> Timing_wheel_intf.Interval_num.t

    val interval_num_start : 'a t ->
           Timing_wheel_intf.Interval_num.t -> Time.t

`interval_num_start t n` is the start of the `n`'th interval in `t`, i.e.:

            start t + n * alarm_precision t

`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 : 'a t -> Time.t -> Time.t

    val advance_clock : 'a t ->
           to_:Time.t ->
           handle_fired:('a Alarm.t -> unit) -> 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 -> unit) -> 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 : 'a 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:Timing_wheel_intf.Interval_num.t ->
           'a -> 'a Alarm.t

    val mem : 'a t ->
           'a Alarm.t -> bool

    val remove : 'a t ->
           'a Alarm.t -> 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 -> 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:Timing_wheel_intf.Interval_num.t -> unit

    val clear : 'a t -> unit

`clear t` removes all alarms from `t`.

    val next_alarm_fires_at : 'a t -> Time.t 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`.

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

    val sexp_of_t : ('a -> Sexplib.Sexp.t) ->
           'a t -> Sexplib.Sexp.t

    val sexp_of_t_now : ('a -> Sexplib.Sexp.t) ->
           'a t_now -> Sexplib.Sexp.t

`<:sexp_of< _ t_now >>` displays only `now t`, not all the alarms.
`null ()` returns an alarm `t` such that `not (mem timing_wheel t)` for all `timing_wheel`s.
All `Alarm` functions will raise if `not (Timing_wheel.mem timing_wheel t)`.
The timing-wheel implementation uses an array of "levels", where level `i` is an array of length `2^b_i`, where the `b_i` are the "level bits" specified via `Level_bits.create_exn [b_0, b_1; ...]`.

A timing wheel can handle approximately `2 ** num_bits t` intervals/keys beyond the current minimum time/key, where `num_bits t = b_0 + b_1 + ...`.

One can use a `Level_bits.t` to trade off run time and space usage of a timing wheel. For a fixed `num_bits`, as the number of levels increases, the length of the levels decreases and the timing wheel uses less space, but the constant factor for the running time of `add` and `increase_min_allowed_key` increases.
`max_num_bits` is how many bits in a key the timing wheel can use, i.e. 61. We subtract 3 for the bits in the word that we won't use:

- for the tag bit
- for negative numbers
- so we can do arithmetic around the bound without worrying about overflow

In `create_exn bits`, it is an error if any of the `b_i` in `bits` has `b_i <= 0`, or if the sum of the `b_i` in `bits` is greater than `max_num_bits`.
`default` returns the default value of `level_bits` used by `Timing_wheel.create` and `Timing_wheel.Priority_queue.create`.

              default = [11; 10; 10; 10; 10; 10]

This default uses 61 bits, i.e. `max_num_bits`, and less than 10k words of memory.
`num_bits t` is the sum of the `b_i` in `t`.
`create` raises if `alarm_precision <= 0`.
accessors
`default` is `create ()`.
`durations t` returns the durations of the levels in `t`
`create ~config ~start` creates a new timing wheel with current time `start`.

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`.
Accessors
One can think of a timing wheel as a set of alarms. Here are various container functions along those lines.
`interval_num t time` returns the number of the interval that `time` is in, where `0` is the interval that starts at `start`. `interval_num` raises if `time` is too far in the past or future to represent.

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

            start t + n * alarm_precision t

`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.
`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.
`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`.
`remove t alarm` removes `alarm` from `t`. `remove` raises if `not (mem t alarm)`.
`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)

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

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

Adding elements to and removing elements from a timing wheel takes constant time, unlike a heap-based priority queue which takes log(N), where N is the number of elements in the heap. `increase_min_allowed_key` takes time proportional to the amount of increase in the min-allowed key, as compared to log(N) for a heap. It is these performance differences that motivate the existence of timing wheels and make them a good choice for maintaing a set of alarms. With a timing wheel, one can support any number of alarms paying constant overhead per alarm, while paying a small constant overhead per unit of time passed.

As the minimum allowed key increases, the timing wheel does a lazy radix sort of the element keys, with level 0 handling the least significant `b_0` bits in a key, and each subsequent level `i` handling the next most significant `b_i` bits. The levels hold increasingly larger ranges of keys, where the union of all the levels can hold any key from `min_allowed_key t` to `max_allowed_key t`. When a key is added to the timing wheel, it is added at the lowest possible level that can store the key. As the minimum allowed key increases, timing-wheel elements move down levels until they reach level 0, and then are eventually removed.
An `Elt.t` represents an element that was added to a timing wheel.
`create ?level_bits ()` creates a new empty timing wheel, `t`, with `length t = 0` and `min_allowed_key t = 0`.
`length t` returns the number of elements in the timing wheel.
`is_empty t` is `length t = 0`
`min_allowed_key t` is the minimum key that can be stored in `t`. This only indicates the possibility; there need not be an element `elt` in `t` with `Elt.key elt = min_allowed_key t`. This is not the same as the "min_key" operation in a typical priority queue.

`min_allowed_key t` can increase over time, via calls to `increase_min_allowed_key`. It is guaranteed that `min_allowed_key t <= Key.max_representable`.
`max_allowed_key t` is the maximum allowed key that can be stored in `t`. As `min_allowed_key` increases, so does `max_allowed_key`; however it is not the case that `max_allowed_key t - min_allowed_key t` is a constant. It is guaranteed that `max_allowed_key t >= min (Key.max_representable, min_allowed_key t + 2^B - 1`, where `B` is the sum of the b_i in `level_bits`. It is also guaranteed that `max_allowed_key t <= Key.max_representable`.
`min_elt t` returns an element in `t` that has the minimum key, if `t` is nonempty. `min_elt` takes time proportional to the size of the timing-wheel data structure in the worst case. It is implemented via a linear search.

`min_key t` returns the key of `min_elt t`, if any.
`add t ~key value` adds a new value to `t` and returns an element that can later be supplied to `remove` the element from `t`. `add` raises if `key < min_allowed_key t || key > max_allowed_key t`.
`remove t elt` removes `elt` from `t`. It is an error if `elt` is not currently in `t`, and this error may or may not be detected.
`change_key t elt ~key` changes the key of `elt` to `key`. `change_key` raises if `not (mem t elt) || key < min_allowed_key t || key > max_allowed_key t`.
`clear t` removes all elts from `t`.
`increase_min_allowed_key t ~key ~handle_removed` increases the minimum allowed key in `t` to `key`, and removes all elements with keys less than `key`, applying `handle_removed` to each element that is removed. If `key <= min_allowed_key t`, then `increase_min_allowed_key` does nothing. Otherwise, if `increase_min_allowed_key` returns successfully, `min_allowed_key t = key`.

`increase_min_allowed_key` raises if `key > Key.max_representable`.

`increase_min_allowed_key` takes time proportional to `key - min_allowed_key t`, although possibly less time.

Behavior is unspecified if `handle_removed` accesses `t` in any way other than `Elt` functions.