use core::cmp::Ordering;
use core::marker::PhantomData;
use core::mem::{self, MaybeUninit};
use core::ptr::{self, NonNull, Unique};
use crate::alloc::{AllocRef, Global, Layout};
use crate::boxed::Box;
const B: usize = 6;
pub const CAPACITY: usize = 2 * B - 1;
pub const MIN_LEN_AFTER_SPLIT: usize = B - 1;
const KV_IDX_CENTER: usize = B - 1;
const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
const EDGE_IDX_RIGHT_OF_CENTER: usize = B;
struct LeafNode<K, V> {
parent: Option<NonNull<InternalNode<K, V>>>,
parent_idx: MaybeUninit<u16>,
len: u16,
keys: [MaybeUninit<K>; CAPACITY],
vals: [MaybeUninit<V>; CAPACITY],
}
impl<K, V> LeafNode<K, V> {
unsafe fn new() -> Self {
LeafNode {
keys: MaybeUninit::uninit_array(),
vals: MaybeUninit::uninit_array(),
parent: None,
parent_idx: MaybeUninit::uninit(),
len: 0,
}
}
}
#[repr(C)]
struct InternalNode<K, V> {
data: LeafNode<K, V>,
edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
}
impl<K, V> InternalNode<K, V> {
unsafe fn new() -> Self {
InternalNode { data: unsafe { LeafNode::new() }, edges: MaybeUninit::uninit_array() }
}
}
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)
}
}
pub struct Root<K, V> {
node: BoxedNode<K, V>,
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> {
pub fn height(&self) -> usize {
self.height
}
pub fn new_leaf() -> Self {
Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 }
}
pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> {
NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
}
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 }
}
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 }
}
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 }
}
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 }
}
fn into_boxed_node(self) -> BoxedNode<K, V> {
self.node
}
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;
unsafe {
let mut ret = self.internal_node_as_mut();
ret.reborrow_mut().first_edge().correct_parent_link();
ret
}
}
pub fn pop_internal_level(&mut self) {
assert!(self.height > 0);
let top = BoxedNode::as_ptr(&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();
unsafe {
Global.dealloc(top.cast(), Layout::new::<InternalNode<K, V>>());
}
}
}
pub struct NodeRef<BorrowType, K, V, Type> {
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::LeafOrInternal> {
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> {
fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
debug_assert!(height > 0);
NodeRef { height, node: node.cast(), _marker: PhantomData }
}
}
impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
fn as_internal_ptr(this: &Self) -> *mut InternalNode<K, V> {
this.node.as_ptr() as *mut InternalNode<K, V>
}
}
impl<'a, K, V> NodeRef<marker::Immut<'a>, K, V, marker::Internal> {
fn as_internal(this: &Self) -> &'a InternalNode<K, V> {
let ptr = Self::as_internal_ptr(this);
unsafe { &*ptr }
}
}
impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
fn as_internal_mut(this: &mut Self) -> &'a mut InternalNode<K, V> {
let ptr = Self::as_internal_ptr(this);
unsafe { &mut *ptr }
}
}
impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
pub fn len(&self) -> usize {
unsafe { usize::from((*Self::as_leaf_ptr(self)).len) }
}
pub fn height(&self) -> usize {
self.height
}
pub fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
NodeRef { height: self.height, node: self.node, _marker: PhantomData }
}
fn as_leaf_ptr(this: &Self) -> *mut LeafNode<K, V> {
this.node.as_ptr()
}
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
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 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() }
}
}
impl<'a, K, V> NodeRef<marker::Immut<'a>, K, V, marker::Internal> {
unsafe fn edge_at(self, idx: usize) -> &'a BoxedNode<K, V> {
debug_assert!(idx <= self.len());
unsafe { Self::as_internal(&self).edges.get_unchecked(idx).assume_init_ref() }
}
}
impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
pub fn ascend(
self,
) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
let leaf_ptr: *const _ = Self::as_leaf_ptr(&self);
unsafe { (*leaf_ptr).parent }
.as_ref()
.map(|parent| Handle {
node: NodeRef::from_internal(*parent, self.height + 1),
idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
_marker: PhantomData,
})
.ok_or(self)
}
pub fn first_edge(self) -> Handle<Self, marker::Edge> {
unsafe { Handle::new_edge(self, 0) }
}
pub fn last_edge(self) -> Handle<Self, marker::Edge> {
let len = self.len();
unsafe { Handle::new_edge(self, len) }
}
pub fn first_kv(self) -> Handle<Self, marker::KV> {
let len = self.len();
assert!(len > 0);
unsafe { Handle::new_kv(self, 0) }
}
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> {
fn as_leaf(this: &Self) -> &'a LeafNode<K, V> {
let ptr = Self::as_leaf_ptr(this);
unsafe { &*ptr }
}
}
impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
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> {
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 }
}
unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
NodeRef { height: self.height, node: self.node, _marker: PhantomData }
}
fn as_leaf_mut(this: &mut Self) -> &'a mut LeafNode<K, V> {
let ptr = Self::as_leaf_ptr(this);
unsafe { &mut *ptr }
}
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
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) }
}
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) }
}
}
impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
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) }
}
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
unsafe fn key_area(self) -> &'a [MaybeUninit<K>] {
Self::as_leaf(&self).keys.as_slice()
}
unsafe fn val_area(self) -> &'a [MaybeUninit<V>] {
Self::as_leaf(&self).vals.as_slice()
}
}
impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::Internal> {
unsafe fn edge_area(self) -> &'a [MaybeUninit<BoxedNode<K, V>>] {
Self::as_internal(&self).edges.as_slice()
}
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
unsafe fn into_key_area_slice(mut self) -> &'a mut [MaybeUninit<K>] {
let len = self.len();
unsafe { Self::as_leaf_mut(&mut self).keys.get_unchecked_mut(..len) }
}
unsafe fn into_val_area_slice(mut self) -> &'a mut [MaybeUninit<V>] {
let len = self.len();
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> {
unsafe fn into_edge_area_slice(mut self) -> &'a mut [MaybeUninit<BoxedNode<K, V>>] {
let len = self.len();
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> {
unsafe fn into_key_val_mut_at(mut self, idx: usize) -> (&'a K, &'a mut V) {
let leaf = Self::as_leaf_ptr(&mut self);
let keys = unsafe { &raw const (*leaf).keys };
let vals = unsafe { &raw mut (*leaf).vals };
let keys: *const [_] = keys;
let vals: *mut [_] = vals;
let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() };
(key, val)
}
}
impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
pub fn into_len_mut(mut self) -> &'a mut u16 {
&mut (*Self::as_leaf_mut(&mut self)).len
}
}
impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
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) };
}
fn clear_parent_link(&mut self) {
let leaf = Self::as_leaf_mut(self);
leaf.parent = None;
}
}
impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
pub fn push(&mut self, key: K, val: V) {
let len = unsafe { self.reborrow_mut().into_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);
}
}
fn push_front(&mut self, key: K, val: V) {
assert!(self.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);
}
}
}
impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
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> {
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 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());
Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
}
}
fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
assert!(edge.height == self.height - 1);
assert!(self.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());
}
self.correct_all_childrens_parent_links();
}
}
impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
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.reborrow().key_at(idx));
let val = ptr::read(self.reborrow().val_at(idx));
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 };
edge.node_as_mut().clear_parent_link();
Some(edge)
}
};
*self.reborrow_mut().into_len_mut() -= 1;
(key, val, edge)
}
}
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.reborrow_mut().into_key_area_slice(), 0);
let val = slice_remove(self.reborrow_mut().into_val_area_slice(), 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 };
edge.node_as_mut().clear_parent_link();
internal.correct_childrens_parent_links(0..old_len);
Some(edge)
}
};
*self.reborrow_mut().into_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 keys = MaybeUninit::slice_as_mut_ptr(&mut leaf.keys);
let vals = MaybeUninit::slice_as_mut_ptr(&mut leaf.vals);
(keys, vals)
}
}
impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
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,
})
}
}
}
pub struct Handle<Node, Type> {
node: Node,
idx: usize,
_marker: PhantomData<Type>,
}
impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
impl<Node: Copy, Type> Clone for Handle<Node, Type> {
fn clone(&self) -> Self {
*self
}
}
impl<Node, Type> Handle<Node, Type> {
pub fn into_node(self) -> Node {
self.node
}
pub fn idx(&self) -> usize {
self.idx
}
}
impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
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> NodeRef<BorrowType, K, V, NodeType> {
fn eq(&self, other: &Self) -> bool {
let Self { node, height, _marker: _ } = self;
if node.eq(&other.node) {
debug_assert_eq!(*height, other.height);
true
} else {
false
}
}
}
impl<BorrowType, K, V, NodeType, HandleType> PartialEq
for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
fn eq(&self, other: &Self) -> bool {
let Self { node, idx, _marker: _ } = self;
node.eq(&other.node) && *idx == other.idx
}
}
impl<BorrowType, K, V, NodeType, HandleType> PartialOrd
for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
let Self { node, idx, _marker: _ } = self;
if node.eq(&other.node) { Some(idx.cmp(&other.idx)) } else { None }
}
}
impl<BorrowType, K, V, NodeType, HandleType>
Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
{
pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
}
}
impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
pub unsafe fn reborrow_mut(
&mut self,
) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
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> {
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),
}
fn splitpoint(edge_idx: usize) -> (usize, InsertionPlace) {
debug_assert!(edge_idx <= CAPACITY);
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> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
fn insert_fit(&mut self, key: K, val: V) -> *mut V {
debug_assert!(self.node.len() < CAPACITY);
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);
self.node.reborrow_mut().into_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> {
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.leaf_node_as_mut(), 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> {
fn correct_parent_link(self) {
let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
let idx = self.idx;
let mut child = self.descend();
child.set_parent_link(ptr, idx);
}
}
impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
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 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);
self.node.correct_childrens_parent_links((self.idx + 1)..=self.node.len());
}
}
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();
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.internal_node_as_mut(), insert_idx)
},
};
insertion_edge.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> {
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> {
pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
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)
}
}
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.key_at(self.idx) }, unsafe { self.node.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_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() }
}
}
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) {
unsafe {
let leaf = NodeRef::as_leaf_mut(&mut self.node.reborrow_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> {
fn split_new_node_len(&self) -> usize {
debug_assert!(self.idx < self.node.len());
self.node.len() - self.idx - 1
}
fn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V) {
let new_len = self.split_new_node_len();
new_node.len = new_len as u16;
unsafe {
let k = ptr::read(self.node.reborrow().key_at(self.idx));
let v = ptr::read(self.node.reborrow().val_at(self.idx));
ptr::copy_nonoverlapping(
self.node.reborrow().key_area().as_ptr().add(self.idx + 1),
new_node.keys.as_mut_ptr(),
new_len,
);
ptr::copy_nonoverlapping(
self.node.reborrow().val_area().as_ptr().add(self.idx + 1),
new_node.vals.as_mut_ptr(),
new_len,
);
*self.node.reborrow_mut().into_len_mut() = self.idx as u16;
(k, v)
}
}
}
impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
pub fn split(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.split_leaf_data(&mut new_node);
let right = Root { node: BoxedNode::from_leaf(new_node), height: 0 };
(self.node, k, v, right)
}
}
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.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;
((k, v), self.left_edge())
}
}
}
impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
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> {
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 new_len = self.split_new_node_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 };
right.internal_node_as_mut().correct_childrens_parent_links(0..=new_len);
(self.node, k, v, right)
}
}
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 {
*left_node.reborrow_mut().into_len_mut() += right_len as u16 + 1;
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);
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),
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);
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),
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;
if self.node.height > 1 {
let mut left_node = left_node.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),
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)
}
}
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()),
}
}
}
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()),
}
}
}
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();
assert!(right_len + count <= CAPACITY);
assert!(left_len >= count);
let new_left_len = left_len - count;
{
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)
};
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_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1);
move_kv(parent_kv, 0, right_kv, count - 1, 1);
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()) {
(ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
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);
move_edges(left, new_left_len + 1, right, 0, count);
}
(ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
_ => unreachable!(),
}
}
}
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();
assert!(left_len + count <= CAPACITY);
assert!(right_len >= count);
let new_right_len = right_len - count;
{
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_kv(parent_kv, 0, left_kv, left_len, 1);
move_kv(right_kv, 0, left_kv, left_len + 1, count - 1);
move_kv(right_kv, count - 1, parent_kv, 0, 1);
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()) {
(ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
move_edges(right.reborrow(), 0, left, left_len + 1, count);
let right_edges = right.reborrow_mut().into_edge_area_slice().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);
}
}
unsafe fn move_edges<'a, K: 'a, V: 'a>(
source: NodeRef<marker::Immut<'a>, K, V, marker::Internal>,
source_offset: usize,
mut dest: NodeRef<marker::Mut<'a>, K, V, marker::Internal>,
dest_offset: usize,
count: usize,
) {
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);
dest.correct_childrens_parent_links(dest_offset..dest_offset + count);
}
}
impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
NodeRef { height: self.height, node: self.node, _marker: PhantomData }
}
}
impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
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>
{
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> {
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.reborrow_mut().into_len_mut() = left_new_len as u16;
*right_node.reborrow_mut().into_len_mut() = right_new_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);
}
(ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
_ => unreachable!(),
}
}
}
}
}
pub enum ForceResult<Leaf, Internal> {
Leaf(Leaf),
Internal(Internal),
}
pub struct SplitResult<'a, K, V> {
pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
pub k: K,
pub v: V,
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 [MaybeUninit<T>], idx: usize, val: T) {
unsafe {
let len = slice.len();
debug_assert!(len > idx);
let slice_ptr = slice.as_mut_ptr();
if len > idx + 1 {
ptr::copy(slice_ptr.add(idx), slice_ptr.add(idx + 1), len - idx - 1);
}
(*slice_ptr.add(idx)).write(val);
}
}
unsafe fn slice_remove<T>(slice: &mut [MaybeUninit<T>], idx: usize) -> T {
unsafe {
let len = slice.len();
debug_assert!(idx < len);
let slice_ptr = slice.as_mut_ptr();
let ret = (*slice_ptr.add(idx)).assume_init_read();
ptr::copy(slice_ptr.add(idx + 1), slice_ptr.add(idx), len - idx - 1);
ret
}
}
#[cfg(test)]
mod tests;