1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//! Generic allocator trait for tree nodes.
//!
//! This module defines [`TreeAllocator`] that abstracts over allocators
//! for different leaf policies.
use seize::LocalGuard;
use crate::leaf15::LeafNode15;
use crate::nodeversion::NodeVersion;
use crate::policy::LeafPolicy;
/// Trait for allocating and deallocating tree nodes generically.
///
/// Enables tree operations to work with any leaf policy implementing [`LeafPolicy`].
///
/// # Type Parameters
///
/// - `P`: The leaf policy implementing [`LeafPolicy`]
///
/// # Internode Handling
///
/// Internode pointers use `*mut u8` for type erasure. Implementations must ensure
/// internodes have the same WIDTH as leaves (invariant enforced by construction).
pub trait TreeAllocator<P: LeafPolicy>: Send + Sync {
// ========================================================================
// Leaf Allocation
// ========================================================================
/// Allocate a leaf node directly from the pool and initialize it in-place.
fn alloc_leaf_direct(&self, is_root: bool, is_layer_root: bool) -> *mut LeafNode15<P>;
/// Retire a leaf node for deferred reclamation.
///
/// # Safety
///
/// - `ptr` must point to a valid leaf allocated by this allocator
/// - `ptr` must be unreachable from the tree (unlinked)
unsafe fn retire_leaf(&self, ptr: *mut LeafNode15<P>, guard: &LocalGuard<'_>);
// ========================================================================
// Internode Allocation
// ========================================================================
/// Allocate an internode directly from the pool and initialize it in-place.
fn alloc_internode_direct(&self, height: u32) -> *mut u8;
/// Allocate an internode as a root node directly from the pool.
fn alloc_internode_direct_root(&self, height: u32) -> *mut u8;
/// Allocate an internode for a split operation directly from the pool.
fn alloc_internode_direct_for_split(
&self,
parent_version: &NodeVersion,
height: u32,
) -> *mut u8;
/// Retire an internode for deferred reclamation.
///
/// # Safety
///
/// - `ptr` must point to a valid internode
/// - `ptr` must be unreachable from the tree
unsafe fn retire_internode_erased(&self, ptr: *mut u8, guard: &LocalGuard<'_>);
// ========================================================================
// Tree Lifecycle
// ========================================================================
/// Teardown all reachable nodes at tree drop.
fn teardown_tree(&self, root_ptr: *mut u8);
}
// ============================================================================
// Tests
// ============================================================================
#[cfg(test)]
mod unit_tests;