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 Ppx_sexp_conv_lib.Sexpable.S with type t := t
val t_of_sexp : Sexplib0.Sexp.t -> tval sexp_of_t : t -> Sexplib0.Sexp.tinclude Core_kernel.Invariant.S with type t := t
val invariant : t -> unitmax_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
val create_exn : ?extend_to_max_num_bits:bool -> int list -> tIn 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. With ~extend_to_max_num_bits:true, the resulting t is extended with sufficient b_i
= 1 so that num_bits t = max_num_bits.
val default : tdefault 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.
val num_bits : t -> intnum_bits t is the sum of the b_i in t.