use core::cmp::Ordering;
use core::marker::PhantomData;
use core::mem::size_of;
use std::io;
use crate::BStackRaiiAllocator;
use bstack::{BStack, BStackRange};
use bytemuck::{Pod, Zeroable};
use super::util::{Scratch, alloc_image, read_fields, w8};
use crate::handback::ReplaceError;
use crate::io_core::{ClonePlan, TryCloneIn, dealloc_range};
use crate::primitives::EightCC;
use crate::types::compiled::{BStackOwned, BlockHeader, HEADER_SIZE};
use crate::types::traits::{BStackBlock, BStackCast, BStackDrop};
use crate::util::{SmallBuf, get_u64, io_error, io_errorfn, read_u64};
#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
pub struct TreeOnDisk {
pub header: BlockHeader,
pub root: u64,
pub len: u64,
}
const ROOT_OFF: u64 = HEADER_SIZE; const LEN_OFF: u64 = HEADER_SIZE + 8; const TREE_SIZE: u64 = size_of::<TreeOnDisk>() as u64;
const T: usize = 8;
const MAXKEYS: usize = 2 * T - 1;
const MAX_TREE_DEPTH: u32 = 64;
io_errorfn!(
depth_exceeded,
InvalidData,
"B-tree deeper than the structural bound (corrupt child pointer or a cycle?)"
);
const MAXCHILDREN: usize = 2 * T;
const NKEYS_OFF: usize = HEADER_SIZE as usize; const LEAF_OFF: usize = HEADER_SIZE as usize + 8; const KEYS_OFF: usize = HEADER_SIZE as usize + 16;
struct BNode {
leaf: bool,
keys: Vec<Vec<u8>>,
vals: Vec<u64>,
children: Vec<u64>,
}
struct Split {
key: Vec<u8>,
val: u64,
right: u64,
}
struct Build<'a, A: BStackRaiiAllocator> {
allocator: &'a A,
node_size: u64,
ksize: usize,
vals_off: usize,
children_off: usize,
writes: Vec<(u64, SmallBuf)>,
freed: Vec<u64>,
}
impl<'a, A: BStackRaiiAllocator> Build<'a, A> {
fn emit(&mut self, nb: &BNode) -> io::Result<u64> {
let mut b = vec![0u8; self.node_size as usize];
b[NKEYS_OFF..NKEYS_OFF + 8].copy_from_slice(&(nb.keys.len() as u64).to_le_bytes());
b[LEAF_OFF..LEAF_OFF + 8].copy_from_slice(&(nb.leaf as u64).to_le_bytes());
for (i, k) in nb.keys.iter().enumerate() {
let ko = KEYS_OFF + i * self.ksize;
b[ko..ko + self.ksize].copy_from_slice(k);
}
for (i, v) in nb.vals.iter().enumerate() {
let vo = self.vals_off + i * 8;
b[vo..vo + 8].copy_from_slice(&v.to_le_bytes());
}
for (i, c) in nb.children.iter().enumerate() {
let co = self.children_off + i * 8;
b[co..co + 8].copy_from_slice(&c.to_le_bytes());
}
let off = self.allocator.alloc(self.node_size)?.as_range().start();
self.writes
.push((off, SmallBuf::Heap(b.into_boxed_slice())));
Ok(off)
}
}
pub struct BStackBTreeMap<K: Pod + Ord, V: BStackBlock> {
range: BStackRange,
_marker: PhantomData<fn() -> (K, V)>,
}
impl<K: Pod + Ord, V: BStackBlock> BStackBTreeMap<K, V> {
const fn ksize() -> usize {
size_of::<K>()
}
const fn vals_off() -> usize {
KEYS_OFF + MAXKEYS * Self::ksize()
}
const fn children_off() -> usize {
Self::vals_off() + MAXKEYS * 8
}
const fn node_size() -> u64 {
(Self::children_off() + MAXCHILDREN * 8) as u64
}
fn value_size() -> u64 {
size_of::<<V as BStackBlock>::OnDisk>() as u64
}
fn value_at(off: u64) -> V {
unsafe { <V as BStackBlock>::from_range(BStackRange::new(off, Self::value_size())) }
}
fn read_key(bytes: &[u8]) -> K {
bytemuck::pod_read_unaligned::<K>(&bytes[..Self::ksize()])
}
pub fn new<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<BStackOwned<Self>> {
let od = TreeOnDisk {
header: BlockHeader {
size: TREE_SIZE,
tag: Self::eightcc(),
},
root: 0,
len: 0,
};
let range = alloc_image(allocator, bytemuck::bytes_of(&od))?;
Ok(unsafe { BStackOwned::from_raw(Self::from_range(range)) })
}
pub fn len(&self, stack: &BStack) -> io::Result<u64> {
read_u64(stack, self.range.start() + LEN_OFF)
}
pub fn is_empty(&self, stack: &BStack) -> io::Result<bool> {
Ok(self.len(stack)? == 0)
}
fn read_node(stack: &BStack, off: u64) -> io::Result<BNode> {
let mut b = vec![0u8; Self::node_size() as usize];
stack.get_into(off, &mut b)?;
let nkeys = get_u64(&b[NKEYS_OFF..]) as usize;
if nkeys > MAXKEYS {
return Err(io_error!("corrupt B-tree node: key count exceeds capacity"));
}
let leaf = get_u64(&b[LEAF_OFF..]) != 0;
let ksize = Self::ksize();
let vals_off = Self::vals_off();
let children_off = Self::children_off();
let mut keys = Vec::with_capacity(nkeys);
let mut vals = Vec::with_capacity(nkeys);
for i in 0..nkeys {
let ko = KEYS_OFF + i * ksize;
keys.push(b[ko..ko + ksize].to_vec());
vals.push(get_u64(&b[vals_off + i * 8..]));
}
let mut children = Vec::new();
if !leaf {
for i in 0..=nkeys {
children.push(get_u64(&b[children_off + i * 8..]));
}
}
Ok(BNode {
leaf,
keys,
vals,
children,
})
}
fn search(nb: &BNode, target: &K) -> (usize, bool) {
for (j, kb) in nb.keys.iter().enumerate() {
match target.cmp(&Self::read_key(kb)) {
Ordering::Less => return (j, false),
Ordering::Equal => return (j, true),
Ordering::Greater => {}
}
}
(nb.keys.len(), false)
}
fn split(mut nb: BNode) -> (BNode, Split, BNode) {
let m = nb.keys.len() / 2;
let right_children = if nb.leaf {
Vec::new()
} else {
nb.children.split_off(m + 1)
};
let right_keys = nb.keys.split_off(m + 1);
let right_vals = nb.vals.split_off(m + 1);
let med_key = nb.keys.pop().unwrap();
let med_val = nb.vals.pop().unwrap();
let right = BNode {
leaf: nb.leaf,
keys: right_keys,
vals: right_vals,
children: right_children,
};
let split = Split {
key: med_key,
val: med_val,
right: 0, };
(nb, split, right)
}
fn insert_rec(
build: &mut Build<'_, impl BStackRaiiAllocator>,
stack: &BStack,
off: u64,
key: &K,
key_bytes: &[u8],
val: u64,
) -> io::Result<(u64, Option<Split>, bool, Option<u64>)> {
let mut nb = Self::read_node(stack, off)?;
build.freed.push(off);
let (i, exact) = Self::search(&nb, key);
if exact {
let old = nb.vals[i];
nb.vals[i] = val;
let new_off = build.emit(&nb)?;
return Ok((new_off, None, false, Some(old)));
}
let (added, old) = if nb.leaf {
nb.keys.insert(i, key_bytes.to_vec());
nb.vals.insert(i, val);
(true, None)
} else {
let child = nb.children[i];
let (new_child, child_split, added, old) =
Self::insert_rec(build, stack, child, key, key_bytes, val)?;
nb.children[i] = new_child;
if let Some(s) = child_split {
nb.keys.insert(i, s.key);
nb.vals.insert(i, s.val);
nb.children.insert(i + 1, s.right);
}
(added, old)
};
if nb.keys.len() <= MAXKEYS {
let new_off = build.emit(&nb)?;
Ok((new_off, None, added, old))
} else {
let (left, mut split, right) = Self::split(nb);
split.right = build.emit(&right)?;
let left_off = build.emit(&left)?;
Ok((left_off, Some(split), added, old))
}
}
pub fn insert<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: K,
value: BStackOwned<V>,
) -> Result<Option<BStackOwned<V>>, ReplaceError<BStackOwned<V>>> {
let handle = self.range.start();
let stack = allocator.stack();
let key_bytes = bytemuck::bytes_of(&key).to_vec();
let value = value.auto(allocator);
let val_ref = value.range().start();
let outcome: io::Result<Option<BStackOwned<V>>> = (|| {
let [root, len] = read_fields::<2>(stack, handle + ROOT_OFF)?;
let mut build = Build {
allocator,
node_size: Self::node_size(),
ksize: Self::ksize(),
vals_off: Self::vals_off(),
children_off: Self::children_off(),
writes: Vec::new(),
freed: Vec::new(),
};
let built: io::Result<(u64, bool, Option<u64>)> = (|| {
if root == 0 {
let leaf = BNode {
leaf: true,
keys: vec![key_bytes.clone()],
vals: vec![val_ref],
children: Vec::new(),
};
let new_root = build.emit(&leaf)?;
return Ok((new_root, true, None));
}
let (new_root0, split, added, old) =
Self::insert_rec(&mut build, stack, root, &key, &key_bytes, val_ref)?;
let new_root = if let Some(s) = split {
let root_node = BNode {
leaf: false,
keys: vec![s.key],
vals: vec![s.val],
children: vec![new_root0, s.right],
};
build.emit(&root_node)?
} else {
new_root0
};
Ok((new_root, added, old))
})();
match built {
Ok((new_root, added, old)) => {
let new_node_offs: Vec<u64> = build.writes.iter().map(|(o, _)| *o).collect();
let mut writes = core::mem::take(&mut build.writes);
writes.push(w8(handle + ROOT_OFF, new_root));
if added {
writes.push(w8(handle + LEN_OFF, len + 1));
}
match stack.set_batched(writes) {
Ok(()) => {
for off in &build.freed {
let _ = unsafe {
dealloc_range(
allocator,
BStackRange::new(*off, build.node_size),
)
};
}
Ok(old.map(|o| unsafe { BStackOwned::from_raw(Self::value_at(o)) }))
}
Err(e) => {
for off in new_node_offs {
let _ = unsafe {
dealloc_range(allocator, BStackRange::new(off, build.node_size))
};
}
Err(e)
}
}
}
Err(e) => {
for (off, _) in &build.writes {
let _ = unsafe {
dealloc_range(allocator, BStackRange::new(*off, build.node_size))
};
}
Err(e)
}
}
})();
value.finish_handback(outcome)
}
pub fn get(&self, stack: &BStack, key: &K) -> io::Result<Option<V>> {
let mut off = read_u64(stack, self.range.start() + ROOT_OFF)?;
let ksize = Self::ksize();
let vals_off = Self::vals_off();
let children_off = Self::children_off();
let mut scratch = Scratch::new();
let node_size = Self::node_size() as usize;
let mut depth = 0u32;
while off != 0 {
depth += 1;
if depth > MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let buf = scratch.buf(node_size);
stack.get_into(off, buf)?;
let nkeys = get_u64(&buf[NKEYS_OFF..]) as usize;
if nkeys > MAXKEYS {
return Err(io_error!("corrupt B-tree node: key count exceeds capacity"));
}
let leaf = get_u64(&buf[LEAF_OFF..]) != 0;
let mut i = nkeys;
let mut exact = false;
for j in 0..nkeys {
let ko = KEYS_OFF + j * ksize;
match key.cmp(&Self::read_key(&buf[ko..ko + ksize])) {
Ordering::Less => {
i = j;
break;
}
Ordering::Equal => {
i = j;
exact = true;
break;
}
Ordering::Greater => {}
}
}
if exact {
return Ok(Some(Self::value_at(get_u64(&buf[vals_off + i * 8..]))));
}
if leaf {
return Ok(None);
}
off = get_u64(&buf[children_off + i * 8..]);
}
Ok(None)
}
pub fn contains_key(&self, stack: &BStack, key: &K) -> io::Result<bool> {
Ok(self.get(stack, key)?.is_some())
}
pub fn get_or_insert_with<A, F>(&self, allocator: &A, key: K, f: F) -> io::Result<(V, bool)>
where
A: BStackRaiiAllocator,
F: FnOnce() -> io::Result<BStackOwned<V>>,
{
if let Some(v) = self.get(allocator.stack(), &key)? {
return Ok((v, false));
}
let value = f()?;
let vref = value.handle().range().start();
if let Some(old) = self
.insert(allocator, key, value)
.map_err(|e| e.discard_freeing(allocator))?
{
old.bstack_drop(allocator)?;
}
Ok((Self::value_at(vref), true))
}
pub fn get_or_insert<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: K,
default: BStackOwned<V>,
) -> io::Result<(V, bool)> {
if let Some(v) = self.get(allocator.stack(), &key)? {
default.bstack_drop(allocator)?;
return Ok((v, false));
}
let vref = default.handle().range().start();
if let Some(old) = self
.insert(allocator, key, default)
.map_err(|e| e.discard_freeing(allocator))?
{
old.bstack_drop(allocator)?;
}
Ok((Self::value_at(vref), true))
}
fn child_nkeys(stack: &BStack, off: u64) -> io::Result<usize> {
let pos = off
.checked_add(NKEYS_OFF as u64)
.ok_or_else(|| io_error!("corrupt B-tree child offset"))?;
let nkeys = get_u64(&{
let mut b = [0u8; 8];
stack.get_into(pos, &mut b)?;
b
}) as usize;
if nkeys > MAXKEYS {
return Err(io_error!("corrupt B-tree node: key count exceeds capacity"));
}
Ok(nkeys)
}
fn max_entry(stack: &BStack, off: u64) -> io::Result<(Vec<u8>, u64)> {
let mut nb = Self::read_node(stack, off)?;
while !nb.leaf {
let child = *nb
.children
.last()
.ok_or_else(|| io_error!("corrupt B-tree: internal node has no children"))?;
nb = Self::read_node(stack, child)?;
}
let i = nb
.keys
.len()
.checked_sub(1)
.ok_or_else(|| io_error!("corrupt B-tree: empty leaf node"))?;
Ok((nb.keys[i].clone(), nb.vals[i]))
}
fn min_entry(stack: &BStack, off: u64) -> io::Result<(Vec<u8>, u64)> {
let mut nb = Self::read_node(stack, off)?;
while !nb.leaf {
let child = *nb
.children
.first()
.ok_or_else(|| io_error!("corrupt B-tree: internal node has no children"))?;
nb = Self::read_node(stack, child)?;
}
if nb.keys.is_empty() {
return Err(io_error!("corrupt B-tree: empty leaf node"));
}
Ok((nb.keys[0].clone(), nb.vals[0]))
}
fn delete_off(
build: &mut Build<'_, impl BStackRaiiAllocator>,
stack: &BStack,
off: u64,
key: &K,
) -> io::Result<(u64, Option<u64>)> {
let nb = Self::read_node(stack, off)?;
build.freed.push(off);
let (nb2, val) = Self::delete_bnode(build, stack, nb, key)?;
Ok((build.emit(&nb2)?, val))
}
fn delete_bnode(
build: &mut Build<'_, impl BStackRaiiAllocator>,
stack: &BStack,
mut nb: BNode,
key: &K,
) -> io::Result<(BNode, Option<u64>)> {
let (i, found) = Self::search(&nb, key);
if found {
if nb.leaf {
let v = nb.vals.remove(i);
nb.keys.remove(i);
return Ok((nb, Some(v)));
}
let removed = nb.vals[i];
let yc = Self::child_nkeys(stack, nb.children[i])?;
let zc = Self::child_nkeys(stack, nb.children[i + 1])?;
if yc >= T {
let (pk, pv) = Self::max_entry(stack, nb.children[i])?;
nb.keys[i] = pk.clone();
nb.vals[i] = pv;
let (new_y, _) =
Self::delete_off(build, stack, nb.children[i], &Self::read_key(&pk))?;
nb.children[i] = new_y;
} else if zc >= T {
let (sk, sv) = Self::min_entry(stack, nb.children[i + 1])?;
nb.keys[i] = sk.clone();
nb.vals[i] = sv;
let (new_z, _) =
Self::delete_off(build, stack, nb.children[i + 1], &Self::read_key(&sk))?;
nb.children[i + 1] = new_z;
} else {
let y_off = nb.children[i];
let z_off = nb.children[i + 1];
let mut y = Self::read_node(stack, y_off)?;
build.freed.push(y_off);
let mut z = Self::read_node(stack, z_off)?;
build.freed.push(z_off);
let sk = nb.keys.remove(i);
let sv = nb.vals.remove(i);
nb.children.remove(i + 1);
y.keys.push(sk);
y.vals.push(sv);
y.keys.append(&mut z.keys);
y.vals.append(&mut z.vals);
if !y.leaf {
y.children.append(&mut z.children);
}
let (y2, _) = Self::delete_bnode(build, stack, y, key)?;
nb.children[i] = build.emit(&y2)?;
}
return Ok((nb, Some(removed)));
}
if nb.leaf {
return Ok((nb, None)); }
if Self::child_nkeys(stack, nb.children[i])? >= T {
let (new_c, val) = Self::delete_off(build, stack, nb.children[i], key)?;
nb.children[i] = new_c;
return Ok((nb, val));
}
let n = nb.keys.len();
if i > 0 && Self::child_nkeys(stack, nb.children[i - 1])? >= T {
let ci_off = nb.children[i];
let ls_off = nb.children[i - 1];
let mut ci = Self::read_node(stack, ci_off)?;
build.freed.push(ci_off);
let mut ls = Self::read_node(stack, ls_off)?;
build.freed.push(ls_off);
ci.keys.insert(0, nb.keys[i - 1].clone());
ci.vals.insert(0, nb.vals[i - 1]);
if !ci.leaf {
ci.children.insert(0, ls.children.pop().unwrap());
}
nb.keys[i - 1] = ls.keys.pop().unwrap();
nb.vals[i - 1] = ls.vals.pop().unwrap();
nb.children[i - 1] = build.emit(&ls)?;
let (ci2, val) = Self::delete_bnode(build, stack, ci, key)?;
nb.children[i] = build.emit(&ci2)?;
return Ok((nb, val));
}
if i < n && Self::child_nkeys(stack, nb.children[i + 1])? >= T {
let ci_off = nb.children[i];
let rs_off = nb.children[i + 1];
let mut ci = Self::read_node(stack, ci_off)?;
build.freed.push(ci_off);
let mut rs = Self::read_node(stack, rs_off)?;
build.freed.push(rs_off);
ci.keys.push(nb.keys[i].clone());
ci.vals.push(nb.vals[i]);
if !ci.leaf {
ci.children.push(rs.children.remove(0));
}
nb.keys[i] = rs.keys.remove(0);
nb.vals[i] = rs.vals.remove(0);
nb.children[i + 1] = build.emit(&rs)?;
let (ci2, val) = Self::delete_bnode(build, stack, ci, key)?;
nb.children[i] = build.emit(&ci2)?;
return Ok((nb, val));
}
if i < n {
let ci_off = nb.children[i];
let rs_off = nb.children[i + 1];
let mut ci = Self::read_node(stack, ci_off)?;
build.freed.push(ci_off);
let mut rs = Self::read_node(stack, rs_off)?;
build.freed.push(rs_off);
let sk = nb.keys.remove(i);
let sv = nb.vals.remove(i);
nb.children.remove(i + 1);
ci.keys.push(sk);
ci.vals.push(sv);
ci.keys.append(&mut rs.keys);
ci.vals.append(&mut rs.vals);
if !ci.leaf {
ci.children.append(&mut rs.children);
}
let (ci2, val) = Self::delete_bnode(build, stack, ci, key)?;
nb.children[i] = build.emit(&ci2)?;
Ok((nb, val))
} else {
let ls_off = nb.children[i - 1];
let ci_off = nb.children[i];
let mut ls = Self::read_node(stack, ls_off)?;
build.freed.push(ls_off);
let mut ci = Self::read_node(stack, ci_off)?;
build.freed.push(ci_off);
let sk = nb.keys.remove(i - 1);
let sv = nb.vals.remove(i - 1);
nb.children.remove(i);
ls.keys.push(sk);
ls.vals.push(sv);
ls.keys.append(&mut ci.keys);
ls.vals.append(&mut ci.vals);
if !ls.leaf {
ls.children.append(&mut ci.children);
}
let (ls2, val) = Self::delete_bnode(build, stack, ls, key)?;
nb.children[i - 1] = build.emit(&ls2)?;
Ok((nb, val))
}
}
pub fn remove<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: &K,
) -> io::Result<Option<BStackOwned<V>>> {
let handle = self.range.start();
let stack = allocator.stack();
let [root, len] = read_fields::<2>(stack, handle + ROOT_OFF)?;
if root == 0 || self.get(stack, key)?.is_none() {
return Ok(None);
}
let mut build = Build {
allocator,
node_size: Self::node_size(),
ksize: Self::ksize(),
vals_off: Self::vals_off(),
children_off: Self::children_off(),
writes: Vec::new(),
freed: Vec::new(),
};
let built: io::Result<(u64, u64)> = (|| {
let nb = Self::read_node(stack, root)?;
build.freed.push(root);
let (root_nb, val) = Self::delete_bnode(&mut build, stack, nb, key)?;
let val = val.ok_or_else(|| io_error!("corrupt B-tree: key vanished mid-delete"))?;
let new_root = if root_nb.keys.is_empty() {
if root_nb.leaf {
0
} else {
*root_nb
.children
.first()
.ok_or_else(|| io_error!("corrupt B-tree: internal node has no children"))?
}
} else {
build.emit(&root_nb)?
};
Ok((new_root, val))
})();
match built {
Ok((new_root, val)) => {
let new_node_offs: Vec<u64> = build.writes.iter().map(|(o, _)| *o).collect();
let mut writes = core::mem::take(&mut build.writes);
writes.push(w8(handle + ROOT_OFF, new_root));
writes.push(w8(handle + LEN_OFF, len - 1));
match stack.set_batched(writes) {
Ok(()) => {
for off in &build.freed {
let _ = unsafe {
dealloc_range(allocator, BStackRange::new(*off, build.node_size))
};
}
Ok(Some(unsafe { BStackOwned::from_raw(Self::value_at(val)) }))
}
Err(e) => {
for off in new_node_offs {
let _ = unsafe {
dealloc_range(allocator, BStackRange::new(off, build.node_size))
};
}
Err(e)
}
}
}
Err(e) => {
for (off, _) in &build.writes {
let _ = unsafe {
dealloc_range(allocator, BStackRange::new(*off, build.node_size))
};
}
Err(e)
}
}
}
pub fn first(&self, stack: &BStack) -> io::Result<Option<(K, V)>> {
self.extreme(stack, true)
}
pub fn last(&self, stack: &BStack) -> io::Result<Option<(K, V)>> {
self.extreme(stack, false)
}
fn extreme(&self, stack: &BStack, leftmost: bool) -> io::Result<Option<(K, V)>> {
let mut off = read_u64(stack, self.range.start() + ROOT_OFF)?;
if off == 0 {
return Ok(None);
}
let mut depth = 0u32;
loop {
depth += 1;
if depth > MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let nb = Self::read_node(stack, off)?;
if nb.leaf {
let i = if leftmost { 0 } else { nb.keys.len() - 1 };
return Ok(Some((
Self::read_key(&nb.keys[i]),
Self::value_at(nb.vals[i]),
)));
}
off = if leftmost {
nb.children[0]
} else {
nb.children[nb.keys.len()]
};
}
}
pub fn to_vec(&self, stack: &BStack) -> io::Result<Vec<(K, V)>> {
let mut out = Vec::new();
let root = read_u64(stack, self.range.start() + ROOT_OFF)?;
Self::collect(stack, root, 0, &mut out)?;
Ok(out)
}
fn collect(stack: &BStack, off: u64, depth: u32, out: &mut Vec<(K, V)>) -> io::Result<()> {
if off == 0 {
return Ok(());
}
if depth >= MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let nb = Self::read_node(stack, off)?;
for i in 0..nb.keys.len() {
if !nb.leaf {
Self::collect(stack, nb.children[i], depth + 1, out)?;
}
out.push((Self::read_key(&nb.keys[i]), Self::value_at(nb.vals[i])));
}
if !nb.leaf {
Self::collect(stack, nb.children[nb.keys.len()], depth + 1, out)?;
}
Ok(())
}
pub fn iter<'a>(&self, stack: &'a BStack) -> io::Result<BTreeMapIter<'a, K, V>> {
let [root, len] = read_fields::<2>(stack, self.range.start() + ROOT_OFF)?;
let frames = Self::descend_left(stack, root)?;
Ok(BTreeMapIter {
stack,
block_off: self.range.start(),
root0: root,
len0: len,
frames,
hi: None,
_marker: PhantomData,
})
}
pub fn range<'a>(&self, stack: &'a BStack, lo: K, hi: K) -> io::Result<BTreeMapIter<'a, K, V>> {
let [root, len] = read_fields::<2>(stack, self.range.start() + ROOT_OFF)?;
let frames = Self::seek(stack, root, &lo)?;
Ok(BTreeMapIter {
stack,
block_off: self.range.start(),
root0: root,
len0: len,
frames,
hi: Some(hi),
_marker: PhantomData,
})
}
fn descend_left(stack: &BStack, mut cur: u64) -> io::Result<Vec<(BNode, usize)>> {
let mut frames = Vec::new();
while cur != 0 {
if frames.len() as u32 >= MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let n = Self::read_node(stack, cur)?;
let next = if n.leaf { 0 } else { n.children[0] };
let leaf = n.leaf;
frames.push((n, 0));
if leaf {
break;
}
cur = next;
}
Ok(frames)
}
fn seek(stack: &BStack, mut cur: u64, lo: &K) -> io::Result<Vec<(BNode, usize)>> {
let mut frames = Vec::new();
while cur != 0 {
if frames.len() as u32 >= MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let n = Self::read_node(stack, cur)?;
let (i, exact) = Self::search(&n, lo);
let descend = if n.leaf || exact {
None
} else {
Some(n.children[i])
};
frames.push((n, i));
match descend {
Some(c) => cur = c,
None => break,
}
}
Ok(frames)
}
fn drop_subtree<A: BStackRaiiAllocator>(
stack: &BStack,
off: u64,
allocator: &A,
depth: u32,
) -> io::Result<()> {
if off == 0 {
return Ok(());
}
if depth >= MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let nb = Self::read_node(stack, off)?;
if !nb.leaf {
for &c in &nb.children {
Self::drop_subtree(stack, c, allocator, depth + 1)?;
}
}
for &v in &nb.vals {
if v != 0 {
let owned = unsafe { BStackOwned::from_raw(Self::value_at(v)) };
owned.bstack_drop(allocator)?;
}
}
unsafe { dealloc_range(allocator, BStackRange::new(off, Self::node_size()))? };
Ok(())
}
fn clone_subtree<A: BStackRaiiAllocator>(
stack: &BStack,
off: u64,
allocator: &A,
plan: &mut ClonePlan,
depth: u32,
) -> io::Result<u64> {
if off == 0 {
return Ok(0);
}
if depth >= MAX_TREE_DEPTH {
return Err(depth_exceeded());
}
let mut buf = vec![0u8; Self::node_size() as usize];
stack.get_into(off, &mut buf)?;
let nkeys = get_u64(&buf[NKEYS_OFF..]) as usize;
if nkeys > MAXKEYS {
return Err(io_error!("corrupt B-tree node: key count exceeds capacity"));
}
let leaf = get_u64(&buf[LEAF_OFF..]) != 0;
let vals_off = Self::vals_off();
let children_off = Self::children_off();
for i in 0..nkeys {
let vo = vals_off + i * 8;
let vref = get_u64(&buf[vo..]);
let cloned = Self::value_at(vref)
.__bstack_clone_into(allocator, plan)?
.start();
buf[vo..vo + 8].copy_from_slice(&cloned.to_le_bytes());
}
if !leaf {
for i in 0..=nkeys {
let co = children_off + i * 8;
let child = get_u64(&buf[co..]);
let new_child = Self::clone_subtree(stack, child, allocator, plan, depth + 1)?;
buf[co..co + 8].copy_from_slice(&new_child.to_le_bytes());
}
}
let dst = plan.alloc_raw(allocator, Self::node_size())?;
plan.write(dst.start(), buf);
Ok(dst.start())
}
}
impl<K: Pod + Ord, V: BStackBlock> BStackCast for BStackBTreeMap<K, V> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'T', b'r', b'e', b'e', 0x80, 0x81, 0x82, 0x83]);
BASE.mix(EightCC::new((size_of::<K>() as u64).to_le_bytes()))
.mix(<V as BStackCast>::eightcc())
}
}
impl<K: Pod + Ord, V: BStackBlock> crate::types::traits::BStackEmbeddable for BStackBTreeMap<K, V> {}
impl<K: Pod + Ord, V: BStackBlock> BStackBlock for BStackBTreeMap<K, V> {
type OnDisk = TreeOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackBTreeMap {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let root = read_u64(allocator.stack(), range.start() + ROOT_OFF)?;
Self::drop_subtree(allocator.stack(), root, allocator, 0)
}
fn __bstack_clone_children_inplace<A: BStackRaiiAllocator>(
&self,
allocator: &A,
plan: &mut ClonePlan,
) -> io::Result<Self::OnDisk> {
let handle = self.range.start();
let [root, len] = read_fields::<2>(allocator.stack(), handle + ROOT_OFF)?;
let new_root = Self::clone_subtree(allocator.stack(), root, allocator, plan, 0)?;
let od = TreeOnDisk {
header: BlockHeader {
size: TREE_SIZE,
tag: Self::eightcc(),
},
root: new_root,
len,
};
Ok(od)
}
}
impl<K: Pod + Ord, V: BStackBlock> TryCloneIn for BStackBTreeMap<K, V> {}
pub struct BTreeMapIter<'a, K: Pod + Ord, V: BStackBlock> {
stack: &'a BStack,
block_off: u64,
root0: u64,
len0: u64,
frames: Vec<(BNode, usize)>,
hi: Option<K>,
_marker: PhantomData<fn() -> (K, V)>,
}
impl<'a, K: Pod + Ord, V: BStackBlock> Iterator for BTreeMapIter<'a, K, V> {
type Item = io::Result<(K, V)>;
fn next(&mut self) -> Option<Self::Item> {
if !self.frames.is_empty() {
match read_fields::<2>(self.stack, self.block_off + ROOT_OFF) {
Ok([root, len]) if root == self.root0 && len == self.len0 => {}
Ok(_) => {
self.frames.clear();
return Some(Err(io_error!(
"BStackBTreeMap was mutated during iteration (its root changed); \
the iterator is invalidated"
)));
}
Err(e) => {
self.frames.clear();
return Some(Err(e));
}
}
}
loop {
let (node, i) = self.frames.last()?;
let i = *i;
if i >= node.keys.len() {
self.frames.pop();
continue;
}
let key = BStackBTreeMap::<K, V>::read_key(&node.keys[i]);
let vref = node.vals[i];
let leaf = node.leaf;
let child = if leaf { 0 } else { node.children[i + 1] };
if let Some(ref hi) = self.hi
&& key > *hi
{
self.frames.clear();
return None;
}
self.frames.last_mut().unwrap().1 = i + 1;
if !leaf {
match BStackBTreeMap::<K, V>::descend_left(self.stack, child) {
Ok(mut f) => self.frames.append(&mut f),
Err(e) => {
self.frames.clear();
return Some(Err(e));
}
}
}
return Some(Ok((key, BStackBTreeMap::<K, V>::value_at(vref))));
}
}
}