async_priority_lock/
queue.rs

1//! Contains the [PriorityQueue] trait and builtin impls when features are enabled.
2//!
3//! Provided queues are [BoxQueue] and [ArenaQueue].
4#[cfg(feature = "box-queue")]
5pub mod boxed;
6#[cfg(feature = "box-queue")]
7pub use boxed::*;
8#[cfg(feature = "arena-queue")]
9pub mod arena;
10#[cfg(feature = "arena-queue")]
11pub use arena::*;
12
13use crate::Priority;
14
15/// A PriorityQueue is a queue which orders entries by priority - higher priority first.
16///
17/// This is marked as unsafe as some associated types exist which must behave correctly, in
18/// particular:
19/// - An enqueued node will return a Self::Handle
20/// - Until that handle is dequeued via self.dequeue, we must be able to lookup the node - even if
21///   that node is repositioned.
22/// - "shared" handles - these allow us to lookup nodes without owning them or retaining a
23///   reference to the queue (allowing us to update them, but not remove them)
24///
25/// Any lookups via a handle which was not returned from enqueue or other functions is UB.
26/// Implementers can choose to panic or simply assume that all handles provided will be valid.
27///
28/// Additionally, it is required that all nodes be dequeued before the queue is dropped - so
29/// the queue should not have any entries when it is dropped.
30pub unsafe trait PriorityQueue<P: Priority>: Default {
31    type Handle: PriorityQueueHandle<P>;
32    type SharedHandle: AsRef<Self::Handle>;
33
34    /// Enqueue an entry with provided data.  This must return a unique handle for this node.
35    fn enqueue(&mut self, data: P) -> Self::Handle;
36    /// Dequeue an entry by its handle
37    fn dequeue(&mut self, handle: Self::Handle) -> (Option<&P>, Option<Self::SharedHandle>);
38
39    /// Get an entry's data by its handle
40    fn get_by_handle(&self, handle: &Self::Handle) -> &P;
41
42    #[inline(always)]
43    /// Iterate through the queue from the start.
44    fn iter<'a>(&'a self) -> impl Iterator<Item = &'a P>
45    where
46        P: 'a,
47    {
48        self.iter_at(None)
49    }
50
51    /// Iterate through the queue starting at a provided handle (or None to start with the head
52    /// node) (including the provided value)
53    fn iter_at<'a>(&'a self, handle: Option<&Self::Handle>) -> impl Iterator<Item = &'a P>
54    where
55        P: 'a;
56
57    /// Returns true if the queue is empty
58    #[inline]
59    fn is_empty(&self) -> bool {
60        self.iter().next().is_none()
61    }
62
63    /// Update a node via handle ref.  `update` is a fn that should return true if the node's
64    /// priority changed.  i.e. if `update` returns false, the queue does not need to consider
65    /// repositioning the changed node.
66    fn update_node(&mut self, handle: &Self::Handle, update: impl FnOnce(&mut P) -> bool);
67
68    #[inline]
69    /// Get the first node in the queue
70    fn head(&self) -> Option<&P> {
71        self.iter().next()
72    }
73
74    /// Get a SharedHandle for the first node in the queue
75    fn head_handle(&self) -> Option<Self::SharedHandle>;
76
77    /// Get the handle for the next node after an input handle (or None if the provided handle is
78    /// the tail node)
79    fn get_next_handle(&self, handle: &Self::Handle) -> Option<Self::SharedHandle>;
80}
81
82/// The "handle" for an entry in a [PriorityQueue].
83///
84/// Allows for skipping a read lock on the owning [PriorityQueue] if a reference to the data can be
85/// retrieved without a reference to the owning queue.
86pub trait PriorityQueueHandle<D: Priority> {
87    /// If the entry can be loaded with only the handle (without needing access to the queue
88    /// itself), then this can optionally be set to a function which loads it directly.
89    ///
90    /// It is up to the caller to ensure that none of the referenced data used can be changed while
91    /// a ref is held (e.g. make sure that update_node is not called on the node, or if it is
92    /// called, none of the data referenced will be mutated)
93    const LOAD_PURE: Option<unsafe fn(&Self) -> &D> = None;
94}
async_priority_lock/queue.rs

async_priority_lock/
queue.rs
