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()
271 // reallocate entries in the tree, as we otherwise have exclusive access. That feature in free_all_entries()
283 // tree. in free_all_entries()
293 // We only iterate the tree if the Rust value has a destructor. in drop()
295 // SAFETY: Other than the below `mtree_destroy` call, the tree will not be accessed in drop()
300 // SAFETY: The tree is valid, and will not be accessed after this call. in drop()
301 unsafe { bindings::mtree_destroy(self.tree.get()) }; in drop()
311 pub struct MapleGuard<'tree, T: ForeignOwnable>(&'tree MapleTree<T>);
313 impl<'tree, T: ForeignOwnable> Drop for MapleGuard<'tree, T> {
321 impl<'tree, T: ForeignOwnable> MapleGuard<'tree, T> {
325 // read/write permissions to the maple tree. in ma_state()
338 /// let tree = KBox::pin_init(MapleTree::<KBox<i32>>::new(), GFP_KERNEL)?;
342 /// tree.insert(100, ten, GFP_KERNEL)?;
343 /// tree.insert(200, twenty, GFP_KERNEL)?;
345 /// let mut lock = tree.lock();
358 /// let tree = KBox::pin_init(MapleTree::<Arc<i32>>::new(), GFP_KERNEL)?;
362 /// tree.insert(100, ten, GFP_KERNEL)?;
363 /// tree.insert(200, twenty, GFP_KERNEL)?;
366 /// let value = tree.lock().load(100).map(Arc::from);
369 /// tree.erase(100);
377 // SAFETY: `self.tree` contains a valid maple tree. in load()
378 let ret = unsafe { bindings::mtree_load(self.0.tree.get(), index) }; in load()
391 /// Create a new allocation tree.
393 let tree = pin_init!(MapleTree { in new() localVariable
394 // SAFETY: This initializes a maple tree into a pinned slot. The maple tree will be in new()
396 tree <- Opaque::ffi_init(|slot| unsafe { in new()
402 pin_init!(MapleTreeAlloc { tree <- tree }) in new()
407 /// The maple tree will search for a location in the given range where there is space to insert
417 /// let tree = KBox::pin_init(MapleTreeAlloc::<KBox<i32>>::new(), GFP_KERNEL)?;
425 /// let idx1 = tree.alloc_range(100, ten, ..1000, GFP_KERNEL)?;
426 /// let idx2 = tree.alloc_range(100, twenty, ..1000, GFP_KERNEL)?;
427 /// let idx3 = tree.alloc_range(100, thirty, ..1000, GFP_KERNEL)?;
435 /// tree.alloc_range(800, hundred, ..1000, GFP_KERNEL).unwrap_err().cause,
460 // SAFETY: The tree is valid, and we are passing a pointer to an owned instance of `T`. in alloc_range()
463 self.tree.tree.get(), in alloc_range()
495 /// For the duration of `'tree`:
498 /// * The `ma_state` has read/write access to the tree.
499 pub struct MaState<'tree, T: ForeignOwnable> {
501 _phantom: PhantomData<&'tree mut MapleTree<T>>,
504 impl<'tree, T: ForeignOwnable> MaState<'tree, T> {
505 /// Initialize a new `MaState` with the given tree.
509 /// The caller must ensure that this `MaState` has read/write access to the maple tree.
511 unsafe fn new_raw(mt: &'tree MapleTree<T>, first: usize, end: usize) -> Self { in new_raw()
513 // * Having a reference ensures that the `MapleTree<T>` is valid for `'tree`. in new_raw()
517 tree: mt.tree.get(), in new_raw()
541 // to the tree. in mas_find_raw()
545 /// Find the next entry in the maple tree.
549 /// Iterate the maple tree.
555 /// let tree = KBox::pin_init(MapleTree::<Arc<i32>>::new(), GFP_KERNEL)?;
559 /// tree.insert(100, ten, GFP_KERNEL)?;
560 /// tree.insert(200, twenty, GFP_KERNEL)?;
562 /// let mut ma_lock = tree.lock();
579 // `MaState` has read/write access to the maple tree. in find()