heapless/
sorted_linked_list.rs

1//! A fixed sorted priority linked list, similar to [`BinaryHeap`] but with different properties
2//! on `push`, `pop`, etc.
3//!
4//! For example, the sorting of the list will never `memcpy` the underlying value, so having large
5//! objects in the list will not cause a performance hit.
6//!
7//! # Examples
8//!
9//! ```
10//! use heapless::sorted_linked_list::{Max, SortedLinkedList};
11//! let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
12//!
13//! // The largest value will always be first
14//! ll.push(1).unwrap();
15//! assert_eq!(ll.peek(), Some(&1));
16//!
17//! ll.push(2).unwrap();
18//! assert_eq!(ll.peek(), Some(&2));
19//!
20//! ll.push(3).unwrap();
21//! assert_eq!(ll.peek(), Some(&3));
22//!
23//! // This will not fit in the queue.
24//! assert_eq!(ll.push(4), Err(4));
25//! ```
26//!
27//! [`BinaryHeap`]: `crate::binary_heap::BinaryHeap`
28
29use core::cmp::Ordering;
30use core::fmt;
31use core::marker::PhantomData;
32use core::mem::MaybeUninit;
33use core::ops::{Deref, DerefMut};
34use core::ptr;
35
36mod storage {
37    use super::{LenType, Node, SortedLinkedListInner, SortedLinkedListView};
38
39    /// Trait defining how data for a container is stored.
40    ///
41    /// There's two implementations available:
42    ///
43    /// - [`OwnedSortedLinkedListStorage`]: stores the data in an array `[T; N]` whose size is known at compile time.
44    /// - [`ViewSortedLinkedListStorage`]: stores the data in an unsized `[T]`.
45    ///
46    /// This allows [`SortedLinkedList`] to be generic over either sized or unsized storage. The [`sorted_linked_list`](super)
47    /// module contains a [`SortedLinkedListInner`] struct that's generic on [`SortedLinkedListStorage`],
48    /// and two type aliases for convenience:
49    ///
50    /// - [`SortedLinkedList<T, Idx, N>`](super::SortedLinkedList) = `SortedLinkedListInner<T, OwnedSortedLinkedListStorage<T, Idx, N>>`
51    /// - [`SortedLinkedListView<T, Idx>`](super::SortedLinkedListView) = `SortedLinkedListInner<T, ViewSortedLinkedListStorage<T, Idx>>`
52    ///
53    /// `SortedLinkedList` can be unsized into `SortedLinkedListView`, either by unsizing coercions such as `&mut SortedLinkedList -> &mut SortedLinkedListView` or
54    /// `Box<SortedLinkedList> -> Box<SortedLinkedListView>`, or explicitly with [`.as_view()`](super::SortedLinkedList::as_view) or [`.as_mut_view()`](super::SortedLinkedList::as_mut_view).
55    ///
56    /// This trait is sealed, so you cannot implement it for your own types. You can only use
57    /// the implementations provided by this crate.
58    ///
59    /// [`SortedLinkedListInner`]: super::SortedLinkedListInner
60    /// [`SortedLinkedList`]: super::SortedLinkedList
61    /// [`SortedLinkedListView`]: super::SortedLinkedListView
62    #[allow(private_bounds)]
63    pub trait SortedLinkedListStorage<T, Idx>: SortedLinkedListSealedStorage<T, Idx> {}
64
65    pub trait SortedLinkedListSealedStorage<T, Idx> {
66        // part of the sealed trait so that no trait is publicly implemented by `OwnedSortedLinkedListStorage` besides `Storage`
67        fn borrow(&self) -> &[Node<T, Idx>];
68        fn borrow_mut(&mut self) -> &mut [Node<T, Idx>];
69        fn as_view<K>(
70            this: &SortedLinkedListInner<T, Idx, K, Self>,
71        ) -> &SortedLinkedListView<T, K, Idx>
72        where
73            Idx: LenType,
74            Self: SortedLinkedListStorage<T, Idx>;
75        fn as_mut_view<K>(
76            this: &mut SortedLinkedListInner<T, Idx, K, Self>,
77        ) -> &mut SortedLinkedListView<T, K, Idx>
78        where
79            Idx: LenType,
80            Self: SortedLinkedListStorage<T, Idx>;
81    }
82
83    // One sealed layer of indirection to hide the internal details (The MaybeUninit).
84    pub struct SortedLinkedListStorageInner<T: ?Sized> {
85        pub(crate) buffer: T,
86    }
87
88    /// Implementation of [`SortedLinkedListStorage`] that stores the data in an array `[T; N]` whose size is known at compile time.
89    pub type OwnedSortedLinkedListStorage<T, Idx, const N: usize> =
90        SortedLinkedListStorageInner<[Node<T, Idx>; N]>;
91    /// Implementation of [`SortedLinkedListStorage`] that stores the data in an unsized `[T]`.
92    pub type ViewSortedLinkedListStorage<T, Idx> = SortedLinkedListStorageInner<[Node<T, Idx>]>;
93
94    impl<T, Idx, const N: usize> SortedLinkedListSealedStorage<T, Idx>
95        for OwnedSortedLinkedListStorage<T, Idx, N>
96    {
97        fn borrow(&self) -> &[Node<T, Idx>] {
98            &self.buffer
99        }
100        fn borrow_mut(&mut self) -> &mut [Node<T, Idx>] {
101            &mut self.buffer
102        }
103        fn as_view<K>(
104            this: &SortedLinkedListInner<T, Idx, K, Self>,
105        ) -> &SortedLinkedListView<T, K, Idx>
106        where
107            Self: SortedLinkedListStorage<T, Idx>,
108            Idx: LenType,
109        {
110            this
111        }
112        fn as_mut_view<K>(
113            this: &mut SortedLinkedListInner<T, Idx, K, Self>,
114        ) -> &mut SortedLinkedListView<T, K, Idx>
115        where
116            Self: SortedLinkedListStorage<T, Idx>,
117            Idx: LenType,
118        {
119            this
120        }
121    }
122    impl<T, Idx, const N: usize> SortedLinkedListStorage<T, Idx>
123        for OwnedSortedLinkedListStorage<T, Idx, N>
124    {
125    }
126
127    impl<T, Idx> SortedLinkedListSealedStorage<T, Idx> for ViewSortedLinkedListStorage<T, Idx> {
128        fn borrow(&self) -> &[Node<T, Idx>] {
129            &self.buffer
130        }
131        fn borrow_mut(&mut self) -> &mut [Node<T, Idx>] {
132            &mut self.buffer
133        }
134        fn as_view<K>(
135            this: &SortedLinkedListInner<T, Idx, K, Self>,
136        ) -> &SortedLinkedListView<T, K, Idx>
137        where
138            Self: SortedLinkedListStorage<T, Idx>,
139            Idx: LenType,
140        {
141            this
142        }
143        fn as_mut_view<K>(
144            this: &mut SortedLinkedListInner<T, Idx, K, Self>,
145        ) -> &mut SortedLinkedListView<T, K, Idx>
146        where
147            Self: SortedLinkedListStorage<T, Idx>,
148            Idx: LenType,
149        {
150            this
151        }
152    }
153    impl<T, Idx> SortedLinkedListStorage<T, Idx> for ViewSortedLinkedListStorage<T, Idx> {}
154}
155pub use storage::{
156    OwnedSortedLinkedListStorage, SortedLinkedListStorage, ViewSortedLinkedListStorage,
157};
158
159use crate::len_type::LenType;
160
161/// Marker for Min sorted [`SortedLinkedList`].
162pub struct Min;
163
164/// Marker for Max sorted [`SortedLinkedList`].
165pub struct Max;
166
167/// The linked list kind: min-list or max-list
168pub trait Kind: private::Sealed {
169    #[doc(hidden)]
170    fn ordering() -> Ordering;
171}
172
173impl Kind for Min {
174    fn ordering() -> Ordering {
175        Ordering::Less
176    }
177}
178
179impl Kind for Max {
180    fn ordering() -> Ordering {
181        Ordering::Greater
182    }
183}
184
185/// Sealed traits
186mod private {
187    pub trait Sealed {}
188}
189
190impl private::Sealed for Max {}
191impl private::Sealed for Min {}
192
193/// A node in the [`SortedLinkedList`].
194pub struct Node<T, Idx> {
195    val: MaybeUninit<T>,
196    next: Idx,
197}
198
199/// Base struct for [`SortedLinkedList`] and [`SortedLinkedListView`], generic over the [`SortedLinkedListStorage`].
200///
201/// In most cases you should use [`SortedLinkedList`] or [`SortedLinkedListView`] directly. Only use this
202/// struct if you want to write code that's generic over both.
203pub struct SortedLinkedListInner<T, Idx, K, S>
204where
205    Idx: LenType,
206    S: SortedLinkedListStorage<T, Idx> + ?Sized,
207{
208    head: Idx,
209    free: Idx,
210    phantom: PhantomData<(K, T)>,
211    list: S,
212}
213
214/// The linked list.
215pub type SortedLinkedList<T, K, const N: usize, Idx = usize> =
216    SortedLinkedListInner<T, Idx, K, OwnedSortedLinkedListStorage<T, Idx, N>>;
217
218/// The linked list.
219pub type SortedLinkedListView<T, K, Idx> =
220    SortedLinkedListInner<T, Idx, K, ViewSortedLinkedListStorage<T, Idx>>;
221
222macro_rules! impl_const_new {
223    ($ty:ty, $new_name:ident) => {
224        impl<T, K, const N: usize> SortedLinkedList<T, K, N, $ty> {
225            /// Create a new linked list.
226            pub const fn $new_name() -> Self {
227                const {
228                    assert!(
229                        (<$ty>::MAX as usize) >= (N + 1),
230                        "The capacity is larger than `LenT` can hold, increase the size of `LenT` or reduce the capacity"
231                    );
232                }
233
234                let mut list = SortedLinkedList {
235                    list: OwnedSortedLinkedListStorage {
236                        buffer: [const {
237                            Node {
238                                val: MaybeUninit::uninit(),
239                                next: <$ty>::MAX,
240                            }
241                        }; N],
242                    },
243                    head: <$ty>::MAX,
244                    free: 0,
245                    phantom: PhantomData,
246                };
247
248                if N == 0 {
249                    list.free = <$ty>::MAX;
250                    return list;
251                }
252
253                let mut free = 0;
254
255                // Initialize indexes
256                while free < N - 1 {
257                    list.list.buffer[free].next = free as $ty + 1;
258                    free += 1;
259                }
260
261                list
262            }
263        }
264    };
265}
266
267impl_const_new!(u8, new_u8);
268impl_const_new!(u16, new_u16);
269impl_const_new!(usize, new_usize);
270
271impl<T, Idx, K, S> SortedLinkedListInner<T, Idx, K, S>
272where
273    Idx: LenType,
274    S: SortedLinkedListStorage<T, Idx> + ?Sized,
275{
276    /// Get a reference to the `SortedLinkedList`, erasing the `N` const-generic.
277    pub fn as_view(&self) -> &SortedLinkedListView<T, K, Idx> {
278        S::as_view(self)
279    }
280
281    /// Get a mutable reference to the `Vec`, erasing the `N` const-generic.
282    pub fn as_mut_view(&mut self) -> &mut SortedLinkedListView<T, K, Idx> {
283        S::as_mut_view(self)
284    }
285
286    /// Internal access helper
287    #[inline(always)]
288    fn node_at(&self, index: usize) -> &Node<T, Idx> {
289        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
290        unsafe { self.list.borrow().get_unchecked(index) }
291    }
292
293    /// Internal access helper
294    #[inline(always)]
295    fn node_at_mut(&mut self, index: usize) -> &mut Node<T, Idx> {
296        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
297        unsafe { self.list.borrow_mut().get_unchecked_mut(index) }
298    }
299
300    /// Internal access helper
301    #[inline(always)]
302    fn write_data_in_node_at(&mut self, index: usize, data: T) {
303        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
304        unsafe {
305            self.node_at_mut(index).val.as_mut_ptr().write(data);
306        }
307    }
308
309    /// Internal access helper
310    #[inline(always)]
311    fn read_data_in_node_at(&self, index: usize) -> &T {
312        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
313        unsafe { &*self.node_at(index).val.as_ptr() }
314    }
315
316    /// Internal access helper
317    #[inline(always)]
318    fn read_mut_data_in_node_at(&mut self, index: usize) -> &mut T {
319        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
320        unsafe { &mut *self.node_at_mut(index).val.as_mut_ptr() }
321    }
322
323    /// Internal access helper
324    #[inline(always)]
325    fn extract_data_in_node_at(&mut self, index: usize) -> T {
326        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
327        unsafe { self.node_at(index).val.as_ptr().read() }
328    }
329}
330
331impl<T, Idx, K, S> SortedLinkedListInner<T, Idx, K, S>
332where
333    T: Ord,
334    Idx: LenType,
335    K: Kind,
336    S: SortedLinkedListStorage<T, Idx> + ?Sized,
337{
338    /// Pushes a value onto the list without checking if the list is full.
339    ///
340    /// Complexity is worst-case *O*(n).
341    ///
342    /// # Safety
343    ///
344    /// Assumes that the list is not full.
345    pub unsafe fn push_unchecked(&mut self, value: T) {
346        let new = self.free.into_usize();
347
348        // Store the data and update the next free spot
349        self.write_data_in_node_at(new, value);
350        self.free = self.node_at(new).next;
351
352        if let Some(head) = self.head.to_non_max() {
353            // Check if we need to replace head
354            if self
355                .read_data_in_node_at(head)
356                .cmp(self.read_data_in_node_at(new))
357                == K::ordering()
358            {
359                // It's not head, search the list for the correct placement
360                let mut current = head;
361
362                while let Some(next) = self.node_at(current).next.to_non_max() {
363                    if self
364                        .read_data_in_node_at(next)
365                        .cmp(self.read_data_in_node_at(new))
366                        != K::ordering()
367                    {
368                        break;
369                    }
370
371                    current = next;
372                }
373
374                self.node_at_mut(new).next = self.node_at(current).next;
375                self.node_at_mut(current).next = Idx::from_usize(new);
376            } else {
377                self.node_at_mut(new).next = self.head;
378                self.head = Idx::from_usize(new);
379            }
380        } else {
381            self.node_at_mut(new).next = self.head;
382            self.head = Idx::from_usize(new);
383        }
384    }
385
386    /// Pushes an element to the linked list and sorts it into place.
387    ///
388    /// Complexity is worst-case *O*(n).
389    ///
390    /// # Example
391    ///
392    /// ```
393    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
394    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
395    ///
396    /// // The largest value will always be first
397    /// ll.push(1).unwrap();
398    /// assert_eq!(ll.peek(), Some(&1));
399    ///
400    /// ll.push(2).unwrap();
401    /// assert_eq!(ll.peek(), Some(&2));
402    ///
403    /// ll.push(3).unwrap();
404    /// assert_eq!(ll.peek(), Some(&3));
405    ///
406    /// // This will not fit in the queue.
407    /// assert_eq!(ll.push(4), Err(4));
408    /// ```
409    pub fn push(&mut self, value: T) -> Result<(), T> {
410        if self.is_full() {
411            Err(value)
412        } else {
413            unsafe { self.push_unchecked(value) }
414            Ok(())
415        }
416    }
417
418    /// Peek at the first element.
419    ///
420    /// # Example
421    ///
422    /// ```
423    /// use heapless::sorted_linked_list::{Max, Min, SortedLinkedList};
424    /// let mut ll_max: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
425    ///
426    /// // The largest value will always be first
427    /// ll_max.push(1).unwrap();
428    /// assert_eq!(ll_max.peek(), Some(&1));
429    /// ll_max.push(2).unwrap();
430    /// assert_eq!(ll_max.peek(), Some(&2));
431    /// ll_max.push(3).unwrap();
432    /// assert_eq!(ll_max.peek(), Some(&3));
433    ///
434    /// let mut ll_min: SortedLinkedList<_, Min, 3, u8> = SortedLinkedList::new_u8();
435    ///
436    /// // The Smallest value will always be first
437    /// ll_min.push(3).unwrap();
438    /// assert_eq!(ll_min.peek(), Some(&3));
439    /// ll_min.push(2).unwrap();
440    /// assert_eq!(ll_min.peek(), Some(&2));
441    /// ll_min.push(1).unwrap();
442    /// assert_eq!(ll_min.peek(), Some(&1));
443    /// ```
444    pub fn peek(&self) -> Option<&T> {
445        self.head
446            .to_non_max()
447            .map(|head| self.read_data_in_node_at(head))
448    }
449
450    /// Pop an element from the list without checking so the list is not empty.
451    ///
452    /// # Safety
453    ///
454    /// Assumes that the list is not empty.
455    pub unsafe fn pop_unchecked(&mut self) -> T {
456        let head = self.head.into_usize();
457        let current = head;
458        self.head = self.node_at(head).next;
459        self.node_at_mut(current).next = self.free;
460        self.free = Idx::from_usize(current);
461
462        self.extract_data_in_node_at(current)
463    }
464
465    /// Pops the first element in the list.
466    ///
467    /// Complexity is worst-case *O*(1).
468    ///
469    /// # Example
470    ///
471    /// ```
472    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
473    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
474    ///
475    /// ll.push(1).unwrap();
476    /// ll.push(2).unwrap();
477    ///
478    /// assert_eq!(ll.pop(), Some(2));
479    /// assert_eq!(ll.pop(), Some(1));
480    /// assert_eq!(ll.pop(), None);
481    /// ```
482    pub fn pop(&mut self) -> Option<T> {
483        if self.is_empty() {
484            None
485        } else {
486            Some(unsafe { self.pop_unchecked() })
487        }
488    }
489
490    /// Checks if the linked list is full.
491    ///
492    /// # Example
493    ///
494    /// ```
495    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
496    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
497    ///
498    /// assert_eq!(ll.is_full(), false);
499    ///
500    /// ll.push(1).unwrap();
501    /// assert_eq!(ll.is_full(), false);
502    /// ll.push(2).unwrap();
503    /// assert_eq!(ll.is_full(), false);
504    /// ll.push(3).unwrap();
505    /// assert_eq!(ll.is_full(), true);
506    /// ```
507    #[inline]
508    pub fn is_full(&self) -> bool {
509        self.free.to_non_max().is_none()
510    }
511
512    /// Checks if the linked list is empty.
513    ///
514    /// # Example
515    ///
516    /// ```
517    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
518    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
519    ///
520    /// assert_eq!(ll.is_empty(), true);
521    ///
522    /// ll.push(1).unwrap();
523    /// assert_eq!(ll.is_empty(), false);
524    /// ```
525    #[inline]
526    pub fn is_empty(&self) -> bool {
527        self.head.to_non_max().is_none()
528    }
529}
530
531impl<T, Idx, K, S> SortedLinkedListInner<T, Idx, K, S>
532where
533    T: Ord,
534    Idx: LenType,
535    K: Kind,
536    S: SortedLinkedListStorage<T, Idx> + ?Sized,
537{
538    /// Get an iterator over the sorted list.
539    ///
540    /// # Example
541    ///
542    /// ```
543    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
544    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
545    ///
546    /// ll.push(1).unwrap();
547    /// ll.push(2).unwrap();
548    ///
549    /// let mut iter = ll.iter();
550    ///
551    /// assert_eq!(iter.next(), Some(&2));
552    /// assert_eq!(iter.next(), Some(&1));
553    /// assert_eq!(iter.next(), None);
554    /// ```
555    pub fn iter(&self) -> IterView<'_, T, Idx, K> {
556        IterView {
557            list: S::as_view(self),
558            index: self.head,
559        }
560    }
561
562    /// Find an element in the list that can be changed and resorted.
563    ///
564    /// # Example
565    ///
566    /// ```
567    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
568    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
569    ///
570    /// ll.push(1).unwrap();
571    /// ll.push(2).unwrap();
572    /// ll.push(3).unwrap();
573    ///
574    /// // Find a value and update it
575    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
576    /// *find += 1000;
577    /// find.finish();
578    ///
579    /// assert_eq!(ll.pop(), Some(1002));
580    /// assert_eq!(ll.pop(), Some(3));
581    /// assert_eq!(ll.pop(), Some(1));
582    /// assert_eq!(ll.pop(), None);
583    /// ```
584    pub fn find_mut<F>(&mut self, mut f: F) -> Option<FindMutView<'_, T, Idx, K>>
585    where
586        F: FnMut(&T) -> bool,
587    {
588        let head = self.head.to_non_max()?;
589
590        // Special-case, first element
591        if f(self.read_data_in_node_at(head)) {
592            return Some(FindMutView {
593                is_head: true,
594                prev_index: Idx::MAX,
595                index: self.head,
596                list: S::as_mut_view(self),
597                maybe_changed: false,
598            });
599        }
600
601        let mut current = head;
602
603        while let Some(next) = self.node_at(current).next.to_non_max() {
604            if f(self.read_data_in_node_at(next)) {
605                return Some(FindMutView {
606                    is_head: false,
607                    prev_index: Idx::from_usize(current),
608                    index: Idx::from_usize(next),
609                    list: S::as_mut_view(self),
610                    maybe_changed: false,
611                });
612            }
613
614            current = next;
615        }
616
617        None
618    }
619}
620
621/// Iterator for the linked list.
622pub struct IterView<'a, T, Idx, K>
623where
624    T: Ord,
625    Idx: LenType,
626    K: Kind,
627{
628    list: &'a SortedLinkedListInner<T, Idx, K, ViewSortedLinkedListStorage<T, Idx>>,
629    index: Idx,
630}
631
632impl<'a, T, Idx, K> Iterator for IterView<'a, T, Idx, K>
633where
634    T: Ord,
635    Idx: LenType,
636    K: Kind,
637{
638    type Item = &'a T;
639
640    fn next(&mut self) -> Option<Self::Item> {
641        let index = self.index.to_non_max()?;
642
643        let node = self.list.node_at(index);
644        self.index = node.next;
645
646        Some(self.list.read_data_in_node_at(index))
647    }
648}
649
650/// Comes from [`SortedLinkedList::find_mut`].
651pub struct FindMutView<'a, T, Idx, K>
652where
653    T: Ord,
654    Idx: LenType,
655    K: Kind,
656{
657    list: &'a mut SortedLinkedListView<T, K, Idx>,
658    is_head: bool,
659    prev_index: Idx,
660    index: Idx,
661    maybe_changed: bool,
662}
663
664impl<T, Idx, K> FindMutView<'_, T, Idx, K>
665where
666    T: Ord,
667    Idx: LenType,
668    K: Kind,
669{
670    fn pop_internal(&mut self) -> T {
671        if self.is_head {
672            // If it is the head element, we can do a normal pop
673            unsafe { self.list.pop_unchecked() }
674        } else {
675            // Somewhere in the list
676            let prev = self.prev_index.into_usize();
677            let curr = self.index.into_usize();
678
679            // Re-point the previous index
680            self.list.node_at_mut(prev).next = self.list.node_at_mut(curr).next;
681
682            // Release the index into the free queue
683            self.list.node_at_mut(curr).next = self.list.free;
684            self.list.free = self.index;
685
686            self.list.extract_data_in_node_at(curr)
687        }
688    }
689
690    /// This will pop the element from the list.
691    ///
692    /// Complexity is worst-case *O*(1).
693    ///
694    /// # Example
695    ///
696    /// ```
697    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
698    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
699    ///
700    /// ll.push(1).unwrap();
701    /// ll.push(2).unwrap();
702    /// ll.push(3).unwrap();
703    ///
704    /// // Find a value and update it
705    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
706    /// find.pop();
707    ///
708    /// assert_eq!(ll.pop(), Some(3));
709    /// assert_eq!(ll.pop(), Some(1));
710    /// assert_eq!(ll.pop(), None);
711    /// ```
712    #[inline]
713    pub fn pop(mut self) -> T {
714        self.pop_internal()
715    }
716
717    /// This will resort the element into the correct position in the list if needed. The resorting
718    /// will only happen if the element has been accessed mutably.
719    ///
720    /// Same as calling `drop`.
721    ///
722    /// Complexity is worst-case *O*(n).
723    ///
724    /// # Example
725    ///
726    /// ```
727    /// use heapless::sorted_linked_list::{Max, SortedLinkedList};
728    /// let mut ll: SortedLinkedList<_, Max, 3, u8> = SortedLinkedList::new_u8();
729    ///
730    /// ll.push(1).unwrap();
731    /// ll.push(2).unwrap();
732    /// ll.push(3).unwrap();
733    ///
734    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
735    /// find.finish(); // No resort, we did not access the value.
736    ///
737    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
738    /// *find += 1000;
739    /// find.finish(); // Will resort, we accessed (and updated) the value.
740    ///
741    /// assert_eq!(ll.pop(), Some(1002));
742    /// assert_eq!(ll.pop(), Some(3));
743    /// assert_eq!(ll.pop(), Some(1));
744    /// assert_eq!(ll.pop(), None);
745    /// ```
746    #[inline]
747    pub fn finish(self) {
748        drop(self);
749    }
750}
751
752impl<T, Idx, K> Drop for FindMutView<'_, T, Idx, K>
753where
754    T: Ord,
755    Idx: LenType,
756    K: Kind,
757{
758    fn drop(&mut self) {
759        // Only resort the list if the element has changed
760        if self.maybe_changed {
761            let val = self.pop_internal();
762            unsafe { self.list.push_unchecked(val) };
763        }
764    }
765}
766
767impl<T, Idx, K> Deref for FindMutView<'_, T, Idx, K>
768where
769    T: Ord,
770    Idx: LenType,
771    K: Kind,
772{
773    type Target = T;
774
775    fn deref(&self) -> &Self::Target {
776        self.list.read_data_in_node_at(self.index.into_usize())
777    }
778}
779
780impl<T, Idx, K> DerefMut for FindMutView<'_, T, Idx, K>
781where
782    T: Ord,
783    Idx: LenType,
784    K: Kind,
785{
786    fn deref_mut(&mut self) -> &mut Self::Target {
787        self.maybe_changed = true;
788        self.list.read_mut_data_in_node_at(self.index.into_usize())
789    }
790}
791
792// /// Useful for debug during development.
793// impl<T, Idx, K, const N: usize> fmt::Debug for FindMut<'_, T, Idx, K, N>
794// where
795//     T: Ord + core::fmt::Debug,
796//     Idx: LenType,
797//     K: Kind,
798// {
799//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
800//         f.debug_struct("FindMut")
801//             .field("prev_index", &self.prev_index.to_non_max())
802//             .field("index", &self.index.to_non_max())
803//             .field(
804//                 "prev_value",
805//                 &self
806//                     .list
807//                     .read_data_in_node_at(self.prev_index.to_non_max().unwrap()),
808//             )
809//             .field(
810//                 "value",
811//                 &self.list.read_data_in_node_at(self.index.to_non_max().unwrap()),
812//             )
813//             .finish()
814//     }
815// }
816
817impl<T, Idx, K, S> fmt::Debug for SortedLinkedListInner<T, Idx, K, S>
818where
819    T: Ord + core::fmt::Debug,
820    Idx: LenType,
821    K: Kind,
822    S: ?Sized + SortedLinkedListStorage<T, Idx>,
823{
824    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
825        f.debug_list().entries(self.iter()).finish()
826    }
827}
828
829impl<T, Idx, K, S> Drop for SortedLinkedListInner<T, Idx, K, S>
830where
831    Idx: LenType,
832    S: SortedLinkedListStorage<T, Idx> + ?Sized,
833{
834    fn drop(&mut self) {
835        let mut index = self.head;
836
837        while let Some(i) = index.to_non_max() {
838            let node = self.node_at_mut(i);
839            index = node.next;
840
841            unsafe {
842                ptr::drop_in_place(node.val.as_mut_ptr());
843            }
844        }
845    }
846}
847
848#[cfg(test)]
849mod tests {
850    use static_assertions::assert_not_impl_any;
851
852    use super::*;
853
854    // Ensure a `SortedLinkedList` containing `!Send` values stays `!Send` itself.
855    assert_not_impl_any!(SortedLinkedList<*const (), (), 4>: Send);
856
857    #[test]
858    fn const_new() {
859        static mut _V1: SortedLinkedList<u32, Max, 100, u8> = SortedLinkedList::new_u8();
860        static mut _V2: SortedLinkedList<u32, Max, 10_000, u16> = SortedLinkedList::new_u16();
861        static mut _V3: SortedLinkedList<u32, Max, 100_000, usize> = SortedLinkedList::new_usize();
862    }
863
864    #[test]
865    fn test_peek() {
866        let mut ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
867
868        ll.push(1).unwrap();
869        assert_eq!(ll.peek().unwrap(), &1);
870
871        ll.push(2).unwrap();
872        assert_eq!(ll.peek().unwrap(), &2);
873
874        ll.push(3).unwrap();
875        assert_eq!(ll.peek().unwrap(), &3);
876
877        let mut ll: SortedLinkedList<u32, Min, 3, u8> = SortedLinkedList::new_u8();
878
879        ll.push(2).unwrap();
880        assert_eq!(ll.peek().unwrap(), &2);
881
882        ll.push(1).unwrap();
883        assert_eq!(ll.peek().unwrap(), &1);
884
885        ll.push(3).unwrap();
886        assert_eq!(ll.peek().unwrap(), &1);
887    }
888
889    #[test]
890    fn test_full() {
891        let mut ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
892        ll.push(1).unwrap();
893        ll.push(2).unwrap();
894        ll.push(3).unwrap();
895
896        assert!(ll.is_full());
897    }
898
899    #[test]
900    fn test_empty() {
901        let ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
902
903        assert!(ll.is_empty());
904    }
905
906    #[test]
907    fn test_zero_size() {
908        let ll: SortedLinkedList<u32, Max, 0, u8> = SortedLinkedList::new_u8();
909
910        assert!(ll.is_empty());
911        assert!(ll.is_full());
912    }
913
914    #[test]
915    fn test_rejected_push() {
916        let mut ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
917        ll.push(1).unwrap();
918        ll.push(2).unwrap();
919        ll.push(3).unwrap();
920
921        // This won't fit
922        let r = ll.push(4);
923
924        assert_eq!(r, Err(4));
925    }
926
927    #[test]
928    fn test_updating() {
929        let mut ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
930        ll.push(1).unwrap();
931        ll.push(2).unwrap();
932        ll.push(3).unwrap();
933
934        let mut find = ll.find_mut(|v| *v == 2).unwrap();
935
936        *find += 1000;
937        find.finish();
938
939        assert_eq!(ll.peek().unwrap(), &1002);
940
941        let mut find = ll.find_mut(|v| *v == 3).unwrap();
942
943        *find += 1000;
944        find.finish();
945
946        assert_eq!(ll.peek().unwrap(), &1003);
947
948        // Remove largest element
949        ll.find_mut(|v| *v == 1003).unwrap().pop();
950
951        assert_eq!(ll.peek().unwrap(), &1002);
952    }
953
954    #[test]
955    fn test_updating_1() {
956        let mut ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
957        ll.push(1).unwrap();
958
959        let v = ll.pop().unwrap();
960
961        assert_eq!(v, 1);
962    }
963
964    #[test]
965    fn test_updating_2() {
966        let mut ll: SortedLinkedList<u32, Max, 3, u8> = SortedLinkedList::new_u8();
967        ll.push(1).unwrap();
968
969        let mut find = ll.find_mut(|v| *v == 1).unwrap();
970
971        *find += 1000;
972        find.finish();
973
974        assert_eq!(ll.peek().unwrap(), &1001);
975    }
976
977    fn _test_variance<'a: 'b, 'b>(
978        x: SortedLinkedList<&'a (), Max, 42, u8>,
979    ) -> SortedLinkedList<&'b (), Max, 42, u8> {
980        x
981    }
982    fn _test_variance_view<'a: 'b, 'b, 'c>(
983        x: &'c SortedLinkedListView<&'a (), Max, u8>,
984    ) -> &'c SortedLinkedListView<&'b (), Max, u8> {
985        x
986    }
987}
heapless/sorted_linked_list.rs

heapless/
sorted_linked_list.rs
