async_priority_lock/
priority.rs

1//! Contains the [Priority] trait responsible for establishing entry position in [PriorityQueue].
2#[cfg(doc)]
3use crate::queue::PriorityQueue;
4#[cfg(feature = "const-default")]
5use const_default::ConstDefault;
6use core::cmp::Ordering;
7
8/// Trait used by [PriorityQueue] to determine the order by which nodes should be enqueued.
9pub trait Priority {
10    /// Compare a (possibly new) priority to an already queued one.
11    ///
12    /// The meaning for the results is as follows:
13    /// - `Less`: Lower priority (i.e. should place after `other`)
14    /// - `Equal`: Same priority - same priority; can be placed before or after `other`
15    /// - `Greater`: Higher priority - Higher priority
16    ///
17    /// This **must** be transitive.
18    fn compare(&self, other: &Self) -> Ordering;
19
20    /// Compare a new (not in a queue) priority with an already queued one (old).
21    ///
22    /// [PriorityQueue]  implementers must always use this function when enqueueing or re-queueing
23    /// an entry to compare it with existing ones.
24    ///
25    /// This does not need to be transitive (and often shouldn't be).
26    ///
27    /// This **must** return the same as [compare](Self::compare) if the result of [compare](Self::compare)
28    /// isn't [Ordering::Equal].
29    ///
30    /// # Example (logic used in [FIFO]):
31    /// ```
32    /// fn compare_new(&self, old: &Self) -> Ordering {
33    ///     // If priority is Equal, then return Less (as `old` was queued first)
34    ///     self.0.compare(&old.0).then(Ordering::Less)
35    /// }
36    /// ```
37    #[inline]
38    fn compare_new(&self, old: &Self) -> Ordering {
39        self.compare(old)
40    }
41}
42
43impl<O: Ord> Priority for O {
44    #[inline(always)]
45    fn compare(&self, other: &Self) -> Ordering {
46        self.cmp(other)
47    }
48}
49
50/// A redundant type alias existing to have parity with LowestFirst (as the default [Priority] impl
51/// for [Ord] is highest first)
52pub type HighestFirst<O> = O;
53
54/// Reverses the result of [Ord::cmp] for `O`. [Less](Ordering::Less) -> [Greater][Ordering::Greater] and
55/// [Greater](Ordering::Greater) -> [Less](Ordering::Less).
56///
57/// This *would* use [Reverse](core::cmp::Reverse), however that does not impl [`From<O>`] - which would make
58/// locking more verbse. e.g. instead of `.acqurie_from(priority)` you'd need
59/// `.acquire(core::cmp::Reverse(priority))`.
60#[derive(Default, Debug, Clone, Copy)]
61#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
62#[repr(transparent)]
63pub struct LowestFirst<O: Ord>(O);
64
65#[cfg(feature = "const-default")]
66impl<O: Ord + ConstDefault> ConstDefault for LowestFirst<O> {
67    const DEFAULT: Self = Self(O::DEFAULT);
68}
69
70impl<O: Ord> Priority for LowestFirst<O> {
71    #[inline]
72    fn compare(&self, other: &Self) -> Ordering {
73        other.0.cmp(&self.0)
74    }
75}
76
77impl<O: Ord> From<O> for LowestFirst<O> {
78    #[inline]
79    fn from(value: O) -> Self {
80        Self(value)
81    }
82}
83
84/// A priority wrapper where newer entries with the same priority are placed after existing entries.
85#[derive(Default, Debug, Clone, Copy)]
86#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
87#[repr(transparent)]
88pub struct FIFO<P: Priority>(P);
89
90impl<P: Priority> Priority for FIFO<P> {
91    #[inline]
92    fn compare(&self, other: &Self) -> Ordering {
93        self.0.compare(&other.0)
94    }
95
96    #[inline]
97    fn compare_new(&self, old: &Self) -> Ordering {
98        // specifically use `compare_new` here as the inner logic may have its own logic that
99        // either only needs to be run for new nodes.
100        //
101        // For fifo, if the old entry is the same priority, then we should place after.
102        // thus, same priority = lower priority
103        self.0.compare_new(&old.0).then(Ordering::Less)
104    }
105}
106
107impl<O: Ord> From<O> for FIFO<LowestFirst<O>> {
108    #[inline]
109    fn from(value: O) -> Self {
110        Self(value.into())
111    }
112}
113
114impl<P: Priority> From<P> for FIFO<P> {
115    #[inline]
116    fn from(value: P) -> Self {
117        Self(value)
118    }
119}
120
121#[cfg(feature = "const-default")]
122impl<P: Priority + ConstDefault> ConstDefault for FIFO<P> {
123    const DEFAULT: Self = Self(P::DEFAULT);
124}
125
126/// A priority wrapper where newer entries with the same priority are placed before existing entries.
127#[derive(Default, Debug, Clone, Copy)]
128#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
129#[repr(transparent)]
130pub struct LIFO<P: Priority>(P);
131
132impl<P: Priority> Priority for LIFO<P> {
133    #[inline]
134    fn compare(&self, other: &Self) -> Ordering {
135        self.0.compare(&other.0)
136    }
137
138    #[inline]
139    fn compare_new(&self, old: &Self) -> Ordering {
140        // specifically use `compare_new` here as the inner logic may have its own logic that
141        // either only needs to be run for new nodes.
142        //
143        // Opposite of fifo - if the new entry has the same priority as the old one, then we
144        // consider it a higher priority
145        self.0.compare_new(&old.0).then(Ordering::Greater)
146    }
147}
148
149impl<P: Priority> From<P> for LIFO<P> {
150    #[inline]
151    fn from(value: P) -> Self {
152        Self(value)
153    }
154}
155
156impl<O: Ord> From<O> for LIFO<LowestFirst<O>> {
157    #[inline]
158    fn from(value: O) -> Self {
159        Self(value.into())
160    }
161}
162
163#[cfg(feature = "const-default")]
164impl<P: Priority + ConstDefault> ConstDefault for LIFO<P> {
165    const DEFAULT: Self = Self(P::DEFAULT);
166}
async_priority_lock/priority.rs

async_priority_lock/
priority.rs
