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::bloom::{BStackCountingBloomFilter, BloomOnDisk};
use super::util::{Scratch, alloc_image, read_fields, w8};
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 TreeSetOnDisk {
pub header: BlockHeader,
pub root: u64,
pub len: u64,
pub bloom: u64,
}
const ROOT_OFF: u64 = HEADER_SIZE; const LEN_OFF: u64 = HEADER_SIZE + 8; const BLOOM_OFF: u64 = HEADER_SIZE + 16; const TREESET_SIZE: u64 = size_of::<TreeSetOnDisk>() as u64;
const BLOOM_SIZE: u64 = size_of::<BloomOnDisk>() 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;
const DEFAULT_ITEMS: u64 = 1024;
const DEFAULT_FP: f64 = 0.01;
struct BNode {
leaf: bool,
keys: Vec<Vec<u8>>,
children: Vec<u64>,
}
struct Split {
key: Vec<u8>,
right: u64,
}
struct Build<'a, A: BStackRaiiAllocator> {
allocator: &'a A,
node_size: u64,
ksize: 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, 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 BStackBTreeSet<K: Pod + Ord> {
range: BStackRange,
_marker: PhantomData<fn() -> K>,
}
impl<K: Pod + Ord> BStackBTreeSet<K> {
const fn ksize() -> usize {
size_of::<K>()
}
const fn children_off() -> usize {
KEYS_OFF + MAXKEYS * Self::ksize()
}
const fn node_size() -> u64 {
(Self::children_off() + MAXCHILDREN * 8) as u64
}
fn read_key(bytes: &[u8]) -> K {
bytemuck::pod_read_unaligned::<K>(&bytes[..Self::ksize()])
}
fn bloom(&self, stack: &BStack) -> io::Result<BStackCountingBloomFilter<K>> {
let off = read_u64(stack, self.range.start() + BLOOM_OFF)?;
Ok(unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
off, BLOOM_SIZE,
))
})
}
pub fn new<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<BStackOwned<Self>> {
Self::with_capacity(allocator, DEFAULT_ITEMS, DEFAULT_FP)
}
pub fn with_capacity<A: BStackRaiiAllocator>(
allocator: &A,
expected_items: u64,
fp_rate: f64,
) -> io::Result<BStackOwned<Self>> {
let bloom =
BStackCountingBloomFilter::<K>::with_capacity(allocator, expected_items, fp_rate)?;
let bloom_off = bloom.into_inner().range().start();
let od = TreeSetOnDisk {
header: BlockHeader {
size: TREESET_SIZE,
tag: Self::eightcc(),
},
root: 0,
len: 0,
bloom: bloom_off,
};
match alloc_image(allocator, bytemuck::bytes_of(&od)) {
Ok(range) => Ok(unsafe { BStackOwned::from_raw(Self::from_range(range)) }),
Err(e) => {
let bloom = unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
bloom_off, BLOOM_SIZE,
))
};
let _ = unsafe { BStackOwned::from_raw(bloom) }.bstack_drop(allocator);
Err(e)
}
}
}
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 children_off = Self::children_off();
let mut keys = Vec::with_capacity(nkeys);
for i in 0..nkeys {
let ko = KEYS_OFF + i * ksize;
keys.push(b[ko..ko + ksize].to_vec());
}
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,
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 med_key = nb.keys.pop().unwrap();
let right = BNode {
leaf: nb.leaf,
keys: right_keys,
children: right_children,
};
(
nb,
Split {
key: med_key,
right: 0,
},
right,
)
}
fn insert_rec(
build: &mut Build<'_, impl BStackRaiiAllocator>,
stack: &BStack,
off: u64,
key: &K,
key_bytes: &[u8],
) -> io::Result<(u64, Option<Split>)> {
let mut nb = Self::read_node(stack, off)?;
build.freed.push(off);
let (i, _exact) = Self::search(&nb, key);
if nb.leaf {
nb.keys.insert(i, key_bytes.to_vec());
} else {
let child = nb.children[i];
let (new_child, child_split) = Self::insert_rec(build, stack, child, key, key_bytes)?;
nb.children[i] = new_child;
if let Some(s) = child_split {
nb.keys.insert(i, s.key);
nb.children.insert(i + 1, s.right);
}
}
if nb.keys.len() <= MAXKEYS {
Ok((build.emit(&nb)?, None))
} else {
let (left, mut split, right) = Self::split(nb);
split.right = build.emit(&right)?;
Ok((build.emit(&left)?, Some(split)))
}
}
pub fn insert<A: BStackRaiiAllocator>(&self, allocator: &A, key: K) -> io::Result<bool> {
if self.tree_contains(allocator.stack(), &key)? {
return Ok(false);
}
let key_bytes = bytemuck::bytes_of(&key).to_vec();
self.bloom(allocator.stack())?.insert(allocator, &key)?;
let handle = self.range.start();
let stack = allocator.stack();
let [root, len] = read_fields::<2>(stack, handle + ROOT_OFF)?;
let mut build = Build {
allocator,
node_size: Self::node_size(),
ksize: Self::ksize(),
children_off: Self::children_off(),
writes: Vec::new(),
freed: Vec::new(),
};
let built: io::Result<u64> = (|| {
if root == 0 {
let leaf = BNode {
leaf: true,
keys: vec![key_bytes.clone()],
children: Vec::new(),
};
return build.emit(&leaf);
}
let (new_root0, split) = Self::insert_rec(&mut build, stack, root, &key, &key_bytes)?;
if let Some(s) = split {
let root_node = BNode {
leaf: false,
keys: vec![s.key],
children: vec![new_root0, s.right],
};
build.emit(&root_node)
} else {
Ok(new_root0)
}
})();
match built {
Ok(new_root) => {
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(true)
}
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 contains(&self, stack: &BStack, key: &K) -> io::Result<bool> {
if !self.bloom(stack)?.contains(stack, key)? {
return Ok(false);
}
self.tree_contains(stack, key)
}
fn tree_contains(&self, stack: &BStack, key: &K) -> io::Result<bool> {
let mut off = read_u64(stack, self.range.start() + ROOT_OFF)?;
let ksize = Self::ksize();
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;
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 => return Ok(true),
Ordering::Greater => {}
}
}
if leaf {
return Ok(false);
}
off = get_u64(&buf[children_off + i * 8..]);
}
Ok(false)
}
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 mut b = [0u8; 8];
stack.get_into(pos, &mut b)?;
let nkeys = get_u64(&b) as usize;
if nkeys > MAXKEYS {
return Err(io_error!("corrupt B-tree node: key count exceeds capacity"));
}
Ok(nkeys)
}
fn edge_key(stack: &BStack, off: u64, rightmost: bool) -> io::Result<Vec<u8>> {
let mut nb = Self::read_node(stack, off)?;
while !nb.leaf {
let c = if rightmost {
nb.children.last()
} else {
nb.children.first()
}
.copied()
.ok_or_else(|| io_error!("corrupt B-tree: internal node has no children"))?;
nb = Self::read_node(stack, c)?;
}
if nb.keys.is_empty() {
return Err(io_error!("corrupt B-tree: empty leaf node"));
}
let i = if rightmost { nb.keys.len() - 1 } else { 0 };
Ok(nb.keys[i].clone())
}
fn delete_off(
build: &mut Build<'_, impl BStackRaiiAllocator>,
stack: &BStack,
off: u64,
key: &K,
) -> io::Result<(u64, bool)> {
let nb = Self::read_node(stack, off)?;
build.freed.push(off);
let (nb2, found) = Self::delete_bnode(build, stack, nb, key)?;
Ok((build.emit(&nb2)?, found))
}
fn delete_bnode(
build: &mut Build<'_, impl BStackRaiiAllocator>,
stack: &BStack,
mut nb: BNode,
key: &K,
) -> io::Result<(BNode, bool)> {
let (i, found) = Self::search(&nb, key);
if found {
if nb.leaf {
nb.keys.remove(i);
return Ok((nb, true));
}
let yc = Self::child_nkeys(stack, nb.children[i])?;
let zc = Self::child_nkeys(stack, nb.children[i + 1])?;
if yc >= T {
let pk = Self::edge_key(stack, nb.children[i], true)?;
nb.keys[i] = pk.clone();
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 = Self::edge_key(stack, nb.children[i + 1], false)?;
nb.keys[i] = sk.clone();
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);
nb.children.remove(i + 1);
y.keys.push(sk);
y.keys.append(&mut z.keys);
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, true));
}
if nb.leaf {
return Ok((nb, false));
}
if Self::child_nkeys(stack, nb.children[i])? >= T {
let (new_c, found) = Self::delete_off(build, stack, nb.children[i], key)?;
nb.children[i] = new_c;
return Ok((nb, found));
}
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());
if !ci.leaf {
ci.children.insert(0, ls.children.pop().unwrap());
}
nb.keys[i - 1] = ls.keys.pop().unwrap();
nb.children[i - 1] = build.emit(&ls)?;
let (ci2, found) = Self::delete_bnode(build, stack, ci, key)?;
nb.children[i] = build.emit(&ci2)?;
return Ok((nb, found));
}
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());
if !ci.leaf {
ci.children.push(rs.children.remove(0));
}
nb.keys[i] = rs.keys.remove(0);
nb.children[i + 1] = build.emit(&rs)?;
let (ci2, found) = Self::delete_bnode(build, stack, ci, key)?;
nb.children[i] = build.emit(&ci2)?;
return Ok((nb, found));
}
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);
nb.children.remove(i + 1);
ci.keys.push(sk);
ci.keys.append(&mut rs.keys);
if !ci.leaf {
ci.children.append(&mut rs.children);
}
let (ci2, found) = Self::delete_bnode(build, stack, ci, key)?;
nb.children[i] = build.emit(&ci2)?;
Ok((nb, found))
} 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);
nb.children.remove(i);
ls.keys.push(sk);
ls.keys.append(&mut ci.keys);
if !ls.leaf {
ls.children.append(&mut ci.children);
}
let (ls2, found) = Self::delete_bnode(build, stack, ls, key)?;
nb.children[i - 1] = build.emit(&ls2)?;
Ok((nb, found))
}
}
pub fn remove<A: BStackRaiiAllocator>(&self, allocator: &A, key: &K) -> io::Result<bool> {
let handle = self.range.start();
let stack = allocator.stack();
if !self.tree_contains(stack, key)? {
return Ok(false);
}
let [root, len] = read_fields::<2>(stack, handle + ROOT_OFF)?;
let mut build = Build {
allocator,
node_size: Self::node_size(),
ksize: Self::ksize(),
children_off: Self::children_off(),
writes: Vec::new(),
freed: Vec::new(),
};
let built: io::Result<u64> = (|| {
let nb = Self::read_node(stack, root)?;
build.freed.push(root);
let (root_nb, _) = Self::delete_bnode(&mut build, stack, nb, key)?;
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)
})();
match built {
Ok(new_root) => {
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))
};
}
let _ = self.bloom(stack).and_then(|b| b.remove(allocator, key));
Ok(true)
}
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>> {
self.extreme(stack, true)
}
pub fn last(&self, stack: &BStack) -> io::Result<Option<K>> {
self.extreme(stack, false)
}
fn extreme(&self, stack: &BStack, leftmost: bool) -> io::Result<Option<K>> {
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])));
}
off = if leftmost {
nb.children[0]
} else {
nb.children[nb.keys.len()]
};
}
}
pub fn to_vec(&self, stack: &BStack) -> io::Result<Vec<K>> {
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>) -> 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]));
}
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<BTreeSetIter<'a, K>> {
let [root, len] = read_fields::<2>(stack, self.range.start() + ROOT_OFF)?;
let frames = Self::descend_left(stack, root)?;
Ok(BTreeSetIter {
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<BTreeSetIter<'a, K>> {
let [root, len] = read_fields::<2>(stack, self.range.start() + ROOT_OFF)?;
let frames = Self::seek(stack, root, &lo)?;
Ok(BTreeSetIter {
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)?;
}
}
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 children_off = Self::children_off();
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> BStackCast for BStackBTreeSet<K> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'T', b'S', b't', 0x80, 0x81, 0x82, 0x83, 0x84]);
BASE.mix(EightCC::new((size_of::<K>() as u64).to_le_bytes()))
}
}
impl<K: Pod + Ord> crate::types::traits::BStackEmbeddable for BStackBTreeSet<K> {}
impl<K: Pod + Ord> BStackBlock for BStackBTreeSet<K> {
type OnDisk = TreeSetOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackBTreeSet {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let handle = range.start();
let [root, _len, bloom_off] = read_fields::<3>(allocator.stack(), handle + ROOT_OFF)?;
Self::drop_subtree(allocator.stack(), root, allocator, 0)?;
if bloom_off != 0 {
let bloom = unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
bloom_off, BLOOM_SIZE,
))
};
unsafe { BStackOwned::from_raw(bloom) }.bstack_drop(allocator)?;
}
Ok(())
}
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, bloom_off] = read_fields::<3>(allocator.stack(), handle + ROOT_OFF)?;
let new_root = Self::clone_subtree(allocator.stack(), root, allocator, plan, 0)?;
let bloom = unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
bloom_off, BLOOM_SIZE,
))
};
let new_bloom = bloom.__bstack_clone_into(allocator, plan)?.start();
let od = TreeSetOnDisk {
header: BlockHeader {
size: TREESET_SIZE,
tag: Self::eightcc(),
},
root: new_root,
len,
bloom: new_bloom,
};
Ok(od)
}
}
impl<K: Pod + Ord> TryCloneIn for BStackBTreeSet<K> {}
pub struct BTreeSetIter<'a, K: Pod + Ord> {
stack: &'a BStack,
block_off: u64,
root0: u64,
len0: u64,
frames: Vec<(BNode, usize)>,
hi: Option<K>,
_marker: PhantomData<fn() -> K>,
}
impl<'a, K: Pod + Ord> Iterator for BTreeSetIter<'a, K> {
type Item = io::Result<K>;
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!(
"BStackBTreeSet 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 = BStackBTreeSet::<K>::read_key(&node.keys[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 BStackBTreeSet::<K>::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));
}
}
}