]>
Commit | Line | Data |
---|---|---|
1b1a35ee | 1 | use core::borrow::Borrow; |
1b1a35ee | 2 | use core::ops::RangeBounds; |
74b04a01 XL |
3 | use core::ptr; |
4 | ||
5 | use super::node::{marker, ForceResult::*, Handle, NodeRef}; | |
74b04a01 | 6 | |
136023e0 | 7 | // `front` and `back` are always both `None` or both `Some`. |
6a06907d | 8 | pub struct LeafRange<BorrowType, K, V> { |
136023e0 XL |
9 | front: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>, |
10 | back: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>, | |
11 | } | |
12 | ||
13 | impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> { | |
14 | fn clone(&self) -> Self { | |
15 | LeafRange { front: self.front.clone(), back: self.back.clone() } | |
16 | } | |
6a06907d | 17 | } |
1b1a35ee | 18 | |
6a06907d XL |
19 | impl<BorrowType, K, V> LeafRange<BorrowType, K, V> { |
20 | pub fn none() -> Self { | |
21 | LeafRange { front: None, back: None } | |
22 | } | |
1b1a35ee | 23 | |
136023e0 | 24 | fn is_empty(&self) -> bool { |
6a06907d XL |
25 | self.front == self.back |
26 | } | |
1b1a35ee | 27 | |
6a06907d XL |
28 | /// Temporarily takes out another, immutable equivalent of the same range. |
29 | pub fn reborrow(&self) -> LeafRange<marker::Immut<'_>, K, V> { | |
30 | LeafRange { | |
31 | front: self.front.as_ref().map(|f| f.reborrow()), | |
32 | back: self.back.as_ref().map(|b| b.reborrow()), | |
1b1a35ee | 33 | } |
6a06907d XL |
34 | } |
35 | } | |
36 | ||
136023e0 XL |
37 | impl<'a, K, V> LeafRange<marker::Immut<'a>, K, V> { |
38 | #[inline] | |
39 | pub fn next_checked(&mut self) -> Option<(&'a K, &'a V)> { | |
40 | if self.is_empty() { None } else { Some(unsafe { self.next_unchecked() }) } | |
41 | } | |
42 | ||
43 | #[inline] | |
44 | pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a V)> { | |
45 | if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) } | |
46 | } | |
47 | ||
48 | #[inline] | |
49 | pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { | |
50 | unsafe { self.front.as_mut().unwrap().next_unchecked() } | |
51 | } | |
52 | ||
53 | #[inline] | |
54 | pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) { | |
55 | unsafe { self.back.as_mut().unwrap().next_back_unchecked() } | |
56 | } | |
57 | } | |
58 | ||
59 | impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> { | |
60 | #[inline] | |
61 | pub fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> { | |
62 | if self.is_empty() { None } else { Some(unsafe { self.next_unchecked() }) } | |
63 | } | |
64 | ||
65 | #[inline] | |
66 | pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> { | |
67 | if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) } | |
68 | } | |
69 | ||
70 | #[inline] | |
71 | pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) { | |
72 | unsafe { self.front.as_mut().unwrap().next_unchecked() } | |
73 | } | |
74 | ||
75 | #[inline] | |
76 | pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) { | |
77 | unsafe { self.back.as_mut().unwrap().next_back_unchecked() } | |
78 | } | |
79 | } | |
80 | ||
81 | impl<K, V> LeafRange<marker::Dying, K, V> { | |
82 | #[inline] | |
83 | pub fn take_front( | |
84 | &mut self, | |
85 | ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge>> { | |
86 | self.front.take() | |
87 | } | |
88 | ||
89 | #[inline] | |
90 | pub unsafe fn deallocating_next_unchecked( | |
91 | &mut self, | |
92 | ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> { | |
93 | debug_assert!(self.front.is_some()); | |
94 | let front = self.front.as_mut().unwrap(); | |
95 | unsafe { front.deallocating_next_unchecked() } | |
96 | } | |
97 | ||
98 | #[inline] | |
99 | pub unsafe fn deallocating_next_back_unchecked( | |
100 | &mut self, | |
101 | ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> { | |
102 | debug_assert!(self.back.is_some()); | |
103 | let back = self.back.as_mut().unwrap(); | |
104 | unsafe { back.deallocating_next_back_unchecked() } | |
105 | } | |
106 | } | |
107 | ||
6a06907d XL |
108 | impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
109 | /// Finds the distinct leaf edges delimiting a specified range in a tree. | |
cdc7bbd5 XL |
110 | /// |
111 | /// If such distinct edges exist, returns them in ascending order, meaning | |
112 | /// that a non-zero number of calls to `next_unchecked` on the `front` of | |
113 | /// the result and/or calls to `next_back_unchecked` on the `back` of the | |
114 | /// result will eventually reach the same edge. | |
115 | /// | |
116 | /// If there are no such edges, i.e., if the tree contains no key within | |
136023e0 | 117 | /// the range, returns an empty `front` and `back`. |
cdc7bbd5 | 118 | /// |
6a06907d | 119 | /// # Safety |
cdc7bbd5 XL |
120 | /// Unless `BorrowType` is `Immut`, do not use the handles to visit the same |
121 | /// KV twice. | |
6a06907d XL |
122 | unsafe fn find_leaf_edges_spanning_range<Q: ?Sized, R>( |
123 | self, | |
124 | range: R, | |
125 | ) -> LeafRange<BorrowType, K, V> | |
126 | where | |
127 | Q: Ord, | |
128 | K: Borrow<Q>, | |
129 | R: RangeBounds<Q>, | |
130 | { | |
131 | match self.search_tree_for_bifurcation(&range) { | |
132 | Err(_) => LeafRange::none(), | |
133 | Ok(( | |
134 | node, | |
135 | lower_edge_idx, | |
136 | upper_edge_idx, | |
137 | mut lower_child_bound, | |
138 | mut upper_child_bound, | |
139 | )) => { | |
140 | let mut lower_edge = unsafe { Handle::new_edge(ptr::read(&node), lower_edge_idx) }; | |
141 | let mut upper_edge = unsafe { Handle::new_edge(node, upper_edge_idx) }; | |
142 | loop { | |
143 | match (lower_edge.force(), upper_edge.force()) { | |
144 | (Leaf(f), Leaf(b)) => return LeafRange { front: Some(f), back: Some(b) }, | |
145 | (Internal(f), Internal(b)) => { | |
146 | (lower_edge, lower_child_bound) = | |
147 | f.descend().find_lower_bound_edge(lower_child_bound); | |
148 | (upper_edge, upper_child_bound) = | |
149 | b.descend().find_upper_bound_edge(upper_child_bound); | |
150 | } | |
151 | _ => unreachable!("BTreeMap has different depths"), | |
152 | } | |
153 | } | |
1b1a35ee | 154 | } |
6a06907d | 155 | } |
1b1a35ee XL |
156 | } |
157 | } | |
158 | ||
6a06907d | 159 | /// Equivalent to `(root1.first_leaf_edge(), root2.last_leaf_edge())` but more efficient. |
5869c6ff | 160 | fn full_range<BorrowType: marker::BorrowType, K, V>( |
1b1a35ee XL |
161 | root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, |
162 | root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, | |
6a06907d | 163 | ) -> LeafRange<BorrowType, K, V> { |
1b1a35ee XL |
164 | let mut min_node = root1; |
165 | let mut max_node = root2; | |
166 | loop { | |
167 | let front = min_node.first_edge(); | |
168 | let back = max_node.last_edge(); | |
169 | match (front.force(), back.force()) { | |
170 | (Leaf(f), Leaf(b)) => { | |
6a06907d | 171 | return LeafRange { front: Some(f), back: Some(b) }; |
1b1a35ee XL |
172 | } |
173 | (Internal(min_int), Internal(max_int)) => { | |
174 | min_node = min_int.descend(); | |
175 | max_node = max_int.descend(); | |
176 | } | |
177 | _ => unreachable!("BTreeMap has different depths"), | |
178 | }; | |
179 | } | |
180 | } | |
181 | ||
182 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> { | |
6a06907d | 183 | /// Finds the pair of leaf edges delimiting a specific range in a tree. |
fc512014 XL |
184 | /// |
185 | /// The result is meaningful only if the tree is ordered by key, like the tree | |
186 | /// in a `BTreeMap` is. | |
6a06907d | 187 | pub fn range_search<Q, R>(self, range: R) -> LeafRange<marker::Immut<'a>, K, V> |
1b1a35ee XL |
188 | where |
189 | Q: ?Sized + Ord, | |
190 | K: Borrow<Q>, | |
191 | R: RangeBounds<Q>, | |
192 | { | |
6a06907d XL |
193 | // SAFETY: our borrow type is immutable. |
194 | unsafe { self.find_leaf_edges_spanning_range(range) } | |
1b1a35ee XL |
195 | } |
196 | ||
6a06907d XL |
197 | /// Finds the pair of leaf edges delimiting an entire tree. |
198 | pub fn full_range(self) -> LeafRange<marker::Immut<'a>, K, V> { | |
1b1a35ee XL |
199 | full_range(self, self) |
200 | } | |
201 | } | |
202 | ||
203 | impl<'a, K: 'a, V: 'a> NodeRef<marker::ValMut<'a>, K, V, marker::LeafOrInternal> { | |
204 | /// Splits a unique reference into a pair of leaf edges delimiting a specified range. | |
205 | /// The result are non-unique references allowing (some) mutation, which must be used | |
206 | /// carefully. | |
fc512014 XL |
207 | /// |
208 | /// The result is meaningful only if the tree is ordered by key, like the tree | |
209 | /// in a `BTreeMap` is. | |
6a06907d XL |
210 | /// |
211 | /// # Safety | |
212 | /// Do not use the duplicate handles to visit the same KV twice. | |
213 | pub fn range_search<Q, R>(self, range: R) -> LeafRange<marker::ValMut<'a>, K, V> | |
1b1a35ee XL |
214 | where |
215 | Q: ?Sized + Ord, | |
216 | K: Borrow<Q>, | |
217 | R: RangeBounds<Q>, | |
218 | { | |
6a06907d | 219 | unsafe { self.find_leaf_edges_spanning_range(range) } |
1b1a35ee XL |
220 | } |
221 | ||
222 | /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree. | |
223 | /// The results are non-unique references allowing mutation (of values only), so must be used | |
224 | /// with care. | |
6a06907d | 225 | pub fn full_range(self) -> LeafRange<marker::ValMut<'a>, K, V> { |
1b1a35ee XL |
226 | // We duplicate the root NodeRef here -- we will never visit the same KV |
227 | // twice, and never end up with overlapping value references. | |
228 | let self2 = unsafe { ptr::read(&self) }; | |
229 | full_range(self, self2) | |
230 | } | |
231 | } | |
232 | ||
5869c6ff | 233 | impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> { |
1b1a35ee XL |
234 | /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree. |
235 | /// The results are non-unique references allowing massively destructive mutation, so must be | |
236 | /// used with the utmost care. | |
6a06907d | 237 | pub fn full_range(self) -> LeafRange<marker::Dying, K, V> { |
1b1a35ee XL |
238 | // We duplicate the root NodeRef here -- we will never access it in a way |
239 | // that overlaps references obtained from the root. | |
240 | let self2 = unsafe { ptr::read(&self) }; | |
241 | full_range(self, self2) | |
242 | } | |
243 | } | |
244 | ||
5869c6ff XL |
245 | impl<BorrowType: marker::BorrowType, K, V> |
246 | Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> | |
247 | { | |
74b04a01 XL |
248 | /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV |
249 | /// on the right side, which is either in the same leaf node or in an ancestor node. | |
250 | /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node. | |
251 | pub fn next_kv( | |
252 | self, | |
253 | ) -> Result< | |
254 | Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>, | |
255 | NodeRef<BorrowType, K, V, marker::LeafOrInternal>, | |
256 | > { | |
257 | let mut edge = self.forget_node_type(); | |
258 | loop { | |
259 | edge = match edge.right_kv() { | |
1b1a35ee | 260 | Ok(kv) => return Ok(kv), |
74b04a01 XL |
261 | Err(last_edge) => match last_edge.into_node().ascend() { |
262 | Ok(parent_edge) => parent_edge.forget_node_type(), | |
3dfed10e | 263 | Err(root) => return Err(root), |
74b04a01 XL |
264 | }, |
265 | } | |
266 | } | |
267 | } | |
268 | ||
269 | /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV | |
270 | /// on the left side, which is either in the same leaf node or in an ancestor node. | |
271 | /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node. | |
136023e0 | 272 | fn next_back_kv( |
74b04a01 XL |
273 | self, |
274 | ) -> Result< | |
275 | Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>, | |
276 | NodeRef<BorrowType, K, V, marker::LeafOrInternal>, | |
277 | > { | |
278 | let mut edge = self.forget_node_type(); | |
279 | loop { | |
280 | edge = match edge.left_kv() { | |
1b1a35ee | 281 | Ok(kv) => return Ok(kv), |
74b04a01 XL |
282 | Err(last_edge) => match last_edge.into_node().ascend() { |
283 | Ok(parent_edge) => parent_edge.forget_node_type(), | |
3dfed10e XL |
284 | Err(root) => return Err(root), |
285 | }, | |
286 | } | |
287 | } | |
288 | } | |
289 | } | |
290 | ||
5869c6ff XL |
291 | impl<BorrowType: marker::BorrowType, K, V> |
292 | Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> | |
293 | { | |
3dfed10e XL |
294 | /// Given an internal edge handle, returns [`Result::Ok`] with a handle to the neighboring KV |
295 | /// on the right side, which is either in the same internal node or in an ancestor node. | |
296 | /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node. | |
136023e0 | 297 | fn next_kv( |
3dfed10e XL |
298 | self, |
299 | ) -> Result< | |
300 | Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>, | |
301 | NodeRef<BorrowType, K, V, marker::Internal>, | |
302 | > { | |
303 | let mut edge = self; | |
304 | loop { | |
305 | edge = match edge.right_kv() { | |
306 | Ok(internal_kv) => return Ok(internal_kv), | |
307 | Err(last_edge) => match last_edge.into_node().ascend() { | |
308 | Ok(parent_edge) => parent_edge, | |
309 | Err(root) => return Err(root), | |
74b04a01 XL |
310 | }, |
311 | } | |
312 | } | |
313 | } | |
314 | } | |
315 | ||
6a06907d XL |
316 | impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> { |
317 | /// Given a leaf edge handle into a dying tree, returns the next leaf edge | |
17df50a5 | 318 | /// on the right side, and the key-value pair in between, if they exist. |
6a06907d | 319 | /// |
17df50a5 XL |
320 | /// If the given edge is the last one in a leaf, this method deallocates |
321 | /// the leaf, as well as any ancestor nodes whose last edge was reached. | |
322 | /// This implies that if no more key-value pair follows, the entire tree | |
323 | /// will have been deallocated and there is nothing left to return. | |
6a06907d XL |
324 | /// |
325 | /// # Safety | |
17df50a5 XL |
326 | /// - The given edge must not have been previously returned by counterpart |
327 | /// `deallocating_next_back`. | |
328 | /// - The returned KV handle is only valid to access the key and value, | |
329 | /// and only valid until the next call to this method or counterpart | |
330 | /// `deallocating_next_back`. | |
136023e0 | 331 | unsafe fn deallocating_next( |
17df50a5 XL |
332 | self, |
333 | ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)> | |
334 | { | |
6a06907d XL |
335 | let mut edge = self.forget_node_type(); |
336 | loop { | |
337 | edge = match edge.right_kv() { | |
17df50a5 | 338 | Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)), |
6a06907d XL |
339 | Err(last_edge) => match unsafe { last_edge.into_node().deallocate_and_ascend() } { |
340 | Some(parent_edge) => parent_edge.forget_node_type(), | |
341 | None => return None, | |
342 | }, | |
74b04a01 XL |
343 | } |
344 | } | |
6a06907d XL |
345 | } |
346 | ||
347 | /// Given a leaf edge handle into a dying tree, returns the next leaf edge | |
17df50a5 | 348 | /// on the left side, and the key-value pair in between, if they exist. |
6a06907d | 349 | /// |
17df50a5 XL |
350 | /// If the given edge is the first one in a leaf, this method deallocates |
351 | /// the leaf, as well as any ancestor nodes whose first edge was reached. | |
352 | /// This implies that if no more key-value pair follows, the entire tree | |
353 | /// will have been deallocated and there is nothing left to return. | |
6a06907d XL |
354 | /// |
355 | /// # Safety | |
17df50a5 XL |
356 | /// - The given edge must not have been previously returned by counterpart |
357 | /// `deallocating_next`. | |
358 | /// - The returned KV handle is only valid to access the key and value, | |
359 | /// and only valid until the next call to this method or counterpart | |
360 | /// `deallocating_next`. | |
361 | unsafe fn deallocating_next_back( | |
362 | self, | |
363 | ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)> | |
364 | { | |
6a06907d XL |
365 | let mut edge = self.forget_node_type(); |
366 | loop { | |
367 | edge = match edge.left_kv() { | |
17df50a5 | 368 | Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)), |
6a06907d XL |
369 | Err(last_edge) => match unsafe { last_edge.into_node().deallocate_and_ascend() } { |
370 | Some(parent_edge) => parent_edge.forget_node_type(), | |
371 | None => return None, | |
372 | }, | |
373 | } | |
374 | } | |
375 | } | |
74b04a01 | 376 | |
6a06907d XL |
377 | /// Deallocates a pile of nodes from the leaf up to the root. |
378 | /// This is the only way to deallocate the remainder of a tree after | |
379 | /// `deallocating_next` and `deallocating_next_back` have been nibbling at | |
380 | /// both sides of the tree, and have hit the same edge. As it is intended | |
381 | /// only to be called when all keys and values have been returned, | |
382 | /// no cleanup is done on any of the keys or values. | |
383 | pub fn deallocating_end(self) { | |
384 | let mut edge = self.forget_node_type(); | |
385 | while let Some(parent_edge) = unsafe { edge.into_node().deallocate_and_ascend() } { | |
386 | edge = parent_edge.forget_node_type(); | |
387 | } | |
388 | } | |
389 | } | |
74b04a01 | 390 | |
74b04a01 XL |
391 | impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> { |
392 | /// Moves the leaf edge handle to the next leaf edge and returns references to the | |
393 | /// key and value in between. | |
1b1a35ee XL |
394 | /// |
395 | /// # Safety | |
396 | /// There must be another KV in the direction travelled. | |
136023e0 | 397 | unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { |
29967ef6 | 398 | super::mem::replace(self, |leaf_edge| { |
136023e0 | 399 | let kv = leaf_edge.next_kv().ok().unwrap(); |
3dfed10e XL |
400 | (kv.next_leaf_edge(), kv.into_kv()) |
401 | }) | |
74b04a01 XL |
402 | } |
403 | ||
404 | /// Moves the leaf edge handle to the previous leaf edge and returns references to the | |
405 | /// key and value in between. | |
1b1a35ee XL |
406 | /// |
407 | /// # Safety | |
408 | /// There must be another KV in the direction travelled. | |
136023e0 | 409 | unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) { |
29967ef6 | 410 | super::mem::replace(self, |leaf_edge| { |
136023e0 | 411 | let kv = leaf_edge.next_back_kv().ok().unwrap(); |
3dfed10e XL |
412 | (kv.next_back_leaf_edge(), kv.into_kv()) |
413 | }) | |
74b04a01 XL |
414 | } |
415 | } | |
416 | ||
1b1a35ee | 417 | impl<'a, K, V> Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge> { |
74b04a01 XL |
418 | /// Moves the leaf edge handle to the next leaf edge and returns references to the |
419 | /// key and value in between. | |
1b1a35ee XL |
420 | /// |
421 | /// # Safety | |
422 | /// There must be another KV in the direction travelled. | |
136023e0 | 423 | unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) { |
29967ef6 | 424 | let kv = super::mem::replace(self, |leaf_edge| { |
136023e0 | 425 | let kv = leaf_edge.next_kv().ok().unwrap(); |
3dfed10e XL |
426 | (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv) |
427 | }); | |
1b1a35ee XL |
428 | // Doing this last is faster, according to benchmarks. |
429 | kv.into_kv_valmut() | |
74b04a01 XL |
430 | } |
431 | ||
432 | /// Moves the leaf edge handle to the previous leaf and returns references to the | |
433 | /// key and value in between. | |
1b1a35ee XL |
434 | /// |
435 | /// # Safety | |
436 | /// There must be another KV in the direction travelled. | |
136023e0 | 437 | unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) { |
29967ef6 | 438 | let kv = super::mem::replace(self, |leaf_edge| { |
136023e0 | 439 | let kv = leaf_edge.next_back_kv().ok().unwrap(); |
3dfed10e XL |
440 | (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv) |
441 | }); | |
1b1a35ee XL |
442 | // Doing this last is faster, according to benchmarks. |
443 | kv.into_kv_valmut() | |
444 | } | |
445 | } | |
446 | ||
5869c6ff | 447 | impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> { |
74b04a01 | 448 | /// Moves the leaf edge handle to the next leaf edge and returns the key and value |
1b1a35ee XL |
449 | /// in between, deallocating any node left behind while leaving the corresponding |
450 | /// edge in its parent node dangling. | |
451 | /// | |
452 | /// # Safety | |
453 | /// - There must be another KV in the direction travelled. | |
17df50a5 XL |
454 | /// - That KV was not previously returned by counterpart |
455 | /// `deallocating_next_back_unchecked` on any copy of the handles | |
456 | /// being used to traverse the tree. | |
1b1a35ee XL |
457 | /// |
458 | /// The only safe way to proceed with the updated handle is to compare it, drop it, | |
17df50a5 XL |
459 | /// or call this method or counterpart `deallocating_next_back_unchecked` again. |
460 | pub unsafe fn deallocating_next_unchecked( | |
461 | &mut self, | |
462 | ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> { | |
136023e0 | 463 | super::mem::replace(self, |leaf_edge| unsafe { leaf_edge.deallocating_next().unwrap() }) |
74b04a01 XL |
464 | } |
465 | ||
1b1a35ee XL |
466 | /// Moves the leaf edge handle to the previous leaf edge and returns the key and value |
467 | /// in between, deallocating any node left behind while leaving the corresponding | |
468 | /// edge in its parent node dangling. | |
469 | /// | |
470 | /// # Safety | |
471 | /// - There must be another KV in the direction travelled. | |
17df50a5 XL |
472 | /// - That leaf edge was not previously returned by counterpart |
473 | /// `deallocating_next_unchecked` on any copy of the handles | |
474 | /// being used to traverse the tree. | |
1b1a35ee XL |
475 | /// |
476 | /// The only safe way to proceed with the updated handle is to compare it, drop it, | |
17df50a5 | 477 | /// or call this method or counterpart `deallocating_next_unchecked` again. |
136023e0 | 478 | unsafe fn deallocating_next_back_unchecked( |
17df50a5 XL |
479 | &mut self, |
480 | ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> { | |
6a06907d | 481 | super::mem::replace(self, |leaf_edge| unsafe { |
136023e0 | 482 | leaf_edge.deallocating_next_back().unwrap() |
3dfed10e | 483 | }) |
74b04a01 XL |
484 | } |
485 | } | |
486 | ||
5869c6ff | 487 | impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { |
74b04a01 XL |
488 | /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge |
489 | /// you need first when navigating forward (or last when navigating backward). | |
490 | #[inline] | |
491 | pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { | |
492 | let mut node = self; | |
493 | loop { | |
494 | match node.force() { | |
495 | Leaf(leaf) => return leaf.first_edge(), | |
496 | Internal(internal) => node = internal.first_edge().descend(), | |
497 | } | |
498 | } | |
499 | } | |
500 | ||
501 | /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge | |
502 | /// you need last when navigating forward (or first when navigating backward). | |
503 | #[inline] | |
504 | pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { | |
505 | let mut node = self; | |
506 | loop { | |
507 | match node.force() { | |
508 | Leaf(leaf) => return leaf.last_edge(), | |
509 | Internal(internal) => node = internal.last_edge().descend(), | |
510 | } | |
511 | } | |
512 | } | |
513 | } | |
514 | ||
3dfed10e XL |
515 | pub enum Position<BorrowType, K, V> { |
516 | Leaf(NodeRef<BorrowType, K, V, marker::Leaf>), | |
517 | Internal(NodeRef<BorrowType, K, V, marker::Internal>), | |
518 | InternalKV(Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>), | |
519 | } | |
520 | ||
521 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> { | |
522 | /// Visits leaf nodes and internal KVs in order of ascending keys, and also | |
523 | /// visits internal nodes as a whole in a depth first order, meaning that | |
524 | /// internal nodes precede their individual KVs and their child nodes. | |
525 | pub fn visit_nodes_in_order<F>(self, mut visit: F) | |
526 | where | |
527 | F: FnMut(Position<marker::Immut<'a>, K, V>), | |
528 | { | |
529 | match self.force() { | |
530 | Leaf(leaf) => visit(Position::Leaf(leaf)), | |
531 | Internal(internal) => { | |
532 | visit(Position::Internal(internal)); | |
533 | let mut edge = internal.first_edge(); | |
534 | loop { | |
535 | edge = match edge.descend().force() { | |
536 | Leaf(leaf) => { | |
537 | visit(Position::Leaf(leaf)); | |
538 | match edge.next_kv() { | |
539 | Ok(kv) => { | |
540 | visit(Position::InternalKV(kv)); | |
541 | kv.right_edge() | |
542 | } | |
543 | Err(_) => return, | |
544 | } | |
545 | } | |
546 | Internal(internal) => { | |
547 | visit(Position::Internal(internal)); | |
548 | internal.first_edge() | |
549 | } | |
550 | } | |
551 | } | |
552 | } | |
553 | } | |
554 | } | |
555 | ||
556 | /// Calculates the number of elements in a (sub)tree. | |
557 | pub fn calc_length(self) -> usize { | |
558 | let mut result = 0; | |
559 | self.visit_nodes_in_order(|pos| match pos { | |
560 | Position::Leaf(node) => result += node.len(), | |
561 | Position::Internal(node) => result += node.len(), | |
562 | Position::InternalKV(_) => (), | |
563 | }); | |
564 | result | |
565 | } | |
566 | } | |
567 | ||
5869c6ff XL |
568 | impl<BorrowType: marker::BorrowType, K, V> |
569 | Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> | |
570 | { | |
74b04a01 XL |
571 | /// Returns the leaf edge closest to a KV for forward navigation. |
572 | pub fn next_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { | |
573 | match self.force() { | |
574 | Leaf(leaf_kv) => leaf_kv.right_edge(), | |
575 | Internal(internal_kv) => { | |
576 | let next_internal_edge = internal_kv.right_edge(); | |
577 | next_internal_edge.descend().first_leaf_edge() | |
578 | } | |
579 | } | |
580 | } | |
581 | ||
582 | /// Returns the leaf edge closest to a KV for backward navigation. | |
136023e0 | 583 | fn next_back_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { |
74b04a01 XL |
584 | match self.force() { |
585 | Leaf(leaf_kv) => leaf_kv.left_edge(), | |
586 | Internal(internal_kv) => { | |
587 | let next_internal_edge = internal_kv.left_edge(); | |
588 | next_internal_edge.descend().last_leaf_edge() | |
589 | } | |
590 | } | |
591 | } | |
592 | } |