Implements a timers queue based on
gb_trees. The queue
can be encoded as JSON with Jason or Elixir's JSON module, and dump/1
returns the same data as plain maps and lists for any other encoder.
All map keys in the encoded form are shrinked to a single letter as this queue is intended to be encoded and published to HTTP clients over the wire, multiple times.
The queue keys are a map composed of the timestamp (t) of an event
and an unique integer (u).
No erlang timers or processes are used, as the queue is only a data structure. The advantage is that the queue can be persisted on storage and keeps working after restarting the runtime. The queue maintain its own list of unique integers to avoir relying on BEAM unique integers as they are reset on VM restarts.
The main drawback of a functional queue is that the queue entries must be manually checked for expired timers.
Summary
Functions
Deletes an event from the queue and returns the new queue.
Deletes all entries from the queue whose values are equal to unwanted.
Returns the queue as plain maps, lists and integers.
Adds a new event to the queue with a TTL and the current system time as now/0.
Adds a new event to the queue with a TTL relative to the given timestamp in milliseconds.
Adds a new event to the queue with an absolute timestamp.
Returns a new queue with entries for whom the given callback returned a truthy value.
Returns a new queue with entries for whom the given callback returned a truthy value.
Creates an empty time queue.
This function is used internally to determine the current time when using
functions enqueue/3, pop/1, pop_event/1 and peek_event/1.
Returns the next value of the queue or a delay in milliseconds before the next value.
Returns the next value of the queue, or a delay, according to the given current time in milliseconds.
Returns the next event of the queue or a delay in milliseconds before the next value.
Returns the next event of the queue according to the given current time in milliseconds.
Extracts the next event in the queue or returns a delay.
Extracts the next event in the queue according to the given current time in milliseconds.
Extracts the next event in the queue with the current system time as now/0.
Extracts the next event in the queue according to the given current time in milliseconds.
Returns the number of entries in the queue.
Returns a stream of all the events in the queue.
Returns the time to next event.
Returns the time to next event.
Provides a GenServer compatible timeout from the queue, giving the time to
the next event.
Returns the absolute timestamp a queue event is scheduled for.
Returns the time reference of a queue event. This reference is used as a key to identify a unique event.
Returns the value of a queue event.
Types
@type dumped() :: %{ m: integer(), s: non_neg_integer(), q: [%{k: %{t: timestamp_ms(), u: integer()}, v: event_value()}] }
@opaque event()
@type event_value() :: any()
@opaque t()
@type timespec() :: {integer(), timespec_unit()}
@type timespec_unit() ::
:ms
| :second
| :seconds
| :minute
| :minutes
| :hour
| :hours
| :day
| :days
| :week
| :weeks
@type timestamp_ms() :: integer()
@opaque tref()
Functions
Deletes an event from the queue and returns the new queue.
It accepts a time reference or a full event. When an event is given, its time reference will be used to find the event to delete, meaning the queue event will be deleted even if the value of the passed event was tampered.
The function does not fail if the event cannot be found and simply returns the queue as-is.
Deletes all entries from the queue whose values are equal to unwanted.
Returns the queue as plain maps, lists and integers.
The Jason.Encoder and JSON.Encoder implementations encode this
representation. Use dump/1 to encode the queue with another encoder, or to
store it in a format that is independent from the internal data structure.
load/1 rebuilds the queue from it.
iex> tq = TimeQueue.new()
iex> {:ok, _, tq} = TimeQueue.enqueue_abs(tq, 2000, :world)
iex> {:ok, _, tq} = TimeQueue.enqueue_abs(tq, 1000, :hello)
iex> %{s: 2, q: [first, second]} = TimeQueue.dump(tq)
iex> first
%{k: %{t: 1000, u: -2147483646}, v: :hello}
iex> second
%{k: %{t: 2000, u: -2147483647}, v: :world}The returned map has the following keys, shortened to a single letter to keep the encoded form small:
:m- The last unique integer given to a time reference. Time references created after aload/1continue from it.:s- The number of events in the queue.:q- The events, in the order they are due. Each event is a map with the time reference under:kand the value under:v. The time reference is a map with the scheduled timestamp in milliseconds under:tand the unique integer under:u.
Values are returned as they were enqueued, so encoding the result as JSON requires values that the encoder supports.
Adds a new event to the queue with a TTL and the current system time as now/0.
See enqueue/4.
Adds a new event to the queue with a TTL relative to the given timestamp in milliseconds.
The TTL is either an integer number of milliseconds, or a {count, unit}
tuple where unit is one of :ms, :second, :minute, :hour, :day or
:week (plural forms such as :seconds are accepted too).
Returns {:ok, tref, new_queue} where tref is a timer reference.
The TTL can be zero or negative. The event is then scheduled at or before
now and is due immediately: pop/2 returns it and timeout/3 returns 0.
Events keep their real scheduled timestamp, so overdue events are returned in
timestamp order, the oldest first. This lets you compute a TTL from a deadline
that may already have passed and still handle the event right away.
iex> tq = TimeQueue.new()
iex> {:ok, _, tq} = TimeQueue.enqueue(tq, {-1, :second}, :due_1s_ago, _now = 10_000)
iex> {:ok, _, tq} = TimeQueue.enqueue(tq, -5000, :due_5s_ago, _now = 10_000)
iex> TimeQueue.timeout(tq, _now = 10_000)
0
iex> {:ok, first, tq} = TimeQueue.pop(tq, _now = 10_000)
iex> {:ok, second, _} = TimeQueue.pop(tq, _now = 10_000)
iex> {first, second}
{:due_5s_ago, :due_1s_ago}
Adds a new event to the queue with an absolute timestamp.
Returns {:ok, tref, new_queue} where tref is a timer reference.
The timestamp can be in the past. The event is then due immediately, and
overdue events are returned in timestamp order. See enqueue/4.
Returns a new queue with entries for whom the given callback returned a truthy value.
Use filter_val/2 to filter only using values.
Returns a new queue with entries for whom the given callback returned a truthy value.
Unlinke filter/2, the callback is only passed the event value.
Rebuilds a queue from the data returned by dump/1.
The keys can be atoms, as returned by dump/1, or strings, as returned by a
JSON decoder. Queues persisted as plain maps by TimeQueue 1.x share this
format and are loaded with this function too.
Event values are loaded as they are given. A value that went through JSON comes back as the decoder returns it.
iex> tq = TimeQueue.new()
iex> {:ok, _, tq} = TimeQueue.enqueue_abs(tq, 1000, :hello)
iex> tq = tq |> TimeQueue.dump() |> TimeQueue.load()
iex> TimeQueue.peek(tq, _now = 1000)
{:ok, :hello}
@spec new() :: t()
Creates an empty time queue.
iex> tq = TimeQueue.new()
iex> TimeQueue.peek_event(tq)
:empty
@spec now() :: integer()
This function is used internally to determine the current time when using
functions enqueue/3, pop/1, pop_event/1 and peek_event/1.
It is a simple alias to :erlang.system_time(:millisecond). TimeQueue does
not use monotonic time since it already manages its own unique identifiers for
queue entries.
@spec peek(t()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event_value()}
Returns the next value of the queue or a delay in milliseconds before the next value.
See peek/2.
@spec peek(t(), now :: timestamp_ms()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event_value()}
Returns the next value of the queue, or a delay, according to the given current time in milliseconds.
Just like pop/2 vs. pop_event/2, peek wil only return {:ok, value}
when a timeout is reached whereas peek_event will return {:ok, event}.
@spec peek_event(t()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event()}
Returns the next event of the queue or a delay in milliseconds before the next value.
event values can be retrieved with TimeQueue.value/1.
See peek_event/2.
@spec peek_event(t(), now :: timestamp_ms()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event()}
Returns the next event of the queue according to the given current time in milliseconds.
Possible return values are:
:empty{:ok, event}if the timestamp of the first event is<=to the given current time.{:delay, tref, ms}if the timestamp of the first event is>to the given current time. The remaining amount of milliseconds is returned.
Example
iex> {:ok, tref, tq} = TimeQueue.new() |> TimeQueue.enqueue(100, :hello, _now = 0)
iex> {:delay, ^tref, 80} = TimeQueue.peek_event(tq, _now = 20)
iex> {:ok, _} = TimeQueue.peek_event(tq, _now = 100)
@spec pop(t()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event_value(), t()}
Extracts the next event in the queue or returns a delay.
See pop/2.
@spec pop(t(), now :: timestamp_ms()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event_value(), t()}
Extracts the next event in the queue according to the given current time in milliseconds.
Much like pop_event/2 but the tuple returned when an event time is reached
(returns with :ok) success will only contain the value inserted in the
queue.
Possible return values are:
:empty{:ok, value, new_queue}if the timestamp of the first event is<=to the given current time. The event is deleted fromnew_queue.{:delay, tref, ms}if the timestamp of the first event is>to the given current time. The remaining amount of milliseconds is returned.
Example
iex> {:ok, tref, tq} = TimeQueue.new() |> TimeQueue.enqueue(100, :hello, _now = 0)
iex> {:delay, ^tref, 80} = TimeQueue.pop(tq, _now = 20)
iex> {:ok, value, _} = TimeQueue.pop(tq, _now = 100)
iex> value
:hello
@spec pop_event(t()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event(), t()}
Extracts the next event in the queue with the current system time as now/0.
See pop_event/2.
@spec pop_event(t(), now :: timestamp_ms()) :: :empty | {:delay, tref(), non_neg_integer()} | {:ok, event(), t()}
Extracts the next event in the queue according to the given current time in milliseconds.
Possible return values are:
:empty{:ok, event, new_queue}if the timestamp of the first event is<=to the given current time. The event is deleted fromnew_queue.{:delay, tref, ms}if the timestamp of the first event is>to the given current time. The remaining amount of milliseconds is returned.
Example
iex> {:ok, tref, tq} = TimeQueue.new() |> TimeQueue.enqueue(100, :hello, _now = 0)
iex> {:delay, ^tref, 80} = TimeQueue.pop_event(tq, _now = 20)
iex> {:ok, event, _} = TimeQueue.pop_event(tq, _now = 100)
iex> TimeQueue.value(event)
:hello
Returns the number of entries in the queue.
@spec stream(t()) :: Enumerable.t()
Returns a stream of all the events in the queue.
Note that this stream is immediate and does not wait for events.
Returns the time to next event.
Same as timeout(tq, :infinity, now()). See timeout/3.
Returns the time to next event.
Accepts either the current time or an atom to return when the queue is empty.
- If an integer is given, it will has the same result as
timeout(tq, :infinity, integer). - If an atom is given, it will has the same result as
timeout(tq, atom, now()).
See timeout/3.
@spec timeout(t(), :infinity | :hibernate | atom(), now :: timestamp_ms()) :: non_neg_integer() | :infinity | :hibernate | atom()
Provides a GenServer compatible timeout from the queue, giving the time to
the next event.
Accepts the current time as a third argument or will default to the current system time.
Returns:
if_emptywhen the queue is empty. A common value in that case is either:infinityor:hibernate.0when there the next event time has been reached.- The delay to the next event otherwise, capped at
4_294_967_295milliseconds (about 49.7 days), the largest timeout accepted byreceiveandGenServer.
When the next event is further away than that limit, the process wakes up
before the event is due. pop/1 then returns {:delay, tref, ms} with the
full remaining delay, and calling timeout/3 again gives the next wait.
Always handle the {:delay, tref, ms} return of pop/1 after a timeout.
iex> {:ok, _, tq} = TimeQueue.enqueue(TimeQueue.new(), {60, :days}, :later, _now = 0)
iex> TimeQueue.timeout(tq, _now = 0)
4_294_967_295
iex> {:delay, _, ms} = TimeQueue.pop(tq, _now = 0)
iex> ms
5_184_000_000For instance, when used in a GenServer, this function can tell when to
automatically wakeup the process.
def handle_call(request, _from, state) do
state = do_stuff(state, request)
timeout = TimeQueue.timeout(state.time_queue)
{:reply, :ok, state, timeout}
end By default, timeout/1 and timeout/2 (if called with an integer for the
current time) will return :infinity if the queue if empty. But you may
pass :hibernate as the second argument for timeout/2 or timeout/3 to
return :hibernate instead.
Note that any other atom than :infinity or :hibernate will be returned
as-is if as well if the queue is empty.
@spec timestamp(event()) :: timestamp_ms()
Returns the absolute timestamp a queue event is scheduled for.
iex> tq = TimeQueue.new()
iex> {:ok, _, tq} = TimeQueue.enqueue_abs(tq, 1234, :my_value)
iex> {:ok, event} = TimeQueue.peek_event(tq)
iex> TimeQueue.timestamp(event)
1234
Returns the time reference of a queue event. This reference is used as a key to identify a unique event.
iex> tq = TimeQueue.new()
iex> {:ok, tref, tq} = TimeQueue.enqueue(tq, 10, :my_value, _now = 0)
iex> {:ok, event} = TimeQueue.peek_event(tq, _now = 10)
iex> tref == TimeQueue.tref(event)
true
Returns the value of a queue event.
iex> tq = TimeQueue.new()
iex> {:ok, _, tq} = TimeQueue.enqueue(tq, 10, :my_value, _now = 0)
iex> {:ok, event} = TimeQueue.peek_event(tq, _now = 10)
iex> TimeQueue.value(event)
:my_value