Module Timing_wheel_intf.S.Level_bits

module Level_bits: sig .. end

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

include Invariant.S

val max_num_bits : int

val create_exn : int list -> t

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.

val default : Word_size.t -> t

default returns the default value of level_bits used by Timing_wheel.create and Timing_wheel.Priority_queue.create. It varies based on the machine's word size. Here are the the values and the amount of space used for the level arrays.

| word | bits used | level_bits | space used | |------+-----------+--------------------------+-------------| | 32 | 29 | 10; 10; 9 | < 4k words | | 64 | 61 | 11; 10; 10; 10; 10; 10 | < 10k words |

val num_bits : t -> int

num_bits t is the sum of the b_i in t.

val t_of_sexp : Sexplib.Sexp.t -> t

val sexp_of_t : t -> Sexplib.Sexp.t