// given node has exactly the same length.
// - A node of length `n` has `n` keys, `n` values, and `n + 1` edges.
// This implies that even an empty node has at least one edge.
+// For a leaf node, "having an edge" only means we can identify a position in the node,
+// since leaf edges are empty and need no data representation. In an internal node,
+// an edge both identifies a position and contains a pointer to a child node.
use core::cmp::Ordering;
use core::marker::PhantomData;
use core::mem::{self, MaybeUninit};
-use core::ptr::{self, NonNull, Unique};
+use core::ptr::{self, NonNull};
+use core::slice::SliceIndex;
-use crate::alloc::{AllocRef, Global, Layout};
+use crate::alloc::{Allocator, Global, Layout};
use crate::boxed::Box;
const B: usize = 6;
///
/// 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: Unique::from(Box::leak(node)) }
- }
-
- fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
- BoxedNode { ptr: Unique::from(Box::leak(node)).cast() }
- }
-
- fn as_ptr(&self) -> NonNull<LeafNode<K, V>> {
- NonNull::from(self.ptr)
- }
-}
+/// is not a separate type and has no destructor.
+type BoxedNode<K, V> = NonNull<LeafNode<K, V>>;
/// 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> {}
+pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;
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 new() -> Self {
+ NodeRef::new_leaf().forget_type()
}
+}
- /// Borrows and returns a mutable reference to the leaf node owned by the root.
- /// # Safety
- /// The root node is a leaf.
- unsafe fn leaf_node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Leaf> {
- debug_assert!(self.height == 0);
- NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
+ fn new_leaf() -> Self {
+ Self::from_new_leaf(Box::new(unsafe { LeafNode::new() }))
}
- /// Borrows and returns a mutable reference to the internal node owned by the root.
- /// # Safety
- /// The root node is not a leaf.
- unsafe fn internal_node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
- debug_assert!(self.height > 0);
- NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
+ fn from_new_leaf(leaf: Box<LeafNode<K, V>>) -> Self {
+ NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _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 }
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
+ fn from_new_internal(internal: Box<InternalNode<K, V>>, height: usize) -> Self {
+ NodeRef { height, node: NonNull::from(Box::leak(internal)).cast(), _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 }
+impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> {
+ /// Mutably borrows the owned node. Unlike `reborrow_mut`, this is safe,
+ /// because the return value cannot be used to destroy the node itself,
+ /// and there cannot be other references to the tree (except during the
+ /// process of `into_iter` or `drop`, but that is horrific already).
+ pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
+ NodeRef { height: self.height, node: self.node, _marker: PhantomData }
}
- /// Packs the reference, aware of type and height, into a type-agnostic pointer.
- fn into_boxed_node(self) -> BoxedNode<K, V> {
- self.node
+ /// Slightly mutably borrows the owned node.
+ pub fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> {
+ NodeRef { height: self.height, node: self.node, _marker: PhantomData }
}
+}
+impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
/// 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 { ptr::read(&mut self.node) });
-
- self.node = BoxedNode::from_internal(new_node);
- self.height += 1;
+ new_node.edges[0].write(self.node);
+ let mut new_root = NodeRef::from_new_internal(new_node, self.height + 1);
+ new_root.borrow_mut().first_edge().correct_parent_link();
+ *self = new_root.forget_type();
- unsafe {
- let mut ret = self.internal_node_as_mut();
- ret.reborrow_mut().first_edge().correct_parent_link();
- ret
- }
+ // `self.borrow_mut()`, except that we just forgot we're internal now:
+ NodeRef { height: self.height, node: self.node, _marker: PhantomData }
}
/// Removes the internal root node, using its first child as the new root node.
/// 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.
+ /// it will not invalidate other 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 = BoxedNode::as_ptr(&self.node);
+ let top = self.node;
- let mut internal_node = unsafe { self.internal_node_as_mut() };
- let internal_node = NodeRef::as_internal_mut(&mut internal_node);
- self.node = unsafe { internal_node.edges[0].assume_init_read() };
- self.height -= 1;
- self.node_as_mut().clear_parent_link();
+ let internal_node = NodeRef { height: self.height, node: top, _marker: PhantomData };
+ *self = internal_node.first_edge().descend();
+ self.clear_parent_link();
unsafe {
- Global.dealloc(top.cast(), Layout::new::<InternalNode<K, V>>());
+ Global.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>());
}
}
}
/// although insert methods allow a mutable pointer to a value to coexist.
/// - When this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`,
/// but does not have a destructor, and must be cleaned up manually.
+/// Since any `NodeRef` allows navigating through the tree, `BorrowType`
+/// effectively applies to the entire tree, not just the node itself.
/// - `K` and `V`: These are the types of keys and values 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
/// such restrictions:
/// - For each type parameter, we can only define a method either generically
/// or for one particular type. For example, we cannot define a method like
-/// `key_at` generically for all `BorrowType`, because we want to return
+/// `key_at` generically for all `BorrowType`, because we want it to return
/// `&'a K` for most choices of `BorrowType`, but plain `K` for `Owned`.
-/// We cannot define `key_at` once for all types that have a lifetime.
+/// We cannot define `key_at` once for all types that carry a lifetime.
/// Therefore, we define it only for the least powerful type `Immut<'a>`.
/// - We cannot get implicit coercion from say `Mut<'a>` to `Immut<'a>`.
/// Therefore, we have to explicitly call `reborrow` on a more powerfull
/// `NodeRef` in order to reach a method like `key_at`.
-/// - All methods on `NodeRef` that return some kind of reference, except
-/// `reborrow` and `reborrow_mut`, take `self` by value and not by reference.
-/// This avoids silently returning a second reference somewhere in the tree.
-/// That is irrelevant when `BorrowType` is `Immut<'a>`, but the rule does
-/// no harm because we make those `NodeRef` implicitly `Copy`.
-/// The rule also avoids implicitly returning the lifetime of `&self`,
-/// instead of the lifetime contained in `BorrowType`.
-/// An exception to this rule are the insert functions.
-/// - Given the above, we need a `reborrow_mut` to explicitly copy a `Mut<'a>`
-/// `NodeRef` whenever we want to invoke a method returning an extra reference
-/// somewhere in the tree.
+///
+/// All methods on `NodeRef` that return some kind of reference, either:
+/// - Take `self` by value, and return the lifetime carried by `BorrowType`.
+/// Sometimes, to invoke such a method, we need to call `reborrow_mut`.
+/// - Take `self` by reference, and (implicitly) return that reference's
+/// lifetime, instead of the lifetime carried by `BorrowType`. That way,
+/// the borrow checker guarantees that the `NodeRef` remains borrowed as long
+/// as the returned reference is used.
+/// The methods supporting insert bend this rule by returning a raw pointer,
+/// i.e., a reference without any lifetime.
pub struct NodeRef<BorrowType, K, V, Type> {
- /// The number of levels below the node, a property of the node that cannot be
- /// entirely described by `Type` and that the node does not store itself either.
- /// Unconstrained if `Type` is `LeafOrInternal`, must be zero if `Type` is `Leaf`,
- /// and must be non-zero if `Type` is `Internal`.
+ /// The number of levels that the node and the level of leaves are apart, a
+ /// constant of the node that cannot be entirely described by `Type`, and that
+ /// the node itself does not store. We only need to store the height of the root
+ /// node, and derive every other node's height from it.
+ /// Must be zero if `Type` is `Leaf` and non-zero if `Type` is `Internal`.
height: usize,
/// The pointer to the leaf or internal node. The definition of `InternalNode`
/// ensures that the pointer is valid either way.
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::LeafOrInternal> {
- /// Unpack a node reference that was packed by `Root::into_boxed_node`.
- fn from_boxed_node(boxed_node: BoxedNode<K, V>, height: usize) -> Self {
- NodeRef { height, node: boxed_node.as_ptr(), _marker: PhantomData }
- }
-}
-
impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
/// Unpack a node reference that was packed as `NodeRef::parent`.
fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
}
impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
- /// Offers exclusive access to the data of an internal node.
- fn as_internal_mut(this: &mut Self) -> &'a mut InternalNode<K, V> {
- let ptr = Self::as_internal_ptr(this);
+ /// Borrows exclusive access to the data of an internal node.
+ fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
+ let ptr = Self::as_internal_ptr(self);
unsafe { &mut *ptr }
}
}
unsafe { usize::from((*Self::as_leaf_ptr(self)).len) }
}
- /// Returns the height of this node with respect to the leaf level. Zero height means the
- /// node is a leaf itself.
+ /// Returns the number of levels that the node and leaves are apart. Zero
+ /// height means the node is a leaf itself. If you picture trees with the
+ /// root on top, the number says at which elevation the node appears.
+ /// If you picture trees with leaves on top, the number says how high
+ /// the tree extends above the node.
pub fn height(&self) -> usize {
self.height
}
/// The node has more than `idx` initialized elements.
pub unsafe fn key_at(self, idx: usize) -> &'a K {
debug_assert!(idx < self.len());
- unsafe { Self::as_leaf(&self).keys.get_unchecked(idx).assume_init_ref() }
+ unsafe { self.into_leaf().keys.get_unchecked(idx).assume_init_ref() }
}
/// Exposes one of the values stored in the node.
/// The node has more than `idx` initialized elements.
unsafe fn val_at(self, idx: usize) -> &'a V {
debug_assert!(idx < self.len());
- unsafe { Self::as_leaf(&self).vals.get_unchecked(idx).assume_init_ref() }
+ unsafe { self.into_leaf().vals.get_unchecked(idx).assume_init_ref() }
}
}
/// that points to the current node. Returns `Err(self)` if the current node has
/// no parent, giving back the original `NodeRef`.
///
+ /// The method name assumes you picture trees with the root node on top.
+ ///
/// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
/// both, upon success, do nothing.
pub fn ascend(
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
/// Exposes the leaf portion of any leaf or internal node in an immutable tree.
- fn as_leaf(this: &Self) -> &'a LeafNode<K, V> {
- let ptr = Self::as_leaf_ptr(this);
+ fn into_leaf(self) -> &'a LeafNode<K, V> {
+ let ptr = Self::as_leaf_ptr(&self);
// SAFETY: there can be no mutable references into this tree borrowed as `Immut`.
unsafe { &*ptr }
}
let node = self.node;
let ret = self.ascend().ok();
unsafe {
- Global.dealloc(
+ Global.deallocate(
node.cast(),
if height > 0 {
Layout::new::<InternalNode<K, V>>()
}
impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+ /// Unsafely asserts to the compiler the static information that this node is a `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 }
+ }
+
/// Unsafely asserts to the compiler the static information that this node is an `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 }
}
+ /// Borrows exclusive access to the leaf portion of any leaf or internal node.
+ fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
+ let ptr = Self::as_leaf_ptr(self);
+ // SAFETY: we have exclusive access to the entire node.
+ unsafe { &mut *ptr }
+ }
+
/// Offers exclusive access to the leaf portion of any leaf or internal node.
- fn as_leaf_mut(this: &mut Self) -> &'a mut LeafNode<K, V> {
- let ptr = Self::as_leaf_ptr(this);
+ fn into_leaf_mut(mut self) -> &'a mut LeafNode<K, V> {
+ let ptr = Self::as_leaf_ptr(&mut self);
// SAFETY: we have exclusive access to the entire node.
unsafe { &mut *ptr }
}
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
- /// Offers exclusive access to a part of the key storage area.
+ /// Borrows exclusive access to an element of the key storage area.
///
/// # Safety
- /// The node has more than `idx` initialized elements.
- unsafe fn into_key_area_mut_at(mut self, idx: usize) -> &'a mut MaybeUninit<K> {
- debug_assert!(idx < self.len());
- unsafe { Self::as_leaf_mut(&mut self).keys.get_unchecked_mut(idx) }
+ /// `index` is in bounds of 0..CAPACITY
+ unsafe fn key_area_mut_at<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
+ where
+ I: SliceIndex<[MaybeUninit<K>], Output = Output>,
+ {
+ // 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.
+ unsafe { self.as_leaf_mut().keys.as_mut_slice().get_unchecked_mut(index) }
}
- /// Offers exclusive access to a part of the value storage area.
+ /// Borrows exclusive access to an element or slice of the node's value storage area.
///
/// # Safety
- /// The node has more than `idx` initialized elements.
- unsafe fn into_val_area_mut_at(mut self, idx: usize) -> &'a mut MaybeUninit<V> {
- debug_assert!(idx < self.len());
- unsafe { Self::as_leaf_mut(&mut self).vals.get_unchecked_mut(idx) }
+ /// `index` is in bounds of 0..CAPACITY
+ unsafe fn val_area_mut_at<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
+ where
+ I: SliceIndex<[MaybeUninit<V>], Output = Output>,
+ {
+ // 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.
+ 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> {
- /// Offers exclusive access to a part of the storage area for edge contents.
+ /// Borrows exclusive access to an element or slice of the node's storage area for edge contents.
///
/// # Safety
- /// The node has at least `idx` initialized elements.
- unsafe fn into_edge_area_mut_at(mut self, idx: usize) -> &'a mut MaybeUninit<BoxedNode<K, V>> {
- debug_assert!(idx <= self.len());
- unsafe { Self::as_internal_mut(&mut self).edges.get_unchecked_mut(idx) }
+ /// `index` is in bounds of 0..CAPACITY + 1
+ unsafe fn edge_area_mut_at<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
+ where
+ I: SliceIndex<[MaybeUninit<BoxedNode<K, V>>], Output = Output>,
+ {
+ // SAFETY: the caller will not be able to call further methods on self
+ // until the edge slice reference is dropped, as we have unique access
+ // for the lifetime of the borrow.
+ unsafe { self.as_internal_mut().edges.as_mut_slice().get_unchecked_mut(index) }
}
}
/// regardless of the node's current length,
/// having exclusive access to the entire node.
unsafe fn key_area(self) -> &'a [MaybeUninit<K>] {
- Self::as_leaf(&self).keys.as_slice()
+ self.into_leaf().keys.as_slice()
}
/// Exposes the entire value storage area in the node,
/// regardless of the node's current length,
/// having exclusive access to the entire node.
unsafe fn val_area(self) -> &'a [MaybeUninit<V>] {
- Self::as_leaf(&self).vals.as_slice()
+ self.into_leaf().vals.as_slice()
}
}
}
}
-impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
- /// Offers exclusive access to a sized slice of key storage area in the node.
- unsafe fn into_key_area_slice(mut self) -> &'a mut [MaybeUninit<K>] {
- let len = self.len();
- // 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.
- unsafe { Self::as_leaf_mut(&mut self).keys.get_unchecked_mut(..len) }
- }
-
- /// Offers exclusive access to a sized slice of value storage area in the node.
- unsafe fn into_val_area_slice(mut self) -> &'a mut [MaybeUninit<V>] {
- let len = self.len();
- // 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.
- unsafe { Self::as_leaf_mut(&mut self).vals.get_unchecked_mut(..len) }
- }
-}
-
-impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
- /// Offers exclusive access to a sized slice of storage area for edge contents in the node.
- unsafe fn into_edge_area_slice(mut self) -> &'a mut [MaybeUninit<BoxedNode<K, V>>] {
- let len = self.len();
- // SAFETY: the caller will not be able to call further methods on self
- // until the edge slice reference is dropped, as we have unique access
- // for the lifetime of the borrow.
- unsafe { Self::as_internal_mut(&mut self).edges.get_unchecked_mut(..len + 1) }
- }
-}
-
impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> {
/// # Safety
/// - The node has more than `idx` initialized elements.
- /// - The keys and values of the node must be initialized up to its current length.
unsafe fn into_key_val_mut_at(mut 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,
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
- /// Exposes exclusive access to the length of the node.
- pub fn into_len_mut(mut self) -> &'a mut u16 {
- &mut (*Self::as_leaf_mut(&mut self)).len
+ /// Borrows exclusive access to the length of the node.
+ pub fn len_mut(&mut self) -> &mut u16 {
+ &mut self.as_leaf_mut().len
}
}
impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
- /// Set or clear the node's link to its parent edge,
+ /// Sets the node's link to its parent edge,
/// without invalidating other references to the node.
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) };
}
+}
- /// Clear the node's link to its parent edge, freeing it from its tree.
- /// This only makes sense when there are no other references to the node.
+impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
+ /// Clears the root's link to its parent edge.
fn clear_parent_link(&mut self) {
- let leaf = Self::as_leaf_mut(self);
+ let mut root_node = self.borrow_mut();
+ let leaf = root_node.as_leaf_mut();
leaf.parent = None;
}
}
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.
+ /// Adds a key-value pair to the end of the node.
pub fn push(&mut self, key: K, val: V) {
- let len = unsafe { self.reborrow_mut().into_len_mut() };
+ let len = self.len_mut();
let idx = usize::from(*len);
assert!(idx < CAPACITY);
*len += 1;
unsafe {
- self.reborrow_mut().into_key_area_mut_at(idx).write(key);
- self.reborrow_mut().into_val_area_mut_at(idx).write(val);
+ self.key_area_mut_at(idx).write(key);
+ self.val_area_mut_at(idx).write(val);
}
}
- /// Adds a key/value pair to the beginning of the node.
+ /// Adds a key-value pair to the beginning of the node.
fn push_front(&mut self, key: K, val: V) {
- assert!(self.len() < CAPACITY);
-
+ let new_len = self.len() + 1;
+ assert!(new_len <= CAPACITY);
unsafe {
- *self.reborrow_mut().into_len_mut() += 1;
- slice_insert(self.reborrow_mut().into_key_area_slice(), 0, key);
- slice_insert(self.reborrow_mut().into_val_area_slice(), 0, val);
+ slice_insert(self.key_area_mut_at(..new_len), 0, key);
+ slice_insert(self.val_area_mut_at(..new_len), 0, val);
+ *self.len_mut() = new_len as u16;
}
}
}
}
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,
+ /// 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 = unsafe { self.reborrow_mut().into_len_mut() };
+ let len = self.len_mut();
let idx = usize::from(*len);
assert!(idx < CAPACITY);
*len += 1;
unsafe {
- self.reborrow_mut().into_key_area_mut_at(idx).write(key);
- self.reborrow_mut().into_val_area_mut_at(idx).write(val);
- self.reborrow_mut().into_edge_area_mut_at(idx + 1).write(edge.into_boxed_node());
+ self.key_area_mut_at(idx).write(key);
+ self.val_area_mut_at(idx).write(val);
+ self.edge_area_mut_at(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,
+ /// Adds a key-value pair, and an edge to go to the left of that pair,
/// to the beginning of the node.
fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
+ let new_len = self.len() + 1;
assert!(edge.height == self.height - 1);
- assert!(self.len() < CAPACITY);
+ assert!(new_len <= CAPACITY);
unsafe {
- *self.reborrow_mut().into_len_mut() += 1;
- slice_insert(self.reborrow_mut().into_key_area_slice(), 0, key);
- slice_insert(self.reborrow_mut().into_val_area_slice(), 0, val);
- slice_insert(self.reborrow_mut().into_edge_area_slice(), 0, edge.into_boxed_node());
+ slice_insert(self.key_area_mut_at(..new_len), 0, key);
+ slice_insert(self.val_area_mut_at(..new_len), 0, val);
+ slice_insert(self.edge_area_mut_at(..new_len + 1), 0, edge.node);
+ *self.len_mut() = new_len as u16;
}
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 the node and returns the pair.
+ /// Removes a key-value pair from the end of the node and returns the pair.
/// Also removes the edge that was to the right of that pair and, if the node
/// is internal, returns the orphaned subtree that this edge owned.
fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
let edge = match self.reborrow_mut().force() {
ForceResult::Leaf(_) => None,
ForceResult::Internal(internal) => {
- let boxed_node = ptr::read(internal.reborrow().edge_at(idx + 1));
- let mut edge = Root { node: boxed_node, height: internal.height - 1 };
- // In practice, clearing the parent is a waste of time, because we will
+ let node = ptr::read(internal.reborrow().edge_at(idx + 1));
+ let mut edge = Root { node, height: internal.height - 1, _marker: PhantomData };
+ // Currently, clearing the parent link is superfluous, because we will
// insert the node elsewhere and set its parent link again.
- edge.node_as_mut().clear_parent_link();
+ edge.clear_parent_link();
Some(edge)
}
};
- *self.reborrow_mut().into_len_mut() -= 1;
+ *self.len_mut() -= 1;
(key, val, edge)
}
}
- /// Removes a key/value pair from the beginning of the node and returns the pair.
+ /// Removes a key-value pair from the beginning of the node and returns the pair.
/// Also removes the edge that was to the left of that pair and, if the node is
/// internal, returns the orphaned subtree that this edge owned.
fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
let old_len = self.len();
unsafe {
- let key = slice_remove(self.reborrow_mut().into_key_area_slice(), 0);
- let val = slice_remove(self.reborrow_mut().into_val_area_slice(), 0);
+ let key = slice_remove(self.key_area_mut_at(..old_len), 0);
+ let val = slice_remove(self.val_area_mut_at(..old_len), 0);
let edge = match self.reborrow_mut().force() {
ForceResult::Leaf(_) => None,
ForceResult::Internal(mut internal) => {
- let boxed_node =
- slice_remove(internal.reborrow_mut().into_edge_area_slice(), 0);
- let mut edge = Root { node: boxed_node, height: internal.height - 1 };
- // In practice, clearing the parent is a waste of time, because we will
+ let node = slice_remove(internal.edge_area_mut_at(..old_len + 1), 0);
+ let mut edge = Root { node, height: internal.height - 1, _marker: PhantomData };
+ // Currently, clearing the parent link is superfluous, because we will
// insert the node elsewhere and set its parent link again.
- edge.node_as_mut().clear_parent_link();
+ edge.clear_parent_link();
internal.correct_childrens_parent_links(0..old_len);
}
};
- *self.reborrow_mut().into_len_mut() -= 1;
+ *self.len_mut() -= 1;
(key, val, edge)
}
}
fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) {
- let leaf = Self::as_leaf_mut(&mut self);
+ let leaf = self.as_leaf_mut();
let keys = MaybeUninit::slice_as_mut_ptr(&mut leaf.keys);
let vals = MaybeUninit::slice_as_mut_ptr(&mut leaf.vals);
(keys, vals)
}
}
-/// 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
+/// 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
+/// 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> {
}
impl<Node, Type> Handle<Node, Type> {
- /// Retrieves the node that contains the edge or key/value pair this handle points to.
+ /// Retrieves the node that contains the edge or key-value pair this handle points to.
pub fn into_node(self) -> Node {
self.node
}
}
impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
- /// Creates a new handle to a key/value pair in `node`.
+ /// 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());
impl<BorrowType, K, V, NodeType> NodeRef<BorrowType, K, V, NodeType> {
/// Could be a public implementation of PartialEq, but only used in this module.
fn eq(&self, other: &Self) -> bool {
- let Self { node, height, _marker: _ } = self;
+ let Self { node, height, _marker } = self;
if node.eq(&other.node) {
debug_assert_eq!(*height, other.height);
true
for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
fn eq(&self, other: &Self) -> bool {
- let Self { node, idx, _marker: _ } = self;
+ let Self { node, idx, _marker } = self;
node.eq(&other.node) && *idx == other.idx
}
}
for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
- let Self { node, idx, _marker: _ } = self;
+ let Self { node, idx, _marker } = self;
if node.eq(&other.node) { Some(idx.cmp(&other.idx)) } else { None }
}
}
}
impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
+ /// Unsafely asserts to the compiler the static information that the handle's node is a `Leaf`.
+ pub unsafe fn cast_to_leaf_unchecked(
+ self,
+ ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, HandleType> {
+ let node = unsafe { self.node.cast_to_leaf_unchecked() };
+ Handle { node, idx: self.idx, _marker: PhantomData }
+ }
+
/// 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.
}
}
-enum InsertionPlace {
- Left(usize),
- Right(usize),
+pub enum LeftOrRight<T> {
+ Left(T),
+ Right(T),
}
/// Given an edge index where we want to insert into a node filled to capacity,
/// 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) {
+fn splitpoint(edge_idx: usize) -> (usize, LeftOrRight<usize>) {
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))),
+ 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> {
- /// Inserts a new key/value pair between the key/value pairs to the right and left of
+ /// 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 {
debug_assert!(self.node.len() < CAPACITY);
+ let new_len = self.node.len() + 1;
unsafe {
- *self.node.reborrow_mut().into_len_mut() += 1;
- slice_insert(self.node.reborrow_mut().into_key_area_slice(), self.idx, key);
- slice_insert(self.node.reborrow_mut().into_val_area_slice(), self.idx, val);
+ slice_insert(self.node.key_area_mut_at(..new_len), self.idx, key);
+ slice_insert(self.node.val_area_mut_at(..new_len), self.idx, val);
+ *self.node.len_mut() = new_len as u16;
- self.node.reborrow_mut().into_val_area_mut_at(self.idx).assume_init_mut()
+ self.node.val_area_mut_at(self.idx).assume_init_mut()
}
}
}
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
+ /// 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.
} 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 result = middle.split();
let mut insertion_edge = match insertion {
- InsertionPlace::Left(insert_idx) => unsafe {
- Handle::new_edge(left.reborrow_mut(), insert_idx)
+ LeftOrRight::Left(insert_idx) => unsafe {
+ Handle::new_edge(result.left.reborrow_mut(), insert_idx)
},
- InsertionPlace::Right(insert_idx) => unsafe {
- Handle::new_edge(right.leaf_node_as_mut(), insert_idx)
+ LeftOrRight::Right(insert_idx) => unsafe {
+ Handle::new_edge(result.right.borrow_mut(), insert_idx)
},
};
let val_ptr = insertion_edge.insert_fit(key, val);
- (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), val_ptr)
+ (InsertResult::Split(result), 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.
+ /// Fixes the parent pointer and index in the child node that this edge
+ /// links to. This is useful when the ordering of edges has been changed,
fn correct_parent_link(self) {
// Create backpointer without invalidating other references to the node.
let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
}
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
+ /// 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!(self.node.len() < CAPACITY);
debug_assert!(edge.height == self.node.height - 1);
+ let new_len = self.node.len() + 1;
- let boxed_node = edge.into_boxed_node();
unsafe {
- *self.node.reborrow_mut().into_len_mut() += 1;
- slice_insert(self.node.reborrow_mut().into_key_area_slice(), self.idx, key);
- slice_insert(self.node.reborrow_mut().into_val_area_slice(), self.idx, val);
- slice_insert(self.node.reborrow_mut().into_edge_area_slice(), self.idx + 1, boxed_node);
+ slice_insert(self.node.key_area_mut_at(..new_len), self.idx, key);
+ slice_insert(self.node.val_area_mut_at(..new_len), self.idx, val);
+ slice_insert(self.node.edge_area_mut_at(..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)..=self.node.len());
+ self.node.correct_childrens_parent_links(self.idx + 1..new_len + 1);
}
}
- /// 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
+ /// 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,
} 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 result = middle.split();
let mut insertion_edge = match insertion {
- InsertionPlace::Left(insert_idx) => unsafe {
- Handle::new_edge(left.reborrow_mut(), insert_idx)
+ LeftOrRight::Left(insert_idx) => unsafe {
+ Handle::new_edge(result.left.reborrow_mut(), insert_idx)
},
- InsertionPlace::Right(insert_idx) => unsafe {
- Handle::new_edge(right.internal_node_as_mut(), insert_idx)
+ LeftOrRight::Right(insert_idx) => unsafe {
+ Handle::new_edge(result.right.borrow_mut(), insert_idx)
},
};
insertion_edge.insert_fit(key, val, edge);
- InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right })
+ InsertResult::Split(result)
}
}
}
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
+ /// 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.
///
(InsertResult::Fit(handle), ptr) => {
return (InsertResult::Fit(handle.forget_node_type()), ptr);
}
- (InsertResult::Split(split), val_ptr) => (split, val_ptr),
+ (InsertResult::Split(split), val_ptr) => (split.forget_node_type(), val_ptr),
};
loop {
split = match split.left.ascend() {
- Ok(parent) => match parent.insert(split.k, split.v, split.right) {
+ Ok(parent) => match parent.insert(split.kv.0, split.kv.1, split.right) {
InsertResult::Fit(handle) => {
return (InsertResult::Fit(handle.forget_node_type()), val_ptr);
}
- InsertResult::Split(split) => split,
+ InsertResult::Split(split) => split.forget_node_type(),
},
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.
///
+ /// The method name assumes you picture trees with the root node on top.
+ ///
/// `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> {
// reference (Rust issue #73987) and invalidate any other references
// to or inside the array, should any be around.
let parent_ptr = NodeRef::as_internal_ptr(&self.node);
- let boxed_node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() };
- NodeRef::from_boxed_node(boxed_node, self.node.height - 1)
+ 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::Mut<'a>, K, V, NodeType>, marker::KV> {
- pub fn into_key_mut(self) -> &'a mut K {
- unsafe { self.node.into_key_area_mut_at(self.idx).assume_init_mut() }
+ pub fn key_mut(&mut self) -> &mut K {
+ unsafe { self.node.key_area_mut_at(self.idx).assume_init_mut() }
}
pub fn into_val_mut(self) -> &'a mut V {
- unsafe { self.node.into_val_area_mut_at(self.idx).assume_init_mut() }
+ let leaf = self.node.into_leaf_mut();
+ unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }
}
}
// We cannot call separate key and value methods, because calling the second one
// invalidates the reference returned by the first.
unsafe {
- let leaf = NodeRef::as_leaf_mut(&mut self.node.reborrow_mut());
+ 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)
}
}
-}
-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 calculating the length of the new node.
- fn split_new_node_len(&self) -> usize {
- debug_assert!(self.idx < self.node.len());
- self.node.len() - self.idx - 1
+ /// Replace the key and value that the KV handle refers to.
+ 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<'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 split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V) {
- let new_len = self.split_new_node_len();
+ debug_assert!(self.idx < self.node.len());
+ let new_len = self.node.len() - self.idx - 1;
new_node.len = new_len as u16;
unsafe {
let k = ptr::read(self.node.reborrow().key_at(self.idx));
new_len,
);
- *self.node.reborrow_mut().into_len_mut() = self.idx as u16;
+ *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> {
/// Splits the underlying node into three parts:
///
- /// - The node is truncated to only contain the key/value pairs to the left of
+ /// - The node is truncated to only contain the key-value pairs to the left 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
+ /// - 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>) {
+ pub fn split(mut self) -> SplitResult<'a, K, V, marker::Leaf> {
unsafe {
let mut new_node = Box::new(LeafNode::new());
- let (k, v) = self.split_leaf_data(&mut new_node);
+ let kv = self.split_leaf_data(&mut new_node);
- let right = Root { node: BoxedNode::from_leaf(new_node), height: 0 };
- (self.node, k, v, right)
+ let right = NodeRef::from_new_leaf(new_node);
+ SplitResult { left: self.node, kv, right }
}
}
- /// Removes the key/value pair pointed to by this handle and returns it, along with the edge
- /// that the key/value pair collapsed into.
+ /// 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>) {
+ let old_len = self.node.len();
unsafe {
- let k = slice_remove(self.node.reborrow_mut().into_key_area_slice(), self.idx);
- let v = slice_remove(self.node.reborrow_mut().into_val_area_slice(), self.idx);
- *self.node.reborrow_mut().into_len_mut() -= 1;
+ let k = slice_remove(self.node.key_area_mut_at(..old_len), self.idx);
+ let v = slice_remove(self.node.val_area_mut_at(..old_len), self.idx);
+ *self.node.len_mut() = (old_len - 1) as u16;
((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
+ /// - The node is truncated to only contain the edges and key-value pairs to the
/// left 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
+ /// - 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>) {
+ pub fn split(mut self) -> SplitResult<'a, K, V, marker::Internal> {
unsafe {
let mut new_node = Box::new(InternalNode::new());
- let new_len = self.split_new_node_len();
- // Move edges out before reducing length:
+ let kv = self.split_leaf_data(&mut new_node.data);
+ let new_len = usize::from(new_node.data.len);
ptr::copy_nonoverlapping(
self.node.reborrow().edge_area().as_ptr().add(self.idx + 1),
new_node.edges.as_mut_ptr(),
new_len + 1,
);
- let (k, v) = self.split_leaf_data(&mut new_node.data);
let height = self.node.height;
- let mut right = Root { node: BoxedNode::from_internal(new_node), height };
+ let mut right = NodeRef::from_new_internal(new_node, height);
- right.internal_node_as_mut().correct_childrens_parent_links(0..=new_len);
+ right.borrow_mut().correct_childrens_parent_links(0..=new_len);
- (self.node, k, v, right)
+ SplitResult { left: self.node, kv, right }
}
}
+}
- /// 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> {
+/// Represents a session for evaluating and performing a balancing operation
+/// around an internal key-value pair.
+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) };
- let mut left_node = self1.left_edge().descend();
- let left_len = left_node.len();
- let right_node = self2.right_edge().descend();
+ 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> {
+ /// Chooses a balancing context involving the node as a child, thus between
+ /// the KV immediately to the left or to the right in the parent node.
+ /// Returns an `Err` if there is no parent.
+ /// Panics if the parent is empty.
+ ///
+ /// Prefers the left side, to be optimal if the given node is somehow
+ /// underfull, meaning here only that it has fewer elements than its left
+ /// sibling and than its right sibling, if they exist. In that case,
+ /// merging with the left sibling is faster, since we only need to move
+ /// the node's N elements, instead of shifting them to the right and moving
+ /// more than N elements in front. Stealing from the left sibling is also
+ /// typically faster, since we only need to shift the node's N elements to
+ /// the right, instead of shifting at least N of the sibling's elements to
+ /// the left.
+ 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
+ }
+
+ /// Returns `true` if it is valid to call `.merge()` in the balancing context,
+ /// i.e., whether there is enough room in a node to hold the combination of
+ /// both adjacent child nodes, along with the key-value pair in the parent.
+ 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> {
+ /// Merges the parent's key-value pair and both adjacent child nodes into
+ /// the left node and returns an edge handle in that expanded left node.
+ /// If `track_edge_idx` is given some value, the returned edge corresponds
+ /// to where the edge in that child node ended up,
+ ///
+ /// Panics unless we `.can_merge()`.
+ pub fn merge(
+ self,
+ track_edge_idx: Option<LeftOrRight<usize>>,
+ ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
+ 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 right_node = self.right_child;
let right_len = right_node.len();
+ let new_left_len = old_left_len + 1 + right_len;
- assert!(left_len + right_len < CAPACITY);
+ assert!(new_left_len <= CAPACITY);
+ assert!(match track_edge_idx {
+ None => true,
+ Some(LeftOrRight::Left(idx)) => idx <= old_left_len,
+ Some(LeftOrRight::Right(idx)) => idx <= right_len,
+ });
unsafe {
- *left_node.reborrow_mut().into_len_mut() += right_len as u16 + 1;
+ *left_node.len_mut() = new_left_len as u16;
- let parent_key = slice_remove(self.node.reborrow_mut().into_key_area_slice(), self.idx);
- left_node.reborrow_mut().into_key_area_mut_at(left_len).write(parent_key);
+ let parent_key =
+ slice_remove(parent_node.key_area_mut_at(..old_parent_len), parent_idx);
+ left_node.key_area_mut_at(old_left_len).write(parent_key);
ptr::copy_nonoverlapping(
right_node.reborrow().key_area().as_ptr(),
- left_node.reborrow_mut().into_key_area_slice().as_mut_ptr().add(left_len + 1),
+ left_node.key_area_mut_at(old_left_len + 1..).as_mut_ptr(),
right_len,
);
- let parent_val = slice_remove(self.node.reborrow_mut().into_val_area_slice(), self.idx);
- left_node.reborrow_mut().into_val_area_mut_at(left_len).write(parent_val);
+ let parent_val =
+ slice_remove(parent_node.val_area_mut_at(..old_parent_len), parent_idx);
+ left_node.val_area_mut_at(old_left_len).write(parent_val);
ptr::copy_nonoverlapping(
right_node.reborrow().val_area().as_ptr(),
- left_node.reborrow_mut().into_val_area_slice().as_mut_ptr().add(left_len + 1),
+ left_node.val_area_mut_at(old_left_len + 1..).as_mut_ptr(),
right_len,
);
- slice_remove(&mut self.node.reborrow_mut().into_edge_area_slice(), self.idx + 1);
- let self_len = self.node.len();
- self.node.correct_childrens_parent_links(self.idx + 1..self_len);
- *self.node.reborrow_mut().into_len_mut() -= 1;
+ slice_remove(&mut parent_node.edge_area_mut_at(..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 self.node.height > 1 {
+ if parent_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_to_internal_unchecked();
+ let mut left_node = left_node.reborrow_mut().cast_to_internal_unchecked();
let right_node = right_node.cast_to_internal_unchecked();
ptr::copy_nonoverlapping(
right_node.reborrow().edge_area().as_ptr(),
- left_node.reborrow_mut().into_edge_area_slice().as_mut_ptr().add(left_len + 1),
+ left_node.edge_area_mut_at(old_left_len + 1..).as_mut_ptr(),
right_len + 1,
);
- left_node.correct_childrens_parent_links(left_len + 1..=left_len + 1 + right_len);
+ left_node.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
- Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
+ Global.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
} else {
- Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
+ Global.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
}
- Handle::new_edge(self.node, self.idx)
+ let new_idx = match track_edge_idx {
+ None => 0,
+ Some(LeftOrRight::Left(idx)) => idx,
+ Some(LeftOrRight::Right(idx)) => old_left_len + 1 + idx,
+ };
+ Handle::new_edge(left_node, new_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) {
+ /// Removes a key-value pair from the left child and places it in the key-value storage
+ /// of the parent, while pushing the old parent key-value pair into the right child.
+ /// Returns a handle to the edge in the right child corresponding to where the original
+ /// edge specified by `track_right_edge_idx` ended up.
+ pub fn steal_left(
+ mut self,
+ track_right_edge_idx: usize,
+ ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
unsafe {
- let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop();
+ let (k, v, edge) = self.left_child.pop();
- let k = mem::replace(self.kv_mut().0, k);
- let v = mem::replace(self.kv_mut().1, v);
+ let (k, v) = self.parent.replace_kv(k, v);
- match self.reborrow_mut().right_edge().descend().force() {
+ match self.right_child.reborrow_mut().force() {
ForceResult::Leaf(mut leaf) => leaf.push_front(k, v),
ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()),
}
+
+ Handle::new_edge(self.right_child, 1 + track_right_edge_idx)
}
}
- /// 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) {
+ /// Removes a key-value pair from the right child and places it in the key-value storage
+ /// of the parent, while pushing the old parent key-value pair onto the left child.
+ /// Returns a handle to the edge in the left child specified by `track_left_edge_idx`,
+ /// which didn't move.
+ pub fn steal_right(
+ mut self,
+ track_left_edge_idx: usize,
+ ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
unsafe {
- let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front();
+ let (k, v, edge) = self.right_child.pop_front();
- let k = mem::replace(self.kv_mut().0, k);
- let v = mem::replace(self.kv_mut().1, v);
+ let (k, v) = self.parent.replace_kv(k, v);
- match self.reborrow_mut().left_edge().descend().force() {
+ match self.left_child.reborrow_mut().force() {
ForceResult::Leaf(mut leaf) => leaf.push(k, v),
ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()),
}
+
+ Handle::new_edge(self.left_child, track_left_edge_idx)
}
}
/// This does stealing similar to `steal_left` but steals multiple elements at once.
pub fn bulk_steal_left(&mut self, count: usize) {
+ assert!(count > 0);
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();
+ 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();
// Make sure that we may steal safely.
- assert!(right_len + count <= CAPACITY);
- assert!(left_len >= count);
+ assert!(old_right_len + count <= CAPACITY);
+ assert!(old_left_len >= count);
- let new_left_len = 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;
- // Move data.
+ // Move leaf 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();
+ let kv = self.parent.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);
+ ptr::copy(right_kv.0, right_kv.0.add(count), old_right_len);
+ ptr::copy(right_kv.1, right_kv.1.add(count), old_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 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.reborrow_mut().into_len_mut() -= count as u16;
- *right_node.reborrow_mut().into_len_mut() += count as u16;
-
- match (left_node.force(), right_node.force()) {
+ match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
(ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
// Make room for stolen edges.
let left = left.reborrow();
- let right_edges = right.reborrow_mut().into_edge_area_slice().as_mut_ptr();
- ptr::copy(right_edges, right_edges.add(count), right_len + 1);
- right.correct_childrens_parent_links(count..count + right_len + 1);
+ let right_edges = right.edge_area_mut_at(..).as_mut_ptr();
+ ptr::copy(right_edges, right_edges.add(count), old_right_len + 1);
+ right.correct_childrens_parent_links(count..new_right_len + 1);
+ // Steal edges.
move_edges(left, new_left_len + 1, right, 0, count);
}
(ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
/// The symmetric clone of `bulk_steal_left`.
pub fn bulk_steal_right(&mut self, count: usize) {
+ assert!(count > 0);
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();
+ 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();
// Make sure that we may steal safely.
- assert!(left_len + count <= CAPACITY);
- assert!(right_len >= count);
+ assert!(old_left_len + count <= CAPACITY);
+ assert!(old_right_len >= count);
- let new_right_len = 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;
- // Move data.
+ // Move leaf 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();
+ let kv = self.parent.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 parent's key-value pair to the left child.
+ move_kv(parent_kv, 0, left_kv, old_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_kv(right_kv, 0, left_kv, old_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
+ // Fill gap where stolen elements used to be.
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.reborrow_mut().into_len_mut() += count as u16;
- *right_node.reborrow_mut().into_len_mut() -= count as u16;
-
- match (left_node.force(), right_node.force()) {
+ match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
(ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
- move_edges(right.reborrow(), 0, left, left_len + 1, count);
+ // Steal edges.
+ move_edges(right.reborrow(), 0, left, old_left_len + 1, count);
- // Fix right indexing.
- let right_edges = right.reborrow_mut().into_edge_area_slice().as_mut_ptr();
+ // Fill gap where stolen edges used to be.
+ let right_edges = right.edge_area_mut_at(..).as_mut_ptr();
ptr::copy(right_edges.add(count), right_edges, new_right_len + 1);
right.correct_childrens_parent_links(0..=new_right_len);
}
) {
unsafe {
let source_ptr = source.edge_area().as_ptr();
- let dest_ptr = dest.reborrow_mut().into_edge_area_slice().as_mut_ptr();
- ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr.add(dest_offset), count);
+ let dest_ptr = dest.edge_area_mut_at(dest_offset..).as_mut_ptr();
+ ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr, count);
dest.correct_childrens_parent_links(dest_offset..dest_offset + count);
}
}
right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
) {
unsafe {
- let left_new_len = self.idx;
+ let new_left_len = self.idx;
let mut left_node = self.reborrow_mut().into_node();
- let right_new_len = left_node.len() - left_new_len;
+ let new_right_len = left_node.len() - new_left_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 {
+ if new_right_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);
+ move_kv(left_kv, new_left_len, right_kv, 0, new_right_len);
- *left_node.reborrow_mut().into_len_mut() = left_new_len as u16;
- *right_node.reborrow_mut().into_len_mut() = right_new_len as u16;
+ *left_node.len_mut() = new_left_len as u16;
+ *right_node.len_mut() = new_right_len as u16;
match (left_node.force(), right_node.force()) {
(ForceResult::Internal(left), ForceResult::Internal(right)) => {
let left = left.reborrow();
- move_edges(left, left_new_len + 1, right, 1, right_new_len);
+ move_edges(left, new_left_len + 1, right, 1, new_right_len);
}
(ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
_ => unreachable!(),
}
/// 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>,
+pub struct SplitResult<'a, K, V, NodeType> {
+ // Altered node in existing tree with elements and edges that belong to the left of `kv`.
+ pub left: NodeRef<marker::Mut<'a>, K, V, NodeType>,
// 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 kv: (K, V),
+ // Owned, unattached, new node with elements and edges that belong to the right of `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 enum InsertResult<'a, K, V, Type> {
- Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
- Split(SplitResult<'a, K, V>),
+pub enum InsertResult<'a, K, V, NodeType> {
+ Fit(Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV>),
+ Split(SplitResult<'a, K, V, NodeType>),
}
pub mod marker {
projects / rustc.git / blobdiff