Struct OrderedQueue 

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

A reorder buffer that outputs items in serial order.

Uses smart backpressure to prevent deadlock:

• When waiting for next_seq: MUST accept items (refusing would deadlock)
• When we have next_seq: CAN refuse items (consumer can drain)

Deadlock Prevention

The key insight is that if we’re waiting for serial N, we must accept serials N+1, N+2, etc. because serial N might be produced by another thread that’s blocked trying to push to this queue. Only when we have serial N available can we safely apply backpressure, because the consumer can make progress by draining serial N.

Example

let queue = OrderedQueue::new(1_000_000); // 1MB limit
queue.insert(2, item2, 1000)?; // Accepted (waiting for 0)
queue.insert(0, item0, 1000)?; // Accepted (now has 0)
let (item, size) = queue.try_pop_next().unwrap(); // Returns item0
queue.insert(1, item1, 1000)?; // Accepted (now has 1)

Implementations

impl<T> OrderedQueue<T>

pub fn new(limit_bytes: u64) -> Self

Create a new ordered queue with the given memory limit.

pub fn can_accept(&self, heap_size: usize) -> bool

Check if we can accept an item (lock-free fast path).

Returns true if:

• We don’t have next_seq (must accept to make progress), OR
• We’re under the memory limit

pub fn insert( &self, serial: u64, item: T, heap_size: usize, ) -> Result<(), (T, usize)>

Insert an item into the reorder buffer.

Acceptance rule:

• If we do NOT have next_seq: ACCEPT (must accumulate for progress)
• If we DO have next_seq: only accept if under memory limit

Returns Err((item, heap_size)) if rejected due to backpressure.

Errors

Returns the item and heap size if rejected due to memory backpressure.

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

Try to pop the next item in serial order.

Returns Some((item, heap_size)) if next_seq is available.

pub fn next_seq(&self) -> u64

Get the next expected serial number.

pub fn can_pop(&self) -> bool

Check if we have the next expected serial (can make progress).

pub fn current_bytes(&self) -> u64

Current memory usage in bytes.

pub fn set_limit(&self, new_limit: u64)

Update the memory limit (for dynamic rebalancing).

pub fn limit_bytes(&self) -> u64

Get current limit.

pub fn len(&self) -> usize

Number of items in the buffer.

pub fn is_empty(&self) -> bool

Check if buffer is empty.

pub fn record_sample(&self)

Record a sample for stats.

pub fn record_blocked(&self, ns: u64)

Record blocked time in nanoseconds.

pub fn collect_stats(&self) -> QueueStats

Collect and reset stats.