Struct ShortQueue

pub struct ShortQueue<T, const N: usize>
where
    T: Cmov + Pod,
{ /* private fields */ }

Implements a queue with a fixed maximum size. The queue access pattern and size are oblivious.

There are two trivial efficient ways to implement this for short queues:

1. Use oblivious compaction:

• Push: n (2 + log n)
• Pop: n
• Iter: n

2. Use timestamps:

• Push: n
• Pop: n
• Iter: n (1 + log^2 n)

This implementation uses timestamps (2.), as we only need push and pop for the unsorted map.

Invariants

• highest_timestamp is the timestamp of the most recently added element
• lowest_timestamp is the timestamp of the oldest element added, or just non-zero if the queue is empty
• size is the number of elements with non-zero timestamps
• an element in elements is valid if its timestamp is non-zero, in which case the timestamp is unique and in the range [lowest_timestamp, highest_timestamp]

Implementations

impl<T, const N: usize> ShortQueue<T, N>

where T: Cmov + Pod + Default,

pub fn new() -> Self

Creates a new empty ShortQueue with maximum size N.

pub fn maybe_push(&mut self, real: bool, element: T)

Pushes element into the queue if real is true.

pub fn maybe_pop(&mut self, real: bool, out: &mut T)

Pops an element from the queue into out if real is true.

Trait Implementations

impl<T, const N: usize> Debug for ShortQueue<T, N>

where T: Cmov + Pod + Debug,

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

Formats the value using the given formatter.

impl<T, const N: usize> Default for ShortQueue<T, N>

where T: Cmov + Pod + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, const N: usize> Length for ShortQueue<T, N>

where T: Cmov + Pod + Default,

fn len(&self) -> usize

Returns the length of the indexable.