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