// 这是遵循理想的实现的尝试
//
// ```
// struct BTreeMap<K, V> {
//     height: usize,
//     root: Option<Box<Node<K, V, height>>>
// }
//
// struct Node<K, V, height: usize> {
//     keys: [K; 2 * B - 1],
//     vals: [V; 2 * B - 1],
//     edges: [if height > 0 { Box<Node<K, V, height - 1>> } else { () }; 2 * B],
//     parent: Option<(NonNull<Node<K, V, height + 1>>, u16)>,
//     len: u16,
// }
// ```
//
// 由于 Rust 实际上没有依赖类型和多态递归，因此我们可以避免很多不安全因素。
//

// 本模块的一个主要目标是通过将树视为一个通用的 (如果形状怪异) 容器来避免复杂性，并避免处理大多数 B 树的不变量。
//
// 这样，该模块不在乎条目是否已排序，哪些节点可能不足，甚至是不足意味着什么。但是，我们确实依赖于一些不变量：
//
// - 树木必须具有统一的 depth/height。这意味着从给定节点到叶子的每条路径都具有完全相同的长度。
// - 长度为 `n` 的节点具有 `n` 键，`n` 值和 `n + 1` edges。
//   这意味着即使一个空节点也至少具有一个 edge。
//   对于叶子节点，"有一个 edge" 仅意味着我们可以标识节点中的位置，因为叶 edges 为空并且不需要数据表示。
// 在内部节点中，edge 既标识位置又包含指向子例程的指针。
//
//
//

use core::marker::PhantomData;
use core::mem::{self, MaybeUninit};
use core::ptr::{self, NonNull};
use core::slice::SliceIndex;

use crate::alloc::{Allocator, Layout};
use crate::boxed::Box;

const B: usize = 6;
pub const CAPACITY: usize = 2 * B - 1;
pub const MIN_LEN_AFTER_SPLIT: usize = B - 1;
const KV_IDX_CENTER: usize = B - 1;
const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
const EDGE_IDX_RIGHT_OF_CENTER: usize = B;

/// 叶节点的底层表示和内部节点的部分表示。
struct LeafNode<K, V> {
    /// 我们希望在 `K` 和 `V` 中是协变的。
    parent: Option<NonNull<InternalNode<K, V>>>,

    /// 该节点到父节点的 `edges` 数组的索引。
    /// `*node.parent.edges[node.parent_idx]` 应该与 `node` 相同。
    /// 仅当 `parent` 不为 null 时，才保证将其初始化。
    parent_idx: MaybeUninit<u16>,

    /// 此节点存储的键和值的数量。
    len: u16,

    /// 存储节点实际数据的数组。
    /// 每个数组中只有前 `len` 个元素被初始化并有效。
    keys: [MaybeUninit<K>; CAPACITY],
    vals: [MaybeUninit<V>; CAPACITY],
}

impl<K, V> LeafNode<K, V> {
    /// 就地初始化一个新的 `LeafNode`。
    unsafe fn init(this: *mut Self) {
        // 根据一般政策，如果可以的话，我们会保留未初始化的字段，因为这应该在 Valgrind 中更快，更轻松地进行跟踪。
        //
        unsafe {
            // parent_idx，键和 val 都是 MaybeUninit
            ptr::addr_of_mut!((*this).parent).write(None);
            ptr::addr_of_mut!((*this).len).write(0);
        }
    }

    /// 创建一个新的 boxed `LeafNode`。
    fn new<A: Allocator + Clone>(alloc: A) -> Box<Self, A> {
        unsafe {
            let mut leaf = Box::new_uninit_in(alloc);
            LeafNode::init(leaf.as_mut_ptr());
            leaf.assume_init()
        }
    }
}

/// 内部节点的底层表示。与 `LeafNode`s 一样，它们应该隐藏在 `BoxedNode`s 的后面，以防止丢弃未初始化的键和值。
/// 任何指向 `InternalNode` 的指针都可以直接转换为指向节点底层 `LeafNode` 部分的指针，从而允许代码在一般情况下作用于叶子节点和内部节点，甚至无需检查指针指向的两个节点中的哪一个。
///
/// 通过使用 `repr(C)` 启用此属性。
///
#[repr(C)]
// gdb_providers.py 使用此类型名称进行内省。
struct InternalNode<K, V> {
    data: LeafNode<K, V>,

    /// 指向此节点的子代的指针。
    /// 其中的 `len + 1` 被认为是初始化和有效的，除了接近尾端，而树是通过借用类型 `Dying` 保持的，其中一些指针是悬垂。
    ///
    edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
}

impl<K, V> InternalNode<K, V> {
    /// 创建一个新的 boxed `InternalNode`。
    ///
    /// # Safety
    /// 内部节点的不变性是它们至少具有一个初始化且有效的 edge。
    /// 此函数未设置这样的 edge。
    ///
    unsafe fn new<A: Allocator + Clone>(alloc: A) -> Box<Self, A> {
        unsafe {
            let mut node = Box::<Self, _>::new_uninit_in(alloc);
            // 我们只需要初始化数据即可。edges 是 MaybeUninit。
            LeafNode::init(ptr::addr_of_mut!((*node.as_mut_ptr()).data));
            node.assume_init()
        }
    }
}

/// 指向节点的托管非空指针。这可以是指向 `LeafNode<K, V>` 的拥有的指针，也可以是指向 `InternalNode<K, V>` 的拥有的指针。
///
/// 但是，`BoxedNode` 不包含有关它实际包含的两种类型的节点中的哪一种的信息，并且部分由于缺少此信息，它不是单独的类型，也没有析构函数。
///
///
///
type BoxedNode<K, V> = NonNull<LeafNode<K, V>>;

// N.B. `NodeRef` 在 `K` 和 `V` 中始终是协变的，即使 `BorrowType` 是 `Mut`。
// 这在技术上是错误的，但是由于内部使用 `NodeRef` 不会导致任何安全隐患，因为我们在 `K` 和 `V` 上完全保持泛型。
//
// 但是，每当公共类型包装 `NodeRef` 时，请确保其具有正确的方差。
//
/// 对节点的引用。
///
/// 此类型具有许多控制其行为的参数：
/// - `BorrowType`: 描述借用种类，携带生命周期的虚拟类型。
///    - 当它是 `Immut<'a>` 时，`NodeRef` 的行为大致类似于 `&'a Node`。
///    - 当这是 `ValMut<'a>` 时，就键和树结构体而言，`NodeRef` 的行为大致类似于 `&'a Node`，但是还允许对整个树的值进行许多引用来共存。
///    - 当这是 `Mut<'a>` 时，尽管插入方法允许指向值的可变指针共存，但 `NodeRef` 的行为大致类似于 `&'a mut Node`。
///    - 当它是 `Owned` 时，`NodeRef` 的行为大致类似于 `Box<Node>`，但没有析构函数，必须手动清理。
///    - 当这是 `Dying` 时，`NodeRef` 的行为仍大致类似于 `Box<Node>`，但具有逐点销毁树的方法，并且普通方法 (虽然未标记为对调用不安全)，但如果调用不正确，则可以调用 UB。
///
///   由于任何 `NodeRef` 都允许在树中导航，因此 `BorrowType` 有效地应用于整个树，而不仅仅是节点本身。
/// - `K` 和 `V`: 这些是存储在节点中的键和值的类型。
/// - `Type`: 这可以是 `Leaf`、`Internal` 或 `LeafOrInternal`。
/// 当这是 `Leaf` 时，`NodeRef` 指向叶子节点; 当这是 `Internal` 时，`NodeRef` 指向内部节点; 当这是 `LeafOrInternal` 时，`NodeRef` 可能指向任一类型的节点。
///   `Type` 在 `NodeRef` 外使用时称为 `NodeType`。
///
/// `BorrowType` 和 `NodeType` 都限制了我们实现哪种方法以利用静态类型安全性。我们应用此类限制的方式存在一些限制：
/// - 对于每个类型参数，我们只能通用地或针对一种特定类型定义一种方法。
/// 例如，我们不能为所有 `BorrowType` 定义一个类似 `into_kv` 的方法，也不能为所有带有生命周期的类型定义一个方法，因为我们希望它返回 `&'a` 引用。
///   因此，我们仅针对功能最弱的 `Immut<'a>` 定义它。
/// - 从 `Mut<'a>` 到 `Immut<'a>`，我们无法获得隐式强制转换。
///   因此，我们必须在功能更强大的 `NodeRef` 上显式调用 `reborrow`，才能达到像 `into_kv` 这样的方法。
///
/// `NodeRef` 上所有返回某种引用的方法，或者：
/// - 按值取 `self`，然后返回 `BorrowType` 携带的生命周期。
///   有时，要调用这种方法，我们需要调用 `reborrow_mut`。
/// - 将 `self` 乘以引用，然后 (implicitly) 返回该引用的生命周期，而不是 `BorrowType` 携带的生命周期。
/// 这样，借用检查器保证 `NodeRef` 保持借用状态，只要使用返回的引用即可。
///   支持插入的方法通过返回一个裸指针，即一个没有任何生命周期的引用来改变这个规则。
///
///
///
///
///
///
///
///
///
///
///
///
///
///
///
///
///
pub struct NodeRef<BorrowType, K, V, Type> {
    /// 节点的级别数和叶子的级别分开，`Type` 无法完全描述该节点的常量，并且该节点本身不存储。
    /// 我们只需要存储根节点的高度，并从中导出所有其他节点的高度。
    /// 如果 `Type` 为 `Leaf`，则必须为零; 如果 `Type` 为 `Internal`，则必须为非零。
    ///
    ///
    height: usize,
    /// 指向叶或内部节点的指针。
    /// `InternalNode` 的定义可确保该指针有效。
    node: NonNull<LeafNode<K, V>>,
    _marker: PhantomData<(BorrowType, Type)>,
}

/// 拥有所有权的树的根节点。
///
/// 请注意，它没有析构函数，必须手动清理。
pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;

impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
    fn clone(&self) -> Self {
        *self
    }
}

unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}

unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {}
unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {}
unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {}
unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {}

impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
    pub fn new_leaf<A: Allocator + Clone>(alloc: A) -> Self {
        Self::from_new_leaf(LeafNode::new(alloc))
    }

    fn from_new_leaf<A: Allocator + Clone>(leaf: Box<LeafNode<K, V>, A>) -> Self {
        NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData }
    }
}

impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
    fn new_internal<A: Allocator + Clone>(child: Root<K, V>, alloc: A) -> Self {
        let mut new_node = unsafe { InternalNode::new(alloc) };
        new_node.edges[0].write(child.node);
        unsafe { NodeRef::from_new_internal(new_node, child.height + 1) }
    }

    /// # Safety
    /// `height` 不能为零。
    unsafe fn from_new_internal<A: Allocator + Clone>(
        internal: Box<InternalNode<K, V>, A>,
        height: usize,
    ) -> Self {
        debug_assert!(height > 0);
        let node = NonNull::from(Box::leak(internal)).cast();
        let mut this = NodeRef { height, node, _marker: PhantomData };
        this.borrow_mut().correct_all_childrens_parent_links();
        this
    }
}

impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
    /// 取消一个被包装为 `NodeRef::parent` 的节点引用。
    fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
        debug_assert!(height > 0);
        NodeRef { height, node: node.cast(), _marker: PhantomData }
    }
}

impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
    /// 公开内部节点的数据。
    ///
    /// 返回原始 ptr，以避免使对该节点的其他引用无效。
    fn as_internal_ptr(this: &Self) -> *mut InternalNode<K, V> {
        // SAFETY: 静态节点类型为 `Internal`。
        this.node.as_ptr() as *mut InternalNode<K, V>
    }
}

impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
    /// 借用独占访问内部节点的数据。
    fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
        let ptr = Self::as_internal_ptr(self);
        unsafe { &mut *ptr }
    }
}

impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
    /// 查找节点的长度。这是键或值的数量。
    /// edges 的数量为 `len() + 1`。
    /// 请注意，尽管安全，但调用此函数可能会产生使不安全代码已创建的变量引用无效的副作用。
    ///
    pub fn len(&self) -> usize {
        // 重要的是，我们仅在此处访问 `len` 字段。
        // 如果 BorrowType 为 marker::ValMut，则对于我们不能使之无效的值，可能会有突出的变量引用。
        unsafe { usize::from((*Self::as_leaf_ptr(self)).len) }
    }

    /// 返回节点和叶子分开的级别数。
    /// 零高度表示节点本身就是叶。
    /// 如果您将树的根放在顶部，则数字表示该节点出现在哪个海拔高度。
    /// 如果您在树上画上有叶子的树，则数字表示树在节点上方延伸的高度。
    ///
    pub fn height(&self) -> usize {
        self.height
    }

    /// 临时取出另一个到同一节点。
    pub fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }

    /// 暴露任何叶子节点或内部节点的叶子部分。
    ///
    /// 返回原始 ptr，以避免使对该节点的其他引用无效。
    fn as_leaf_ptr(this: &Self) -> *mut LeafNode<K, V> {
        // 该节点必须至少对 LeafNode 部分有效。
        // 这不是 NodeRef 类型的引用，因为我们不知道它应该是唯一的还是共享的。
        //
        this.node.as_ptr()
    }
}

impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
    /// 查找当前节点的父节点。
    /// 如果当前节点实际上有一个父节点，则返回 `Ok(handle)`，其中 `handle` 指向指向当前节点的父节点的 edge。
    ///
    /// 如果当前节点没有父节点，则返回 `Err(self)`，并返回原始 `NodeRef`。
    ///
    /// 方法名称假定您在树的根节点位于顶部。
    ///
    /// `edge.descend().ascend().unwrap()` 和 `node.ascend().unwrap().descend()` 都应该在成功后什么都不做。
    ///
    pub fn ascend(
        self,
    ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
        const {
            assert!(BorrowType::TRAVERSAL_PERMIT);
        }

        // 我们需要对节点使用裸指针，因为如果 BorrowType 为 marker::ValMut，则对于我们不能使之无效的值，可能会有显着的可变引用。
        //
        let leaf_ptr: *const _ = Self::as_leaf_ptr(&self);
        unsafe { (*leaf_ptr).parent }
            .as_ref()
            .map(|parent| Handle {
                node: NodeRef::from_internal(*parent, self.height + 1),
                idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
                _marker: PhantomData,
            })
            .ok_or(self)
    }

    pub fn first_edge(self) -> Handle<Self, marker::Edge> {
        unsafe { Handle::new_edge(self, 0) }
    }

    pub fn last_edge(self) -> Handle<Self, marker::Edge> {
        let len = self.len();
        unsafe { Handle::new_edge(self, len) }
    }

    /// 请注意，`self` 必须为非空。
    pub fn first_kv(self) -> Handle<Self, marker::KV> {
        let len = self.len();
        assert!(len > 0);
        unsafe { Handle::new_kv(self, 0) }
    }

    /// 请注意，`self` 必须为非空。
    pub fn last_kv(self) -> Handle<Self, marker::KV> {
        let len = self.len();
        assert!(len > 0);
        unsafe { Handle::new_kv(self, len - 1) }
    }
}

impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
    /// 可以是 PartialEq 的公共实现，但仅在此模块中使用。
    fn eq(&self, other: &Self) -> bool {
        let Self { node, height, _marker } = self;
        if node.eq(&other.node) {
            debug_assert_eq!(*height, other.height);
            true
        } else {
            false
        }
    }
}

impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
    /// 暴露不可变树中任何叶子或内部节点的叶子部分。
    fn into_leaf(self) -> &'a LeafNode<K, V> {
        let ptr = Self::as_leaf_ptr(&self);
        // SAFETY: 借给 `Immut` 的树不能有任何可变引用。
        unsafe { &*ptr }
    }

    /// 借用查看存储在节点中的键。
    pub fn keys(&self) -> &[K] {
        let leaf = self.into_leaf();
        unsafe {
            MaybeUninit::slice_assume_init_ref(leaf.keys.get_unchecked(..usize::from(leaf.len)))
        }
    }
}

impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
    /// 与 `ascend` 相似，获取对节点父节点的引用，但也会在此进程中释放当前节点。
    /// 这是不安全的，因为尽管当前节点已被释放，但仍将可访问。
    ///
    pub unsafe fn deallocate_and_ascend<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Internal>, marker::Edge>> {
        let height = self.height;
        let node = self.node;
        let ret = self.ascend().ok();
        unsafe {
            alloc.deallocate(
                node.cast(),
                if height > 0 {
                    Layout::new::<InternalNode<K, V>>()
                } else {
                    Layout::new::<LeafNode<K, V>>()
                },
            );
        }
        ret
    }
}

impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
    /// 临时取出对同一节点的另一个可变引用。请注意，因为这种方法非常危险，所以加倍危险，因为它可能不会立即出现危险。
    ///
    /// 因为可变指针可以在树的任何位置漫游，所以返回的指针可以很容易地用于使原始指针悬垂，越界或在堆叠借用规则下无效。
    ///
    ///
    ///
    ///
    // FIXME(@gereeter) 考虑向 `NodeRef` 添加另一个类型参数，限制在重新借用的指针上使用导航方法，防止这种不安全。
    //
    //
    unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }

    /// 借用对叶子或内部节点的叶子部分的独占访问权。
    fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
        let ptr = Self::as_leaf_ptr(self);
        // SAFETY: 我们拥有对整个节点的独占访问权。
        unsafe { &mut *ptr }
    }

    /// 提供对叶子或内部节点的叶子部分的独占访问。
    fn into_leaf_mut(mut self) -> &'a mut LeafNode<K, V> {
        let ptr = Self::as_leaf_ptr(&mut self);
        // SAFETY: 我们拥有对整个节点的独占访问权。
        unsafe { &mut *ptr }
    }

    /// 返回此节点的休眠副本及其生命周期 erased，稍后可以重新唤醒。
    ///
    pub fn dormant(&self) -> NodeRef<marker::DormantMut, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }
}

impl<K, V, Type> NodeRef<marker::DormantMut, K, V, Type> {
    /// 恢复为最初捕获的唯一借用。
    ///
    /// # Safety
    ///
    /// 重新借用必须已经结束，即不再使用 `new` 返回的引用以及从该指针派生的所有指针和引用。
    ///
    pub unsafe fn awaken<'a>(self) -> NodeRef<marker::Mut<'a>, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }
}

impl<K, V, Type> NodeRef<marker::Dying, K, V, Type> {
    /// 借用对 dying 叶子或内部节点的叶子部分的独占访问。
    fn as_leaf_dying(&mut self) -> &mut LeafNode<K, V> {
        let ptr = Self::as_leaf_ptr(self);
        // SAFETY: 我们拥有对整个节点的独占访问权。
        unsafe { &mut *ptr }
    }
}

impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
    /// 借用独占访问密钥存储区中的某个元素。
    ///
    /// # Safety
    /// `index` 在 0..CAPACITY 的范围内
    unsafe fn key_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
    where
        I: SliceIndex<[MaybeUninit<K>], Output = Output>,
    {
        // SAFETY: 在丢弃切片引用之前，调用者将不能调用 self 上的其他方法，因为我们对借用的生命周期具有唯一的访问权。
        //
        //
        unsafe { self.as_leaf_mut().keys.as_mut_slice().get_unchecked_mut(index) }
    }

    /// 借用对节点的值存储区的元素或切片的唯一的访问权。
    ///
    /// # Safety
    /// `index` 在 0..CAPACITY 的范围内
    unsafe fn val_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
    where
        I: SliceIndex<[MaybeUninit<V>], Output = Output>,
    {
        // SAFETY: 在值切片引用被丢弃之前，调用者将无法在 self 上调用更多方法，因为我们在借用的生命周期内拥有唯一的访问权限。
        //
        //
        unsafe { self.as_leaf_mut().vals.as_mut_slice().get_unchecked_mut(index) }
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
    /// 借用对 edge 内容的节点存储区域的元素或切片的独占访问权。
    ///
    /// # Safety
    /// `index` 在 0..CAPACITY + 1 的范围内
    unsafe fn edge_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
    where
        I: SliceIndex<[MaybeUninit<BoxedNode<K, V>>], Output = Output>,
    {
        // SAFETY: 在丢弃 edge 切片引用之前，调用者将无法自行调用其他方法，因为我们对借用的生命周期具有唯一的访问权。
        //
        //
        unsafe { self.as_internal_mut().edges.as_mut_slice().get_unchecked_mut(index) }
    }
}

impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> {
    /// # Safety
    /// - 该节点具有多个 `idx` 初始化的元素。
    unsafe fn into_key_val_mut_at(mut self, idx: usize) -> (&'a K, &'a mut V) {
        // 我们仅对我们感兴趣的一个元素创建一个引用，以避免对其他元素 (特别是在较早的迭代中返回给调用者的那些元素) 使用突出的引用而造成别名。
        //
        //
        let leaf = Self::as_leaf_ptr(&mut self);
        let keys = unsafe { ptr::addr_of!((*leaf).keys) };
        let vals = unsafe { ptr::addr_of_mut!((*leaf).vals) };
        // 由于 Rust issue #74679，我们必须强制使用未定义大小的数组指针。
        let keys: *const [_] = keys;
        let vals: *mut [_] = vals;
        let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
        let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() };
        (key, val)
    }
}

impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
    /// 借用独占访问该节点的长度。
    pub fn len_mut(&mut self) -> &mut u16 {
        &mut self.as_leaf_mut().len
    }
}

impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
    /// # Safety
    /// `range` 返回的每个项都是该节点的有效 edge 索引。
    unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) {
        for i in range {
            debug_assert!(i <= self.len());
            unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link();
        }
    }

    fn correct_all_childrens_parent_links(&mut self) {
        let len = self.len();
        unsafe { self.correct_childrens_parent_links(0..=len) };
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
    /// 将节点的链接设置为其父级 edge，而不会使对该节点的其他引用无效。
    ///
    fn set_parent_link(&mut self, parent: NonNull<InternalNode<K, V>>, parent_idx: usize) {
        let leaf = Self::as_leaf_ptr(self);
        unsafe { (*leaf).parent = Some(parent) };
        unsafe { (*leaf).parent_idx.write(parent_idx as u16) };
    }
}

impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
    /// 清除根节点到其父 edge 的链接。
    fn clear_parent_link(&mut self) {
        let mut root_node = self.borrow_mut();
        let leaf = root_node.as_leaf_mut();
        leaf.parent = None;
    }
}

impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
    /// 返回一个新的拥有的树，其树的根节点最初为空。
    pub fn new<A: Allocator + Clone>(alloc: A) -> Self {
        NodeRef::new_leaf(alloc).forget_type()
    }

    /// 添加一个新的内部节点，该节点的单个 edge 指向先前的根节点，使该新节点成为根节点，然后将其返回。
    /// 这会使高度增加 1，与 `pop_internal_level` 相反。
    ///
    pub fn push_internal_level<A: Allocator + Clone>(
        &mut self,
        alloc: A,
    ) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
        super::mem::take_mut(self, |old_root| NodeRef::new_internal(old_root, alloc).forget_type());

        // `self.borrow_mut()`，只是我们忘记了我们现在是内部的：
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }

    /// 使用第一个子节点作为新的根节点，删除内部根节点。
    /// 由于仅在根节点只有一个子节点时才调用它，因此不会对任何键，值和其他子节点进行清理。
    ///
    /// 这会将高度减小 1，与 `push_internal_level` 相反。
    ///
    /// 需要对 `NodeRef` 对象的独占访问，而不是对根节点的独占访问；
    /// 它不会使其他句柄或对根节点的引用无效。
    ///
    /// 如果没有内部级别，即如果根节点是叶，就会出现 panics。
    pub fn pop_internal_level<A: Allocator + Clone>(&mut self, alloc: A) {
        assert!(self.height > 0);

        let top = self.node;

        // SAFETY: 我们断言是内部的。
        let internal_self = unsafe { self.borrow_mut().cast_to_internal_unchecked() };
        // SAFETY: 我们是专门借用 `self` 的，而借用类型是专有的。
        let internal_node = unsafe { &mut *NodeRef::as_internal_ptr(&internal_self) };
        // SAFETY: 第一个 edge 总是被初始化。
        self.node = unsafe { internal_node.edges[0].assume_init_read() };
        self.height -= 1;
        self.clear_parent_link();

        unsafe {
            alloc.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>());
        }
    }
}

impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> {
    /// 相互借用拥有的根节点。
    /// 与 `reborrow_mut` 不同，这是安全的，因为返回值不能用于销毁 root，并且树上不能有其他引用。
    ///
    pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }

    /// 稍微可变地借用拥有的根节点。
    pub fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }

    /// 不可逆地转换为允许遍历并提供破坏性方法的引用。
    ///
    pub fn into_dying(self) -> NodeRef<marker::Dying, K, V, Type> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
    /// 在节点末尾添加一个键值对，并返回插入值的可变引用。
    ///
    pub fn push(&mut self, key: K, val: V) -> &mut V {
        let len = self.len_mut();
        let idx = usize::from(*len);
        assert!(idx < CAPACITY);
        *len += 1;
        unsafe {
            self.key_area_mut(idx).write(key);
            self.val_area_mut(idx).write(val)
        }
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
    /// 将一个键 - 值对以及一个 edge 添加到该对的右侧 (在该节点的末尾)。
    ///
    pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
        assert!(edge.height == self.height - 1);

        let len = self.len_mut();
        let idx = usize::from(*len);
        assert!(idx < CAPACITY);
        *len += 1;
        unsafe {
            self.key_area_mut(idx).write(key);
            self.val_area_mut(idx).write(val);
            self.edge_area_mut(idx + 1).write(edge.node);
            Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
        }
    }
}

impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
    /// 删除所有断言该节点是 `Leaf` 节点的静态信息。
    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }
}

impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
    /// 删除所有断言该节点是 `Internal` 节点的静态信息。
    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }
}

impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    /// 检查节点是 `Internal` 节点还是 `Leaf` 节点。
    pub fn force(
        self,
    ) -> ForceResult<
        NodeRef<BorrowType, K, V, marker::Leaf>,
        NodeRef<BorrowType, K, V, marker::Internal>,
    > {
        if self.height == 0 {
            ForceResult::Leaf(NodeRef {
                height: self.height,
                node: self.node,
                _marker: PhantomData,
            })
        } else {
            ForceResult::Internal(NodeRef {
                height: self.height,
                node: self.node,
                _marker: PhantomData,
            })
        }
    }
}

impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
    /// 不安全地向编译器断言该节点是 `Leaf` 的静态信息。
    unsafe fn cast_to_leaf_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
        debug_assert!(self.height == 0);
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }

    /// 不安全地向编译器断言该节点是 `Internal` 的静态信息。
    unsafe fn cast_to_internal_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
        debug_assert!(self.height > 0);
        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
    }
}

/// 对节点中特定键值对或 edge 的引用。
/// `Node` 参数必须是 `NodeRef`，而 `Type` 可以是 `KV` (表示键值对上的句柄) 或 `Edge` (表示 edge 上的句柄)。
///
/// 请注意，即使 `Leaf` 节点也可以具有 `Edge` 句柄。
/// 这些代表子项指针将在键 - 值对之间移动的空间，而不是表示指向子节点的指针。
/// 例如，在一个长度为 2 的节点中，将存在 3 个可能的 edge 位置 - 一个在该节点的左侧，一个在两对之间，另一个在该节点的右侧。
///
///
pub struct Handle<Node, Type> {
    node: Node,
    idx: usize,
    _marker: PhantomData<Type>,
}

impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
// 我们不需要 `#[derive(Clone)]` 的全部通用性，因为 `Node` 唯一可以被克隆的时间是当 `Node` 是不可变引用时。
//
impl<Node: Copy, Type> Clone for Handle<Node, Type> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<Node, Type> Handle<Node, Type> {
    /// 检索包含此句柄指向的 edge 或键值对的节点。
    pub fn into_node(self) -> Node {
        self.node
    }

    /// 返回此句柄在节点中的位置。
    pub fn idx(&self) -> usize {
        self.idx
    }
}

impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
    /// 在 `node` 中为键值对创建新的句柄。
    /// 不安全，因为调用者必须确保 `idx < node.len()`。
    pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
        debug_assert!(idx < node.len());

        Handle { node, idx, _marker: PhantomData }
    }

    pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
        unsafe { Handle::new_edge(self.node, self.idx) }
    }

    pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
        unsafe { Handle::new_edge(self.node, self.idx + 1) }
    }
}

impl<BorrowType, K, V, NodeType, HandleType> PartialEq
    for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
    fn eq(&self, other: &Self) -> bool {
        let Self { node, idx, _marker } = self;
        node.eq(&other.node) && *idx == other.idx
    }
}

impl<BorrowType, K, V, NodeType, HandleType>
    Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
    /// 临时取出同一位置的另一个不可变句柄。
    pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
        // 我们无法使用 Handle::new_kv 或 Handle::new_edge，因为我们不知道我们的类型
        Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
    }
}

impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
    /// 临时取出同一位置的另一个可变句柄。
    /// 请注意，因为这种方法非常危险，所以加倍危险，因为它可能不会立即出现危险。
    ///
    ///
    /// 有关详细信息，请参见 `NodeRef::reborrow_mut`。
    pub unsafe fn reborrow_mut(
        &mut self,
    ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
        // 我们无法使用 Handle::new_kv 或 Handle::new_edge，因为我们不知道我们的类型
        Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
    }

    /// 返回此句柄的休眠副本，稍后可以将其重新唤醒。
    ///
    /// 有关详细信息，请参见 `DormantMutRef`。
    pub fn dormant(&self) -> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> {
        Handle { node: self.node.dormant(), idx: self.idx, _marker: PhantomData }
    }
}

impl<K, V, NodeType, HandleType> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> {
    /// 恢复为最初捕获的唯一借用。
    ///
    /// # Safety
    ///
    /// 重新借用必须已经结束，即不再使用 `new` 返回的引用以及从该指针派生的所有指针和引用。
    ///
    pub unsafe fn awaken<'a>(self) -> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
        Handle { node: unsafe { self.node.awaken() }, idx: self.idx, _marker: PhantomData }
    }
}

impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
    /// 在 `node` 中为 edge 创建新的句柄。
    /// 不安全，因为调用者必须确保 `idx <= node.len()`。
    pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
        debug_assert!(idx <= node.len());

        Handle { node, idx, _marker: PhantomData }
    }

    pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
        if self.idx > 0 {
            Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
        } else {
            Err(self)
        }
    }

    pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
        if self.idx < self.node.len() {
            Ok(unsafe { Handle::new_kv(self.node, self.idx) })
        } else {
            Err(self)
        }
    }
}

pub enum LeftOrRight<T> {
    Left(T),
    Right(T),
}

/// 给定 edge 索引，我们要在其中插入到已满容量的节点中，计算分割点的明智 KV 索引以及执行插入的位置。
///
/// 分割点的目标是使其关键和值最终成为父节点。
/// 分割点左侧的键，值和 edges 成为左侧子级；
/// 分割点右侧的键，值和 edges 成为右子级。
fn splitpoint(edge_idx: usize) -> (usize, LeftOrRight<usize>) {
    debug_assert!(edge_idx <= CAPACITY);
    // Rust issue #74834 试图解释这些对称规则。
    match edge_idx {
        0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, LeftOrRight::Left(edge_idx)),
        EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Left(edge_idx)),
        EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Right(0)),
        _ => (KV_IDX_CENTER + 1, LeftOrRight::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))),
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
    /// 在此 edge 左右两侧的键值对之间插入新的键值对。
    /// 此方法假定节点中有足够的空间来容纳新的配对。
    ///
    unsafe fn insert_fit(
        mut self,
        key: K,
        val: V,
    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
        debug_assert!(self.node.len() < CAPACITY);
        let new_len = self.node.len() + 1;

        unsafe {
            slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
            slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
            *self.node.len_mut() = new_len as u16;

            Handle::new_kv(self.node, self.idx)
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
    /// 在此 edge 左右两侧的键值对之间插入新的键值对。
    /// 如果没有足够的空间，此方法将拆分节点。
    ///
    /// 返回一个休眠句柄到插入的节点，一旦分裂完成就可以重新唤醒。
    ///
    fn insert<A: Allocator + Clone>(
        self,
        key: K,
        val: V,
        alloc: A,
    ) -> (
        Option<SplitResult<'a, K, V, marker::Leaf>>,
        Handle<NodeRef<marker::DormantMut, K, V, marker::Leaf>, marker::KV>,
    ) {
        if self.node.len() < CAPACITY {
            // SAFETY: 节点中有足够的空间用于插入。
            let handle = unsafe { self.insert_fit(key, val) };
            (None, handle.dormant())
        } else {
            let (middle_kv_idx, insertion) = splitpoint(self.idx);
            let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
            let mut result = middle.split(alloc);
            let insertion_edge = match insertion {
                LeftOrRight::Left(insert_idx) => unsafe {
                    Handle::new_edge(result.left.reborrow_mut(), insert_idx)
                },
                LeftOrRight::Right(insert_idx) => unsafe {
                    Handle::new_edge(result.right.borrow_mut(), insert_idx)
                },
            };
            // SAFETY: 我们只是拆分节点，所以有足够的空间用于插入。
            //
            let handle = unsafe { insertion_edge.insert_fit(key, val).dormant() };
            (Some(result), handle)
        }
    }
}

impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
    /// 修复此 edge 链接到的子节点中的父指针和索引。
    /// 当 edges 的顺序已更改时，这很有用，
    fn correct_parent_link(self) {
        // 创建反向指针，而不会使对该节点的其他引用无效。
        let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
        let idx = self.idx;
        let mut child = self.descend();
        child.set_parent_link(ptr, idx);
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
    /// 在此 edge 和此 edge 右侧的键值对之间插入一个新的键值对和一个 edge，它们将位于该新对的右侧。
    /// 此方法假定节点中有足够的空间来容纳新的配对。
    ///
    fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
        debug_assert!(self.node.len() < CAPACITY);
        debug_assert!(edge.height == self.node.height - 1);
        let new_len = self.node.len() + 1;

        unsafe {
            slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
            slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
            slice_insert(self.node.edge_area_mut(..new_len + 1), self.idx + 1, edge.node);
            *self.node.len_mut() = new_len as u16;

            self.node.correct_childrens_parent_links(self.idx + 1..new_len + 1);
        }
    }

    /// 在此 edge 和此 edge 右侧的键值对之间插入一个新的键值对和一个 edge，它们将位于该新对的右侧。
    /// 如果没有足够的空间，此方法将拆分节点。
    ///
    fn insert<A: Allocator + Clone>(
        mut self,
        key: K,
        val: V,
        edge: Root<K, V>,
        alloc: A,
    ) -> Option<SplitResult<'a, K, V, marker::Internal>> {
        assert!(edge.height == self.node.height - 1);

        if self.node.len() < CAPACITY {
            self.insert_fit(key, val, edge);
            None
        } else {
            let (middle_kv_idx, insertion) = splitpoint(self.idx);
            let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
            let mut result = middle.split(alloc);
            let mut insertion_edge = match insertion {
                LeftOrRight::Left(insert_idx) => unsafe {
                    Handle::new_edge(result.left.reborrow_mut(), insert_idx)
                },
                LeftOrRight::Right(insert_idx) => unsafe {
                    Handle::new_edge(result.right.borrow_mut(), insert_idx)
                },
            };
            insertion_edge.insert_fit(key, val, edge);
            Some(result)
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
    /// 在此 edge 左右两侧的键值对之间插入新的键值对。
    /// 如果没有足够的空间，此方法将拆分节点，并尝试将拆分的部分递归插入父节点，直到到达根节点为止。
    ///
    ///
    /// 如果返回的结果是某个 `SplitResult`，则 `left` 字段将是根节点。
    /// 返回的指针指向插入的值，在 `SplitResult` 的情况下，该值位于 `left` 或 `right` 树中。
    ///
    pub fn insert_recursing<A: Allocator + Clone>(
        self,
        key: K,
        value: V,
        alloc: A,
        split_root: impl FnOnce(SplitResult<'a, K, V, marker::LeafOrInternal>),
    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
        let (mut split, handle) = match self.insert(key, value, alloc.clone()) {
            // SAFETY: 我们已经完成拆分，现在可以重新唤醒插入元素的句柄。
            //
            (None, handle) => return unsafe { handle.awaken() },
            (Some(split), handle) => (split.forget_node_type(), handle),
        };

        loop {
            split = match split.left.ascend() {
                Ok(parent) => {
                    match parent.insert(split.kv.0, split.kv.1, split.right, alloc.clone()) {
                        // SAFETY: 我们已经完成拆分，现在可以重新唤醒插入元素的句柄。
                        //
                        None => return unsafe { handle.awaken() },
                        Some(split) => split.forget_node_type(),
                    }
                }
                Err(root) => {
                    split_root(SplitResult { left: root, ..split });
                    // SAFETY: 我们已经完成拆分，现在可以重新唤醒插入元素的句柄。
                    //
                    return unsafe { handle.awaken() };
                }
            };
        }
    }
}

impl<BorrowType: marker::BorrowType, K, V>
    Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
{
    /// 查找此 edge 指向的节点。
    ///
    /// 方法名称假定您在树的根节点位于顶部。
    ///
    /// `edge.descend().ascend().unwrap()` 和 `node.ascend().unwrap().descend()` 都应该在成功后什么都不做。
    ///
    pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
        const {
            assert!(BorrowType::TRAVERSAL_PERMIT);
        }

        // 我们需要对节点使用裸指针，因为如果 BorrowType 为 marker::ValMut，则对于我们不能使之无效的值，可能会有显着的可变引用。
        // 不必担心访问 height 字段，因为该值已被复制。
        // 请注意，一旦解引用节点指针，我们将使用引用 (Rust issue #73987) 访问 edges 数组，并使该数组中或数组内的其他任何引用无效 (如果有的话)。
        //
        //
        //
        //
        let parent_ptr = NodeRef::as_internal_ptr(&self.node);
        let node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() };
        NodeRef { node, height: self.node.height - 1, _marker: PhantomData }
    }
}

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
    pub fn into_kv(self) -> (&'a K, &'a V) {
        debug_assert!(self.idx < self.node.len());
        let leaf = self.node.into_leaf();
        let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() };
        let v = unsafe { leaf.vals.get_unchecked(self.idx).assume_init_ref() };
        (k, v)
    }
}

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
    pub fn key_mut(&mut self) -> &mut K {
        unsafe { self.node.key_area_mut(self.idx).assume_init_mut() }
    }

    pub fn into_val_mut(self) -> &'a mut V {
        debug_assert!(self.idx < self.node.len());
        let leaf = self.node.into_leaf_mut();
        unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }
    }

    pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) {
        debug_assert!(self.idx < self.node.len());
        let leaf = self.node.into_leaf_mut();
        let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() };
        let v = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() };
        (k, v)
    }
}

impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> {
    pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) {
        unsafe { self.node.into_key_val_mut_at(self.idx) }
    }
}

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
    pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
        debug_assert!(self.idx < self.node.len());
        // 我们不能调用单独的键和值方法，因为调用第二个方法会使第一个方法返回的引用无效。
        //
        unsafe {
            let leaf = self.node.as_leaf_mut();
            let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_mut();
            let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_mut();
            (key, val)
        }
    }

    /// 替换 KV 句柄引用的键和值。
    pub fn replace_kv(&mut self, k: K, v: V) -> (K, V) {
        let (key, val) = self.kv_mut();
        (mem::replace(key, k), mem::replace(val, v))
    }
}

impl<K, V, NodeType> Handle<NodeRef<marker::Dying, K, V, NodeType>, marker::KV> {
    /// 提取 KV 句柄引用的键和值。
    /// # Safety
    /// 句柄所指的节点必须尚未释放。
    pub unsafe fn into_key_val(mut self) -> (K, V) {
        debug_assert!(self.idx < self.node.len());
        let leaf = self.node.as_leaf_dying();
        unsafe {
            let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_read();
            let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_read();
            (key, val)
        }
    }

    /// 丢弃 KV 句柄引用的键和值。
    /// # Safety
    /// 句柄所指的节点必须尚未释放。
    #[inline]
    pub unsafe fn drop_key_val(mut self) {
        debug_assert!(self.idx < self.node.len());
        let leaf = self.node.as_leaf_dying();
        unsafe {
            leaf.keys.get_unchecked_mut(self.idx).assume_init_drop();
            leaf.vals.get_unchecked_mut(self.idx).assume_init_drop();
        }
    }
}

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
    /// 通过处理叶数据，帮助为特定的 `NodeType` 实现 `split`。
    ///
    fn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V) {
        debug_assert!(self.idx < self.node.len());
        let old_len = self.node.len();
        let new_len = old_len - self.idx - 1;
        new_node.len = new_len as u16;
        unsafe {
            let k = self.node.key_area_mut(self.idx).assume_init_read();
            let v = self.node.val_area_mut(self.idx).assume_init_read();

            move_to_slice(
                self.node.key_area_mut(self.idx + 1..old_len),
                &mut new_node.keys[..new_len],
            );
            move_to_slice(
                self.node.val_area_mut(self.idx + 1..old_len),
                &mut new_node.vals[..new_len],
            );

            *self.node.len_mut() = self.idx as u16;
            (k, v)
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
    /// 将底层节点拆分为三个部分：
    ///
    /// - 节点被截断为仅包含此句柄左侧的键 / 值对。
    /// - 提取此句柄指向的键和值。
    /// - 该句柄右边的所有键值对都放入一个新分配的节点中。
    ///
    ///
    pub fn split<A: Allocator + Clone>(mut self, alloc: A) -> SplitResult<'a, K, V, marker::Leaf> {
        let mut new_node = LeafNode::new(alloc);

        let kv = self.split_leaf_data(&mut new_node);

        let right = NodeRef::from_new_leaf(new_node);
        SplitResult { left: self.node, kv, right }
    }

    /// 删除此句柄指向的键值对，并将其与键值对折叠到的 edge 一起返回。
    ///
    pub fn remove(
        mut self,
    ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
        let old_len = self.node.len();
        unsafe {
            let k = slice_remove(self.node.key_area_mut(..old_len), self.idx);
            let v = slice_remove(self.node.val_area_mut(..old_len), self.idx);
            *self.node.len_mut() = (old_len - 1) as u16;
            ((k, v), self.left_edge())
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
    /// 将底层节点拆分为三个部分：
    ///
    /// - 该节点被截断为仅包含此句柄左侧的 edges 和键值对。
    /// - 提取此句柄指向的键和值。
    /// - 该句柄右边的所有 edges 和键值对都放入一个新分配的节点中。
    ///
    ///
    pub fn split<A: Allocator + Clone>(
        mut self,
        alloc: A,
    ) -> SplitResult<'a, K, V, marker::Internal> {
        let old_len = self.node.len();
        unsafe {
            let mut new_node = InternalNode::new(alloc);
            let kv = self.split_leaf_data(&mut new_node.data);
            let new_len = usize::from(new_node.data.len);
            move_to_slice(
                self.node.edge_area_mut(self.idx + 1..old_len + 1),
                &mut new_node.edges[..new_len + 1],
            );

            let height = self.node.height;
            let right = NodeRef::from_new_internal(new_node, height);

            SplitResult { left: self.node, kv, right }
        }
    }
}

/// 代表一个会话，用于围绕内部键值对评估和执行平衡操作。
///
pub struct BalancingContext<'a, K, V> {
    parent: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV>,
    left_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
    right_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
}

impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
    pub fn consider_for_balancing(self) -> BalancingContext<'a, K, V> {
        let self1 = unsafe { ptr::read(&self) };
        let self2 = unsafe { ptr::read(&self) };
        BalancingContext {
            parent: self,
            left_child: self1.left_edge().descend(),
            right_child: self2.right_edge().descend(),
        }
    }
}

impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
    /// 选择一个涉及节点作为子节点的平衡上下文，从而在父节点的左 KV 或右 KV 之间进行选择。
    /// 如果没有父级，则返回 `Err`。
    /// 如果 parent 为空，就会出现 panics。
    ///
    /// 如果给定节点某种程度上不足，则最好选择左侧，这是最优的，这意味着此处仅是其元素少于其左同级，而其元素则少于其右同级 (如果存在)。
    /// 在这种情况下，与左侧同级合并更快，因为我们只需要移动节点的 N 个元素，而不是将它们向右移动并在前面移动超过 N 个元素。
    /// 从左侧同级进行窃取通常也更快，因为我们只需要将节点的 N 个元素向右移，而不是将同级元素中的至少 N 个向左移。
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    pub fn choose_parent_kv(self) -> Result<LeftOrRight<BalancingContext<'a, K, V>>, Self> {
        match unsafe { ptr::read(&self) }.ascend() {
            Ok(parent_edge) => match parent_edge.left_kv() {
                Ok(left_parent_kv) => Ok(LeftOrRight::Left(BalancingContext {
                    parent: unsafe { ptr::read(&left_parent_kv) },
                    left_child: left_parent_kv.left_edge().descend(),
                    right_child: self,
                })),
                Err(parent_edge) => match parent_edge.right_kv() {
                    Ok(right_parent_kv) => Ok(LeftOrRight::Right(BalancingContext {
                        parent: unsafe { ptr::read(&right_parent_kv) },
                        left_child: self,
                        right_child: right_parent_kv.right_edge().descend(),
                    })),
                    Err(_) => unreachable!("empty internal node"),
                },
            },
            Err(root) => Err(root),
        }
    }
}

impl<'a, K, V> BalancingContext<'a, K, V> {
    pub fn left_child_len(&self) -> usize {
        self.left_child.len()
    }

    pub fn right_child_len(&self) -> usize {
        self.right_child.len()
    }

    pub fn into_left_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
        self.left_child
    }

    pub fn into_right_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
        self.right_child
    }

    /// 返回是否可以合并，即，节点中是否有足够的空间将中央 KV 与两个相邻的子节点合并。
    ///
    pub fn can_merge(&self) -> bool {
        self.left_child.len() + 1 + self.right_child.len() <= CAPACITY
    }
}

impl<'a, K: 'a, V: 'a> BalancingContext<'a, K, V> {
    /// 执行合并，让闭包决定要返回的内容。
    fn do_merge<
        F: FnOnce(
            NodeRef<marker::Mut<'a>, K, V, marker::Internal>,
            NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
        ) -> R,
        R,
        A: Allocator,
    >(
        self,
        result: F,
        alloc: A,
    ) -> R {
        let Handle { node: mut parent_node, idx: parent_idx, _marker } = self.parent;
        let old_parent_len = parent_node.len();
        let mut left_node = self.left_child;
        let old_left_len = left_node.len();
        let mut right_node = self.right_child;
        let right_len = right_node.len();
        let new_left_len = old_left_len + 1 + right_len;

        assert!(new_left_len <= CAPACITY);

        unsafe {
            *left_node.len_mut() = new_left_len as u16;

            let parent_key = slice_remove(parent_node.key_area_mut(..old_parent_len), parent_idx);
            left_node.key_area_mut(old_left_len).write(parent_key);
            move_to_slice(
                right_node.key_area_mut(..right_len),
                left_node.key_area_mut(old_left_len + 1..new_left_len),
            );

            let parent_val = slice_remove(parent_node.val_area_mut(..old_parent_len), parent_idx);
            left_node.val_area_mut(old_left_len).write(parent_val);
            move_to_slice(
                right_node.val_area_mut(..right_len),
                left_node.val_area_mut(old_left_len + 1..new_left_len),
            );

            slice_remove(&mut parent_node.edge_area_mut(..old_parent_len + 1), parent_idx + 1);
            parent_node.correct_childrens_parent_links(parent_idx + 1..old_parent_len);
            *parent_node.len_mut() -= 1;

            if parent_node.height > 1 {
                // SAFETY: 合并的节点的高度比此 edge 的节点的高度低 1，因此高于零，因此它们是内部的。
                //
                let mut left_node = left_node.reborrow_mut().cast_to_internal_unchecked();
                let mut right_node = right_node.cast_to_internal_unchecked();
                move_to_slice(
                    right_node.edge_area_mut(..right_len + 1),
                    left_node.edge_area_mut(old_left_len + 1..new_left_len + 1),
                );

                left_node.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);

                alloc.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
            } else {
                alloc.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
            }
        }
        result(parent_node, left_node)
    }

    /// 将父级的键值对和两个相邻的子节点合并到左侧的子节点中，并返回缩小后的父节点。
    ///
    ///
    /// 除非我们 `.can_merge()`，否就会出现 panics。
    pub fn merge_tracking_parent<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
        self.do_merge(|parent, _child| parent, alloc)
    }

    /// 将父级的键值对和两个相邻的子节点合并到左侧的子例程中，并返回该子例程。
    ///
    ///
    /// 除非我们 `.can_merge()`，否就会出现 panics。
    pub fn merge_tracking_child<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
        self.do_merge(|_parent, child| child, alloc)
    }

    /// 将父级的键值对和两个相邻的子节点合并到左侧的子子节点中，并在被跟踪的子级 edge 结束的那个子节点中返回 edge 句柄，
    ///
    ///
    /// 除非我们 `.can_merge()`，否就会出现 panics。
    ///
    pub fn merge_tracking_child_edge<A: Allocator + Clone>(
        self,
        track_edge_idx: LeftOrRight<usize>,
        alloc: A,
    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
        let old_left_len = self.left_child.len();
        let right_len = self.right_child.len();
        assert!(match track_edge_idx {
            LeftOrRight::Left(idx) => idx <= old_left_len,
            LeftOrRight::Right(idx) => idx <= right_len,
        });
        let child = self.merge_tracking_child(alloc);
        let new_idx = match track_edge_idx {
            LeftOrRight::Left(idx) => idx,
            LeftOrRight::Right(idx) => old_left_len + 1 + idx,
        };
        unsafe { Handle::new_edge(child, new_idx) }
    }

    /// 从左侧的子项中删除键值对并将其放置在父级的键值存储中，同时将旧的父级键值对推入右侧的子级中。
    ///
    /// 返回右子 edge 的句柄，该句柄对应于 `track_right_edge_idx` 指定的原始 edge 的终止位置。
    ///
    pub fn steal_left(
        mut self,
        track_right_edge_idx: usize,
    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
        self.bulk_steal_left(1);
        unsafe { Handle::new_edge(self.right_child, 1 + track_right_edge_idx) }
    }

    /// 从右侧的子项中删除键值对，并将其放置在父级的键值存储中，同时将旧的父级键值对推入左侧的子级。
    ///
    /// 返回 `track_left_edge_idx` 指定的左子级中 edge 的句柄，该句柄没有移动。
    ///
    pub fn steal_right(
        mut self,
        track_left_edge_idx: usize,
    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
        self.bulk_steal_right(1);
        unsafe { Handle::new_edge(self.left_child, track_left_edge_idx) }
    }

    /// 这确实与 `steal_left` 相似，但是会同时窃取多个元素。
    pub fn bulk_steal_left(&mut self, count: usize) {
        assert!(count > 0);
        unsafe {
            let left_node = &mut self.left_child;
            let old_left_len = left_node.len();
            let right_node = &mut self.right_child;
            let old_right_len = right_node.len();

            // 确保我们可以安全偷窃。
            assert!(old_right_len + count <= CAPACITY);
            assert!(old_left_len >= count);

            let new_left_len = old_left_len - count;
            let new_right_len = old_right_len + count;
            *left_node.len_mut() = new_left_len as u16;
            *right_node.len_mut() = new_right_len as u16;

            // 移动叶子数据。
            {
                // 为合适的子节点中的被 stolen 的元素腾出空间。
                slice_shr(right_node.key_area_mut(..new_right_len), count);
                slice_shr(right_node.val_area_mut(..new_right_len), count);

                // 将元素从左子元素移到右子元素。
                move_to_slice(
                    left_node.key_area_mut(new_left_len + 1..old_left_len),
                    right_node.key_area_mut(..count - 1),
                );
                move_to_slice(
                    left_node.val_area_mut(new_left_len + 1..old_left_len),
                    right_node.val_area_mut(..count - 1),
                );

                // 将最左边的被盗对移到父对。
                let k = left_node.key_area_mut(new_left_len).assume_init_read();
                let v = left_node.val_area_mut(new_left_len).assume_init_read();
                let (k, v) = self.parent.replace_kv(k, v);

                // 将父级的键 / 值对移到正确的子级。
                right_node.key_area_mut(count - 1).write(k);
                right_node.val_area_mut(count - 1).write(v);
            }

            match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
                (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
                    // 为 stolen 的 edges 腾出空间。
                    slice_shr(right.edge_area_mut(..new_right_len + 1), count);

                    // 拿走 edges。
                    move_to_slice(
                        left.edge_area_mut(new_left_len + 1..old_left_len + 1),
                        right.edge_area_mut(..count),
                    );

                    right.correct_childrens_parent_links(0..new_right_len + 1);
                }
                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
                _ => unreachable!(),
            }
        }
    }

    /// `bulk_steal_left` 的对称克隆。
    pub fn bulk_steal_right(&mut self, count: usize) {
        assert!(count > 0);
        unsafe {
            let left_node = &mut self.left_child;
            let old_left_len = left_node.len();
            let right_node = &mut self.right_child;
            let old_right_len = right_node.len();

            // 确保我们可以安全偷窃。
            assert!(old_left_len + count <= CAPACITY);
            assert!(old_right_len >= count);

            let new_left_len = old_left_len + count;
            let new_right_len = old_right_len - count;
            *left_node.len_mut() = new_left_len as u16;
            *right_node.len_mut() = new_right_len as u16;

            // 移动叶子数据。
            {
                // 将最右边的被盗对移到父对。
                let k = right_node.key_area_mut(count - 1).assume_init_read();
                let v = right_node.val_area_mut(count - 1).assume_init_read();
                let (k, v) = self.parent.replace_kv(k, v);

                // 将父级的键 / 值对移到左子级。
                left_node.key_area_mut(old_left_len).write(k);
                left_node.val_area_mut(old_left_len).write(v);

                // 将元素从右子元素移到左子元素。
                move_to_slice(
                    right_node.key_area_mut(..count - 1),
                    left_node.key_area_mut(old_left_len + 1..new_left_len),
                );
                move_to_slice(
                    right_node.val_area_mut(..count - 1),
                    left_node.val_area_mut(old_left_len + 1..new_left_len),
                );

                // 填补曾经被盗元素的空白。
                slice_shl(right_node.key_area_mut(..old_right_len), count);
                slice_shl(right_node.val_area_mut(..old_right_len), count);
            }

            match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
                (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
                    // 拿走 edges。
                    move_to_slice(
                        right.edge_area_mut(..count),
                        left.edge_area_mut(old_left_len + 1..new_left_len + 1),
                    );

                    // 填充曾经被盗的 edges 的空隙。
                    slice_shl(right.edge_area_mut(..old_right_len + 1), count);

                    left.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
                    right.correct_childrens_parent_links(0..new_right_len + 1);
                }
                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
                _ => unreachable!(),
            }
        }
    }
}

impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
    pub fn forget_node_type(
        self,
    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
        unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
    }
}

impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
    pub fn forget_node_type(
        self,
    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
        unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
    }
}

impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
    pub fn forget_node_type(
        self,
    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
        unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
    }
}

impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, Type> {
    /// 检查底层节点是 `Internal` 节点还是 `Leaf` 节点。
    pub fn force(
        self,
    ) -> ForceResult<
        Handle<NodeRef<BorrowType, K, V, marker::Leaf>, Type>,
        Handle<NodeRef<BorrowType, K, V, marker::Internal>, Type>,
    > {
        match self.node.force() {
            ForceResult::Leaf(node) => {
                ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
            }
            ForceResult::Internal(node) => {
                ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
            }
        }
    }
}

impl<'a, K, V, Type> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, Type> {
    /// 不安全地向编译器断言静态信息，即句柄的节点是 `Leaf`。
    pub unsafe fn cast_to_leaf_unchecked(
        self,
    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, Type> {
        let node = unsafe { self.node.cast_to_leaf_unchecked() };
        Handle { node, idx: self.idx, _marker: PhantomData }
    }
}

impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
    /// `self` 之后的后缀从一个节点移动到另一个节点。`right` 必须为空。
    /// `right` 的第一个 edge 保持不变。
    pub fn move_suffix(
        &mut self,
        right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
    ) {
        unsafe {
            let new_left_len = self.idx;
            let mut left_node = self.reborrow_mut().into_node();
            let old_left_len = left_node.len();

            let new_right_len = old_left_len - new_left_len;
            let mut right_node = right.reborrow_mut();

            assert!(right_node.len() == 0);
            assert!(left_node.height == right_node.height);

            if new_right_len > 0 {
                *left_node.len_mut() = new_left_len as u16;
                *right_node.len_mut() = new_right_len as u16;

                move_to_slice(
                    left_node.key_area_mut(new_left_len..old_left_len),
                    right_node.key_area_mut(..new_right_len),
                );
                move_to_slice(
                    left_node.val_area_mut(new_left_len..old_left_len),
                    right_node.val_area_mut(..new_right_len),
                );
                match (left_node.force(), right_node.force()) {
                    (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
                        move_to_slice(
                            left.edge_area_mut(new_left_len + 1..old_left_len + 1),
                            right.edge_area_mut(1..new_right_len + 1),
                        );
                        right.correct_childrens_parent_links(1..new_right_len + 1);
                    }
                    (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
                    _ => unreachable!(),
                }
            }
        }
    }
}

pub enum ForceResult<Leaf, Internal> {
    Leaf(Leaf),
    Internal(Internal),
}

/// 插入的结果，当节点需要扩展到超出其容量时。
pub struct SplitResult<'a, K, V, NodeType> {
    // 现有树中具有 `kv` 左侧元素和 edges 的已更改节点。
    pub left: NodeRef<marker::Mut<'a>, K, V, NodeType>,
    // 一些以前存在的键和值被分离出来，插入到其他地方。
    pub kv: (K, V),
    // 拥有的，未附加的新节点，其元素和 edges 属于 `kv` 的右侧。
    pub right: NodeRef<marker::Owned, K, V, NodeType>,
}

impl<'a, K, V> SplitResult<'a, K, V, marker::Leaf> {
    pub fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
        SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
    }
}

impl<'a, K, V> SplitResult<'a, K, V, marker::Internal> {
    pub fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
        SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
    }
}

pub mod marker {
    use core::marker::PhantomData;

    pub enum Leaf {}
    pub enum Internal {}
    pub enum LeafOrInternal {}

    pub enum Owned {}
    pub enum Dying {}
    pub enum DormantMut {}
    pub struct Immut<'a>(PhantomData<&'a ()>);
    pub struct Mut<'a>(PhantomData<&'a mut ()>);
    pub struct ValMut<'a>(PhantomData<&'a mut ()>);

    pub trait BorrowType {
        /// 如果该引用类型的节点引用允许遍历到树中的其他节点，则该常量设置为 `true`。
        /// 它可用于编译时断言。
        ///
        const TRAVERSAL_PERMIT: bool = true;
    }
    impl BorrowType for Owned {
        /// 拒绝遍历，因为不需要。而是使用 `borrow_mut` 的结果进行遍历。
        /// 通过禁用遍历，仅对根创建新的引用，我们知道 `Owned` 类型的每个引用都针对根节点。
        ///
        ///
        const TRAVERSAL_PERMIT: bool = false;
    }
    impl BorrowType for Dying {}
    impl<'a> BorrowType for Immut<'a> {}
    impl<'a> BorrowType for Mut<'a> {}
    impl<'a> BorrowType for ValMut<'a> {}
    impl BorrowType for DormantMut {}

    pub enum KV {}
    pub enum Edge {}
}

/// 将值插入初始化元素的切片中，然后插入一个未初始化的元素。
///
/// # Safety
/// 切片具有 `idx` 个以上的元素。
unsafe fn slice_insert<T>(slice: &mut [MaybeUninit<T>], idx: usize, val: T) {
    unsafe {
        let len = slice.len();
        debug_assert!(len > idx);
        let slice_ptr = slice.as_mut_ptr();
        if len > idx + 1 {
            ptr::copy(slice_ptr.add(idx), slice_ptr.add(idx + 1), len - idx - 1);
        }
        (*slice_ptr.add(idx)).write(val);
    }
}

/// 从所有已初始化元素的切片中删除并返回一个值，而留下一个尾随的未初始化元素。
///
///
/// # Safety
/// 切片具有 `idx` 个以上的元素。
unsafe fn slice_remove<T>(slice: &mut [MaybeUninit<T>], idx: usize) -> T {
    unsafe {
        let len = slice.len();
        debug_assert!(idx < len);
        let slice_ptr = slice.as_mut_ptr();
        let ret = (*slice_ptr.add(idx)).assume_init_read();
        ptr::copy(slice_ptr.add(idx + 1), slice_ptr.add(idx), len - idx - 1);
        ret
    }
}

/// 将切片 `distance` 位置中的元素向左移动。
///
/// # Safety
/// 切片至少具有 `distance` 元素。
unsafe fn slice_shl<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
    unsafe {
        let slice_ptr = slice.as_mut_ptr();
        ptr::copy(slice_ptr.add(distance), slice_ptr, slice.len() - distance);
    }
}

/// 将切片 `distance` 位置中的元素向右移动。
///
/// # Safety
/// 切片至少具有 `distance` 元素。
unsafe fn slice_shr<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
    unsafe {
        let slice_ptr = slice.as_mut_ptr();
        ptr::copy(slice_ptr, slice_ptr.add(distance), slice.len() - distance);
    }
}

/// 将所有值从已初始化元素的切片移动到未初始化元素的切片，将 `src` 保留为所有未初始化。
///
/// 像 `dst.copy_from_slice(src)` 一样工作，但不需要 `T` 为 `Copy`。
fn move_to_slice<T>(src: &mut [MaybeUninit<T>], dst: &mut [MaybeUninit<T>]) {
    assert!(src.len() == dst.len());
    unsafe {
        ptr::copy_nonoverlapping(src.as_ptr(), dst.as_mut_ptr(), src.len());
    }
}

#[cfg(test)]
mod tests;