// edges: if height > 0 {
// [Box<Node<K, V, height - 1>>; 2 * B]
// } else { () },
-// parent: *const Node<K, V, height + 1>,
+// parent: Option<NonNull<Node<K, V, height + 1>>>,
// parent_idx: u16,
// len: u16,
// }
/// The underlying representation of leaf nodes.
#[repr(C)]
struct LeafNode<K, V> {
- /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`.
- /// This either points to an actual node or is null.
- parent: *const InternalNode<K, V>,
+ /// We want to be covariant in `K` and `V`.
+ parent: Option<NonNull<InternalNode<K, V>>>,
/// This node's index into the parent node's `edges` array.
/// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
// be both slightly faster and easier to track in Valgrind.
keys: MaybeUninit::uninit_array(),
vals: MaybeUninit::uninit_array(),
- parent: ptr::null(),
+ parent: None,
parent_idx: MaybeUninit::uninit(),
len: 0,
}
)
};
self.height -= 1;
- self.node_as_mut().as_leaf_mut().parent = ptr::null();
+ self.node_as_mut().as_leaf_mut().parent = None;
unsafe {
Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>());
pub fn len(&self) -> usize {
// Crucially, we only access the `len` field here. If BorrowType is marker::ValMut,
// there might be outstanding mutable references to values that we must not invalidate.
- unsafe { (*self.as_leaf_ptr()).len as usize }
+ unsafe { usize::from((*self.as_leaf_ptr()).len) }
}
/// Returns the height of this node in the whole tree. Zero height denotes the
) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
// We need to use raw pointers to nodes because, if BorrowType is marker::ValMut,
// there might be outstanding mutable references to values that we must not invalidate.
- let parent_as_leaf = unsafe { (*self.as_leaf_ptr()).parent as *const LeafNode<K, V> };
- if let Some(non_zero) = NonNull::new(parent_as_leaf as *mut _) {
- Ok(Handle {
- node: NodeRef { height: self.height + 1, node: non_zero, _marker: PhantomData },
- idx: unsafe { usize::from(*(*self.as_leaf_ptr()).parent_idx.as_ptr()) },
+ let leaf_ptr = self.as_leaf_ptr();
+ unsafe { (*leaf_ptr).parent }
+ .as_ref()
+ .map(|parent| Handle {
+ node: NodeRef {
+ height: self.height + 1,
+ node: parent.cast(),
+ _marker: PhantomData,
+ },
+ idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
_marker: PhantomData,
})
- } else {
- Err(self)
- }
+ .ok_or(self)
}
pub fn first_edge(self) -> Handle<Self, marker::Edge> {
unsafe { &mut (*self.node.as_ptr()) }
}
+ /// Borrows a mutable reference to one of the keys stored in the node.
+ ///
+ /// # Safety
+ /// The node has more than `idx` initialized elements.
+ pub unsafe fn key_mut_at(&mut self, idx: usize) -> &mut K {
+ unsafe { self.reborrow_mut().into_key_mut_at(idx) }
+ }
+
+ /// Borrows a mutable reference to one of the values stored in the node.
+ ///
+ /// # Safety
+ /// The node has more than `idx` initialized elements.
+ pub unsafe fn val_mut_at(&mut self, idx: usize) -> &mut V {
+ unsafe { self.reborrow_mut().into_val_mut_at(idx) }
+ }
+
fn keys_mut(&mut self) -> &mut [K] {
// 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
impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
/// Adds a key/value pair to the end of the node.
pub fn push(&mut self, key: K, val: V) {
- assert!(self.len() < CAPACITY);
-
- let idx = self.len();
-
+ let len = &mut self.as_leaf_mut().len;
+ let idx = usize::from(*len);
+ assert!(idx < CAPACITY);
+ *len += 1;
unsafe {
- ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
- ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
+ ptr::write(self.key_mut_at(idx), key);
+ ptr::write(self.val_mut_at(idx), val);
}
- self.as_leaf_mut().len += 1;
}
/// Adds a key/value pair to the beginning of the node.
/// the end of the node.
pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
assert!(edge.height == self.height - 1);
- assert!(self.len() < CAPACITY);
-
- let idx = self.len();
+ let len = &mut self.as_leaf_mut().len;
+ let idx = usize::from(*len);
+ assert!(idx < CAPACITY);
+ *len += 1;
unsafe {
- ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
- ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
+ ptr::write(self.key_mut_at(idx), key);
+ ptr::write(self.val_mut_at(idx), val);
self.as_internal_mut().edges.get_unchecked_mut(idx + 1).write(edge.node);
-
- self.as_leaf_mut().len += 1;
-
Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
}
}
let edge =
ptr::read(internal.as_internal().edges.get_unchecked(idx + 1).as_ptr());
let mut new_root = Root { node: edge, height: internal.height - 1 };
- new_root.node_as_mut().as_leaf_mut().parent = ptr::null();
+ new_root.node_as_mut().as_leaf_mut().parent = None;
Some(new_root)
}
};
);
let mut new_root = Root { node: edge, height: internal.height - 1 };
- new_root.node_as_mut().as_leaf_mut().parent = ptr::null();
+ new_root.node_as_mut().as_leaf_mut().parent = None;
for i in 0..old_len {
Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
/// The returned pointer points to the inserted value.
fn insert_fit(&mut self, key: K, val: V) -> *mut V {
self.leafy_insert_fit(key, val);
- unsafe { self.node.vals_mut().get_unchecked_mut(self.idx) }
+ unsafe { self.node.val_mut_at(self.idx) }
}
}
/// The returned pointer points to the inserted value.
fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
if self.node.len() < CAPACITY {
- let ptr = self.insert_fit(key, val);
+ let val_ptr = self.insert_fit(key, val);
let kv = unsafe { Handle::new_kv(self.node, self.idx) };
- (InsertResult::Fit(kv), ptr)
+ (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 ptr = match insertion {
+ let val_ptr = match insertion {
InsertionPlace::Left(insert_idx) => unsafe {
Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val)
},
.insert_fit(key, val)
},
};
- (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), ptr)
+ (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), val_ptr)
}
}
}
/// when the ordering of edges has been changed, such as in the various `insert` methods.
fn correct_parent_link(mut self) {
let idx = self.idx as u16;
- let ptr = self.node.as_internal_mut() as *mut _;
+ let ptr = NonNull::new(self.node.as_internal_mut());
let mut child = self.descend();
child.as_leaf_mut().parent = ptr;
child.as_leaf_mut().parent_idx.write(idx);
projects / rust.git / blobdiff