| // This is an attempt at an implementation following the ideal |
| // |
| // ``` |
| // 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>>; 2 * B] |
| // } else { () }, |
| // parent: Option<NonNull<Node<K, V, height + 1>>>, |
| // parent_idx: u16, |
| // len: u16, |
| // } |
| // ``` |
| // |
| // Since Rust doesn't actually have dependent types and polymorphic recursion, |
| // we make do with lots of unsafety. |
| |
| // A major goal of this module is to avoid complexity by treating the tree as a generic (if |
| // weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such, |
| // this module doesn't care whether the entries are sorted, which nodes can be underfull, or |
| // even what underfull means. However, we do rely on a few invariants: |
| // |
| // - Trees must have uniform depth/height. This means that every path down to a leaf from a |
| // given node has exactly the same length. |
| // - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges. |
| // This implies that even an empty internal node has at least one edge. |
| |
| use core::cmp::Ordering; |
| use core::marker::PhantomData; |
| use core::mem::{self, MaybeUninit}; |
| use core::ptr::{self, NonNull, Unique}; |
| use core::slice; |
| |
| use crate::alloc::{AllocRef, Global, Layout}; |
| use crate::boxed::Box; |
| |
| const B: usize = 6; |
| pub const MIN_LEN: usize = B - 1; |
| pub const CAPACITY: usize = 2 * 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; |
| |
| /// The underlying representation of leaf nodes and part of the representation of internal nodes. |
| struct LeafNode<K, V> { |
| /// We want to be covariant in `K` and `V`. |
| parent: Option<NonNull<InternalNode<K, V>>>, |
| |
| /// This node's index into the parent node's `edges` array. |
| /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`. |
| /// This is only guaranteed to be initialized when `parent` is non-null. |
| parent_idx: MaybeUninit<u16>, |
| |
| /// The number of keys and values this node stores. |
| len: u16, |
| |
| /// The arrays storing the actual data of the node. Only the first `len` elements of each |
| /// array are initialized and valid. |
| keys: [MaybeUninit<K>; CAPACITY], |
| vals: [MaybeUninit<V>; CAPACITY], |
| } |
| |
| impl<K, V> LeafNode<K, V> { |
| /// Creates a new `LeafNode`. Unsafe because all nodes should really be hidden behind |
| /// `BoxedNode`, preventing accidental dropping of uninitialized keys and values. |
| unsafe fn new() -> Self { |
| LeafNode { |
| // As a general policy, we leave fields uninitialized if they can be, as this should |
| // be both slightly faster and easier to track in Valgrind. |
| keys: MaybeUninit::uninit_array(), |
| vals: MaybeUninit::uninit_array(), |
| parent: None, |
| parent_idx: MaybeUninit::uninit(), |
| len: 0, |
| } |
| } |
| } |
| |
| /// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden |
| /// behind `BoxedNode`s to prevent dropping uninitialized keys and values. Any pointer to an |
| /// `InternalNode` can be directly casted to a pointer to the underlying `LeafNode` portion of the |
| /// node, allowing code to act on leaf and internal nodes generically without having to even check |
| /// which of the two a pointer is pointing at. This property is enabled by the use of `repr(C)`. |
| #[repr(C)] |
| // gdb_providers.py uses this type name for introspection. |
| struct InternalNode<K, V> { |
| // gdb_providers.py uses this field name for introspection. |
| data: LeafNode<K, V>, |
| |
| /// The pointers to the children of this node. `len + 1` of these are considered |
| /// initialized and valid. Although during the process of `into_iter` or `drop`, |
| /// some pointers are dangling while others still need to be traversed. |
| edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B], |
| } |
| |
| impl<K, V> InternalNode<K, V> { |
| /// Creates a new `InternalNode`. |
| /// |
| /// This is unsafe for two reasons. First, it returns an `InternalNode` by value, risking |
| /// dropping of uninitialized fields. Second, an invariant of internal nodes is that `len + 1` |
| /// edges are initialized and valid, meaning that even when the node is empty (having a |
| /// `len` of 0), there must be one initialized and valid edge. This function does not set up |
| /// such an edge. |
| unsafe fn new() -> Self { |
| InternalNode { data: unsafe { LeafNode::new() }, edges: MaybeUninit::uninit_array() } |
| } |
| } |
| |
| /// A managed, non-null pointer to a node. This is either an owned pointer to |
| /// `LeafNode<K, V>` or an owned pointer to `InternalNode<K, V>`. |
| /// |
| /// However, `BoxedNode` contains no information as to which of the two types |
| /// of nodes it actually contains, and, partially due to this lack of information, |
| /// has no destructor. |
| struct BoxedNode<K, V> { |
| ptr: Unique<LeafNode<K, V>>, |
| } |
| |
| impl<K, V> BoxedNode<K, V> { |
| fn from_leaf(node: Box<LeafNode<K, V>>) -> Self { |
| BoxedNode { ptr: Box::into_unique(node) } |
| } |
| |
| fn from_internal(node: Box<InternalNode<K, V>>) -> Self { |
| BoxedNode { ptr: Box::into_unique(node).cast() } |
| } |
| |
| unsafe fn from_ptr(ptr: NonNull<LeafNode<K, V>>) -> Self { |
| BoxedNode { ptr: unsafe { Unique::new_unchecked(ptr.as_ptr()) } } |
| } |
| |
| fn as_ptr(&self) -> NonNull<LeafNode<K, V>> { |
| NonNull::from(self.ptr) |
| } |
| } |
| |
| /// An owned tree. |
| /// |
| /// Note that this does not have a destructor, and must be cleaned up manually. |
| pub struct Root<K, V> { |
| node: BoxedNode<K, V>, |
| /// The number of levels below the root node. |
| height: usize, |
| } |
| |
| unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {} |
| unsafe impl<K: Send, V: Send> Send for Root<K, V> {} |
| |
| impl<K, V> Root<K, V> { |
| /// Returns the number of levels below the root. |
| pub fn height(&self) -> usize { |
| self.height |
| } |
| |
| /// Returns a new owned tree, with its own root node that is initially empty. |
| pub fn new_leaf() -> Self { |
| Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 } |
| } |
| |
| /// Borrows and returns an immutable reference to the node owned by the root. |
| pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> { |
| NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
| } |
| |
| /// Borrows and returns a mutable reference to the node owned by the root. |
| pub fn node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> { |
| NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
| } |
| |
| pub fn node_as_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, marker::LeafOrInternal> { |
| NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
| } |
| |
| pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { |
| NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
| } |
| |
| /// Adds a new internal node with a single edge pointing to the previous root node, |
| /// make that new node the root node, and return it. This increases the height by 1 |
| /// and is the opposite of `pop_internal_level`. |
| pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { |
| let mut new_node = Box::new(unsafe { InternalNode::new() }); |
| new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) }); |
| |
| self.node = BoxedNode::from_internal(new_node); |
| self.height += 1; |
| |
| let mut ret = |
| NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }; |
| |
| unsafe { |
| ret.reborrow_mut().first_edge().correct_parent_link(); |
| } |
| |
| ret |
| } |
| |
| /// Removes the internal root node, using its first child as the new root node. |
| /// As it is intended only to be called when the root node has only one child, |
| /// no cleanup is done on any of the other children. |
| /// This decreases the height by 1 and is the opposite of `push_internal_level`. |
| /// |
| /// Requires exclusive access to the `Root` object but not to the root node; |
| /// it will not invalidate existing handles or references to the root node. |
| /// |
| /// Panics if there is no internal level, i.e., if the root node is a leaf. |
| pub fn pop_internal_level(&mut self) { |
| assert!(self.height > 0); |
| |
| let top = self.node.ptr; |
| |
| self.node = unsafe { |
| BoxedNode::from_ptr( |
| self.node_as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node, |
| ) |
| }; |
| self.height -= 1; |
| self.node_as_mut().as_leaf_mut().parent = None; |
| |
| unsafe { |
| Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>()); |
| } |
| } |
| } |
| |
| // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType` |
| // is `Mut`. This is technically wrong, but cannot result in any unsafety due to |
| // internal use of `NodeRef` because we stay completely generic over `K` and `V`. |
| // However, whenever a public type wraps `NodeRef`, make sure that it has the |
| // correct variance. |
| /// A reference to a node. |
| /// |
| /// This type has a number of parameters that controls how it acts: |
| /// - `BorrowType`: This can be `Immut<'a>`, `Mut<'a>` or `ValMut<'a>' for some `'a` |
| /// or `Owned`. |
| /// When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`, |
| /// when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`, |
| /// when this is `ValMut<'a>`, the `NodeRef` acts as immutable with respect |
| /// to keys and tree structure, but allows mutable references to values, |
| /// and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`. |
| /// - `K` and `V`: These control what types of things are stored in the nodes. |
| /// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is |
| /// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the |
| /// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the |
| /// `NodeRef` could be pointing to either type of node. |
| pub struct NodeRef<BorrowType, K, V, Type> { |
| /// The number of levels below the node. |
| height: usize, |
| node: NonNull<LeafNode<K, V>>, |
| _marker: PhantomData<(BorrowType, Type)>, |
| } |
| |
| 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<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {} |
| unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {} |
| unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {} |
| unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {} |
| |
| impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { |
| /// Exposes the data of an internal node for reading. |
| /// |
| /// Returns a raw ptr to avoid invalidating other references to this node, |
| /// which is possible when BorrowType is marker::ValMut. |
| fn as_internal_ptr(&self) -> *const InternalNode<K, V> { |
| self.node.as_ptr() as *const InternalNode<K, V> |
| } |
| } |
| |
| impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { |
| /// Exposes the data of an internal node for reading, |
| /// when we know we have exclusive access. |
| fn as_internal(&mut self) -> &InternalNode<K, V> { |
| unsafe { &*self.as_internal_ptr() } |
| } |
| } |
| |
| impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { |
| /// Exposes the data of an internal node for writing. |
| /// |
| /// We don't need to return a raw ptr because we have unique access to the entire node. |
| fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> { |
| unsafe { &mut *(self.node.as_ptr() as *mut InternalNode<K, V>) } |
| } |
| } |
| |
| impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { |
| /// Finds the length of the node. This is the number of keys or values. In an |
| /// internal node, the number of edges is `len() + 1`. |
| /// For any node, the number of possible edge handles is also `len() + 1`. |
| /// Note that, despite being safe, calling this function can have the side effect |
| /// of invalidating mutable references that unsafe code has created. |
| pub fn len(&self) -> usize { |
| // Crucially, we only access the `len` field here. If BorrowType is marker::ValMut, |
| // there might be outstanding mutable references to values that we must not invalidate. |
| unsafe { usize::from((*self.as_leaf_ptr()).len) } |
| } |
| |
| /// Returns the height of this node in the whole tree. Zero height denotes the |
| /// leaf level. |
| pub fn height(&self) -> usize { |
| self.height |
| } |
| |
| /// Temporarily takes out another, immutable reference to the same node. |
| fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> { |
| NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
| } |
| |
| /// Exposes the leaf portion of any leaf or internal node. |
| /// If the node is a leaf, this function simply opens up its data. |
| /// If the node is an internal node, so not a leaf, it does have all the data a leaf has |
| /// (header, keys and values), and this function exposes that. |
| /// |
| /// Returns a raw ptr to avoid invalidating other references to this node, |
| /// which is possible when BorrowType is marker::ValMut. |
| fn as_leaf_ptr(&self) -> *const LeafNode<K, V> { |
| // The node must be valid for at least the LeafNode portion. |
| // This is not a reference in the NodeRef type because we don't know if |
| // it should be unique or shared. |
| self.node.as_ptr() |
| } |
| |
| /// Borrows a reference to one of the keys stored in the node. |
| /// |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| pub unsafe fn key_at(&self, idx: usize) -> &K { |
| unsafe { self.reborrow().into_key_at(idx) } |
| } |
| |
| /// Borrows a reference to one of the values stored in the node. |
| /// |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn val_at(&self, idx: usize) -> &V { |
| unsafe { self.reborrow().into_val_at(idx) } |
| } |
| } |
| |
| impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { |
| /// Borrows a reference to the contents of one of the edges that delimit |
| /// the elements of the node, without invalidating other references. |
| /// |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn edge_at(&self, idx: usize) -> &BoxedNode<K, V> { |
| debug_assert!(idx <= self.len()); |
| let node = self.as_internal_ptr(); |
| unsafe { (*node).edges.get_unchecked(idx).assume_init_ref() } |
| } |
| } |
| |
| impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { |
| /// Finds the parent of the current node. Returns `Ok(handle)` if the current |
| /// node actually has a parent, where `handle` points to the edge of the parent |
| /// that points to the current node. Returns `Err(self)` if the current node has |
| /// no parent, giving back the original `NodeRef`. |
| /// |
| /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should |
| /// both, upon success, do nothing. |
| pub fn ascend( |
| self, |
| ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> { |
| // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut, |
| // there might be outstanding mutable references to values that we must not invalidate. |
| let leaf_ptr = self.as_leaf_ptr(); |
| unsafe { (*leaf_ptr).parent } |
| .as_ref() |
| .map(|parent| Handle { |
| node: NodeRef { |
| height: self.height + 1, |
| node: parent.cast(), |
| _marker: PhantomData, |
| }, |
| 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) } |
| } |
| |
| /// Note that `self` must be nonempty. |
| pub fn first_kv(self) -> Handle<Self, marker::KV> { |
| let len = self.len(); |
| assert!(len > 0); |
| unsafe { Handle::new_kv(self, 0) } |
| } |
| |
| /// Note that `self` must be nonempty. |
| pub fn last_kv(self) -> Handle<Self, marker::KV> { |
| let len = self.len(); |
| assert!(len > 0); |
| unsafe { Handle::new_kv(self, len - 1) } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { |
| /// Exposes the data of a leaf node for reading in an immutable tree. |
| fn into_leaf(self) -> &'a LeafNode<K, V> { |
| // SAFETY: we can access the entire node freely and do no need raw pointers, |
| // because there can be no mutable references to this Immut tree. |
| unsafe { &(*self.as_leaf_ptr()) } |
| } |
| } |
| |
| impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { |
| /// Similar to `ascend`, gets a reference to a node's parent node, but also |
| /// deallocate the current node in the process. This is unsafe because the |
| /// current node will still be accessible despite being deallocated. |
| pub unsafe fn deallocate_and_ascend( |
| self, |
| ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> { |
| let height = self.height; |
| let node = self.node; |
| let ret = self.ascend().ok(); |
| unsafe { |
| Global.dealloc( |
| 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> { |
| /// Unsafely asserts to the compiler some static information about whether this |
| /// node is a `Leaf` or an `Internal`. |
| unsafe fn cast_unchecked<NewType>(self) -> NodeRef<marker::Mut<'a>, K, V, NewType> { |
| NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
| } |
| |
| /// Temporarily takes out another, mutable reference to the same node. Beware, as |
| /// this method is very dangerous, doubly so since it may not immediately appear |
| /// dangerous. |
| /// |
| /// Because mutable pointers can roam anywhere around the tree, the returned |
| /// pointer can easily be used to make the original pointer dangling, out of |
| /// bounds, or invalid under stacked borrow rules. |
| // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` |
| // that restricts the use of navigation methods on reborrowed pointers, |
| // preventing this unsafety. |
| unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> { |
| NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
| } |
| |
| /// Exposes the leaf portion of any leaf or internal node for writing. |
| /// If the node is a leaf, this function simply opens up its data. |
| /// If the node is an internal node, so not a leaf, it does have all the data a leaf has |
| /// (header, keys and values), and this function exposes that. |
| /// |
| /// We don't need to return a raw ptr because we have unique access to the entire node. |
| fn as_leaf_mut(&mut self) -> &'a mut LeafNode<K, V> { |
| unsafe { &mut (*self.node.as_ptr()) } |
| } |
| |
| /// Borrows a mutable reference to one of the keys stored in the node. |
| /// |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| pub unsafe fn key_mut_at(&mut self, idx: usize) -> &mut K { |
| unsafe { self.reborrow_mut().into_key_mut_at(idx) } |
| } |
| |
| /// Borrows a mutable reference to one of the values stored in the node. |
| /// |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| pub unsafe fn val_mut_at(&mut self, idx: usize) -> &mut V { |
| unsafe { self.reborrow_mut().into_val_mut_at(idx) } |
| } |
| |
| fn keys_mut(&mut self) -> &mut [K] |
| where |
| K: 'a, |
| V: 'a, |
| { |
| // SAFETY: the caller will not be able to call further methods on self |
| // until the key slice reference is dropped, as we have unique access |
| // for the lifetime of the borrow. |
| // SAFETY: The keys of a node must always be initialized up to length. |
| unsafe { |
| slice::from_raw_parts_mut( |
| MaybeUninit::slice_as_mut_ptr(&mut self.as_leaf_mut().keys), |
| self.len(), |
| ) |
| } |
| } |
| |
| fn vals_mut(&mut self) -> &mut [V] |
| where |
| K: 'a, |
| V: 'a, |
| { |
| // SAFETY: the caller will not be able to call further methods on self |
| // until the value slice reference is dropped, as we have unique access |
| // for the lifetime of the borrow. |
| // SAFETY: The values of a node must always be initialized up to length. |
| unsafe { |
| slice::from_raw_parts_mut( |
| MaybeUninit::slice_as_mut_ptr(&mut self.as_leaf_mut().vals), |
| self.len(), |
| ) |
| } |
| } |
| } |
| |
| impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { |
| fn edges_mut(&mut self) -> &mut [BoxedNode<K, V>] { |
| unsafe { |
| slice::from_raw_parts_mut( |
| MaybeUninit::slice_as_mut_ptr(&mut self.as_internal_mut().edges), |
| self.len() + 1, |
| ) |
| } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn into_key_at(self, idx: usize) -> &'a K { |
| unsafe { self.into_leaf().keys.get_unchecked(idx).assume_init_ref() } |
| } |
| |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn into_val_at(self, idx: usize) -> &'a V { |
| unsafe { self.into_leaf().vals.get_unchecked(idx).assume_init_ref() } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> { |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn into_key_mut_at(mut self, idx: usize) -> &'a mut K { |
| debug_assert!(idx < self.len()); |
| |
| let leaf = self.as_leaf_mut(); |
| unsafe { leaf.keys.get_unchecked_mut(idx).assume_init_mut() } |
| } |
| |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn into_val_mut_at(mut self, idx: usize) -> &'a mut V { |
| debug_assert!(idx < self.len()); |
| |
| let leaf = self.as_leaf_mut(); |
| unsafe { leaf.vals.get_unchecked_mut(idx).assume_init_mut() } |
| } |
| } |
| |
| impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> { |
| /// # Safety |
| /// The node has more than `idx` initialized elements. |
| unsafe fn into_key_val_mut_at(self, idx: usize) -> (&'a K, &'a mut V) { |
| // We only create a reference to the one element we are interested in, |
| // to avoid aliasing with outstanding references to other elements, |
| // in particular, those returned to the caller in earlier iterations. |
| let leaf = self.node.as_ptr(); |
| // We must coerce to unsized array pointers because of Rust issue #74679. |
| let keys: *const [_] = unsafe { &raw const (*leaf).keys }; |
| let vals: *mut [_] = unsafe { &raw mut (*leaf).vals }; |
| // SAFETY: The keys and values of a node must always be initialized up to length. |
| 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> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { |
| /// Adds a key/value pair to the end of the node. |
| pub fn push(&mut self, key: K, val: V) { |
| let len = &mut self.as_leaf_mut().len; |
| let idx = usize::from(*len); |
| assert!(idx < CAPACITY); |
| *len += 1; |
| unsafe { |
| ptr::write(self.key_mut_at(idx), key); |
| ptr::write(self.val_mut_at(idx), val); |
| } |
| } |
| |
| /// Adds a key/value pair to the beginning of the node. |
| fn push_front(&mut self, key: K, val: V) { |
| debug_assert!(self.len() < CAPACITY); |
| |
| unsafe { |
| slice_insert(self.keys_mut(), 0, key); |
| slice_insert(self.vals_mut(), 0, val); |
| } |
| self.as_leaf_mut().len += 1; |
| } |
| } |
| |
| impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { |
| /// # Safety |
| /// Every item returned by `range` is a valid edge index for the node. |
| 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::Internal> { |
| /// Adds a key/value pair, and an edge to go to the right of that pair, |
| /// to the end of the node. |
| pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) { |
| assert!(edge.height == self.height - 1); |
| |
| let len = &mut self.as_leaf_mut().len; |
| let idx = usize::from(*len); |
| assert!(idx < CAPACITY); |
| *len += 1; |
| unsafe { |
| ptr::write(self.key_mut_at(idx), key); |
| ptr::write(self.val_mut_at(idx), val); |
| self.as_internal_mut().edges.get_unchecked_mut(idx + 1).write(edge.node); |
| Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link(); |
| } |
| } |
| |
| /// Adds a key/value pair, and an edge to go to the left of that pair, |
| /// to the beginning of the node. |
| pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) { |
| assert!(edge.height == self.height - 1); |
| assert!(self.len() < CAPACITY); |
| |
| unsafe { |
| slice_insert(self.keys_mut(), 0, key); |
| slice_insert(self.vals_mut(), 0, val); |
| slice_insert( |
| slice::from_raw_parts_mut( |
| MaybeUninit::slice_as_mut_ptr(&mut self.as_internal_mut().edges), |
| self.len() + 1, |
| ), |
| 0, |
| edge.node, |
| ); |
| } |
| |
| self.as_leaf_mut().len += 1; |
| |
| self.correct_all_childrens_parent_links(); |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { |
| /// Removes a key/value pair from the end of this node and returns the pair. |
| /// If this is an internal node, also removes the edge that was to the right |
| /// of that pair and returns the orphaned node that this edge owned. |
| fn pop(&mut self) -> (K, V, Option<Root<K, V>>) { |
| debug_assert!(self.len() > 0); |
| |
| let idx = self.len() - 1; |
| |
| unsafe { |
| let key = ptr::read(self.key_at(idx)); |
| let val = ptr::read(self.val_at(idx)); |
| let edge = match self.reborrow_mut().force() { |
| ForceResult::Leaf(_) => None, |
| ForceResult::Internal(internal) => { |
| let edge = ptr::read(internal.edge_at(idx + 1)); |
| let mut new_root = Root { node: edge, height: internal.height - 1 }; |
| new_root.node_as_mut().as_leaf_mut().parent = None; |
| Some(new_root) |
| } |
| }; |
| |
| self.as_leaf_mut().len -= 1; |
| (key, val, edge) |
| } |
| } |
| |
| /// Removes a key/value pair from the beginning of this node and returns the pair. |
| /// If this is an internal node, also removes the edge that was to the left |
| /// of that pair and returns the orphaned node that this edge owned. |
| fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) { |
| debug_assert!(self.len() > 0); |
| |
| let old_len = self.len(); |
| |
| unsafe { |
| let key = slice_remove(self.keys_mut(), 0); |
| let val = slice_remove(self.vals_mut(), 0); |
| let edge = match self.reborrow_mut().force() { |
| ForceResult::Leaf(_) => None, |
| ForceResult::Internal(mut internal) => { |
| let edge = slice_remove(internal.edges_mut(), 0); |
| let mut new_root = Root { node: edge, height: internal.height - 1 }; |
| new_root.node_as_mut().as_leaf_mut().parent = None; |
| |
| internal.correct_childrens_parent_links(0..old_len); |
| |
| Some(new_root) |
| } |
| }; |
| |
| self.as_leaf_mut().len -= 1; |
| |
| (key, val, edge) |
| } |
| } |
| |
| fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) { |
| (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr()) |
| } |
| } |
| |
| impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
| /// Checks whether a node is an `Internal` node or a `Leaf` node. |
| 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, |
| }) |
| } |
| } |
| } |
| |
| /// A reference to a specific key/value pair or edge within a node. The `Node` parameter |
| /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key/value |
| /// pair) or `Edge` (signifying a handle on an edge). |
| /// |
| /// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to |
| /// a child node, these represent the spaces where child pointers would go between the key/value |
| /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one |
| /// to the left of the node, one between the two pairs, and one at the right of the node. |
| pub struct Handle<Node, Type> { |
| node: Node, |
| idx: usize, |
| _marker: PhantomData<Type>, |
| } |
| |
| impl<Node: Copy, Type> Copy for Handle<Node, Type> {} |
| // We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be |
| // `Clone`able is when it is an immutable reference and therefore `Copy`. |
| impl<Node: Copy, Type> Clone for Handle<Node, Type> { |
| fn clone(&self) -> Self { |
| *self |
| } |
| } |
| |
| impl<Node, Type> Handle<Node, Type> { |
| /// Retrieves the node that contains the edge or key/value pair this handle points to. |
| pub fn into_node(self) -> Node { |
| self.node |
| } |
| |
| /// Returns the position of this handle in the node. |
| pub fn idx(&self) -> usize { |
| self.idx |
| } |
| } |
| |
| impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> { |
| /// Creates a new handle to a key/value pair in `node`. |
| /// Unsafe because the caller must ensure that `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 { |
| self.node.node == other.node.node && self.idx == other.idx |
| } |
| } |
| |
| impl<BorrowType, K, V, NodeType, HandleType> PartialOrd |
| for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> |
| { |
| fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |
| if self.node.node == other.node.node { Some(self.idx.cmp(&other.idx)) } else { None } |
| } |
| } |
| |
| impl<BorrowType, K, V, NodeType, HandleType> |
| Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> |
| { |
| /// Temporarily takes out another, immutable handle on the same location. |
| pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> { |
| // We can't use Handle::new_kv or Handle::new_edge because we don't know our type |
| 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> { |
| /// Temporarily takes out another, mutable handle on the same location. Beware, as |
| /// this method is very dangerous, doubly so since it may not immediately appear |
| /// dangerous. |
| /// |
| /// For details, see `NodeRef::reborrow_mut`. |
| pub unsafe fn reborrow_mut( |
| &mut self, |
| ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> { |
| // We can't use Handle::new_kv or Handle::new_edge because we don't know our type |
| Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData } |
| } |
| } |
| |
| impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { |
| /// Creates a new handle to an edge in `node`. |
| /// Unsafe because the caller must ensure that `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) |
| } |
| } |
| } |
| |
| enum InsertionPlace { |
| Left(usize), |
| Right(usize), |
| } |
| |
| /// Given an edge index where we want to insert into a node filled to capacity, |
| /// computes a sensible KV index of a split point and where to perform the insertion. |
| /// The goal of the split point is for its key and value to end up in a parent node; |
| /// the keys, values and edges to the left of the split point become the left child; |
| /// the keys, values and edges to the right of the split point become the right child. |
| fn splitpoint(edge_idx: usize) -> (usize, InsertionPlace) { |
| debug_assert!(edge_idx <= CAPACITY); |
| // Rust issue #74834 tries to explain these symmetric rules. |
| match edge_idx { |
| 0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, InsertionPlace::Left(edge_idx)), |
| EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Left(edge_idx)), |
| EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Right(0)), |
| _ => (KV_IDX_CENTER + 1, InsertionPlace::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))), |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::Edge> { |
| /// Helps implementations of `insert_fit` for a particular `NodeType`, |
| /// by taking care of leaf data. |
| /// Inserts a new key/value pair between the key/value pairs to the right and left of |
| /// this edge. This method assumes that there is enough space in the node for the new |
| /// pair to fit. |
| fn leafy_insert_fit(&mut self, key: K, val: V) { |
| debug_assert!(self.node.len() < CAPACITY); |
| |
| unsafe { |
| slice_insert(self.node.keys_mut(), self.idx, key); |
| slice_insert(self.node.vals_mut(), self.idx, val); |
| |
| self.node.as_leaf_mut().len += 1; |
| } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { |
| /// Inserts a new key/value pair between the key/value pairs to the right and left of |
| /// this edge. This method assumes that there is enough space in the node for the new |
| /// pair to fit. |
| /// |
| /// The returned pointer points to the inserted value. |
| fn insert_fit(&mut self, key: K, val: V) -> *mut V { |
| self.leafy_insert_fit(key, val); |
| unsafe { self.node.val_mut_at(self.idx) } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { |
| /// Inserts a new key/value pair between the key/value pairs to the right and left of |
| /// this edge. This method splits the node if there isn't enough room. |
| /// |
| /// The returned pointer points to the inserted value. |
| fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) { |
| if self.node.len() < CAPACITY { |
| let val_ptr = self.insert_fit(key, val); |
| let kv = unsafe { Handle::new_kv(self.node, self.idx) }; |
| (InsertResult::Fit(kv), val_ptr) |
| } else { |
| let (middle_kv_idx, insertion) = splitpoint(self.idx); |
| let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; |
| let (mut left, k, v, mut right) = middle.split(); |
| let mut insertion_edge = match insertion { |
| InsertionPlace::Left(insert_idx) => unsafe { |
| Handle::new_edge(left.reborrow_mut(), insert_idx) |
| }, |
| InsertionPlace::Right(insert_idx) => unsafe { |
| Handle::new_edge( |
| right.node_as_mut().cast_unchecked::<marker::Leaf>(), |
| insert_idx, |
| ) |
| }, |
| }; |
| let val_ptr = insertion_edge.insert_fit(key, val); |
| (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), val_ptr) |
| } |
| } |
| } |
| |
| impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { |
| /// Fixes the parent pointer and index in the child node below this edge. This is useful |
| /// when the ordering of edges has been changed, such as in the various `insert` methods. |
| fn correct_parent_link(mut self) { |
| let idx = self.idx as u16; |
| let ptr = NonNull::new(self.node.as_internal_mut()); |
| let mut child = self.descend(); |
| child.as_leaf_mut().parent = ptr; |
| child.as_leaf_mut().parent_idx.write(idx); |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { |
| /// Inserts a new key/value pair and an edge that will go to the right of that new pair |
| /// between this edge and the key/value pair to the right of this edge. This method assumes |
| /// that there is enough space in the node for the new pair to fit. |
| fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) { |
| debug_assert!(edge.height == self.node.height - 1); |
| |
| unsafe { |
| slice_insert(self.node.edges_mut(), self.idx + 1, edge.node); |
| self.leafy_insert_fit(key, val); |
| |
| self.node.correct_childrens_parent_links((self.idx + 1)..=self.node.len()); |
| } |
| } |
| |
| /// Inserts a new key/value pair and an edge that will go to the right of that new pair |
| /// between this edge and the key/value pair to the right of this edge. This method splits |
| /// the node if there isn't enough room. |
| fn insert( |
| mut self, |
| key: K, |
| val: V, |
| edge: Root<K, V>, |
| ) -> InsertResult<'a, K, V, marker::Internal> { |
| assert!(edge.height == self.node.height - 1); |
| |
| if self.node.len() < CAPACITY { |
| self.insert_fit(key, val, edge); |
| let kv = unsafe { Handle::new_kv(self.node, self.idx) }; |
| InsertResult::Fit(kv) |
| } else { |
| let (middle_kv_idx, insertion) = splitpoint(self.idx); |
| let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; |
| let (mut left, k, v, mut right) = middle.split(); |
| match insertion { |
| InsertionPlace::Left(insert_idx) => unsafe { |
| Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val, edge); |
| }, |
| InsertionPlace::Right(insert_idx) => unsafe { |
| Handle::new_edge( |
| right.node_as_mut().cast_unchecked::<marker::Internal>(), |
| insert_idx, |
| ) |
| .insert_fit(key, val, edge); |
| }, |
| } |
| InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }) |
| } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { |
| /// Inserts a new key/value pair between the key/value pairs to the right and left of |
| /// this edge. This method splits the node if there isn't enough room, and tries to |
| /// insert the split off portion into the parent node recursively, until the root is reached. |
| /// |
| /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor. |
| /// If the returned result is a `Split`, the `left` field will be the root node. |
| /// The returned pointer points to the inserted value. |
| pub fn insert_recursing( |
| self, |
| key: K, |
| value: V, |
| ) -> (InsertResult<'a, K, V, marker::LeafOrInternal>, *mut V) { |
| let (mut split, val_ptr) = match self.insert(key, value) { |
| (InsertResult::Fit(handle), ptr) => { |
| return (InsertResult::Fit(handle.forget_node_type()), ptr); |
| } |
| (InsertResult::Split(split), val_ptr) => (split, val_ptr), |
| }; |
| |
| loop { |
| split = match split.left.ascend() { |
| Ok(parent) => match parent.insert(split.k, split.v, split.right) { |
| InsertResult::Fit(handle) => { |
| return (InsertResult::Fit(handle.forget_node_type()), val_ptr); |
| } |
| InsertResult::Split(split) => split, |
| }, |
| Err(root) => { |
| return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr); |
| } |
| }; |
| } |
| } |
| } |
| |
| impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> { |
| /// Finds the node pointed to by this edge. |
| /// |
| /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should |
| /// both, upon success, do nothing. |
| pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
| // We need to use raw pointers to nodes because, if BorrowType is |
| // marker::ValMut, there might be outstanding mutable references to |
| // values that we must not invalidate. There's no worry accessing the |
| // height field because that value is copied. Beware that, once the |
| // node pointer is dereferenced, we access the edges array with a |
| // reference (Rust issue #73987) and invalidate any other references |
| // to or inside the array, should any be around. |
| let internal_node = self.node.as_internal_ptr(); |
| NodeRef { |
| height: self.node.height - 1, |
| node: unsafe { (&*(*internal_node).edges.get_unchecked(self.idx).as_ptr()).as_ptr() }, |
| _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) { |
| (unsafe { self.node.into_key_at(self.idx) }, unsafe { self.node.into_val_at(self.idx) }) |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { |
| pub fn into_key_mut(self) -> &'a mut K { |
| unsafe { self.node.into_key_mut_at(self.idx) } |
| } |
| |
| pub fn into_val_mut(self) -> &'a mut V { |
| unsafe { self.node.into_val_mut_at(self.idx) } |
| } |
| } |
| |
| 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) { |
| // We cannot call into_key_mut_at and into_val_mut_at, because calling the second one |
| // invalidates the reference returned by the first. |
| let leaf = self.node.as_leaf_mut(); |
| let key = unsafe { leaf.keys.get_unchecked_mut(self.idx).assume_init_mut() }; |
| let val = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }; |
| (key, val) |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { |
| /// Helps implementations of `split` for a particular `NodeType`, |
| /// by taking care of leaf data. |
| fn leafy_split(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V, usize) { |
| unsafe { |
| let k = ptr::read(self.node.key_at(self.idx)); |
| let v = ptr::read(self.node.val_at(self.idx)); |
| |
| let new_len = self.node.len() - self.idx - 1; |
| |
| ptr::copy_nonoverlapping( |
| self.node.key_at(self.idx + 1), |
| MaybeUninit::slice_as_mut_ptr(&mut new_node.keys), |
| new_len, |
| ); |
| ptr::copy_nonoverlapping( |
| self.node.val_at(self.idx + 1), |
| MaybeUninit::slice_as_mut_ptr(&mut new_node.vals), |
| new_len, |
| ); |
| |
| self.node.as_leaf_mut().len = self.idx as u16; |
| new_node.len = new_len as u16; |
| (k, v, new_len) |
| } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { |
| /// Splits the underlying node into three parts: |
| /// |
| /// - The node is truncated to only contain the key/value pairs to the right of |
| /// this handle. |
| /// - The key and value pointed to by this handle are extracted. |
| /// - All the key/value pairs to the right of this handle are put into a newly |
| /// allocated node. |
| pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) { |
| unsafe { |
| let mut new_node = Box::new(LeafNode::new()); |
| |
| let (k, v, _) = self.leafy_split(&mut new_node); |
| |
| (self.node, k, v, Root { node: BoxedNode::from_leaf(new_node), height: 0 }) |
| } |
| } |
| |
| /// Removes the key/value pair pointed to by this handle and returns it, along with the edge |
| /// that the key/value pair collapsed into. |
| pub fn remove( |
| mut self, |
| ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) { |
| unsafe { |
| let k = slice_remove(self.node.keys_mut(), self.idx); |
| let v = slice_remove(self.node.vals_mut(), self.idx); |
| self.node.as_leaf_mut().len -= 1; |
| ((k, v), self.left_edge()) |
| } |
| } |
| } |
| |
| impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> { |
| /// Returns `true` if it is valid to call `.merge()`, i.e., whether there is enough room in |
| /// a node to hold the combination of the nodes to the left and right of this handle along |
| /// with the key/value pair at this handle. |
| pub fn can_merge(&self) -> bool { |
| (self.reborrow().left_edge().descend().len() |
| + self.reborrow().right_edge().descend().len() |
| + 1) |
| <= CAPACITY |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> { |
| /// Splits the underlying node into three parts: |
| /// |
| /// - The node is truncated to only contain the edges and key/value pairs to the |
| /// right of this handle. |
| /// - The key and value pointed to by this handle are extracted. |
| /// - All the edges and key/value pairs to the right of this handle are put into |
| /// a newly allocated node. |
| pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) { |
| unsafe { |
| let mut new_node = Box::new(InternalNode::new()); |
| |
| let (k, v, new_len) = self.leafy_split(&mut new_node.data); |
| let height = self.node.height; |
| let old_node = &*self.node.as_internal_ptr(); |
| |
| ptr::copy_nonoverlapping( |
| old_node.edges.as_ptr().add(self.idx + 1), |
| new_node.edges.as_mut_ptr(), |
| new_len + 1, |
| ); |
| |
| let mut new_root = Root { node: BoxedNode::from_internal(new_node), height }; |
| |
| new_root.node_as_mut().cast_unchecked().correct_childrens_parent_links(0..=new_len); |
| |
| (self.node, k, v, new_root) |
| } |
| } |
| |
| /// Combines the node immediately to the left of this handle, the key/value pair pointed |
| /// to by this handle, and the node immediately to the right of this handle into one new |
| /// child of the underlying node, returning an edge referencing that new child. |
| /// |
| /// Panics unless this edge `.can_merge()`. |
| pub fn merge( |
| mut self, |
| ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { |
| let self1 = unsafe { ptr::read(&self) }; |
| let self2 = unsafe { ptr::read(&self) }; |
| let mut left_node = self1.left_edge().descend(); |
| let left_len = left_node.len(); |
| let right_node = self2.right_edge().descend(); |
| let right_len = right_node.len(); |
| |
| assert!(left_len + right_len < CAPACITY); |
| |
| unsafe { |
| ptr::write( |
| left_node.keys_mut().get_unchecked_mut(left_len), |
| slice_remove(self.node.keys_mut(), self.idx), |
| ); |
| ptr::copy_nonoverlapping( |
| right_node.key_at(0), |
| left_node.keys_mut().as_mut_ptr().add(left_len + 1), |
| right_len, |
| ); |
| ptr::write( |
| left_node.vals_mut().get_unchecked_mut(left_len), |
| slice_remove(self.node.vals_mut(), self.idx), |
| ); |
| ptr::copy_nonoverlapping( |
| right_node.val_at(0), |
| left_node.vals_mut().as_mut_ptr().add(left_len + 1), |
| right_len, |
| ); |
| |
| slice_remove(&mut self.node.edges_mut(), self.idx + 1); |
| let self_len = self.node.len(); |
| self.node.correct_childrens_parent_links(self.idx + 1..self_len); |
| self.node.as_leaf_mut().len -= 1; |
| |
| left_node.as_leaf_mut().len += right_len as u16 + 1; |
| |
| if self.node.height > 1 { |
| // SAFETY: the height of the nodes being merged is one below the height |
| // of the node of this edge, thus above zero, so they are internal. |
| let mut left_node = left_node.cast_unchecked::<marker::Internal>(); |
| let right_node = right_node.cast_unchecked::<marker::Internal>(); |
| ptr::copy_nonoverlapping( |
| right_node.edge_at(0), |
| left_node.edges_mut().as_mut_ptr().add(left_len + 1), |
| right_len + 1, |
| ); |
| |
| left_node.correct_childrens_parent_links(left_len + 1..=left_len + 1 + right_len); |
| |
| Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>()); |
| } else { |
| Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>()); |
| } |
| |
| Handle::new_edge(self.node, self.idx) |
| } |
| } |
| |
| /// This removes a key/value pair from the left child and places it in the key/value storage |
| /// pointed to by this handle while pushing the old key/value pair of this handle into the right |
| /// child. |
| pub fn steal_left(&mut self) { |
| unsafe { |
| let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop(); |
| |
| let k = mem::replace(self.kv_mut().0, k); |
| let v = mem::replace(self.kv_mut().1, v); |
| |
| match self.reborrow_mut().right_edge().descend().force() { |
| ForceResult::Leaf(mut leaf) => leaf.push_front(k, v), |
| ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()), |
| } |
| } |
| } |
| |
| /// This removes a key/value pair from the right child and places it in the key/value storage |
| /// pointed to by this handle while pushing the old key/value pair of this handle into the left |
| /// child. |
| pub fn steal_right(&mut self) { |
| unsafe { |
| let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front(); |
| |
| let k = mem::replace(self.kv_mut().0, k); |
| let v = mem::replace(self.kv_mut().1, v); |
| |
| match self.reborrow_mut().left_edge().descend().force() { |
| ForceResult::Leaf(mut leaf) => leaf.push(k, v), |
| ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()), |
| } |
| } |
| } |
| |
| /// This does stealing similar to `steal_left` but steals multiple elements at once. |
| pub fn bulk_steal_left(&mut self, count: usize) { |
| unsafe { |
| let mut left_node = ptr::read(self).left_edge().descend(); |
| let left_len = left_node.len(); |
| let mut right_node = ptr::read(self).right_edge().descend(); |
| let right_len = right_node.len(); |
| |
| // Make sure that we may steal safely. |
| assert!(right_len + count <= CAPACITY); |
| assert!(left_len >= count); |
| |
| let new_left_len = left_len - count; |
| |
| // Move data. |
| { |
| let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); |
| let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); |
| let parent_kv = { |
| let kv = self.kv_mut(); |
| (kv.0 as *mut K, kv.1 as *mut V) |
| }; |
| |
| // Make room for stolen elements in the right child. |
| ptr::copy(right_kv.0, right_kv.0.add(count), right_len); |
| ptr::copy(right_kv.1, right_kv.1.add(count), right_len); |
| |
| // Move elements from the left child to the right one. |
| move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1); |
| |
| // Move parent's key/value pair to the right child. |
| move_kv(parent_kv, 0, right_kv, count - 1, 1); |
| |
| // Move the left-most stolen pair to the parent. |
| move_kv(left_kv, new_left_len, parent_kv, 0, 1); |
| } |
| |
| left_node.as_leaf_mut().len -= count as u16; |
| right_node.as_leaf_mut().len += count as u16; |
| |
| match (left_node.force(), right_node.force()) { |
| (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { |
| // Make room for stolen edges. |
| let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); |
| ptr::copy(right_edges, right_edges.add(count), right_len + 1); |
| right.correct_childrens_parent_links(count..count + right_len + 1); |
| |
| move_edges(left, new_left_len + 1, right, 0, count); |
| } |
| (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} |
| _ => unreachable!(), |
| } |
| } |
| } |
| |
| /// The symmetric clone of `bulk_steal_left`. |
| pub fn bulk_steal_right(&mut self, count: usize) { |
| unsafe { |
| let mut left_node = ptr::read(self).left_edge().descend(); |
| let left_len = left_node.len(); |
| let mut right_node = ptr::read(self).right_edge().descend(); |
| let right_len = right_node.len(); |
| |
| // Make sure that we may steal safely. |
| assert!(left_len + count <= CAPACITY); |
| assert!(right_len >= count); |
| |
| let new_right_len = right_len - count; |
| |
| // Move data. |
| { |
| let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); |
| let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); |
| let parent_kv = { |
| let kv = self.kv_mut(); |
| (kv.0 as *mut K, kv.1 as *mut V) |
| }; |
| |
| // Move parent's key/value pair to the left child. |
| move_kv(parent_kv, 0, left_kv, left_len, 1); |
| |
| // Move elements from the right child to the left one. |
| move_kv(right_kv, 0, left_kv, left_len + 1, count - 1); |
| |
| // Move the right-most stolen pair to the parent. |
| move_kv(right_kv, count - 1, parent_kv, 0, 1); |
| |
| // Fix right indexing |
| ptr::copy(right_kv.0.add(count), right_kv.0, new_right_len); |
| ptr::copy(right_kv.1.add(count), right_kv.1, new_right_len); |
| } |
| |
| left_node.as_leaf_mut().len += count as u16; |
| right_node.as_leaf_mut().len -= count as u16; |
| |
| match (left_node.force(), right_node.force()) { |
| (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { |
| move_edges(right.reborrow_mut(), 0, left, left_len + 1, count); |
| |
| // Fix right indexing. |
| let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); |
| ptr::copy(right_edges.add(count), right_edges, new_right_len + 1); |
| right.correct_childrens_parent_links(0..=new_right_len); |
| } |
| (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} |
| _ => unreachable!(), |
| } |
| } |
| } |
| } |
| |
| unsafe fn move_kv<K, V>( |
| source: (*mut K, *mut V), |
| source_offset: usize, |
| dest: (*mut K, *mut V), |
| dest_offset: usize, |
| count: usize, |
| ) { |
| unsafe { |
| ptr::copy_nonoverlapping(source.0.add(source_offset), dest.0.add(dest_offset), count); |
| ptr::copy_nonoverlapping(source.1.add(source_offset), dest.1.add(dest_offset), count); |
| } |
| } |
| |
| // Source and destination must have the same height. |
| unsafe fn move_edges<K, V>( |
| mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, |
| source_offset: usize, |
| mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, |
| dest_offset: usize, |
| count: usize, |
| ) { |
| let source_ptr = source.as_internal().edges.as_ptr(); |
| let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr(); |
| unsafe { |
| ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr.add(dest_offset), count); |
| dest.correct_childrens_parent_links(dest_offset..dest_offset + count); |
| } |
| } |
| |
| impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> { |
| /// Removes any static information asserting that this node is a `Leaf` node. |
| 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> { |
| /// Removes any static information asserting that this node is an `Internal` node. |
| pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
| NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
| } |
| } |
| |
| 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> Handle<NodeRef<BorrowType, K, V, marker::Internal>, 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, HandleType> |
| Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> |
| { |
| /// Checks whether the underlying node is an `Internal` node or a `Leaf` node. |
| pub fn force( |
| self, |
| ) -> ForceResult< |
| Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>, |
| Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>, |
| > { |
| 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> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> { |
| /// Move the suffix after `self` from one node to another one. `right` must be empty. |
| /// The first edge of `right` remains unchanged. |
| pub fn move_suffix( |
| &mut self, |
| right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, |
| ) { |
| unsafe { |
| let left_new_len = self.idx; |
| let mut left_node = self.reborrow_mut().into_node(); |
| |
| let right_new_len = left_node.len() - left_new_len; |
| let mut right_node = right.reborrow_mut(); |
| |
| assert!(right_node.len() == 0); |
| assert!(left_node.height == right_node.height); |
| |
| if right_new_len > 0 { |
| let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); |
| let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); |
| |
| move_kv(left_kv, left_new_len, right_kv, 0, right_new_len); |
| |
| left_node.as_leaf_mut().len = left_new_len as u16; |
| right_node.as_leaf_mut().len = right_new_len as u16; |
| |
| match (left_node.force(), right_node.force()) { |
| (ForceResult::Internal(left), ForceResult::Internal(right)) => { |
| move_edges(left, left_new_len + 1, right, 1, right_new_len); |
| } |
| (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} |
| _ => unreachable!(), |
| } |
| } |
| } |
| } |
| } |
| |
| pub enum ForceResult<Leaf, Internal> { |
| Leaf(Leaf), |
| Internal(Internal), |
| } |
| |
| /// Result of insertion, when a node needed to expand beyond its capacity. |
| /// Does not distinguish between `Leaf` and `Internal` because `Root` doesn't. |
| pub struct SplitResult<'a, K, V> { |
| // Altered node in existing tree with elements and edges that belong to the left of `k`. |
| pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, |
| // Some key and value split off, to be inserted elsewhere. |
| pub k: K, |
| pub v: V, |
| // Owned, unattached, new node with elements and edges that belong to the right of `k`. |
| pub right: Root<K, V>, |
| } |
| |
| pub enum InsertResult<'a, K, V, Type> { |
| Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>), |
| Split(SplitResult<'a, K, V>), |
| } |
| |
| pub mod marker { |
| use core::marker::PhantomData; |
| |
| pub enum Leaf {} |
| pub enum Internal {} |
| pub enum LeafOrInternal {} |
| |
| pub enum Owned {} |
| pub struct Immut<'a>(PhantomData<&'a ()>); |
| pub struct Mut<'a>(PhantomData<&'a mut ()>); |
| pub struct ValMut<'a>(PhantomData<&'a mut ()>); |
| |
| pub enum KV {} |
| pub enum Edge {} |
| } |
| |
| unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) { |
| unsafe { |
| ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx); |
| ptr::write(slice.get_unchecked_mut(idx), val); |
| } |
| } |
| |
| unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T { |
| unsafe { |
| let ret = ptr::read(slice.get_unchecked(idx)); |
| ptr::copy(slice.as_ptr().add(idx + 1), slice.as_mut_ptr().add(idx), slice.len() - idx - 1); |
| ret |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests; |