aboutsummaryrefslogtreecommitdiff
path: root/src/linked_list.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/linked_list.rs')
-rw-r--r--src/linked_list.rs599
1 files changed, 599 insertions, 0 deletions
diff --git a/src/linked_list.rs b/src/linked_list.rs
new file mode 100644
index 00000000..6a9836ee
--- /dev/null
+++ b/src/linked_list.rs
@@ -0,0 +1,599 @@
+use core::fmt;
+use core::marker::PhantomData;
+use core::mem::MaybeUninit;
+use core::ops::{Deref, DerefMut};
+use core::ptr;
+pub use generic_array::ArrayLength;
+use generic_array::GenericArray;
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+struct LinkedIndex(u16);
+
+impl LinkedIndex {
+ #[inline]
+ const unsafe fn new_unchecked(value: u16) -> Self {
+ LinkedIndex(value)
+ }
+
+ #[inline]
+ const fn none() -> Self {
+ LinkedIndex(u16::MAX)
+ }
+
+ #[inline]
+ const fn option(self) -> Option<u16> {
+ if self.0 == u16::MAX {
+ None
+ } else {
+ Some(self.0)
+ }
+ }
+}
+
+/// A node in the linked list.
+pub struct Node<T> {
+ val: MaybeUninit<T>,
+ next: LinkedIndex,
+}
+
+/// Iterator for the linked list.
+pub struct Iter<'a, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ list: &'a LinkedList<T, Kind, N>,
+ index: LinkedIndex,
+}
+
+impl<'a, T, Kind, N> Iterator for Iter<'a, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ type Item = &'a T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ let index = self.index.option()?;
+
+ let node = self.list.node_at(index as usize);
+ self.index = node.next;
+
+ Some(self.list.read_data_in_node_at(index as usize))
+ }
+}
+
+/// Comes from [`LinkedList::find_mut`].
+pub struct FindMut<'a, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ list: &'a mut LinkedList<T, Kind, N>,
+ is_head: bool,
+ prev_index: LinkedIndex,
+ index: LinkedIndex,
+ maybe_changed: bool,
+}
+
+impl<'a, T, Kind, N> FindMut<'a, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ fn pop_internal(&mut self) -> T {
+ if self.is_head {
+ // If it is the head element, we can do a normal pop
+ unsafe { self.list.pop_unchecked() }
+ } else {
+ // Somewhere in the list
+
+ // Re-point the previous index
+ self.list.node_at_mut(self.prev_index.0 as usize).next =
+ self.list.node_at_mut(self.index.0 as usize).next;
+
+ // Release the index into the free queue
+ self.list.node_at_mut(self.index.0 as usize).next = self.list.free;
+ self.list.free = self.index;
+
+ self.list.extract_data_in_node_at(self.index.0 as usize)
+ }
+ }
+
+ /// This will pop the element from the list.
+ ///
+ /// Complexity is O(1).
+ #[inline]
+ pub fn pop(mut self) -> T {
+ self.pop_internal()
+ }
+
+ /// This will resort the element into the correct position in the list in needed.
+ /// Same as calling `drop`.
+ ///
+ /// Complexity is worst-case O(N).
+ #[inline]
+ pub fn finish(self) {
+ drop(self)
+ }
+}
+
+impl<T, Kind, N> Drop for FindMut<'_, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ fn drop(&mut self) {
+ // Only resort the list if the element has changed
+ if self.maybe_changed {
+ let val = self.pop_internal();
+ unsafe { self.list.push_unchecked(val) };
+ }
+ }
+}
+
+impl<T, Kind, N> Deref for FindMut<'_, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ type Target = T;
+
+ fn deref(&self) -> &Self::Target {
+ self.list.read_data_in_node_at(self.index.0 as usize)
+ }
+}
+
+impl<T, Kind, N> DerefMut for FindMut<'_, T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ self.maybe_changed = true;
+ self.list.read_mut_data_in_node_at(self.index.0 as usize)
+ }
+}
+
+impl<T, Kind, N> fmt::Debug for FindMut<'_, T, Kind, N>
+where
+ T: PartialEq + PartialOrd + core::fmt::Debug,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("FindMut")
+ .field("prev_index", &self.prev_index)
+ .field("index", &self.index)
+ .field(
+ "prev_value",
+ &self
+ .list
+ .read_data_in_node_at(self.prev_index.option().unwrap() as usize),
+ )
+ .field(
+ "value",
+ &self
+ .list
+ .read_data_in_node_at(self.index.option().unwrap() as usize),
+ )
+ .finish()
+ }
+}
+
+/// The linked list.
+pub struct LinkedList<T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ list: MaybeUninit<GenericArray<Node<T>, N>>,
+ head: LinkedIndex,
+ free: LinkedIndex,
+ _kind: PhantomData<Kind>,
+}
+
+impl<T, Kind, N> LinkedList<T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ /// Internal helper to not do pointer arithmetic all over the place.
+ #[inline]
+ fn node_at(&self, index: usize) -> &Node<T> {
+ // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
+ unsafe { &*(self.list.as_ptr() as *const Node<T>).add(index) }
+ }
+
+ /// Internal helper to not do pointer arithmetic all over the place.
+ #[inline]
+ fn node_at_mut(&mut self, index: usize) -> &mut Node<T> {
+ // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
+ unsafe { &mut *(self.list.as_mut_ptr() as *mut Node<T>).add(index) }
+ }
+
+ /// Internal helper to not do pointer arithmetic all over the place.
+ #[inline]
+ fn write_data_in_node_at(&mut self, index: usize, data: T) {
+ unsafe {
+ self.node_at_mut(index).val.as_mut_ptr().write(data);
+ }
+ }
+
+ /// Internal helper to not do pointer arithmetic all over the place.
+ #[inline]
+ fn read_data_in_node_at(&self, index: usize) -> &T {
+ unsafe { &*self.node_at(index).val.as_ptr() }
+ }
+
+ /// Internal helper to not do pointer arithmetic all over the place.
+ #[inline]
+ fn read_mut_data_in_node_at(&mut self, index: usize) -> &mut T {
+ unsafe { &mut *self.node_at_mut(index).val.as_mut_ptr() }
+ }
+
+ /// Internal helper to not do pointer arithmetic all over the place.
+ #[inline]
+ fn extract_data_in_node_at(&mut self, index: usize) -> T {
+ unsafe { self.node_at(index).val.as_ptr().read() }
+ }
+
+ /// Internal helper to not do pointer arithmetic all over the place.
+ /// Safety: This can overwrite existing allocated nodes if used improperly, meaning their
+ /// `Drop` methods won't run.
+ #[inline]
+ unsafe fn write_node_at(&mut self, index: usize, node: Node<T>) {
+ (self.list.as_mut_ptr() as *mut Node<T>)
+ .add(index)
+ .write(node)
+ }
+
+ /// Create a new linked list.
+ pub fn new() -> Self {
+ let mut list = LinkedList {
+ list: MaybeUninit::uninit(),
+ head: LinkedIndex::none(),
+ free: unsafe { LinkedIndex::new_unchecked(0) },
+ _kind: PhantomData,
+ };
+
+ let len = N::U16;
+ let mut free = 0;
+
+ // Initialize indexes
+ while free < len - 1 {
+ unsafe {
+ list.write_node_at(
+ free as usize,
+ Node {
+ val: MaybeUninit::uninit(),
+ next: LinkedIndex::new_unchecked(free + 1),
+ },
+ );
+ }
+ free += 1;
+ }
+
+ // Initialize final index
+ unsafe {
+ list.write_node_at(
+ free as usize,
+ Node {
+ val: MaybeUninit::uninit(),
+ next: LinkedIndex::none(),
+ },
+ );
+ }
+
+ list
+ }
+
+ /// Push unchecked
+ ///
+ /// Complexity is O(N).
+ ///
+ /// # Safety
+ ///
+ /// Assumes that the list is not full.
+ pub unsafe fn push_unchecked(&mut self, value: T) {
+ let new = self.free.0;
+ // Store the data and update the next free spot
+ self.write_data_in_node_at(new as usize, value);
+ self.free = self.node_at(new as usize).next;
+
+ if let Some(head) = self.head.option() {
+ // Check if we need to replace head
+ if self
+ .read_data_in_node_at(head as usize)
+ .partial_cmp(self.read_data_in_node_at(new as usize))
+ != Kind::ordering()
+ {
+ self.node_at_mut(new as usize).next = self.head;
+ self.head = LinkedIndex::new_unchecked(new);
+ } else {
+ // It's not head, search the list for the correct placement
+ let mut current = head;
+
+ while let Some(next) = self.node_at(current as usize).next.option() {
+ if self
+ .read_data_in_node_at(next as usize)
+ .partial_cmp(self.read_data_in_node_at(new as usize))
+ != Kind::ordering()
+ {
+ break;
+ }
+
+ current = next;
+ }
+
+ self.node_at_mut(new as usize).next = self.node_at(current as usize).next;
+ self.node_at_mut(current as usize).next = LinkedIndex::new_unchecked(new);
+ }
+ } else {
+ self.node_at_mut(new as usize).next = self.head;
+ self.head = LinkedIndex::new_unchecked(new);
+ }
+ }
+
+ /// Pushes an element to the linked list and sorts it into place.
+ ///
+ /// Complexity is O(N).
+ pub fn push(&mut self, value: T) -> Result<(), T> {
+ if !self.is_full() {
+ Ok(unsafe { self.push_unchecked(value) })
+ } else {
+ Err(value)
+ }
+ }
+
+ /// Get an iterator over the sorted list.
+ pub fn iter(&self) -> Iter<'_, T, Kind, N> {
+ Iter {
+ list: self,
+ index: self.head,
+ }
+ }
+
+ /// Find an element in the list.
+ pub fn find_mut<F>(&mut self, mut f: F) -> Option<FindMut<'_, T, Kind, N>>
+ where
+ F: FnMut(&T) -> bool,
+ {
+ let head = self.head.option()?;
+
+ // Special-case, first element
+ if f(self.read_data_in_node_at(head as usize)) {
+ return Some(FindMut {
+ is_head: true,
+ prev_index: LinkedIndex::none(),
+ index: self.head,
+ list: self,
+ maybe_changed: false,
+ });
+ }
+
+ let mut current = head;
+
+ while let Some(next) = self.node_at(current as usize).next.option() {
+ if f(self.read_data_in_node_at(next as usize)) {
+ return Some(FindMut {
+ is_head: false,
+ prev_index: unsafe { LinkedIndex::new_unchecked(current) },
+ index: unsafe { LinkedIndex::new_unchecked(next) },
+ list: self,
+ maybe_changed: false,
+ });
+ }
+
+ current = next;
+ }
+
+ None
+ }
+
+ /// Peek at the first element.
+ pub fn peek(&self) -> Option<&T> {
+ self.head
+ .option()
+ .map(|head| self.read_data_in_node_at(head as usize))
+ }
+
+ /// Pop unchecked
+ ///
+ /// # Safety
+ ///
+ /// Assumes that the list is not empty.
+ pub unsafe fn pop_unchecked(&mut self) -> T {
+ let head = self.head.0;
+ let current = head;
+ self.head = self.node_at(head as usize).next;
+ self.node_at_mut(current as usize).next = self.free;
+ self.free = LinkedIndex::new_unchecked(current);
+
+ self.extract_data_in_node_at(current as usize)
+ }
+
+ /// Pops the first element in the list.
+ ///
+ /// Complexity is O(1).
+ pub fn pop(&mut self) -> Result<T, ()> {
+ if !self.is_empty() {
+ Ok(unsafe { self.pop_unchecked() })
+ } else {
+ Err(())
+ }
+ }
+
+ /// Checks if the linked list is full.
+ #[inline]
+ pub fn is_full(&self) -> bool {
+ self.free.option().is_none()
+ }
+
+ /// Checks if the linked list is empty.
+ #[inline]
+ pub fn is_empty(&self) -> bool {
+ self.head.option().is_none()
+ }
+}
+
+impl<T, Kind, N> Drop for LinkedList<T, Kind, N>
+where
+ T: PartialEq + PartialOrd,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ fn drop(&mut self) {
+ let mut index = self.head;
+
+ while let Some(i) = index.option() {
+ let node = self.node_at_mut(i as usize);
+ index = node.next;
+
+ unsafe {
+ ptr::drop_in_place(node.val.as_mut_ptr());
+ }
+ }
+ }
+}
+
+impl<T, Kind, N> fmt::Debug for LinkedList<T, Kind, N>
+where
+ T: PartialEq + PartialOrd + core::fmt::Debug,
+ Kind: kind::Kind,
+ N: ArrayLength<Node<T>>,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.iter()).finish()
+ }
+}
+
+/// Min sorted linked list.
+pub struct Min;
+
+/// Max sorted linked list.
+pub struct Max;
+
+/// Sealed traits and implementations for `linked_list`
+pub mod kind {
+ use super::{Max, Min};
+ use core::cmp::Ordering;
+
+ /// The linked list kind: min first or max first
+ pub unsafe trait Kind {
+ #[doc(hidden)]
+ fn ordering() -> Option<Ordering>;
+ }
+
+ unsafe impl Kind for Min {
+ #[inline]
+ fn ordering() -> Option<Ordering> {
+ Some(Ordering::Less)
+ }
+ }
+
+ unsafe impl Kind for Max {
+ #[inline]
+ fn ordering() -> Option<Ordering> {
+ Some(Ordering::Greater)
+ }
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ // Note this useful idiom: importing names from outer (for mod tests) scope.
+ use super::*;
+ use generic_array::typenum::consts::*;
+
+ #[test]
+ fn test_peek() {
+ let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+
+ ll.push(1).unwrap();
+ assert_eq!(ll.peek().unwrap(), &1);
+
+ ll.push(2).unwrap();
+ assert_eq!(ll.peek().unwrap(), &2);
+
+ ll.push(3).unwrap();
+ assert_eq!(ll.peek().unwrap(), &3);
+
+ let mut ll: LinkedList<u32, Min, U3> = LinkedList::new();
+
+ ll.push(2).unwrap();
+ assert_eq!(ll.peek().unwrap(), &2);
+
+ ll.push(1).unwrap();
+ assert_eq!(ll.peek().unwrap(), &1);
+
+ ll.push(3).unwrap();
+ assert_eq!(ll.peek().unwrap(), &1);
+ }
+
+ #[test]
+ fn test_full() {
+ let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+ ll.push(1).unwrap();
+ ll.push(2).unwrap();
+ ll.push(3).unwrap();
+
+ assert!(ll.is_full())
+ }
+
+ #[test]
+ fn test_empty() {
+ let ll: LinkedList<u32, Max, U3> = LinkedList::new();
+
+ assert!(ll.is_empty())
+ }
+
+ #[test]
+ fn test_rejected_push() {
+ let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+ ll.push(1).unwrap();
+ ll.push(2).unwrap();
+ ll.push(3).unwrap();
+
+ // This won't fit
+ let r = ll.push(4);
+
+ assert_eq!(r, Err(4));
+ }
+
+ #[test]
+ fn test_updating() {
+ let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+ ll.push(1).unwrap();
+ ll.push(2).unwrap();
+ ll.push(3).unwrap();
+
+ let mut find = ll.find_mut(|v| *v == 2).unwrap();
+
+ *find += 1000;
+ find.finish();
+
+ assert_eq!(ll.peek().unwrap(), &1002);
+
+ let mut find = ll.find_mut(|v| *v == 3).unwrap();
+
+ *find += 1000;
+ find.finish();
+
+ assert_eq!(ll.peek().unwrap(), &1003);
+
+ // Remove largest element
+ ll.find_mut(|v| *v == 1003).unwrap().pop();
+
+ assert_eq!(ll.peek().unwrap(), &1002);
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-29 19:42:01 +0000