Lines Matching full:tree
22 /// A maple tree optimized for storing non-overlapping ranges.
26 /// Each range in the maple tree owns an instance of `T`.
31 tree: Opaque<bindings::maple_tree>, field
35 /// A maple tree with `MT_FLAGS_ALLOC_RANGE` set.
42 tree: MapleTree<T>, field
51 &self.tree in deref()
77 /// Create a new maple tree.
79 /// The tree will use the regular implementation with a higher branching factor, rather than
80 /// the allocation tree.
84 // SAFETY: This initializes a maple tree into a pinned slot. The maple tree will be in new()
86 tree <- Opaque::ffi_init(|slot| unsafe { bindings::mt_init_flags(slot, 0) }), in new()
95 /// If the maple tree already contains a range using the given index, then this call will
103 /// let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;
110 /// tree.insert(100, ten, GFP_KERNEL)?;
111 /// tree.insert(101, twenty, GFP_KERNEL)?;
115 /// tree.insert(100, the_answer, GFP_KERNEL).unwrap_err().cause,
133 /// If the maple tree already contains an overlapping range, then this call will return an
142 /// let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;
150 /// tree.insert_range(100..500, ten, GFP_KERNEL)?;
153 /// tree.insert_range(500..=1000, twenty, GFP_KERNEL)?;
157 /// tree.insert_range(1000..1200, the_answer, GFP_KERNEL).unwrap_err().cause,
164 /// tree.insert_range(72..72, hundred, GFP_KERNEL).unwrap_err().cause,
182 // SAFETY: The tree is valid, and we are passing a pointer to an owned instance of `T`. in insert_range()
184 bindings::mtree_insert_range(self.tree.get(), first, last, ptr, gfp.as_raw()) in insert_range()
211 /// let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;
216 /// tree.insert_range(100..500, ten, GFP_KERNEL)?;
217 /// tree.insert(67, twenty, GFP_KERNEL)?;
219 /// assert_eq!(tree.erase(67).map(|v| *v), Some(20));
220 /// assert_eq!(tree.erase(275).map(|v| *v), Some(10));
223 /// assert!(tree.erase(127).is_none());
228 // SAFETY: `self.tree` contains a valid maple tree. in erase()
229 let ret = unsafe { bindings::mtree_erase(self.tree.get(), index) }; in erase()
232 // from the tree. in erase()
239 // SAFETY: It's safe to lock the spinlock in a maple tree. in lock()
249 let lock_ptr = unsafe { &raw mut (*self.tree.get()).__bindgen_anon_1.ma_lock }; in ma_lock()
253 /// Free all `T` instances in this tree.
257 /// This frees Rust data referenced by the maple tree without removing it from the maple tree,
261 // SAFETY: The caller provides exclusive access to the entire maple tree, so we have in free_all_entries()
262 // exclusive access to the entire maple tree despite not holding the lock. in free_all_entries()
267 // from the maple tree, which is only valid because this is the destructor. in free_all_entries()
274 // tree. in free_all_entries()
284 // We only iterate the tree if the Rust value has a destructor. in drop()
286 // SAFETY: Other than the below `mtree_destroy` call, the tree will not be accessed in drop()
291 // SAFETY: The tree is valid, and will not be accessed after this call. in drop()
292 unsafe { bindings::mtree_destroy(self.tree.get()) }; in drop()
302 pub struct MapleGuard<'tree, T: ForeignOwnable>(&'tree MapleTree<T>);
304 impl<'tree, T: ForeignOwnable> Drop for MapleGuard<'tree, T> {
312 impl<'tree, T: ForeignOwnable> MapleGuard<'tree, T> {
316 // read/write permissions to the maple tree. in ma_state()
329 /// let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;
333 /// tree.insert(100, ten, GFP_KERNEL)?;
334 /// tree.insert(200, twenty, GFP_KERNEL)?;
336 /// let mut lock = tree.lock();
349 /// let tree = KBox::pin_init(MapleTree::<Arc<i32>>::new(), GFP_KERNEL)?;
353 /// tree.insert(100, ten, GFP_KERNEL)?;
354 /// tree.insert(200, twenty, GFP_KERNEL)?;
357 /// let value = tree.lock().load(100).map(Arc::from);
360 /// tree.erase(100);
368 // SAFETY: `self.tree` contains a valid maple tree. in load()
369 let ret = unsafe { bindings::mtree_load(self.0.tree.get(), index) }; in load()
382 /// Create a new allocation tree.
384 let tree = pin_init!(MapleTree { in new() localVariable
385 // SAFETY: This initializes a maple tree into a pinned slot. The maple tree will be in new()
387 tree <- Opaque::ffi_init(|slot| unsafe { in new()
393 pin_init!(MapleTreeAlloc { tree <- tree }) in new()
398 /// The maple tree will search for a location in the given range where there is space to insert
408 /// let tree = KBox::pin_init(MapleTreeAlloc::<KBox<i32>>::new(), GFP_KERNEL)?;
416 /// let idx1 = tree.alloc_range(100, ten, ..1000, GFP_KERNEL)?;
417 /// let idx2 = tree.alloc_range(100, twenty, ..1000, GFP_KERNEL)?;
418 /// let idx3 = tree.alloc_range(100, thirty, ..1000, GFP_KERNEL)?;
426 /// tree.alloc_range(800, hundred, ..1000, GFP_KERNEL).unwrap_err().cause,
451 // SAFETY: The tree is valid, and we are passing a pointer to an owned instance of `T`. in alloc_range()
454 self.tree.tree.get(), in alloc_range()
486 /// For the duration of `'tree`:
489 /// * The `ma_state` has read/write access to the tree.
490 pub struct MaState<'tree, T: ForeignOwnable> {
492 _phantom: PhantomData<&'tree mut MapleTree<T>>,
495 impl<'tree, T: ForeignOwnable> MaState<'tree, T> {
496 /// Initialize a new `MaState` with the given tree.
500 /// The caller must ensure that this `MaState` has read/write access to the maple tree.
502 unsafe fn new_raw(mt: &'tree MapleTree<T>, first: usize, end: usize) -> Self { in new_raw()
504 // * Having a reference ensures that the `MapleTree<T>` is valid for `'tree`. in new_raw()
508 tree: mt.tree.get(), in new_raw()
532 // to the tree. in mas_find_raw()
536 /// Find the next entry in the maple tree.
540 /// Iterate the maple tree.
546 /// let tree = KBox::pin_init(MapleTree::<Arc<i32>>::new(), GFP_KERNEL)?;
550 /// tree.insert(100, ten, GFP_KERNEL)?;
551 /// tree.insert(200, twenty, GFP_KERNEL)?;
553 /// let mut ma_lock = tree.lock();
570 // `MaState` has read/write access to the maple tree. in find()