Struct ReorderBuffer 

pub struct ReorderBuffer<T> { /* private fields */ }

A buffer that releases items in sequential order.

Items can be inserted with any sequence number, but they are only released when all prior sequence numbers have been released. This enables ordered output from parallel processing where items may complete out of order.

Uses a sparse VecDeque for O(1) insert and pop operations.

Memory Tracking

The buffer optionally tracks heap memory usage when using the insert_with_size/try_pop_next_with_size methods. This enables memory-bounded backpressure without expensive per-item size calculations.

Implementations

impl<T> ReorderBuffer<T>

pub fn new() -> Self

Create a new reorder buffer.

pub fn insert(&mut self, seq: u64, item: T)

Insert an item with a sequence number (without memory tracking).

Items can be inserted in any order. They will be released in sequence order via try_pop_next() or drain_ready().

Arguments

• seq - The sequence number for this item (0-indexed, monotonically increasing).
• item - The item to buffer.

Panics

Panics in debug mode if an item with the same sequence number is already buffered, or if the sequence number is before the current base.

pub fn insert_with_size(&mut self, seq: u64, item: T, heap_size: usize)

Insert an item with a sequence number and pre-computed heap size.

This variant tracks memory usage for backpressure control. The size should be computed once when creating the item.

Arguments

• seq - The sequence number for this item (0-indexed, monotonically increasing).
• item - The item to buffer.
• heap_size - Pre-computed heap size of the item in bytes.

Panics

Panics in debug mode if an item with the same sequence number is already buffered, or if the sequence number is before the current base.

pub fn try_pop_next(&mut self) -> Option<T>

Pop the next sequential item if available (without returning size).

Returns Some(item) if the item with next_seq is buffered, otherwise returns None.

This advances the internal sequence counter, so subsequent calls will return the next item in sequence.

pub fn try_pop_next_with_size(&mut self) -> Option<(T, usize)>

Pop the next sequential item if available, returning the item and its tracked size.

Returns Some((item, heap_size)) if the item with next_seq is buffered, otherwise returns None.

Panics

Panics if internal state is inconsistent (the front item was indicated as poppable but is missing).

pub fn drain_ready(&mut self) -> DrainReady<'_, T>

Drain all consecutive ready items starting from the current sequence.

Returns an iterator that yields items in sequence order, stopping when it reaches a gap in the sequence.

Example

use fgumi_lib::reorder_buffer::ReorderBuffer;

let mut buffer: ReorderBuffer<i32> = ReorderBuffer::new();
buffer.insert(0, 10);
buffer.insert(1, 20);
buffer.insert(3, 40);  // Gap at 2

let ready: Vec<_> = buffer.drain_ready().collect();
assert_eq!(ready, vec![10, 20]);  // Stops at gap

pub fn is_empty(&self) -> bool

Check if the buffer is empty.

pub fn len(&self) -> usize

Get the number of items currently stored in the buffer.

pub fn buffer_len(&self) -> usize

Get the internal buffer length (number of slots including gaps).

This reflects the actual memory footprint of the VecDeque, which grows when items arrive out of order (gaps are filled with None). Use this to limit memory growth when items may arrive with large serial gaps.

pub fn next_seq(&self) -> u64

Get the next expected sequence number.

pub fn can_pop(&self) -> bool

Check if the next sequential item is ready to pop.

This is O(1) and can be called frequently for backpressure decisions.

pub fn heap_bytes(&self) -> u64

Get the tracked heap memory in bytes.

This returns the sum of sizes passed to insert_with_size. It’s O(1) and suitable for frequent backpressure checks.

pub fn would_accept(&self, serial: u64, memory_limit: u64) -> bool

Check if this reorder buffer would accept a new item with the given serial.

This implements deadlock-free admission control:

• Always accept if serial == next_seq (the item we’re waiting for)
• Always accept if we can’t pop (we’re stuck, need more items)
• Reject if over the memory limit AND we can make progress

Arguments

• serial - The sequence number of the item to potentially insert
• memory_limit - The memory limit in bytes (0 = unlimited)

Returns

true if the item should be accepted, false if backpressure should be applied.

pub fn total_heap_size(&self) -> usize

where T: MemoryEstimate,

Calculate total heap memory used by all items in the buffer.

This iterates all items and sums their heap sizes. Only use for profiling/debugging as it’s O(n) in the number of buffered items.

Note: This calculates fresh from items using MemoryEstimate, not from tracked sizes. Use heap_bytes() for the tracked value.

Trait Implementations

impl<T: Debug> Debug for ReorderBuffer<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for ReorderBuffer<T>

fn default() -> Self

Returns the “default value” for a type.