]>
Commit | Line | Data |
---|---|---|
9cc50fc6 SL |
1 | // This is an attempt at an implementation following the ideal |
2 | // | |
3 | // ``` | |
4 | // struct BTreeMap<K, V> { | |
5 | // height: usize, | |
6 | // root: Option<Box<Node<K, V, height>>> | |
7 | // } | |
8 | // | |
9 | // struct Node<K, V, height: usize> { | |
10 | // keys: [K; 2 * B - 1], | |
11 | // vals: [V; 2 * B - 1], | |
12 | // edges: if height > 0 { | |
13 | // [Box<Node<K, V, height - 1>>; 2 * B] | |
14 | // } else { () }, | |
1b1a35ee | 15 | // parent: Option<NonNull<Node<K, V, height + 1>>>, |
9cc50fc6 SL |
16 | // parent_idx: u16, |
17 | // len: u16, | |
18 | // } | |
19 | // ``` | |
20 | // | |
7453a54e | 21 | // Since Rust doesn't actually have dependent types and polymorphic recursion, |
9cc50fc6 | 22 | // we make do with lots of unsafety. |
1a4d82fc | 23 | |
a7813a04 XL |
24 | // A major goal of this module is to avoid complexity by treating the tree as a generic (if |
25 | // weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such, | |
26 | // this module doesn't care whether the entries are sorted, which nodes can be underfull, or | |
27 | // even what underfull means. However, we do rely on a few invariants: | |
28 | // | |
29 | // - Trees must have uniform depth/height. This means that every path down to a leaf from a | |
30 | // given node has exactly the same length. | |
31 | // - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges. | |
32 | // This implies that even an empty internal node has at least one edge. | |
33 | ||
74b04a01 | 34 | use core::cmp::Ordering; |
85aaf69f | 35 | use core::marker::PhantomData; |
0bf4aa26 | 36 | use core::mem::{self, MaybeUninit}; |
dfeec247 | 37 | use core::ptr::{self, NonNull, Unique}; |
9cc50fc6 SL |
38 | use core::slice; |
39 | ||
74b04a01 | 40 | use crate::alloc::{AllocRef, Global, Layout}; |
9fa01778 | 41 | use crate::boxed::Box; |
9cc50fc6 SL |
42 | |
43 | const B: usize = 6; | |
3157f602 | 44 | pub const MIN_LEN: usize = B - 1; |
9cc50fc6 | 45 | pub const CAPACITY: usize = 2 * B - 1; |
3dfed10e XL |
46 | const KV_IDX_CENTER: usize = B - 1; |
47 | const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1; | |
48 | const EDGE_IDX_RIGHT_OF_CENTER: usize = B; | |
9cc50fc6 | 49 | |
1b1a35ee | 50 | /// The underlying representation of leaf nodes and part of the representation of internal nodes. |
9cc50fc6 | 51 | struct LeafNode<K, V> { |
1b1a35ee XL |
52 | /// We want to be covariant in `K` and `V`. |
53 | parent: Option<NonNull<InternalNode<K, V>>>, | |
a7813a04 XL |
54 | |
55 | /// This node's index into the parent node's `edges` array. | |
56 | /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`. | |
a1dfa0c6 | 57 | /// This is only guaranteed to be initialized when `parent` is non-null. |
0bf4aa26 | 58 | parent_idx: MaybeUninit<u16>, |
a7813a04 XL |
59 | |
60 | /// The number of keys and values this node stores. | |
9cc50fc6 | 61 | len: u16, |
94b46f34 XL |
62 | |
63 | /// The arrays storing the actual data of the node. Only the first `len` elements of each | |
64 | /// array are initialized and valid. | |
9fa01778 XL |
65 | keys: [MaybeUninit<K>; CAPACITY], |
66 | vals: [MaybeUninit<V>; CAPACITY], | |
1a4d82fc JJ |
67 | } |
68 | ||
9cc50fc6 | 69 | impl<K, V> LeafNode<K, V> { |
a7813a04 XL |
70 | /// Creates a new `LeafNode`. Unsafe because all nodes should really be hidden behind |
71 | /// `BoxedNode`, preventing accidental dropping of uninitialized keys and values. | |
9cc50fc6 SL |
72 | unsafe fn new() -> Self { |
73 | LeafNode { | |
a7813a04 XL |
74 | // As a general policy, we leave fields uninitialized if they can be, as this should |
75 | // be both slightly faster and easier to track in Valgrind. | |
1b1a35ee XL |
76 | keys: MaybeUninit::uninit_array(), |
77 | vals: MaybeUninit::uninit_array(), | |
78 | parent: None, | |
532ac7d7 | 79 | parent_idx: MaybeUninit::uninit(), |
dfeec247 | 80 | len: 0, |
b039eaaf | 81 | } |
9cc50fc6 | 82 | } |
0731742a | 83 | } |
94b46f34 | 84 | |
a7813a04 XL |
85 | /// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden |
86 | /// behind `BoxedNode`s to prevent dropping uninitialized keys and values. Any pointer to an | |
87 | /// `InternalNode` can be directly casted to a pointer to the underlying `LeafNode` portion of the | |
88 | /// node, allowing code to act on leaf and internal nodes generically without having to even check | |
89 | /// which of the two a pointer is pointing at. This property is enabled by the use of `repr(C)`. | |
9cc50fc6 | 90 | #[repr(C)] |
1b1a35ee | 91 | // gdb_providers.py uses this type name for introspection. |
9cc50fc6 | 92 | struct InternalNode<K, V> { |
1b1a35ee | 93 | // gdb_providers.py uses this field name for introspection. |
9cc50fc6 | 94 | data: LeafNode<K, V>, |
a7813a04 XL |
95 | |
96 | /// The pointers to the children of this node. `len + 1` of these are considered | |
3dfed10e XL |
97 | /// initialized and valid. Although during the process of `into_iter` or `drop`, |
98 | /// some pointers are dangling while others still need to be traversed. | |
9fa01778 | 99 | edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B], |
1a4d82fc JJ |
100 | } |
101 | ||
9cc50fc6 | 102 | impl<K, V> InternalNode<K, V> { |
a7813a04 XL |
103 | /// Creates a new `InternalNode`. |
104 | /// | |
105 | /// This is unsafe for two reasons. First, it returns an `InternalNode` by value, risking | |
106 | /// dropping of uninitialized fields. Second, an invariant of internal nodes is that `len + 1` | |
107 | /// edges are initialized and valid, meaning that even when the node is empty (having a | |
108 | /// `len` of 0), there must be one initialized and valid edge. This function does not set up | |
109 | /// such an edge. | |
9cc50fc6 | 110 | unsafe fn new() -> Self { |
1b1a35ee | 111 | InternalNode { data: unsafe { LeafNode::new() }, edges: MaybeUninit::uninit_array() } |
1a4d82fc JJ |
112 | } |
113 | } | |
114 | ||
74b04a01 | 115 | /// A managed, non-null pointer to a node. This is either an owned pointer to |
ba9703b0 XL |
116 | /// `LeafNode<K, V>` or an owned pointer to `InternalNode<K, V>`. |
117 | /// | |
118 | /// However, `BoxedNode` contains no information as to which of the two types | |
74b04a01 XL |
119 | /// of nodes it actually contains, and, partially due to this lack of information, |
120 | /// has no destructor. | |
9cc50fc6 | 121 | struct BoxedNode<K, V> { |
dfeec247 | 122 | ptr: Unique<LeafNode<K, V>>, |
9cc50fc6 | 123 | } |
1a4d82fc | 124 | |
9cc50fc6 SL |
125 | impl<K, V> BoxedNode<K, V> { |
126 | fn from_leaf(node: Box<LeafNode<K, V>>) -> Self { | |
3b2f2976 | 127 | BoxedNode { ptr: Box::into_unique(node) } |
1a4d82fc | 128 | } |
1a4d82fc | 129 | |
9cc50fc6 | 130 | fn from_internal(node: Box<InternalNode<K, V>>) -> Self { |
1b1a35ee | 131 | BoxedNode { ptr: Unique::from(&mut Box::leak(node).data) } |
1a4d82fc | 132 | } |
1a4d82fc | 133 | |
0531ce1d | 134 | unsafe fn from_ptr(ptr: NonNull<LeafNode<K, V>>) -> Self { |
f035d41b | 135 | BoxedNode { ptr: unsafe { Unique::new_unchecked(ptr.as_ptr()) } } |
1a4d82fc | 136 | } |
1a4d82fc | 137 | |
0531ce1d XL |
138 | fn as_ptr(&self) -> NonNull<LeafNode<K, V>> { |
139 | NonNull::from(self.ptr) | |
1a4d82fc JJ |
140 | } |
141 | } | |
142 | ||
ba9703b0 XL |
143 | /// An owned tree. |
144 | /// | |
145 | /// Note that this does not have a destructor, and must be cleaned up manually. | |
9cc50fc6 SL |
146 | pub struct Root<K, V> { |
147 | node: BoxedNode<K, V>, | |
74b04a01 | 148 | /// The number of levels below the root node. |
dfeec247 | 149 | height: usize, |
9cc50fc6 | 150 | } |
1a4d82fc | 151 | |
dfeec247 XL |
152 | unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {} |
153 | unsafe impl<K: Send, V: Send> Send for Root<K, V> {} | |
1a4d82fc | 154 | |
9cc50fc6 | 155 | impl<K, V> Root<K, V> { |
3dfed10e XL |
156 | /// Returns the number of levels below the root. |
157 | pub fn height(&self) -> usize { | |
158 | self.height | |
159 | } | |
160 | ||
74b04a01 | 161 | /// Returns a new owned tree, with its own root node that is initially empty. |
9cc50fc6 | 162 | pub fn new_leaf() -> Self { |
dfeec247 | 163 | Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 } |
1a4d82fc JJ |
164 | } |
165 | ||
3dfed10e XL |
166 | /// Borrows and returns an immutable reference to the node owned by the root. |
167 | pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> { | |
1b1a35ee | 168 | NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
1a4d82fc JJ |
169 | } |
170 | ||
3dfed10e XL |
171 | /// Borrows and returns a mutable reference to the node owned by the root. |
172 | pub fn node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> { | |
1b1a35ee XL |
173 | NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
174 | } | |
175 | ||
176 | pub fn node_as_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, marker::LeafOrInternal> { | |
177 | NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } | |
1a4d82fc JJ |
178 | } |
179 | ||
dfeec247 | 180 | pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { |
1b1a35ee | 181 | NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } |
1a4d82fc JJ |
182 | } |
183 | ||
1b1a35ee XL |
184 | /// Adds a new internal node with a single edge pointing to the previous root node, |
185 | /// make that new node the root node, and return it. This increases the height by 1 | |
186 | /// and is the opposite of `pop_internal_level`. | |
3dfed10e | 187 | pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { |
9cc50fc6 | 188 | let mut new_node = Box::new(unsafe { InternalNode::new() }); |
532ac7d7 | 189 | new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) }); |
1a4d82fc | 190 | |
9cc50fc6 SL |
191 | self.node = BoxedNode::from_internal(new_node); |
192 | self.height += 1; | |
1a4d82fc | 193 | |
1b1a35ee XL |
194 | let mut ret = |
195 | NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }; | |
1a4d82fc | 196 | |
9cc50fc6 SL |
197 | unsafe { |
198 | ret.reborrow_mut().first_edge().correct_parent_link(); | |
199 | } | |
1a4d82fc | 200 | |
9cc50fc6 | 201 | ret |
1a4d82fc JJ |
202 | } |
203 | ||
1b1a35ee XL |
204 | /// Removes the internal root node, using its first child as the new root node. |
205 | /// As it is intended only to be called when the root node has only one child, | |
206 | /// no cleanup is done on any of the other children. | |
3dfed10e | 207 | /// This decreases the height by 1 and is the opposite of `push_internal_level`. |
1b1a35ee XL |
208 | /// |
209 | /// Requires exclusive access to the `Root` object but not to the root node; | |
210 | /// it will not invalidate existing handles or references to the root node. | |
211 | /// | |
212 | /// Panics if there is no internal level, i.e., if the root node is a leaf. | |
3dfed10e | 213 | pub fn pop_internal_level(&mut self) { |
74b04a01 | 214 | assert!(self.height > 0); |
1a4d82fc | 215 | |
83c7162d | 216 | let top = self.node.ptr; |
1a4d82fc | 217 | |
9cc50fc6 | 218 | self.node = unsafe { |
dfeec247 | 219 | BoxedNode::from_ptr( |
3dfed10e | 220 | self.node_as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node, |
dfeec247 | 221 | ) |
1a4d82fc | 222 | }; |
9cc50fc6 | 223 | self.height -= 1; |
1b1a35ee | 224 | self.node_as_mut().as_leaf_mut().parent = None; |
1a4d82fc JJ |
225 | |
226 | unsafe { | |
94b46f34 | 227 | Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>()); |
1a4d82fc | 228 | } |
1a4d82fc JJ |
229 | } |
230 | } | |
231 | ||
9cc50fc6 SL |
232 | // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType` |
233 | // is `Mut`. This is technically wrong, but cannot result in any unsafety due to | |
234 | // internal use of `NodeRef` because we stay completely generic over `K` and `V`. | |
235 | // However, whenever a public type wraps `NodeRef`, make sure that it has the | |
236 | // correct variance. | |
237 | /// A reference to a node. | |
1a4d82fc | 238 | /// |
3b2f2976 | 239 | /// This type has a number of parameters that controls how it acts: |
1b1a35ee XL |
240 | /// - `BorrowType`: This can be `Immut<'a>`, `Mut<'a>` or `ValMut<'a>' for some `'a` |
241 | /// or `Owned`. | |
9cc50fc6 SL |
242 | /// When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`, |
243 | /// when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`, | |
1b1a35ee XL |
244 | /// when this is `ValMut<'a>`, the `NodeRef` acts as immutable with respect |
245 | /// to keys and tree structure, but allows mutable references to values, | |
9cc50fc6 SL |
246 | /// and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`. |
247 | /// - `K` and `V`: These control what types of things are stored in the nodes. | |
248 | /// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is | |
249 | /// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the | |
250 | /// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the | |
251 | /// `NodeRef` could be pointing to either type of node. | |
252 | pub struct NodeRef<BorrowType, K, V, Type> { | |
74b04a01 | 253 | /// The number of levels below the node. |
9cc50fc6 | 254 | height: usize, |
0531ce1d | 255 | node: NonNull<LeafNode<K, V>>, |
dfeec247 | 256 | _marker: PhantomData<(BorrowType, Type)>, |
1a4d82fc JJ |
257 | } |
258 | ||
dfeec247 | 259 | impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {} |
9cc50fc6 SL |
260 | impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> { |
261 | fn clone(&self) -> Self { | |
262 | *self | |
263 | } | |
1a4d82fc JJ |
264 | } |
265 | ||
dfeec247 | 266 | unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {} |
9cc50fc6 | 267 | |
dfeec247 XL |
268 | unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {} |
269 | unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {} | |
1b1a35ee | 270 | unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {} |
dfeec247 | 271 | unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {} |
9cc50fc6 SL |
272 | |
273 | impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { | |
1b1a35ee XL |
274 | /// Exposes the data of an internal node for reading. |
275 | /// | |
276 | /// Returns a raw ptr to avoid invalidating other references to this node, | |
277 | /// which is possible when BorrowType is marker::ValMut. | |
278 | fn as_internal_ptr(&self) -> *const InternalNode<K, V> { | |
279 | self.node.as_ptr() as *const InternalNode<K, V> | |
1a4d82fc | 280 | } |
1a4d82fc JJ |
281 | } |
282 | ||
9cc50fc6 | 283 | impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { |
1b1a35ee XL |
284 | /// Exposes the data of an internal node for reading, |
285 | /// when we know we have exclusive access. | |
286 | fn as_internal(&mut self) -> &InternalNode<K, V> { | |
287 | unsafe { &*self.as_internal_ptr() } | |
288 | } | |
289 | } | |
290 | ||
291 | impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { | |
292 | /// Exposes the data of an internal node for writing. | |
293 | /// | |
294 | /// We don't need to return a raw ptr because we have unique access to the entire node. | |
9cc50fc6 | 295 | fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> { |
dfeec247 | 296 | unsafe { &mut *(self.node.as_ptr() as *mut InternalNode<K, V>) } |
1a4d82fc | 297 | } |
9cc50fc6 SL |
298 | } |
299 | ||
9cc50fc6 | 300 | impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { |
a7813a04 XL |
301 | /// Finds the length of the node. This is the number of keys or values. In an |
302 | /// internal node, the number of edges is `len() + 1`. | |
74b04a01 XL |
303 | /// For any node, the number of possible edge handles is also `len() + 1`. |
304 | /// Note that, despite being safe, calling this function can have the side effect | |
305 | /// of invalidating mutable references that unsafe code has created. | |
85aaf69f | 306 | pub fn len(&self) -> usize { |
1b1a35ee XL |
307 | // Crucially, we only access the `len` field here. If BorrowType is marker::ValMut, |
308 | // there might be outstanding mutable references to values that we must not invalidate. | |
309 | unsafe { usize::from((*self.as_leaf_ptr()).len) } | |
1a4d82fc JJ |
310 | } |
311 | ||
a7813a04 XL |
312 | /// Returns the height of this node in the whole tree. Zero height denotes the |
313 | /// leaf level. | |
314 | pub fn height(&self) -> usize { | |
315 | self.height | |
316 | } | |
317 | ||
a7813a04 | 318 | /// Temporarily takes out another, immutable reference to the same node. |
416331ca | 319 | fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> { |
1b1a35ee | 320 | NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
1a4d82fc JJ |
321 | } |
322 | ||
1b1a35ee | 323 | /// Exposes the leaf portion of any leaf or internal node. |
dfeec247 XL |
324 | /// If the node is a leaf, this function simply opens up its data. |
325 | /// If the node is an internal node, so not a leaf, it does have all the data a leaf has | |
326 | /// (header, keys and values), and this function exposes that. | |
1b1a35ee XL |
327 | /// |
328 | /// Returns a raw ptr to avoid invalidating other references to this node, | |
329 | /// which is possible when BorrowType is marker::ValMut. | |
330 | fn as_leaf_ptr(&self) -> *const LeafNode<K, V> { | |
ba9703b0 XL |
331 | // The node must be valid for at least the LeafNode portion. |
332 | // This is not a reference in the NodeRef type because we don't know if | |
333 | // it should be unique or shared. | |
1b1a35ee | 334 | self.node.as_ptr() |
94b46f34 XL |
335 | } |
336 | ||
1b1a35ee XL |
337 | /// Borrows a reference to one of the keys stored in the node. |
338 | /// | |
339 | /// # Safety | |
340 | /// The node has more than `idx` initialized elements. | |
341 | pub unsafe fn key_at(&self, idx: usize) -> &K { | |
342 | unsafe { self.reborrow().into_key_at(idx) } | |
1a4d82fc JJ |
343 | } |
344 | ||
1b1a35ee XL |
345 | /// Borrows a reference to one of the values stored in the node. |
346 | /// | |
347 | /// # Safety | |
348 | /// The node has more than `idx` initialized elements. | |
349 | unsafe fn val_at(&self, idx: usize) -> &V { | |
350 | unsafe { self.reborrow().into_val_at(idx) } | |
1a4d82fc | 351 | } |
1b1a35ee | 352 | } |
1a4d82fc | 353 | |
1b1a35ee XL |
354 | impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { |
355 | /// Borrows a reference to the contents of one of the edges that delimit | |
356 | /// the elements of the node, without invalidating other references. | |
357 | /// | |
358 | /// # Safety | |
359 | /// The node has more than `idx` initialized elements. | |
360 | unsafe fn edge_at(&self, idx: usize) -> &BoxedNode<K, V> { | |
361 | debug_assert!(idx <= self.len()); | |
362 | let node = self.as_internal_ptr(); | |
363 | unsafe { (*node).edges.get_unchecked(idx).assume_init_ref() } | |
364 | } | |
365 | } | |
366 | ||
367 | impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { | |
a7813a04 XL |
368 | /// Finds the parent of the current node. Returns `Ok(handle)` if the current |
369 | /// node actually has a parent, where `handle` points to the edge of the parent | |
370 | /// that points to the current node. Returns `Err(self)` if the current node has | |
371 | /// no parent, giving back the original `NodeRef`. | |
372 | /// | |
373 | /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should | |
374 | /// both, upon success, do nothing. | |
dfeec247 XL |
375 | pub fn ascend( |
376 | self, | |
377 | ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> { | |
1b1a35ee XL |
378 | // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut, |
379 | // there might be outstanding mutable references to values that we must not invalidate. | |
380 | let leaf_ptr = self.as_leaf_ptr(); | |
381 | unsafe { (*leaf_ptr).parent } | |
382 | .as_ref() | |
383 | .map(|parent| Handle { | |
9cc50fc6 SL |
384 | node: NodeRef { |
385 | height: self.height + 1, | |
1b1a35ee | 386 | node: parent.cast(), |
dfeec247 | 387 | _marker: PhantomData, |
9cc50fc6 | 388 | }, |
1b1a35ee | 389 | idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) }, |
dfeec247 | 390 | _marker: PhantomData, |
9cc50fc6 | 391 | }) |
1b1a35ee | 392 | .ok_or(self) |
1a4d82fc | 393 | } |
1a4d82fc | 394 | |
9cc50fc6 | 395 | pub fn first_edge(self) -> Handle<Self, marker::Edge> { |
74b04a01 | 396 | unsafe { Handle::new_edge(self, 0) } |
1a4d82fc JJ |
397 | } |
398 | ||
9cc50fc6 SL |
399 | pub fn last_edge(self) -> Handle<Self, marker::Edge> { |
400 | let len = self.len(); | |
74b04a01 | 401 | unsafe { Handle::new_edge(self, len) } |
1a4d82fc | 402 | } |
3157f602 XL |
403 | |
404 | /// Note that `self` must be nonempty. | |
405 | pub fn first_kv(self) -> Handle<Self, marker::KV> { | |
74b04a01 XL |
406 | let len = self.len(); |
407 | assert!(len > 0); | |
408 | unsafe { Handle::new_kv(self, 0) } | |
3157f602 XL |
409 | } |
410 | ||
411 | /// Note that `self` must be nonempty. | |
412 | pub fn last_kv(self) -> Handle<Self, marker::KV> { | |
413 | let len = self.len(); | |
74b04a01 XL |
414 | assert!(len > 0); |
415 | unsafe { Handle::new_kv(self, len - 1) } | |
1a4d82fc JJ |
416 | } |
417 | } | |
418 | ||
1b1a35ee XL |
419 | impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { |
420 | /// Exposes the data of a leaf node for reading in an immutable tree. | |
421 | fn into_leaf(self) -> &'a LeafNode<K, V> { | |
422 | // SAFETY: we can access the entire node freely and do no need raw pointers, | |
423 | // because there can be no mutable references to this Immut tree. | |
424 | unsafe { &(*self.as_leaf_ptr()) } | |
425 | } | |
426 | } | |
427 | ||
74b04a01 | 428 | impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { |
a7813a04 XL |
429 | /// Similar to `ascend`, gets a reference to a node's parent node, but also |
430 | /// deallocate the current node in the process. This is unsafe because the | |
431 | /// current node will still be accessible despite being deallocated. | |
dfeec247 XL |
432 | pub unsafe fn deallocate_and_ascend( |
433 | self, | |
434 | ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> { | |
74b04a01 | 435 | let height = self.height; |
83c7162d | 436 | let node = self.node; |
9cc50fc6 | 437 | let ret = self.ascend().ok(); |
f035d41b XL |
438 | unsafe { |
439 | Global.dealloc( | |
440 | node.cast(), | |
441 | if height > 0 { | |
442 | Layout::new::<InternalNode<K, V>>() | |
443 | } else { | |
444 | Layout::new::<LeafNode<K, V>>() | |
445 | }, | |
446 | ); | |
447 | } | |
9cc50fc6 | 448 | ret |
1a4d82fc JJ |
449 | } |
450 | } | |
451 | ||
9cc50fc6 | 452 | impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> { |
a7813a04 | 453 | /// Unsafely asserts to the compiler some static information about whether this |
3dfed10e XL |
454 | /// node is a `Leaf` or an `Internal`. |
455 | unsafe fn cast_unchecked<NewType>(self) -> NodeRef<marker::Mut<'a>, K, V, NewType> { | |
1b1a35ee | 456 | NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
1a4d82fc | 457 | } |
1a4d82fc | 458 | |
a7813a04 XL |
459 | /// Temporarily takes out another, mutable reference to the same node. Beware, as |
460 | /// this method is very dangerous, doubly so since it may not immediately appear | |
461 | /// dangerous. | |
462 | /// | |
1b1a35ee XL |
463 | /// Because mutable pointers can roam anywhere around the tree, the returned |
464 | /// pointer can easily be used to make the original pointer dangling, out of | |
465 | /// bounds, or invalid under stacked borrow rules. | |
466 | // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` | |
467 | // that restricts the use of navigation methods on reborrowed pointers, | |
468 | // preventing this unsafety. | |
9fa01778 | 469 | unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> { |
1b1a35ee | 470 | NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
1a4d82fc JJ |
471 | } |
472 | ||
1b1a35ee | 473 | /// Exposes the leaf portion of any leaf or internal node for writing. |
dfeec247 XL |
474 | /// If the node is a leaf, this function simply opens up its data. |
475 | /// If the node is an internal node, so not a leaf, it does have all the data a leaf has | |
476 | /// (header, keys and values), and this function exposes that. | |
477 | /// | |
1b1a35ee XL |
478 | /// We don't need to return a raw ptr because we have unique access to the entire node. |
479 | fn as_leaf_mut(&mut self) -> &'a mut LeafNode<K, V> { | |
480 | unsafe { &mut (*self.node.as_ptr()) } | |
481 | } | |
482 | ||
483 | /// Borrows a mutable reference to one of the keys stored in the node. | |
484 | /// | |
485 | /// # Safety | |
486 | /// The node has more than `idx` initialized elements. | |
487 | pub unsafe fn key_mut_at(&mut self, idx: usize) -> &mut K { | |
488 | unsafe { self.reborrow_mut().into_key_mut_at(idx) } | |
1a4d82fc JJ |
489 | } |
490 | ||
1b1a35ee XL |
491 | /// Borrows a mutable reference to one of the values stored in the node. |
492 | /// | |
493 | /// # Safety | |
494 | /// The node has more than `idx` initialized elements. | |
495 | pub unsafe fn val_mut_at(&mut self, idx: usize) -> &mut V { | |
496 | unsafe { self.reborrow_mut().into_val_mut_at(idx) } | |
497 | } | |
498 | ||
499 | fn keys_mut(&mut self) -> &mut [K] | |
500 | where | |
501 | K: 'a, | |
502 | V: 'a, | |
503 | { | |
ba9703b0 XL |
504 | // SAFETY: the caller will not be able to call further methods on self |
505 | // until the key slice reference is dropped, as we have unique access | |
506 | // for the lifetime of the borrow. | |
1b1a35ee XL |
507 | // SAFETY: The keys of a node must always be initialized up to length. |
508 | unsafe { | |
509 | slice::from_raw_parts_mut( | |
510 | MaybeUninit::slice_as_mut_ptr(&mut self.as_leaf_mut().keys), | |
511 | self.len(), | |
512 | ) | |
513 | } | |
1a4d82fc JJ |
514 | } |
515 | ||
1b1a35ee XL |
516 | fn vals_mut(&mut self) -> &mut [V] |
517 | where | |
518 | K: 'a, | |
519 | V: 'a, | |
520 | { | |
ba9703b0 XL |
521 | // SAFETY: the caller will not be able to call further methods on self |
522 | // until the value slice reference is dropped, as we have unique access | |
523 | // for the lifetime of the borrow. | |
1b1a35ee XL |
524 | // SAFETY: The values of a node must always be initialized up to length. |
525 | unsafe { | |
526 | slice::from_raw_parts_mut( | |
527 | MaybeUninit::slice_as_mut_ptr(&mut self.as_leaf_mut().vals), | |
528 | self.len(), | |
529 | ) | |
530 | } | |
531 | } | |
532 | } | |
533 | ||
534 | impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { | |
535 | fn edges_mut(&mut self) -> &mut [BoxedNode<K, V>] { | |
536 | unsafe { | |
537 | slice::from_raw_parts_mut( | |
538 | MaybeUninit::slice_as_mut_ptr(&mut self.as_internal_mut().edges), | |
539 | self.len() + 1, | |
540 | ) | |
541 | } | |
1a4d82fc JJ |
542 | } |
543 | } | |
544 | ||
9cc50fc6 | 545 | impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { |
1b1a35ee XL |
546 | /// # Safety |
547 | /// The node has more than `idx` initialized elements. | |
548 | unsafe fn into_key_at(self, idx: usize) -> &'a K { | |
549 | unsafe { self.into_leaf().keys.get_unchecked(idx).assume_init_ref() } | |
94b46f34 XL |
550 | } |
551 | ||
1b1a35ee XL |
552 | /// # Safety |
553 | /// The node has more than `idx` initialized elements. | |
554 | unsafe fn into_val_at(self, idx: usize) -> &'a V { | |
555 | unsafe { self.into_leaf().vals.get_unchecked(idx).assume_init_ref() } | |
1a4d82fc | 556 | } |
9cc50fc6 | 557 | } |
1a4d82fc | 558 | |
9cc50fc6 | 559 | impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> { |
1b1a35ee XL |
560 | /// # Safety |
561 | /// The node has more than `idx` initialized elements. | |
562 | unsafe fn into_key_mut_at(mut self, idx: usize) -> &'a mut K { | |
563 | debug_assert!(idx < self.len()); | |
1a4d82fc | 564 | |
1b1a35ee XL |
565 | let leaf = self.as_leaf_mut(); |
566 | unsafe { leaf.keys.get_unchecked_mut(idx).assume_init_mut() } | |
94b46f34 XL |
567 | } |
568 | ||
1b1a35ee XL |
569 | /// # Safety |
570 | /// The node has more than `idx` initialized elements. | |
571 | unsafe fn into_val_mut_at(mut self, idx: usize) -> &'a mut V { | |
572 | debug_assert!(idx < self.len()); | |
94b46f34 | 573 | |
74b04a01 | 574 | let leaf = self.as_leaf_mut(); |
1b1a35ee XL |
575 | unsafe { leaf.vals.get_unchecked_mut(idx).assume_init_mut() } |
576 | } | |
577 | } | |
578 | ||
579 | impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> { | |
580 | /// # Safety | |
581 | /// The node has more than `idx` initialized elements. | |
582 | unsafe fn into_key_val_mut_at(self, idx: usize) -> (&'a K, &'a mut V) { | |
583 | // We only create a reference to the one element we are interested in, | |
584 | // to avoid aliasing with outstanding references to other elements, | |
585 | // in particular, those returned to the caller in earlier iterations. | |
586 | let leaf = self.node.as_ptr(); | |
587 | // We must coerce to unsized array pointers because of Rust issue #74679. | |
588 | let keys: *const [_] = unsafe { &raw const (*leaf).keys }; | |
589 | let vals: *mut [_] = unsafe { &raw mut (*leaf).vals }; | |
ba9703b0 | 590 | // SAFETY: The keys and values of a node must always be initialized up to length. |
1b1a35ee XL |
591 | let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() }; |
592 | let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() }; | |
593 | (key, val) | |
94b46f34 | 594 | } |
1a4d82fc JJ |
595 | } |
596 | ||
1b1a35ee | 597 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { |
3dfed10e | 598 | /// Adds a key/value pair to the end of the node. |
9cc50fc6 | 599 | pub fn push(&mut self, key: K, val: V) { |
1b1a35ee XL |
600 | let len = &mut self.as_leaf_mut().len; |
601 | let idx = usize::from(*len); | |
602 | assert!(idx < CAPACITY); | |
603 | *len += 1; | |
1a4d82fc | 604 | unsafe { |
1b1a35ee XL |
605 | ptr::write(self.key_mut_at(idx), key); |
606 | ptr::write(self.val_mut_at(idx), val); | |
0731742a | 607 | } |
1a4d82fc JJ |
608 | } |
609 | ||
a7813a04 | 610 | /// Adds a key/value pair to the beginning of the node. |
1b1a35ee XL |
611 | fn push_front(&mut self, key: K, val: V) { |
612 | debug_assert!(self.len() < CAPACITY); | |
9cc50fc6 SL |
613 | |
614 | unsafe { | |
615 | slice_insert(self.keys_mut(), 0, key); | |
616 | slice_insert(self.vals_mut(), 0, val); | |
0731742a | 617 | } |
1b1a35ee | 618 | self.as_leaf_mut().len += 1; |
1a4d82fc JJ |
619 | } |
620 | } | |
621 | ||
9cc50fc6 | 622 | impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { |
1b1a35ee XL |
623 | /// # Safety |
624 | /// Every item returned by `range` is a valid edge index for the node. | |
625 | unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) { | |
626 | for i in range { | |
627 | debug_assert!(i <= self.len()); | |
628 | unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link(); | |
629 | } | |
630 | } | |
631 | ||
632 | fn correct_all_childrens_parent_links(&mut self) { | |
633 | let len = self.len(); | |
634 | unsafe { self.correct_childrens_parent_links(0..=len) }; | |
635 | } | |
636 | } | |
637 | ||
638 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { | |
639 | /// Adds a key/value pair, and an edge to go to the right of that pair, | |
640 | /// to the end of the node. | |
9cc50fc6 | 641 | pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) { |
74b04a01 | 642 | assert!(edge.height == self.height - 1); |
1a4d82fc | 643 | |
1b1a35ee XL |
644 | let len = &mut self.as_leaf_mut().len; |
645 | let idx = usize::from(*len); | |
646 | assert!(idx < CAPACITY); | |
647 | *len += 1; | |
9cc50fc6 | 648 | unsafe { |
1b1a35ee XL |
649 | ptr::write(self.key_mut_at(idx), key); |
650 | ptr::write(self.val_mut_at(idx), val); | |
532ac7d7 | 651 | self.as_internal_mut().edges.get_unchecked_mut(idx + 1).write(edge.node); |
9cc50fc6 | 652 | Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link(); |
1a4d82fc JJ |
653 | } |
654 | } | |
655 | ||
1b1a35ee XL |
656 | /// Adds a key/value pair, and an edge to go to the left of that pair, |
657 | /// to the beginning of the node. | |
9cc50fc6 | 658 | pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) { |
74b04a01 XL |
659 | assert!(edge.height == self.height - 1); |
660 | assert!(self.len() < CAPACITY); | |
9cc50fc6 SL |
661 | |
662 | unsafe { | |
663 | slice_insert(self.keys_mut(), 0, key); | |
664 | slice_insert(self.vals_mut(), 0, val); | |
665 | slice_insert( | |
666 | slice::from_raw_parts_mut( | |
1b1a35ee | 667 | MaybeUninit::slice_as_mut_ptr(&mut self.as_internal_mut().edges), |
dfeec247 | 668 | self.len() + 1, |
9cc50fc6 SL |
669 | ), |
670 | 0, | |
dfeec247 | 671 | edge.node, |
9cc50fc6 | 672 | ); |
1b1a35ee | 673 | } |
9cc50fc6 | 674 | |
1b1a35ee | 675 | self.as_leaf_mut().len += 1; |
9cc50fc6 | 676 | |
1b1a35ee | 677 | self.correct_all_childrens_parent_links(); |
1a4d82fc JJ |
678 | } |
679 | } | |
680 | ||
1b1a35ee | 681 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { |
3dfed10e XL |
682 | /// Removes a key/value pair from the end of this node and returns the pair. |
683 | /// If this is an internal node, also removes the edge that was to the right | |
1b1a35ee XL |
684 | /// of that pair and returns the orphaned node that this edge owned. |
685 | fn pop(&mut self) -> (K, V, Option<Root<K, V>>) { | |
686 | debug_assert!(self.len() > 0); | |
9cc50fc6 SL |
687 | |
688 | let idx = self.len() - 1; | |
689 | ||
690 | unsafe { | |
1b1a35ee XL |
691 | let key = ptr::read(self.key_at(idx)); |
692 | let val = ptr::read(self.val_at(idx)); | |
9cc50fc6 SL |
693 | let edge = match self.reborrow_mut().force() { |
694 | ForceResult::Leaf(_) => None, | |
695 | ForceResult::Internal(internal) => { | |
1b1a35ee | 696 | let edge = ptr::read(internal.edge_at(idx + 1)); |
9cc50fc6 | 697 | let mut new_root = Root { node: edge, height: internal.height - 1 }; |
1b1a35ee | 698 | new_root.node_as_mut().as_leaf_mut().parent = None; |
9cc50fc6 SL |
699 | Some(new_root) |
700 | } | |
1a4d82fc JJ |
701 | }; |
702 | ||
1b1a35ee | 703 | self.as_leaf_mut().len -= 1; |
1a4d82fc | 704 | (key, val, edge) |
1a4d82fc JJ |
705 | } |
706 | } | |
707 | ||
1b1a35ee XL |
708 | /// Removes a key/value pair from the beginning of this node and returns the pair. |
709 | /// If this is an internal node, also removes the edge that was to the left | |
710 | /// of that pair and returns the orphaned node that this edge owned. | |
711 | fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) { | |
712 | debug_assert!(self.len() > 0); | |
1a4d82fc | 713 | |
9cc50fc6 | 714 | let old_len = self.len(); |
1a4d82fc | 715 | |
9cc50fc6 SL |
716 | unsafe { |
717 | let key = slice_remove(self.keys_mut(), 0); | |
718 | let val = slice_remove(self.vals_mut(), 0); | |
719 | let edge = match self.reborrow_mut().force() { | |
720 | ForceResult::Leaf(_) => None, | |
721 | ForceResult::Internal(mut internal) => { | |
1b1a35ee | 722 | let edge = slice_remove(internal.edges_mut(), 0); |
9cc50fc6 | 723 | let mut new_root = Root { node: edge, height: internal.height - 1 }; |
1b1a35ee | 724 | new_root.node_as_mut().as_leaf_mut().parent = None; |
9cc50fc6 | 725 | |
1b1a35ee | 726 | internal.correct_childrens_parent_links(0..old_len); |
9cc50fc6 SL |
727 | |
728 | Some(new_root) | |
729 | } | |
730 | }; | |
1a4d82fc | 731 | |
1b1a35ee | 732 | self.as_leaf_mut().len -= 1; |
1a4d82fc | 733 | |
9cc50fc6 SL |
734 | (key, val, edge) |
735 | } | |
1a4d82fc | 736 | } |
3157f602 | 737 | |
ba9703b0 | 738 | fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) { |
dfeec247 | 739 | (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr()) |
3157f602 | 740 | } |
1a4d82fc JJ |
741 | } |
742 | ||
9cc50fc6 | 743 | impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
a7813a04 | 744 | /// Checks whether a node is an `Internal` node or a `Leaf` node. |
dfeec247 XL |
745 | pub fn force( |
746 | self, | |
747 | ) -> ForceResult< | |
9cc50fc6 | 748 | NodeRef<BorrowType, K, V, marker::Leaf>, |
dfeec247 | 749 | NodeRef<BorrowType, K, V, marker::Internal>, |
9cc50fc6 SL |
750 | > { |
751 | if self.height == 0 { | |
752 | ForceResult::Leaf(NodeRef { | |
753 | height: self.height, | |
754 | node: self.node, | |
dfeec247 | 755 | _marker: PhantomData, |
9cc50fc6 SL |
756 | }) |
757 | } else { | |
758 | ForceResult::Internal(NodeRef { | |
759 | height: self.height, | |
760 | node: self.node, | |
dfeec247 | 761 | _marker: PhantomData, |
9cc50fc6 | 762 | }) |
1a4d82fc JJ |
763 | } |
764 | } | |
9cc50fc6 | 765 | } |
1a4d82fc | 766 | |
a7813a04 XL |
767 | /// A reference to a specific key/value pair or edge within a node. The `Node` parameter |
768 | /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key/value | |
769 | /// pair) or `Edge` (signifying a handle on an edge). | |
770 | /// | |
771 | /// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to | |
772 | /// a child node, these represent the spaces where child pointers would go between the key/value | |
773 | /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one | |
774 | /// to the left of the node, one between the two pairs, and one at the right of the node. | |
9cc50fc6 SL |
775 | pub struct Handle<Node, Type> { |
776 | node: Node, | |
777 | idx: usize, | |
dfeec247 | 778 | _marker: PhantomData<Type>, |
9cc50fc6 | 779 | } |
1a4d82fc | 780 | |
dfeec247 | 781 | impl<Node: Copy, Type> Copy for Handle<Node, Type> {} |
a7813a04 XL |
782 | // We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be |
783 | // `Clone`able is when it is an immutable reference and therefore `Copy`. | |
9cc50fc6 SL |
784 | impl<Node: Copy, Type> Clone for Handle<Node, Type> { |
785 | fn clone(&self) -> Self { | |
786 | *self | |
1a4d82fc | 787 | } |
9cc50fc6 | 788 | } |
1a4d82fc | 789 | |
9cc50fc6 | 790 | impl<Node, Type> Handle<Node, Type> { |
3dfed10e | 791 | /// Retrieves the node that contains the edge or key/value pair this handle points to. |
9cc50fc6 SL |
792 | pub fn into_node(self) -> Node { |
793 | self.node | |
1a4d82fc | 794 | } |
ba9703b0 XL |
795 | |
796 | /// Returns the position of this handle in the node. | |
797 | pub fn idx(&self) -> usize { | |
798 | self.idx | |
799 | } | |
9cc50fc6 | 800 | } |
1a4d82fc | 801 | |
9cc50fc6 | 802 | impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> { |
74b04a01 XL |
803 | /// Creates a new handle to a key/value pair in `node`. |
804 | /// Unsafe because the caller must ensure that `idx < node.len()`. | |
805 | pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self { | |
9cc50fc6 | 806 | debug_assert!(idx < node.len()); |
1a4d82fc | 807 | |
dfeec247 | 808 | Handle { node, idx, _marker: PhantomData } |
1a4d82fc | 809 | } |
1a4d82fc | 810 | |
9cc50fc6 | 811 | pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { |
74b04a01 | 812 | unsafe { Handle::new_edge(self.node, self.idx) } |
1a4d82fc JJ |
813 | } |
814 | ||
9cc50fc6 | 815 | pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { |
74b04a01 | 816 | unsafe { Handle::new_edge(self.node, self.idx + 1) } |
1a4d82fc | 817 | } |
9cc50fc6 | 818 | } |
1a4d82fc | 819 | |
9cc50fc6 | 820 | impl<BorrowType, K, V, NodeType, HandleType> PartialEq |
dfeec247 XL |
821 | for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> |
822 | { | |
9cc50fc6 SL |
823 | fn eq(&self, other: &Self) -> bool { |
824 | self.node.node == other.node.node && self.idx == other.idx | |
825 | } | |
826 | } | |
1a4d82fc | 827 | |
74b04a01 XL |
828 | impl<BorrowType, K, V, NodeType, HandleType> PartialOrd |
829 | for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> | |
830 | { | |
831 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
832 | if self.node.node == other.node.node { Some(self.idx.cmp(&other.idx)) } else { None } | |
833 | } | |
834 | } | |
835 | ||
9cc50fc6 | 836 | impl<BorrowType, K, V, NodeType, HandleType> |
dfeec247 XL |
837 | Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> |
838 | { | |
a7813a04 | 839 | /// Temporarily takes out another, immutable handle on the same location. |
dfeec247 | 840 | pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> { |
9cc50fc6 | 841 | // We can't use Handle::new_kv or Handle::new_edge because we don't know our type |
dfeec247 | 842 | Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData } |
1a4d82fc | 843 | } |
9cc50fc6 | 844 | } |
1a4d82fc | 845 | |
dfeec247 | 846 | impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> { |
a7813a04 XL |
847 | /// Temporarily takes out another, mutable handle on the same location. Beware, as |
848 | /// this method is very dangerous, doubly so since it may not immediately appear | |
849 | /// dangerous. | |
850 | /// | |
1b1a35ee | 851 | /// For details, see `NodeRef::reborrow_mut`. |
dfeec247 XL |
852 | pub unsafe fn reborrow_mut( |
853 | &mut self, | |
854 | ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> { | |
9cc50fc6 | 855 | // We can't use Handle::new_kv or Handle::new_edge because we don't know our type |
f035d41b | 856 | Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData } |
1a4d82fc | 857 | } |
9cc50fc6 | 858 | } |
1a4d82fc | 859 | |
dfeec247 | 860 | impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { |
74b04a01 XL |
861 | /// Creates a new handle to an edge in `node`. |
862 | /// Unsafe because the caller must ensure that `idx <= node.len()`. | |
863 | pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self { | |
9cc50fc6 | 864 | debug_assert!(idx <= node.len()); |
1a4d82fc | 865 | |
dfeec247 | 866 | Handle { node, idx, _marker: PhantomData } |
9cc50fc6 | 867 | } |
1a4d82fc | 868 | |
dfeec247 | 869 | pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> { |
74b04a01 XL |
870 | if self.idx > 0 { |
871 | Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) }) | |
872 | } else { | |
873 | Err(self) | |
874 | } | |
1a4d82fc JJ |
875 | } |
876 | ||
dfeec247 | 877 | pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> { |
74b04a01 XL |
878 | if self.idx < self.node.len() { |
879 | Ok(unsafe { Handle::new_kv(self.node, self.idx) }) | |
880 | } else { | |
881 | Err(self) | |
882 | } | |
1a4d82fc JJ |
883 | } |
884 | } | |
885 | ||
3dfed10e XL |
886 | enum InsertionPlace { |
887 | Left(usize), | |
888 | Right(usize), | |
889 | } | |
890 | ||
891 | /// Given an edge index where we want to insert into a node filled to capacity, | |
892 | /// computes a sensible KV index of a split point and where to perform the insertion. | |
893 | /// The goal of the split point is for its key and value to end up in a parent node; | |
894 | /// the keys, values and edges to the left of the split point become the left child; | |
895 | /// the keys, values and edges to the right of the split point become the right child. | |
896 | fn splitpoint(edge_idx: usize) -> (usize, InsertionPlace) { | |
897 | debug_assert!(edge_idx <= CAPACITY); | |
898 | // Rust issue #74834 tries to explain these symmetric rules. | |
899 | match edge_idx { | |
900 | 0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, InsertionPlace::Left(edge_idx)), | |
901 | EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Left(edge_idx)), | |
902 | EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Right(0)), | |
903 | _ => (KV_IDX_CENTER + 1, InsertionPlace::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))), | |
904 | } | |
905 | } | |
906 | ||
1b1a35ee | 907 | impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::Edge> { |
3dfed10e XL |
908 | /// Helps implementations of `insert_fit` for a particular `NodeType`, |
909 | /// by taking care of leaf data. | |
a7813a04 XL |
910 | /// Inserts a new key/value pair between the key/value pairs to the right and left of |
911 | /// this edge. This method assumes that there is enough space in the node for the new | |
912 | /// pair to fit. | |
3dfed10e | 913 | fn leafy_insert_fit(&mut self, key: K, val: V) { |
9cc50fc6 | 914 | debug_assert!(self.node.len() < CAPACITY); |
1a4d82fc JJ |
915 | |
916 | unsafe { | |
9cc50fc6 SL |
917 | slice_insert(self.node.keys_mut(), self.idx, key); |
918 | slice_insert(self.node.vals_mut(), self.idx, val); | |
1a4d82fc | 919 | |
1b1a35ee | 920 | self.node.as_leaf_mut().len += 1; |
1a4d82fc JJ |
921 | } |
922 | } | |
3dfed10e XL |
923 | } |
924 | ||
1b1a35ee | 925 | impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { |
3dfed10e XL |
926 | /// Inserts a new key/value pair between the key/value pairs to the right and left of |
927 | /// this edge. This method assumes that there is enough space in the node for the new | |
928 | /// pair to fit. | |
929 | /// | |
930 | /// The returned pointer points to the inserted value. | |
931 | fn insert_fit(&mut self, key: K, val: V) -> *mut V { | |
932 | self.leafy_insert_fit(key, val); | |
1b1a35ee | 933 | unsafe { self.node.val_mut_at(self.idx) } |
3dfed10e XL |
934 | } |
935 | } | |
1a4d82fc | 936 | |
1b1a35ee | 937 | impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { |
a7813a04 XL |
938 | /// Inserts a new key/value pair between the key/value pairs to the right and left of |
939 | /// this edge. This method splits the node if there isn't enough room. | |
940 | /// | |
941 | /// The returned pointer points to the inserted value. | |
3dfed10e | 942 | fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) { |
9cc50fc6 | 943 | if self.node.len() < CAPACITY { |
1b1a35ee | 944 | let val_ptr = self.insert_fit(key, val); |
74b04a01 | 945 | let kv = unsafe { Handle::new_kv(self.node, self.idx) }; |
1b1a35ee | 946 | (InsertResult::Fit(kv), val_ptr) |
9cc50fc6 | 947 | } else { |
3dfed10e XL |
948 | let (middle_kv_idx, insertion) = splitpoint(self.idx); |
949 | let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; | |
9cc50fc6 | 950 | let (mut left, k, v, mut right) = middle.split(); |
1b1a35ee | 951 | let mut insertion_edge = match insertion { |
3dfed10e | 952 | InsertionPlace::Left(insert_idx) => unsafe { |
1b1a35ee | 953 | Handle::new_edge(left.reborrow_mut(), insert_idx) |
3dfed10e XL |
954 | }, |
955 | InsertionPlace::Right(insert_idx) => unsafe { | |
9cc50fc6 | 956 | Handle::new_edge( |
3dfed10e XL |
957 | right.node_as_mut().cast_unchecked::<marker::Leaf>(), |
958 | insert_idx, | |
dfeec247 | 959 | ) |
3dfed10e | 960 | }, |
9cc50fc6 | 961 | }; |
1b1a35ee XL |
962 | let val_ptr = insertion_edge.insert_fit(key, val); |
963 | (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), val_ptr) | |
1a4d82fc JJ |
964 | } |
965 | } | |
966 | } | |
967 | ||
9cc50fc6 | 968 | impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { |
a7813a04 XL |
969 | /// Fixes the parent pointer and index in the child node below this edge. This is useful |
970 | /// when the ordering of edges has been changed, such as in the various `insert` methods. | |
9cc50fc6 SL |
971 | fn correct_parent_link(mut self) { |
972 | let idx = self.idx as u16; | |
1b1a35ee | 973 | let ptr = NonNull::new(self.node.as_internal_mut()); |
9cc50fc6 | 974 | let mut child = self.descend(); |
1b1a35ee XL |
975 | child.as_leaf_mut().parent = ptr; |
976 | child.as_leaf_mut().parent_idx.write(idx); | |
9cc50fc6 | 977 | } |
1b1a35ee | 978 | } |
1a4d82fc | 979 | |
1b1a35ee | 980 | impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { |
a7813a04 XL |
981 | /// Inserts a new key/value pair and an edge that will go to the right of that new pair |
982 | /// between this edge and the key/value pair to the right of this edge. This method assumes | |
983 | /// that there is enough space in the node for the new pair to fit. | |
9cc50fc6 | 984 | fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) { |
9cc50fc6 | 985 | debug_assert!(edge.height == self.node.height - 1); |
1a4d82fc | 986 | |
9cc50fc6 | 987 | unsafe { |
1b1a35ee | 988 | slice_insert(self.node.edges_mut(), self.idx + 1, edge.node); |
3dfed10e | 989 | self.leafy_insert_fit(key, val); |
9cc50fc6 | 990 | |
1b1a35ee | 991 | self.node.correct_childrens_parent_links((self.idx + 1)..=self.node.len()); |
9cc50fc6 SL |
992 | } |
993 | } | |
1a4d82fc | 994 | |
a7813a04 XL |
995 | /// Inserts a new key/value pair and an edge that will go to the right of that new pair |
996 | /// between this edge and the key/value pair to the right of this edge. This method splits | |
997 | /// the node if there isn't enough room. | |
3dfed10e | 998 | fn insert( |
dfeec247 XL |
999 | mut self, |
1000 | key: K, | |
1001 | val: V, | |
1002 | edge: Root<K, V>, | |
1003 | ) -> InsertResult<'a, K, V, marker::Internal> { | |
74b04a01 | 1004 | assert!(edge.height == self.node.height - 1); |
1a4d82fc | 1005 | |
9cc50fc6 SL |
1006 | if self.node.len() < CAPACITY { |
1007 | self.insert_fit(key, val, edge); | |
74b04a01 XL |
1008 | let kv = unsafe { Handle::new_kv(self.node, self.idx) }; |
1009 | InsertResult::Fit(kv) | |
9cc50fc6 | 1010 | } else { |
3dfed10e XL |
1011 | let (middle_kv_idx, insertion) = splitpoint(self.idx); |
1012 | let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; | |
9cc50fc6 | 1013 | let (mut left, k, v, mut right) = middle.split(); |
3dfed10e XL |
1014 | match insertion { |
1015 | InsertionPlace::Left(insert_idx) => unsafe { | |
1016 | Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val, edge); | |
1017 | }, | |
1018 | InsertionPlace::Right(insert_idx) => unsafe { | |
9cc50fc6 | 1019 | Handle::new_edge( |
3dfed10e XL |
1020 | right.node_as_mut().cast_unchecked::<marker::Internal>(), |
1021 | insert_idx, | |
dfeec247 XL |
1022 | ) |
1023 | .insert_fit(key, val, edge); | |
3dfed10e | 1024 | }, |
9cc50fc6 | 1025 | } |
3dfed10e XL |
1026 | InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }) |
1027 | } | |
1028 | } | |
1029 | } | |
1030 | ||
1b1a35ee | 1031 | impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { |
3dfed10e XL |
1032 | /// Inserts a new key/value pair between the key/value pairs to the right and left of |
1033 | /// this edge. This method splits the node if there isn't enough room, and tries to | |
1034 | /// insert the split off portion into the parent node recursively, until the root is reached. | |
1035 | /// | |
1036 | /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor. | |
1037 | /// If the returned result is a `Split`, the `left` field will be the root node. | |
1038 | /// The returned pointer points to the inserted value. | |
1039 | pub fn insert_recursing( | |
1040 | self, | |
1041 | key: K, | |
1042 | value: V, | |
1043 | ) -> (InsertResult<'a, K, V, marker::LeafOrInternal>, *mut V) { | |
1044 | let (mut split, val_ptr) = match self.insert(key, value) { | |
1045 | (InsertResult::Fit(handle), ptr) => { | |
1046 | return (InsertResult::Fit(handle.forget_node_type()), ptr); | |
1047 | } | |
1048 | (InsertResult::Split(split), val_ptr) => (split, val_ptr), | |
1049 | }; | |
1050 | ||
1051 | loop { | |
1052 | split = match split.left.ascend() { | |
1053 | Ok(parent) => match parent.insert(split.k, split.v, split.right) { | |
1054 | InsertResult::Fit(handle) => { | |
1055 | return (InsertResult::Fit(handle.forget_node_type()), val_ptr); | |
1056 | } | |
1057 | InsertResult::Split(split) => split, | |
1058 | }, | |
1059 | Err(root) => { | |
1060 | return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr); | |
1061 | } | |
1062 | }; | |
9cc50fc6 SL |
1063 | } |
1064 | } | |
1a4d82fc JJ |
1065 | } |
1066 | ||
dfeec247 | 1067 | impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> { |
a7813a04 XL |
1068 | /// Finds the node pointed to by this edge. |
1069 | /// | |
1070 | /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should | |
1071 | /// both, upon success, do nothing. | |
9cc50fc6 | 1072 | pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
1b1a35ee XL |
1073 | // We need to use raw pointers to nodes because, if BorrowType is |
1074 | // marker::ValMut, there might be outstanding mutable references to | |
1075 | // values that we must not invalidate. There's no worry accessing the | |
1076 | // height field because that value is copied. Beware that, once the | |
1077 | // node pointer is dereferenced, we access the edges array with a | |
1078 | // reference (Rust issue #73987) and invalidate any other references | |
1079 | // to or inside the array, should any be around. | |
1080 | let internal_node = self.node.as_internal_ptr(); | |
9cc50fc6 SL |
1081 | NodeRef { |
1082 | height: self.node.height - 1, | |
1b1a35ee | 1083 | node: unsafe { (&*(*internal_node).edges.get_unchecked(self.idx).as_ptr()).as_ptr() }, |
dfeec247 | 1084 | _marker: PhantomData, |
9cc50fc6 SL |
1085 | } |
1086 | } | |
1a4d82fc JJ |
1087 | } |
1088 | ||
dfeec247 | 1089 | impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> { |
9cc50fc6 | 1090 | pub fn into_kv(self) -> (&'a K, &'a V) { |
1b1a35ee | 1091 | (unsafe { self.node.into_key_at(self.idx) }, unsafe { self.node.into_val_at(self.idx) }) |
1a4d82fc | 1092 | } |
9cc50fc6 | 1093 | } |
1a4d82fc | 1094 | |
dfeec247 | 1095 | impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { |
3dfed10e | 1096 | pub fn into_key_mut(self) -> &'a mut K { |
1b1a35ee | 1097 | unsafe { self.node.into_key_mut_at(self.idx) } |
3dfed10e XL |
1098 | } |
1099 | ||
1100 | pub fn into_val_mut(self) -> &'a mut V { | |
1b1a35ee | 1101 | unsafe { self.node.into_val_mut_at(self.idx) } |
3dfed10e | 1102 | } |
1b1a35ee | 1103 | } |
3dfed10e | 1104 | |
1b1a35ee XL |
1105 | impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> { |
1106 | pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) { | |
1107 | unsafe { self.node.into_key_val_mut_at(self.idx) } | |
1a4d82fc | 1108 | } |
9cc50fc6 | 1109 | } |
1a4d82fc | 1110 | |
1b1a35ee | 1111 | impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { |
9cc50fc6 | 1112 | pub fn kv_mut(&mut self) -> (&mut K, &mut V) { |
1b1a35ee XL |
1113 | // We cannot call into_key_mut_at and into_val_mut_at, because calling the second one |
1114 | // invalidates the reference returned by the first. | |
1115 | let leaf = self.node.as_leaf_mut(); | |
1116 | let key = unsafe { leaf.keys.get_unchecked_mut(self.idx).assume_init_mut() }; | |
1117 | let val = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }; | |
1118 | (key, val) | |
1a4d82fc JJ |
1119 | } |
1120 | } | |
1121 | ||
1b1a35ee | 1122 | impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { |
3dfed10e XL |
1123 | /// Helps implementations of `split` for a particular `NodeType`, |
1124 | /// by taking care of leaf data. | |
1125 | fn leafy_split(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V, usize) { | |
9cc50fc6 | 1126 | unsafe { |
1b1a35ee XL |
1127 | let k = ptr::read(self.node.key_at(self.idx)); |
1128 | let v = ptr::read(self.node.val_at(self.idx)); | |
9cc50fc6 SL |
1129 | |
1130 | let new_len = self.node.len() - self.idx - 1; | |
1131 | ||
1132 | ptr::copy_nonoverlapping( | |
1b1a35ee XL |
1133 | self.node.key_at(self.idx + 1), |
1134 | MaybeUninit::slice_as_mut_ptr(&mut new_node.keys), | |
dfeec247 | 1135 | new_len, |
9cc50fc6 SL |
1136 | ); |
1137 | ptr::copy_nonoverlapping( | |
1b1a35ee XL |
1138 | self.node.val_at(self.idx + 1), |
1139 | MaybeUninit::slice_as_mut_ptr(&mut new_node.vals), | |
dfeec247 | 1140 | new_len, |
9cc50fc6 SL |
1141 | ); |
1142 | ||
1b1a35ee | 1143 | self.node.as_leaf_mut().len = self.idx as u16; |
9cc50fc6 | 1144 | new_node.len = new_len as u16; |
3dfed10e XL |
1145 | (k, v, new_len) |
1146 | } | |
1147 | } | |
1148 | } | |
1149 | ||
1b1a35ee | 1150 | impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { |
3dfed10e XL |
1151 | /// Splits the underlying node into three parts: |
1152 | /// | |
1153 | /// - The node is truncated to only contain the key/value pairs to the right of | |
1154 | /// this handle. | |
1b1a35ee | 1155 | /// - The key and value pointed to by this handle are extracted. |
3dfed10e XL |
1156 | /// - All the key/value pairs to the right of this handle are put into a newly |
1157 | /// allocated node. | |
1158 | pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) { | |
1159 | unsafe { | |
1160 | let mut new_node = Box::new(LeafNode::new()); | |
1161 | ||
1162 | let (k, v, _) = self.leafy_split(&mut new_node); | |
9cc50fc6 | 1163 | |
dfeec247 | 1164 | (self.node, k, v, Root { node: BoxedNode::from_leaf(new_node), height: 0 }) |
9cc50fc6 SL |
1165 | } |
1166 | } | |
1a4d82fc | 1167 | |
dfeec247 | 1168 | /// Removes the key/value pair pointed to by this handle and returns it, along with the edge |
3dfed10e | 1169 | /// that the key/value pair collapsed into. |
dfeec247 XL |
1170 | pub fn remove( |
1171 | mut self, | |
3dfed10e | 1172 | ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) { |
9cc50fc6 SL |
1173 | unsafe { |
1174 | let k = slice_remove(self.node.keys_mut(), self.idx); | |
1175 | let v = slice_remove(self.node.vals_mut(), self.idx); | |
1b1a35ee | 1176 | self.node.as_leaf_mut().len -= 1; |
3dfed10e | 1177 | ((k, v), self.left_edge()) |
9cc50fc6 | 1178 | } |
1a4d82fc JJ |
1179 | } |
1180 | } | |
1181 | ||
9cc50fc6 | 1182 | impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> { |
1b1a35ee XL |
1183 | /// Returns `true` if it is valid to call `.merge()`, i.e., whether there is enough room in |
1184 | /// a node to hold the combination of the nodes to the left and right of this handle along | |
1185 | /// with the key/value pair at this handle. | |
1186 | pub fn can_merge(&self) -> bool { | |
1187 | (self.reborrow().left_edge().descend().len() | |
1188 | + self.reborrow().right_edge().descend().len() | |
1189 | + 1) | |
1190 | <= CAPACITY | |
1191 | } | |
1192 | } | |
1193 | ||
1194 | impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> { | |
a7813a04 XL |
1195 | /// Splits the underlying node into three parts: |
1196 | /// | |
1197 | /// - The node is truncated to only contain the edges and key/value pairs to the | |
1198 | /// right of this handle. | |
1b1a35ee | 1199 | /// - The key and value pointed to by this handle are extracted. |
a7813a04 XL |
1200 | /// - All the edges and key/value pairs to the right of this handle are put into |
1201 | /// a newly allocated node. | |
dfeec247 | 1202 | pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) { |
9cc50fc6 SL |
1203 | unsafe { |
1204 | let mut new_node = Box::new(InternalNode::new()); | |
1205 | ||
3dfed10e | 1206 | let (k, v, new_len) = self.leafy_split(&mut new_node.data); |
9cc50fc6 | 1207 | let height = self.node.height; |
1b1a35ee | 1208 | let old_node = &*self.node.as_internal_ptr(); |
9cc50fc6 | 1209 | |
9cc50fc6 | 1210 | ptr::copy_nonoverlapping( |
1b1a35ee | 1211 | old_node.edges.as_ptr().add(self.idx + 1), |
9cc50fc6 | 1212 | new_node.edges.as_mut_ptr(), |
dfeec247 | 1213 | new_len + 1, |
9cc50fc6 SL |
1214 | ); |
1215 | ||
dfeec247 | 1216 | let mut new_root = Root { node: BoxedNode::from_internal(new_node), height }; |
1a4d82fc | 1217 | |
1b1a35ee | 1218 | new_root.node_as_mut().cast_unchecked().correct_childrens_parent_links(0..=new_len); |
1a4d82fc | 1219 | |
dfeec247 | 1220 | (self.node, k, v, new_root) |
9cc50fc6 SL |
1221 | } |
1222 | } | |
1a4d82fc | 1223 | |
a7813a04 XL |
1224 | /// Combines the node immediately to the left of this handle, the key/value pair pointed |
1225 | /// to by this handle, and the node immediately to the right of this handle into one new | |
1226 | /// child of the underlying node, returning an edge referencing that new child. | |
1227 | /// | |
3dfed10e | 1228 | /// Panics unless this edge `.can_merge()`. |
dfeec247 XL |
1229 | pub fn merge( |
1230 | mut self, | |
1231 | ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { | |
9cc50fc6 SL |
1232 | let self1 = unsafe { ptr::read(&self) }; |
1233 | let self2 = unsafe { ptr::read(&self) }; | |
1234 | let mut left_node = self1.left_edge().descend(); | |
1235 | let left_len = left_node.len(); | |
3dfed10e | 1236 | let right_node = self2.right_edge().descend(); |
9cc50fc6 SL |
1237 | let right_len = right_node.len(); |
1238 | ||
74b04a01 | 1239 | assert!(left_len + right_len < CAPACITY); |
1a4d82fc | 1240 | |
9cc50fc6 | 1241 | unsafe { |
dfeec247 XL |
1242 | ptr::write( |
1243 | left_node.keys_mut().get_unchecked_mut(left_len), | |
1244 | slice_remove(self.node.keys_mut(), self.idx), | |
1245 | ); | |
9cc50fc6 | 1246 | ptr::copy_nonoverlapping( |
1b1a35ee | 1247 | right_node.key_at(0), |
b7449926 | 1248 | left_node.keys_mut().as_mut_ptr().add(left_len + 1), |
dfeec247 XL |
1249 | right_len, |
1250 | ); | |
1251 | ptr::write( | |
1252 | left_node.vals_mut().get_unchecked_mut(left_len), | |
1253 | slice_remove(self.node.vals_mut(), self.idx), | |
9cc50fc6 | 1254 | ); |
9cc50fc6 | 1255 | ptr::copy_nonoverlapping( |
1b1a35ee | 1256 | right_node.val_at(0), |
b7449926 | 1257 | left_node.vals_mut().as_mut_ptr().add(left_len + 1), |
dfeec247 | 1258 | right_len, |
9cc50fc6 SL |
1259 | ); |
1260 | ||
1b1a35ee XL |
1261 | slice_remove(&mut self.node.edges_mut(), self.idx + 1); |
1262 | let self_len = self.node.len(); | |
1263 | self.node.correct_childrens_parent_links(self.idx + 1..self_len); | |
1264 | self.node.as_leaf_mut().len -= 1; | |
9cc50fc6 | 1265 | |
1b1a35ee | 1266 | left_node.as_leaf_mut().len += right_len as u16 + 1; |
7453a54e | 1267 | |
3dfed10e XL |
1268 | if self.node.height > 1 { |
1269 | // SAFETY: the height of the nodes being merged is one below the height | |
1270 | // of the node of this edge, thus above zero, so they are internal. | |
1b1a35ee XL |
1271 | let mut left_node = left_node.cast_unchecked::<marker::Internal>(); |
1272 | let right_node = right_node.cast_unchecked::<marker::Internal>(); | |
9cc50fc6 | 1273 | ptr::copy_nonoverlapping( |
1b1a35ee XL |
1274 | right_node.edge_at(0), |
1275 | left_node.edges_mut().as_mut_ptr().add(left_len + 1), | |
dfeec247 | 1276 | right_len + 1, |
9cc50fc6 SL |
1277 | ); |
1278 | ||
1b1a35ee | 1279 | left_node.correct_childrens_parent_links(left_len + 1..=left_len + 1 + right_len); |
1a4d82fc | 1280 | |
3dfed10e | 1281 | Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>()); |
9cc50fc6 | 1282 | } else { |
3dfed10e XL |
1283 | Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>()); |
1284 | } | |
85aaf69f | 1285 | |
9cc50fc6 SL |
1286 | Handle::new_edge(self.node, self.idx) |
1287 | } | |
85aaf69f | 1288 | } |
a7813a04 | 1289 | |
dfeec247 | 1290 | /// This removes a key/value pair from the left child and places it in the key/value storage |
a7813a04 XL |
1291 | /// pointed to by this handle while pushing the old key/value pair of this handle into the right |
1292 | /// child. | |
1293 | pub fn steal_left(&mut self) { | |
1294 | unsafe { | |
1295 | let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop(); | |
1296 | ||
3dfed10e XL |
1297 | let k = mem::replace(self.kv_mut().0, k); |
1298 | let v = mem::replace(self.kv_mut().1, v); | |
a7813a04 XL |
1299 | |
1300 | match self.reborrow_mut().right_edge().descend().force() { | |
1301 | ForceResult::Leaf(mut leaf) => leaf.push_front(k, v), | |
dfeec247 | 1302 | ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()), |
a7813a04 XL |
1303 | } |
1304 | } | |
1305 | } | |
1306 | ||
dfeec247 | 1307 | /// This removes a key/value pair from the right child and places it in the key/value storage |
a7813a04 XL |
1308 | /// pointed to by this handle while pushing the old key/value pair of this handle into the left |
1309 | /// child. | |
1310 | pub fn steal_right(&mut self) { | |
1311 | unsafe { | |
1312 | let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front(); | |
1313 | ||
3dfed10e XL |
1314 | let k = mem::replace(self.kv_mut().0, k); |
1315 | let v = mem::replace(self.kv_mut().1, v); | |
a7813a04 XL |
1316 | |
1317 | match self.reborrow_mut().left_edge().descend().force() { | |
1318 | ForceResult::Leaf(mut leaf) => leaf.push(k, v), | |
dfeec247 | 1319 | ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()), |
a7813a04 XL |
1320 | } |
1321 | } | |
1322 | } | |
1323 | ||
1324 | /// This does stealing similar to `steal_left` but steals multiple elements at once. | |
3157f602 | 1325 | pub fn bulk_steal_left(&mut self, count: usize) { |
a7813a04 | 1326 | unsafe { |
3157f602 XL |
1327 | let mut left_node = ptr::read(self).left_edge().descend(); |
1328 | let left_len = left_node.len(); | |
1329 | let mut right_node = ptr::read(self).right_edge().descend(); | |
1330 | let right_len = right_node.len(); | |
a7813a04 XL |
1331 | |
1332 | // Make sure that we may steal safely. | |
74b04a01 XL |
1333 | assert!(right_len + count <= CAPACITY); |
1334 | assert!(left_len >= count); | |
3157f602 XL |
1335 | |
1336 | let new_left_len = left_len - count; | |
1337 | ||
1338 | // Move data. | |
1339 | { | |
1340 | let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); | |
1341 | let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); | |
1342 | let parent_kv = { | |
3dfed10e | 1343 | let kv = self.kv_mut(); |
3157f602 XL |
1344 | (kv.0 as *mut K, kv.1 as *mut V) |
1345 | }; | |
1346 | ||
1347 | // Make room for stolen elements in the right child. | |
dfeec247 XL |
1348 | ptr::copy(right_kv.0, right_kv.0.add(count), right_len); |
1349 | ptr::copy(right_kv.1, right_kv.1.add(count), right_len); | |
3157f602 XL |
1350 | |
1351 | // Move elements from the left child to the right one. | |
1352 | move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1); | |
1353 | ||
1354 | // Move parent's key/value pair to the right child. | |
1355 | move_kv(parent_kv, 0, right_kv, count - 1, 1); | |
1356 | ||
1357 | // Move the left-most stolen pair to the parent. | |
1358 | move_kv(left_kv, new_left_len, parent_kv, 0, 1); | |
a7813a04 XL |
1359 | } |
1360 | ||
1b1a35ee XL |
1361 | left_node.as_leaf_mut().len -= count as u16; |
1362 | right_node.as_leaf_mut().len += count as u16; | |
3157f602 XL |
1363 | |
1364 | match (left_node.force(), right_node.force()) { | |
1365 | (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { | |
1366 | // Make room for stolen edges. | |
1367 | let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); | |
dfeec247 | 1368 | ptr::copy(right_edges, right_edges.add(count), right_len + 1); |
1b1a35ee | 1369 | right.correct_childrens_parent_links(count..count + right_len + 1); |
3157f602 XL |
1370 | |
1371 | move_edges(left, new_left_len + 1, right, 0, count); | |
dfeec247 XL |
1372 | } |
1373 | (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} | |
1b1a35ee | 1374 | _ => unreachable!(), |
a7813a04 | 1375 | } |
3157f602 XL |
1376 | } |
1377 | } | |
a7813a04 | 1378 | |
3157f602 XL |
1379 | /// The symmetric clone of `bulk_steal_left`. |
1380 | pub fn bulk_steal_right(&mut self, count: usize) { | |
1381 | unsafe { | |
1382 | let mut left_node = ptr::read(self).left_edge().descend(); | |
1383 | let left_len = left_node.len(); | |
1384 | let mut right_node = ptr::read(self).right_edge().descend(); | |
1385 | let right_len = right_node.len(); | |
1386 | ||
1387 | // Make sure that we may steal safely. | |
74b04a01 XL |
1388 | assert!(left_len + count <= CAPACITY); |
1389 | assert!(right_len >= count); | |
3157f602 XL |
1390 | |
1391 | let new_right_len = right_len - count; | |
1392 | ||
1393 | // Move data. | |
1394 | { | |
1395 | let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); | |
1396 | let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); | |
1397 | let parent_kv = { | |
3dfed10e | 1398 | let kv = self.kv_mut(); |
3157f602 XL |
1399 | (kv.0 as *mut K, kv.1 as *mut V) |
1400 | }; | |
1401 | ||
1402 | // Move parent's key/value pair to the left child. | |
1403 | move_kv(parent_kv, 0, left_kv, left_len, 1); | |
1404 | ||
1405 | // Move elements from the right child to the left one. | |
1406 | move_kv(right_kv, 0, left_kv, left_len + 1, count - 1); | |
1407 | ||
1408 | // Move the right-most stolen pair to the parent. | |
1409 | move_kv(right_kv, count - 1, parent_kv, 0, 1); | |
1410 | ||
1411 | // Fix right indexing | |
dfeec247 XL |
1412 | ptr::copy(right_kv.0.add(count), right_kv.0, new_right_len); |
1413 | ptr::copy(right_kv.1.add(count), right_kv.1, new_right_len); | |
3157f602 XL |
1414 | } |
1415 | ||
1b1a35ee XL |
1416 | left_node.as_leaf_mut().len += count as u16; |
1417 | right_node.as_leaf_mut().len -= count as u16; | |
3157f602 XL |
1418 | |
1419 | match (left_node.force(), right_node.force()) { | |
1420 | (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { | |
1421 | move_edges(right.reborrow_mut(), 0, left, left_len + 1, count); | |
1422 | ||
1423 | // Fix right indexing. | |
1424 | let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); | |
dfeec247 | 1425 | ptr::copy(right_edges.add(count), right_edges, new_right_len + 1); |
1b1a35ee | 1426 | right.correct_childrens_parent_links(0..=new_right_len); |
dfeec247 XL |
1427 | } |
1428 | (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} | |
1b1a35ee | 1429 | _ => unreachable!(), |
a7813a04 XL |
1430 | } |
1431 | } | |
1432 | } | |
85aaf69f SL |
1433 | } |
1434 | ||
3157f602 | 1435 | unsafe fn move_kv<K, V>( |
dfeec247 XL |
1436 | source: (*mut K, *mut V), |
1437 | source_offset: usize, | |
1438 | dest: (*mut K, *mut V), | |
1439 | dest_offset: usize, | |
1440 | count: usize, | |
1441 | ) { | |
f035d41b XL |
1442 | unsafe { |
1443 | ptr::copy_nonoverlapping(source.0.add(source_offset), dest.0.add(dest_offset), count); | |
1444 | ptr::copy_nonoverlapping(source.1.add(source_offset), dest.1.add(dest_offset), count); | |
1445 | } | |
3157f602 XL |
1446 | } |
1447 | ||
1448 | // Source and destination must have the same height. | |
1449 | unsafe fn move_edges<K, V>( | |
dfeec247 XL |
1450 | mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, |
1451 | source_offset: usize, | |
1452 | mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, | |
1453 | dest_offset: usize, | |
1454 | count: usize, | |
1455 | ) { | |
1b1a35ee | 1456 | let source_ptr = source.as_internal().edges.as_ptr(); |
3157f602 | 1457 | let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr(); |
f035d41b XL |
1458 | unsafe { |
1459 | ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr.add(dest_offset), count); | |
1b1a35ee | 1460 | dest.correct_childrens_parent_links(dest_offset..dest_offset + count); |
f035d41b | 1461 | } |
3157f602 XL |
1462 | } |
1463 | ||
3dfed10e XL |
1464 | impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> { |
1465 | /// Removes any static information asserting that this node is a `Leaf` node. | |
1466 | pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { | |
1b1a35ee | 1467 | NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
3dfed10e XL |
1468 | } |
1469 | } | |
1470 | ||
1471 | impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { | |
1472 | /// Removes any static information asserting that this node is an `Internal` node. | |
1473 | pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { | |
1b1a35ee | 1474 | NodeRef { height: self.height, node: self.node, _marker: PhantomData } |
3dfed10e XL |
1475 | } |
1476 | } | |
1477 | ||
74b04a01 XL |
1478 | impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { |
1479 | pub fn forget_node_type( | |
1480 | self, | |
1481 | ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> { | |
1482 | unsafe { Handle::new_edge(self.node.forget_type(), self.idx) } | |
1483 | } | |
1484 | } | |
1485 | ||
1486 | impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> { | |
1487 | pub fn forget_node_type( | |
1488 | self, | |
1489 | ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> { | |
1490 | unsafe { Handle::new_edge(self.node.forget_type(), self.idx) } | |
1491 | } | |
1492 | } | |
1493 | ||
1494 | impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> { | |
1495 | pub fn forget_node_type( | |
1496 | self, | |
1497 | ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> { | |
1498 | unsafe { Handle::new_kv(self.node.forget_type(), self.idx) } | |
1499 | } | |
1500 | } | |
1501 | ||
3dfed10e XL |
1502 | impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> { |
1503 | pub fn forget_node_type( | |
1504 | self, | |
1505 | ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> { | |
1506 | unsafe { Handle::new_kv(self.node.forget_type(), self.idx) } | |
1507 | } | |
1508 | } | |
1509 | ||
9cc50fc6 | 1510 | impl<BorrowType, K, V, HandleType> |
dfeec247 XL |
1511 | Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> |
1512 | { | |
9fa01778 | 1513 | /// Checks whether the underlying node is an `Internal` node or a `Leaf` node. |
dfeec247 XL |
1514 | pub fn force( |
1515 | self, | |
1516 | ) -> ForceResult< | |
9cc50fc6 | 1517 | Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>, |
dfeec247 | 1518 | Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>, |
9cc50fc6 SL |
1519 | > { |
1520 | match self.node.force() { | |
dfeec247 XL |
1521 | ForceResult::Leaf(node) => { |
1522 | ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData }) | |
1523 | } | |
1524 | ForceResult::Internal(node) => { | |
1525 | ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData }) | |
1526 | } | |
9cc50fc6 | 1527 | } |
85aaf69f SL |
1528 | } |
1529 | } | |
1a4d82fc | 1530 | |
3157f602 XL |
1531 | impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> { |
1532 | /// Move the suffix after `self` from one node to another one. `right` must be empty. | |
1533 | /// The first edge of `right` remains unchanged. | |
dfeec247 XL |
1534 | pub fn move_suffix( |
1535 | &mut self, | |
1536 | right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, | |
1537 | ) { | |
3157f602 XL |
1538 | unsafe { |
1539 | let left_new_len = self.idx; | |
1540 | let mut left_node = self.reborrow_mut().into_node(); | |
1541 | ||
1542 | let right_new_len = left_node.len() - left_new_len; | |
1543 | let mut right_node = right.reborrow_mut(); | |
1544 | ||
74b04a01 XL |
1545 | assert!(right_node.len() == 0); |
1546 | assert!(left_node.height == right_node.height); | |
3157f602 | 1547 | |
74b04a01 XL |
1548 | if right_new_len > 0 { |
1549 | let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); | |
1550 | let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); | |
3157f602 | 1551 | |
74b04a01 | 1552 | move_kv(left_kv, left_new_len, right_kv, 0, right_new_len); |
3157f602 | 1553 | |
1b1a35ee XL |
1554 | left_node.as_leaf_mut().len = left_new_len as u16; |
1555 | right_node.as_leaf_mut().len = right_new_len as u16; | |
3157f602 | 1556 | |
74b04a01 XL |
1557 | match (left_node.force(), right_node.force()) { |
1558 | (ForceResult::Internal(left), ForceResult::Internal(right)) => { | |
1559 | move_edges(left, left_new_len + 1, right, 1, right_new_len); | |
1560 | } | |
1561 | (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} | |
1b1a35ee | 1562 | _ => unreachable!(), |
dfeec247 | 1563 | } |
3157f602 XL |
1564 | } |
1565 | } | |
1566 | } | |
1567 | } | |
1568 | ||
9cc50fc6 SL |
1569 | pub enum ForceResult<Leaf, Internal> { |
1570 | Leaf(Leaf), | |
dfeec247 | 1571 | Internal(Internal), |
9cc50fc6 | 1572 | } |
85aaf69f | 1573 | |
3dfed10e XL |
1574 | /// Result of insertion, when a node needed to expand beyond its capacity. |
1575 | /// Does not distinguish between `Leaf` and `Internal` because `Root` doesn't. | |
1576 | pub struct SplitResult<'a, K, V> { | |
1577 | // Altered node in existing tree with elements and edges that belong to the left of `k`. | |
1578 | pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, | |
1579 | // Some key and value split off, to be inserted elsewhere. | |
1580 | pub k: K, | |
1581 | pub v: V, | |
1582 | // Owned, unattached, new node with elements and edges that belong to the right of `k`. | |
1583 | pub right: Root<K, V>, | |
1584 | } | |
1585 | ||
9cc50fc6 SL |
1586 | pub enum InsertResult<'a, K, V, Type> { |
1587 | Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>), | |
3dfed10e | 1588 | Split(SplitResult<'a, K, V>), |
1a4d82fc JJ |
1589 | } |
1590 | ||
9cc50fc6 SL |
1591 | pub mod marker { |
1592 | use core::marker::PhantomData; | |
1a4d82fc | 1593 | |
dfeec247 XL |
1594 | pub enum Leaf {} |
1595 | pub enum Internal {} | |
1596 | pub enum LeafOrInternal {} | |
85aaf69f | 1597 | |
dfeec247 | 1598 | pub enum Owned {} |
9cc50fc6 SL |
1599 | pub struct Immut<'a>(PhantomData<&'a ()>); |
1600 | pub struct Mut<'a>(PhantomData<&'a mut ()>); | |
1b1a35ee | 1601 | pub struct ValMut<'a>(PhantomData<&'a mut ()>); |
85aaf69f | 1602 | |
dfeec247 XL |
1603 | pub enum KV {} |
1604 | pub enum Edge {} | |
1a4d82fc | 1605 | } |
85aaf69f | 1606 | |
9cc50fc6 | 1607 | unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) { |
f035d41b XL |
1608 | unsafe { |
1609 | ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx); | |
1610 | ptr::write(slice.get_unchecked_mut(idx), val); | |
1611 | } | |
9cc50fc6 SL |
1612 | } |
1613 | ||
1614 | unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T { | |
f035d41b XL |
1615 | unsafe { |
1616 | let ret = ptr::read(slice.get_unchecked(idx)); | |
1617 | ptr::copy(slice.as_ptr().add(idx + 1), slice.as_mut_ptr().add(idx), slice.len() - idx - 1); | |
1618 | ret | |
1619 | } | |
9cc50fc6 | 1620 | } |
3dfed10e XL |
1621 | |
1622 | #[cfg(test)] | |
1623 | mod tests; |