lewis.moe
Nothing to see here, move along
1use crate::block_io::BlockIo;
2use crate::cache::BlockCache;
3use crate::error::FsError;
4use crate::pool::{NodeIdx, NodePool, is_pool_ref, pool_idx_to_addr};
5use lancer_core::fs::{
6 BLOCK_SIZE_MIN_LOG2, BTREE_MAX_ENTRIES, BTREE_MIN_ENTRIES, BTreeNode, BlockRef, BlockType,
7 Compression,
8};
9
10const MAX_DEPTH: usize = 5;
11
12enum WalkDone {
13 Leaf(NodeIdx),
14 Err(FsError),
15}
16
17impl From<FsError> for WalkDone {
18 fn from(e: FsError) -> Self {
19 WalkDone::Err(e)
20 }
21}
22
23fn load_node(
24 pool: &mut NodePool,
25 cache: &mut BlockCache,
26 bio: &mut BlockIo,
27 block_ref: &BlockRef,
28) -> Result<NodeIdx, FsError> {
29 let addr = block_ref.physical_block_addr();
30 match is_pool_ref(addr) {
31 true => Ok(crate::pool::addr_to_pool_idx(addr)),
32 false => {
33 let block_num = crate::blockref_block_num(block_ref);
34 pool.pool_load(cache, bio, block_num)
35 }
36 }
37}
38
39fn load_and_validate(
40 pool: &mut NodePool,
41 cache: &mut BlockCache,
42 bio: &mut BlockIo,
43 block_ref: &BlockRef,
44) -> Result<NodeIdx, FsError> {
45 let idx = load_node(pool, cache, bio, block_ref)?;
46 match pool.get(idx).is_valid() {
47 true => Ok(idx),
48 false => {
49 pool.pool_free(idx);
50 Err(FsError::CorruptNode)
51 }
52 }
53}
54
55fn node_insert_entry(node: &mut BTreeNode, pos: usize, entry: BlockRef) -> bool {
56 let count = node.entry_count();
57 match count < BTREE_MAX_ENTRIES {
58 true => {
59 node.entries.copy_within(pos..count, pos + 1);
60 node.entries[pos] = entry;
61 node.header.entry_count += 1;
62 false
63 }
64 false => true,
65 }
66}
67
68fn node_remove_entry(node: &mut BTreeNode, pos: usize) -> BlockRef {
69 let count = node.entry_count();
70 let removed = node.entries[pos];
71 node.entries.copy_within(pos + 1..count, pos);
72 node.entries[count - 1] = BlockRef::ZERO;
73 node.header.entry_count -= 1;
74 removed
75}
76
77fn node_merge(
78 pool: &mut NodePool,
79 left_idx: NodeIdx,
80 right_idx: NodeIdx,
81) -> Result<NodeIdx, FsError> {
82 let merged_idx = pool.pool_alloc()?;
83
84 let left = pool.get(left_idx);
85 let left_count = left.entry_count();
86 let level = left.header.level;
87 let left_entries: [BlockRef; BTREE_MAX_ENTRIES] = {
88 let mut arr = [BlockRef::ZERO; BTREE_MAX_ENTRIES];
89 (0..left_count).for_each(|i| {
90 arr[i] = left.entries[i];
91 });
92 arr
93 };
94
95 let right = pool.get(right_idx);
96 let right_count = right.entry_count();
97 let right_entries: [BlockRef; BTREE_MAX_ENTRIES] = {
98 let mut arr = [BlockRef::ZERO; BTREE_MAX_ENTRIES];
99 (0..right_count).for_each(|i| {
100 arr[i] = right.entries[i];
101 });
102 arr
103 };
104
105 let merged = pool.get_mut(merged_idx);
106 merged.header = lancer_core::fs::BTreeNodeHeader::new(level);
107 (0..left_count).for_each(|i| {
108 merged.entries[i] = left_entries[i];
109 });
110 (0..right_count).for_each(|i| {
111 merged.entries[left_count + i] = right_entries[i];
112 });
113 merged.header.entry_count = (left_count + right_count) as u16;
114
115 pool.pool_free(left_idx);
116 pool.pool_free(right_idx);
117
118 Ok(merged_idx)
119}
120
121pub fn btree_lookup(
122 pool: &mut NodePool,
123 cache: &mut BlockCache,
124 bio: &mut BlockIo,
125 root: &BlockRef,
126 key: u64,
127 txn_filter: Option<u64>,
128) -> Result<Option<BlockRef>, FsError> {
129 if root.is_null() {
130 return Ok(None);
131 }
132
133 let mut loaded: [NodeIdx; MAX_DEPTH + 1] = [0; { MAX_DEPTH + 1 }];
134 let mut loaded_count = 0usize;
135 let mut result: Option<BlockRef> = None;
136
137 let walk_err = (0..MAX_DEPTH + 1).try_fold(*root, |current_ref, _| {
138 let idx = load_and_validate(pool, cache, bio, ¤t_ref)?;
139 loaded[loaded_count] = idx;
140 loaded_count += 1;
141
142 let node = pool.get(idx);
143 match node.is_leaf() {
144 true => {
145 result = node
146 .search_by_key(key)
147 .ok()
148 .map(|i| node.entries[i])
149 .filter(|entry| match txn_filter {
150 Some(max_txn) => entry.transaction_id <= max_txn,
151 None => true,
152 });
153 Err(WalkDone::Leaf(idx))
154 }
155 false => {
156 let child_idx = node.find_child_index(key);
157 match child_idx < node.entry_count() {
158 true => Ok(node.entries[child_idx]),
159 false => {
160 result = None;
161 Err(WalkDone::Leaf(idx))
162 }
163 }
164 }
165 }
166 });
167
168 (0..loaded_count).for_each(|i| {
169 let idx = loaded[i];
170 if !pool.is_dirty(idx) {
171 pool.pool_free(idx);
172 }
173 });
174
175 match walk_err {
176 Err(WalkDone::Leaf(_)) => Ok(result),
177 Err(WalkDone::Err(e)) => Err(e),
178 Ok(_) => Err(FsError::CorruptNode),
179 }
180}
181
182struct PathEntry {
183 pool_idx: NodeIdx,
184 child_index: usize,
185}
186
187pub fn btree_insert(
188 pool: &mut NodePool,
189 cache: &mut BlockCache,
190 bio: &mut BlockIo,
191 root: &BlockRef,
192 key: u64,
193 value: BlockRef,
194 txn: u64,
195) -> Result<BlockRef, FsError> {
196 if root.is_null() {
197 let leaf_idx = pool.pool_alloc()?;
198 let leaf = pool.get_mut(leaf_idx);
199 *leaf = BTreeNode::new(0);
200 let mut entry = value;
201 entry.key = key;
202 entry.transaction_id = txn;
203 leaf.entries[0] = entry;
204 leaf.header.entry_count = 1;
205 return Ok(make_pool_blockref(leaf_idx));
206 }
207
208 let mut path: [PathEntry; MAX_DEPTH] = core::array::from_fn(|_| PathEntry {
209 pool_idx: 0,
210 child_index: 0,
211 });
212 let mut depth = 0usize;
213 let mut leaf_idx: NodeIdx = 0;
214
215 let walk_err = (0..MAX_DEPTH + 1).try_fold(*root, |current_ref, _| {
216 let idx = load_and_validate(pool, cache, bio, ¤t_ref)?;
217 let node = pool.get(idx);
218
219 match node.is_leaf() {
220 true => {
221 leaf_idx = idx;
222 Err(WalkDone::Leaf(idx))
223 }
224 false => {
225 let child_idx = node.find_child_index(key);
226 match depth < MAX_DEPTH {
227 true => {
228 path[depth] = PathEntry {
229 pool_idx: idx,
230 child_index: child_idx,
231 };
232 depth += 1;
233 }
234 false => return Err(FsError::TreeFull.into()),
235 }
236 match child_idx < node.entry_count() {
237 true => Ok(node.entries[child_idx]),
238 false => Err(FsError::CorruptNode.into()),
239 }
240 }
241 }
242 });
243
244 match walk_err {
245 Err(WalkDone::Leaf(_)) => {}
246 Err(WalkDone::Err(e)) => return Err(e),
247 Ok(_) => return Err(FsError::CorruptNode),
248 }
249
250 if pool.get(leaf_idx).search_by_key(key).is_ok() {
251 return Err(FsError::DuplicateKey);
252 }
253
254 let new_leaf_idx = cow_node(pool, leaf_idx)?;
255 let new_leaf = pool.get_mut(new_leaf_idx);
256 let insert_pos = match new_leaf.search_by_key(key) {
257 Ok(_) => return Err(FsError::DuplicateKey),
258 Err(pos) => pos,
259 };
260
261 match new_leaf.entry_count() < BTREE_MAX_ENTRIES {
262 true => {
263 let mut entry = value;
264 entry.key = key;
265 entry.transaction_id = txn;
266 node_insert_entry(new_leaf, insert_pos, entry);
267 propagate_up(pool, &path, depth, new_leaf_idx, None, root, txn)
268 }
269 false => {
270 let mut entry = value;
271 entry.key = key;
272 entry.transaction_id = txn;
273 let split = split_with_insert(pool, new_leaf_idx, insert_pos, entry)?;
274 propagate_up(pool, &path, depth, 0, Some(split), root, txn)
275 }
276 }
277}
278
279fn split_with_insert(
280 pool: &mut NodePool,
281 full_idx: NodeIdx,
282 insert_pos: usize,
283 entry: BlockRef,
284) -> Result<(NodeIdx, NodeIdx), FsError> {
285 let left_idx = pool.pool_alloc()?;
286 let right_idx = pool.pool_alloc()?;
287
288 let full_node = pool.get(full_idx);
289 let level = full_node.header.level;
290 let count = full_node.entry_count();
291
292 let total = count + 1;
293 let mid = total / 2;
294
295 let mut combined = [BlockRef::ZERO; BTREE_MAX_ENTRIES + 1];
296 (0..insert_pos).for_each(|i| {
297 combined[i] = full_node.entries[i];
298 });
299 combined[insert_pos] = entry;
300 (insert_pos..count).for_each(|i| {
301 combined[i + 1] = full_node.entries[i];
302 });
303
304 {
305 let left = pool.get_mut(left_idx);
306 left.header = lancer_core::fs::BTreeNodeHeader::new(level);
307 left.header.entry_count = mid as u16;
308 (0..mid).for_each(|i| {
309 left.entries[i] = combined[i];
310 });
311 }
312
313 let right_count = total - mid;
314 {
315 let right = pool.get_mut(right_idx);
316 right.header = lancer_core::fs::BTreeNodeHeader::new(level);
317 right.header.entry_count = right_count as u16;
318 (0..right_count).for_each(|i| {
319 right.entries[i] = combined[mid + i];
320 });
321 }
322
323 pool.pool_free(full_idx);
324
325 Ok((left_idx, right_idx))
326}
327
328fn free_if_clean(pool: &mut NodePool, idx: NodeIdx) {
329 match pool.is_dirty(idx) {
330 true => {}
331 false => pool.pool_free(idx),
332 }
333}
334
335fn cow_node(pool: &mut NodePool, src_idx: NodeIdx) -> Result<NodeIdx, FsError> {
336 match pool.is_dirty(src_idx) {
337 true => Ok(src_idx),
338 false => {
339 let src = pool.get(src_idx).clone();
340 let new_idx = pool.pool_alloc()?;
341 *pool.get_mut(new_idx) = src;
342 [src_idx]
343 .iter()
344 .filter(|&&idx| new_idx != idx)
345 .for_each(|&idx| pool.pool_free(idx));
346 Ok(new_idx)
347 }
348 }
349}
350
351fn make_pool_blockref(idx: NodeIdx) -> BlockRef {
352 let addr = pool_idx_to_addr(idx);
353 BlockRef::new(
354 addr & !0xF,
355 BLOCK_SIZE_MIN_LOG2,
356 0,
357 0,
358 0u128,
359 0u32,
360 BlockType::Indirect,
361 Compression::None,
362 0,
363 0,
364 )
365}
366
367fn make_child_ref(pool_idx: NodeIdx, key: u64, txn: u64) -> BlockRef {
368 let mut r = make_pool_blockref(pool_idx);
369 r.key = key;
370 r.transaction_id = txn;
371 r
372}
373
374fn max_key_in_node(pool: &NodePool, idx: NodeIdx) -> u64 {
375 let node = pool.get(idx);
376 let count = node.entry_count();
377 match count {
378 0 => 0,
379 _ => node.entries[count - 1].key,
380 }
381}
382
383fn propagate_up(
384 pool: &mut NodePool,
385 path: &[PathEntry; MAX_DEPTH],
386 depth: usize,
387 child_idx: NodeIdx,
388 pending_split: Option<(NodeIdx, NodeIdx)>,
389 root: &BlockRef,
390 txn: u64,
391) -> Result<BlockRef, FsError> {
392 let mut split: Option<(NodeIdx, NodeIdx)> = pending_split;
393
394 let top_result: Result<u16, FsError> =
395 (0..depth)
396 .rev()
397 .try_fold(child_idx, |current_child, level| {
398 let parent_entry = &path[level];
399 let new_parent_idx = cow_node(pool, parent_entry.pool_idx)?;
400
401 match split.take() {
402 Some((left_idx, right_idx)) => {
403 let left_max = max_key_in_node(pool, left_idx);
404 let right_max = max_key_in_node(pool, right_idx);
405
406 let left_ref = make_child_ref(left_idx, left_max, txn);
407 let right_ref = make_child_ref(right_idx, right_max, txn);
408
409 let parent = pool.get_mut(new_parent_idx);
410 let ci = parent_entry.child_index;
411 parent.entries[ci] = left_ref;
412
413 let overflow = node_insert_entry(parent, ci + 1, right_ref);
414 match overflow {
415 true => {
416 let new_split = split_with_parent_insert(
417 pool,
418 new_parent_idx,
419 ci + 1,
420 right_ref,
421 )?;
422 split = Some(new_split);
423 Ok(new_split.0)
424 }
425 false => {
426 split = None;
427 Ok(new_parent_idx)
428 }
429 }
430 }
431 None => {
432 let child_max = max_key_in_node(pool, current_child);
433 let parent = pool.get_mut(new_parent_idx);
434 let child_ref = &mut parent.entries[parent_entry.child_index];
435 child_ref.physical_addr =
436 pool_idx_to_addr(current_child) | (child_ref.physical_addr & 0xF);
437 child_ref.key = child_max;
438 child_ref.transaction_id = txn;
439 Ok(new_parent_idx)
440 }
441 }
442 });
443
444 let top_idx = top_result?;
445
446 match split {
447 Some((left_idx, right_idx)) => {
448 let new_root_idx = pool.pool_alloc()?;
449 let top_level = pool.get(left_idx).header.level;
450
451 let left_max = max_key_in_node(pool, left_idx);
452 let right_max = max_key_in_node(pool, right_idx);
453
454 let left_ref = make_child_ref(left_idx, left_max, txn);
455 let right_ref = make_child_ref(right_idx, right_max, txn);
456
457 let new_root = pool.get_mut(new_root_idx);
458 *new_root = BTreeNode::new(top_level + 1);
459 new_root.entries[0] = left_ref;
460 new_root.entries[1] = right_ref;
461 new_root.header.entry_count = 2;
462
463 Ok(make_pool_blockref(new_root_idx))
464 }
465 None => {
466 let mut r = make_pool_blockref(top_idx);
467 r.key = root.key;
468 r.transaction_id = root.transaction_id;
469 Ok(r)
470 }
471 }
472}
473
474fn split_with_parent_insert(
475 pool: &mut NodePool,
476 full_idx: NodeIdx,
477 insert_pos: usize,
478 entry: BlockRef,
479) -> Result<(NodeIdx, NodeIdx), FsError> {
480 split_with_insert(pool, full_idx, insert_pos, entry)
481}
482
483pub fn btree_delete(
484 pool: &mut NodePool,
485 cache: &mut BlockCache,
486 bio: &mut BlockIo,
487 root: &BlockRef,
488 key: u64,
489 txn: u64,
490) -> Result<Option<BlockRef>, FsError> {
491 if root.is_null() {
492 return Ok(None);
493 }
494
495 let mut path: [PathEntry; MAX_DEPTH] = core::array::from_fn(|_| PathEntry {
496 pool_idx: 0,
497 child_index: 0,
498 });
499 let mut depth = 0usize;
500 let mut leaf_idx: NodeIdx = 0;
501
502 let walk_err = (0..MAX_DEPTH + 1).try_fold(*root, |current_ref, _| {
503 let idx = load_and_validate(pool, cache, bio, ¤t_ref)?;
504 let node = pool.get(idx);
505
506 match node.is_leaf() {
507 true => {
508 leaf_idx = idx;
509 Err(WalkDone::Leaf(idx))
510 }
511 false => {
512 let child_idx = node.find_child_index(key);
513 match depth < MAX_DEPTH {
514 true => {
515 path[depth] = PathEntry {
516 pool_idx: idx,
517 child_index: child_idx,
518 };
519 depth += 1;
520 }
521 false => return Err(FsError::TreeFull.into()),
522 }
523 match child_idx < node.entry_count() {
524 true => Ok(node.entries[child_idx]),
525 false => Err(FsError::CorruptNode.into()),
526 }
527 }
528 }
529 });
530
531 match walk_err {
532 Err(WalkDone::Leaf(_)) => {}
533 Err(WalkDone::Err(e)) => return Err(e),
534 Ok(_) => return Err(FsError::CorruptNode),
535 }
536
537 let key_pos = match pool.get(leaf_idx).search_by_key(key) {
538 Ok(pos) => pos,
539 Err(_) => return Ok(None),
540 };
541
542 let new_leaf_idx = cow_node(pool, leaf_idx)?;
543 node_remove_entry(pool.get_mut(new_leaf_idx), key_pos);
544
545 match depth {
546 0 => Ok(Some(make_pool_blockref(new_leaf_idx))),
547 _ => propagate_delete_up(pool, cache, bio, &path, depth, new_leaf_idx, txn),
548 }
549}
550
551#[allow(clippy::too_many_arguments)]
552fn propagate_delete_up(
553 pool: &mut NodePool,
554 cache: &mut BlockCache,
555 bio: &mut BlockIo,
556 path: &[PathEntry; MAX_DEPTH],
557 depth: usize,
558 child_idx: NodeIdx,
559 txn: u64,
560) -> Result<Option<BlockRef>, FsError> {
561 let mut needs_rebalance = pool.get(child_idx).entry_count() < BTREE_MIN_ENTRIES;
562
563 let top_idx = (0..depth)
564 .rev()
565 .try_fold(child_idx, |current_child, level| {
566 let parent_entry = &path[level];
567 let new_parent_idx = cow_node(pool, parent_entry.pool_idx)?;
568
569 match needs_rebalance {
570 true => {
571 let rebalanced = rebalance(
572 pool,
573 cache,
574 bio,
575 new_parent_idx,
576 parent_entry.child_index,
577 current_child,
578 txn,
579 )?;
580 needs_rebalance = match level > 0 {
581 true => pool.get(rebalanced).entry_count() < BTREE_MIN_ENTRIES,
582 false => false,
583 };
584 Ok::<NodeIdx, FsError>(rebalanced)
585 }
586 false => {
587 let child_max = max_key_in_node(pool, current_child);
588 let parent = pool.get_mut(new_parent_idx);
589 let child_ref = &mut parent.entries[parent_entry.child_index];
590 child_ref.physical_addr =
591 pool_idx_to_addr(current_child) | (child_ref.physical_addr & 0xF);
592 child_ref.key = child_max;
593 child_ref.transaction_id = txn;
594 needs_rebalance = false;
595 Ok(new_parent_idx)
596 }
597 }
598 })?;
599
600 let top_node = pool.get(top_idx);
601 match top_node.entry_count() == 1 && top_node.header.level > 0 {
602 true => {
603 let only_child_ref = top_node.entries[0];
604 match is_pool_ref(only_child_ref.physical_block_addr()) {
605 true => {
606 let child_pool_idx =
607 crate::pool::addr_to_pool_idx(only_child_ref.physical_block_addr());
608 pool.pool_free(top_idx);
609 Ok(Some(make_pool_blockref(child_pool_idx)))
610 }
611 false => {
612 pool.pool_free(top_idx);
613 Ok(Some(only_child_ref))
614 }
615 }
616 }
617 false => Ok(Some(make_pool_blockref(top_idx))),
618 }
619}
620
621#[allow(clippy::too_many_arguments)]
622fn rebalance(
623 pool: &mut NodePool,
624 cache: &mut BlockCache,
625 bio: &mut BlockIo,
626 parent_idx: NodeIdx,
627 child_pos: usize,
628 child_idx: NodeIdx,
629 txn: u64,
630) -> Result<NodeIdx, FsError> {
631 let parent_count = pool.get(parent_idx).entry_count();
632
633 let right_sib_ref = match child_pos + 1 < parent_count {
634 true => Some(pool.get(parent_idx).entries[child_pos + 1]),
635 false => None,
636 };
637 let left_sib_ref = match child_pos > 0 {
638 true => Some(pool.get(parent_idx).entries[child_pos - 1]),
639 false => None,
640 };
641
642 let right_sibling = match right_sib_ref {
643 Some(ref sib_ref) => Some(load_and_validate(pool, cache, bio, sib_ref)?),
644 None => None,
645 };
646
647 match right_sibling {
648 Some(sib_idx) if pool.get(sib_idx).entry_count() > BTREE_MIN_ENTRIES => {
649 return redistribute_from_right(pool, parent_idx, child_pos, child_idx, sib_idx, txn);
650 }
651 _ => {}
652 }
653
654 let left_sibling = match left_sib_ref {
655 Some(ref sib_ref) => Some(load_and_validate(pool, cache, bio, sib_ref)?),
656 None => None,
657 };
658
659 match left_sibling {
660 Some(sib_idx) if pool.get(sib_idx).entry_count() > BTREE_MIN_ENTRIES => {
661 if let Some(right_idx) = right_sibling {
662 free_if_clean(pool, right_idx);
663 }
664 return redistribute_from_left(pool, parent_idx, child_pos, child_idx, sib_idx, txn);
665 }
666 _ => {}
667 }
668
669 if let Some(sib_idx) = right_sibling {
670 if let Some(left_idx) = left_sibling {
671 free_if_clean(pool, left_idx);
672 }
673 let merged_idx = node_merge(pool, child_idx, sib_idx)?;
674 let merged_max = max_key_in_node(pool, merged_idx);
675 let parent = pool.get_mut(parent_idx);
676 parent.entries[child_pos] = make_child_ref(merged_idx, merged_max, txn);
677 node_remove_entry(parent, child_pos + 1);
678 return Ok(parent_idx);
679 }
680
681 if let Some(sib_idx) = left_sibling {
682 let merged_idx = node_merge(pool, sib_idx, child_idx)?;
683 let merged_max = max_key_in_node(pool, merged_idx);
684 let parent = pool.get_mut(parent_idx);
685 parent.entries[child_pos - 1] = make_child_ref(merged_idx, merged_max, txn);
686 node_remove_entry(parent, child_pos);
687 return Ok(parent_idx);
688 }
689
690 let child_max = max_key_in_node(pool, child_idx);
691 let parent = pool.get_mut(parent_idx);
692 let child_ref = &mut parent.entries[child_pos];
693 child_ref.physical_addr = pool_idx_to_addr(child_idx) | (child_ref.physical_addr & 0xF);
694 child_ref.key = child_max;
695 child_ref.transaction_id = txn;
696 Ok(parent_idx)
697}
698
699fn redistribute_from_right(
700 pool: &mut NodePool,
701 parent_idx: NodeIdx,
702 child_pos: usize,
703 child_idx: NodeIdx,
704 sib_idx: NodeIdx,
705 txn: u64,
706) -> Result<NodeIdx, FsError> {
707 let new_child_idx = cow_node(pool, child_idx)?;
708 let new_sib_idx = cow_node(pool, sib_idx)?;
709
710 let first_from_sib = node_remove_entry(pool.get_mut(new_sib_idx), 0);
711
712 let child = pool.get_mut(new_child_idx);
713 node_insert_entry(child, child.entry_count(), first_from_sib);
714
715 let child_max = max_key_in_node(pool, new_child_idx);
716 let sib_max = max_key_in_node(pool, new_sib_idx);
717
718 let parent = pool.get_mut(parent_idx);
719 parent.entries[child_pos] = make_child_ref(new_child_idx, child_max, txn);
720 parent.entries[child_pos + 1] = make_child_ref(new_sib_idx, sib_max, txn);
721
722 Ok(parent_idx)
723}
724
725fn redistribute_from_left(
726 pool: &mut NodePool,
727 parent_idx: NodeIdx,
728 child_pos: usize,
729 child_idx: NodeIdx,
730 sib_idx: NodeIdx,
731 txn: u64,
732) -> Result<NodeIdx, FsError> {
733 let new_child_idx = cow_node(pool, child_idx)?;
734 let new_sib_idx = cow_node(pool, sib_idx)?;
735
736 let sib = pool.get_mut(new_sib_idx);
737 let last_pos = sib.entry_count() - 1;
738 let last_from_sib = node_remove_entry(sib, last_pos);
739
740 let child = pool.get_mut(new_child_idx);
741 node_insert_entry(child, 0, last_from_sib);
742
743 let child_max = max_key_in_node(pool, new_child_idx);
744 let sib_max = max_key_in_node(pool, new_sib_idx);
745
746 let parent = pool.get_mut(parent_idx);
747 parent.entries[child_pos] = make_child_ref(new_child_idx, child_max, txn);
748 parent.entries[child_pos - 1] = make_child_ref(new_sib_idx, sib_max, txn);
749
750 Ok(parent_idx)
751}
752
753pub struct BTreeIter {
754 root: BlockRef,
755 start_key: u64,
756 end_key: u64,
757 txn_filter: Option<u64>,
758 last_key: Option<u64>,
759 exhausted: bool,
760}
761
762pub fn btree_range(
763 root: &BlockRef,
764 start_key: u64,
765 end_key: u64,
766 txn_filter: Option<u64>,
767) -> BTreeIter {
768 BTreeIter {
769 root: *root,
770 start_key,
771 end_key,
772 txn_filter,
773 last_key: None,
774 exhausted: false,
775 }
776}
777
778impl BTreeIter {
779 pub fn next(
780 &mut self,
781 pool: &mut NodePool,
782 cache: &mut BlockCache,
783 bio: &mut BlockIo,
784 ) -> Result<Option<BlockRef>, FsError> {
785 if self.exhausted {
786 return Ok(None);
787 }
788
789 let search_key = self
790 .last_key
791 .map(|k| k.saturating_add(1))
792 .unwrap_or(self.start_key);
793
794 if search_key > self.end_key {
795 self.exhausted = true;
796 return Ok(None);
797 }
798
799 if self.root.is_null() {
800 self.exhausted = true;
801 return Ok(None);
802 }
803
804 let leaf_idx = walk_to_leaf_pool(pool, cache, bio, &self.root, search_key)?;
805 let node = pool.get(leaf_idx);
806 let count = node.entry_count();
807
808 let txn_filter = self.txn_filter;
809 let end_key = self.end_key;
810 let found = (0..count)
811 .map(|i| node.entries[i])
812 .filter(|e| e.key >= search_key && e.key <= end_key)
813 .find(|e| match txn_filter {
814 Some(max_txn) => e.transaction_id <= max_txn,
815 None => true,
816 });
817
818 let max_key = (0..count).map(|i| node.entries[i].key).max();
819
820 if !pool.is_dirty(leaf_idx) {
821 pool.pool_free(leaf_idx);
822 }
823
824 match found {
825 Some(entry) => {
826 self.last_key = Some(entry.key);
827 Ok(Some(entry))
828 }
829 None => match max_key {
830 Some(mk) if mk >= search_key && mk < self.end_key => {
831 self.last_key = Some(mk);
832 self.next(pool, cache, bio)
833 }
834 _ => {
835 self.exhausted = true;
836 Ok(None)
837 }
838 },
839 }
840 }
841}
842
843fn walk_to_leaf_pool(
844 pool: &mut NodePool,
845 cache: &mut BlockCache,
846 bio: &mut BlockIo,
847 root: &BlockRef,
848 target_key: u64,
849) -> Result<NodeIdx, FsError> {
850 let mut intermediates: [NodeIdx; MAX_DEPTH] = [0; MAX_DEPTH];
851 let mut intermediate_count = 0usize;
852 let mut leaf_result: Option<NodeIdx> = None;
853
854 let walk_err = (0..MAX_DEPTH + 1).try_fold(*root, |current_ref, _| {
855 let idx = load_and_validate(pool, cache, bio, ¤t_ref).map_err(WalkDone::Err)?;
856 let node = pool.get(idx);
857
858 match node.is_leaf() {
859 true => {
860 leaf_result = Some(idx);
861 Err(WalkDone::Leaf(idx))
862 }
863 false => {
864 intermediates[intermediate_count] = idx;
865 intermediate_count += 1;
866 let child_idx = node.find_child_index(target_key);
867 match child_idx < node.entry_count() {
868 true => Ok(node.entries[child_idx]),
869 false => {
870 let last = node.entry_count().saturating_sub(1);
871 Ok(node.entries[last])
872 }
873 }
874 }
875 }
876 });
877
878 (0..intermediate_count).for_each(|i| {
879 free_if_clean(pool, intermediates[i]);
880 });
881
882 match leaf_result {
883 Some(idx) => Ok(idx),
884 None => match walk_err {
885 Err(WalkDone::Err(e)) => Err(e),
886 _ => Err(FsError::CorruptNode),
887 },
888 }
889}