Struct LinkedList

pub struct LinkedList<M>
where
    Link<M>: AnyFrameMeta,
{ /* private fields */ }

A linked list of frames.

Two key features that LinkedList is different from [alloc::collections::LinkedList] is that:

1. It is intrusive, meaning that the links are part of the frame metadata. This allows the linked list to be used without heap allocation. But it disallows a frame to be in multiple linked lists at the same time.
2. The linked list exclusively own the frames, meaning that it takes unique pointers UniqueFrame. And other bodies cannot from_in_use a frame that is inside a linked list.
3. We also allow creating cursors at a specific frame, allowing $O(1)$ removal without iterating through the list at a cost of some checks.

Example

To create metadata types that allows linked list links, wrap the metadata type in Link:

use ostd::{
    mm::{frame::{linked_list::{Link, LinkedList}, Frame}, FrameAllocOptions},
    impl_untyped_frame_meta_for,
};

#[derive(Debug)]
struct MyMeta { mark: usize }

type MyFrame = Frame<Link<MyMeta>>;

impl_untyped_frame_meta_for!(MyMeta);

let alloc_options = FrameAllocOptions::new();
let frame1 = alloc_options.alloc_frame_with(Link::new(MyMeta { mark: 1 })).unwrap();
let frame2 = alloc_options.alloc_frame_with(Link::new(MyMeta { mark: 2 })).unwrap();

let mut list = LinkedList::new();
list.push_front(frame1.try_into().unwrap());
list.push_front(frame2.try_into().unwrap());

let mut cursor = list.cursor_front_mut();
assert_eq!(cursor.current_meta().unwrap().mark, 2);
cursor.move_next();
assert_eq!(cursor.current_meta().unwrap().mark, 1);

Implementations

impl<M> LinkedList<M>

where Link<M>: AnyFrameMeta,

pub const fn new() -> Self

Creates a new linked list.

pub fn size(&self) -> usize

Gets the number of frames in the linked list.

pub fn is_empty(&self) -> bool

Tells if the linked list is empty.

pub fn push_front(&mut self, frame: UniqueFrame<Link<M>>)

Pushes a frame to the front of the linked list.

pub fn pop_front(&mut self) -> Option<UniqueFrame<Link<M>>>

Pops a frame from the front of the linked list.

pub fn push_back(&mut self, frame: UniqueFrame<Link<M>>)

Pushes a frame to the back of the linked list.

pub fn pop_back(&mut self) -> Option<UniqueFrame<Link<M>>>

Pops a frame from the back of the linked list.

pub fn contains(&mut self, frame: Paddr) -> bool

Tells if a frame is in the list.

pub fn cursor_mut_at(&mut self, frame: Paddr) -> Option<CursorMut<'_, M>>

Gets a cursor at the specified frame if the frame is in the list.

This method fail if Self::contains returns false.

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, M>

Gets a cursor at the front that can mutate the linked list links.

If the list is empty, the cursor points to the “ghost” non-element.

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, M>

Gets a cursor at the back that can mutate the linked list links.

If the list is empty, the cursor points to the “ghost” non-element.

Trait Implementations

impl<M> Default for LinkedList<M>

where Link<M>: AnyFrameMeta,

fn default() -> Self

Returns the “default value” for a type.

impl<M> Drop for LinkedList<M>

where Link<M>: AnyFrameMeta,

fn drop(&mut self)

Executes the destructor for this type.

impl<M> Send for LinkedList<M>

where Link<M>: AnyFrameMeta,

impl<M> Sync for LinkedList<M>

where Link<M>: AnyFrameMeta,