Struct XArray 

pub struct XArray<T: ForeignOwnable, const SHIFT: usize, const SIZE: usize> { /* private fields */ }

An extensible array backed by a radix tree, mapping usize indices to Entry values.

T must be a ForeignOwnable whose FOREIGN_ALIGN is at least 4. The type can be named with any other T, but constructing a value of it fails to compile.

Ownership

When an XArray is dropped, all stored Entry::Pointer entries are freed via ForeignOwnable::from_foreign(). This differs from the C xa_destroy(), which only frees internal nodes and requires callers to free stored pointers themselves. Entry::Int entries are encoded integers with no backing allocation and need no cleanup.

Examples

use kernel::alloc::{flags, KBox};
use kernel::rxarray::{BorrowedEntry, Entry, XArray6};

let mut xa = XArray6::<KBox<u64>>::new();
assert!(xa.is_empty());

// Store a pointer entry at index 1.
let boxed = KBox::new(0xbeef_u64, flags::GFP_KERNEL)?;
xa.store(1, Entry::Pointer(boxed), flags::GFP_KERNEL)?;
match xa.load(1) {
    Some(BorrowedEntry::Pointer(val)) => assert_eq!(*val, 0xbeef_u64),
    _ => panic!("expected Pointer"),
}

// Store a value entry at index 0.
let old = xa.store(0, Entry::int::<0xdead>(), flags::GFP_KERNEL)?;
assert!(old.is_none());
assert!(!xa.is_empty());

match xa.load(0) {
    Some(BorrowedEntry::Int(v)) => assert_eq!(v, 0xdead),
    _ => panic!("expected Int"),
}

let old = xa.store(0, Entry::int::<0xcafe>(), flags::GFP_KERNEL)?;
match old {
    Some(Entry::Int(v)) => assert_eq!(v, 0xdead),
    _ => panic!("expected old Int"),
}

match xa.erase(0) {
    Some(Entry::Int(v)) => assert_eq!(v, 0xcafe),
    _ => panic!("expected erased Int"),
}
assert!(xa.erase(1).is_some());
assert!(xa.is_empty());

Invariants

• T::FOREIGN_ALIGN >= 4, ensuring pointer entries do not collide with the integer or internal entry encoding.
• SHIFT > 0 and SIZE == 1 << SHIFT.
• Every slot in every node satisfies the Slot invariants.
• Interior levels (level > 0) contain only empty or node slots. Leaf level (level 0) contains only empty, Int, or Pointer slots.
• The subtree below every node slot contains at least one of the Entry types (Int or Pointer).

Implementations

impl<T: ForeignOwnable, const SHIFT: usize, const SIZE: usize> XArray<T, SHIFT, SIZE>

pub const fn new() -> Self

Creates a new empty XArray.

pub fn is_empty(&self) -> bool

Returns true if the tree contains no entries.

Scanning the root node suffices: by the type invariants, every node slot in it leads to at least one entry.

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

Erases the entry at index.

Returns the previous entry, or None if the slot was empty. Empty intermediate nodes are freed during traversal.

pub fn store( &mut self, index: usize, entry: Entry<T>, flags: Flags, ) -> Result<Option<Entry<T>>, StoreError<T>>

Stores an entry at index.

Returns the previous entry, or None if the slot was empty.

Errors

Returns a StoreError carrying the entry back to the caller, with error ENOMEM if a new intermediate node cannot be allocated. A failed stored leaves the tree unchanged. For C callers, EINVAL in case of tree corruption detection.

pub fn load(&self, index: usize) -> Option<BorrowedEntry<'_, T>>

Loads the entry at index.

Returns None if the slot is empty. The returned BorrowedEntry is a value that borrows from the array where pointer entries carry T::Borrowed<'_> (e.g., &T for KBox<T>), and integer entries carry a copy of the Value.

pub fn load_mut(&mut self, index: usize) -> Option<BorrowedEntryMut<'_, T>>

Loads the entry at index for mutation.

Returns None if the slot is empty. The returned BorrowedEntryMut is a value that borrows from the array where pointer entries carry T::BorrowedMut<'_> (e.g., &mut T for KBox<T>), and integer entries carry a copy of the Value.

Trait Implementations

impl<T: ForeignOwnable, const SHIFT: usize, const SIZE: usize> Default for XArray<T, SHIFT, SIZE>

fn default() -> Self

Returns the “default value” for a type.