// option. This file may not be copied, modified, or distributed
// except according to those terms.
-// This module represents all the internal representation and logic for a B-Tree's node
-// with a safe interface, so that BTreeMap itself does not depend on any of these details.
-
-pub use self::InsertionResult::*;
-pub use self::SearchResult::*;
-pub use self::ForceResult::*;
-pub use self::TraversalItem::*;
+// This is an attempt at an implementation following the ideal
+//
+// ```
+// struct BTreeMap<K, V> {
+// height: usize,
+// root: Option<Box<Node<K, V, height>>>
+// }
+//
+// struct Node<K, V, height: usize> {
+// keys: [K; 2 * B - 1],
+// vals: [V; 2 * B - 1],
+// edges: if height > 0 {
+// [Box<Node<K, V, height - 1>>; 2 * B]
+// } else { () },
+// parent: *const Node<K, V, height + 1>,
+// parent_idx: u16,
+// len: u16,
+// }
+// ```
+//
+// Since Rust doesn't acutally have dependent types and polymorphic recursion,
+// we make do with lots of unsafety.
-use core::cmp::Ordering::{Greater, Less, Equal};
-use core::intrinsics::arith_offset;
-use core::iter::Zip;
-use core::marker::PhantomData;
-use core::ops::{Deref, DerefMut, Index, IndexMut};
-use core::ptr::Unique;
-use core::{slice, mem, ptr, cmp};
use alloc::heap;
-
-use borrow::Borrow;
-
-/// Represents the result of an Insertion: either the item fit, or the node had to split
-pub enum InsertionResult<K, V> {
- /// The inserted element fit
- Fit,
- /// The inserted element did not fit, so the node was split
- Split(K, V, Node<K, V>),
-}
-
-/// Represents the result of a search for a key in a single node
-pub enum SearchResult<NodeRef> {
- /// The element was found at the given index
- Found(Handle<NodeRef, handle::KV, handle::LeafOrInternal>),
- /// The element wasn't found, but if it's anywhere, it must be beyond this edge
- GoDown(Handle<NodeRef, handle::Edge, handle::LeafOrInternal>),
-}
-
-/// A B-Tree Node. We keep keys/edges/values separate to optimize searching for keys.
-#[unsafe_no_drop_flag]
-pub struct Node<K, V> {
- // To avoid the need for multiple allocations, we allocate a single buffer with enough space
- // for `capacity` keys, `capacity` values, and (in internal nodes) `capacity + 1` edges.
- // Despite this, we store three separate pointers to the three "chunks" of the buffer because
- // the performance drops significantly if the locations of the vals and edges need to be
- // recalculated upon access.
- //
- // These will never be null during normal usage of a `Node`. However, to avoid the need for a
- // drop flag, `Node::drop` zeroes `keys`, signaling that the `Node` has already been cleaned
- // up.
- keys: Unique<K>,
- vals: Unique<V>,
-
- // In leaf nodes, this will be None, and no space will be allocated for edges.
- edges: Option<Unique<Node<K, V>>>,
-
- // At any given time, there will be `_len` keys, `_len` values, and (in an internal node)
- // `_len + 1` edges. In a leaf node, there will never be any edges.
- //
- // Note: instead of accessing this field directly, please call the `len()` method, which should
- // be more stable in the face of representation changes.
- _len: usize,
-
- // FIXME(gereeter) It shouldn't be necessary to store the capacity in every node, as it should
- // be constant throughout the tree. Once a solution to this is found, it might be possible to
- // also pass down the offsets into the buffer that vals and edges are stored at, removing the
- // need for those two pointers.
- //
- // Note: instead of accessing this field directly, please call the `capacity()` method, which
- // should be more stable in the face of representation changes.
- _capacity: usize,
-}
-
-pub struct NodeSlice<'a, K: 'a, V: 'a> {
- keys: &'a [K],
- vals: &'a [V],
- pub edges: &'a [Node<K, V>],
- head_is_edge: bool,
- tail_is_edge: bool,
- has_edges: bool,
-}
-
-pub struct MutNodeSlice<'a, K: 'a, V: 'a> {
- keys: &'a [K],
- vals: &'a mut [V],
- pub edges: &'a mut [Node<K, V>],
- head_is_edge: bool,
- tail_is_edge: bool,
- has_edges: bool,
-}
-
-/// Rounds up to a multiple of a power of two. Returns the closest multiple
-/// of `target_alignment` that is higher or equal to `unrounded`.
-///
-/// # Panics
-///
-/// Fails if `target_alignment` is not a power of two.
-#[inline]
-fn round_up_to_next(unrounded: usize, target_alignment: usize) -> usize {
- assert!(target_alignment.is_power_of_two());
- (unrounded + target_alignment - 1) & !(target_alignment - 1)
-}
-
-#[test]
-fn test_rounding() {
- assert_eq!(round_up_to_next(0, 4), 0);
- assert_eq!(round_up_to_next(1, 4), 4);
- assert_eq!(round_up_to_next(2, 4), 4);
- assert_eq!(round_up_to_next(3, 4), 4);
- assert_eq!(round_up_to_next(4, 4), 4);
- assert_eq!(round_up_to_next(5, 4), 8);
-}
-
-// Returns a tuple of (val_offset, edge_offset),
-// from the start of a mallocated array.
-#[inline]
-fn calculate_offsets(keys_size: usize,
- vals_size: usize,
- vals_align: usize,
- edges_align: usize)
- -> (usize, usize) {
- let vals_offset = round_up_to_next(keys_size, vals_align);
- let end_of_vals = vals_offset + vals_size;
-
- let edges_offset = round_up_to_next(end_of_vals, edges_align);
-
- (vals_offset, edges_offset)
-}
-
-// Returns a tuple of (minimum required alignment, array_size),
-// from the start of a mallocated array.
-#[inline]
-fn calculate_allocation(keys_size: usize,
- keys_align: usize,
- vals_size: usize,
- vals_align: usize,
- edges_size: usize,
- edges_align: usize)
- -> (usize, usize) {
- let (_, edges_offset) = calculate_offsets(keys_size, vals_size, vals_align, edges_align);
- let end_of_edges = edges_offset + edges_size;
-
- let min_align = cmp::max(keys_align, cmp::max(vals_align, edges_align));
-
- (min_align, end_of_edges)
-}
-
-#[test]
-fn test_offset_calculation() {
- assert_eq!(calculate_allocation(128, 8, 15, 1, 4, 4), (8, 148));
- assert_eq!(calculate_allocation(3, 1, 2, 1, 1, 1), (1, 6));
- assert_eq!(calculate_allocation(6, 2, 12, 4, 24, 8), (8, 48));
- assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144));
- assert_eq!(calculate_offsets(3, 2, 1, 1), (3, 5));
- assert_eq!(calculate_offsets(6, 12, 4, 8), (8, 24));
+use core::marker::PhantomData;
+use core::mem;
+use core::nonzero::NonZero;
+use core::ptr::{self, Unique};
+use core::slice;
+
+use boxed::Box;
+
+const B: usize = 6;
+pub const CAPACITY: usize = 2 * B - 1;
+
+struct LeafNode<K, V> {
+ keys: [K; CAPACITY],
+ vals: [V; CAPACITY],
+ parent: *const InternalNode<K, V>,
+ parent_idx: u16,
+ len: u16,
}
-fn calculate_allocation_generic<K, V>(capacity: usize, is_leaf: bool) -> (usize, usize) {
- let (keys_size, keys_align) = (capacity * mem::size_of::<K>(), mem::align_of::<K>());
- let (vals_size, vals_align) = (capacity * mem::size_of::<V>(), mem::align_of::<V>());
- let (edges_size, edges_align) = if is_leaf {
- // allocate one edge to ensure that we don't pass size 0 to `heap::allocate`
- if mem::size_of::<K>() == 0 && mem::size_of::<V>() == 0 {
- (1, mem::align_of::<Node<K, V>>())
- } else {
- (0, 1)
+impl<K, V> LeafNode<K, V> {
+ unsafe fn new() -> Self {
+ LeafNode {
+ keys: mem::uninitialized(),
+ vals: mem::uninitialized(),
+ parent: ptr::null(),
+ parent_idx: mem::uninitialized(),
+ len: 0
}
- } else {
- ((capacity + 1) * mem::size_of::<Node<K, V>>(),
- mem::align_of::<Node<K, V>>())
- };
-
- calculate_allocation(keys_size,
- keys_align,
- vals_size,
- vals_align,
- edges_size,
- edges_align)
-}
-
-fn calculate_offsets_generic<K, V>(capacity: usize, is_leaf: bool) -> (usize, usize) {
- let keys_size = capacity * mem::size_of::<K>();
- let vals_size = capacity * mem::size_of::<V>();
- let vals_align = mem::align_of::<V>();
- let edges_align = if is_leaf {
- 1
- } else {
- mem::align_of::<Node<K, V>>()
- };
-
- calculate_offsets(keys_size, vals_size, vals_align, edges_align)
+ }
}
-/// An iterator over a slice that owns the elements of the slice but not the allocation.
-struct RawItems<T> {
- head: *const T,
- tail: *const T,
+// We use repr(C) so that a pointer to an internal node can be
+// directly used as a pointer to a leaf node
+#[repr(C)]
+struct InternalNode<K, V> {
+ data: LeafNode<K, V>,
+ edges: [BoxedNode<K, V>; 2 * B],
}
-impl<T> RawItems<T> {
- unsafe fn from_slice(slice: &[T]) -> RawItems<T> {
- RawItems::from_parts(slice.as_ptr(), slice.len())
- }
-
- unsafe fn from_parts(ptr: *const T, len: usize) -> RawItems<T> {
- if mem::size_of::<T>() == 0 {
- RawItems {
- head: ptr,
- tail: arith_offset(ptr as *const i8, len as isize) as *const T,
- }
- } else {
- RawItems {
- head: ptr,
- tail: ptr.offset(len as isize),
- }
- }
- }
-
- unsafe fn push(&mut self, val: T) {
- ptr::write(self.tail as *mut T, val);
-
- if mem::size_of::<T>() == 0 {
- self.tail = arith_offset(self.tail as *const i8, 1) as *const T;
- } else {
- self.tail = self.tail.offset(1);
+impl<K, V> InternalNode<K, V> {
+ unsafe fn new() -> Self {
+ InternalNode {
+ data: LeafNode::new(),
+ edges: mem::uninitialized()
}
}
}
-impl<T> Iterator for RawItems<T> {
- type Item = T;
-
- fn next(&mut self) -> Option<T> {
- if self.head == self.tail {
- None
- } else {
- unsafe {
- let ret = Some(ptr::read(self.head));
-
- if mem::size_of::<T>() == 0 {
- self.head = arith_offset(self.head as *const i8, 1) as *const T;
- } else {
- self.head = self.head.offset(1);
- }
+struct BoxedNode<K, V> {
+ ptr: Unique<LeafNode<K, V>> // we don't know if this points to a leaf node or an internal node
+}
- ret
- }
+impl<K, V> BoxedNode<K, V> {
+ fn from_leaf(node: Box<LeafNode<K, V>>) -> Self {
+ unsafe {
+ BoxedNode { ptr: Unique::new(Box::into_raw(node)) }
}
}
-}
-
-impl<T> DoubleEndedIterator for RawItems<T> {
- fn next_back(&mut self) -> Option<T> {
- if self.head == self.tail {
- None
- } else {
- unsafe {
- if mem::size_of::<T>() == 0 {
- self.tail = arith_offset(self.tail as *const i8, -1) as *const T;
- } else {
- self.tail = self.tail.offset(-1);
- }
- Some(ptr::read(self.tail))
- }
+ fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
+ unsafe {
+ BoxedNode { ptr: Unique::new(Box::into_raw(node) as *mut LeafNode<K, V>) }
}
}
-}
-impl<T> Drop for RawItems<T> {
- #[unsafe_destructor_blind_to_params]
- fn drop(&mut self) {
- for _ in self {}
+ unsafe fn from_ptr(ptr: NonZero<*const LeafNode<K, V>>) -> Self {
+ BoxedNode { ptr: Unique::new(*ptr as *mut LeafNode<K, V>) }
}
-}
-impl<K, V> Drop for Node<K, V> {
- #[unsafe_destructor_blind_to_params]
- fn drop(&mut self) {
- if self.keys.is_null() ||
- (unsafe { self.keys.get() as *const K as usize == mem::POST_DROP_USIZE }) {
- // Since we have #[unsafe_no_drop_flag], we have to watch
- // out for the sentinel value being stored in self.keys. (Using
- // null is technically a violation of the `Unique`
- // requirements, though.)
- return;
- }
-
- // Do the actual cleanup.
+ fn as_ptr(&self) -> NonZero<*const LeafNode<K, V>> {
unsafe {
- drop(RawItems::from_slice(self.keys()));
- drop(RawItems::from_slice(self.vals()));
- drop(RawItems::from_slice(self.edges()));
-
- self.destroy();
+ NonZero::new(*self.ptr as *const LeafNode<K, V>)
}
-
- self.keys = unsafe { Unique::new(ptr::null_mut()) };
}
}
-impl<K, V> Node<K, V> {
- /// Make a new internal node. The caller must initialize the result to fix the invariant that
- /// there are `len() + 1` edges.
- unsafe fn new_internal(capacity: usize) -> Node<K, V> {
- let (alignment, size) = calculate_allocation_generic::<K, V>(capacity, false);
-
- let buffer = heap::allocate(size, alignment);
- if buffer.is_null() {
- ::alloc::oom();
- }
+/// An owned tree. Note that despite being owned, this does not have a destructor,
+/// and must be cleaned up manually.
+pub struct Root<K, V> {
+ node: BoxedNode<K, V>,
+ height: usize
+}
- let (vals_offset, edges_offset) = calculate_offsets_generic::<K, V>(capacity, false);
+unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> { }
+unsafe impl<K: Send, V: Send> Send for Root<K, V> { }
- Node {
- keys: Unique::new(buffer as *mut K),
- vals: Unique::new(buffer.offset(vals_offset as isize) as *mut V),
- edges: Some(Unique::new(buffer.offset(edges_offset as isize) as *mut Node<K, V>)),
- _len: 0,
- _capacity: capacity,
+impl<K, V> Root<K, V> {
+ pub fn new_leaf() -> Self {
+ Root {
+ node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })),
+ height: 0
}
}
- /// Make a new leaf node
- fn new_leaf(capacity: usize) -> Node<K, V> {
- let (alignment, size) = calculate_allocation_generic::<K, V>(capacity, true);
-
- let buffer = unsafe { heap::allocate(size, alignment) };
- if buffer.is_null() {
- ::alloc::oom();
- }
-
- let (vals_offset, _) = calculate_offsets_generic::<K, V>(capacity, true);
-
- Node {
- keys: unsafe { Unique::new(buffer as *mut K) },
- vals: unsafe { Unique::new(buffer.offset(vals_offset as isize) as *mut V) },
- edges: None,
- _len: 0,
- _capacity: capacity,
+ pub fn as_ref(&self)
+ -> NodeRef<marker::Immut, K, V, marker::LeafOrInternal> {
+ NodeRef {
+ height: self.height,
+ node: self.node.as_ptr(),
+ root: self as *const _ as *mut _,
+ _marker: PhantomData,
}
}
- unsafe fn destroy(&mut self) {
- let (alignment, size) = calculate_allocation_generic::<K, V>(self.capacity(),
- self.is_leaf());
- heap::deallocate(*self.keys as *mut u8, size, alignment);
- }
-
- #[inline]
- pub fn as_slices<'a>(&'a self) -> (&'a [K], &'a [V]) {
- unsafe {
- (slice::from_raw_parts(*self.keys, self.len()),
- slice::from_raw_parts(*self.vals, self.len()))
+ pub fn as_mut(&mut self)
+ -> NodeRef<marker::Mut, K, V, marker::LeafOrInternal> {
+ NodeRef {
+ height: self.height,
+ node: self.node.as_ptr(),
+ root: self as *mut _,
+ _marker: PhantomData,
}
}
- #[inline]
- pub fn as_slices_mut<'a>(&'a mut self) -> (&'a mut [K], &'a mut [V]) {
- unsafe {
- (slice::from_raw_parts_mut(*self.keys, self.len()),
- slice::from_raw_parts_mut(*self.vals, self.len()))
+ pub fn into_ref(self)
+ -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
+ NodeRef {
+ height: self.height,
+ node: self.node.as_ptr(),
+ root: ptr::null_mut(), // FIXME: Is there anything better to do here?
+ _marker: PhantomData,
}
}
- #[inline]
- pub fn as_slices_internal<'b>(&'b self) -> NodeSlice<'b, K, V> {
- let is_leaf = self.is_leaf();
- let (keys, vals) = self.as_slices();
- let edges: &[_] = if self.is_leaf() {
- &[]
- } else {
- unsafe {
- let data = match self.edges {
- None => heap::EMPTY as *const Node<K, V>,
- Some(ref p) => **p as *const Node<K, V>,
- };
- slice::from_raw_parts(data, self.len() + 1)
- }
- };
- NodeSlice {
- keys: keys,
- vals: vals,
- edges: edges,
- head_is_edge: true,
- tail_is_edge: true,
- has_edges: !is_leaf,
- }
- }
+ /// Add a new internal node with a single edge, pointing to the previous root, and make that
+ /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
+ pub fn push_level(&mut self)
+ -> NodeRef<marker::Mut, K, V, marker::Internal> {
+ let mut new_node = Box::new(unsafe { InternalNode::new() });
+ new_node.edges[0] = unsafe { BoxedNode::from_ptr(self.node.as_ptr()) };
- #[inline]
- pub fn as_slices_internal_mut<'b>(&'b mut self) -> MutNodeSlice<'b, K, V> {
- let len = self.len();
- let is_leaf = self.is_leaf();
- let keys = unsafe { slice::from_raw_parts_mut(*self.keys, len) };
- let vals = unsafe { slice::from_raw_parts_mut(*self.vals, len) };
- let edges: &mut [_] = if is_leaf {
- &mut []
- } else {
- unsafe {
- let data = match self.edges {
- None => heap::EMPTY as *mut Node<K, V>,
- Some(ref mut p) => **p as *mut Node<K, V>,
- };
- slice::from_raw_parts_mut(data, len + 1)
- }
- };
- MutNodeSlice {
- keys: keys,
- vals: vals,
- edges: edges,
- head_is_edge: true,
- tail_is_edge: true,
- has_edges: !is_leaf,
- }
- }
+ self.node = BoxedNode::from_internal(new_node);
+ self.height += 1;
- #[inline]
- pub fn keys<'a>(&'a self) -> &'a [K] {
- self.as_slices().0
- }
+ let mut ret = NodeRef {
+ height: self.height,
+ node: self.node.as_ptr(),
+ root: self as *mut _,
+ _marker: PhantomData
+ };
- #[inline]
- pub fn keys_mut<'a>(&'a mut self) -> &'a mut [K] {
- self.as_slices_mut().0
- }
+ unsafe {
+ ret.reborrow_mut().first_edge().correct_parent_link();
+ }
- #[inline]
- pub fn vals<'a>(&'a self) -> &'a [V] {
- self.as_slices().1
+ ret
}
- #[inline]
- pub fn vals_mut<'a>(&'a mut self) -> &'a mut [V] {
- self.as_slices_mut().1
- }
+ ///Â Remove the root node, using its first child as the new root. This cannot be called when
+ /// the tree consists only of a leaf node. As it is intended only to be called when the root
+ /// has only one edge, no cleanup is done on any of the other children are elements of the root.
+ /// This decreases the height by 1 and is the opposite of `push_level`.
+ pub fn pop_level(&mut self) {
+ debug_assert!(self.height > 0);
- #[inline]
- pub fn edges<'a>(&'a self) -> &'a [Node<K, V>] {
- self.as_slices_internal().edges
- }
+ let top = *self.node.ptr as *mut u8;
- #[inline]
- pub fn edges_mut<'a>(&'a mut self) -> &'a mut [Node<K, V>] {
- self.as_slices_internal_mut().edges
- }
-}
-
-// FIXME(gereeter) Write an efficient clone_from
-impl<K: Clone, V: Clone> Clone for Node<K, V> {
- fn clone(&self) -> Node<K, V> {
- let mut ret = if self.is_leaf() {
- Node::new_leaf(self.capacity())
- } else {
- unsafe { Node::new_internal(self.capacity()) }
+ self.node = unsafe {
+ BoxedNode::from_ptr(self.as_mut()
+ .cast_unchecked::<marker::Internal>()
+ .first_edge()
+ .descend()
+ .node)
};
+ self.height -= 1;
+ self.as_mut().as_leaf_mut().parent = ptr::null();
unsafe {
- // For failure safety
- let mut keys = RawItems::from_parts(ret.keys().as_ptr(), 0);
- let mut vals = RawItems::from_parts(ret.vals().as_ptr(), 0);
- let mut edges = RawItems::from_parts(ret.edges().as_ptr(), 0);
-
- for key in self.keys() {
- keys.push(key.clone())
- }
- for val in self.vals() {
- vals.push(val.clone())
- }
- for edge in self.edges() {
- edges.push(edge.clone())
- }
-
- mem::forget(keys);
- mem::forget(vals);
- mem::forget(edges);
-
- ret._len = self.len();
+ heap::deallocate(
+ top,
+ mem::size_of::<InternalNode<K, V>>(),
+ mem::align_of::<InternalNode<K, V>>()
+ );
}
-
- ret
}
}
-/// A reference to something in the middle of a `Node`. There are two `Type`s of `Handle`s,
-/// namely `KV` handles, which point to key/value pairs, and `Edge` handles, which point to edges
-/// before or after key/value pairs. Methods are provided for removing pairs, inserting into edges,
-/// accessing the stored values, and moving around the `Node`.
-///
-/// This handle is generic, and can take any sort of reference to a `Node`. The reason for this is
-/// two-fold. First of all, it reduces the amount of repetitive code, implementing functions that
-/// don't need mutability on both mutable and immutable references. Secondly and more importantly,
-/// this allows users of the `Handle` API to associate metadata with the reference. This is used in
-/// `BTreeMap` to give `Node`s temporary "IDs" that persist to when the `Node` is used in a
-/// `Handle`.
+// N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType`
+// is `Mut`. This is technically wrong, but cannot result in any unsafety due to
+// internal use of `NodeRef` because we stay completely generic over `K` and `V`.
+// However, whenever a public type wraps `NodeRef`, make sure that it has the
+// correct variance.
+/// A reference to a node.
///
-/// # A note on safety
-///
-/// Unfortunately, the extra power afforded by being generic also means that safety can technically
-/// be broken. For sensible implementations of `Deref` and `DerefMut`, these handles are perfectly
-/// safe. As long as repeatedly calling `.deref()` results in the same Node being returned each
-/// time, everything should work fine. However, if the `Deref` implementation swaps in multiple
-/// different nodes, then the indices that are assumed to be in bounds suddenly stop being so. For
-/// example:
-///
-/// ```rust,ignore
-/// struct Nasty<'a> {
-/// first: &'a Node<usize, usize>,
-/// second: &'a Node<usize, usize>,
-/// flag: &'a Cell<bool>,
-/// }
-///
-/// impl<'a> Deref for Nasty<'a> {
-/// type Target = Node<usize, usize>;
-///
-/// fn deref(&self) -> &Node<usize, usize> {
-/// if self.flag.get() {
-/// &*self.second
-/// } else {
-/// &*self.first
-/// }
-/// }
-/// }
-///
-/// fn main() {
-/// let flag = Cell::new(false);
-/// let mut small_node = Node::make_leaf_root(3);
-/// let mut large_node = Node::make_leaf_root(100);
-///
-/// for i in 0..100 {
-/// // Insert to the end
-/// large_node.edge_handle(i).insert_as_leaf(i, i);
-/// }
-///
-/// let nasty = Nasty {
-/// first: &large_node,
-/// second: &small_node,
-/// flag: &flag
-/// }
-///
-/// // The handle points at index 75.
-/// let handle = Node::search(nasty, 75);
-///
-/// // Now the handle still points at index 75, but on the small node, which has no index 75.
-/// flag.set(true);
-///
-/// println!("Uninitialized memory: {:?}", handle.into_kv());
-/// }
-/// ```
-#[derive(Copy, Clone)]
-pub struct Handle<NodeRef, Type, NodeType> {
- node: NodeRef,
- index: usize,
- marker: PhantomData<(Type, NodeType)>,
+/// This type has a number of paramaters that controls how it acts:
+/// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`.
+/// When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`,
+/// when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
+/// and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`.
+/// - `K` and `V`: These control what types of things are stored in the nodes.
+/// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
+/// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
+/// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
+/// `NodeRef` could be pointing to either type of node.
+pub struct NodeRef<BorrowType, K, V, Type> {
+ height: usize,
+ node: NonZero<*const LeafNode<K, V>>,
+ root: *const Root<K, V>,
+ _marker: PhantomData<(BorrowType, Type)>
}
-pub mod handle {
- // Handle types.
- pub enum KV {}
- pub enum Edge {}
-
- // Handle node types.
- pub enum LeafOrInternal {}
- pub enum Leaf {}
- pub enum Internal {}
+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
+ }
}
-impl<K: Ord, V> Node<K, V> {
- /// Searches for the given key in the node. If it finds an exact match,
- /// `Found` will be yielded with the matching index. If it doesn't find an exact match,
- /// `GoDown` will be yielded with the index of the subtree the key must lie in.
- pub fn search<Q: ?Sized, NodeRef: Deref<Target = Node<K, V>>>(node: NodeRef,
- key: &Q)
- -> SearchResult<NodeRef>
- where K: Borrow<Q>,
- Q: Ord
- {
- // FIXME(Gankro): Tune when to search linear or binary based on B (and maybe K/V).
- // For the B configured as of this writing (B = 6), binary search was *significantly*
- // worse for usizes.
- match node.as_slices_internal().search_linear(key) {
- (index, true) => {
- Found(Handle {
- node: node,
- index: index,
- marker: PhantomData,
- })
- }
- (index, false) => {
- GoDown(Handle {
- node: node,
- index: index,
- marker: PhantomData,
- })
- }
+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<K: Send, V: Send, Type> Send
+ for NodeRef<marker::Owned, K, V, Type> { }
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
+ fn as_internal(&self) -> &InternalNode<K, V> {
+ unsafe {
+ &*(*self.node as *const InternalNode<K, V>)
}
}
}
-// Public interface
-impl<K, V> Node<K, V> {
- /// Make a leaf root from scratch
- pub fn make_leaf_root(b: usize) -> Node<K, V> {
- Node::new_leaf(capacity_from_b(b))
- }
-
- /// Make an internal root and swap it with an old root
- pub fn make_internal_root(left_and_out: &mut Node<K, V>,
- b: usize,
- key: K,
- value: V,
- right: Node<K, V>) {
- let node = mem::replace(left_and_out,
- unsafe { Node::new_internal(capacity_from_b(b)) });
- left_and_out._len = 1;
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
+ fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
unsafe {
- ptr::write(left_and_out.keys_mut().get_unchecked_mut(0), key);
- ptr::write(left_and_out.vals_mut().get_unchecked_mut(0), value);
- ptr::write(left_and_out.edges_mut().get_unchecked_mut(0), node);
- ptr::write(left_and_out.edges_mut().get_unchecked_mut(1), right);
+ &mut *(*self.node as *mut InternalNode<K, V>)
}
}
+}
- /// How many key-value pairs the node contains
- pub fn len(&self) -> usize {
- self._len
- }
- /// Does the node not contain any key-value pairs
- pub fn is_empty(&self) -> bool {
- self.len() == 0
+impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
+ pub fn len(&self) -> usize {
+ self.as_leaf().len as usize
}
- /// How many key-value pairs the node can fit
- pub fn capacity(&self) -> usize {
- self._capacity
+ pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+ NodeRef {
+ height: self.height,
+ node: self.node,
+ root: self.root,
+ _marker: PhantomData
+ }
}
- /// If the node has any children
- pub fn is_leaf(&self) -> bool {
- self.edges.is_none()
+ fn reborrow<'a>(&'a self) -> NodeRef<marker::Immut<'a>, K, V, Type> {
+ NodeRef {
+ height: self.height,
+ node: self.node,
+ root: self.root,
+ _marker: PhantomData
+ }
}
- /// if the node has too few elements
- pub fn is_underfull(&self) -> bool {
- self.len() < min_load_from_capacity(self.capacity())
+ fn as_leaf(&self) -> &LeafNode<K, V> {
+ unsafe {
+ &**self.node
+ }
}
- /// if the node cannot fit any more elements
- pub fn is_full(&self) -> bool {
- self.len() == self.capacity()
+ pub fn keys(&self) -> &[K] {
+ self.reborrow().into_slices().0
}
-}
-impl<K, V, NodeRef: Deref<Target = Node<K, V>>, Type, NodeType> Handle<NodeRef, Type, NodeType> {
- /// Returns a reference to the node that contains the pointed-to edge or key/value pair. This
- /// is very different from `edge` and `edge_mut` because those return children of the node
- /// returned by `node`.
- pub fn node(&self) -> &Node<K, V> {
- &*self.node
+ pub fn vals(&self) -> &[V] {
+ self.reborrow().into_slices().1
}
-}
-impl<K, V, NodeRef, Type, NodeType> Handle<NodeRef, Type, NodeType>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Converts a handle into one that stores the same information using a raw pointer. This can
- /// be useful in conjunction with `from_raw` when the type system is insufficient for
- /// determining the lifetimes of the nodes.
- pub fn as_raw(&mut self) -> Handle<*mut Node<K, V>, Type, NodeType> {
- Handle {
- node: &mut *self.node as *mut _,
- index: self.index,
- marker: PhantomData,
+ pub fn ascend(self) -> Result<
+ Handle<
+ NodeRef<
+ BorrowType,
+ K, V,
+ marker::Internal
+ >,
+ marker::Edge
+ >,
+ Self
+ > {
+ if self.as_leaf().parent.is_null() {
+ Err(self)
+ } else {
+ Ok(Handle {
+ node: NodeRef {
+ height: self.height + 1,
+ node: unsafe {
+ NonZero::new(self.as_leaf().parent as *mut LeafNode<K, V>)
+ },
+ root: self.root,
+ _marker: PhantomData
+ },
+ idx: self.as_leaf().parent_idx as usize,
+ _marker: PhantomData
+ })
}
}
-}
-impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> {
- /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle
- /// stored with a reference. This is an unsafe inverse of `as_raw`, and together they allow
- /// unsafely extending the lifetime of the reference to the `Node`.
- pub unsafe fn from_raw<'a>(&'a self) -> Handle<&'a Node<K, V>, Type, NodeType> {
- Handle {
- node: &*self.node,
- index: self.index,
- marker: PhantomData,
- }
+ pub fn first_edge(self) -> Handle<Self, marker::Edge> {
+ Handle::new_edge(self, 0)
}
- /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle
- /// stored with a mutable reference. This is an unsafe inverse of `as_raw`, and together they
- /// allow unsafely extending the lifetime of the reference to the `Node`.
- pub unsafe fn from_raw_mut<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, Type, NodeType> {
- Handle {
- node: &mut *self.node,
- index: self.index,
- marker: PhantomData,
- }
+ pub fn last_edge(self) -> Handle<Self, marker::Edge> {
+ let len = self.len();
+ Handle::new_edge(self, len)
}
}
-impl<'a, K: 'a, V: 'a> Handle<&'a Node<K, V>, handle::Edge, handle::Internal> {
- /// Turns the handle into a reference to the edge it points at. This is necessary because the
- /// returned pointer has a larger lifetime than what would be returned by `edge` or `edge_mut`,
- /// making it more suitable for moving down a chain of nodes.
- pub fn into_edge(self) -> &'a Node<K, V> {
- unsafe { self.node.edges().get_unchecked(self.index) }
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
+ pub unsafe fn deallocate_and_ascend(self) -> Option<
+ Handle<
+ NodeRef<
+ marker::Owned,
+ K, V,
+ marker::Internal
+ >,
+ marker::Edge
+ >
+ > {
+ let ptr = self.as_leaf() as *const LeafNode<K, V> as *const u8 as *mut u8;
+ let ret = self.ascend().ok();
+ heap::deallocate(ptr, mem::size_of::<LeafNode<K, V>>(), mem::align_of::<LeafNode<K, V>>());
+ ret
}
}
-impl<'a, K: 'a, V: 'a> Handle<&'a mut Node<K, V>, handle::Edge, handle::Internal> {
- /// Turns the handle into a mutable reference to the edge it points at. This is necessary
- /// because the returned pointer has a larger lifetime than what would be returned by
- /// `edge_mut`, making it more suitable for moving down a chain of nodes.
- pub fn into_edge_mut(self) -> &'a mut Node<K, V> {
- unsafe { self.node.edges_mut().get_unchecked_mut(self.index) }
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
+ pub unsafe fn deallocate_and_ascend(self) -> Option<
+ Handle<
+ NodeRef<
+ marker::Owned,
+ K, V,
+ marker::Internal
+ >,
+ marker::Edge
+ >
+ > {
+ let ptr = self.as_internal() as *const InternalNode<K, V> as *const u8 as *mut u8;
+ let ret = self.ascend().ok();
+ heap::deallocate(
+ ptr,
+ mem::size_of::<InternalNode<K, V>>(),
+ mem::align_of::<InternalNode<K, V>>()
+ );
+ ret
}
}
-impl<K, V, NodeRef: Deref<Target = Node<K, V>>> Handle<NodeRef, handle::Edge, handle::Internal> {
- // This doesn't exist because there are no uses for it,
- // but is fine to add, analogous to edge_mut.
- //
- // /// Returns a reference to the edge pointed-to by this handle. This should not be
- // /// confused with `node`, which references the parent node of what is returned here.
- // pub fn edge(&self) -> &Node<K, V>
-}
-
-pub enum ForceResult<NodeRef, Type> {
- Leaf(Handle<NodeRef, Type, handle::Leaf>),
- Internal(Handle<NodeRef, Type, handle::Internal>),
-}
+impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+ unsafe fn cast_unchecked<NewType>(&mut self)
+ -> NodeRef<marker::Mut, K, V, NewType> {
-impl<K, V, NodeRef: Deref<Target = Node<K, V>>, Type>
- Handle<NodeRef, Type, handle::LeafOrInternal>
-{
- /// Figure out whether this handle is pointing to something in a leaf node or to something in
- /// an internal node, clarifying the type according to the result.
- pub fn force(self) -> ForceResult<NodeRef, Type> {
- if self.node.is_leaf() {
- Leaf(Handle {
- node: self.node,
- index: self.index,
- marker: PhantomData,
- })
- } else {
- Internal(Handle {
- node: self.node,
- index: self.index,
- marker: PhantomData,
- })
+ NodeRef {
+ height: self.height,
+ node: self.node,
+ root: self.root,
+ _marker: PhantomData
}
}
-}
-impl<K, V, NodeRef> Handle<NodeRef, handle::Edge, handle::Leaf>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Tries to insert this key-value pair at the given index in this leaf node
- /// If the node is full, we have to split it.
- ///
- /// Returns a *mut V to the inserted value, because the caller may want this when
- /// they're done mutating the tree, but we don't want to borrow anything for now.
- pub fn insert_as_leaf(mut self, key: K, value: V) -> (InsertionResult<K, V>, *mut V) {
- if !self.node.is_full() {
- // The element can fit, just insert it
- (Fit, unsafe { self.node.insert_kv(self.index, key, value) as *mut _ })
- } else {
- // The element can't fit, this node is full. Split it into two nodes.
- let (new_key, new_val, mut new_right) = self.node.split();
- let left_len = self.node.len();
-
- let ptr = unsafe {
- if self.index <= left_len {
- self.node.insert_kv(self.index, key, value)
- } else {
- // We need to subtract 1 because in splitting we took out new_key and new_val.
- // Just being in the right node means we are past left_len k/v pairs in the
- // left node and 1 k/v pair in the parent node.
- new_right.insert_kv(self.index - left_len - 1, key, value)
- }
- } as *mut _;
-
- (Split(new_key, new_val, new_right), ptr)
- }
- }
-}
-
-impl<K, V, NodeRef> Handle<NodeRef, handle::Edge, handle::Internal>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Returns a mutable reference to the edge pointed-to by this handle. This should not be
- /// confused with `node`, which references the parent node of what is returned here.
- pub fn edge_mut(&mut self) -> &mut Node<K, V> {
- unsafe { self.node.edges_mut().get_unchecked_mut(self.index) }
- }
-
- /// Tries to insert this key-value pair at the given index in this internal node
- /// If the node is full, we have to split it.
- pub fn insert_as_internal(mut self,
- key: K,
- value: V,
- right: Node<K, V>)
- -> InsertionResult<K, V> {
- if !self.node.is_full() {
- // The element can fit, just insert it
- unsafe {
- self.node.insert_kv(self.index, key, value);
- self.node.insert_edge(self.index + 1, right); // +1 to insert to the right
- }
- Fit
- } else {
- // The element can't fit, this node is full. Split it into two nodes.
- let (new_key, new_val, mut new_right) = self.node.split();
- let left_len = self.node.len();
- if self.index <= left_len {
- unsafe {
- self.node.insert_kv(self.index, key, value);
- self.node.insert_edge(self.index + 1, right); // +1 to insert to the right
- }
- } else {
- unsafe {
- // The -1 here is for the same reason as in insert_as_internal - because we
- // split, there are actually left_len + 1 k/v pairs before the right node, with
- // the extra 1 being put in the parent.
- new_right.insert_kv(self.index - left_len - 1, key, value);
- new_right.insert_edge(self.index - left_len, right);
- }
- }
-
- Split(new_key, new_val, new_right)
+ unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut, K, V, Type> {
+ NodeRef {
+ height: self.height,
+ node: self.node,
+ root: self.root,
+ _marker: PhantomData
}
}
- /// Handle an underflow in this node's child. We favor handling "to the left" because we know
- /// we're empty, but our neighbour can be full. Handling to the left means when we choose to
- /// steal, we pop off the end of our neighbour (always fast) and "unshift" ourselves
- /// (always slow, but at least faster since we know we're half-empty).
- /// Handling "to the right" reverses these roles. Of course, we merge whenever possible
- /// because we want dense nodes, and merging is about equal work regardless of direction.
- pub fn handle_underflow(mut self) {
+ fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
unsafe {
- if self.index > 0 {
- self.handle_underflow_to_left();
- } else {
- self.handle_underflow_to_right();
- }
+ &mut *(*self.node as *mut LeafNode<K, V>)
}
}
- /// Right is underflowed. Tries to steal from left,
- /// but merges left and right if left is low too.
- unsafe fn handle_underflow_to_left(&mut self) {
- let left_len = self.node.edges()[self.index - 1].len();
- if left_len > min_load_from_capacity(self.node.capacity()) {
- self.left_kv().steal_rightward();
- } else {
- self.left_kv().merge_children();
- }
+ pub fn keys_mut(&mut self) -> &mut [K] {
+ unsafe { self.reborrow_mut().into_slices_mut().0 }
}
- /// Left is underflowed. Tries to steal from the right,
- /// but merges left and right if right is low too.
- unsafe fn handle_underflow_to_right(&mut self) {
- let right_len = self.node.edges()[self.index + 1].len();
- if right_len > min_load_from_capacity(self.node.capacity()) {
- self.right_kv().steal_leftward();
- } else {
- self.right_kv().merge_children();
- }
+ pub fn vals_mut(&mut self) -> &mut [V] {
+ unsafe { self.reborrow_mut().into_slices_mut().1 }
}
}
-impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Gets the handle pointing to the key/value pair just to the left of the pointed-to edge.
- /// This is unsafe because the handle might point to the first edge in the node, which has no
- /// pair to its left.
- unsafe fn left_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
- Handle {
- node: &mut *self.node,
- index: self.index - 1,
- marker: PhantomData,
+impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
+ pub fn into_slices(self) -> (&'a [K], &'a [V]) {
+ unsafe {
+ (
+ slice::from_raw_parts(
+ self.as_leaf().keys.as_ptr(),
+ self.len()
+ ),
+ slice::from_raw_parts(
+ self.as_leaf().vals.as_ptr(),
+ self.len()
+ )
+ )
}
}
+}
- /// Gets the handle pointing to the key/value pair just to the right of the pointed-to edge.
- /// This is unsafe because the handle might point to the last edge in the node, which has no
- /// pair to its right.
- unsafe fn right_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
- Handle {
- node: &mut *self.node,
- index: self.index,
- marker: PhantomData,
+impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+ pub fn into_root_mut(self) -> &'a mut Root<K, V> {
+ unsafe {
+ &mut *(self.root as *mut Root<K, V>)
}
}
-}
-impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a Node<K, V>, handle::KV, NodeType> {
- /// Turns the handle into references to the key and value it points at. This is necessary
- /// because the returned pointers have larger lifetimes than what would be returned by `key`
- /// or `val`.
- pub fn into_kv(self) -> (&'a K, &'a V) {
- let (keys, vals) = self.node.as_slices();
+ pub fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
unsafe {
- (keys.get_unchecked(self.index),
- vals.get_unchecked(self.index))
+ (
+ slice::from_raw_parts_mut(
+ &mut self.as_leaf_mut().keys as *mut [K] as *mut K,
+ self.len()
+ ),
+ slice::from_raw_parts_mut(
+ &mut self.as_leaf_mut().vals as *mut [V] as *mut V,
+ self.len()
+ )
+ )
}
}
}
-impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
- /// Turns the handle into mutable references to the key and value it points at. This is
- /// necessary because the returned pointers have larger lifetimes than what would be returned
- /// by `key_mut` or `val_mut`.
- pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
- let (keys, vals) = self.node.as_slices_mut();
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
+ pub fn push(&mut self, key: K, val: V) {
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(self.len() < CAPACITY);
+
+ let idx = self.len();
+
unsafe {
- (keys.get_unchecked_mut(self.index),
- vals.get_unchecked_mut(self.index))
+ ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
+ ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
}
+
+ self.as_leaf_mut().len += 1;
}
- /// Convert this handle into one pointing at the edge immediately to the left of the key/value
- /// pair pointed-to by this handle. This is useful because it returns a reference with larger
- /// lifetime than `left_edge`.
- pub fn into_left_edge(self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
- Handle {
- node: &mut *self.node,
- index: self.index,
- marker: PhantomData,
+ pub fn push_front(&mut self, key: K, val: V) {
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(self.len() < CAPACITY);
+
+ unsafe {
+ slice_insert(self.keys_mut(), 0, key);
+ slice_insert(self.vals_mut(), 0, val);
}
+
+ self.as_leaf_mut().len += 1;
}
}
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
+ pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(edge.height == self.height - 1);
+ debug_assert!(self.len() < CAPACITY);
-impl<'a, K: 'a, V: 'a, NodeRef: Deref<Target = Node<K, V>> + 'a, NodeType> Handle<NodeRef,
- handle::KV,
- NodeType> {
- // These are fine to include, but are currently unneeded.
- //
- // /// Returns a reference to the key pointed-to by this handle. This doesn't return a
- // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
- // /// handle.
- // pub fn key(&'a self) -> &'a K {
- // unsafe { self.node.keys().get_unchecked(self.index) }
- // }
- //
- // /// Returns a reference to the value pointed-to by this handle. This doesn't return a
- // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
- // /// handle.
- // pub fn val(&'a self) -> &'a V {
- // unsafe { self.node.vals().get_unchecked(self.index) }
- // }
-}
+ let idx = self.len();
-impl<'a, K: 'a, V: 'a, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType>
- where NodeRef: 'a + Deref<Target = Node<K, V>> + DerefMut
-{
- /// Returns a mutable reference to the key pointed-to by this handle. This doesn't return a
- /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
- /// handle.
- pub fn key_mut(&'a mut self) -> &'a mut K {
- unsafe { self.node.keys_mut().get_unchecked_mut(self.index) }
- }
+ unsafe {
+ ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
+ ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
+ ptr::write(self.as_internal_mut().edges.get_unchecked_mut(idx + 1), edge.node);
- /// Returns a mutable reference to the value pointed-to by this handle. This doesn't return a
- /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
- /// handle.
- pub fn val_mut(&'a mut self) -> &'a mut V {
- unsafe { self.node.vals_mut().get_unchecked_mut(self.index) }
- }
-}
+ self.as_leaf_mut().len += 1;
-impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Gets the handle pointing to the edge immediately to the left of the key/value pair pointed
- /// to by this handle.
- pub fn left_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
- Handle {
- node: &mut *self.node,
- index: self.index,
- marker: PhantomData,
+ Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
}
}
- /// Gets the handle pointing to the edge immediately to the right of the key/value pair pointed
- /// to by this handle.
- pub fn right_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
- Handle {
- node: &mut *self.node,
- index: self.index + 1,
- marker: PhantomData,
+ pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(edge.height == self.height - 1);
+ debug_assert!(self.len() < CAPACITY);
+
+ unsafe {
+ slice_insert(self.keys_mut(), 0, key);
+ slice_insert(self.vals_mut(), 0, val);
+ slice_insert(
+ slice::from_raw_parts_mut(
+ self.as_internal_mut().edges.as_mut_ptr(),
+ self.len()+1
+ ),
+ 0,
+ edge.node
+ );
+
+ self.as_leaf_mut().len += 1;
+
+ for i in 0..self.len()+1 {
+ Handle::new_edge(self.reborrow_mut(), i).correct_parent_link();
+ }
}
- }
-}
-impl<K, V, NodeRef> Handle<NodeRef, handle::KV, handle::Leaf>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Removes the key/value pair at the handle's location.
- ///
- /// # Panics (in debug build)
- ///
- /// Panics if the node containing the pair is not a leaf node.
- pub fn remove_as_leaf(mut self) -> (K, V) {
- unsafe { self.node.remove_kv(self.index) }
}
}
-impl<K, V, NodeRef> Handle<NodeRef, handle::KV, handle::Internal>
- where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
- /// Steal! Stealing is roughly analogous to a binary tree rotation.
- /// In this case, we're "rotating" right.
- unsafe fn steal_rightward(&mut self) {
- // Take the biggest stuff off left
- let (mut key, mut val, edge) = {
- let mut left_handle = self.left_edge();
- let left = left_handle.edge_mut();
- let (key, val) = left.pop_kv();
- let edge = if left.is_leaf() {
- None
- } else {
- Some(left.pop_edge())
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
+ pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(self.len() > 0);
+
+ let idx = self.len() - 1;
+
+ unsafe {
+ let key = ptr::read(self.keys().get_unchecked(idx));
+ let val = ptr::read(self.vals().get_unchecked(idx));
+ let edge = match self.reborrow_mut().force() {
+ ForceResult::Leaf(_) => None,
+ ForceResult::Internal(internal) => {
+ let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1));
+ let mut new_root = Root { node: edge, height: internal.height - 1 };
+ new_root.as_mut().as_leaf_mut().parent = ptr::null();
+ Some(new_root)
+ }
};
+ self.as_leaf_mut().len -= 1;
(key, val, edge)
- };
-
- // Swap the parent's separating key-value pair with left's
- mem::swap(&mut key, self.key_mut());
- mem::swap(&mut val, self.val_mut());
-
- // Put them at the start of right
- let mut right_handle = self.right_edge();
- let right = right_handle.edge_mut();
- right.insert_kv(0, key, val);
- match edge {
- Some(edge) => right.insert_edge(0, edge),
- None => {}
}
}
- /// Steal! Stealing is roughly analogous to a binary tree rotation.
- /// In this case, we're "rotating" left.
- unsafe fn steal_leftward(&mut self) {
- // Take the smallest stuff off right
- let (mut key, mut val, edge) = {
- let mut right_handle = self.right_edge();
- let right = right_handle.edge_mut();
- let (key, val) = right.remove_kv(0);
- let edge = if right.is_leaf() {
- None
- } else {
- Some(right.remove_edge(0))
- };
+ pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(self.len() > 0);
- (key, val, edge)
- };
+ let old_len = self.len();
- // Swap the parent's separating key-value pair with right's
- mem::swap(&mut key, self.key_mut());
- mem::swap(&mut val, self.val_mut());
-
- // Put them at the end of left
- let mut left_handle = self.left_edge();
- let left = left_handle.edge_mut();
- left.push_kv(key, val);
- match edge {
- Some(edge) => left.push_edge(edge),
- None => {}
- }
- }
+ unsafe {
+ let key = slice_remove(self.keys_mut(), 0);
+ let val = slice_remove(self.vals_mut(), 0);
+ let edge = match self.reborrow_mut().force() {
+ ForceResult::Leaf(_) => None,
+ ForceResult::Internal(mut internal) => {
+ let edge = slice_remove(
+ slice::from_raw_parts_mut(
+ internal.as_internal_mut().edges.as_mut_ptr(),
+ old_len+1
+ ),
+ 0
+ );
+
+ let mut new_root = Root { node: edge, height: internal.height - 1 };
+ new_root.as_mut().as_leaf_mut().parent = ptr::null();
+
+ for i in 0..old_len {
+ Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
+ }
+
+ Some(new_root)
+ }
+ };
- /// Merge! Smooshes left and right into one node, along with the key-value
- /// pair that separated them in their parent.
- unsafe fn merge_children(mut self) {
- // Permanently remove right's index, and the key-value pair that separates
- // left and right
- let (key, val) = self.node.remove_kv(self.index);
- let right = self.node.remove_edge(self.index + 1);
+ self.as_leaf_mut().len -= 1;
- // Give left right's stuff.
- self.left_edge()
- .edge_mut()
- .absorb(key, val, right);
+ (key, val, edge)
+ }
}
}
-impl<K, V> Node<K, V> {
- /// Returns the mutable handle pointing to the key/value pair at a given index.
- ///
- /// # Panics (in debug build)
- ///
- /// Panics if the given index is out of bounds.
- pub fn kv_handle(&mut self,
- index: usize)
- -> Handle<&mut Node<K, V>, handle::KV, handle::LeafOrInternal> {
- // Necessary for correctness, but in a private module
- debug_assert!(index < self.len(), "kv_handle index out of bounds");
- Handle {
- node: self,
- index: index,
- marker: PhantomData,
+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,
+ root: self.root,
+ _marker: PhantomData
+ })
+ } else {
+ ForceResult::Internal(NodeRef {
+ height: self.height,
+ node: self.node,
+ root: self.root,
+ _marker: PhantomData
+ })
}
}
+}
- pub fn iter<'a>(&'a self) -> Traversal<'a, K, V> {
- self.as_slices_internal().iter()
- }
+pub struct Handle<Node, Type> {
+ node: Node,
+ idx: usize,
+ _marker: PhantomData<Type>
+}
- pub fn iter_mut<'a>(&'a mut self) -> MutTraversal<'a, K, V> {
- self.as_slices_internal_mut().iter_mut()
+impl<Node: Copy, Type> Copy for Handle<Node, Type> { }
+impl<Node: Copy, Type> Clone for Handle<Node, Type> {
+ fn clone(&self) -> Self {
+ *self
}
+}
- pub fn into_iter(self) -> MoveTraversal<K, V> {
- unsafe {
- let ret = MoveTraversal {
- inner: MoveTraversalImpl {
- keys: RawItems::from_slice(self.keys()),
- vals: RawItems::from_slice(self.vals()),
- edges: RawItems::from_slice(self.edges()),
-
- ptr: Unique::new(*self.keys as *mut u8),
- capacity: self.capacity(),
- is_leaf: self.is_leaf(),
- },
- head_is_edge: true,
- tail_is_edge: true,
- has_edges: !self.is_leaf(),
- };
- mem::forget(self);
- ret
- }
+impl<Node, Type> Handle<Node, Type> {
+ pub fn into_node(self) -> Node {
+ self.node
}
+}
- /// When a node has no keys or values and only a single edge, extract that edge.
- pub fn hoist_lone_child(&mut self) {
+impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
+ pub fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
// Necessary for correctness, but in a private module
- debug_assert!(self.is_empty());
- debug_assert!(!self.is_leaf());
+ debug_assert!(idx < node.len());
- unsafe {
- let ret = ptr::read(self.edges().get_unchecked(0));
- self.destroy();
- ptr::write(self, ret);
+ Handle {
+ node: node,
+ idx: idx,
+ _marker: PhantomData
}
}
-}
-
-// Vector functions (all unchecked)
-impl<K, V> Node<K, V> {
- // This must be followed by push_edge on an internal node.
- #[inline]
- unsafe fn push_kv(&mut self, key: K, val: V) {
- let len = self.len();
-
- ptr::write(self.keys_mut().get_unchecked_mut(len), key);
- ptr::write(self.vals_mut().get_unchecked_mut(len), val);
- self._len += 1;
+ pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+ Handle::new_edge(self.node, self.idx)
}
- // This can only be called immediately after a call to push_kv.
- #[inline]
- unsafe fn push_edge(&mut self, edge: Node<K, V>) {
- let len = self.len();
-
- ptr::write(self.edges_mut().get_unchecked_mut(len), edge);
+ pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+ Handle::new_edge(self.node, self.idx + 1)
}
+}
- // This must be followed by insert_edge on an internal node.
- #[inline]
- unsafe fn insert_kv(&mut self, index: usize, key: K, val: V) -> &mut V {
- ptr::copy(self.keys().as_ptr().offset(index as isize),
- self.keys_mut().as_mut_ptr().offset(index as isize + 1),
- self.len() - index);
- ptr::copy(self.vals().as_ptr().offset(index as isize),
- self.vals_mut().as_mut_ptr().offset(index as isize + 1),
- self.len() - index);
+impl<BorrowType, K, V, NodeType, HandleType> PartialEq
+ for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
- ptr::write(self.keys_mut().get_unchecked_mut(index), key);
- ptr::write(self.vals_mut().get_unchecked_mut(index), val);
+ fn eq(&self, other: &Self) -> bool {
+ self.node.node == other.node.node && self.idx == other.idx
+ }
+}
- self._len += 1;
+impl<BorrowType, K, V, NodeType, HandleType>
+ Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
- self.vals_mut().get_unchecked_mut(index)
- }
+ pub fn reborrow(&self)
+ -> Handle<NodeRef<marker::Immut, K, V, NodeType>, HandleType> {
- // This can only be called immediately after a call to insert_kv.
- #[inline]
- unsafe fn insert_edge(&mut self, index: usize, edge: Node<K, V>) {
- ptr::copy(self.edges().as_ptr().offset(index as isize),
- self.edges_mut().as_mut_ptr().offset(index as isize + 1),
- self.len() - index);
- ptr::write(self.edges_mut().get_unchecked_mut(index), edge);
+ // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
+ Handle {
+ node: self.node.reborrow(),
+ idx: self.idx,
+ _marker: PhantomData
+ }
}
+}
- // This must be followed by pop_edge on an internal node.
- #[inline]
- unsafe fn pop_kv(&mut self) -> (K, V) {
- let key = ptr::read(self.keys().get_unchecked(self.len() - 1));
- let val = ptr::read(self.vals().get_unchecked(self.len() - 1));
+impl<'a, K, V, NodeType, HandleType>
+ Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
- self._len -= 1;
+ pub unsafe fn reborrow_mut(&mut self)
+ -> Handle<NodeRef<marker::Mut, K, V, NodeType>, HandleType> {
- (key, val)
+ // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
+ Handle {
+ node: self.node.reborrow_mut(),
+ idx: self.idx,
+ _marker: PhantomData
+ }
}
+}
- // This can only be called immediately after a call to pop_kv.
- #[inline]
- unsafe fn pop_edge(&mut self) -> Node<K, V> {
- let edge = ptr::read(self.edges().get_unchecked(self.len() + 1));
-
- edge
- }
+impl<BorrowType, K, V, NodeType>
+ Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
- // This must be followed by remove_edge on an internal node.
- #[inline]
- unsafe fn remove_kv(&mut self, index: usize) -> (K, V) {
- let key = ptr::read(self.keys().get_unchecked(index));
- let val = ptr::read(self.vals().get_unchecked(index));
+ pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
+ // Necessary for correctness, but in a private module
+ debug_assert!(idx <= node.len());
- ptr::copy(self.keys().as_ptr().offset(index as isize + 1),
- self.keys_mut().as_mut_ptr().offset(index as isize),
- self.len() - index - 1);
- ptr::copy(self.vals().as_ptr().offset(index as isize + 1),
- self.vals_mut().as_mut_ptr().offset(index as isize),
- self.len() - index - 1);
+ Handle {
+ node: node,
+ idx: idx,
+ _marker: PhantomData
+ }
+ }
- self._len -= 1;
+ pub fn left_kv(self)
+ -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
- (key, val)
+ if self.idx > 0 {
+ Ok(Handle::new_kv(self.node, self.idx - 1))
+ } else {
+ Err(self)
+ }
}
- // This can only be called immediately after a call to remove_kv.
- #[inline]
- unsafe fn remove_edge(&mut self, index: usize) -> Node<K, V> {
- let edge = ptr::read(self.edges().get_unchecked(index));
-
- ptr::copy(self.edges().as_ptr().offset(index as isize + 1),
- self.edges_mut().as_mut_ptr().offset(index as isize),
- // index can be == len+1, so do the +1 first to avoid underflow.
- (self.len() + 1) - index);
+ pub fn right_kv(self)
+ -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
- edge
+ if self.idx < self.node.len() {
+ Ok(Handle::new_kv(self.node, self.idx))
+ } else {
+ Err(self)
+ }
}
}
-// Private implementation details
-impl<K, V> Node<K, V> {
- /// Node is full, so split it into two nodes, and yield the middle-most key-value pair
- /// because we have one too many, and our parent now has one too few
- fn split(&mut self) -> (K, V, Node<K, V>) {
- // Necessary for correctness, but in a private function
- debug_assert!(!self.is_empty());
-
- let mut right = if self.is_leaf() {
- Node::new_leaf(self.capacity())
- } else {
- unsafe { Node::new_internal(self.capacity()) }
- };
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
+ fn insert_fit(&mut self, key: K, val: V) -> *mut V {
+ // Necessary for correctness, but in a private module
+ debug_assert!(self.node.len() < CAPACITY);
unsafe {
- right._len = self.len() / 2;
- let right_offset = self.len() - right.len();
- ptr::copy_nonoverlapping(self.keys().as_ptr().offset(right_offset as isize),
- right.keys_mut().as_mut_ptr(),
- right.len());
- ptr::copy_nonoverlapping(self.vals().as_ptr().offset(right_offset as isize),
- right.vals_mut().as_mut_ptr(),
- right.len());
- if !self.is_leaf() {
- ptr::copy_nonoverlapping(self.edges().as_ptr().offset(right_offset as isize),
- right.edges_mut().as_mut_ptr(),
- right.len() + 1);
- }
-
- let key = ptr::read(self.keys().get_unchecked(right_offset - 1));
- let val = ptr::read(self.vals().get_unchecked(right_offset - 1));
+ slice_insert(self.node.keys_mut(), self.idx, key);
+ slice_insert(self.node.vals_mut(), self.idx, val);
- self._len = right_offset - 1;
+ self.node.as_leaf_mut().len += 1;
- (key, val, right)
+ self.node.vals_mut().get_unchecked_mut(self.idx)
}
}
- /// Take all the values from right, separated by the given key and value
- fn absorb(&mut self, key: K, val: V, mut right: Node<K, V>) {
- // Necessary for correctness, but in a private function
- // Just as a sanity check, make sure we can fit this guy in
- debug_assert!(self.len() + right.len() <= self.capacity());
- debug_assert!(self.is_leaf() == right.is_leaf());
+ pub fn insert(mut self, key: K, val: V)
+ -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
- unsafe {
- let old_len = self.len();
- self._len += right.len() + 1;
-
- ptr::write(self.keys_mut().get_unchecked_mut(old_len), key);
- ptr::write(self.vals_mut().get_unchecked_mut(old_len), val);
-
- ptr::copy_nonoverlapping(right.keys().as_ptr(),
- self.keys_mut().as_mut_ptr().offset(old_len as isize + 1),
- right.len());
- ptr::copy_nonoverlapping(right.vals().as_ptr(),
- self.vals_mut().as_mut_ptr().offset(old_len as isize + 1),
- right.len());
- if !self.is_leaf() {
- ptr::copy_nonoverlapping(right.edges().as_ptr(),
- self.edges_mut()
- .as_mut_ptr()
- .offset(old_len as isize + 1),
- right.len() + 1);
- }
-
- right.destroy();
- mem::forget(right);
+ if self.node.len() < CAPACITY {
+ let ptr = self.insert_fit(key, val);
+ (InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr)
+ } else {
+ let middle = Handle::new_kv(self.node, B);
+ let (mut left, k, v, mut right) = middle.split();
+ let ptr = if self.idx <= B {
+ unsafe {
+ Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val)
+ }
+ } else {
+ unsafe {
+ Handle::new_edge(
+ right.as_mut().cast_unchecked::<marker::Leaf>(),
+ self.idx - (B + 1)
+ ).insert_fit(key, val)
+ }
+ };
+ (InsertResult::Split(left, k, v, right), ptr)
}
}
}
-/// Get the capacity of a node from the order of the parent B-Tree
-fn capacity_from_b(b: usize) -> usize {
- 2 * b - 1
-}
-
-/// Get the minimum load of a node from its capacity
-fn min_load_from_capacity(cap: usize) -> usize {
- // B - 1
- cap / 2
-}
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+ fn correct_parent_link(mut self) {
+ let idx = self.idx as u16;
+ let ptr = self.node.as_internal_mut() as *mut _;
+ let mut child = self.descend();
+ child.as_leaf_mut().parent = ptr;
+ child.as_leaf_mut().parent_idx = idx;
+ }
-/// A trait for pairs of `Iterator`s, one over edges and the other over key/value pairs. This is
-/// necessary, as the `MoveTraversalImpl` needs to have a destructor that deallocates the `Node`,
-/// and a pair of `Iterator`s would require two independent destructors.
-pub trait TraversalImpl {
- type Item;
- type Edge;
+ unsafe fn cast_unchecked<NewType>(&mut self)
+ -> Handle<NodeRef<marker::Mut, K, V, NewType>, marker::Edge> {
- fn next_kv(&mut self) -> Option<Self::Item>;
- fn next_kv_back(&mut self) -> Option<Self::Item>;
+ Handle::new_edge(self.node.cast_unchecked(), self.idx)
+ }
- fn next_edge(&mut self) -> Option<Self::Edge>;
- fn next_edge_back(&mut self) -> Option<Self::Edge>;
-}
+ fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
+ // Necessary for correctness, but in an internal module
+ debug_assert!(self.node.len() < CAPACITY);
+ debug_assert!(edge.height == self.node.height - 1);
-/// A `TraversalImpl` that actually is backed by two iterators. This works in the non-moving case,
-/// as no deallocation needs to be done.
-#[derive(Clone)]
-pub struct ElemsAndEdges<Elems, Edges>(Elems, Edges);
+ unsafe {
+ self.cast_unchecked::<marker::Leaf>().insert_fit(key, val);
+
+ slice_insert(
+ slice::from_raw_parts_mut(
+ self.node.as_internal_mut().edges.as_mut_ptr(),
+ self.node.len()
+ ),
+ self.idx + 1,
+ edge.node
+ );
+
+ for i in (self.idx+1)..(self.node.len()+1) {
+ Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
+ }
+ }
+ }
-impl<K, V, E, Elems: DoubleEndedIterator, Edges: DoubleEndedIterator>
- TraversalImpl for ElemsAndEdges<Elems, Edges>
- where Elems : Iterator<Item=(K, V)>, Edges : Iterator<Item=E>
-{
- type Item = (K, V);
- type Edge = E;
+ pub fn insert(mut self, key: K, val: V, edge: Root<K, V>)
+ -> InsertResult<'a, K, V, marker::Internal> {
- fn next_kv(&mut self) -> Option<(K, V)> { self.0.next() }
- fn next_kv_back(&mut self) -> Option<(K, V)> { self.0.next_back() }
+ // Necessary for correctness, but this is an internal module
+ debug_assert!(edge.height == self.node.height - 1);
- fn next_edge(&mut self) -> Option<E> { self.1.next() }
- fn next_edge_back(&mut self) -> Option<E> { self.1.next_back() }
+ if self.node.len() < CAPACITY {
+ self.insert_fit(key, val, edge);
+ InsertResult::Fit(Handle::new_kv(self.node, self.idx))
+ } else {
+ let middle = Handle::new_kv(self.node, B);
+ let (mut left, k, v, mut right) = middle.split();
+ if self.idx <= B {
+ unsafe {
+ Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge);
+ }
+ } else {
+ unsafe {
+ Handle::new_edge(
+ right.as_mut().cast_unchecked::<marker::Internal>(),
+ self.idx - (B + 1)
+ ).insert_fit(key, val, edge);
+ }
+ }
+ InsertResult::Split(left, k, v, right)
+ }
+ }
}
-/// A `TraversalImpl` taking a `Node` by value.
-pub struct MoveTraversalImpl<K, V> {
- keys: RawItems<K>,
- vals: RawItems<V>,
- edges: RawItems<Node<K, V>>,
+impl<BorrowType, K, V>
+ Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
- // For deallocation when we are done iterating.
- ptr: Unique<u8>,
- capacity: usize,
- is_leaf: bool,
+ pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+ NodeRef {
+ height: self.node.height - 1,
+ node: unsafe { self.node.as_internal().edges.get_unchecked(self.idx).as_ptr() },
+ root: self.node.root,
+ _marker: PhantomData
+ }
+ }
}
-unsafe impl<K: Sync, V: Sync> Sync for MoveTraversalImpl<K, V> {}
-unsafe impl<K: Send, V: Send> Send for MoveTraversalImpl<K, V> {}
-
-impl<K, V> TraversalImpl for MoveTraversalImpl<K, V> {
- type Item = (K, V);
- type Edge = Node<K, V>;
+impl<'a, K: 'a, V: 'a, NodeType>
+ Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
- fn next_kv(&mut self) -> Option<(K, V)> {
- match (self.keys.next(), self.vals.next()) {
- (Some(k), Some(v)) => Some((k, v)),
- _ => None,
+ pub fn into_kv(self) -> (&'a K, &'a V) {
+ let (keys, vals) = self.node.into_slices();
+ unsafe {
+ (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx))
}
}
+}
- fn next_kv_back(&mut self) -> Option<(K, V)> {
- match (self.keys.next_back(), self.vals.next_back()) {
- (Some(k), Some(v)) => Some((k, v)),
- _ => None,
- }
- }
+impl<'a, K: 'a, V: 'a, NodeType>
+ Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
- fn next_edge(&mut self) -> Option<Node<K, V>> {
- // Necessary for correctness, but in a private module
- debug_assert!(!self.is_leaf);
- self.edges.next()
+ pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
+ let (mut keys, mut vals) = self.node.into_slices_mut();
+ unsafe {
+ (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+ }
}
+}
- fn next_edge_back(&mut self) -> Option<Node<K, V>> {
- // Necessary for correctness, but in a private module
- debug_assert!(!self.is_leaf);
- self.edges.next_back()
+impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
+ pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
+ unsafe {
+ let (mut keys, mut vals) = self.node.reborrow_mut().into_slices_mut();
+ (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+ }
}
}
-impl<K, V> Drop for MoveTraversalImpl<K, V> {
- #[unsafe_destructor_blind_to_params]
- fn drop(&mut self) {
- // We need to cleanup the stored values manually, as the RawItems destructor would run
- // after our deallocation.
- for _ in self.keys.by_ref() {}
- for _ in self.vals.by_ref() {}
- for _ in self.edges.by_ref() {}
-
- let (alignment, size) = calculate_allocation_generic::<K, V>(self.capacity, self.is_leaf);
- unsafe { heap::deallocate(*self.ptr, size, alignment) };
+impl<'a, K, V> 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 = ptr::read(self.node.keys().get_unchecked(self.idx));
+ let v = ptr::read(self.node.vals().get_unchecked(self.idx));
+
+ let new_len = self.node.len() - self.idx - 1;
+
+ ptr::copy_nonoverlapping(
+ self.node.keys().as_ptr().offset(self.idx as isize + 1),
+ new_node.keys.as_mut_ptr(),
+ new_len
+ );
+ ptr::copy_nonoverlapping(
+ self.node.vals().as_ptr().offset(self.idx as isize + 1),
+ new_node.vals.as_mut_ptr(),
+ new_len
+ );
+
+ self.node.as_leaf_mut().len = self.idx as u16;
+ new_node.len = new_len as u16;
+
+ (
+ self.node,
+ k, v,
+ Root {
+ node: BoxedNode::from_leaf(new_node),
+ height: 0
+ }
+ )
+ }
}
-}
-/// An abstraction over all the different kinds of traversals a node supports
-#[derive(Clone)]
-pub struct AbsTraversal<Impl> {
- inner: Impl,
- head_is_edge: bool,
- tail_is_edge: bool,
- has_edges: bool,
+ pub fn remove(mut self)
+ -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
+ unsafe {
+ let k = slice_remove(self.node.keys_mut(), self.idx);
+ let v = slice_remove(self.node.vals_mut(), self.idx);
+ self.node.as_leaf_mut().len -= 1;
+ (self.left_edge(), k, v)
+ }
+ }
}
-/// A single atomic step in a traversal.
-pub enum TraversalItem<K, V, E> {
- /// An element is visited. This isn't written as `Elem(K, V)` just because `opt.map(Elem)`
- /// requires the function to take a single argument. (Enum constructors are functions.)
- Elem((K, V)),
- /// An edge is followed.
- Edge(E),
-}
+impl<'a, K, V> 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 k = ptr::read(self.node.keys().get_unchecked(self.idx));
+ let v = ptr::read(self.node.vals().get_unchecked(self.idx));
+
+ let height = self.node.height;
+ let new_len = self.node.len() - self.idx - 1;
+
+ ptr::copy_nonoverlapping(
+ self.node.keys().as_ptr().offset(self.idx as isize + 1),
+ new_node.data.keys.as_mut_ptr(),
+ new_len
+ );
+ ptr::copy_nonoverlapping(
+ self.node.vals().as_ptr().offset(self.idx as isize + 1),
+ new_node.data.vals.as_mut_ptr(),
+ new_len
+ );
+ ptr::copy_nonoverlapping(
+ self.node.as_internal().edges.as_ptr().offset(self.idx as isize + 1),
+ new_node.edges.as_mut_ptr(),
+ new_len + 1
+ );
+
+ self.node.as_leaf_mut().len = self.idx as u16;
+ new_node.data.len = new_len as u16;
+
+ let mut new_root = Root {
+ node: BoxedNode::from_internal(new_node),
+ height: height
+ };
-/// A traversal over a node's entries and edges
-pub type Traversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
- slice::Iter<'a, V>>,
- slice::Iter<'a, Node<K, V>>>>;
+ for i in 0..(new_len+1) {
+ Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link();
+ }
-/// A mutable traversal over a node's entries and edges
-pub type MutTraversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
- slice::IterMut<'a, V>>,
- slice::IterMut<'a, Node<K, V>>>>;
+ (
+ self.node,
+ k, v,
+ new_root
+ )
+ }
+ }
-/// An owning traversal over a node's entries and edges
-pub type MoveTraversal<K, V> = AbsTraversal<MoveTraversalImpl<K, V>>;
+ pub fn can_merge(&self) -> bool {
+ (
+ self.reborrow()
+ .left_edge()
+ .descend()
+ .len()
+ + self.reborrow()
+ .right_edge()
+ .descend()
+ .len()
+ + 1
+ ) <= CAPACITY
+ }
+
+ 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 mut right_node = self2.right_edge().descend();
+ let right_len = right_node.len();
+
+ // necessary for correctness, but in a private module
+ debug_assert!(left_len + right_len + 1 <= CAPACITY);
+ unsafe {
+ ptr::write(left_node.keys_mut().get_unchecked_mut(left_len),
+ slice_remove(self.node.keys_mut(), self.idx));
+ ptr::copy_nonoverlapping(
+ right_node.keys().as_ptr(),
+ left_node.keys_mut().as_mut_ptr().offset(left_len as isize + 1),
+ right_len
+ );
+ ptr::write(left_node.vals_mut().get_unchecked_mut(left_len),
+ slice_remove(self.node.vals_mut(), self.idx));
+ ptr::copy_nonoverlapping(
+ right_node.vals().as_ptr(),
+ left_node.vals_mut().as_mut_ptr().offset(left_len as isize + 1),
+ right_len
+ );
+
+ slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
+ for i in self.idx+1..self.node.len() {
+ Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
+ }
+ self.node.as_leaf_mut().len -= 1;
+
+ left_node.as_leaf_mut().len += right_len as u16 + 1;
+
+ if self.node.height > 1 {
+ ptr::copy_nonoverlapping(
+ right_node.cast_unchecked().as_internal().edges.as_ptr(),
+ left_node.cast_unchecked()
+ .as_internal_mut()
+ .edges
+ .as_mut_ptr()
+ .offset(left_len as isize + 1),
+ right_len + 1
+ );
+
+ for i in left_len+1..left_len+right_len+2 {
+ Handle::new_edge(
+ left_node.cast_unchecked().reborrow_mut(),
+ i
+ ).correct_parent_link();
+ }
-impl<K, V, E, Impl> Iterator for AbsTraversal<Impl>
- where Impl: TraversalImpl<Item = (K, V), Edge = E>
-{
- type Item = TraversalItem<K, V, E>;
+ heap::deallocate(
+ *right_node.node as *mut u8,
+ mem::size_of::<InternalNode<K, V>>(),
+ mem::align_of::<InternalNode<K, V>>()
+ );
+ } else {
+ heap::deallocate(
+ *right_node.node as *mut u8,
+ mem::size_of::<LeafNode<K, V>>(),
+ mem::align_of::<LeafNode<K, V>>()
+ );
+ }
- fn next(&mut self) -> Option<TraversalItem<K, V, E>> {
- self.next_edge_item().map(Edge).or_else(|| self.next_kv_item().map(Elem))
+ Handle::new_edge(self.node, self.idx)
+ }
}
}
-impl<K, V, E, Impl> DoubleEndedIterator for AbsTraversal<Impl>
- where Impl: TraversalImpl<Item = (K, V), Edge = E>
-{
- fn next_back(&mut self) -> Option<TraversalItem<K, V, E>> {
- self.next_edge_item_back().map(Edge).or_else(|| self.next_kv_item_back().map(Elem))
+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: node,
+ idx: self.idx,
+ _marker: PhantomData
+ }),
+ ForceResult::Internal(node) => ForceResult::Internal(Handle {
+ node: node,
+ idx: self.idx,
+ _marker: PhantomData
+ })
+ }
}
}
-impl<K, V, E, Impl> AbsTraversal<Impl> where Impl: TraversalImpl<Item = (K, V), Edge = E> {
- /// Advances the iterator and returns the item if it's an edge. Returns None
- /// and does nothing if the first item is not an edge.
- pub fn next_edge_item(&mut self) -> Option<E> {
- // NB. `&& self.has_edges` might be redundant in this condition.
- let edge = if self.head_is_edge && self.has_edges {
- self.inner.next_edge()
- } else {
- None
- };
- self.head_is_edge = false;
- edge
- }
-
- /// Advances the iterator and returns the item if it's an edge. Returns None
- /// and does nothing if the last item is not an edge.
- pub fn next_edge_item_back(&mut self) -> Option<E> {
- let edge = if self.tail_is_edge && self.has_edges {
- self.inner.next_edge_back()
- } else {
- None
- };
- self.tail_is_edge = false;
- edge
- }
-
- /// Advances the iterator and returns the item if it's a key-value pair. Returns None
- /// and does nothing if the first item is not a key-value pair.
- pub fn next_kv_item(&mut self) -> Option<(K, V)> {
- if !self.head_is_edge {
- self.head_is_edge = true;
- self.inner.next_kv()
- } else {
- None
- }
- }
+pub enum ForceResult<Leaf, Internal> {
+ Leaf(Leaf),
+ Internal(Internal)
+}
- /// Advances the iterator and returns the item if it's a key-value pair. Returns None
- /// and does nothing if the last item is not a key-value pair.
- pub fn next_kv_item_back(&mut self) -> Option<(K, V)> {
- if !self.tail_is_edge {
- self.tail_is_edge = true;
- self.inner.next_kv_back()
- } else {
- None
- }
- }
+pub enum InsertResult<'a, K, V, Type> {
+ Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
+ Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>)
}
-macro_rules! node_slice_impl {
- ($NodeSlice:ident, $Traversal:ident,
- $as_slices_internal:ident, $index:ident, $iter:ident) => {
- impl<'a, K: Ord + 'a, V: 'a> $NodeSlice<'a, K, V> {
- /// Performs linear search in a slice. Returns a tuple of (index, is_exact_match).
- fn search_linear<Q: ?Sized>(&self, key: &Q) -> (usize, bool)
- where K: Borrow<Q>, Q: Ord {
- for (i, k) in self.keys.iter().enumerate() {
- match key.cmp(k.borrow()) {
- Greater => {},
- Equal => return (i, true),
- Less => return (i, false),
- }
- }
- (self.keys.len(), false)
- }
+pub mod marker {
+ use core::marker::PhantomData;
- /// Returns a sub-slice with elements starting with `min_key`.
- pub fn slice_from<Q: ?Sized + Ord>(self, min_key: &Q) -> $NodeSlice<'a, K, V> where
- K: Borrow<Q>,
- {
- // _______________
- // |_1_|_3_|_5_|_7_|
- // | | | | |
- // 0 0 1 1 2 2 3 3 4 index
- // | | | | |
- // \___|___|___|___/ slice_from(&0); pos = 0
- // \___|___|___/ slice_from(&2); pos = 1
- // |___|___|___/ slice_from(&3); pos = 1; result.head_is_edge = false
- // \___|___/ slice_from(&4); pos = 2
- // \___/ slice_from(&6); pos = 3
- // \|/ slice_from(&999); pos = 4
- let (pos, pos_is_kv) = self.search_linear(min_key);
- $NodeSlice {
- has_edges: self.has_edges,
- edges: if !self.has_edges {
- self.edges
- } else {
- self.edges.$index(pos ..)
- },
- keys: &self.keys[pos ..],
- vals: self.vals.$index(pos ..),
- head_is_edge: !pos_is_kv,
- tail_is_edge: self.tail_is_edge,
- }
- }
+ pub enum Leaf { }
+ pub enum Internal { }
+ pub enum LeafOrInternal { }
- /// Returns a sub-slice with elements up to and including `max_key`.
- pub fn slice_to<Q: ?Sized + Ord>(self, max_key: &Q) -> $NodeSlice<'a, K, V> where
- K: Borrow<Q>,
- {
- // _______________
- // |_1_|_3_|_5_|_7_|
- // | | | | |
- // 0 0 1 1 2 2 3 3 4 index
- // | | | | |
- //\|/ | | | | slice_to(&0); pos = 0
- // \___/ | | | slice_to(&2); pos = 1
- // \___|___| | | slice_to(&3); pos = 1; result.tail_is_edge = false
- // \___|___/ | | slice_to(&4); pos = 2
- // \___|___|___/ | slice_to(&6); pos = 3
- // \___|___|___|___/ slice_to(&999); pos = 4
- let (pos, pos_is_kv) = self.search_linear(max_key);
- let pos = pos + if pos_is_kv { 1 } else { 0 };
- $NodeSlice {
- has_edges: self.has_edges,
- edges: if !self.has_edges {
- self.edges
- } else {
- self.edges.$index(.. (pos + 1))
- },
- keys: &self.keys[..pos],
- vals: self.vals.$index(.. pos),
- head_is_edge: self.head_is_edge,
- tail_is_edge: !pos_is_kv,
- }
- }
- }
+ pub enum Owned { }
+ pub struct Immut<'a>(PhantomData<&'a ()>);
+ pub struct Mut<'a>(PhantomData<&'a mut ()>);
- impl<'a, K: 'a, V: 'a> $NodeSlice<'a, K, V> {
- /// Returns an iterator over key/value pairs and edges in a slice.
- #[inline]
- pub fn $iter(self) -> $Traversal<'a, K, V> {
- let mut edges = self.edges.$iter();
- // Skip edges at both ends, if excluded.
- if !self.head_is_edge { edges.next(); }
- if !self.tail_is_edge { edges.next_back(); }
- // The key iterator is always immutable.
- $Traversal {
- inner: ElemsAndEdges(
- self.keys.iter().zip(self.vals.$iter()),
- edges
- ),
- head_is_edge: self.head_is_edge,
- tail_is_edge: self.tail_is_edge,
- has_edges: self.has_edges,
- }
- }
- }
- }
+ pub enum KV { }
+ pub enum Edge { }
}
-node_slice_impl!(NodeSlice, Traversal, as_slices_internal, index, iter);
-node_slice_impl!(MutNodeSlice, MutTraversal, as_slices_internal_mut, index_mut, iter_mut);
+unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
+ ptr::copy(
+ slice.as_ptr().offset(idx as isize),
+ slice.as_mut_ptr().offset(idx as isize + 1),
+ slice.len() - idx
+ );
+ ptr::write(slice.get_unchecked_mut(idx), val);
+}
+
+unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
+ let ret = ptr::read(slice.get_unchecked(idx));
+ ptr::copy(
+ slice.as_ptr().offset(idx as isize + 1),
+ slice.as_mut_ptr().offset(idx as isize),
+ slice.len() - idx - 1
+ );
+ ret
+}
projects / rust.git / blobdiff