Struct PrioGraph

pub struct PrioGraph<Id: TransactionId, Rk: ResourceKey, Tl: TopLevelId<Id>, Pfn: Fn(&Id, &GraphNode<Id>) -> Tl> { /* private fields */ }

A directed acyclic graph where edges are only present between nodes if that node is the next-highest priority node for a particular resource. Resources can be either read or write locked with write locks being exclusive. Transactions are inserted into the graph and then popped in time-priority order. Between conflicting transactions, the first to be inserted will always have higher priority.

Implementations

impl<Id: TransactionId, Rk: ResourceKey, Tl: TopLevelId<Id>, Pfn: Fn(&Id, &GraphNode<Id>) -> Tl> PrioGraph<Id, Rk, Tl, Pfn>

pub fn natural_batches( iter: impl IntoIterator<Item = (Id, impl IntoIterator<Item = (Rk, AccessKind)>)>, top_level_prioritization_fn: Pfn, ) -> Vec<Vec<Id>>

Drains all transactions from the primary queue into a batch. Then, for each transaction in the batch, unblock transactions it was blocking. If any of those transactions are now unblocked, add them to the main queue. Repeat until the main queue is empty.

pub fn new(top_level_prioritization_fn: Pfn) -> Self

Create a new priority graph.

pub fn clear(&mut self)

Clear the graph.

pub fn make_natural_batches(&mut self) -> Vec<Vec<Id>>

Make natural batches from the transactions already inserted into the graph. Drains all transactions from the primary queue into a batch. Then, for each transaction in the batch, unblock transactions it was blocking. If any of those transactions are now unblocked, add them to the main queue. Repeat until the main queue is empty.

pub fn insert_transaction( &mut self, id: Id, tx: impl IntoIterator<Item = (Rk, AccessKind)>, )

Insert a transaction into the graph with the given Id. Transactions should be inserted in priority order.

pub fn is_empty(&self) -> bool

Returns true if the main queue is empty.

pub fn pop_and_unblock(&mut self) -> Option<(Id, Vec<Id>)>

Combination of pop and unblock. Returns None if the queue is empty. Returns the Id of the popped node, and the set of unblocked Ids.

pub fn pop(&mut self) -> Option<Id>

Pop the highest priority node id from the main queue. Returns None if the queue is empty.

pub fn unblock(&mut self, id: &Id) -> Vec<Id>

This will unblock transactions that were blocked by this transaction. Returns the set of Ids that were unblocked.

Panics: - Node does not exist. - If the node.blocked_by_count != 0

pub fn is_blocked(&self, id: Id) -> bool

Returns whether the given Id is at the top level of the graph, i.e. not blocked. If the node does not exist, returns false.