An ordered multiset: add, remove one occurrence, and read back in arrival order.
Internal. Everything above it sees a list in arrival order, which to_list/1
produces. Adding and removing one occurrence are both O(1) amortised, however large the
bucket grows — a plain list cannot do both, and neither can a queue on its own.
Two things in the engine need exactly this, which is why it is one module rather than
two. Rete.Memory keys a bucket per join key: a Rete.Network.Node.RootJoin has nothing
to join on, so it stores every matching fact under one key. Rete.Agenda keys a bucket
per sort key, which is one rule's pending matches, and cancels from it by value when
truth maintenance takes a match back.
:queue holds every item ever pushed. :counts holds live occurrences per value, and
:dead holds retracted ones still in the queue. Removal tombstones an occurrence,
instead of rebuilding. to_list/1 and pop/1 then skip the first dead[value]
occurrences of each value, in arrival order — so the oldest occurrence is the one
that went. Tombstones are compacted once they outnumber the living occurrences. See
docs/design/engine.md §7.
:counts is what makes take/2 O(1), and take/2 is the only thing that reads it. So it
is not maintained until the first take/2 builds it from the queue in one pass. A session
that only inserts never takes from a bucket, and pays nothing for an index it never uses.
That build is safe because take/2 is also the only writer of :dead. While :indexed?
is false there are no tombstones, so the queue holds exactly the live items.
iex> alias Rete.Bucket
iex> {:ok, bucket} = Bucket.new([:a, :b, :a]) |> Bucket.take(:a)
iex> Bucket.to_list(bucket)
[:b, :a]
iex> {:error, _bucket} = Bucket.take(bucket, :never_stored)
iex> {:ok, :b, _rest} = Bucket.pop(bucket)Summary
Functions
Whether anything live is left.
A bucket holding items, in arrival order.
Takes the oldest live item, or :empty.
Adds items behind the ones already there. O(1) per item.
Adds one item behind the ones already there.
How many live items there are. O(1).
Removes the oldest live occurrence of target.
The live items, in arrival order.
Types
@type t() :: %Rete.Bucket{ counts: %{required(term()) => pos_integer()}, dead: %{required(term()) => pos_integer()}, dead_total: non_neg_integer(), indexed?: boolean(), live: non_neg_integer(), queue: :queue.queue(term()) }
Functions
Whether anything live is left.
A bucket holding items, in arrival order.
Takes the oldest live item, or :empty.
Discards the tombstones it walks past, so the cost of skipping one is paid once.
Adds items behind the ones already there. O(1) per item.
Adds one item behind the ones already there.
The single-item clause of push/2 delegates here, because one at a time is the common
call. The list form walks its argument three times and takes its length. This does
neither.
@spec size(t()) :: non_neg_integer()
How many live items there are. O(1).
Removes the oldest live occurrence of target.
Returns {:ok, bucket}, or {:error, bucket} if there is no such occurrence. A miss
carries a bucket too, because the miss is what builds the index. Rete.Agenda misses
once per activation that has already fired, so discarding it would rebuild every time.
A miss is reported rather than silently doing nothing. A caller that propagated a
retraction of something the bucket never held would corrupt every count below it, and
Rete.Agenda tells a cancelled activation from an already-fired one by exactly this.
The live items, in arrival order.