Struct Cursor

Source

pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { /* private fields */ }

Expand description

A cursor into a List.

A cursor always rests between two elements in the list. This means that a cursor has a previous and next element, but no current element. It also means that it’s possible to have a cursor into an empty list.

§Examples

use kernel::prelude::*;
use kernel::list::{List, ListArc, ListLinks};

#[pin_data]
struct ListItem {
    value: u32,
    #[pin]
    links: ListLinks,
}

impl ListItem {
    fn new(value: u32) -> Result<ListArc<Self>> {
        ListArc::pin_init(try_pin_init!(Self {
            value,
            links <- ListLinks::new(),
        }), GFP_KERNEL)
    }
}

kernel::list::impl_has_list_links! {
    impl HasListLinks<0> for ListItem { self.links }
}
kernel::list::impl_list_arc_safe! {
    impl ListArcSafe<0> for ListItem { untracked; }
}
kernel::list::impl_list_item! {
    impl ListItem<0> for ListItem { using ListLinks; }
}

// Use a cursor to remove the first element with the given value.
fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
    let mut cursor = list.cursor_front();
    while let Some(next) = cursor.peek_next() {
        if next.value == value {
            return Some(next.remove());
        }
        cursor.move_next();
    }
    None
}

// Use a cursor to remove the last element with the given value.
fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
    let mut cursor = list.cursor_back();
    while let Some(prev) = cursor.peek_prev() {
        if prev.value == value {
            return Some(prev.remove());
        }
        cursor.move_prev();
    }
    None
}

// Use a cursor to remove all elements with the given value. The removed elements are moved to
// a new list.
fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
    let mut out = List::new();
    let mut cursor = list.cursor_front();
    while let Some(next) = cursor.peek_next() {
        if next.value == value {
            out.push_back(next.remove());
        } else {
            cursor.move_next();
        }
    }
    out
}

// Use a cursor to insert a value at a specific index. Returns an error if the index is out of
// bounds.
fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
    let mut cursor = list.cursor_front();
    for _ in 0..idx {
        if !cursor.move_next() {
            return Err(EINVAL);
        }
    }
    cursor.insert_next(new);
    Ok(())
}

// Merge two sorted lists into a single sorted list.
fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
    let mut cursor = list.cursor_front();
    for to_insert in merge {
        while let Some(next) = cursor.peek_next() {
            if to_insert.value < next.value {
                break;
            }
            cursor.move_next();
        }
        cursor.insert_prev(to_insert);
    }
}

let mut list = List::new();
list.push_back(ListItem::new(14)?);
list.push_back(ListItem::new(12)?);
list.push_back(ListItem::new(10)?);
list.push_back(ListItem::new(12)?);
list.push_back(ListItem::new(15)?);
list.push_back(ListItem::new(14)?);
assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
// [14, 10, 15, 14]
assert!(remove_first(&mut list, 14).is_some());
// [10, 15, 14]
insert_at(&mut list, ListItem::new(12)?, 2)?;
// [10, 15, 12, 14]
assert!(remove_last(&mut list, 15).is_some());
// [10, 12, 14]

let mut list2 = List::new();
list2.push_back(ListItem::new(11)?);
list2.push_back(ListItem::new(13)?);
merge_sorted(&mut list, list2);

let mut items = list.into_iter();
assert_eq!(items.next().unwrap().value, 10);
assert_eq!(items.next().unwrap().value, 11);
assert_eq!(items.next().unwrap().value, 12);
assert_eq!(items.next().unwrap().value, 13);
assert_eq!(items.next().unwrap().value, 14);
assert!(items.next().is_none());