nquic_pn_buf (nquic v1.0.0)
View SourceSent-packet buffer for nquic_loss.
QUIC's send pattern is monotonic-PN insert at the tail (RFC 9000
§12.3, packet numbers strictly increase within a packet number
space) followed by ACK arrivals that typically remove a prefix of
the oldest unacked entries. The previous implementation backed
this by gb_trees, which fires periodic O(N) rebalances under
monotonic-key insertion that show up as hot frames in profiling
(gb_trees:to_list, gb_trees:balance_list_1, gb_trees:count).
Internal representation is a two-list deque. front holds older
entries in ascending PN order; back holds newer entries in
descending PN order with the head being the newest. The invariant
max(PN in front) < min(PN in back) is preserved by every
operation.
Insert at the tail is O(1). Ascending walk with early stop is
O(K) where K is the number of entries scanned. The common
case for ACK and loss-detection sweeps is "scan a prefix of the
front", which never touches back. Operations that consume the
entire front then peek into the back reverse back once, paid
amortised across the full traversal.
Summary
Functions
Remove the entry at PN. Worst-case O(N) linear scan. Used by
spurious-loss bookkeeping where an ACK arrives for a previously
declared-lost packet and the entry must be cleared from the
recently_lost index.
Build a buffer from a list of {PN, Pkt} pairs. Sorts ascending and
seeds front with the result. Intended for tests and migration
helpers; production code should grow the buffer via insert/3.
Get the packet at PN or raise. Mirrors gb_trees:get/2 for tests
that depended on the exception shape; production code should prefer
lookup/2.
Insert Pkt at packet number PN. The caller must guarantee PN is
strictly greater than every existing PN in the buffer (the natural
monotonic-PN-per-space invariant from RFC 9000 §12.3). The function
does not validate this; violating the invariant only matters for
later iteration / range operations, which assume PN-ascending order.
Existence predicate. Same complexity as lookup/2.
Return whether the buffer holds no entries.
Packet numbers in ascending order. Materialises the full list.
Look up the packet at PN. Worst-case O(N) linear scan; the buffer
is not designed for random access, so callers should reserve this
for tests or rare paths (e.g. computing an RTT sample from the
largest acked PN, which is at most one call per ACK).
Construct an empty buffer.
Number of entries currently held.
Take all entries that satisfy the RFC 9002 §6.1 loss conditions
(PN =< PThresh OR time_sent =< TCutoff). Returns the lost
packets in PN-ascending order, the residual buffer, and the
NextLossTime hint (the first not-lost packet's
time_sent + LossDelay, or undefined if every packet was lost).
Stops at the first packet that fails both conditions. PN order
equals time-sent order on monotonic clock + monotonic PN, so all
suffix entries are also not lost; early-stop is safe.
Take all entries with time_sent =< Cutoff. Walks ascending and
stops at the first entry newer than Cutoff. Used to prune the
recently-lost index past the spurious-loss reorder window.
Take all entries with Low =< PN =< High. Returns the matched
packets in PN-ascending order plus the residual buffer. The common
case (range covers a prefix of front) touches only front and
runs in O(K) where K is the partition position. When the range
straddles into back, back is reversed once into front and the
scan continues; paid as a single linear pass amortised across the
caller.
All {PN, Pkt} entries in PN-ascending order.
Packet records in PN-ascending order. Materialises the full list.
Types
Functions
-spec delete(nquic_packet_number:t(), buf()) -> buf().
Remove the entry at PN. Worst-case O(N) linear scan. Used by
spurious-loss bookkeeping where an ACK arrives for a previously
declared-lost packet and the entry must be cleared from the
recently_lost index.
-spec from_list([{nquic_packet_number:t(), nquic_loss:sent_packet()}]) -> buf().
Build a buffer from a list of {PN, Pkt} pairs. Sorts ascending and
seeds front with the result. Intended for tests and migration
helpers; production code should grow the buffer via insert/3.
-spec get(nquic_packet_number:t(), buf()) -> nquic_loss:sent_packet().
Get the packet at PN or raise. Mirrors gb_trees:get/2 for tests
that depended on the exception shape; production code should prefer
lookup/2.
-spec insert(nquic_packet_number:t(), nquic_loss:sent_packet(), buf()) -> buf().
Insert Pkt at packet number PN. The caller must guarantee PN is
strictly greater than every existing PN in the buffer (the natural
monotonic-PN-per-space invariant from RFC 9000 §12.3). The function
does not validate this; violating the invariant only matters for
later iteration / range operations, which assume PN-ascending order.
-spec is_defined(nquic_packet_number:t(), buf()) -> boolean().
Existence predicate. Same complexity as lookup/2.
Return whether the buffer holds no entries.
-spec keys(buf()) -> [nquic_packet_number:t()].
Packet numbers in ascending order. Materialises the full list.
-spec lookup(nquic_packet_number:t(), buf()) -> none | {value, nquic_loss:sent_packet()}.
Look up the packet at PN. Worst-case O(N) linear scan; the buffer
is not designed for random access, so callers should reserve this
for tests or rare paths (e.g. computing an RTT sample from the
largest acked PN, which is at most one call per ACK).
-spec new() -> buf().
Construct an empty buffer.
-spec size(buf()) -> non_neg_integer().
Number of entries currently held.
-spec take_lost(buf(), integer(), integer(), pos_integer()) -> {[nquic_loss:sent_packet()], buf(), non_neg_integer() | undefined}.
Take all entries that satisfy the RFC 9002 §6.1 loss conditions
(PN =< PThresh OR time_sent =< TCutoff). Returns the lost
packets in PN-ascending order, the residual buffer, and the
NextLossTime hint (the first not-lost packet's
time_sent + LossDelay, or undefined if every packet was lost).
Stops at the first packet that fails both conditions. PN order
equals time-sent order on monotonic clock + monotonic PN, so all
suffix entries are also not lost; early-stop is safe.
-spec take_older_than(buf(), integer()) -> {[nquic_loss:sent_packet()], buf()}.
Take all entries with time_sent =< Cutoff. Walks ascending and
stops at the first entry newer than Cutoff. Used to prune the
recently-lost index past the spurious-loss reorder window.
-spec take_range(nquic_packet_number:t(), nquic_packet_number:t(), buf()) -> {[nquic_loss:sent_packet()], buf()}.
Take all entries with Low =< PN =< High. Returns the matched
packets in PN-ascending order plus the residual buffer. The common
case (range covers a prefix of front) touches only front and
runs in O(K) where K is the partition position. When the range
straddles into back, back is reversed once into front and the
scan continues; paid as a single linear pass amortised across the
caller.
-spec to_list(buf()) -> [{nquic_packet_number:t(), nquic_loss:sent_packet()}].
All {PN, Pkt} entries in PN-ascending order.
-spec values(buf()) -> [nquic_loss:sent_packet()].
Packet records in PN-ascending order. Materialises the full list.