Struct MapleTree

Source

pub struct MapleTree<T: ForeignOwnable> { /* private fields */ }

Expand description

A maple tree optimized for storing non-overlapping ranges.

§Invariants

Each range in the maple tree owns an instance of T.

Implementations§

Source §

impl<T: ForeignOwnable> MapleTree<T>

Source

pub fn project<'pin>( self: Pin<&'pin mut Self>, ) -> MapleTreeProjection<'__pin, T>

Pin-projects all fields of Self.

These fields are structurally pinned:

tree

These fields are not structurally pinned:

_p

Source §

impl<T: ForeignOwnable> MapleTree<T>

Source

pub fn new() -> impl PinInit<Self>

Create a new maple tree.

The tree will use the regular implementation with a higher branching factor, rather than the allocation tree.

Source

pub fn insert( &self, index: usize, value: T, gfp: Flags, ) -> Result<(), InsertError<T>>

Insert the value at the given index.

§Errors

If the maple tree already contains a range using the given index, then this call will return an InsertErrorKind::Occupied. It may also fail if memory allocation fails.

§Examples

use kernel::maple_tree::{InsertErrorKind, MapleTree};

let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;

let ten = KBox::new(10, GFP_KERNEL)?;
let twenty = KBox::new(20, GFP_KERNEL)?;
let the_answer = KBox::new(42, GFP_KERNEL)?;

// These calls will succeed.
tree.insert(100, ten, GFP_KERNEL)?;
tree.insert(101, twenty, GFP_KERNEL)?;

// This will fail because the index is already in use.
assert_eq!(
    tree.insert(100, the_answer, GFP_KERNEL).unwrap_err().cause,
    InsertErrorKind::Occupied,
);

Source

pub fn insert_range<R>( &self, range: R, value: T, gfp: Flags, ) -> Result<(), InsertError<T>>
where R: RangeBounds<usize>,

Insert a value to the specified range, failing on overlap.

This accepts the usual types of Rust ranges using the .. and ..= syntax for exclusive and inclusive ranges respectively. The range must not be empty, and must not overlap with any existing range.

§Errors

If the maple tree already contains an overlapping range, then this call will return an InsertErrorKind::Occupied. It may also fail if memory allocation fails or if the requested range is invalid (e.g. empty).

§Examples

use kernel::maple_tree::{InsertErrorKind, MapleTree};

let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;

let ten = KBox::new(10, GFP_KERNEL)?;
let twenty = KBox::new(20, GFP_KERNEL)?;
let the_answer = KBox::new(42, GFP_KERNEL)?;
let hundred = KBox::new(100, GFP_KERNEL)?;

// Insert the value 10 at the indices 100 to 499.
tree.insert_range(100..500, ten, GFP_KERNEL)?;

// Insert the value 20 at the indices 500 to 1000.
tree.insert_range(500..=1000, twenty, GFP_KERNEL)?;

// This will fail due to overlap with the previous range on index 1000.
assert_eq!(
    tree.insert_range(1000..1200, the_answer, GFP_KERNEL).unwrap_err().cause,
    InsertErrorKind::Occupied,
);

// When using .. to specify the range, you must be careful to ensure that the range is
// non-empty.
assert_eq!(
    tree.insert_range(72..72, hundred, GFP_KERNEL).unwrap_err().cause,
    InsertErrorKind::InvalidRequest,
);

Source

pub fn erase(&self, index: usize) -> Option<T>

Erase the range containing the given index.

§Examples

use kernel::maple_tree::MapleTree;

let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;

let ten = KBox::new(10, GFP_KERNEL)?;
let twenty = KBox::new(20, GFP_KERNEL)?;

tree.insert_range(100..500, ten, GFP_KERNEL)?;
tree.insert(67, twenty, GFP_KERNEL)?;

assert_eq!(tree.erase(67).map(|v| *v), Some(20));
assert_eq!(tree.erase(275).map(|v| *v), Some(10));

// The previous call erased the entire range, not just index 275.
assert!(tree.erase(127).is_none());