{"header":{"message":"Adding sanakirja-core-async","description":null,"timestamp":"2022-11-11T12:24:09.671866679Z","authors":[{}]},"hash":"KK3SBH4P3FBZ3ER344TO6WEK7EX5AFB57UX2G5PKANG3NUF5IQLAC","authors":[{"login":"pmeunier","key":"FZQ2g7VfnzLYM4mtTVDk9HAZjA8Jk9ndkwN1icgbtWUr"}],"deps":{"hashes":[["KK3SBH4P3FBZ3ER344TO6WEK7EX5AFB57UX2G5PKANG3NUF5IQLAC","Adding sanakirja-core-async"],["AA",null],["RLVQDUPYOWVNHTVFCHKNIQYNBRLOFY2UGIJPLD6U5S22AMEF5YSAC","Fixing a double-free error introduced in 1.2.13"],["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","Resetting history"]],"deps":["RLVQDUPYOWVNHTVFCHKNIQYNBRLOFY2UGIJPLD6U5S22AMEF5YSAC"],"known":["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC"]},"hunks":[{"FileAdd":{"meta":{"basename":"sanakirja-core-async","metadata":576},"context":[{"change":2,"pos":2}],"contents":[]}},{"FileAdd":{"meta":{"basename":"src","metadata":576},"context":[{"change":0,"pos":32}],"contents":[]}},{"FileAdd":{"meta":{"basename":"lib.rs","metadata":0},"context":[{"change":0,"pos":49}],"contents":[{"Add":"//! This crate defines tools to implement datastructures that can live"},{"Add":"//! in main memory or on-disk, meaning that their natural habitat is"},{"Add":"//! memory-mapped files, but if that environment is threatened, they"},{"Add":"//! might seek refuge in lower-level environments."},{"Add":"//!"},{"Add":"//! One core building block of this library is the notion of virtual"},{"Add":"//! memory pages, which are allocated and freed by an"},{"Add":"//! externally-provided allocator (see how the `sanakirja` crate does"},{"Add":"//! this). The particular implementation used here is meant to allow a"},{"Add":"//! transactional system with readers reading the structures"},{"Add":"//! concurrently with one writer at a time."},{"Add":"//!"},{"Add":"//! At the moment, only B trees are implemented, as well as the"},{"Add":"//! following general traits:"},{"Add":"//!"},{"Add":"//! - [`LoadPage`] is a trait used to get a pointer to a page. In the"},{"Add":"//! most basic version, this may just return a pointer to the file,"},{"Add":"//! offset by the requested offset. In more sophisticated versions,"},{"Add":"//! this can be used to encrypt and compress pages."},{"Add":"//! - [`AllocPage`] allocates and frees pages, because as"},{"Add":"//! datastructures need to be persisted on disk, we can't rely on"},{"Add":"//! Rust's memory management to do it for us. Users of this crate"},{"Add":"//! don't have to worry about this though."},{"Add":"//!"},{"Add":"//! Moreover, two other traits can be used to store things on pages:"},{"Add":"//! [`Storable`] is a simple trait that all `Sized + Ord` types"},{"Add":"//! without references can readily implement (the [`direct_repr!`]"},{"Add":"//! macro does that). For types containing references to pages"},{"Add":"//! allocated in the database, the comparison function can be"},{"Add":"//! customised. Moreover, these types must supply an iterator over"},{"Add":"//! these references, in order for reference-counting to work properly"},{"Add":"//! when the datastructures referencing these types are forked."},{"Add":"//!"},{"Add":"//! Dynamically-sized types, or types that need to be represented in a"},{"Add":"//! dynamically-sized way, can use the [`UnsizedStorable`] format."},{"Add":"use async_trait::async_trait;"},{"Add":"pub mod btree;"},{"Add":""},{"Add":"/// There's a hard-coded assumption that pages have 4K bytes. This is"},{"Add":"/// true for normal memory pages on almost all platforms."},{"Add":"pub const PAGE_SIZE: usize = 4096;"},{"Add":""},{"Add":"/// Types that can be stored on disk. This trait may be used in"},{"Add":"/// conjunction with `Sized` in order to determine the on-disk size,"},{"Add":"/// or with [`UnsizedStorable`] when special arrangements are needed."},{"Add":"#[async_trait(?Send)]"},{"Add":"pub trait Storable: Send + Sync + core::fmt::Debug {"},{"Add":" /// This is required for B trees, not necessarily for other"},{"Add":" /// structures. The default implementation panics."},{"Add":" fn compare(&self, _b: &Self) -> core::cmp::Ordering {"},{"Add":" unimplemented!()"},{"Add":" }"},{"Add":""},{"Add":" /// If this value is an offset to another page at offset `offset`,"},{"Add":" /// return `Some(offset)`. Return `None` else."},{"Add":" fn page_references(&self) -> Self::PageReferences;"},{"Add":""},{"Add":" /// If this value is an offset to another page at offset `offset`,"},{"Add":" /// return `Some(offset)`. Return `None` else."},{"Add":" async fn drop(&self, txn: &mut T) -> Result<(), T::Error> {"},{"Add":" for p in self.page_references() {"},{"Add":" txn.decr_rc(p).await?;"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" /// An iterator over the offsets to pages contained in this"},{"Add":" /// value. Only values from this crate can generate non-empty"},{"Add":" /// iterators, but combined values (like tuples) must chain the"},{"Add":" /// iterators returned by method `page_offsets`."},{"Add":" type PageReferences: Iterator + Send;"},{"Add":"}"},{"Add":""},{"Add":"/// A macro to implement [`Storable`] on \"plain\" types,"},{"Add":"/// i.e. fixed-sized types that are `repr(C)` and don't hold"},{"Add":"/// references."},{"Add":"#[macro_export]"},{"Add":"macro_rules! direct_repr {"},{"Add":" ($t: ty) => {"},{"Add":" impl Storable for $t {"},{"Add":" type PageReferences = core::iter::Empty;"},{"Add":" fn page_references(&self) -> Self::PageReferences {"},{"Add":" core::iter::empty()"},{"Add":" }"},{"Add":" fn compare(&self, b: &Self) -> core::cmp::Ordering {"},{"Add":" self.cmp(b)"},{"Add":" }"},{"Add":" }"},{"Add":" impl UnsizedStorable for $t {"},{"Add":" const ALIGN: usize = core::mem::align_of::<$t>();"},{"Add":""},{"Add":" /// If `Self::SIZE.is_some()`, this must return the same"},{"Add":" /// value. The default implementation is `Self;:SIZE.unwrap()`."},{"Add":" fn size(&self) -> usize {"},{"Add":" core::mem::size_of::()"},{"Add":" }"},{"Add":""},{"Add":" /// Read the size from an on-page entry."},{"Add":" unsafe fn onpage_size(_: *const u8) -> usize {"},{"Add":" core::mem::size_of::()"},{"Add":" }"},{"Add":""},{"Add":" /// Write to a page. Must not overwrite the allocated size, but"},{"Add":" /// this isn't checked (which is why it's unsafe)."},{"Add":" unsafe fn write_to_page(&self, p: *mut u8) {"},{"Add":" core::ptr::copy_nonoverlapping(self, p as *mut Self, 1)"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn from_raw_ptr<'a>(p: *const u8) -> &'a Self {"},{"Add":" &*(p as *const Self)"},{"Add":" }"},{"Add":" }"},{"Add":" };"},{"Add":"}"},{"Add":""},{"Add":"direct_repr!(());"},{"Add":"direct_repr!(u8);"},{"Add":"direct_repr!(i8);"},{"Add":"direct_repr!(u16);"},{"Add":"direct_repr!(i16);"},{"Add":"direct_repr!(u32);"},{"Add":"direct_repr!(i32);"},{"Add":"direct_repr!(u64);"},{"Add":"direct_repr!(i64);"},{"Add":"direct_repr!([u8; 16]);"},{"Add":""},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"extern crate std;"},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"direct_repr!(std::net::Ipv4Addr);"},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"direct_repr!(std::net::Ipv6Addr);"},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"direct_repr!(std::net::IpAddr);"},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"direct_repr!(std::net::SocketAddr);"},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"direct_repr!(std::time::SystemTime);"},{"Add":"#[cfg(feature = \"std\")]"},{"Add":"direct_repr!(std::time::Duration);"},{"Add":"#[cfg(feature = \"uuid\")]"},{"Add":"direct_repr!(uuid::Uuid);"},{"Add":"#[cfg(feature = \"ed25519\")]"},{"Add":"direct_repr!(ed25519_zebra::VerificationKeyBytes);"},{"Add":""},{"Add":"/// Types that can be stored on disk."},{"Add":"pub trait UnsizedStorable: Storable {"},{"Add":" const ALIGN: usize;"},{"Add":""},{"Add":" /// If `Self::SIZE.is_some()`, this must return the same"},{"Add":" /// value. The default implementation is `Self;:SIZE.unwrap()`."},{"Add":" fn size(&self) -> usize;"},{"Add":""},{"Add":" /// Read the size from an on-page entry. If `Self::SIZE.is_some()`"},{"Add":" /// this must be the same value."},{"Add":" unsafe fn onpage_size(_: *const u8) -> usize;"},{"Add":""},{"Add":" /// Write to a page. Must not overwrite the allocated size, but"},{"Add":" /// this isn't checked (which is why it's unsafe)."},{"Add":" unsafe fn write_to_page(&self, p: *mut u8);"},{"Add":""},{"Add":" unsafe fn from_raw_ptr<'a>(p: *const u8) -> &'a Self;"},{"Add":"}"},{"Add":""},{"Add":"impl Storable for [u8] {"},{"Add":" type PageReferences = core::iter::Empty;"},{"Add":" fn page_references(&self) -> Self::PageReferences {"},{"Add":" core::iter::empty()"},{"Add":" }"},{"Add":" fn compare(&self, b: &Self) -> core::cmp::Ordering {"},{"Add":" self.cmp(b)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl UnsizedStorable for [u8] {"},{"Add":" const ALIGN: usize = 2;"},{"Add":" fn size(&self) -> usize {"},{"Add":" 2 + self.len()"},{"Add":" }"},{"Add":" unsafe fn from_raw_ptr<'a>(p: *const u8) -> &'a Self {"},{"Add":" let len = u16::from_le(*(p as *const u16));"},{"Add":" assert_ne!(len, 0);"},{"Add":" assert_eq!(len & 0xf000, 0);"},{"Add":" core::slice::from_raw_parts(p.add(2), len as usize)"},{"Add":" }"},{"Add":" unsafe fn onpage_size(p: *const u8) -> usize {"},{"Add":" let len = u16::from_le(*(p as *const u16));"},{"Add":" 2 + len as usize"},{"Add":" }"},{"Add":" unsafe fn write_to_page(&self, p: *mut u8) {"},{"Add":" assert!(self.len() <= 510);"},{"Add":" *(p as *mut u16) = (self.len() as u16).to_le();"},{"Add":" core::ptr::copy_nonoverlapping(self.as_ptr(), p.add(2), self.len())"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn read("},{"Add":" k: *const u8,"},{"Add":") -> (*const u8, *const u8) {"},{"Add":" let s = K::onpage_size(k);"},{"Add":" let v = k.add(s);"},{"Add":" let al = v.align_offset(V::ALIGN);"},{"Add":" let v = v.add(al);"},{"Add":" (k, v)"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn entry_size("},{"Add":" k: *const u8,"},{"Add":") -> usize {"},{"Add":" assert_eq!(k.align_offset(K::ALIGN), 0);"},{"Add":" let ks = K::onpage_size(k);"},{"Add":" // next multiple of va, assuming va is a power of 2."},{"Add":" let v_off = (ks + V::ALIGN - 1) & !(V::ALIGN - 1);"},{"Add":" let v_ptr = k.add(v_off);"},{"Add":" let vs = V::onpage_size(v_ptr);"},{"Add":" let ka = K::ALIGN.max(V::ALIGN);"},{"Add":" let size = v_off + vs;"},{"Add":" (size + ka - 1) & !(ka - 1)"},{"Add":"}"},{"Add":""},{"Add":"/// Representation of a mutable or shared page. This is an owned page"},{"Add":"/// (like `Vec` in Rust's std), but we do not know whether we can"},{"Add":"/// mutate it or not."},{"Add":"///"},{"Add":"/// The least-significant bit of the first byte of each page is 1 if"},{"Add":"/// and only if the page was allocated by the current transaction (and"},{"Add":"/// hence isn't visible to any other transaction, meaning we can write"},{"Add":"/// on it)."},{"Add":"#[derive(Debug)]"},{"Add":"#[repr(C)]"},{"Add":"pub struct CowPage {"},{"Add":" pub data: *mut u8,"},{"Add":" pub offset: u64,"},{"Add":"}"},{"Add":""},{"Add":"/// Representation of a borrowed, or immutable page, like a slice in"},{"Add":"/// Rust."},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"#[repr(C)]"},{"Add":"pub struct Page<'a> {"},{"Add":" pub data: &'a [u8; PAGE_SIZE],"},{"Add":" pub offset: u64,"},{"Add":"}"},{"Add":""},{"Add":"impl CowPage {"},{"Add":" /// Borrows the page."},{"Add":" pub fn as_page(&self) -> Page {"},{"Add":" Page {"},{"Add":" data: unsafe { &*(self.data as *const [u8; PAGE_SIZE]) },"},{"Add":" offset: self.offset,"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" #[cfg(feature = \"crc32\")]"},{"Add":" pub fn crc(&self, hasher: &crc32fast::Hasher) -> u32 {"},{"Add":" let mut hasher = hasher.clone();"},{"Add":" hasher.reset();"},{"Add":" // Hash the beginning and the end of the page (i.e. remove"},{"Add":" // the CRC)."},{"Add":" unsafe {"},{"Add":" // Remove the dirty bit."},{"Add":" let x = [(*self.data) & 0xfe];"},{"Add":" hasher.update(&x[..]);"},{"Add":" hasher.update(core::slice::from_raw_parts(self.data.add(1), 3));"},{"Add":" hasher.update(core::slice::from_raw_parts("},{"Add":" self.data.add(8),"},{"Add":" PAGE_SIZE - 8,"},{"Add":" ));"},{"Add":" }"},{"Add":" hasher.finalize()"},{"Add":" }"},{"Add":""},{"Add":" #[cfg(feature = \"crc32\")]"},{"Add":" pub fn crc_check(&self, hasher: &crc32fast::Hasher) -> bool {"},{"Add":" let crc = unsafe { u32::from_le(*(self.data as *const u32).add(1)) };"},{"Add":" self.crc(hasher) == crc"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// An owned page on which we can write. This is just a wrapper around"},{"Add":"/// `CowPage` to avoid checking the \"dirty\" bit at runtime."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct MutPage(pub CowPage);"},{"Add":""},{"Add":"#[cfg(not(feature = \"crc32\"))]"},{"Add":"pub fn clear_dirty(data: &mut [u8]) {"},{"Add":" data[0] &= 0xfe"},{"Add":"}"},{"Add":""},{"Add":"#[cfg(feature = \"crc32\")]"},{"Add":"pub fn clear_dirty(data: &mut [u8], hasher: &crc32fast::Hasher) {"},{"Add":" unsafe {"},{"Add":" data[0] &= 0xfe;"},{"Add":" let crc = (self.0.data.as_mut_ptr() as *mut u32).add(1);"},{"Add":" *crc = self.0.crc(hasher)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"impl MutPage {"},{"Add":" #[cfg(not(feature = \"crc32\"))]"},{"Add":" pub fn clear_dirty(&mut self) {"},{"Add":" unsafe { *self.0.data &= 0xfe }"},{"Add":" }"},{"Add":""},{"Add":" #[cfg(feature = \"crc32\")]"},{"Add":" pub fn clear_dirty(&mut self, hasher: &crc32fast::Hasher) {"},{"Add":" unsafe {"},{"Add":" *self.0.data &= 0xfe;"},{"Add":" let crc = (self.0.data as *mut u32).add(1);"},{"Add":" *crc = self.0.crc(hasher)"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe impl Sync for CowPage {}"},{"Add":"unsafe impl Send for CowPage {}"},{"Add":""},{"Add":"impl CowPage {"},{"Add":" /// Checks the dirty bit of a page."},{"Add":" pub fn is_dirty(&self) -> bool {"},{"Add":" unsafe { (*self.data) & 1 != 0 }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Trait for loading a page."},{"Add":"#[async_trait(?Send)]"},{"Add":"pub trait LoadPage: Send + Sync {"},{"Add":" type Error;"},{"Add":" /// Loading a page."},{"Add":" async fn load_page(&self, off: u64) -> Result;"},{"Add":""},{"Add":" /// Reference-counting. Since reference-counts are designed to be"},{"Add":" /// storable into B trees by external allocators, pages referenced"},{"Add":" /// once aren't stored, and hence are indistinguishable from pages"},{"Add":" /// that are never referenced. The default implementation returns"},{"Add":" /// 0."},{"Add":" ///"},{"Add":" /// This has the extra benefit of requiring less disk space, and"},{"Add":" /// isn't more unsafe than storing the reference count, since we"},{"Add":" /// aren't supposed to hold a reference to a page with \"logical"},{"Add":" /// RC\" 0, so storing \"1\" for that page would be redundant anyway."},{"Add":" async fn rc(&self, _off: u64) -> Result {"},{"Add":" Ok(0)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Trait for allocating and freeing pages."},{"Add":"#[async_trait(?Send)]"},{"Add":"pub trait AllocPage: LoadPage {"},{"Add":" /// Allocate a new page."},{"Add":" async fn alloc_page(&mut self) -> Result;"},{"Add":" /// Increment the page's reference count."},{"Add":" async fn incr_rc(&mut self, off: u64) -> Result;"},{"Add":" /// Decrement the page's reference count, assuming the page was"},{"Add":" /// first allocated by another transaction. If the RC reaches 0,"},{"Add":" /// free the page. Must return the new RC (0 if freed)."},{"Add":" async fn decr_rc(&mut self, off: u64) -> Result;"},{"Add":" /// Same as [`Self::decr_rc`], but for pages allocated by the current"},{"Add":" /// transaction. This is an important distinction, as pages"},{"Add":" /// allocated by the current transaction can be reused immediately"},{"Add":" /// after being freed."},{"Add":" async fn decr_rc_owned(&mut self, off: u64) -> Result;"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"btree","metadata":576},"context":[{"change":0,"pos":49}],"contents":[]}},{"FileAdd":{"meta":{"basename":"put_async.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"//! Insertions into a B tree."},{"Add":"use super::cursor::*;"},{"Add":"use super::*;"},{"Add":""},{"Add":"/// The representation of the update to a page."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Ok {"},{"Add":" /// The new page, possibly the same as the previous version."},{"Add":" pub page: MutPage,"},{"Add":" /// The freed page, or 0 if no page was freed."},{"Add":" pub freed: u64,"},{"Add":"}"},{"Add":""},{"Add":"/// The result of an insertion, i.e. either an update or a split."},{"Add":"#[derive(Debug)]"},{"Add":"pub enum Put<'a, K: ?Sized, V: ?Sized> {"},{"Add":" Ok(Ok),"},{"Add":" Split {"},{"Add":" split_key: &'a K,"},{"Add":" split_value: &'a V,"},{"Add":" left: MutPage,"},{"Add":" right: MutPage,"},{"Add":" freed: u64,"},{"Add":" },"},{"Add":"}"},{"Add":""},{"Add":"/// Insert an entry into a database, returning `false` if and only if"},{"Add":"/// the exact same entry (key *and* value) was already in the"},{"Add":"/// database."},{"Add":"pub async fn put_async<"},{"Add":" T: AsyncAllocPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db_,"},{"Add":" key: &K,"},{"Add":" value: &V,"},{"Add":") -> Result {"},{"Add":" // Set the cursor to the first element larger than or equal to"},{"Add":" // `(key, value)`. We will insert at that position (where \"insert\""},{"Add":" // is meant in the sense of Rust's `Vec::insert`."},{"Add":" let mut cursor = Cursor::async_new(txn, db).await?;"},{"Add":" if cursor.async_set(txn, key, Some(value)).await?.is_some() {"},{"Add":" // If `(key, value)` already exists in the tree, return."},{"Add":" return Ok(false);"},{"Add":" }"},{"Add":" // Else, we are at a leaf, since cursors that don't find an"},{"Add":" // element go all the way to the leaves."},{"Add":" //"},{"Add":" // We put on the leaf page, resulting in a `Put`, i.e. either"},{"Add":" // `Put::Ok` or `Put::Split`."},{"Add":" let p = cursor.len(); // Save the position of the leaf cursor."},{"Add":" let is_owned = p < cursor.first_rc_len();"},{"Add":""},{"Add":" // Insert the key and value at the leaf, i.e. pop the top level of"},{"Add":" // the stack (the leaf) and insert in there."},{"Add":" let cur = cursor.pop().unwrap();"},{"Add":" let put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" is_owned,"},{"Add":" false,"},{"Add":" &cur.cursor,"},{"Add":" key,"},{"Add":" value,"},{"Add":" None,"},{"Add":" 0,"},{"Add":" 0,"},{"Add":" )?;"},{"Add":""},{"Add":" // In both cases (`Ok` and `Split`), we need to walk up the tree"},{"Add":" // and update each node."},{"Add":""},{"Add":" // Moreover, since the middle elements of the splits may be on"},{"Add":" // pages that must be freed at the end of this call, we collect"},{"Add":" // them in the `free` array below, and free them only at the end"},{"Add":" // of this function."},{"Add":" //"},{"Add":" // If we didn't hold on to these pages, they could be reallocated"},{"Add":" // in subsequent splits, and the middle element could be"},{"Add":" // lost. This is important when the middle element climbs up more"},{"Add":" // than one level (i.e. the middle element of the split of a leaf"},{"Add":" // is also the middle element of the split of the leaf's parent,"},{"Add":" // etc)."},{"Add":" let mut free = [0; N_CURSORS];"},{"Add":" db.db = put_cascade(txn, &mut cursor, put, &mut free).await?.0.offset;"},{"Add":" for f in &free[..p] {"},{"Add":" if *f & 1 != 0 {"},{"Add":" txn.decr_rc_owned((*f) ^ 1)?;"},{"Add":" } else if *f > 0 {"},{"Add":" txn.decr_rc(*f)?;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(true)"},{"Add":"}"},{"Add":""},{"Add":"async fn put_cascade<"},{"Add":" 'a,"},{"Add":" T: AsyncAllocPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" mut put: Put<'a, K, V>,"},{"Add":" free: &mut [u64; N_CURSORS],"},{"Add":") -> Result {"},{"Add":" loop {"},{"Add":" match put {"},{"Add":" Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed,"},{"Add":" } => {"},{"Add":" // Here, we are copying all children of the freed"},{"Add":" // page, except possibly the last freed page (which is"},{"Add":" // a child of the current node, if we aren't at a"},{"Add":" // leaf). This includes the split key/value, also"},{"Add":" // incremented in the following call:"},{"Add":" incr_descendants::(txn, cursor, free, freed)?;"},{"Add":" // Then, insert the split key/value in the relevant page:"},{"Add":" let is_owned = cursor.len() < cursor.first_rc_len();"},{"Add":" if let Some(cur) = cursor.pop() {"},{"Add":" // In this case, there's a page above the page"},{"Add":" // that just split (since we can pop the stack),"},{"Add":" // so the page that just split isn't the root (but"},{"Add":" // `cur` might be)."},{"Add":" put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" is_owned,"},{"Add":" false,"},{"Add":" &cur.cursor,"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" None,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" )?;"},{"Add":" } else {"},{"Add":" // No page above the split, so the root has just"},{"Add":" // split. Insert the split key/value into a new"},{"Add":" // page above the entire tree."},{"Add":" let mut p = txn.alloc_page()?;"},{"Add":" let cursor = P::cursor_first(&p.0);"},{"Add":" P::init(&mut p);"},{"Add":" if let Put::Ok(p) = P::put("},{"Add":" txn,"},{"Add":" p.0,"},{"Add":" true,"},{"Add":" false,"},{"Add":" &cursor,"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" None,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" )? {"},{"Add":" // Return the new root."},{"Add":" return Ok(p.page);"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" Put::Ok(Ok { page, freed }) => {"},{"Add":" // Same as above: increment the relevant reference"},{"Add":" // counters."},{"Add":" incr_descendants::(txn, cursor, free, freed)?;"},{"Add":" // And update the left child of the current cursor,"},{"Add":" // since the main invariant of cursors is that we're"},{"Add":" // always visiting the left child (if we're visiting"},{"Add":" // the last child of a page, the cursor is set to the"},{"Add":" // position strictly after the entries)."},{"Add":" let is_owned = cursor.len() < cursor.first_rc_len();"},{"Add":" if let Some(curs) = cursor.pop() {"},{"Add":" // If we aren't at the root, just update the child."},{"Add":" put = Put::Ok(P::update_left_child("},{"Add":" txn,"},{"Add":" curs.page,"},{"Add":" is_owned,"},{"Add":" &curs.cursor,"},{"Add":" page.0.offset,"},{"Add":" )?)"},{"Add":" } else {"},{"Add":" // If we are at the root, `page` is the updated root."},{"Add":" return Ok(page);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// This function does all the memory management for `put`."},{"Add":"fn incr_descendants<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreePage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" free: &mut [u64; N_CURSORS],"},{"Add":" mut freed: u64,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" // The freed page is on the page below."},{"Add":" if cursor.len() < cursor.first_rc_len() {"},{"Add":" // If a page has split or was immutable (allocated by a"},{"Add":" // previous transaction) and has been updated, we need to free"},{"Add":" // the old page."},{"Add":" free[cursor.len()] = freed;"},{"Add":" } else {"},{"Add":" // This means that the new version of the page (either split"},{"Add":" // or not) contains references to all the children of the"},{"Add":" // freed page, except the last freed page (because the new"},{"Add":" // version of that page isn't shared)."},{"Add":" let cur = cursor.cur();"},{"Add":""},{"Add":" // Start a cursor at the leftmost position and increase the"},{"Add":" // leftmost child page's RC (if we aren't at a leaf, and if"},{"Add":" // that child isn't the last freed page)."},{"Add":" let mut c = P::cursor_first(&cur.page);"},{"Add":" let left = P::left_child(cur.page.as_page(), &c);"},{"Add":" if left != 0 {"},{"Add":" if left != (freed & !1) {"},{"Add":" txn.incr_rc(left)?;"},{"Add":" } else if cursor.len() == cursor.first_rc_len() {"},{"Add":" freed = 0"},{"Add":" }"},{"Add":" }"},{"Add":" // Then, for each entry of the page, increase the RCs of"},{"Add":" // references contained in the keys and values, and increase"},{"Add":" // the RC of the right child."},{"Add":" while let Some((k, v, r)) = P::next(txn, cur.page.as_page(), &mut c) {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" if r != 0 {"},{"Add":" if r != (freed & !1) {"},{"Add":" txn.incr_rc(r)?;"},{"Add":" } else if cursor.len() == cursor.first_rc_len() {"},{"Add":" freed = 0"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" // Else, the \"freed\" page is shared with another tree, and"},{"Add":" // hence we just need to decrement its RC."},{"Add":" if freed > 0 && cursor.len() == cursor.first_rc_len() {"},{"Add":" free[cursor.len()] = freed;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"put.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"//! Insertions into a B tree."},{"Add":"use super::cursor::*;"},{"Add":"use super::*;"},{"Add":""},{"Add":"/// The representation of the update to a page."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Ok {"},{"Add":" /// The new page, possibly the same as the previous version."},{"Add":" pub page: MutPage,"},{"Add":" /// The freed page, or 0 if no page was freed."},{"Add":" pub freed: u64,"},{"Add":"}"},{"Add":""},{"Add":"/// The result of an insertion, i.e. either an update or a split."},{"Add":"#[derive(Debug)]"},{"Add":"pub enum Put<'a, K: ?Sized, V: ?Sized> {"},{"Add":" Ok(Ok),"},{"Add":" Split {"},{"Add":" split_key: &'a K,"},{"Add":" split_value: &'a V,"},{"Add":" left: MutPage,"},{"Add":" right: MutPage,"},{"Add":" freed: u64,"},{"Add":" },"},{"Add":"}"},{"Add":""},{"Add":"/// Insert an entry into a database, returning `false` if and only if"},{"Add":"/// the exact same entry (key *and* value) was already in the"},{"Add":"/// database."},{"Add":"pub async fn put<"},{"Add":" T: AllocPage,"},{"Add":" K: Storable + ?Sized + Sync,"},{"Add":" V: Storable + ?Sized + Sync,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db_,"},{"Add":" key: &K,"},{"Add":" value: &V,"},{"Add":") -> Result {"},{"Add":" // Set the cursor to the first element larger than or equal to"},{"Add":" // `(key, value)`. We will insert at that position (where \"insert\""},{"Add":" // is meant in the sense of Rust's `Vec::insert`."},{"Add":" let mut cursor = Cursor::new(txn, db).await?;"},{"Add":" if cursor.set(txn, key, Some(value)).await?.is_some() {"},{"Add":" // If `(key, value)` already exists in the tree, return."},{"Add":" return Ok(false);"},{"Add":" }"},{"Add":" // Else, we are at a leaf, since cursors that don't find an"},{"Add":" // element go all the way to the leaves."},{"Add":" //"},{"Add":" // We put on the leaf page, resulting in a `Put`, i.e. either"},{"Add":" // `Put::Ok` or `Put::Split`."},{"Add":" let p = cursor.len(); // Save the position of the leaf cursor."},{"Add":" let is_owned = p < cursor.first_rc_len();"},{"Add":""},{"Add":" // Insert the key and value at the leaf, i.e. pop the top level of"},{"Add":" // the stack (the leaf) and insert in there."},{"Add":" let cur = cursor.pop().unwrap();"},{"Add":" let put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" is_owned,"},{"Add":" false,"},{"Add":" &cur.cursor,"},{"Add":" key,"},{"Add":" value,"},{"Add":" None,"},{"Add":" 0,"},{"Add":" 0,"},{"Add":" ).await?;"},{"Add":""},{"Add":" // In both cases (`Ok` and `Split`), we need to walk up the tree"},{"Add":" // and update each node."},{"Add":""},{"Add":" // Moreover, since the middle elements of the splits may be on"},{"Add":" // pages that must be freed at the end of this call, we collect"},{"Add":" // them in the `free` array below, and free them only at the end"},{"Add":" // of this function."},{"Add":" //"},{"Add":" // If we didn't hold on to these pages, they could be reallocated"},{"Add":" // in subsequent splits, and the middle element could be"},{"Add":" // lost. This is important when the middle element climbs up more"},{"Add":" // than one level (i.e. the middle element of the split of a leaf"},{"Add":" // is also the middle element of the split of the leaf's parent,"},{"Add":" // etc)."},{"Add":" let mut free = [0; N_CURSORS];"},{"Add":" db.db = put_cascade(txn, &mut cursor, put, &mut free).await?.0.offset;"},{"Add":" for f in &free[..p] {"},{"Add":" if *f & 1 != 0 {"},{"Add":" txn.decr_rc_owned((*f) ^ 1).await?;"},{"Add":" } else if *f > 0 {"},{"Add":" txn.decr_rc(*f).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(true)"},{"Add":"}"},{"Add":""},{"Add":"async fn put_cascade<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" mut put: Put<'a, K, V>,"},{"Add":" free: &mut [u64; N_CURSORS],"},{"Add":") -> Result {"},{"Add":" loop {"},{"Add":" match put {"},{"Add":" Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed,"},{"Add":" } => {"},{"Add":" // Here, we are copying all children of the freed"},{"Add":" // page, except possibly the last freed page (which is"},{"Add":" // a child of the current node, if we aren't at a"},{"Add":" // leaf). This includes the split key/value, also"},{"Add":" // incremented in the following call:"},{"Add":" incr_descendants::(txn, cursor, free, freed).await?;"},{"Add":" // Then, insert the split key/value in the relevant page:"},{"Add":" let is_owned = cursor.len() < cursor.first_rc_len();"},{"Add":" if let Some(cur) = cursor.pop() {"},{"Add":" // In this case, there's a page above the page"},{"Add":" // that just split (since we can pop the stack),"},{"Add":" // so the page that just split isn't the root (but"},{"Add":" // `cur` might be)."},{"Add":" put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" is_owned,"},{"Add":" false,"},{"Add":" &cur.cursor,"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" None,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" ).await?;"},{"Add":" } else {"},{"Add":" // No page above the split, so the root has just"},{"Add":" // split. Insert the split key/value into a new"},{"Add":" // page above the entire tree."},{"Add":" let mut p = txn.alloc_page().await?;"},{"Add":" let cursor = P::cursor_first(&p.0);"},{"Add":" P::init(&mut p);"},{"Add":" if let Put::Ok(p) = P::put("},{"Add":" txn,"},{"Add":" p.0,"},{"Add":" true,"},{"Add":" false,"},{"Add":" &cursor,"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" None,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" ).await? {"},{"Add":" // Return the new root."},{"Add":" return Ok(p.page);"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" Put::Ok(Ok { page, freed }) => {"},{"Add":" // Same as above: increment the relevant reference"},{"Add":" // counters."},{"Add":" incr_descendants::(txn, cursor, free, freed).await?;"},{"Add":" // And update the left child of the current cursor,"},{"Add":" // since the main invariant of cursors is that we're"},{"Add":" // always visiting the left child (if we're visiting"},{"Add":" // the last child of a page, the cursor is set to the"},{"Add":" // position strictly after the entries)."},{"Add":" let is_owned = cursor.len() < cursor.first_rc_len();"},{"Add":" if let Some(curs) = cursor.pop() {"},{"Add":" // If we aren't at the root, just update the child."},{"Add":" put = Put::Ok(P::update_left_child("},{"Add":" txn,"},{"Add":" curs.page,"},{"Add":" is_owned,"},{"Add":" &curs.cursor,"},{"Add":" page.0.offset,"},{"Add":" ).await?)"},{"Add":" } else {"},{"Add":" // If we are at the root, `page` is the updated root."},{"Add":" return Ok(page);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// This function does all the memory management for `put`."},{"Add":"async fn incr_descendants<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreePage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" free: &mut [u64; N_CURSORS],"},{"Add":" mut freed: u64,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" // The freed page is on the page below."},{"Add":" if cursor.len() < cursor.first_rc_len() {"},{"Add":" // If a page has split or was immutable (allocated by a"},{"Add":" // previous transaction) and has been updated, we need to free"},{"Add":" // the old page."},{"Add":" free[cursor.len()] = freed;"},{"Add":" } else {"},{"Add":" // This means that the new version of the page (either split"},{"Add":" // or not) contains references to all the children of the"},{"Add":" // freed page, except the last freed page (because the new"},{"Add":" // version of that page isn't shared)."},{"Add":" let cur = cursor.cur();"},{"Add":""},{"Add":" // Start a cursor at the leftmost position and increase the"},{"Add":" // leftmost child page's RC (if we aren't at a leaf, and if"},{"Add":" // that child isn't the last freed page)."},{"Add":" let mut c = P::cursor_first(&cur.page);"},{"Add":" let left = P::left_child(cur.page.as_page(), &c);"},{"Add":" if left != 0 {"},{"Add":" if left != (freed & !1) {"},{"Add":" txn.incr_rc(left).await?;"},{"Add":" } else if cursor.len() == cursor.first_rc_len() {"},{"Add":" freed = 0"},{"Add":" }"},{"Add":" }"},{"Add":" // Then, for each entry of the page, increase the RCs of"},{"Add":" // references contained in the keys and values, and increase"},{"Add":" // the RC of the right child."},{"Add":" while let Some((k, v, r)) = P::next(cur.page.as_page(), &mut c) {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" if r != 0 {"},{"Add":" if r != (freed & !1) {"},{"Add":" txn.incr_rc(r).await?;"},{"Add":" } else if cursor.len() == cursor.first_rc_len() {"},{"Add":" freed = 0"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" // Else, the \"freed\" page is shared with another tree, and"},{"Add":" // hence we just need to decrement its RC."},{"Add":" if freed > 0 && cursor.len() == cursor.first_rc_len() {"},{"Add":" free[cursor.len()] = freed;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"page_unsized.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"//! Implementation of B tree pages for Unsized types, or types with an"},{"Add":"//! dynamically-sized representation (for example enums with widely"},{"Add":"//! different sizes)."},{"Add":"//!"},{"Add":"//! This module follows the same organisation as the sized"},{"Add":"//! implementation, and contains types shared between the two"},{"Add":"//! implementations."},{"Add":"//!"},{"Add":"//! The types that can be used with this implementation must implement"},{"Add":"//! the [`UnsizedStorable`] trait, which essentially replaces the"},{"Add":"//! [`core::mem`] functions for determining the size and alignment of"},{"Add":"//! values."},{"Add":"//!"},{"Add":"//! One key difference is the implementation of leaves (internal nodes"},{"Add":"//! have the same format): indeed, in this implementation, leaves have"},{"Add":"//! almost the same format as internal nodes, except that their"},{"Add":"//! offsets are written on the page as little-endian-encoded [`u16`]"},{"Add":"//! (with only the 12 LSBs used, i.e. 4 bits unused)."},{"Add":""},{"Add":"use super::*;"},{"Add":"use crate::btree::del::*;"},{"Add":"use crate::btree::put::*;"},{"Add":"use core::cmp::Ordering;"},{"Add":""},{"Add":"// The header is the same as for the sized implementation, so we share"},{"Add":"// it here."},{"Add":"pub(super) mod header;"},{"Add":""},{"Add":"// Like in the sized implementation, we have the same three submodules."},{"Add":"mod alloc;"},{"Add":""},{"Add":"// This is a common module with the sized implementation."},{"Add":"pub(super) mod cursor;"},{"Add":""},{"Add":"mod put;"},{"Add":"pub(super) mod rebalance;"},{"Add":"use alloc::*;"},{"Add":"use cursor::*;"},{"Add":"use header::*;"},{"Add":"use rebalance::*;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Page {"},{"Add":" k: core::marker::PhantomData,"},{"Add":" v: core::marker::PhantomData,"},{"Add":"}"},{"Add":""},{"Add":"// Many of these functions are the same as in the Sized implementations."},{"Add":"#[async_trait(?Send)]"},{"Add":"impl super::BTreePage"},{"Add":" for Page"},{"Add":"{"},{"Add":" fn is_empty(c: &Self::Cursor) -> bool {"},{"Add":" c.cur >= c.total as isize"},{"Add":" }"},{"Add":""},{"Add":" fn is_init(c: &Self::Cursor) -> bool {"},{"Add":" c.cur < 0"},{"Add":" }"},{"Add":" type Cursor = PageCursor;"},{"Add":" fn cursor_before(p: &crate::CowPage) -> Self::Cursor {"},{"Add":" PageCursor::new(p, -1)"},{"Add":" }"},{"Add":" fn cursor_after(p: &crate::CowPage) -> Self::Cursor {"},{"Add":" PageCursor::after(p)"},{"Add":" }"},{"Add":""},{"Add":" // Split a cursor, returning two cursors `(a, b)` where b is the"},{"Add":" // same as `c`, and `a` is a cursor running from the first element"},{"Add":" // of the page to `c` (excluding `c`)."},{"Add":" fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {"},{"Add":" ("},{"Add":" PageCursor {"},{"Add":" cur: 0,"},{"Add":" total: c.cur.max(0) as usize,"},{"Add":" is_leaf: c.is_leaf,"},{"Add":" },"},{"Add":" *c,"},{"Add":" )"},{"Add":" }"},{"Add":""},{"Add":" fn move_next(c: &mut Self::Cursor) -> bool {"},{"Add":" if c.cur < c.total as isize {"},{"Add":" c.cur += 1;"},{"Add":" true"},{"Add":" } else {"},{"Add":" false"},{"Add":" }"},{"Add":" }"},{"Add":" fn move_prev(c: &mut Self::Cursor) -> bool {"},{"Add":" if c.cur > 0 {"},{"Add":" c.cur -= 1;"},{"Add":" true"},{"Add":" } else {"},{"Add":" c.cur = -1;"},{"Add":" false"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // This function is the same as the sized implementation for"},{"Add":" // internal nodes, since the only difference between leaves and"},{"Add":" // internal nodes in this implementation is the size of offsets (2"},{"Add":" // bytes for leaves, 8 bytes for internal nodes)."},{"Add":" fn current<'a>("},{"Add":" page: crate::Page<'a>,"},{"Add":" c: &Self::Cursor,"},{"Add":" ) -> Option<(&'a K, &'a V, u64)> {"},{"Add":" if c.cur < 0 || c.cur >= c.total as isize {"},{"Add":" None"},{"Add":" } else if c.is_leaf {"},{"Add":" unsafe {"},{"Add":" let off ="},{"Add":" u16::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 2) as *const u16));"},{"Add":" let (k, v) = read::(page.data.as_ptr().add(off as usize));"},{"Add":" Some(("},{"Add":" K::from_raw_ptr(k as *const u8),"},{"Add":" V::from_raw_ptr(v as *const u8),"},{"Add":" 0,"},{"Add":" ))"},{"Add":" }"},{"Add":" } else {"},{"Add":" unsafe {"},{"Add":" let off ="},{"Add":" u64::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64));"},{"Add":" let (k, v) = read::(page.data.as_ptr().add((off & 0xfff) as usize));"},{"Add":" Some(("},{"Add":" K::from_raw_ptr(k as *const u8),"},{"Add":" V::from_raw_ptr(v as *const u8),"},{"Add":" off & !0xfff,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // These methods are the same as in the sized implementation."},{"Add":" fn left_child(page: crate::Page, c: &Self::Cursor) -> u64 {"},{"Add":" assert!(c.cur >= 0);"},{"Add":" if c.is_leaf {"},{"Add":" 0"},{"Add":" } else {"},{"Add":" assert!(c.cur >= 0 && HDR as isize + c.cur * 8 - 8 <= 4088);"},{"Add":" let off ="},{"Add":" unsafe { *(page.data.as_ptr().offset(HDR as isize + c.cur * 8 - 8) as *const u64) };"},{"Add":" u64::from_le(off) & !0xfff"},{"Add":" }"},{"Add":" }"},{"Add":" fn right_child(page: crate::Page, c: &Self::Cursor) -> u64 {"},{"Add":" assert!(c.cur < c.total as isize);"},{"Add":" if c.is_leaf {"},{"Add":" 0"},{"Add":" } else {"},{"Add":" assert!(c.cur < c.total as isize && HDR as isize + c.cur * 8 - 8 <= 4088);"},{"Add":" let off = unsafe { *(page.data.as_ptr().offset(HDR as isize + c.cur * 8) as *const u64) };"},{"Add":" u64::from_le(off) & !0xfff"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" async fn set_cursor<'a, 'b, T: LoadPage>("},{"Add":" _txn: &'a T,"},{"Add":" page: crate::Page<'b>,"},{"Add":" c: &mut PageCursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" ) -> Result<(&'a K, &'a V, u64), usize> {"},{"Add":" unsafe {"},{"Add":" // `lookup` has the same semantic as"},{"Add":" // `core::slice::binary_search`, i.e. it returns either"},{"Add":" // `Ok(n)`, where `n` is the position where `(k0, v0)` was"},{"Add":" // found, or `Err(n)` where `n` is the position where"},{"Add":" // `(k0, v0)` can be inserted to preserve the order."},{"Add":" match lookup(page, c, k0, v0).await {"},{"Add":" Ok(n) => {"},{"Add":" c.cur = n as isize;"},{"Add":" if c.is_leaf {"},{"Add":" let off ="},{"Add":" u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));"},{"Add":" let (k, v) = read::(page.data.as_ptr().add(off as usize));"},{"Add":" Ok((K::from_raw_ptr(k), V::from_raw_ptr(v), 0))"},{"Add":" } else {"},{"Add":" let off ="},{"Add":" u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));"},{"Add":" let (k, v) ="},{"Add":" read::(page.data.as_ptr().add(off as usize & 0xfff));"},{"Add":" Ok(("},{"Add":" K::from_raw_ptr(k),"},{"Add":" V::from_raw_ptr(v),"},{"Add":" off & !0xfff,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":" Err(n) => {"},{"Add":" c.cur = n as isize;"},{"Add":" Err(n)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// There quite some duplicated code in the following function, because"},{"Add":"// we're forming a slice of offsets, and the using the core library's"},{"Add":"// `binary_search_by` method on slices."},{"Add":"async unsafe fn lookup<'a, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>("},{"Add":" page: crate::Page<'a>,"},{"Add":" c: &mut PageCursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":") -> Result {"},{"Add":" let hdr = header(page);"},{"Add":" c.total = hdr.n() as usize;"},{"Add":" c.is_leaf = hdr.is_leaf();"},{"Add":" if c.is_leaf {"},{"Add":" lookup_leaf(page, k0, v0, hdr)"},{"Add":" } else {"},{"Add":" lookup_internal(page, k0, v0, hdr)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn lookup_internal<'a, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>("},{"Add":" page: crate::Page<'a>,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" hdr: &header::Header,"},{"Add":") -> Result {"},{"Add":" let s = core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const u64,"},{"Add":" hdr.n() as usize,"},{"Add":" );"},{"Add":" if let Some(v0) = v0 {"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u64::from_le(off) & 0xfff;"},{"Add":" let (k, v) = read::(page.data.as_ptr().offset(off as isize & 0xfff));"},{"Add":" let k = K::from_raw_ptr(k);"},{"Add":" match k.compare(k0) {"},{"Add":" Ordering::Equal => {"},{"Add":" let v = V::from_raw_ptr(v);"},{"Add":" v.compare(v0)"},{"Add":" }"},{"Add":" cmp => cmp,"},{"Add":" }"},{"Add":" })"},{"Add":" } else {"},{"Add":" match s.binary_search_by(|&off| {"},{"Add":" let off = u64::from_le(off) & 0xfff;"},{"Add":" let (k, _) = read::(page.data.as_ptr().offset(off as isize & 0xfff));"},{"Add":" let k = K::from_raw_ptr(k);"},{"Add":" k.compare(k0)"},{"Add":" }) {"},{"Add":" Err(i) => Err(i),"},{"Add":" Ok(mut i) => {"},{"Add":" // Rewind if there are multiple matching keys."},{"Add":" while i > 0 {"},{"Add":" let off = u64::from_le(s[i-1]) & 0xfff;"},{"Add":" let (k, _) = read::(page.data.as_ptr().offset(off as isize));"},{"Add":" let k = K::from_raw_ptr(k);"},{"Add":" if let Ordering::Equal = k.compare(k0) {"},{"Add":" i -= 1"},{"Add":" } else {"},{"Add":" break"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(i)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"unsafe fn lookup_leaf<'a, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>("},{"Add":" page: crate::Page<'a>,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" hdr: &header::Header,"},{"Add":") -> Result {"},{"Add":" let s = core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const u16,"},{"Add":" hdr.n() as usize,"},{"Add":" );"},{"Add":" if let Some(v0) = v0 {"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u16::from_le(off);"},{"Add":" let (k, v) = read::(page.data.as_ptr().offset(off as isize));"},{"Add":" let k = K::from_raw_ptr(k as *const u8);"},{"Add":" match k.compare(k0) {"},{"Add":" Ordering::Equal => {"},{"Add":" let v = V::from_raw_ptr(v as *const u8);"},{"Add":" v.compare(v0)"},{"Add":" }"},{"Add":" cmp => cmp,"},{"Add":" }"},{"Add":" })"},{"Add":" } else {"},{"Add":" match s.binary_search_by(|&off| {"},{"Add":" let off = u16::from_le(off);"},{"Add":" let (k, _) = read::(page.data.as_ptr().offset(off as isize));"},{"Add":" let k = K::from_raw_ptr(k);"},{"Add":" k.compare(k0)"},{"Add":" }) {"},{"Add":" Err(e) => Err(e),"},{"Add":" Ok(mut i) => {"},{"Add":" // Rewind if there are multiple matching keys."},{"Add":" while i > 0 {"},{"Add":" let off = u16::from_le(s[i-1]);"},{"Add":" let (k, _) = read::(page.data.as_ptr().offset(off as isize));"},{"Add":" let k = K::from_raw_ptr(k);"},{"Add":" if let Ordering::Equal = k.compare(k0){"},{"Add":" i -= 1"},{"Add":" } else {"},{"Add":" break"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(i)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[async_trait(?Send)]"},{"Add":"impl<"},{"Add":" K: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" V: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" > super::BTreeMutPage for Page"},{"Add":"{"},{"Add":" // The init function is straightforward."},{"Add":" fn init(page: &mut MutPage) {"},{"Add":" let h = header_mut(page);"},{"Add":" h.init();"},{"Add":" }"},{"Add":""},{"Add":" // Deletions in internal nodes of a B tree need to replace the"},{"Add":" // deleted value with a value from a leaf."},{"Add":" //"},{"Add":" // In this implementation of pages, we never actually wipe any"},{"Add":" // data from pages, we're even only appending data, or cloning the"},{"Add":" // pages to compact them. Therefore, raw pointers to leaves are"},{"Add":" // always valid for as long as the page isn't freed, which can"},{"Add":" // only happen at the very last step of an insertion or deletion."},{"Add":" type Saved = (*const K, *const V);"},{"Add":" fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved {"},{"Add":" (k as *const K, v as *const V)"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {"},{"Add":" (&*s.0, &*s.1)"},{"Add":" }"},{"Add":""},{"Add":" // As in the sized implementation, `put` is split into its own submodule."},{"Add":" async fn put<'a, T: AllocPage>("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" replace: bool,"},{"Add":" c: &PageCursor,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" k1v1: Option<(&'a K, &'a V)>,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" debug_assert!(c.cur >= 0);"},{"Add":" debug_assert!(k1v1.is_none() || replace);"},{"Add":" if r == 0 {"},{"Add":" put::put::<_, _, _, Leaf>("},{"Add":" txn,"},{"Add":" page,"},{"Add":" mutable,"},{"Add":" replace,"},{"Add":" c.cur as usize,"},{"Add":" k0,"},{"Add":" v0,"},{"Add":" k1v1,"},{"Add":" 0,"},{"Add":" 0,"},{"Add":" ).await"},{"Add":" } else {"},{"Add":" put::put::<_, _, _, Internal>("},{"Add":" txn,"},{"Add":" page,"},{"Add":" mutable,"},{"Add":" replace,"},{"Add":" c.cur as usize,"},{"Add":" k0,"},{"Add":" v0,"},{"Add":" k1v1,"},{"Add":" l,"},{"Add":" r,"},{"Add":" ).await"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn put_mut("},{"Add":" page: &mut MutPage,"},{"Add":" c: &mut Self::Cursor,"},{"Add":" k0: &K,"},{"Add":" v0: &V,"},{"Add":" r: u64,"},{"Add":" ) {"},{"Add":" let mut n = c.cur;"},{"Add":" if r == 0 {"},{"Add":" Leaf::alloc_write(page, k0, v0, 0, r, &mut n);"},{"Add":" } else {"},{"Add":" Internal::alloc_write(page, k0, v0, 0, r, &mut n);"},{"Add":" }"},{"Add":" c.total += 1;"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn set_left_child("},{"Add":" page: &mut MutPage,"},{"Add":" c: &Self::Cursor,"},{"Add":" l: u64"},{"Add":" ) {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":""},{"Add":" // Update the left child of the entry pointed to by cursor `c`."},{"Add":" async fn update_left_child("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" l: u64,"},{"Add":" ) -> Result {"},{"Add":" assert!(!c.is_leaf);"},{"Add":" let freed;"},{"Add":" let page = if mutable && page.is_dirty() {"},{"Add":" // If the page is dirty (allocated by this transaction)"},{"Add":" // and isn't shared, just make it mutable."},{"Add":" freed = 0;"},{"Add":" MutPage(page)"},{"Add":" } else {"},{"Add":" // Else, clone the page:"},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":" // Copy the left child"},{"Add":" let l = header(page.as_page()).left_page() & !0xfff;"},{"Add":" let hdr = header_mut(&mut new);"},{"Add":" hdr.set_left_page(l);"},{"Add":" // Copy all the entries"},{"Add":" let s = Internal::offset_slice(page.as_page());"},{"Add":" clone::(page.as_page(), &mut new, s, &mut 0);"},{"Add":" // Mark the old version for freeing."},{"Add":" freed = page.offset | if page.is_dirty() { 1 } else { 0 };"},{"Add":" new"},{"Add":" };"},{"Add":" // Finally, update the left children of the cursor. We know"},{"Add":" // that all valid positions of a cursor except the leftmost"},{"Add":" // one (-1) have a left child."},{"Add":" assert!(c.cur >= 0);"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur as isize - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" Ok(Ok { page, freed })"},{"Add":" }"},{"Add":""},{"Add":" // Here is how deletions work: if the page is dirty and mutable,"},{"Add":" // we \"unlink\" the value by moving the end of the offset array to"},{"Add":" // the left by one offset (2 bytes in leaves, 8 bytes in internal"},{"Add":" // nodes)."},{"Add":" async fn del("},{"Add":" txn: &mut T,"},{"Add":" page: crate::CowPage,"},{"Add":" mutable: bool,"},{"Add":" c: &PageCursor,"},{"Add":" l: u64,"},{"Add":" ) -> Result<(MutPage, u64), T::Error> {"},{"Add":" // Check that the cursor is at a valid position for a deletion."},{"Add":" debug_assert!(c.cur >= 0 && c.cur < c.total as isize);"},{"Add":" if mutable && page.is_dirty() {"},{"Add":" let p = page.data;"},{"Add":" let mut page = MutPage(page);"},{"Add":" let hdr = header_mut(&mut page);"},{"Add":" let n = hdr.n();"},{"Add":" if c.is_leaf {"},{"Add":" unsafe {"},{"Add":" let ptr = p.add(HDR + c.cur as usize * 2) as *mut u16;"},{"Add":" // Get the offset in the page of the key/value data."},{"Add":" let off = u16::from_le(*ptr);"},{"Add":" assert_eq!(off & 0xf000, 0);"},{"Add":" // Erase the offset by shifting the last (`n -"},{"Add":" // c.cur - 1`) offsets. The reasoning against"},{"Add":" // \"off-by-one errors\" is that if the cursor is"},{"Add":" // positioned on the first element (`c.cur == 0`),"},{"Add":" // there are `n-1` elements to shift."},{"Add":" core::ptr::copy(ptr.offset(1), ptr, n as usize - c.cur as usize - 1);"},{"Add":" // Remove the size of the actualy key/value, plus"},{"Add":" // 2 bytes (the offset)."},{"Add":" hdr.decr(2 + entry_size::(p.add(off as usize)));"},{"Add":" }"},{"Add":" } else {"},{"Add":" unsafe {"},{"Add":" let ptr = p.add(HDR + c.cur as usize * 8) as *mut u64;"},{"Add":" // Offset to the key/value data."},{"Add":" let off = u64::from_le(*ptr);"},{"Add":" // Shift the offsets like in the leaf case above."},{"Add":" core::ptr::copy(ptr.offset(1), ptr, n as usize - c.cur as usize - 1);"},{"Add":" if l > 0 {"},{"Add":" // In an internal node, we may have to update"},{"Add":" // the left child of the current"},{"Add":" // position. After the move, the current"},{"Add":" // offset is at `ptr`, so we need to find the"},{"Add":" // offset one step to the left."},{"Add":" let p = ptr.offset(-1);"},{"Add":" *p = (l | (u64::from_le(*p) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" // Remove the size of the key/value, plus 8 bytes"},{"Add":" // (the offset)."},{"Add":" hdr.decr(8 + entry_size::(p.add((off & 0xfff) as usize)));"},{"Add":" }"},{"Add":" };"},{"Add":" hdr.set_n(n - 1);"},{"Add":" // Return the page, and 0 for \"nothing was freed\"."},{"Add":" Ok((page, 0))"},{"Add":" } else {"},{"Add":" // If the page cannot be mutated, we allocate a new page and clone."},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":" if c.is_leaf {"},{"Add":" // In a leaf, this is just a matter of getting the"},{"Add":" // offset slice, removing the current position and"},{"Add":" // cloning."},{"Add":" let s = Leaf::offset_slice(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(c.cur as usize);"},{"Add":" let (_, s1) = s1.split_at(1);"},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":" } else {"},{"Add":" // In an internal node, things are a bit trickier,"},{"Add":" // since we might need to update the left child."},{"Add":" //"},{"Add":" // First, clone the leftmost child of the page."},{"Add":" let hdr = header(page.as_page());"},{"Add":" let left = hdr.left_page() & !0xfff;"},{"Add":" unsafe {"},{"Add":" *(new.0.data.add(HDR) as *mut u64).offset(-1) = left.to_le();"},{"Add":" }"},{"Add":" // Then, clone the first half of the page."},{"Add":" let s = Internal::offset_slice(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(c.cur as usize);"},{"Add":" let (_, s1) = s1.split_at(1);"},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":" // Update the left child, which was written by the"},{"Add":" // call to `clone` as the right child of the last"},{"Add":" // entry in `s0`."},{"Add":" if l > 0 {"},{"Add":" unsafe {"},{"Add":" let off = (new.0.data.add(HDR) as *mut u64).offset(n - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":" // Then, clone the second half of the page."},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":" }"},{"Add":" // Return the new page, and the offset of the freed page."},{"Add":" Ok((new, page.offset))"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Decide what to do with the concatenation of two neighbouring"},{"Add":" // pages, with a middle element."},{"Add":" //"},{"Add":" // This is highly similar to the sized case."},{"Add":" async fn merge_or_rebalance<'a, T: AllocPage>("},{"Add":" txn: &mut T,"},{"Add":" m: Concat<'a, K, V, Self>,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" // First evaluate the size of the middle element on a"},{"Add":" // page. Contrarily to the sized case, the offsets are"},{"Add":" // aligned, so the header is always the same size (no"},{"Add":" // padding)."},{"Add":" let mid_size = if m.modified.c0.is_leaf {"},{"Add":" 2 + alloc_size::(m.mid.0, m.mid.1)"},{"Add":" } else {"},{"Add":" 8 + alloc_size::(m.mid.0, m.mid.1)"},{"Add":" };"},{"Add":""},{"Add":" // Evaluate the size of the modified page of the concatenation"},{"Add":" // (which includes the header)."},{"Add":" let mod_size = size::(&m.modified);"},{"Add":" // Add the \"occupied\" size (which excludes the header)."},{"Add":" let occupied = {"},{"Add":" let hdr = header(m.other.as_page());"},{"Add":" (hdr.left_page() & 0xfff) as usize"},{"Add":" };"},{"Add":" if mod_size + mid_size + occupied <= PAGE_SIZE {"},{"Add":" // If the concatenation fits on a page, merge."},{"Add":" return if m.modified.c0.is_leaf {"},{"Add":" merge::<_, _, _, _, Leaf>(txn, m).await"},{"Add":" } else {"},{"Add":" merge::<_, _, _, _, Internal>(txn, m).await"},{"Add":" };"},{"Add":" }"},{"Add":""},{"Add":" // If we can't merge, evaluate the size of the first binding"},{"Add":" // on the other page, to see if we can rebalance."},{"Add":" let first_other = PageCursor::new(&m.other, 0);"},{"Add":" let first_other_size = current_size::(m.other.as_page(), &first_other);"},{"Add":""},{"Add":" // If the modified page is at least half-full, or if removing"},{"Add":" // the first entry on the other page would make that other"},{"Add":" // page less than half-full, don't rebalance. See the Sized"},{"Add":" // implementation to see cases where this happens."},{"Add":" if mod_size >= PAGE_SIZE / 2 || HDR + occupied - first_other_size < PAGE_SIZE / 2 {"},{"Add":" if let Some((k, v)) = m.modified.ins {"},{"Add":" return Ok(Op::Put(Self::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" m.modified.skip_first,"},{"Add":" &m.modified.c1,"},{"Add":" k,"},{"Add":" v,"},{"Add":" m.modified.ins2,"},{"Add":" m.modified.l,"},{"Add":" m.modified.r,"},{"Add":" ).await?));"},{"Add":" } else if m.modified.skip_first {"},{"Add":" debug_assert!(m.modified.ins2.is_none());"},{"Add":" let (page, freed) = Self::del("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &m.modified.c1,"},{"Add":" m.modified.l,"},{"Add":" ).await?;"},{"Add":" return Ok(Op::Put(Put::Ok(Ok { page, freed })));"},{"Add":" } else {"},{"Add":" let mut c1 = m.modified.c1.clone();"},{"Add":" let mut l = m.modified.l;"},{"Add":" if l == 0 {"},{"Add":" Self::move_next(&mut c1);"},{"Add":" l = m.modified.r;"},{"Add":" }"},{"Add":" return Ok(Op::Put(Put::Ok(Self::update_left_child("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &c1,"},{"Add":" l,"},{"Add":" ).await?)));"},{"Add":" }"},{"Add":" }"},{"Add":" // Finally, if we're here, we can rebalance. There are four"},{"Add":" // (relatively explicit) cases, see the `rebalance` submodule"},{"Add":" // to see how this is done."},{"Add":" if m.mod_is_left {"},{"Add":" if m.modified.c0.is_leaf {"},{"Add":" rebalance_left::<_, _, _, Leaf>(txn, m).await"},{"Add":" } else {"},{"Add":" rebalance_left::<_, _, _, Internal>(txn, m).await"},{"Add":" }"},{"Add":" } else {"},{"Add":" rebalance_right::<_, _, _, Self>(txn, m).await"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Size of a modified page (including the header)."},{"Add":"fn size("},{"Add":" m: &ModifiedPage>,"},{"Add":") -> usize {"},{"Add":" let mut total = {"},{"Add":" let hdr = header(m.page.as_page());"},{"Add":" (hdr.left_page() & 0xfff) as usize"},{"Add":" };"},{"Add":" total += HDR;"},{"Add":""},{"Add":" // Extra size for the offsets."},{"Add":" let extra = if m.c1.is_leaf { 2 } else { 8 };"},{"Add":" if let Some((k, v)) = m.ins {"},{"Add":" total += extra + alloc_size(k, v) as usize;"},{"Add":" if let Some((k, v)) = m.ins2 {"},{"Add":" total += extra + alloc_size(k, v) as usize;"},{"Add":" }"},{"Add":" }"},{"Add":" if m.skip_first {"},{"Add":" total -= current_size::(m.page.as_page(), &m.c1) as usize;"},{"Add":" }"},{"Add":" total"},{"Add":"}"},{"Add":""},{"Add":"// Size of a pair of type `(K, V)`. This is computed in the same way"},{"Add":"// as a struct with fields of type `K` and `V` in C."},{"Add":"fn alloc_size(k: &K, v: &V) -> usize {"},{"Add":" let s = ((k.size() + V::ALIGN - 1) & !(V::ALIGN - 1)) + v.size();"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" (s + al - 1) & !(al - 1)"},{"Add":"}"},{"Add":""},{"Add":"// Total size of the entry for that cursor position, including the"},{"Add":"// offset size."},{"Add":"fn current_size("},{"Add":" page: crate::Page,"},{"Add":" c: &PageCursor,"},{"Add":") -> usize {"},{"Add":" if c.is_leaf {"},{"Add":" Leaf::current_size::(page, c.cur)"},{"Add":" } else {"},{"Add":" Internal::current_size::(page, c.cur)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub(super) trait AllocWrite {"},{"Add":" fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize);"},{"Add":" fn set_left_child(new: &mut MutPage, n: isize, l: u64);"},{"Add":"}"},{"Add":""},{"Add":"/// Perform the modifications on a page, by copying it onto page `new`."},{"Add":"fn modify, L: AllocWrite>("},{"Add":" new: &mut MutPage,"},{"Add":" m: &mut ModifiedPage,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" let mut l = P::left_child(m.page.as_page(), &m.c0);"},{"Add":" while let Some((k, v, r)) = P::next(m.page.as_page(), &mut m.c0) {"},{"Add":" L::alloc_write(new, k, v, l, r, n);"},{"Add":" l = 0;"},{"Add":" }"},{"Add":" let mut rr = m.r;"},{"Add":" if let Some((k, v)) = m.ins {"},{"Add":" if let Some((k2, v2)) = m.ins2 {"},{"Add":" L::alloc_write(new, k, v, l, m.l, n);"},{"Add":" L::alloc_write(new, k2, v2, 0, m.r, n);"},{"Add":" } else if m.l > 0 {"},{"Add":" L::alloc_write(new, k, v, m.l, m.r, n);"},{"Add":" } else {"},{"Add":" L::alloc_write(new, k, v, l, m.r, n);"},{"Add":" }"},{"Add":" l = 0;"},{"Add":" rr = 0;"},{"Add":" } else if m.l > 0 {"},{"Add":" l = m.l"},{"Add":" }"},{"Add":" let mut c1 = m.c1.clone();"},{"Add":" if m.skip_first {"},{"Add":" P::move_next(&mut c1);"},{"Add":" }"},{"Add":" // Here's a confusing thing: if the first element of `c1` is the"},{"Add":" // last element of a page, we may be updating its right child (in"},{"Add":" // which case m.r > 0) rather than its left child like for all"},{"Add":" // other elements."},{"Add":" //"},{"Add":" // This case only ever happens for this function when we're"},{"Add":" // updating the last child of a page p, and then merging p with"},{"Add":" // its right neighbour."},{"Add":" while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c1) {"},{"Add":" if rr > 0 {"},{"Add":" L::alloc_write(new, k, v, l, rr, n);"},{"Add":" rr = 0;"},{"Add":" } else {"},{"Add":" L::alloc_write(new, k, v, l, r, n);"},{"Add":" }"},{"Add":" l = 0;"},{"Add":" }"},{"Add":" if l != 0 {"},{"Add":" // The while loop above didn't run, i.e. the insertion"},{"Add":" // happened at the end of the page. In this case, we haven't"},{"Add":" // had a chance to update the left page, so do it now."},{"Add":" L::set_left_child(new, *n, l)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// The very unsurprising `merge` function"},{"Add":"pub(super) async fn merge<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: ?Sized + core::fmt::Debug,"},{"Add":" V: ?Sized + core::fmt::Debug,"},{"Add":" P: BTreeMutPage,"},{"Add":" L: AllocWrite,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" mut m: Concat<'a, K, V, P>,"},{"Add":") -> Result, T::Error> {"},{"Add":" // Here, we first allocate a page, then clone both pages onto it,"},{"Add":" // in a different order depending on whether the modified page is"},{"Add":" // the left or the right child."},{"Add":" //"},{"Add":" // Note that in the case that this merge happens immediately after"},{"Add":" // a put that reallocated the two sides of the merge in order to"},{"Add":" // split (not all splits do that), we could be slightly more"},{"Add":" // efficient, but with considerably more code."},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" P::init(&mut new);"},{"Add":""},{"Add":" let mut n = 0;"},{"Add":" if m.mod_is_left {"},{"Add":" modify::<_, _, _, L>(&mut new, &mut m.modified, &mut n);"},{"Add":" let mut rc = P::cursor_first(&m.other);"},{"Add":" let l = P::left_child(m.other.as_page(), &rc);"},{"Add":" L::alloc_write(&mut new, m.mid.0, m.mid.1, 0, l, &mut n);"},{"Add":" while let Some((k, v, r)) = P::next(m.other.as_page(), &mut rc) {"},{"Add":" L::alloc_write(&mut new, k, v, 0, r, &mut n);"},{"Add":" }"},{"Add":" } else {"},{"Add":" let mut rc = P::cursor_first(&m.other);"},{"Add":" let mut l = P::left_child(m.other.as_page(), &rc);"},{"Add":" while let Some((k, v, r)) = P::next(m.other.as_page(), &mut rc) {"},{"Add":" L::alloc_write(&mut new, k, v, l, r, &mut n);"},{"Add":" l = 0;"},{"Add":" }"},{"Add":" L::alloc_write(&mut new, m.mid.0, m.mid.1, 0, 0, &mut n);"},{"Add":" modify::<_, _, _, L>(&mut new, &mut m.modified, &mut n);"},{"Add":" }"},{"Add":""},{"Add":" let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };"},{"Add":" let b1 = if m.other.is_dirty() { 1 } else { 0 };"},{"Add":" Ok(Op::Merged {"},{"Add":" page: new,"},{"Add":" freed: [m.modified.page.offset | b0, m.other.offset | b1],"},{"Add":" marker: core::marker::PhantomData,"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"fn clone("},{"Add":" page: crate::Page,"},{"Add":" new: &mut MutPage,"},{"Add":" s: Offsets,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" for off in s.0.iter() {"},{"Add":" let (r, off): (u64, usize) = (*off).into();"},{"Add":" unsafe {"},{"Add":" let ptr = page.data.as_ptr().add(off);"},{"Add":" let size = entry_size::(ptr);"},{"Add":" // Reserve the space on the page"},{"Add":" let hdr = header_mut(new);"},{"Add":" let data = hdr.data() as u16;"},{"Add":" let off_new = data - size as u16;"},{"Add":" hdr.set_data(off_new);"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" if hdr.is_leaf() {"},{"Add":" hdr.incr(2 + size);"},{"Add":" let ptr = new.0.data.offset(HDR as isize + *n * 2) as *mut u16;"},{"Add":" *ptr = (off_new as u16).to_le();"},{"Add":" } else {"},{"Add":" hdr.incr(8 + size);"},{"Add":" // Set the offset to this new entry in the offset"},{"Add":" // array, along with the right child page."},{"Add":" let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;"},{"Add":" *ptr = (r | off_new as u64).to_le();"},{"Add":" }"},{"Add":" core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);"},{"Add":" }"},{"Add":" *n += 1;"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"page_unsized","metadata":576},"context":[{"change":0,"pos":12617}],"contents":[]}},{"FileAdd":{"meta":{"basename":"rebalance.rs","metadata":0},"context":[{"change":0,"pos":61868}],"contents":[{"Add":"use super::cursor::*;"},{"Add":"use super::*;"},{"Add":""},{"Add":"// The implementation here is mostly the same as in the sized case,"},{"Add":"// except for leaves, which makes it hard to refactor."},{"Add":"pub(crate) async fn rebalance_left<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" V: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" L: Alloc,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" m: Concat<'a, K, V, Page>,"},{"Add":") -> Result, T::Error> {"},{"Add":" assert!(m.mod_is_left);"},{"Add":" // First element of the right page. We'll rotate it to the left"},{"Add":" // page, i.e. return a middle element, and append the current"},{"Add":" // middle element to the left page."},{"Add":" let rc = super::cursor::PageCursor::new(&m.other, 0);"},{"Add":" let rl = >::left_child(m.other.as_page(), &rc);"},{"Add":" let (k, v, r) = >::current(m.other.as_page(), &rc).unwrap();"},{"Add":""},{"Add":" let mut freed_ = [0, 0];"},{"Add":""},{"Add":" // First, perform the modification on the modified page, which we"},{"Add":" // know is the left page, and return the resulting mutable page"},{"Add":" // (the modified page may or may not be mutable before we do this)."},{"Add":" let new_left = if let Some((k, v)) = m.modified.ins {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let new_left = if let Put::Ok(Ok { page, freed }) = >::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" m.modified.skip_first,"},{"Add":" &m.modified.c1,"},{"Add":" k,"},{"Add":" v,"},{"Add":" m.modified.ins2,"},{"Add":" m.modified.l,"},{"Add":" m.modified.r,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b;"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" };"},{"Add":" // Append the middle element of the concatenation at the end"},{"Add":" // of the left page. We know the left page to be mutable by"},{"Add":" // now, and we also know there's enough space to do this."},{"Add":" let lc = PageCursor::after(&new_left.0);"},{"Add":" if let Put::Ok(Ok { freed, page }) = >::put("},{"Add":" txn, new_left.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b;"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" } else if m.modified.skip_first {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let (page, freed) = >::del("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &m.modified.c1,"},{"Add":" m.modified.l,"},{"Add":" ).await?;"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b;"},{"Add":" }"},{"Add":""},{"Add":" // Append the middle element of the concatenation at the end"},{"Add":" // of the left page. We know the left page to be mutable by"},{"Add":" // now, and we also know there's enough space to do this."},{"Add":" let lc = PageCursor::after(&page.0);"},{"Add":" if let Put::Ok(Ok { freed, page }) ="},{"Add":" >::put(txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl).await?"},{"Add":" {"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b;"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" } else {"},{"Add":" // Append the middle element of the concatenation at the end"},{"Add":" // of the left page. We know the left page to be mutable by"},{"Add":" // now, and we also know there's enough space to do this."},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let lc = PageCursor::after(&m.modified.page);"},{"Add":" if let Put::Ok(Ok { freed, page }) = >::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" false,"},{"Add":" &lc,"},{"Add":" m.mid.0,"},{"Add":" m.mid.1,"},{"Add":" None,"},{"Add":" 0,"},{"Add":" rl,"},{"Add":" ).await? {"},{"Add":" if m.modified.l > 0 {"},{"Add":" assert_eq!(m.modified.r, 0);"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur - 1);"},{"Add":" *off = (m.modified.l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" } else if m.modified.r > 0 {"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur);"},{"Add":" *off = (m.modified.r | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b;"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" // We extend the pointer's lifetime here, because we know the"},{"Add":" // current deletion (we only rebalance during deletions) won't"},{"Add":" // touch this page anymore after this."},{"Add":" let k = unsafe { core::mem::transmute(k) };"},{"Add":" let v = unsafe { core::mem::transmute(v) };"},{"Add":""},{"Add":" // If this frees the old \"other\" page, add it to the \"freed\""},{"Add":" // array."},{"Add":" let is_dirty = m.other.is_dirty();"},{"Add":" let (new_right, freed) = >::del(txn, m.other, m.other_is_mutable, &rc, r).await?;"},{"Add":" if freed > 0 {"},{"Add":" freed_[1] = if is_dirty { freed | 1 } else { freed }"},{"Add":" }"},{"Add":" Ok(Op::Rebalanced {"},{"Add":" l: new_left.0.offset,"},{"Add":" r: new_right.0.offset,"},{"Add":" k,"},{"Add":" v,"},{"Add":" freed: freed_,"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"// Surprisingly, the `rebalance_right` function is simpler,"},{"Add":"// since:"},{"Add":"//"},{"Add":"// - if we call it to rebalance two internal nodes, we're in the easy"},{"Add":"// case of rebalance_left."},{"Add":"//"},{"Add":"// - Else, the middle element is the last one on the left page, and"},{"Add":"// isn't erased be leaf deletions, because these just move entries to"},{"Add":"// the left."},{"Add":"//"},{"Add":"// This implementation is shared with the sized one."},{"Add":"pub(crate) async fn rebalance_right<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: ?Sized,"},{"Add":" V: ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" m: Concat<'a, K, V, P>,"},{"Add":") -> Result, T::Error> {"},{"Add":" assert!(!m.mod_is_left);"},{"Add":" // Take the last element of the left page."},{"Add":" let lc = P::cursor_last(&m.other);"},{"Add":" let (k0, v0, r0) = P::current(m.other.as_page(), &lc).unwrap();"},{"Add":""},{"Add":" let mut freed_ = [0, 0];"},{"Add":""},{"Add":" // Perform the modification on the modified page."},{"Add":" let new_right = if let Some((k, v)) = m.modified.ins {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let new_right = if let Put::Ok(Ok { page, freed }) = P::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" m.modified.skip_first,"},{"Add":" &m.modified.c1,"},{"Add":" k,"},{"Add":" v,"},{"Add":" m.modified.ins2,"},{"Add":" m.modified.l,"},{"Add":" m.modified.r,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" freed_[0] = if is_dirty { freed | 1 } else { freed };"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" };"},{"Add":" // Add the middle element of the concatenation as the first"},{"Add":" // element of the right page. We know the right page is"},{"Add":" // mutable, since we just modified it (hence the"},{"Add":" // `assert_eq!(freed, 0)`."},{"Add":""},{"Add":" // First element of the right page (after potential"},{"Add":" // modification by `put` above)."},{"Add":" let rc = P::cursor_first(&new_right.0);"},{"Add":" let rl = P::left_child(new_right.0.as_page(), &rc);"},{"Add":" if let Put::Ok(Ok { freed, page }) = P::put("},{"Add":" txn,"},{"Add":" new_right.0,"},{"Add":" true,"},{"Add":" false,"},{"Add":" &rc,"},{"Add":" m.mid.0,"},{"Add":" m.mid.1,"},{"Add":" None,"},{"Add":" r0,"},{"Add":" rl,"},{"Add":" ).await? {"},{"Add":" debug_assert_eq!(freed, 0);"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" } else if m.modified.skip_first {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let (page, freed) = P::del("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &m.modified.c1,"},{"Add":" m.modified.l,"},{"Add":" ).await?;"},{"Add":" if freed > 0 {"},{"Add":" freed_[0] = if is_dirty { freed | 1 } else { freed };"},{"Add":" }"},{"Add":" // Add the middle element of the concatenation as the first"},{"Add":" // element of the right page. We know the right page is"},{"Add":" // mutable, since we just modified it. Moreover, if it is"},{"Add":" // compacted by the `put` below, we know that the `del` didn't"},{"Add":" // free anything, hence we can reuse the slot 0.."},{"Add":""},{"Add":" // First element of the right page (after potential"},{"Add":" // modification by `del` above)."},{"Add":" let rc = P::cursor_first(&page.0);"},{"Add":" let rl = P::left_child(page.0.as_page(), &rc);"},{"Add":" if let Put::Ok(Ok { freed, page }) = P::put("},{"Add":" txn, page.0, true, false, &rc, m.mid.0, m.mid.1, None, r0, rl,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" freed_[0] = if is_dirty { freed | 1 } else { freed };"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" } else {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let rc = P::cursor_first(&m.modified.page);"},{"Add":" let rl = P::left_child(m.modified.page.as_page(), &rc);"},{"Add":" if let Put::Ok(Ok { freed, page }) = P::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" false,"},{"Add":" &rc,"},{"Add":" m.mid.0,"},{"Add":" m.mid.1,"},{"Add":" None,"},{"Add":" r0,"},{"Add":" rl,"},{"Add":" ).await? {"},{"Add":" // Update the left and right offsets. We know that at"},{"Add":" // least one of them is 0, but it can be either one (or"},{"Add":" // both), depending on what happened on the page below."},{"Add":" //"},{"Add":" // Since we inserted an entry at the beginning of the"},{"Add":" // page, we need to add 1 to the index given by"},{"Add":" // `m.modified.c1.cur`."},{"Add":" if m.modified.l > 0 {"},{"Add":" assert_eq!(m.modified.r, 0);"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur);"},{"Add":" *off = (m.modified.l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" } else if m.modified.r > 0 {"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur + 1);"},{"Add":" *off = (m.modified.r | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":" if freed > 0 {"},{"Add":" freed_[0] = if is_dirty { freed | 1 } else { freed };"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" // As explained in the general comment on this function, this"},{"Add":" // entry isn't erased by the deletion in `m.other` below, so we"},{"Add":" // can safely extend its lifetime."},{"Add":" let k = unsafe { core::mem::transmute(k0) };"},{"Add":" let v = unsafe { core::mem::transmute(v0) };"},{"Add":""},{"Add":" let is_dirty = m.other.is_dirty();"},{"Add":" let (new_left, freed) = P::del(txn, m.other, m.other_is_mutable, &lc, 0).await?;"},{"Add":" if freed > 0 {"},{"Add":" freed_[1] = if is_dirty { freed | 1 } else { freed }"},{"Add":" }"},{"Add":" Ok(Op::Rebalanced {"},{"Add":" l: new_left.0.offset,"},{"Add":" r: new_right.0.offset,"},{"Add":" k,"},{"Add":" v,"},{"Add":" freed: freed_,"},{"Add":" })"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"put.rs","metadata":0},"context":[{"change":0,"pos":61868}],"contents":[{"Add":"use super::header::{header, header_mut, HDR};"},{"Add":"use super::*;"},{"Add":""},{"Add":"pub(super) async fn put<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" V: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" L: Alloc + AllocWrite,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" replace: bool,"},{"Add":" u: usize,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" k1v1: Option<(&'a K, &'a V)>,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":") -> Result, T::Error> {"},{"Add":" // Size of the new insertions, not counting the offsets."},{"Add":" let size = alloc_size(k0, v0)"},{"Add":" + if let Some((k1, v1)) = k1v1 {"},{"Add":" alloc_size(k1, v1)"},{"Add":" } else {"},{"Add":" 0"},{"Add":" };"},{"Add":" // Sized occupied by the data in these insertions (not counting"},{"Add":" // the offsets), if we need to compact the page."},{"Add":" let size_replaced = if replace {"},{"Add":" // We're always in an internal node if we replace."},{"Add":" let cur_size = Internal::current_size::(page.as_page(), u as isize);"},{"Add":" // Since `size` isn't counting the size of the 64-bit offset,"},{"Add":" // and `cur_size` is, we need to add 8."},{"Add":" 8 + size as isize - cur_size as isize"},{"Add":" } else {"},{"Add":" size as isize"},{"Add":" };"},{"Add":" // Number of extra offsets."},{"Add":" let n_ins = {"},{"Add":" let n_ins = if k1v1.is_some() { 2 } else { 1 };"},{"Add":" if replace {"},{"Add":" n_ins - 1"},{"Add":" } else {"},{"Add":" n_ins"},{"Add":" }"},{"Add":" };"},{"Add":" let hdr = header(page.as_page());"},{"Add":" if mutable && page.is_dirty() && L::can_alloc(header(page.as_page()), size, n_ins) {"},{"Add":" // First, if the page is dirty and mutable, mark it mutable."},{"Add":" let mut page = MutPage(page);"},{"Add":" let mut n = u as isize;"},{"Add":""},{"Add":" // If we replace, we first need to \"unlink\" the previous"},{"Add":" // value, by erasing its offset."},{"Add":" if replace {"},{"Add":" let p = page.0.data;"},{"Add":" let hdr = header_mut(&mut page);"},{"Add":" // In this case, we know we're not in a leaf, so offsets"},{"Add":" // are of size 8."},{"Add":" assert!(!hdr.is_leaf());"},{"Add":" unsafe {"},{"Add":" let ptr = p.add(HDR + n as usize * 8) as *mut u64;"},{"Add":" let off = (u64::from_le(*ptr) & 0xfff) as usize;"},{"Add":" let kv_ptr = p.add(off);"},{"Add":" let size = entry_size::(kv_ptr);"},{"Add":" core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - n as usize - 1);"},{"Add":" // Decreasing these figures here, we'll increase them"},{"Add":" // again in the calls to `alloc_write` below."},{"Add":" hdr.decr(8 + size);"},{"Add":" hdr.set_n(hdr.n() - 1);"},{"Add":" }"},{"Add":" }"},{"Add":" // Do the actual insertions."},{"Add":" if let Some((k1, v1)) = k1v1 {"},{"Add":" L::alloc_write(&mut page, k0, v0, 0, 0, &mut n);"},{"Add":" L::alloc_write(&mut page, k1, v1, l, r, &mut n);"},{"Add":" } else {"},{"Add":" L::alloc_write(&mut page, k0, v0, l, r, &mut n);"},{"Add":" }"},{"Add":" // Return: no page was freed."},{"Add":" Ok(Put::Ok(Ok { page, freed: 0 }))"},{"Add":" } else if L::can_compact(hdr, size_replaced, n_ins) {"},{"Add":" // Allocate a new page, split the offsets at the position of"},{"Add":" // the insertion, and each side of the split onto the new"},{"Add":" // page, with the insertion between them."},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":""},{"Add":" // Clone the leftmost child."},{"Add":" L::set_right_child(&mut new, -1, hdr.left_page() & !0xfff);"},{"Add":""},{"Add":" // Split the offsets."},{"Add":" let s = L::offset_slice(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(u as usize);"},{"Add":" // Drop the first element of `s1` if we're replacing it."},{"Add":" let s1 = if replace { s1.split_at(1).1 } else { s1 };"},{"Add":""},{"Add":" // Finally, clone and insert."},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":" if let Some((k1, v1)) = k1v1 {"},{"Add":" L::alloc_write(&mut new, k0, v0, 0, l, &mut n);"},{"Add":" L::alloc_write(&mut new, k1, v1, 0, r, &mut n);"},{"Add":" } else {"},{"Add":" L::alloc_write(&mut new, k0, v0, l, r, &mut n);"},{"Add":" }"},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":""},{"Add":" // And return, freeing the old version of the page."},{"Add":" Ok(Put::Ok(Ok {"},{"Add":" page: new,"},{"Add":" freed: page.offset | if page.is_dirty() { 1 } else { 0 },"},{"Add":" }))"},{"Add":" } else {"},{"Add":" split_unsized::<_, _, _, L>(txn, page, replace, u, k0, v0, k1v1, l, r).await"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// Surprisingly, the following function is simpler than in the sized"},{"Add":"// case, because we can't be too efficient in this case, since we have"},{"Add":"// to go through all the elements linearly anyway to get their sizes."},{"Add":"async fn split_unsized<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" V: UnsizedStorable + ?Sized + core::fmt::Debug,"},{"Add":" L: Alloc + AllocWrite,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" replace: bool,"},{"Add":" u: usize,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" k1v1: Option<(&'a K, &'a V)>,"},{"Add":" l0: u64,"},{"Add":" r0: u64,"},{"Add":") -> Result, T::Error> {"},{"Add":" let hdr = header(page.as_page());"},{"Add":" let mut left = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut left);"},{"Add":""},{"Add":" let mut right = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut right);"},{"Add":""},{"Add":" // Clone the leftmost child. If we're inserting at position 0,"},{"Add":" // this means this leftmost child must, and will be replaced."},{"Add":" let left_child = hdr.left_page() & !0xfff;"},{"Add":" L::set_right_child(&mut left, -1, left_child);"},{"Add":""},{"Add":" // Pointer to the split key and value."},{"Add":" let mut split = None;"},{"Add":""},{"Add":" // We start filling the left page, and we will change to filling"},{"Add":" // the right page when the left one is at least half-full."},{"Add":" let mut current_page = &mut left;"},{"Add":""},{"Add":" // There are two synchronised counters here: `hdr.n()` and"},{"Add":" // `n`. The reason for this is that operations on `hdr.n()` are"},{"Add":" // somewhat cumbersome, as they might involve extra operations to"},{"Add":" // convert to/from the little-endian encoding of `hdr.n()`."},{"Add":" let mut n = 0;"},{"Add":" let s = L::offset_slice(page.as_page());"},{"Add":" let mut total = HDR;"},{"Add":" for (uu, off) in s.0.iter().enumerate() {"},{"Add":" // If the current position of the cursor is the insertion,"},{"Add":" // (i.e. `uu == u`), insert."},{"Add":" if uu == u {"},{"Add":" // The following is tricky and makes assumptions on the"},{"Add":" // rest of the code. If we are inserting two elements"},{"Add":" // (i.e. if `k1v1.is_some()`), this means we're replacing"},{"Add":" // one on the page."},{"Add":" header_mut(current_page).set_n(n as u16);"},{"Add":" if let Some((k1, v1)) = k1v1 {"},{"Add":" // As explained in the documentation for `put` in the"},{"Add":" // definition of `BTreeMutPage`, `l0` and `r0` are the"},{"Add":" // left and right children of k1v1, since this means"},{"Add":" // the right child of a deleted entry has split, and"},{"Add":" // we must replace the deleted entry with `(k0, v0)`."},{"Add":" L::alloc_write(current_page, k0, v0, 0, l0, &mut n);"},{"Add":" total += alloc_size(k0, v0) + L::OFFSET_SIZE;"},{"Add":" L::alloc_write(current_page, k1, v1, 0, r0, &mut n);"},{"Add":" total += alloc_size(k1, v1) + L::OFFSET_SIZE;"},{"Add":""},{"Add":" // Replacing the next element:"},{"Add":" debug_assert!(replace);"},{"Add":" continue;"},{"Add":" } else {"},{"Add":" L::alloc_write(current_page, k0, v0, l0, r0, &mut n);"},{"Add":" total += alloc_size(k0, v0) + L::OFFSET_SIZE;"},{"Add":" if replace {"},{"Add":" continue;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" // Then, i.e. either if we're not at the position of an"},{"Add":" // insertion, or else if we're not replacing the current"},{"Add":" // position, just copy the current entry to the appropriate"},{"Add":" // page (left or right)."},{"Add":" let (r, off): (u64, usize) = (*off).into();"},{"Add":" assert_ne!(off, 0);"},{"Add":" unsafe {"},{"Add":" let ptr = page.data.add(off);"},{"Add":" let size = entry_size::(ptr);"},{"Add":""},{"Add":" // If the left side of the split is at least half-full, we"},{"Add":" // know that we can do all the insertions we need on the"},{"Add":" // right-hand side (even if there are two of them, and the"},{"Add":" // replaced value is of size 0), so we switch."},{"Add":" if split.is_none() && total >= PAGE_SIZE / 2 {"},{"Add":" // Don't write the next entry onto any page, keep it"},{"Add":" // as the split entry."},{"Add":" let (k, v) = read::(ptr);"},{"Add":" split = Some((K::from_raw_ptr(k), V::from_raw_ptr(v)));"},{"Add":" // Set the entry count for the current page, before"},{"Add":" // switching and resetting the counter."},{"Add":" header_mut(current_page).set_n(n as u16);"},{"Add":""},{"Add":" // And set the leftmost child of the right page to"},{"Add":" // `r`."},{"Add":" L::set_right_child(&mut right, -1, r);"},{"Add":""},{"Add":" // Then, switch page and reset the counter."},{"Add":" current_page = &mut right;"},{"Add":" n = 0;"},{"Add":" } else {"},{"Add":" // Else, we're simply allocating a new entry on the"},{"Add":" // current page."},{"Add":" let off_new = {"},{"Add":" let hdr = header_mut(current_page);"},{"Add":" let data = hdr.data();"},{"Add":" assert!("},{"Add":" HDR + hdr.n() as usize * L::OFFSET_SIZE + L::OFFSET_SIZE + size"},{"Add":" < data as usize"},{"Add":" );"},{"Add":" // Move the data pointer `size` bytes to the left."},{"Add":" hdr.set_data(data - size as u16);"},{"Add":" // And increase the number of entries, and"},{"Add":" // occupied size of the page."},{"Add":" hdr.incr(size + L::OFFSET_SIZE);"},{"Add":" data - size as u16"},{"Add":" };"},{"Add":" // Copy the entry."},{"Add":" core::ptr::copy_nonoverlapping("},{"Add":" ptr,"},{"Add":" current_page.0.data.offset(off_new as isize),"},{"Add":" size,"},{"Add":" );"},{"Add":" // And set the offset."},{"Add":" L::set_offset(current_page, n, r | (off_new as u64));"},{"Add":" n += 1;"},{"Add":" }"},{"Add":" total += size + L::OFFSET_SIZE;"},{"Add":" }"},{"Add":" }"},{"Add":" header_mut(current_page).set_n(n as u16);"},{"Add":""},{"Add":" // Finally, it is possible that we haven't had a chance to do the"},{"Add":" // insertions yet: this is the case iff we're inserting at the end"},{"Add":" // of all the entries, so handle this now."},{"Add":" if u == s.0.len() {"},{"Add":" if let Some((k1, v1)) = k1v1 {"},{"Add":" L::alloc_write(current_page, k0, v0, 0, l0, &mut n);"},{"Add":" L::alloc_write(current_page, k1, v1, 0, r0, &mut n);"},{"Add":" } else {"},{"Add":" L::alloc_write(current_page, k0, v0, l0, r0, &mut n);"},{"Add":" }"},{"Add":" }"},{"Add":" let (split_key, split_value) = split.unwrap();"},{"Add":" Ok(Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed: if page.is_dirty() {"},{"Add":" page.offset | 1"},{"Add":" } else {"},{"Add":" page.offset"},{"Add":" },"},{"Add":" })"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"header.rs","metadata":0},"context":[{"change":0,"pos":61868}],"contents":[{"Add":"use crate::PAGE_SIZE;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"#[repr(C)]"},{"Add":"pub struct Header {"},{"Add":" data: u16,"},{"Add":" n: u16,"},{"Add":" crc: u32,"},{"Add":" left_page: u64,"},{"Add":"}"},{"Add":""},{"Add":"impl Header {"},{"Add":" pub(crate) fn init(&mut self) {"},{"Add":" self.data = (((PAGE_SIZE as u16) << 3) | 1).to_le();"},{"Add":" self.n = 0;"},{"Add":" self.crc = 0;"},{"Add":" self.left_page = 0;"},{"Add":" }"},{"Add":""},{"Add":" pub(crate) fn n(&self) -> u16 {"},{"Add":" u16::from_le(self.n)"},{"Add":" }"},{"Add":""},{"Add":" pub(crate) fn set_n(&mut self, n: u16) {"},{"Add":" self.n = n.to_le();"},{"Add":" }"},{"Add":""},{"Add":" pub fn left_page(&self) -> u64 {"},{"Add":" u64::from_le(self.left_page)"},{"Add":" }"},{"Add":""},{"Add":" pub fn set_left_page(&mut self, l: u64) {"},{"Add":" self.left_page = l.to_le()"},{"Add":" }"},{"Add":""},{"Add":" pub fn data(&self) -> u16 {"},{"Add":" u16::from_le(self.data) >> 3"},{"Add":" }"},{"Add":""},{"Add":" pub fn set_data(&mut self, d: u16) {"},{"Add":" let dirty = u16::from_le(self.data) & 7;"},{"Add":" self.data = ((d << 3) | dirty).to_le()"},{"Add":" }"},{"Add":""},{"Add":" pub fn decr(&mut self, s: usize) {"},{"Add":" self.left_page = (self.left_page() - s as u64).to_le();"},{"Add":" }"},{"Add":""},{"Add":" pub fn set_occupied(&mut self, size: u64) {"},{"Add":" self.left_page = ((self.left_page() & !0xfff) | size).to_le()"},{"Add":" }"},{"Add":""},{"Add":" pub fn incr(&mut self, s: usize) {"},{"Add":" self.left_page = (self.left_page() + s as u64).to_le();"},{"Add":" }"},{"Add":""},{"Add":" pub fn is_leaf(&self) -> bool {"},{"Add":" u64::from_le(self.left_page) <= 0xfff"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub const HDR: usize = core::mem::size_of::

();"},{"Add":""},{"Add":"pub(crate) fn header<'a>(page: crate::Page<'a>) -> &'a Header {"},{"Add":" unsafe { &*(page.data.as_ptr() as *const Header) }"},{"Add":"}"},{"Add":""},{"Add":"pub fn header_mut(page: &mut crate::MutPage) -> &mut Header {"},{"Add":" unsafe { &mut *(page.0.data as *mut Header) }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"cursor.rs","metadata":0},"context":[{"change":0,"pos":61868}],"contents":[{"Add":"use super::{header, Header};"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"pub struct PageCursor {"},{"Add":" pub cur: isize,"},{"Add":" pub total: usize,"},{"Add":" pub is_leaf: bool,"},{"Add":"}"},{"Add":""},{"Add":"impl PageCursor {"},{"Add":" /// Initialise a cursor on page `p` at position `cur`, checking"},{"Add":" /// that `cur` is a valid position."},{"Add":" pub fn new(p: &crate::CowPage, cur: isize) -> Self {"},{"Add":" let hdr = unsafe { &*(p.data as *const Header) };"},{"Add":" assert!(cur >= -1 && cur < hdr.n() as isize);"},{"Add":" PageCursor {"},{"Add":" cur,"},{"Add":" total: hdr.n() as usize,"},{"Add":" is_leaf: hdr.is_leaf(),"},{"Add":" }"},{"Add":" }"},{"Add":" /// Initialise a cursor set after the last entry of page `p`."},{"Add":" pub fn after(p: &crate::CowPage) -> Self {"},{"Add":" let hdr = unsafe { &*(p.data as *const Header) };"},{"Add":" let total = hdr.n();"},{"Add":" PageCursor {"},{"Add":" cur: total as isize,"},{"Add":" total: total as usize,"},{"Add":" is_leaf: hdr.is_leaf(),"},{"Add":" }"},{"Add":" }"},{"Add":" /// Initialise a cursor set on the last entry of page `p`."},{"Add":" pub fn last(p: crate::Page) -> Self {"},{"Add":" let hdr = header(p);"},{"Add":" let total = hdr.n();"},{"Add":" PageCursor {"},{"Add":" cur: (total - 1) as isize,"},{"Add":" total: total as usize,"},{"Add":" is_leaf: hdr.is_leaf(),"},{"Add":" }"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"alloc.rs","metadata":0},"context":[{"change":0,"pos":61868}],"contents":[{"Add":"use super::header::{header, header_mut, Header, HDR};"},{"Add":"use super::*;"},{"Add":""},{"Add":"/// We'd love to share this trait with the sized implementation, but"},{"Add":"/// unfortunately, the type parameters of almost all methods are"},{"Add":"/// different."},{"Add":"pub(crate) trait Alloc {"},{"Add":" const OFFSET_SIZE: usize;"},{"Add":""},{"Add":" /// Size (including the offset size) of the entry at position"},{"Add":" /// `cur`."},{"Add":" fn current_size("},{"Add":" page: crate::Page,"},{"Add":" cur: isize,"},{"Add":" ) -> usize;"},{"Add":""},{"Add":" /// Can we allocate an entry of `size` bytes, where `size` doesn't"},{"Add":" /// include the offset bytes?"},{"Add":" fn can_alloc(hdr: &Header, size: usize, n: usize) -> bool {"},{"Add":" (HDR as usize) + (hdr.n() as usize) * Self::OFFSET_SIZE + n * Self::OFFSET_SIZE + size"},{"Add":" <= hdr.data() as usize"},{"Add":" }"},{"Add":""},{"Add":" /// If we cloned the page, could we allocate an entry of `size`"},{"Add":" /// bytes, where `size` doesn't include the offset bytes?"},{"Add":" fn can_compact(hdr: &Header, size: isize, n: usize) -> bool {"},{"Add":" (HDR as isize)"},{"Add":" + ((hdr.left_page() & 0xfff) as isize)"},{"Add":" + (n * Self::OFFSET_SIZE) as isize"},{"Add":" + size"},{"Add":" <= PAGE_SIZE as isize"},{"Add":" }"},{"Add":""},{"Add":" /// Set the right child of the `n`th entry to `r`. If `n == -1`,"},{"Add":" /// this method can be used to set the leftmost child of a page."},{"Add":" fn set_right_child(_new: &mut MutPage, _n: isize, _r: u64) {}"},{"Add":""},{"Add":" /// Set the n^th offset on the page to `r`, which encodes a page"},{"Add":" /// offset in its 52 MSBs, and an offset on the page in its 12 LSBs."},{"Add":" fn set_offset(new: &mut MutPage, n: isize, r: u64);"},{"Add":""},{"Add":" /// The type of offsets, u64 in internal nodes, u16 in leaves."},{"Add":" type Offset: Into<(u64, usize)> + Copy + core::fmt::Debug;"},{"Add":""},{"Add":" fn offset_slice<'a>(page: crate::Page<'a>) -> Offsets<'a, Self::Offset>;"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"pub struct Offsets<'a, A>(pub &'a [A]);"},{"Add":""},{"Add":"impl<'a, A: Copy> Offsets<'a, A> {"},{"Add":" pub fn split_at(self, mid: usize) -> (Self, Self) {"},{"Add":" if mid < self.0.len() {"},{"Add":" let (a, b) = self.0.split_at(mid);"},{"Add":" (Offsets(a), Offsets(b))"},{"Add":" } else {"},{"Add":" debug_assert_eq!(mid, self.0.len());"},{"Add":" (self, Offsets(&[][..]))"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub struct Leaf {}"},{"Add":"pub struct Internal {}"},{"Add":""},{"Add":"impl Alloc for Leaf {"},{"Add":" const OFFSET_SIZE: usize = 2;"},{"Add":""},{"Add":" // Note: the size returned by this function includes the offset."},{"Add":" fn current_size("},{"Add":" page: crate::Page,"},{"Add":" cur: isize,"},{"Add":" ) -> usize {"},{"Add":" // Find the offset of the current position, get its size."},{"Add":" unsafe {"},{"Add":" debug_assert!(cur >= 0);"},{"Add":" let off = *(page.data.as_ptr().add(HDR + 2 * cur as usize) as *const u16);"},{"Add":" Self::OFFSET_SIZE"},{"Add":" + entry_size::(page.data.as_ptr().add(u16::from_le(off) as usize))"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn set_offset(new: &mut MutPage, n: isize, off: u64) {"},{"Add":" unsafe {"},{"Add":" let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;"},{"Add":" *ptr = (off as u16).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" type Offset = LeafOffset;"},{"Add":""},{"Add":" fn offset_slice<'a>(page: crate::Page<'a>) -> Offsets<'a, Self::Offset> {"},{"Add":" let hdr_n = header(page).n();"},{"Add":" unsafe {"},{"Add":" Offsets(core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const LeafOffset,"},{"Add":" hdr_n as usize,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Alloc for Internal {"},{"Add":" const OFFSET_SIZE: usize = 8;"},{"Add":" fn current_size("},{"Add":" page: crate::Page,"},{"Add":" cur: isize,"},{"Add":" ) -> usize {"},{"Add":" unsafe {"},{"Add":" 8 + entry_size::(page.data.as_ptr().add("},{"Add":" (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).offset(cur)) & 0xfff)"},{"Add":" as usize,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Set the right-hand child in the offset array, preserving the"},{"Add":" /// current offset."},{"Add":" fn set_right_child(page: &mut MutPage, n: isize, r: u64) {"},{"Add":" unsafe {"},{"Add":" debug_assert_eq!(r & 0xfff, 0);"},{"Add":" let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;"},{"Add":" let off = u64::from_le(*ptr) & 0xfff;"},{"Add":" *ptr = (r | off as u64).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn set_offset(new: &mut MutPage, n: isize, off: u64) {"},{"Add":" unsafe {"},{"Add":" let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;"},{"Add":" *ptr = off.to_le();"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" type Offset = InternalOffset;"},{"Add":""},{"Add":" fn offset_slice<'a>(page: crate::Page<'a>) -> Offsets<'a, Self::Offset> {"},{"Add":" let hdr_n = header(page).n() as usize;"},{"Add":" unsafe {"},{"Add":" Offsets(core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const InternalOffset,"},{"Add":" hdr_n,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"#[repr(C)]"},{"Add":"pub struct LeafOffset(u16);"},{"Add":""},{"Add":"impl Into<(u64, usize)> for LeafOffset {"},{"Add":" fn into(self) -> (u64, usize) {"},{"Add":" (0, self.0 as usize)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Into for LeafOffset {"},{"Add":" fn into(self) -> usize {"},{"Add":" self.0 as usize"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"#[repr(C)]"},{"Add":"pub struct InternalOffset(u64);"},{"Add":""},{"Add":"impl Into<(u64, usize)> for InternalOffset {"},{"Add":" fn into(self) -> (u64, usize) {"},{"Add":" (self.0 & !0xfff, (self.0 & 0xfff) as usize)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Into for InternalOffset {"},{"Add":" fn into(self) -> usize {"},{"Add":" self.0 as usize"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl AllocWrite for Leaf {"},{"Add":" fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {"},{"Add":" alloc_write::(new, k0, v0, l, r, n)"},{"Add":" }"},{"Add":" fn set_left_child(_new: &mut MutPage, _n: isize, l: u64) {"},{"Add":" debug_assert_eq!(l, 0);"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl AllocWrite for Internal {"},{"Add":" fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {"},{"Add":" alloc_write::(new, k0, v0, l, r, n)"},{"Add":" }"},{"Add":" fn set_left_child(new: &mut MutPage, n: isize, l: u64) {"},{"Add":" if l > 0 {"},{"Add":" Internal::set_right_child(new, n - 1, l);"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// Allocate a new entry and copy (k0, v0) into the new slot."},{"Add":"fn alloc_write("},{"Add":" new: &mut MutPage,"},{"Add":" k0: &K,"},{"Add":" v0: &V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" let size = alloc_size(k0, v0);"},{"Add":" let off_new = alloc_insert::(new, n, size, r);"},{"Add":" unsafe {"},{"Add":" let new_ptr = new.0.data.add(off_new);"},{"Add":" k0.write_to_page(new_ptr);"},{"Add":" let ks = k0.size();"},{"Add":" let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));"},{"Add":" v0.write_to_page(v_ptr);"},{"Add":" }"},{"Add":" if l > 0 {"},{"Add":" L::set_right_child(new, *n - 1, l);"},{"Add":" }"},{"Add":" *n += 1;"},{"Add":"}"},{"Add":""},{"Add":"/// Reserve space on the page for `size` bytes of data (i.e. not"},{"Add":"/// counting the offset), set the right child of the new position"},{"Add":"/// to `r`, add the offset to the new data to the offset array,"},{"Add":"/// and return the new offset."},{"Add":"fn alloc_insert("},{"Add":" new: &mut MutPage,"},{"Add":" n: &mut isize,"},{"Add":" size: usize,"},{"Add":" r: u64,"},{"Add":") -> usize {"},{"Add":" let hdr = header_mut(new);"},{"Add":" let data = hdr.data();"},{"Add":" // If we're here, the following assertion has been checked by the"},{"Add":" // `can_alloc` method."},{"Add":" debug_assert!(HDR + (hdr.n() as usize + 1) * L::OFFSET_SIZE + size <= data as usize);"},{"Add":" hdr.set_data(data - size as u16);"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.incr(L::OFFSET_SIZE + size);"},{"Add":" let off_new = data - size as u16;"},{"Add":" let hdr_n = hdr.n();"},{"Add":""},{"Add":" // Making space for the new offset"},{"Add":" unsafe {"},{"Add":" core::ptr::copy("},{"Add":" new.0.data.add(HDR + (*n as usize) * L::OFFSET_SIZE),"},{"Add":" new.0"},{"Add":" .data"},{"Add":" .add(HDR + (*n as usize) * L::OFFSET_SIZE + L::OFFSET_SIZE),"},{"Add":" (hdr_n as usize - (*n as usize)) * L::OFFSET_SIZE,"},{"Add":" );"},{"Add":" }"},{"Add":" L::set_offset(new, *n, r | (off_new as u64));"},{"Add":" off_new as usize"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"page.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"//! Implementation of B tree pages for Sized types, i.e. types whose"},{"Add":"//! representation has a size known at compile time (and the same as"},{"Add":"//! [`core::mem::size_of()`])."},{"Add":"//!"},{"Add":"//! The details of the implementation are as follows:"},{"Add":"//!"},{"Add":"//! - The page starts with a 16 bytes header of the following form"},{"Add":"//! (where all the fields are encoded in Little-Endian):"},{"Add":"//!"},{"Add":"//! ```"},{"Add":"//! #[repr(C)]"},{"Add":"//! pub struct Header {"},{"Add":""},{"Add":"//! /// Offset to the first entry in the page, shifted 3 bits"},{"Add":"//! /// to the right to allow for the dirty bit (plus two"},{"Add":"//! /// extra bits, zero for now), as explained in the"},{"Add":"//! /// documentation of CowPage, at the root of this"},{"Add":"//! /// crate. This is 4096 for empty pages, and it is unused"},{"Add":"//! /// for leaves. Moreover, this field can't be increased:"},{"Add":"//! /// when it reaches the bottom, the page must be cloned."},{"Add":"//! data: u16,"},{"Add":"//! /// Number of entries on the page."},{"Add":"//! n: u16,"},{"Add":"//! /// CRC (if used)."},{"Add":"//! crc: u32,"},{"Add":""},{"Add":"//! /// The 52 most significant bits are the left child of"},{"Add":"//! /// this page (0 for leaves), while the 12 LSBs represent"},{"Add":"//! /// the space this page would take when cloned from scratch,"},{"Add":"//! /// minus the header. The reason for this is that entries"},{"Add":"//! /// in internal nodes aren't really removed when deleted,"},{"Add":"//! /// they're only \"unlinked\" from the array of offsets (see"},{"Add":"//! /// below). Therefore, we must have a way to tell when a"},{"Add":"//! /// page can be \"compacted\" to reclaim space."},{"Add":""},{"Add":"//! left_page: u64,"},{"Add":"//! }"},{"Add":"//! ```"},{"Add":""},{"Add":"//! - For leaves, the rest of the page has the same representation as"},{"Add":"//! an array of length `n`, of elements of type `Tuple`:"},{"Add":"//! ```"},{"Add":"//! #[repr(C)]"},{"Add":"//! struct Tuple {"},{"Add":"//! k: K,"},{"Add":"//! v: V,"},{"Add":"//! }"},{"Add":"//! ```"},{"Add":"//! If the alignment of that structure is more than 16 bytes, we"},{"Add":"//! need to add some padding between the header and that array."},{"Add":""},{"Add":"//! - For internal nodes, the rest of the page starts with an array of"},{"Add":"//! length `n` of Little-Endian-encoded [`u64`], where the 12 least"},{"Add":"//! significant bits of each [`u64`] are an offset to a `Tuple` in"},{"Add":"//! the page, and the 52 other bits are an offset in the file to the"},{"Add":"//! right child of the entry."},{"Add":"//!"},{"Add":"//! Moreover, the offset represented by the 12 LSBs is after (or at)"},{"Add":"//! `header.data`."},{"Add":""},{"Add":"//! We say we can \"allocate\" in the page if the `data` of the header"},{"Add":"//! is greater than or equal to the position of the last \"offset\","},{"Add":"//! plus the size we want to allocate (note that since we allocate"},{"Add":"//! from the end of the page, `data` is always a multiple of the"},{"Add":"//! alignment of `Tuple`)."},{"Add":""},{"Add":"use super::*;"},{"Add":"use crate::btree::del::*;"},{"Add":"use crate::btree::put::*;"},{"Add":"use core::cmp::Ordering;"},{"Add":""},{"Add":"mod alloc; // The \"alloc\" trait, to provide common methods for leaves and internal nodes."},{"Add":""},{"Add":"mod put; // Inserting a new value onto a page (possibly splitting the page)."},{"Add":""},{"Add":"mod rebalance; // Rebalance two sibling pages to the left or to the right."},{"Add":""},{"Add":"use super::page_unsized::{cursor::PageCursor, header};"},{"Add":"use alloc::*;"},{"Add":"use header::*;"},{"Add":"use rebalance::*;"},{"Add":""},{"Add":"/// This struct is used to allocate a pair `(K, V)` on the stack, and"},{"Add":"/// copy it from a C pointer from a page."},{"Add":"///"},{"Add":"/// This is also used to form slices of pairs in order to use"},{"Add":"/// functions from the core library."},{"Add":"#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]"},{"Add":"#[repr(C)]"},{"Add":"struct Tuple {"},{"Add":" k: K,"},{"Add":" v: V,"},{"Add":"}"},{"Add":""},{"Add":"/// Empty type implementing `BTreePage` and `BTreeMutPage`."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Page {"},{"Add":" k: core::marker::PhantomData,"},{"Add":" v: core::marker::PhantomData,"},{"Add":"}"},{"Add":""},{"Add":"#[async_trait(?Send)]"},{"Add":"impl super::BTreePage for Page {"},{"Add":" // Cursors are quite straightforward. One non-trivial thing is"},{"Add":" // that they represent both a position on a page and the interval"},{"Add":" // from that position to the end of the page, as is apparent in"},{"Add":" // their `split_at` method."},{"Add":" //"},{"Add":" // Another thing to note is that -1 and `c.total` are valid"},{"Add":" // positions for a cursor `c`. The reason for this is that"},{"Add":" // position `-1` has a right child (which is the first element's"},{"Add":" // left child)."},{"Add":""},{"Add":" type Cursor = PageCursor;"},{"Add":""},{"Add":" fn is_empty(c: &Self::Cursor) -> bool {"},{"Add":" c.cur >= c.total as isize"},{"Add":" }"},{"Add":""},{"Add":" fn is_init(c: &Self::Cursor) -> bool {"},{"Add":" c.cur < 0"},{"Add":" }"},{"Add":""},{"Add":" fn cursor_before(p: &crate::CowPage) -> Self::Cursor {"},{"Add":" PageCursor::new(p, -1)"},{"Add":" }"},{"Add":""},{"Add":" fn cursor_after(p: &crate::CowPage) -> Self::Cursor {"},{"Add":" PageCursor::after(p)"},{"Add":" }"},{"Add":""},{"Add":" fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {"},{"Add":" ("},{"Add":" PageCursor {"},{"Add":" cur: 0,"},{"Add":" total: c.cur.max(0) as usize,"},{"Add":" is_leaf: c.is_leaf,"},{"Add":" },"},{"Add":" *c,"},{"Add":" )"},{"Add":" }"},{"Add":" fn move_next(c: &mut Self::Cursor) -> bool {"},{"Add":" if c.cur >= c.total as isize {"},{"Add":" return false;"},{"Add":" }"},{"Add":" c.cur += 1;"},{"Add":" true"},{"Add":" }"},{"Add":" fn move_prev(c: &mut Self::Cursor) -> bool {"},{"Add":" if c.cur < 0 {"},{"Add":" return false;"},{"Add":" }"},{"Add":" c.cur -= 1;"},{"Add":" true"},{"Add":" }"},{"Add":""},{"Add":" fn current<'a>("},{"Add":" page: crate::Page<'a>,"},{"Add":" c: &Self::Cursor,"},{"Add":" ) -> Option<(&'a K, &'a V, u64)> {"},{"Add":" // First, there's no current entry if the cursor is outside"},{"Add":" // the range of entries."},{"Add":" if c.cur < 0 || c.cur >= c.total as isize {"},{"Add":" None"},{"Add":" } else if c.is_leaf {"},{"Add":" // Else, if this is a leaf, the elements are packed"},{"Add":" // together in a contiguous array."},{"Add":" //"},{"Add":" // This means that the header may be followed by padding"},{"Add":" // (in order to align the entries). These are constants"},{"Add":" // known at compile-time, so `al` and `hdr` are optimised"},{"Add":" // away by the compiler."},{"Add":" let al = core::mem::align_of::>();"},{"Add":""},{"Add":" // The following is a way to compute the first multiple of"},{"Add":" // `al` after `HDR`, assuming `al` is a power of 2 (which"},{"Add":" // is always the case since we get it from `align_of`)."},{"Add":" let hdr = (HDR + al - 1) & !(al - 1);"},{"Add":""},{"Add":" // The position of the `Tuple` we're looking for is"},{"Add":" // `f * cur` bytes after the padded header (because"},{"Add":" // `size_of` includes alignment padding)."},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let kv = unsafe {"},{"Add":" &*(page.data.as_ptr().add(hdr + c.cur as usize * f) as *const Tuple)"},{"Add":" };"},{"Add":" Some((&kv.k, &kv.v, 0))"},{"Add":" } else {"},{"Add":" // Internal nodes have an extra level of indirection: we"},{"Add":" // first need to find `off`, the offset in the page, in"},{"Add":" // the initial array of offsets. Since these offsets are"},{"Add":" // `u64`, and the header is of size 16 bytes, the array is"},{"Add":" // already aligned."},{"Add":" unsafe {"},{"Add":" let off ="},{"Add":" u64::from_le(*(page.data.as_ptr().add(HDR + 8 * c.cur as usize) as *const u64));"},{"Add":" // Check that we aren't reading outside of the page"},{"Add":" // (for example because of a malformed offset)."},{"Add":" assert!((off as usize & 0xfff) + core::mem::size_of::>() <= 4096);"},{"Add":""},{"Add":" // Once we have the offset, cast its 12 LSBs to a"},{"Add":" // position in the page, and read the `Tuple` at"},{"Add":" // that position."},{"Add":" let kv = &*(page.data.as_ptr().add((off as usize) & 0xfff) as *const Tuple);"},{"Add":" Some((&kv.k, &kv.v, off & !0xfff))"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // The left and right child methods aren't really surprising. One"},{"Add":" // thing to note is that cursors are always in positions between"},{"Add":" // `-1` and `c.total` (bounds included), so we only have to check"},{"Add":" // one side of the bound in the assertions."},{"Add":" //"},{"Add":" // We also check, before entering the `unsafe` sections, that"},{"Add":" // we're only reading data that is on a page."},{"Add":" fn left_child(page: crate::Page, c: &Self::Cursor) -> u64 {"},{"Add":" if c.is_leaf {"},{"Add":" 0"},{"Add":" } else {"},{"Add":" assert!(c.cur >= 0 && HDR as isize + c.cur * 8 - 8 <= 4088);"},{"Add":" let off ="},{"Add":" unsafe { *(page.data.as_ptr().offset((HDR as isize + c.cur * 8) - 8) as *const u64) };"},{"Add":" u64::from_le(off) & !0xfff"},{"Add":" }"},{"Add":" }"},{"Add":" fn right_child(page: crate::Page, c: &Self::Cursor) -> u64 {"},{"Add":" if c.is_leaf {"},{"Add":" 0"},{"Add":" } else {"},{"Add":" assert!(c.cur < c.total as isize && HDR as isize + c.cur * 8 <= 4088);"},{"Add":" let off ="},{"Add":" unsafe { *(page.data.as_ptr().offset(HDR as isize + c.cur * 8) as *const u64) };"},{"Add":" u64::from_le(off) & !0xfff"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" async fn set_cursor<'a, 'b, T: LoadPage>("},{"Add":" _txn: &'a T,"},{"Add":" page: crate::Page<'b>,"},{"Add":" c: &mut PageCursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" ) -> Result<(&'a K, &'a V, u64), usize> {"},{"Add":" unsafe {"},{"Add":" // `lookup` has the same semantic as"},{"Add":" // `core::slice::binary_search`, i.e. it returns either"},{"Add":" // `Ok(n)`, where `n` is the position where `(k0, v0)` was"},{"Add":" // found, or `Err(n)` where `n` is the position where"},{"Add":" // `(k0, v0)` can be inserted to preserve the order."},{"Add":" match lookup(page, c, k0, v0).await {"},{"Add":" Ok(n) => {"},{"Add":" c.cur = n as isize;"},{"Add":" // Just read the tuple and return it."},{"Add":" if c.is_leaf {"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let tup ="},{"Add":" &*(page.data.as_ptr().add(hdr_size + f * n) as *const Tuple);"},{"Add":" Ok((&tup.k, &tup.v, 0))"},{"Add":" } else {"},{"Add":" let off ="},{"Add":" u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));"},{"Add":" let tup ="},{"Add":" &*(page.data.as_ptr().add(off as usize & 0xfff) as *const Tuple);"},{"Add":" Ok((&tup.k, &tup.v, off & !0xfff))"},{"Add":" }"},{"Add":" }"},{"Add":" Err(n) => {"},{"Add":" c.cur = n as isize;"},{"Add":" Err(n)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[async_trait(?Send)]"},{"Add":"impl super::BTreeMutPage"},{"Add":" for Page"},{"Add":"{"},{"Add":" // Once again, this is quite straightforward."},{"Add":" fn init(page: &mut MutPage) {"},{"Add":" let h = header_mut(page);"},{"Add":" h.init();"},{"Add":" }"},{"Add":""},{"Add":" // When deleting from internal nodes, we take a replacement from"},{"Add":" // one of the leaves (in our current implementation, the leftmost"},{"Add":" // entry of the right subtree). This method copies an entry from"},{"Add":" // the leaf onto the program stack, which is necessary since"},{"Add":" // deletions in leaves overwrites entries."},{"Add":" //"},{"Add":" // Another design choice would have been to do the same as for the"},{"Add":" // unsized implementation, but in this case this would have meant"},{"Add":" // copying the saved value to the end of the leaf, potentially"},{"Add":" // preventing merges, and not even saving a memory copy."},{"Add":" type Saved = (K, V);"},{"Add":""},{"Add":" fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved {"},{"Add":" unsafe {"},{"Add":" let mut k0 = core::mem::MaybeUninit::uninit();"},{"Add":" let mut v0 = core::mem::MaybeUninit::uninit();"},{"Add":" core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);"},{"Add":" core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1);"},{"Add":" (k0.assume_init(), v0.assume_init())"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {"},{"Add":" (core::mem::transmute(&s.0), core::mem::transmute(&s.1))"},{"Add":" }"},{"Add":""},{"Add":" // `put` inserts one or two entries onto a node (internal or"},{"Add":" // leaf). This is implemented in the `put` module."},{"Add":" async fn put<'a, T: AllocPage>("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" replace: bool,"},{"Add":" c: &PageCursor,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" k1v1: Option<(&'a K, &'a V)>,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" assert!(c.cur >= 0);"},{"Add":" // In the sized case, deletions can never cause a split, so we"},{"Add":" // never have to insert two elements at the same position."},{"Add":" assert!(k1v1.is_none());"},{"Add":" if r == 0 {"},{"Add":" put::put::<_, _, _, Leaf>(txn, page, mutable, replace, c.cur as usize, k0, v0, 0, 0).await"},{"Add":" } else {"},{"Add":" put::put::<_, _, _, Internal>(txn, page, mutable, replace, c.cur as usize, k0, v0, l, r).await"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn put_mut(page: &mut MutPage, c: &mut Self::Cursor, k0: &K, v0: &V, r: u64) {"},{"Add":" use super::page_unsized::AllocWrite;"},{"Add":" let mut n = c.cur;"},{"Add":" if r == 0 {"},{"Add":" Leaf::alloc_write(page, k0, v0, 0, r, &mut n);"},{"Add":" } else {"},{"Add":" Internal::alloc_write(page, k0, v0, 0, r, &mut n);"},{"Add":" }"},{"Add":" c.total += 1;"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn set_left_child(page: &mut MutPage, c: &Self::Cursor, l: u64) {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":""},{"Add":" // This function updates an internal node, setting the left child"},{"Add":" // of the cursor to `l`."},{"Add":" async fn update_left_child("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" l: u64,"},{"Add":" ) -> Result {"},{"Add":" assert!(!c.is_leaf && c.cur >= 0 && (c.cur as usize) <= c.total);"},{"Add":" let freed;"},{"Add":" let page = if mutable && page.is_dirty() {"},{"Add":" // If the page is mutable (dirty), just convert it to a"},{"Add":" // mutable page, and update."},{"Add":" freed = 0;"},{"Add":" MutPage(page)"},{"Add":" } else {"},{"Add":" // Else, clone the page."},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":" // First clone the left child of the page."},{"Add":" let l = header(page.as_page()).left_page() & !0xfff;"},{"Add":" let hdr = header_mut(&mut new);"},{"Add":" hdr.set_left_page(l);"},{"Add":" // And then the rest of the page."},{"Add":" let s = Internal::offset_slice::(page.as_page());"},{"Add":" clone::(page.as_page(), &mut new, s, &mut 0);"},{"Add":" // Mark the former version of the page as free."},{"Add":" freed = page.offset | if page.is_dirty() { 1 } else { 0 };"},{"Add":" new"},{"Add":" };"},{"Add":" // Finally, update the left child of the cursor."},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" Ok(Ok { page, freed })"},{"Add":" }"},{"Add":""},{"Add":" async fn del("},{"Add":" txn: &mut T,"},{"Add":" page: crate::CowPage,"},{"Add":" mutable: bool,"},{"Add":" c: &PageCursor,"},{"Add":" l: u64,"},{"Add":" ) -> Result<(MutPage, u64), T::Error> {"},{"Add":" assert!(c.cur >= 0 && (c.cur as usize) < c.total);"},{"Add":" if mutable && page.is_dirty() {"},{"Add":" // In the mutable case, we just need to move some memory"},{"Add":" // around."},{"Add":" let p = page.data;"},{"Add":" let mut page = MutPage(page);"},{"Add":" let hdr = header_mut(&mut page);"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" if c.is_leaf {"},{"Add":" // In leaves, we need to move the n - c - 1 elements"},{"Add":" // that are strictly after the cursor, by `f` (the"},{"Add":" // size of an entry)."},{"Add":" //"},{"Add":" // Here's the reasoning to avoid off-by-one errors: if"},{"Add":" // `c` is 0 (i.e. we're deleting the first element on"},{"Add":" // the page), we remove one entry, so there are n - 1"},{"Add":" // remaining entries."},{"Add":" let n = hdr.n() as usize;"},{"Add":" let hdr_size = {"},{"Add":" // As usual, header + padding"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" (HDR + al - 1) & !(al - 1)"},{"Add":" };"},{"Add":" let off = hdr_size + c.cur as usize * f;"},{"Add":" unsafe {"},{"Add":" core::ptr::copy(p.add(off + f), p.add(off), f * (n - c.cur as usize - 1));"},{"Add":" }"},{"Add":" // Removing `f` bytes from the page."},{"Add":" hdr.decr(f);"},{"Add":" } else {"},{"Add":" // Internal nodes are easier to deal with, as we just"},{"Add":" // have to move the offsets."},{"Add":" unsafe {"},{"Add":" let ptr = p.add(HDR + c.cur as usize * 8) as *mut u64;"},{"Add":" core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize - 1);"},{"Add":" }"},{"Add":" // Removing `f` bytes from the page (the tuple), plus"},{"Add":" // one 8-bytes offset."},{"Add":" hdr.decr(f + 8);"},{"Add":""},{"Add":" // Updating the left page if necessary."},{"Add":" if l > 0 {"},{"Add":" unsafe {"},{"Add":" let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" hdr.set_n(hdr.n() - 1);"},{"Add":" // Returning the mutable page itself, and 0 (for \"no page freed\")"},{"Add":" Ok((page, 0))"},{"Add":" } else {"},{"Add":" // Immutable pages need to be cloned. The strategy is the"},{"Add":" // same in both cases: get an \"offset slice\", split it at"},{"Add":" // the cursor, remove the first entry of the second half,"},{"Add":" // and clone."},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":" if c.is_leaf {"},{"Add":" let s = Leaf::offset_slice::(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(c.cur as usize);"},{"Add":" let (_, s1) = s1.split_at(1);"},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":" } else {"},{"Add":" // Internal nodes a bit trickier, since the left child"},{"Add":" // is not counted in the \"offset slice\", so we need to"},{"Add":" // clone it separately. Also, the `l` argument to this"},{"Add":" // function might be non-zero in this case."},{"Add":" let s = Internal::offset_slice::(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(c.cur as usize);"},{"Add":" let (_, s1) = s1.split_at(1);"},{"Add":""},{"Add":" // First, clone the left child of the page."},{"Add":" let hdr = header(page.as_page());"},{"Add":" let left = hdr.left_page() & !0xfff;"},{"Add":" unsafe { *(new.0.data.add(HDR - 8) as *mut u64) = left.to_le() };"},{"Add":""},{"Add":" // Then, clone the entries strictly before the cursor"},{"Add":" // (i.e. clone `s0`)."},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":""},{"Add":" // If we need to update the left child of the deleted"},{"Add":" // item, do it."},{"Add":" if l > 0 {"},{"Add":" unsafe {"},{"Add":" let off = new.0.data.offset(HDR as isize + (n - 1) * 8) as *mut u64;"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Finally, clone the right half of the page (`s1`)."},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":" }"},{"Add":" Ok((new, page.offset))"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Decide what to do with the concatenation of two neighbouring"},{"Add":" // pages, with a middle element."},{"Add":" async fn merge_or_rebalance<'a, T: AllocPage>("},{"Add":" txn: &mut T,"},{"Add":" m: Concat<'a, K, V, Self>,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" // First evaluate the size of the middle element on a page."},{"Add":" let (hdr_size, mid_size) = if m.modified.c0.is_leaf {"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" ("},{"Add":" (HDR + al - 1) & !(al - 1),"},{"Add":" core::mem::size_of::>(),"},{"Add":" )"},{"Add":" } else {"},{"Add":" (HDR, 8 + core::mem::size_of::>())"},{"Add":" };"},{"Add":""},{"Add":" // Evaluate the size of the modified half of the concatenation"},{"Add":" // (which includes the header)."},{"Add":" let mod_size = size::(&m.modified);"},{"Add":" // Add the \"occupied\" size (which excludes the header)."},{"Add":" let occupied = {"},{"Add":" let hdr = header(m.other.as_page());"},{"Add":" (hdr.left_page() & 0xfff) as usize"},{"Add":" };"},{"Add":""},{"Add":" // One surprising observation here is that adding the sizes"},{"Add":" // works. This is surprising because of alignment and"},{"Add":" // padding. It works because we can split the sizes into an"},{"Add":" // offset part (always 8 bytes) and a data part (of a constant"},{"Add":" // alignment), and thus we never need any padding anywhere on"},{"Add":" // the page."},{"Add":" if mod_size + mid_size + occupied <= PAGE_SIZE {"},{"Add":" // If the concatenation fits on a page, merge."},{"Add":" return if m.modified.c0.is_leaf {"},{"Add":" super::page_unsized::merge::<_, _, _, _, Leaf>(txn, m).await"},{"Add":" } else {"},{"Add":" super::page_unsized::merge::<_, _, _, _, Internal>(txn, m).await"},{"Add":" };"},{"Add":" }"},{"Add":" // If the modified page is large enough, or if the other page"},{"Add":" // has only just barely the minimum number of elements to be"},{"Add":" // at least half-full, return."},{"Add":" //"},{"Add":" // The situation where the other page isn't full enough might"},{"Add":" // happen for example if elements occupy exactly 1/5th of a"},{"Add":" // page + 1 byte, and the modified page has 2 of them after"},{"Add":" // the deletion, while the other page has 3."},{"Add":" if mod_size >= PAGE_SIZE / 2 || hdr_size + occupied - mid_size < PAGE_SIZE / 2 {"},{"Add":" if let Some((k, v)) = m.modified.ins {"},{"Add":" // Perform the required modification and return."},{"Add":" return Ok(Op::Put(Self::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" m.modified.skip_first,"},{"Add":" &m.modified.c1,"},{"Add":" k,"},{"Add":" v,"},{"Add":" m.modified.ins2,"},{"Add":" m.modified.l,"},{"Add":" m.modified.r,"},{"Add":" ).await?));"},{"Add":" } else if m.modified.skip_first {"},{"Add":" // `ins2` is only ever used when the page immediately"},{"Add":" // below a deletion inside an internal node has split,"},{"Add":" // and we need to replace the deleted value, *and*"},{"Add":" // insert the middle entry of the split."},{"Add":" debug_assert!(m.modified.ins2.is_none());"},{"Add":" let (page, freed) = Self::del("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &m.modified.c1,"},{"Add":" m.modified.l,"},{"Add":" ).await?;"},{"Add":" return Ok(Op::Put(Put::Ok(Ok { page, freed })));"},{"Add":" } else {"},{"Add":" let mut c1 = m.modified.c1.clone();"},{"Add":" let mut l = m.modified.l;"},{"Add":" if l == 0 {"},{"Add":" Self::move_next(&mut c1);"},{"Add":" l = m.modified.r;"},{"Add":" }"},{"Add":" return Ok(Op::Put(Put::Ok(Self::update_left_child("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &c1,"},{"Add":" l,"},{"Add":" ).await?)));"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Finally, if we're here, we can rebalance. There are four"},{"Add":" // (relatively explicit) cases, see the `rebalance` submodule"},{"Add":" // to see how this is done."},{"Add":" if m.mod_is_left {"},{"Add":" if m.modified.c0.is_leaf {"},{"Add":" rebalance_left::<_, _, _, Leaf>(txn, m).await"},{"Add":" } else {"},{"Add":" rebalance_left::<_, _, _, Internal>(txn, m).await"},{"Add":" }"},{"Add":" } else {"},{"Add":" super::page_unsized::rebalance::rebalance_right::<_, _, _, Self>(txn, m).await"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Size of a modified page (including the header)."},{"Add":"fn size(m: &ModifiedPage>) -> usize {"},{"Add":" let mut total = {"},{"Add":" let hdr = header(m.page.as_page());"},{"Add":" (hdr.left_page() & 0xfff) as usize"},{"Add":" };"},{"Add":" if m.c1.is_leaf {"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" total += (HDR + al - 1) & (!al - 1);"},{"Add":" } else {"},{"Add":" total += HDR"},{"Add":" };"},{"Add":""},{"Add":" // Extra size for the offsets."},{"Add":" let extra = if m.c1.is_leaf { 0 } else { 8 };"},{"Add":""},{"Add":" if m.ins.is_some() {"},{"Add":" total += extra + core::mem::size_of::>();"},{"Add":" if m.ins2.is_some() {"},{"Add":" total += extra + core::mem::size_of::>()"},{"Add":" }"},{"Add":" }"},{"Add":" // If we skip the first entry of `m.c1`, remove its size."},{"Add":" if m.skip_first {"},{"Add":" total -= extra + core::mem::size_of::>()"},{"Add":" }"},{"Add":" total"},{"Add":"}"},{"Add":""},{"Add":"/// Linear search, leaf version. This is relatively straightforward."},{"Add":"fn leaf_linear_search("},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" s: &[Tuple],"},{"Add":") -> Result {"},{"Add":" let mut n = 0;"},{"Add":" for sm in s.iter() {"},{"Add":" match sm.k.compare(k0) {"},{"Add":" Ordering::Less => n += 1,"},{"Add":" Ordering::Greater => return Err(n),"},{"Add":" Ordering::Equal => {"},{"Add":" if let Some(v0) = v0 {"},{"Add":" match sm.v.compare(v0) {"},{"Add":" Ordering::Less => n += 1,"},{"Add":" Ordering::Greater => return Err(n),"},{"Add":" Ordering::Equal => return Ok(n),"},{"Add":" }"},{"Add":" } else {"},{"Add":" return Ok(n);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" Err(n)"},{"Add":"}"},{"Add":""},{"Add":"/// An equivalent of `Ord::cmp` on `Tuple` but using"},{"Add":"/// `Storable::compare` instead of `Ord::cmp` on `K` and `V`."},{"Add":"fn cmp("},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" p: &[u8; 4096],"},{"Add":" off: u64,"},{"Add":") -> Ordering {"},{"Add":" let off = u64::from_le(off) & 0xfff;"},{"Add":" if off as usize + core::mem::size_of::>() > PAGE_SIZE {"},{"Add":" panic!("},{"Add":" \"off = {:?}, size = {:?}\","},{"Add":" off,"},{"Add":" core::mem::size_of::>()"},{"Add":" );"},{"Add":" }"},{"Add":" let tup = unsafe { &*(p.as_ptr().offset(off as isize & 0xfff) as *const Tuple) };"},{"Add":" match tup.k.compare(k0) {"},{"Add":" Ordering::Equal => {"},{"Add":" if let Some(v0) = v0 {"},{"Add":" tup.v.compare(v0)"},{"Add":" } else {"},{"Add":" Ordering::Equal"},{"Add":" }"},{"Add":" }"},{"Add":" o => o,"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Linear search for internal nodes. Does what it says."},{"Add":"unsafe fn internal_search("},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" s: &[u64],"},{"Add":" p: &[u8; 4096],"},{"Add":") -> Result {"},{"Add":" for (n, off) in s.iter().enumerate() {"},{"Add":" match cmp(k0, v0, p, *off) {"},{"Add":" Ordering::Less => {}"},{"Add":" Ordering::Greater => return Err(n),"},{"Add":" Ordering::Equal => return Ok(n),"},{"Add":" }"},{"Add":" }"},{"Add":" Err(s.len())"},{"Add":"}"},{"Add":""},{"Add":"/// Lookup just forms slices of offsets (for internal nodes) or values"},{"Add":"/// (for leaves), and runs an internal search on them."},{"Add":"async unsafe fn lookup<'a, K: Storable, V: Storable>("},{"Add":" page: crate::Page<'a>,"},{"Add":" c: &mut PageCursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":") -> Result {"},{"Add":" let hdr = header(page);"},{"Add":" c.total = hdr.n() as usize;"},{"Add":" c.is_leaf = hdr.is_leaf();"},{"Add":" if c.is_leaf {"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let s = core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(hdr_size) as *const Tuple,"},{"Add":" hdr.n() as usize,"},{"Add":" );"},{"Add":" leaf_linear_search(k0, v0, s)"},{"Add":" } else {"},{"Add":" let s = core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const u64,"},{"Add":" hdr.n() as usize,"},{"Add":" );"},{"Add":" internal_search(k0, v0, s, page.data)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Clone a slice of offsets onto a page. This essentially does what"},{"Add":"/// it says. Note that the leftmost child of a page is not included in"},{"Add":"/// the offset slices, so we don't have to handle it here."},{"Add":"///"},{"Add":"/// This should really be in the `Alloc` trait, but Rust doesn't have"},{"Add":"/// associated type constructors, so we can't have an associated type"},{"Add":"/// that's sometimes a slice and sometimes a \"Range\"."},{"Add":"fn clone("},{"Add":" page: crate::Page,"},{"Add":" new: &mut MutPage,"},{"Add":" s: Offsets,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" match s {"},{"Add":" Offsets::Slice(s) => {"},{"Add":" // We know we're in an internal node here."},{"Add":" let size = core::mem::size_of::>();"},{"Add":" for off in s.iter() {"},{"Add":" let off = u64::from_le(*off);"},{"Add":" let r = off & !0xfff;"},{"Add":" let off = off & 0xfff;"},{"Add":" unsafe {"},{"Add":" let ptr = page.data.as_ptr().add(off as usize);"},{"Add":""},{"Add":" // Reserve the space on the page"},{"Add":" let hdr = header_mut(new);"},{"Add":" let data = hdr.data() as u16;"},{"Add":" let off_new = data - size as u16;"},{"Add":" hdr.set_data(off_new);"},{"Add":""},{"Add":" // Copy the entry from the original page to its"},{"Add":" // position on the new page."},{"Add":" core::ptr::copy_nonoverlapping(ptr, new.0.data.add(off_new as usize), size);"},{"Add":""},{"Add":" // Set the offset to this new entry in the offset"},{"Add":" // array, along with the right child page."},{"Add":" let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;"},{"Add":" *ptr = (r | off_new as u64).to_le();"},{"Add":" }"},{"Add":" *n += 1;"},{"Add":" }"},{"Add":" let hdr = header_mut(new);"},{"Add":" hdr.set_n(hdr.n() + s.len() as u16);"},{"Add":" hdr.incr((8 + size) * s.len());"},{"Add":" }"},{"Add":" Offsets::Range(r) => {"},{"Add":" let size = core::mem::size_of::>();"},{"Add":" let a = core::mem::align_of::>();"},{"Add":" let header_size = (HDR + a - 1) & !(a - 1);"},{"Add":" let len = r.len();"},{"Add":" for off in r {"},{"Add":" unsafe {"},{"Add":" let ptr = page.data.as_ptr().add(header_size + off * size);"},{"Add":" let new_ptr = new.0.data.add(header_size + (*n as usize) * size);"},{"Add":" core::ptr::copy_nonoverlapping(ptr, new_ptr, size);"},{"Add":" }"},{"Add":" *n += 1;"},{"Add":" }"},{"Add":" // On leaves, we do have to update everything manually,"},{"Add":" // because we're simply copying stuff."},{"Add":" let hdr = header_mut(new);"},{"Add":" hdr.set_n(hdr.n() + len as u16);"},{"Add":" hdr.incr(size * len);"},{"Add":" }"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"page","metadata":576},"context":[{"change":0,"pos":12617}],"contents":[]}},{"FileAdd":{"meta":{"basename":"rebalance.rs","metadata":0},"context":[{"change":0,"pos":125961}],"contents":[{"Add":"use super::*;"},{"Add":"use core::mem::MaybeUninit;"},{"Add":""},{"Add":"pub(crate) async fn rebalance_left<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: Storable + core::fmt::Debug,"},{"Add":" V: Storable + core::fmt::Debug,"},{"Add":" L: Alloc,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" m: Concat<'a, K, V, Page>,"},{"Add":") -> Result, T::Error> {"},{"Add":" assert!(m.mod_is_left);"},{"Add":" // First element of the right page. We'll rotate it to the left"},{"Add":" // page, i.e. return a middle element, and append the current"},{"Add":" // middle element to the left page."},{"Add":" let rc = super::PageCursor::new(&m.other, 0);"},{"Add":" let rl = >::left_child(m.other.as_page(), &rc);"},{"Add":" let (k, v, r) = >::current(m.other.as_page(), &rc).unwrap();"},{"Add":""},{"Add":" let mut freed_ = [0, 0];"},{"Add":""},{"Add":" // First, perform the modification on the modified page, which we"},{"Add":" // know is the left page, and return the resulting mutable page"},{"Add":" // (the modified page may or may not be mutable before we do this)."},{"Add":" let new_left = if let Some((k, v)) = m.modified.ins {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let page = if let Put::Ok(Ok { page, freed }) = >::put("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" m.modified.skip_first,"},{"Add":" &m.modified.c1,"},{"Add":" k,"},{"Add":" v,"},{"Add":" m.modified.ins2,"},{"Add":" m.modified.l,"},{"Add":" m.modified.r,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b;"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" };"},{"Add":" // Append the middle element of the concatenation at the end"},{"Add":" // of the left page. We know the left page to be mutable by"},{"Add":" // now, and we also know there's enough space to do this."},{"Add":" let lc = PageCursor::after(&page.0);"},{"Add":" if let Put::Ok(Ok { page, freed }) = >::put("},{"Add":" txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" // index 0 is ok here: if a page is freed, it means we"},{"Add":" // just compacted a page, which implies that the call"},{"Add":" // to `put` above didn't free."},{"Add":" freed_[0] = freed | b"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" } else if m.modified.skip_first {"},{"Add":" // Looking at module `super::del`, the only way we can be in"},{"Add":" // this case"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let (page, freed) = >::del("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &m.modified.c1,"},{"Add":" m.modified.l,"},{"Add":" ).await?;"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b"},{"Add":" }"},{"Add":" // Append the middle element of the concatenation at the end"},{"Add":" // of the left page. We know the left page to be mutable by"},{"Add":" // now, and we also know there's enough space to do this."},{"Add":" let lc = PageCursor::after(&page.0);"},{"Add":" if let Put::Ok(Ok { page, freed }) = >::put("},{"Add":" txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,"},{"Add":" ).await? {"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" // index 0 is ok here: if we freed a page in the call"},{"Add":" // to `del` above, it is mutable and we can allocate"},{"Add":" // on it. Else, we just compacted a page, but that"},{"Add":" // also means `del` above didn't free."},{"Add":" freed_[0] = freed | b"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" } else {"},{"Add":" let is_dirty = m.modified.page.is_dirty();"},{"Add":" let lc = PageCursor::after(&m.modified.page);"},{"Add":" if let Put::Ok(Ok { page, freed }) = >::put("},{"Add":" txn, m.modified.page, m.modified.mutable, false, &lc, m.mid.0, m.mid.1, None, 0, rl,"},{"Add":" ).await? {"},{"Add":" if m.modified.l > 0 {"},{"Add":" assert_eq!(m.modified.r, 0);"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur - 1);"},{"Add":" *off = (m.modified.l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" } else if m.modified.r > 0 {"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur);"},{"Add":" *off = (m.modified.r | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":" if freed > 0 {"},{"Add":" let b = if is_dirty { 1 } else { 0 };"},{"Add":" freed_[0] = freed | b"},{"Add":" }"},{"Add":" page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let (new_right, k, v) = if r == 0 && m.other_is_mutable && m.other.is_dirty() {"},{"Add":" // Since `r == 0`, we know this is a leaf. Therefore, we need"},{"Add":" // to rewrite the deleted element to the end of the page, so"},{"Add":" // that the pointer to the new middle entry is valid when this"},{"Add":" // function returns."},{"Add":" let data = m.other.data;"},{"Add":" let mut other = MutPage(m.other);"},{"Add":" let right_hdr = header_mut(&mut other);"},{"Add":" // Remove the space for one entry."},{"Add":" let n = right_hdr.n() as usize;"},{"Add":" right_hdr.decr(f);"},{"Add":" right_hdr.set_n((n - 1) as u16);"},{"Add":""},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let mut t: MaybeUninit> = MaybeUninit::uninit();"},{"Add":" unsafe {"},{"Add":" // Save the leftmost element (we can't directly copy it to"},{"Add":" // the end, because the page may be full)."},{"Add":" core::ptr::copy_nonoverlapping("},{"Add":" data.add(hdr_size) as *mut Tuple,"},{"Add":" t.as_mut_ptr(),"},{"Add":" 1,"},{"Add":" );"},{"Add":" // Move the n - 1 last elements one entry to the left."},{"Add":" core::ptr::copy("},{"Add":" data.add(hdr_size + f) as *const Tuple,"},{"Add":" data.add(hdr_size) as *mut Tuple,"},{"Add":" n - 1,"},{"Add":" );"},{"Add":" // Copy the last element to the end of the page."},{"Add":" let last = data.add(hdr_size + f * (n - 1)) as *mut Tuple;"},{"Add":" core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);"},{"Add":" (other, &(&*last).k, &(&*last).v)"},{"Add":" }"},{"Add":" } else {"},{"Add":" // If this isn't a leaf, or isn't mutable, use the standard"},{"Add":" // deletion function, because we know this will leave the"},{"Add":" // pointer to the current entry valid."},{"Add":""},{"Add":" // We extend the pointer's lifetime here, because we know the"},{"Add":" // current deletion (we only rebalance during deletions) won't"},{"Add":" // touch this page anymore after this."},{"Add":" let k = unsafe { core::mem::transmute(k) };"},{"Add":" let v = unsafe { core::mem::transmute(v) };"},{"Add":""},{"Add":" // If this frees the old \"other\" page, add it to the \"freed\""},{"Add":" // array."},{"Add":" let is_dirty = m.other.is_dirty();"},{"Add":" let (page, freed) = >::del(txn, m.other, m.other_is_mutable, &rc, r).await?;"},{"Add":" if freed > 0 {"},{"Add":" freed_[1] = if is_dirty { freed | 1 } else { freed };"},{"Add":" }"},{"Add":" (page, k, v)"},{"Add":" };"},{"Add":" Ok(Op::Rebalanced {"},{"Add":" l: new_left.0.offset,"},{"Add":" r: new_right.0.offset,"},{"Add":" k,"},{"Add":" v,"},{"Add":" freed: freed_,"},{"Add":" })"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"put.rs","metadata":0},"context":[{"change":0,"pos":125961}],"contents":[{"Add":"use super::*;"},{"Add":""},{"Add":"pub(super) async fn put<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: Storable + core::fmt::Debug,"},{"Add":" V: Storable + core::fmt::Debug,"},{"Add":" L: Alloc + super::super::page_unsized::AllocWrite,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" replace: bool,"},{"Add":" u: usize,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":") -> Result, T::Error> {"},{"Add":" let hdr = header(page.as_page());"},{"Add":" let is_dirty = page.is_dirty();"},{"Add":" if mutable && is_dirty && L::can_alloc::(hdr) {"},{"Add":" // If the page is mutable (i.e. not shared with another tree)"},{"Add":" // and dirty, here's what we do:"},{"Add":" let mut page = MutPage(page);"},{"Add":" let p = page.0.data;"},{"Add":" let hdr = header_mut(&mut page);"},{"Add":" let mut n = u as isize;"},{"Add":" if replace {"},{"Add":" // If we're replacing a value, this can't be in a leaf,"},{"Add":" // hence the only thing that needs to be done is erasing"},{"Add":" // the offset in the offset array. This is a bit naive,"},{"Add":" // since we're moving that array back and forth."},{"Add":" assert!(!hdr.is_leaf());"},{"Add":" unsafe {"},{"Add":" let ptr = p.add(HDR + n as usize * 8) as *mut u64;"},{"Add":" core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - n as usize - 1);"},{"Add":" hdr.decr(8 + core::mem::size_of::>());"},{"Add":" hdr.set_n(hdr.n() - 1);"},{"Add":" }"},{"Add":" }"},{"Add":" // Do the actual insertions."},{"Add":" L::alloc_write(&mut page, k0, v0, l, r, &mut n);"},{"Add":" // No page was freed, return the page."},{"Add":" Ok(Put::Ok(Ok { page, freed: 0 }))"},{"Add":" } else if replace || L::can_compact::(hdr) {"},{"Add":" // Here, we could allocate if we cloned, so let's clone:"},{"Add":" let mut new = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":" L::set_right_child(&mut new, -1, hdr.left_page() & !0xfff);"},{"Add":""},{"Add":" // Take the offsets and split it at the cursor position."},{"Add":" let s = L::offset_slice::(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(u as usize);"},{"Add":""},{"Add":" // If we're replacing, remove the offset that needs to go."},{"Add":" let s1 = if replace { s1.split_at(1).1 } else { s1 };"},{"Add":""},{"Add":" // And then clone the page, inserting the new elements between"},{"Add":" // the two halves of the split offsets."},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":" L::alloc_write(&mut new, k0, v0, l, r, &mut n);"},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":" Ok(Put::Ok(Ok {"},{"Add":" page: new,"},{"Add":" freed: if is_dirty {"},{"Add":" page.offset | 1"},{"Add":" } else {"},{"Add":" page.offset"},{"Add":" },"},{"Add":" }))"},{"Add":" } else {"},{"Add":" // Else, split the page."},{"Add":" split::<_, _, _, L>(txn, page, mutable, u, k0, v0, l, r).await"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"async fn split<"},{"Add":" 'a,"},{"Add":" T: AllocPage,"},{"Add":" K: Storable + core::fmt::Debug,"},{"Add":" V: Storable + core::fmt::Debug,"},{"Add":" L: Alloc + super::super::page_unsized::AllocWrite,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" u: usize,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":") -> Result, T::Error> {"},{"Add":" let mut left;"},{"Add":" let hdr = header(page.as_page());"},{"Add":""},{"Add":" let page_is_dirty = if page.is_dirty() { 1 } else { 0 };"},{"Add":""},{"Add":" let mut n = hdr.n();"},{"Add":" let k = n / 2;"},{"Add":" n += 1;"},{"Add":" let s = L::offset_slice::(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(k as usize);"},{"Add":""},{"Add":" // Find the split entry (i.e. the entry going up in the B"},{"Add":" // tree). Then, mid_child is the right child of the split"},{"Add":" // key/value, and `s1` is the offsets of the right side of the"},{"Add":" // split."},{"Add":" let (mut split_key, mut split_value, mid_child, s1) = if u == k as usize {"},{"Add":" // The inserted element is exactly in the middle."},{"Add":" (k0, v0, r, s1)"},{"Add":" } else {"},{"Add":" // Else, the split key is the first element of `s1`: set the"},{"Add":" // new, updated `s1`."},{"Add":" let (s1a, s1b) = s1.split_at(1);"},{"Add":" let (k, v, r) = L::kv(page.as_page(), L::first::(&s1a));"},{"Add":" (k, v, r, s1b)"},{"Add":" };"},{"Add":" let mut freed = 0;"},{"Add":" if u >= k as usize {"},{"Add":" // If we are here, u >= k, i.e. the insertion is in the"},{"Add":" // right-hand side of the split, or is the split entry itself."},{"Add":" let mut right = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut right);"},{"Add":" if u > k as usize {"},{"Add":" // if we're inserting in the right-hand side, clone to the"},{"Add":" // newly allocated `right` page, by"},{"Add":" let mut n = 0;"},{"Add":""},{"Add":" // Splitting the offsets to make space for an insertion,"},{"Add":" // and insert in the middle."},{"Add":" //"},{"Add":" // Off-by-one error? Nope: since `k` is the split entry,"},{"Add":" // the right page starts at index `k + 1`, hence if `u =="},{"Add":" // k + 1`, `kk` must be 0."},{"Add":" let kk = u as usize - k as usize - 1;"},{"Add":" let (s1a, s1b) = s1.split_at(kk);"},{"Add":" L::set_right_child(&mut right, -1, mid_child);"},{"Add":" clone::(page.as_page(), &mut right, s1a, &mut n);"},{"Add":" L::alloc_write(&mut right, k0, v0, l, r, &mut n);"},{"Add":" clone::(page.as_page(), &mut right, s1b, &mut n);"},{"Add":" } else {"},{"Add":" // Else, just clone the page, we'll take care of returning"},{"Add":" // the split entry afterwards."},{"Add":" clone::(page.as_page(), &mut right, s1, &mut 0);"},{"Add":" }"},{"Add":""},{"Add":" if mutable && page.is_dirty() {"},{"Add":" // (k0, v0) is to be inserted on the right-hand side of"},{"Add":" // the split, hence we don't have to clone the left-hand"},{"Add":" // side, we can just truncate it."},{"Add":" left = MutPage(page);"},{"Add":" let hdr = header_mut(&mut left);"},{"Add":" hdr.set_n(k);"},{"Add":" hdr.decr((n - 1 - k) as usize * core::mem::size_of::>());"},{"Add":" } else {"},{"Add":" // Else, we need to clone the first `k-1` entries,"},{"Add":" // i.e. `s0`, onto a new left page."},{"Add":" left = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut left);"},{"Add":" let mut n = 0;"},{"Add":" L::set_right_child(&mut left, -1, hdr.left_page() & !0xfff);"},{"Add":" clone::(page.as_page(), &mut left, s0, &mut n);"},{"Add":" freed = page.offset | page_is_dirty"},{"Add":" }"},{"Add":""},{"Add":" // Finally, if `u` is the middle element, its left and right"},{"Add":" // children become the leftmost child of the right page, and"},{"Add":" // the rightmost child of the left page, respectively."},{"Add":" if u == k as usize {"},{"Add":" // Insertion in the middle:"},{"Add":" // - `l` becomes the right child of the last element on `left`."},{"Add":" L::set_right_child(&mut left, k as isize - 1, l);"},{"Add":" // - `r` (i.e. `mid_child`) becomes the left child of `right`."},{"Add":" L::set_right_child(&mut right, -1, mid_child);"},{"Add":" }"},{"Add":" Ok(Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed,"},{"Add":" })"},{"Add":" } else {"},{"Add":" // Else, the insertion is in the new left page. We first clone"},{"Add":" // the left page, inserting (k,v) at its position:"},{"Add":" left = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut left);"},{"Add":" // Clone the leftmost page"},{"Add":" let ll = header(page.as_page()).left_page() & !0xfff;"},{"Add":" L::set_right_child(&mut left, -1, ll);"},{"Add":" // Clone the two sides, with an entry in between."},{"Add":" let (s0a, s0b) = s0.split_at(u as usize);"},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut left, s0a, &mut n);"},{"Add":" L::alloc_write(&mut left, k0, v0, l, r, &mut n);"},{"Add":" clone::(page.as_page(), &mut left, s0b, &mut n);"},{"Add":""},{"Add":" let mut right;"},{"Add":" let freed;"},{"Add":" // Then, for the right page:"},{"Add":" if mutable && page.is_dirty() {"},{"Add":" // If we can mutate the original page, remove the first"},{"Add":" // `k` entries, and return a pointer to the split key (at"},{"Add":" // position `k` on the page)"},{"Add":" right = MutPage(page);"},{"Add":" if let Some((k, v)) = L::truncate_left::(&mut right, k as usize + 1) {"},{"Add":" unsafe {"},{"Add":" split_key = &*k;"},{"Add":" split_value = &*v;"},{"Add":" }"},{"Add":" }"},{"Add":" freed = 0;"},{"Add":" } else {"},{"Add":" // Else, clone the right page."},{"Add":" right = txn.alloc_page().await?;"},{"Add":" as BTreeMutPage>::init(&mut right);"},{"Add":" // The left child of the right page is `mid_child`,"},{"Add":" // i.e. the right child of the split entry."},{"Add":" L::set_right_child(&mut right, -1, mid_child);"},{"Add":" // Clone the rest of the page."},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut right, s1, &mut n);"},{"Add":" freed = page.offset | page_is_dirty"},{"Add":" }"},{"Add":" Ok(Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed,"},{"Add":" })"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"alloc.rs","metadata":0},"context":[{"change":0,"pos":125961}],"contents":[{"Add":"use super::*;"},{"Add":""},{"Add":"/// This trait contains methods common to leaves and internal"},{"Add":"/// nodes. These methods are meant to be just a few lines long each,"},{"Add":"/// and avoid duplicating code in higher-level functions where just a"},{"Add":"/// few constants change between internal nodes and leaves."},{"Add":"pub(crate) trait Alloc {"},{"Add":" /// Is there enough room to add one entry into this page (without cloning)?"},{"Add":" fn can_alloc(hdr: &Header) -> bool;"},{"Add":""},{"Add":" /// If we clone the page, will there be enough room for one entry?"},{"Add":" fn can_compact(hdr: &Header) -> bool;"},{"Add":""},{"Add":" /// Remove the leftmost `n` elements from the page. On leaves,"},{"Add":" /// this moves the last truncated element to the end of the page"},{"Add":" /// and returns a pointer to that element (this function is only"},{"Add":" /// used in `crate::btree::put`, and the pointer becomes invalid"},{"Add":" /// at the end of the `crate::btree::put`)."},{"Add":" ///"},{"Add":" /// Returning the last deleted element isn't required for internal"},{"Add":" /// nodes, since the entries are still valid there."},{"Add":" fn truncate_left("},{"Add":" page: &mut MutPage,"},{"Add":" n: usize,"},{"Add":" ) -> Option<(*const K, *const V)>;"},{"Add":""},{"Add":" /// Allocate a new entry (size inferred), and return the offset on"},{"Add":" /// the page where the new entry can be copied."},{"Add":" fn alloc_insert(new: &mut MutPage, n: &mut isize, r: u64) -> usize;"},{"Add":""},{"Add":" /// Set the right child of the `n`th entry to `r`. If `n == -1`,"},{"Add":" /// this method can be used to set the leftmost child of a page."},{"Add":" fn set_right_child(new: &mut MutPage, n: isize, r: u64);"},{"Add":""},{"Add":" /// \"Slices\" of offsets, which aren't really slices in the case of"},{"Add":" /// leaves, but just intervals or \"ranges\"."},{"Add":" fn offset_slice<'a, T: LoadPage, K: Storable, V: Storable>("},{"Add":" page: crate::Page<'a>,"},{"Add":" ) -> Offsets<'a>;"},{"Add":""},{"Add":" /// First element of a slice offset. For the sake of code"},{"Add":" /// simplicity, we return a `u64` even for leaves. In internal"},{"Add":" /// nodes, the 52 MSBs encode a child page, and the 12 LSBs encode"},{"Add":" /// an offset in the page."},{"Add":" fn first<'a, K, V>(off: &Offsets<'a>) -> u64;"},{"Add":""},{"Add":" /// The tuple and right child at offset `off`."},{"Add":" fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64);"},{"Add":"}"},{"Add":""},{"Add":"/// The type of offsets."},{"Add":"#[derive(Debug, Clone)]"},{"Add":"pub enum Offsets<'a> {"},{"Add":" /// Slices of child pages and offset-in-page for internal nodes,"},{"Add":" Slice(&'a [u64]),"},{"Add":" /// Ranges for leaves."},{"Add":" Range(core::ops::Range),"},{"Add":"}"},{"Add":""},{"Add":"impl<'a> Offsets<'a> {"},{"Add":" /// Splitting an offset slice, with the same semantics as"},{"Add":" /// `split_at` for slices, except if `mid` is equal to the length,"},{"Add":" /// in which case we return `(self, &[])`."},{"Add":" pub fn split_at(&self, mid: usize) -> (Self, Self) {"},{"Add":" match self {"},{"Add":" Offsets::Slice(s) if mid < s.len() => {"},{"Add":" let (a, b) = s.split_at(mid);"},{"Add":" (Offsets::Slice(a), Offsets::Slice(b))"},{"Add":" }"},{"Add":" Offsets::Slice(s) => {"},{"Add":" debug_assert_eq!(mid, s.len());"},{"Add":" (Offsets::Slice(s), Offsets::Slice(&[][..]))"},{"Add":" }"},{"Add":" Offsets::Range(r) => ("},{"Add":" Offsets::Range(r.start..r.start + mid),"},{"Add":" Offsets::Range(r.start + mid..r.end),"},{"Add":" ),"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub struct Leaf {}"},{"Add":"pub struct Internal {}"},{"Add":""},{"Add":"impl Alloc for Leaf {"},{"Add":" // Checking if there's enough room is just bookkeeping."},{"Add":" fn can_alloc(hdr: &Header) -> bool {"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let header_size = (HDR + al - 1) & !(al - 1);"},{"Add":" header_size + (hdr.n() as usize + 1) * f <= PAGE_SIZE"},{"Add":" }"},{"Add":""},{"Add":" /// There's no possible compaction on leaves, it's the same as allocating."},{"Add":" fn can_compact(hdr: &Header) -> bool {"},{"Add":" Self::can_alloc::(hdr)"},{"Add":" }"},{"Add":""},{"Add":" fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}"},{"Add":""},{"Add":" fn offset_slice<'a, T: LoadPage, K: Storable, V: Storable>("},{"Add":" page: crate::Page<'a>,"},{"Add":" ) -> Offsets<'a> {"},{"Add":" let hdr = header(page);"},{"Add":" Offsets::Range(0..(hdr.n() as usize))"},{"Add":" }"},{"Add":""},{"Add":" /// This returns an offset on the page, so we need to compute that."},{"Add":" fn first<'a, K, V>(off: &Offsets<'a>) -> u64 {"},{"Add":" match off {"},{"Add":" Offsets::Slice(_) => unreachable!(),"},{"Add":" Offsets::Range(r) => {"},{"Add":" let size = core::mem::size_of::>();"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" (hdr_size + r.start * size) as u64"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64) {"},{"Add":" unsafe {"},{"Add":" let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple);"},{"Add":" (&tup.k, &tup.v, 0)"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Here, we just move `total - *n` elements to the right, and"},{"Add":" /// increase the bookkeeping values (occupied bytes and number of"},{"Add":" /// elements)."},{"Add":" fn alloc_insert(new: &mut MutPage, n: &mut isize, _: u64) -> usize {"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let hdr_n = header_mut(new).n();"},{"Add":" unsafe {"},{"Add":" core::ptr::copy("},{"Add":" new.0.data.add(hdr_size + (*n as usize) * f),"},{"Add":" new.0.data.add(hdr_size + (*n as usize) * f + f),"},{"Add":" (hdr_n as usize - (*n as usize)) * f,"},{"Add":" );"},{"Add":" }"},{"Add":" let hdr = header_mut(new);"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.incr(f);"},{"Add":" hdr_size + (*n as usize) * f"},{"Add":" }"},{"Add":""},{"Add":" fn truncate_left("},{"Add":" page: &mut MutPage,"},{"Add":" n: usize,"},{"Add":" ) -> Option<(*const K, *const V)> {"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let hdr = header_mut(page);"},{"Add":" let hdr_n = hdr.n();"},{"Add":" hdr.set_n(hdr_n - n as u16);"},{"Add":" hdr.decr(n * f);"},{"Add":""},{"Add":" // Now, this is a bit trickier. This performs a rotation by 1"},{"Add":" // without all the rotation machinery from the Rust core"},{"Add":" // library."},{"Add":" //"},{"Add":" // Indeed, since we're in a leaf, we are effectively erasing"},{"Add":" // the split entry. There is a choice to be made here, between"},{"Add":" // passing the entry by value or by reference. Because splits"},{"Add":" // might cascade with the same middle entry, passing it by"},{"Add":" // value may be significantly worse if the tree is deep, and"},{"Add":" // is never significantly better (we'll end up copying this"},{"Add":" // entry twice anyway)."},{"Add":" unsafe {"},{"Add":" let mut swap: core::mem::MaybeUninit> = core::mem::MaybeUninit::uninit();"},{"Add":" core::ptr::copy("},{"Add":" page.0.data.add(hdr_size + (n - 1) * f),"},{"Add":" swap.as_mut_ptr() as *mut u8,"},{"Add":" f,"},{"Add":" );"},{"Add":" core::ptr::copy("},{"Add":" page.0.data.add(hdr_size + n * f),"},{"Add":" page.0.data.add(hdr_size),"},{"Add":" (hdr_n as usize - n) * f,"},{"Add":" );"},{"Add":" core::ptr::copy("},{"Add":" swap.as_ptr() as *mut u8,"},{"Add":" page.0.data.add(hdr_size + (hdr_n as usize - n) * f),"},{"Add":" f,"},{"Add":" );"},{"Add":" let tup ="},{"Add":" &*(page.0.data.add(hdr_size + (hdr_n as usize - n) * f) as *const Tuple);"},{"Add":" Some((&tup.k, &tup.v))"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Alloc for Internal {"},{"Add":" fn can_alloc(hdr: &Header) -> bool {"},{"Add":" (HDR as usize) + (hdr.n() as usize + 1) * 8 + core::mem::size_of::>()"},{"Add":" < hdr.data() as usize"},{"Add":" }"},{"Add":""},{"Add":" fn can_compact(hdr: &Header) -> bool {"},{"Add":" (HDR as usize)"},{"Add":" + ((hdr.left_page() & 0xfff) as usize)"},{"Add":" + 8"},{"Add":" + core::mem::size_of::>()"},{"Add":" <= PAGE_SIZE"},{"Add":" }"},{"Add":""},{"Add":" /// Set the right-hand child in the offset array, preserving the"},{"Add":" /// current offset."},{"Add":" fn set_right_child(page: &mut MutPage, n: isize, r: u64) {"},{"Add":" unsafe {"},{"Add":" debug_assert_eq!(r & 0xfff, 0);"},{"Add":" let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;"},{"Add":" let off = u64::from_le(*ptr) & 0xfff;"},{"Add":" *ptr = (r | off as u64).to_le();"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn offset_slice<'a, T, K: Storable, V: Storable>(page: crate::Page<'a>) -> Offsets<'a> {"},{"Add":" let hdr = header(page);"},{"Add":" unsafe {"},{"Add":" Offsets::Slice(core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const u64,"},{"Add":" hdr.n() as usize,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn first<'a, K, V>(off: &Offsets<'a>) -> u64 {"},{"Add":" match off {"},{"Add":" Offsets::Slice(s) => s[0],"},{"Add":" Offsets::Range(_) => unreachable!(),"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64) {"},{"Add":" unsafe {"},{"Add":" let tup = &*(page.data.as_ptr().add((off & 0xfff) as usize) as *const Tuple);"},{"Add":" (&tup.k, &tup.v, off & !0xfff)"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Much simpler than in leaves, because we just need to move the"},{"Add":" // offsets. There's a little bit of bookkeeping involved though."},{"Add":" fn truncate_left("},{"Add":" page: &mut MutPage,"},{"Add":" n: usize,"},{"Add":" ) -> Option<(*const K, *const V)> {"},{"Add":" let hdr_n = header_mut(page).n();"},{"Add":" unsafe {"},{"Add":" // We want to copy the left child of the first entry that"},{"Add":" // will be kept alive as the left child of the page."},{"Add":" core::ptr::copy("},{"Add":" page.0.data.add(HDR + (n - 1) * 8),"},{"Add":" page.0.data.add(HDR - 8),"},{"Add":" // We're removing n entries, so we need to copy the"},{"Add":" // remaining `hdr_n - n`, plus the leftmost child"},{"Add":" // (hence the + 1)."},{"Add":" (hdr_n as usize - n + 1) * 8,"},{"Add":" );"},{"Add":" }"},{"Add":" // Remaining occupied size on the page (minus the header)."},{"Add":" let size = (8 + core::mem::size_of::>()) * (hdr_n as usize - n);"},{"Add":" let hdr = header_mut(page);"},{"Add":" hdr.set_n(hdr_n - n as u16);"},{"Add":" // Because the leftmost child has been copied from an entry"},{"Add":" // containing an offset, its 12 LBSs are still enconding an"},{"Add":" // offset on the page, whereas it should encode the occupied"},{"Add":" // bytes on the page. Reset it."},{"Add":" hdr.set_occupied(size as u64);"},{"Add":" None"},{"Add":" }"},{"Add":""},{"Add":" fn alloc_insert(new: &mut MutPage, n: &mut isize, r: u64) -> usize {"},{"Add":" let hdr = header_mut(new);"},{"Add":""},{"Add":" // Move the `data` field one entry to the left."},{"Add":" let data = hdr.data() as u16;"},{"Add":" let off_new = data - core::mem::size_of::>() as u16;"},{"Add":" hdr.set_data(off_new);"},{"Add":""},{"Add":" // Increment the number of entries, add the newly occupied size."},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.incr(8 + core::mem::size_of::>());"},{"Add":""},{"Add":" let hdr_n = hdr.n();"},{"Add":" unsafe {"},{"Add":" // Make space in the offset array by moving the last"},{"Add":" // `hdr_n - *n` elements."},{"Add":" core::ptr::copy("},{"Add":" new.0.data.add(HDR + (*n as usize) * 8),"},{"Add":" new.0.data.add(HDR + (*n as usize) * 8 + 8),"},{"Add":" (hdr_n as usize - (*n as usize)) * 8,"},{"Add":" );"},{"Add":" // Add the offset."},{"Add":" let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;"},{"Add":" *ptr = (r | off_new as u64).to_le();"},{"Add":" }"},{"Add":" off_new as usize"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl crate::btree::page_unsized::AllocWrite for Internal {"},{"Add":" fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {"},{"Add":" alloc_write::(new, k0, v0, l, r, n)"},{"Add":" }"},{"Add":" fn set_left_child(new: &mut MutPage, n: isize, l: u64) {"},{"Add":" if l > 0 {"},{"Add":" Internal::set_right_child(new, n - 1, l);"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl crate::btree::page_unsized::AllocWrite for Leaf {"},{"Add":" fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {"},{"Add":" alloc_write::(new, k0, v0, l, r, n)"},{"Add":" }"},{"Add":" fn set_left_child(_new: &mut MutPage, _n: isize, l: u64) {"},{"Add":" debug_assert_eq!(l, 0);"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Simply allocate an entry in the page, copy it, and set its right"},{"Add":"/// and left children."},{"Add":"fn alloc_write("},{"Add":" new: &mut MutPage,"},{"Add":" k0: &K,"},{"Add":" v0: &V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" let off_new = L::alloc_insert::(new, n, r);"},{"Add":" unsafe {"},{"Add":" let new_ptr = &mut *(new.0.data.add(off_new as usize) as *mut Tuple);"},{"Add":" core::ptr::copy_nonoverlapping(k0, &mut new_ptr.k, 1);"},{"Add":" core::ptr::copy_nonoverlapping(v0, &mut new_ptr.v, 1);"},{"Add":" }"},{"Add":" if l > 0 {"},{"Add":" L::set_right_child(new, *n - 1, l);"},{"Add":" }"},{"Add":" *n += 1;"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"mod.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"//! An implementation of B trees. The core operations on B trees"},{"Add":"//! (lookup, iterate, put and del) are generic in the actual"},{"Add":"//! implementation of nodes, via the [`BTreePage`] and"},{"Add":"//! [`BTreeMutPage`]. This allows for a simpler code for the"},{"Add":"//! high-level functions, as well as specialised, high-performance"},{"Add":"//! implementations for the nodes."},{"Add":"//!"},{"Add":"//! Two different implementations are supplied: one in [`page`] for"},{"Add":"//! types with a size known at compile-time, which yields denser"},{"Add":"//! leaves, and hence shallower trees (if the values are really using"},{"Add":"//! the space). The other one, in [`page_unsized`], is for"},{"Add":"//! dynamic-sized types, or types whose representation is dynamic, for"},{"Add":"//! example enums that are `Sized` in Rust, but whose cases vary"},{"Add":"//! widely in size."},{"Add":"use crate::*;"},{"Add":"#[doc(hidden)]"},{"Add":"pub mod cursor;"},{"Add":"pub use cursor::{iter, rev_iter, Cursor, Iter, RevIter};"},{"Add":"pub mod del;"},{"Add":"pub use del::{del, del_no_decr};"},{"Add":"pub mod put;"},{"Add":"pub use put::put;"},{"Add":"pub mod page;"},{"Add":"pub mod page_unsized;"},{"Add":""},{"Add":"#[async_trait(?Send)]"},{"Add":"pub trait BTreePage: Sized {"},{"Add":" type Cursor: Send + Sync + Clone + Copy + core::fmt::Debug;"},{"Add":""},{"Add":" /// Whether this cursor is at the end of the page."},{"Add":" fn is_empty(c: &Self::Cursor) -> bool;"},{"Add":""},{"Add":" /// Whether this cursor is strictly before the first element."},{"Add":" fn is_init(c: &Self::Cursor) -> bool;"},{"Add":""},{"Add":" /// Returns a cursor set before the first element of the page"},{"Add":" /// (i.e. set to -1)."},{"Add":" fn cursor_before(p: &CowPage) -> Self::Cursor;"},{"Add":""},{"Add":" /// Returns a cursor set to the first element of the page"},{"Add":" /// (i.e. 0). If the page is empty, the returned cursor might be"},{"Add":" /// empty."},{"Add":" fn cursor_first(p: &CowPage) -> Self::Cursor {"},{"Add":" let mut c = Self::cursor_before(p);"},{"Add":" Self::move_next(&mut c);"},{"Add":" c"},{"Add":" }"},{"Add":""},{"Add":" /// Returns a cursor set after the last element of the page"},{"Add":" /// (i.e. to element n)"},{"Add":" fn cursor_after(p: &CowPage) -> Self::Cursor;"},{"Add":""},{"Add":" /// Returns a cursor set to the last element of the page. If the"},{"Add":" /// cursor is empty, this is the same as `cursor_before`."},{"Add":" fn cursor_last(p: &CowPage) -> Self::Cursor {"},{"Add":" let mut c = Self::cursor_after(p);"},{"Add":" Self::move_prev(&mut c);"},{"Add":" c"},{"Add":" }"},{"Add":""},{"Add":" /// Return the element currently pointed to by the cursor (if the"},{"Add":" /// cursor is not before or after the elements of the page), and"},{"Add":" /// move the cursor to the next element."},{"Add":" fn next<'b>("},{"Add":" p: Page<'b>,"},{"Add":" c: &mut Self::Cursor,"},{"Add":" ) -> Option<(&'b K, &'b V, u64)> {"},{"Add":" if let Some((k, v, r)) = Self::current(p, c) {"},{"Add":" Self::move_next(c);"},{"Add":" Some((k, v, r))"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Move the cursor to the previous element, and return that"},{"Add":" /// element. Note that this is not the symmetric of `next`."},{"Add":" fn prev<'b>("},{"Add":" p: Page<'b>,"},{"Add":" c: &mut Self::Cursor,"},{"Add":" ) -> Option<(&'b K, &'b V, u64)> {"},{"Add":" if Self::move_prev(c) {"},{"Add":" Self::current(p, c)"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Move the cursor to the next position. Returns whether the"},{"Add":" /// cursor was actually moved (i.e. `true` if and only if the"},{"Add":" /// cursor isn't already after the last element)."},{"Add":" fn move_next(c: &mut Self::Cursor) -> bool;"},{"Add":""},{"Add":" /// Move the cursor to the previous position. Returns whether the"},{"Add":" /// cursor was actually moved (i.e. `true` if and only if the"},{"Add":" /// cursor isn't strictly before the page)."},{"Add":" fn move_prev(c: &mut Self::Cursor) -> bool;"},{"Add":""},{"Add":" /// Returns the current element, if the cursor is pointing at one."},{"Add":" fn current<'a>("},{"Add":" p: Page<'a>,"},{"Add":" c: &Self::Cursor,"},{"Add":" ) -> Option<(&'a K, &'a V, u64)>;"},{"Add":""},{"Add":" /// Returns the left child of the entry pointed to by the cursor."},{"Add":" fn left_child(p: Page, c: &Self::Cursor) -> u64;"},{"Add":""},{"Add":" /// Returns the right child of the entry pointed to by the cursor."},{"Add":" fn right_child(p: Page, c: &Self::Cursor) -> u64;"},{"Add":""},{"Add":" /// Sets the cursor to the last element less than or equal to `k0`"},{"Add":" /// if `v0.is_none()`, and to `(k0, v0)` if `v0.is_some()`. If a"},{"Add":" /// match is found (on `k0` only if `v0.is_none()`, on `(k0, v0)`"},{"Add":" /// else), return the match along with the right child."},{"Add":" ///"},{"Add":" /// Else (in the `Err` case of the `Result`), return the position"},{"Add":" /// at which `(k0, v0)` can be inserted."},{"Add":" async fn set_cursor<'a, 'b, T: LoadPage>("},{"Add":" txn: &'a T,"},{"Add":" page: Page<'b>,"},{"Add":" c: &mut Self::Cursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" ) -> Result<(&'a K, &'a V, u64), usize>;"},{"Add":""},{"Add":" /// Splits the cursor into two cursors: the elements strictly"},{"Add":" /// before the current position, and the elements greater than or"},{"Add":" /// equal the current element."},{"Add":" fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor);"},{"Add":"}"},{"Add":""},{"Add":"pub struct PageIterator<'a, T: LoadPage, K: ?Sized, V: ?Sized, P: BTreePage> {"},{"Add":" cursor: P::Cursor,"},{"Add":" _txn: &'a T,"},{"Add":" page: Page<'a>,"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, T: LoadPage, K: ?Sized + 'a, V: ?Sized + 'a, P: BTreePage> Iterator"},{"Add":" for PageIterator<'a, T, K, V, P>"},{"Add":"{"},{"Add":" type Item = (&'a K, &'a V, u64);"},{"Add":" fn next(&mut self) -> Option {"},{"Add":" P::next(self.page, &mut self.cursor)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[async_trait(?Send)]"},{"Add":"pub trait BTreeMutPage: BTreePage + core::fmt::Debug {"},{"Add":" /// Initialise a page."},{"Add":" fn init(page: &mut MutPage);"},{"Add":""},{"Add":" /// Add an entry to the page, possibly splitting the page in the"},{"Add":" /// process."},{"Add":" ///"},{"Add":" /// Makes the assumption that `k1v1.is_some()` implies"},{"Add":" /// `replace`. When `k1v1.is_some()`, we insert both `(k0, v0)`"},{"Add":" /// (as a replacement), followed by `(k1, v1)`. This is only ever"},{"Add":" /// used when deleting, and when the right child of a deleted"},{"Add":" /// entry (in an internal node) has split while we were looking"},{"Add":" /// for a replacement for the deleted entry."},{"Add":" ///"},{"Add":" /// Since we only look for replacements in the right child, the"},{"Add":" /// left child of the insertion isn't modified, in which case `l`"},{"Add":" /// and `r` are interpreted as the left and right child of the new"},{"Add":" /// entry, `k1v1`."},{"Add":" async fn put<'a, T: AllocPage>("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" replace: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" k1v1: Option<(&'a K, &'a V)>,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" ) -> Result, T::Error>;"},{"Add":""},{"Add":" /// Add an entry to `page`, at position `c`. Does not check"},{"Add":" /// whether there is enough space to do so. This method is mostly"},{"Add":" /// useful for cloning pages."},{"Add":" #[allow(unused_variables)]"},{"Add":" unsafe fn put_mut("},{"Add":" page: &mut MutPage,"},{"Add":" c: &mut Self::Cursor,"},{"Add":" k0: &K,"},{"Add":" v0: &V,"},{"Add":" r: u64,"},{"Add":" );"},{"Add":""},{"Add":" #[allow(unused_variables)]"},{"Add":" unsafe fn set_left_child("},{"Add":" page: &mut MutPage,"},{"Add":" c: &Self::Cursor,"},{"Add":" l: u64"},{"Add":" );"},{"Add":""},{"Add":""},{"Add":" /// Update the left child of the position pointed to by the"},{"Add":" /// cursor."},{"Add":" async fn update_left_child("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" r: u64,"},{"Add":" ) -> Result;"},{"Add":""},{"Add":" type Saved;"},{"Add":""},{"Add":" /// Save a leaf entry as a replacement, when we delete at an"},{"Add":" /// internal node. This can be a pointer to the leaf if the leaf"},{"Add":" /// isn't mutated, or the actual value, or something else."},{"Add":" fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved;"},{"Add":""},{"Add":" /// Recover the saved value."},{"Add":" unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V);"},{"Add":""},{"Add":" /// Delete an entry on the page, returning the resuting page along"},{"Add":" /// with the offset of the freed page (or 0 if no page was freed,"},{"Add":" /// i.e. if `page` is mutable)."},{"Add":" async fn del("},{"Add":" txn: &mut T,"},{"Add":" page: CowPage,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" l: u64,"},{"Add":" ) -> Result<(MutPage, u64), T::Error>;"},{"Add":""},{"Add":" /// Merge, rebalance or update a concatenation."},{"Add":" async fn merge_or_rebalance<'a, T: AllocPage>("},{"Add":" txn: &mut T,"},{"Add":" m: del::Concat<'a, K, V, Self>,"},{"Add":" ) -> Result, T::Error>;"},{"Add":"}"},{"Add":""},{"Add":"/// A database, which is essentially just a page offset along with markers."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Db_> {"},{"Add":" pub db: u64,"},{"Add":" pub k: core::marker::PhantomData,"},{"Add":" pub v: core::marker::PhantomData,"},{"Add":" pub p: core::marker::PhantomData

,"},{"Add":"}"},{"Add":""},{"Add":"unsafe impl> Sync for Db_{}"},{"Add":""},{"Add":"/// A database of sized values."},{"Add":"pub type Db = Db_>;"},{"Add":""},{"Add":"#[async_trait(?Send)]"},{"Add":"impl + Send + core::fmt::Debug> Storable for Db_ {"},{"Add":" type PageReferences = core::iter::Once;"},{"Add":" fn page_references(&self) -> Self::PageReferences {"},{"Add":" core::iter::once(self.db)"},{"Add":" }"},{"Add":""},{"Add":" async fn drop(&self, t: &mut T) -> Result<(), T::Error> {"},{"Add":" drop_(t, self).await"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// A database of unsized values."},{"Add":"pub type UDb = Db_>;"},{"Add":""},{"Add":"impl> Db_ {"},{"Add":" /// Load a database from a page offset."},{"Add":" pub fn from_page(db: u64) -> Self {"},{"Add":" Db_ {"},{"Add":" db,"},{"Add":" k: core::marker::PhantomData,"},{"Add":" v: core::marker::PhantomData,"},{"Add":" p: core::marker::PhantomData,"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Create a database with an arbitrary page implementation."},{"Add":"pub async fn create_db_>("},{"Add":" txn: &mut T,"},{"Add":") -> Result, T::Error> {"},{"Add":" let mut page = txn.alloc_page().await?;"},{"Add":" P::init(&mut page);"},{"Add":" Ok(Db_ {"},{"Add":" db: page.0.offset,"},{"Add":" k: core::marker::PhantomData,"},{"Add":" v: core::marker::PhantomData,"},{"Add":" p: core::marker::PhantomData,"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"/// Create a database for sized keys and values."},{"Add":"pub async fn create_db("},{"Add":" txn: &mut T,"},{"Add":") -> Result>, T::Error> {"},{"Add":" create_db_(txn).await"},{"Add":"}"},{"Add":""},{"Add":"/// Fork a database."},{"Add":"pub async fn fork_db>("},{"Add":" txn: &mut T,"},{"Add":" db: &Db_,"},{"Add":") -> Result, T::Error> {"},{"Add":" txn.incr_rc(db.db).await?;"},{"Add":" Ok(Db_ {"},{"Add":" db: db.db,"},{"Add":" k: core::marker::PhantomData,"},{"Add":" v: core::marker::PhantomData,"},{"Add":" p: core::marker::PhantomData,"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"/// Get the first entry of a database greater than or equal to `k` (or"},{"Add":"/// to `(k, v)` if `v.is_some()`), and return `true` if this entry is"},{"Add":"/// shared with another structure (i.e. the RC of at least one page"},{"Add":"/// along a path to the entry is at least 2)."},{"Add":"pub async fn get_shared<'a, T: LoadPage, K: 'a + Storable + ?Sized, V: 'a + Storable + ?Sized, P: BTreePage>("},{"Add":" txn: &'a T,"},{"Add":" db: &Db_,"},{"Add":" k: &K,"},{"Add":" v: Option<&V>,"},{"Add":") -> Result, T::Error> {"},{"Add":""},{"Add":" // Set the \"cursor stack\" by setting a skip list cursor in"},{"Add":" // each page from the root to the appropriate leaf."},{"Add":" let mut last_match = None;"},{"Add":" let mut page = txn.load_page(db.db).await?;"},{"Add":" let mut is_shared = txn.rc(db.db).await? >= 2;"},{"Add":" // This is a for loop, to allow the compiler to unroll (maybe)."},{"Add":" for _ in 0..cursor::N_CURSORS {"},{"Add":" let mut cursor = P::cursor_before(&page);"},{"Add":" if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), &mut cursor, k, v).await {"},{"Add":" if v.is_some() {"},{"Add":" return Ok(Some((kk, vv, is_shared)));"},{"Add":" }"},{"Add":" last_match = Some((kk, vv, is_shared));"},{"Add":" } else if let Some((k, v, _)) = P::current(page.as_page(), &cursor) {"},{"Add":" // Here, Rust says that `k` and `v` have the same lifetime"},{"Add":" // as `page`, but we actually know that they're alive for"},{"Add":" // as long as `txn` doesn't change, so we can safely"},{"Add":" // extend their lifetimes:"},{"Add":" unsafe { last_match = Some((core::mem::transmute(k), core::mem::transmute(v), is_shared)) }"},{"Add":" }"},{"Add":" // The cursor is set to the first element greater than or"},{"Add":" // equal to the (k, v) we're looking for, so we need to"},{"Add":" // explore the left subtree."},{"Add":" let next_page = P::left_child(page.as_page(), &cursor);"},{"Add":" if next_page > 0 {"},{"Add":" page = txn.load_page(next_page).await?;"},{"Add":" is_shared |= txn.rc(db.db).await? >= 2;"},{"Add":" } else {"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(last_match)"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"/// Get the first entry of a database greater than or equal to `k` (or"},{"Add":"/// to `(k, v)` if `v.is_some()`), and return `true` if this entry is"},{"Add":"/// shared with another structure (i.e. the RC of at least one page"},{"Add":"/// along a path to the entry is at least 2)."},{"Add":"pub async fn get<'a, T: LoadPage, K: 'a + Storable + ?Sized, V: 'a + Storable + ?Sized, P: BTreePage>("},{"Add":" txn: &'a T,"},{"Add":" db: &Db_,"},{"Add":" k: &K,"},{"Add":" v: Option<&V>,"},{"Add":") -> Result, T::Error> {"},{"Add":""},{"Add":" // Unfortunately, since the above function `get_shared` uses this"},{"Add":" // one in order to get the RC of pages, we can't really refactor,"},{"Add":" // so this is mostly a copy of the other function."},{"Add":""},{"Add":" // Set the \"cursor stack\" by setting a skip list cursor in"},{"Add":" // each page from the root to the appropriate leaf."},{"Add":" let mut last_match = None;"},{"Add":" let mut page = txn.load_page(db.db).await?;"},{"Add":" // This is a for loop, to allow the compiler to unroll (maybe)."},{"Add":" for _ in 0..cursor::N_CURSORS {"},{"Add":" let mut cursor = P::cursor_before(&page);"},{"Add":" if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), &mut cursor, k, v).await {"},{"Add":" if v.is_some() {"},{"Add":" return Ok(Some((kk, vv)));"},{"Add":" }"},{"Add":" last_match = Some((kk, vv));"},{"Add":" } else if let Some((k, v, _)) = P::current(page.as_page(), &cursor) {"},{"Add":" // Here, Rust says that `k` and `v` have the same lifetime"},{"Add":" // as `page`, but we actually know that they're alive for"},{"Add":" // as long as `txn` doesn't change, so we can safely"},{"Add":" // extend their lifetimes:"},{"Add":" unsafe { last_match = Some((core::mem::transmute(k), core::mem::transmute(v))) }"},{"Add":" }"},{"Add":" // The cursor is set to the first element greater than or"},{"Add":" // equal to the (k, v) we're looking for, so we need to"},{"Add":" // explore the left subtree."},{"Add":" let next_page = P::left_child(page.as_page(), &cursor);"},{"Add":" if next_page > 0 {"},{"Add":" page = txn.load_page(next_page).await?;"},{"Add":" } else {"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(last_match)"},{"Add":"}"},{"Add":""},{"Add":"/// Drop a database recursively, dropping all referenced keys and"},{"Add":"/// values that aren't shared with other databases."},{"Add":"pub async fn drop>("},{"Add":" txn: &mut T,"},{"Add":" db: Db_,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" drop_(txn, &db).await"},{"Add":"}"},{"Add":""},{"Add":"use core::mem::MaybeUninit;"},{"Add":"struct PageCursor_>(MaybeUninit>);"},{"Add":""},{"Add":"unsafe impl> Send for PageCursor_ {}"},{"Add":""},{"Add":""},{"Add":"async fn drop_>("},{"Add":" txn: &mut T,"},{"Add":" db: &Db_,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" let mut stack: [PageCursor_; cursor::N_CURSORS] = ["},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" PageCursor_(MaybeUninit::uninit()),"},{"Add":" ];"},{"Add":" let mut ptr = 0;"},{"Add":""},{"Add":" // Push the root page of `db` onto the stack."},{"Add":" let page = txn.load_page(db.db).await?;"},{"Add":" stack[0] = PageCursor_(MaybeUninit::new(cursor::PageCursor {"},{"Add":" cursor: P::cursor_before(&page),"},{"Add":" page,"},{"Add":" }));"},{"Add":""},{"Add":" // Then perform a DFS:"},{"Add":" loop {"},{"Add":" // Look at the top element of the stack."},{"Add":" let cur_off = unsafe { (&*stack[ptr].0.as_ptr()).page.offset };"},{"Add":" // If it needs to be dropped (i.e. if its RC is <= 1), iterate"},{"Add":" // its cursor and drop all its referenced pages."},{"Add":" let rc = txn.rc(cur_off).await?;"},{"Add":" if rc <= 1 {"},{"Add":" // if there's a current element in the cursor (i.e. we"},{"Add":" // aren't before or after the elements), decrease its RC."},{"Add":" if let Some((k, v, _)) = {"},{"Add":" let cur = unsafe { &mut *stack[ptr].0.as_mut_ptr() };"},{"Add":" P::current(cur.page.as_page(), &cur.cursor)"},{"Add":" } {"},{"Add":" k.drop(txn).await?;"},{"Add":" v.drop(txn).await?;"},{"Add":" }"},{"Add":" // In all cases, move next and push the left child onto"},{"Add":" // the stack. This works because pushed cursors are"},{"Add":" // initially set to before the page's elements."},{"Add":" let r = {"},{"Add":" let cur = unsafe { &mut *stack[ptr].0.as_mut_ptr() };"},{"Add":" if P::move_next(&mut cur.cursor) {"},{"Add":" Some(P::left_child(cur.page.as_page(), &cur.cursor))"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":" };"},{"Add":" if let Some(r) = r {"},{"Add":" if r > 0 {"},{"Add":" ptr += 1;"},{"Add":" let page = txn.load_page(r).await?;"},{"Add":" stack[ptr] = PageCursor_(MaybeUninit::new(cursor::PageCursor {"},{"Add":" cursor: P::cursor_before(&page),"},{"Add":" page,"},{"Add":" }))"},{"Add":" }"},{"Add":" continue;"},{"Add":" }"},{"Add":" }"},{"Add":" // Here, either rc > 1 (in which case the only thing we need"},{"Add":" // to do in this iteration is to decrement the RC), or else"},{"Add":" // `P::move_next` returned `false`, meaning that the cursor is"},{"Add":" // after the last element (in which case we are done with this"},{"Add":" // page, and also need to decrement its RC, in order to free"},{"Add":" // it)."},{"Add":" let (is_dirty, offset) = {"},{"Add":" let cur = unsafe { &mut *stack[ptr].0.as_mut_ptr() };"},{"Add":" (cur.page.is_dirty(), cur.page.offset)"},{"Add":" };"},{"Add":" if is_dirty {"},{"Add":" txn.decr_rc_owned(offset).await?;"},{"Add":" } else {"},{"Add":" txn.decr_rc(offset).await?;"},{"Add":" }"},{"Add":" // If this was the bottom element of the stack, stop, else, pop."},{"Add":" if ptr == 0 {"},{"Add":" break;"},{"Add":" } else {"},{"Add":" ptr -= 1;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"del.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"//! Deletions from a B tree."},{"Add":"use super::cursor::*;"},{"Add":"use super::put::{Ok, Put};"},{"Add":"use super::*;"},{"Add":"use crate::LoadPage;"},{"Add":""},{"Add":"/// Represents the result of a merge or rebalance, without touching"},{"Add":"/// the parent of the merge/rebalance."},{"Add":"#[derive(Debug)]"},{"Add":"pub enum Op<'a, T, K: ?Sized, V: ?Sized> {"},{"Add":" Merged {"},{"Add":" // New merged page."},{"Add":" page: MutPage,"},{"Add":" // Pages freed by the merge (0 meaning \"no page\")."},{"Add":" freed: [u64; 2],"},{"Add":" marker: core::marker::PhantomData,"},{"Add":" },"},{"Add":" Rebalanced {"},{"Add":" // New middle key."},{"Add":" k: &'a K,"},{"Add":" // New middle value."},{"Add":" v: &'a V,"},{"Add":" // New left page."},{"Add":" l: u64,"},{"Add":" // New right page."},{"Add":" r: u64,"},{"Add":" // Pages freed by the rebalance (0 meaning \"no page\")."},{"Add":" freed: [u64; 2],"},{"Add":" },"},{"Add":" Put(crate::btree::put::Put<'a, K, V>),"},{"Add":"}"},{"Add":""},{"Add":"/// Represents a page with modifications from a merge."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct ModifiedPage<'a, K: ?Sized, V: ?Sized, P: BTreePage> {"},{"Add":" pub page: CowPage,"},{"Add":" // Whether the page is mutable with another tree."},{"Add":" pub mutable: bool,"},{"Add":" // Start copying c0 (keep `page`'s left child)."},{"Add":" pub c0: P::Cursor,"},{"Add":" // If > 0, replace the right child of c0's last element with `l`."},{"Add":" pub l: u64,"},{"Add":" // If > 0, replace the left child of c1's last element with `r`."},{"Add":" pub r: u64,"},{"Add":" // Possibly insert a new binding."},{"Add":" pub ins: Option<(&'a K, &'a V)>,"},{"Add":" // If a rebalance causes a split, we might need to insert an entry"},{"Add":" // after the replacement."},{"Add":" pub ins2: Option<(&'a K, &'a V)>,"},{"Add":" // The first element of c1 is to be deleted, the others must be copied."},{"Add":" pub c1: P::Cursor,"},{"Add":" // Whether to skip `c1`'s first element."},{"Add":" pub skip_first: bool,"},{"Add":" // Whether the page we just modified is `self.l`."},{"Add":" pub mod_is_left: bool,"},{"Add":"}"},{"Add":""},{"Add":"/// Represents the concatenation of a modified page and one of its"},{"Add":"/// sibling (left or right)."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Concat<'a, K: ?Sized, V: ?Sized, P: BTreePage> {"},{"Add":" /// Modified page."},{"Add":" pub modified: ModifiedPage<'a, K, V, P>,"},{"Add":" /// Middle element."},{"Add":" pub mid: (&'a K, &'a V),"},{"Add":" /// Sibling of the modified page."},{"Add":" pub other: CowPage,"},{"Add":" /// Is the modified field on the left or on the right of the"},{"Add":" /// concatenation?"},{"Add":" pub mod_is_left: bool,"},{"Add":" /// Is the other page owned by this tree? If not, it means `other`"},{"Add":" /// is shared with another tree, and hence we need to increase the"},{"Add":" /// reference count of entries coming from `other`."},{"Add":" pub other_is_mutable: bool,"},{"Add":"}"},{"Add":""},{"Add":"/// If `value` is `None`, delete the first entry for `key` from the"},{"Add":"/// database, if present. Else, delete the entry for `(key, value)`,"},{"Add":"/// if present."},{"Add":"pub async fn del<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized + PartialEq + Sync,"},{"Add":" V: Storable + ?Sized + PartialEq + Sync,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db_,"},{"Add":" key: &K,"},{"Add":" value: Option<&V>,"},{"Add":") -> Result {"},{"Add":" let mut cursor = Cursor::new(txn, db).await?;"},{"Add":" // If the key and value weren't found, return."},{"Add":" match (cursor.set(txn, key, value).await?, value) {"},{"Add":" (Some((k, v)), Some(value)) if k == key && v == value => {}"},{"Add":" (Some((k, _)), None) if k == key => {}"},{"Add":" _ => return Ok(false),"},{"Add":" }"},{"Add":" // Else, the cursor is set on `(key, value)` if `value.is_some()`"},{"Add":" // or on the first entry with key `key` else."},{"Add":" //"},{"Add":" // We delete that position, which might be in a leaf or in an"},{"Add":" // internal node."},{"Add":" del_at_cursor(txn, db, &mut cursor, true).await"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"/// If `value` is `None`, delete the first entry for `key` from the"},{"Add":"/// database, if present. Else, delete the entry for `(key, value)`,"},{"Add":"/// if present."},{"Add":"pub async fn del_no_decr<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized + PartialEq + Sync,"},{"Add":" V: Storable + ?Sized + PartialEq + Sync,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db_,"},{"Add":" key: &K,"},{"Add":" value: Option<&V>,"},{"Add":") -> Result {"},{"Add":" let mut cursor = Cursor::new(txn, db).await?;"},{"Add":" // If the key and value weren't found, return."},{"Add":" match (cursor.set(txn, key, value).await?, value) {"},{"Add":" (Some((k, v)), Some(value)) if k == key && v == value => {}"},{"Add":" (Some((k, _)), None) if k == key => {}"},{"Add":" _ => return Ok(false),"},{"Add":" }"},{"Add":" // Else, the cursor is set on `(key, value)` if `value.is_some()`"},{"Add":" // or on the first entry with key `key` else."},{"Add":" //"},{"Add":" // We delete that position, which might be in a leaf or in an"},{"Add":" // internal node."},{"Add":" del_at_cursor(txn, db, &mut cursor, false).await"},{"Add":"}"},{"Add":""},{"Add":"/// Delete the entry pointed to by `cursor`. The cursor can't be used"},{"Add":"/// after this."},{"Add":"#[doc(hidden)]"},{"Add":"pub async fn del_at_cursor<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized + PartialEq + Sync,"},{"Add":" V: Storable + ?Sized + Sync,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db_,"},{"Add":" cursor: &mut Cursor,"},{"Add":" decr_del_rc: bool,"},{"Add":") -> Result {"},{"Add":" let p0 = cursor.len();"},{"Add":""},{"Add":" // If p0 < cursor.first_rc_level, the page containing the deleted"},{"Add":" // element is not shared with another table. Therefore, the RC of"},{"Add":" // the pages referenced by the deleted element needs to be"},{"Add":" // decreased."},{"Add":" //"},{"Add":" // Else, that RC doesn't need to be changed, since it's still"},{"Add":" // referenced by the same pages as before, just not by the pages"},{"Add":" // that are cloned by this deletion."},{"Add":" //"},{"Add":" // Note in particular that if p0 == cursor.first_rc_len(), then we"},{"Add":" // don't need to touch the RC, since we're cloning this page, but"},{"Add":" // without including a reference to the deleted entry."},{"Add":" if decr_del_rc && p0 < cursor.first_rc_len() {"},{"Add":" let (delk, delv, _) = {"},{"Add":" let cur = cursor.cur();"},{"Add":" P::current(cur.page.as_page(), &cur.cursor).unwrap()"},{"Add":" };"},{"Add":" delk.drop(txn).await?;"},{"Add":" delv.drop(txn).await?;"},{"Add":" }"},{"Add":""},{"Add":" // Find the leftmost page in the right subtree of the deleted"},{"Add":" // element, in order to find a replacement."},{"Add":" let cur = cursor.cur();"},{"Add":" let right_subtree = P::right_child(cur.page.as_page(), &cur.cursor);"},{"Add":" cursor.set_first_leaf(txn, right_subtree).await?;"},{"Add":" let leaf_is_shared = cursor.len() >= cursor.first_rc_len();"},{"Add":""},{"Add":" // In the leaf, mark the replacement for deletion, and keep a"},{"Add":" // reference to it in k0v0 if the deletion happens in an internal"},{"Add":" // node (k0v0 is `Option::None` else)."},{"Add":" let (mut last_op, k0v0) = leaf_delete(txn, cursor, p0).await?;"},{"Add":""},{"Add":" // If the leaf is shared with another tree, then since we're"},{"Add":" // cloning the leaf, update the reference counts of all the"},{"Add":" // references contained in the leaf."},{"Add":" if leaf_is_shared {"},{"Add":" modify_rc(txn, &last_op).await?;"},{"Add":" }"},{"Add":""},{"Add":" let mut free = [[0, 0]; N_CURSORS];"},{"Add":""},{"Add":" // Then, climb up the stack, performing the operations lazily. At"},{"Add":" // each step, we are one level above the page that we plan to"},{"Add":" // modify, since `last_op` is the result of popping the"},{"Add":" // stack."},{"Add":" //"},{"Add":" // We iterate up to the root. The last iteration builds a modified"},{"Add":" // page for the root, but doesn't actually execute it."},{"Add":" while cursor.len() > 0 {"},{"Add":" // Prepare a plan for merging the current modified page (which"},{"Add":" // is stored in `last_op`) with one of its neighbours."},{"Add":" let concat = concat(txn, cursor, p0, &k0v0, last_op).await?;"},{"Add":" let mil = concat.mod_is_left;"},{"Add":""},{"Add":" let incr_page = if !concat.other_is_mutable {"},{"Add":" Some(CowPage {"},{"Add":" offset: concat.other.offset,"},{"Add":" data: concat.other.data,"},{"Add":" })"},{"Add":" } else {"},{"Add":" None"},{"Add":" };"},{"Add":" let incr_mid = if cursor.len() >= cursor.first_rc_len() {"},{"Add":" Some(concat.mid)"},{"Add":" } else {"},{"Add":" None"},{"Add":" };"},{"Add":""},{"Add":" // Execute the modification plan, resulting in one of four"},{"Add":" // different outcomes (described in the big match in"},{"Add":" // `handle_merge`). This mutates or clones the current"},{"Add":" // modified page, returning an `Op` describing what happened"},{"Add":" // (between update, merge, rebalance and split)."},{"Add":" let merge = P::merge_or_rebalance(txn, concat).await?;"},{"Add":" // Prepare a description (`last_op`) of the next page"},{"Add":" // modification, without mutating nor cloning that page."},{"Add":" last_op = handle_merge(txn, cursor, p0, &k0v0, incr_page, incr_mid, mil, merge, &mut free).await?;"},{"Add":" // If the modified page is shared with another tree, we will"},{"Add":" // clone it in the next round. Therefore, update the reference"},{"Add":" // counts of all the references in the modified page."},{"Add":" //"},{"Add":" // Since `handle_merge` pops the stack, the modified page is"},{"Add":" // at level `cursor.len() + 1`."},{"Add":" if cursor.len() + 1 >= cursor.first_rc_len() {"},{"Add":" modify_rc(txn, &last_op).await?;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // The last modification plan was on the root, and still needs to"},{"Add":" // be executed."},{"Add":" let root_is_shared = cursor.first_rc_len() == 1;"},{"Add":" update_root(txn, db, last_op, k0v0, root_is_shared, &mut free).await?;"},{"Add":""},{"Add":" // Finally, free all the pages marked as free during the deletion,"},{"Add":" // now that we don't need to read them anymore."},{"Add":" for p in free.iter() {"},{"Add":" if p[0] & 1 == 1 {"},{"Add":" txn.decr_rc_owned(p[0] ^ 1).await?;"},{"Add":" } else if p[0] > 0 {"},{"Add":" txn.decr_rc(p[0]).await?;"},{"Add":" }"},{"Add":" if p[1] & 1 == 1 {"},{"Add":" txn.decr_rc_owned(p[1] ^ 1).await?;"},{"Add":" } else if p[1] > 0 {"},{"Add":" txn.decr_rc(p[1]).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(true)"},{"Add":"}"},{"Add":""},{"Add":"/// Preparing a modified page for the leaf."},{"Add":"async fn leaf_delete<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized + 'a,"},{"Add":" V: Storable + ?Sized + 'a,"},{"Add":" P: BTreeMutPage + 'a,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" p0: usize,"},{"Add":") -> Result<(ModifiedPage<'a, K, V, P>, Option), T::Error> {"},{"Add":" let is_rc = cursor.len() >= cursor.first_rc_len();"},{"Add":" let del_at_internal = p0 < cursor.len();"},{"Add":" let curs0 = cursor.pop().unwrap();"},{"Add":" let (c0, c1) = P::split_at(&curs0.cursor);"},{"Add":" let mut deleted = None;"},{"Add":" if del_at_internal {"},{"Add":" // In this case, we need to save the replacement, and if this"},{"Add":" // leaf is shared with another tree, we also need increment"},{"Add":" // the replacement's references, since we are copying it."},{"Add":" let (k, v, _) = P::current(curs0.page.as_page(), &c1).unwrap();"},{"Add":" if is_rc {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" deleted = Some(P::save_deleted_leaf_entry(k, v))"},{"Add":" }"},{"Add":" Ok(("},{"Add":" ModifiedPage {"},{"Add":" page: curs0.page,"},{"Add":" mutable: !is_rc,"},{"Add":" c0,"},{"Add":" c1,"},{"Add":" skip_first: true,"},{"Add":" l: 0,"},{"Add":" r: 0,"},{"Add":" ins: None,"},{"Add":" ins2: None,"},{"Add":" // The following (`mod_is_left`) is meaningless in this"},{"Add":" // context, and isn't actually used: indeed, the only"},{"Add":" // place where this field is used is when modifying the"},{"Add":" // root, when `ins.is_some()`."},{"Add":" mod_is_left: true,"},{"Add":" },"},{"Add":" deleted,"},{"Add":" ))"},{"Add":"}"},{"Add":""},{"Add":"/// From a cursor at level `p = cursor.len()`, form the"},{"Add":"/// concatenation of `last_op` (which is a modified page at level p +"},{"Add":"/// 1`, and its left or right sibling, depending on the case."},{"Add":"async fn concat<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" p0: usize,"},{"Add":" k0v0: &Option,"},{"Add":" last_op: ModifiedPage<'a, K, V, P>,"},{"Add":") -> Result, T::Error> {"},{"Add":" let p = cursor.len();"},{"Add":" let rc_level = cursor.first_rc_len();"},{"Add":" let curs = cursor.current_mut();"},{"Add":""},{"Add":" if p == p0 {"},{"Add":" // Here, p == p0, meaning that we're deleting at an internal"},{"Add":" // node. If that's the case, k0v0 is `Some`, hence we can"},{"Add":" // safely unwrap the replacement."},{"Add":" let (k0, v0) = unsafe { P::from_saved(k0v0.as_ref().unwrap()) };"},{"Add":""},{"Add":" // Since we've picked the leftmost entry of the right child of"},{"Add":" // the deleted entry, the other page to consider in the"},{"Add":" // concatenation is the left child of the deleted entry."},{"Add":" let other = txn.load_page(P::left_child(curs.page.as_page(), &curs.cursor)).await?;"},{"Add":" // Then, if the page at level `p` or one of its ancestor, is"},{"Add":" // pointed at least twice (i.e. if `p >= rc_level`, or"},{"Add":" // alternatively if `other` is itself pointed at least twice,"},{"Add":" // the page is immutable, meaning that we can't delete on it"},{"Add":" // when rebalancing."},{"Add":" let other_is_mutable = (p < rc_level) && txn.rc(other.offset).await? < 2;"},{"Add":" Ok(Concat {"},{"Add":" modified: last_op,"},{"Add":" mid: (k0, v0),"},{"Add":" other,"},{"Add":" mod_is_left: false,"},{"Add":" other_is_mutable,"},{"Add":" })"},{"Add":" } else {"},{"Add":" // Here, `p` is not a leaf (but `last_op` might be), and does"},{"Add":" // not contain the deleted entry."},{"Add":""},{"Add":" // In this case, the visited page at level `p+1` is always on"},{"Add":" // the left-hand side of the cursor at level `p` (this is an"},{"Add":" // invariant of cursors). However, if the cursor at level `p`"},{"Add":" // is past the end of the page, we need to move one step back"},{"Add":" // to find a middle element for the concatenation, in which"},{"Add":" // case the visited page becomes the right-hand side of the"},{"Add":" // cursor."},{"Add":" let ((k, v, r), mod_is_left) ="},{"Add":" if let Some(x) = P::current(curs.page.as_page(), &curs.cursor) {"},{"Add":" // Not the last element of the page."},{"Add":" (x, true)"},{"Add":" } else {"},{"Add":" // Last element of the page."},{"Add":" let (k, v, _) = P::prev(curs.page.as_page(), &mut curs.cursor).unwrap();"},{"Add":" let l = P::left_child(curs.page.as_page(), &curs.cursor);"},{"Add":" ((k, v, l), false)"},{"Add":" };"},{"Add":" let other = txn.load_page(r).await?;"},{"Add":" let other_is_mutable = (p < rc_level) && txn.rc(other.offset).await? < 2;"},{"Add":" Ok(Concat {"},{"Add":" modified: last_op,"},{"Add":""},{"Add":" // The middle element comes from the page above this"},{"Add":" // concatenation, and hence has the same lifetime as that"},{"Add":" // page. However, our choice of lifetimes can't express"},{"Add":" // this, but we also know that we are not going to mutate"},{"Add":" // the parent before rebalancing or merging the"},{"Add":" // concatenation, and hence this pointer will be alive"},{"Add":" // during these operations (i.e. during the merge or"},{"Add":" // rebalance)."},{"Add":" mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v)) },"},{"Add":""},{"Add":" other,"},{"Add":" mod_is_left,"},{"Add":" other_is_mutable,"},{"Add":" })"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Prepare a modified version of the page at the current level `p ="},{"Add":"/// cursor.len()`."},{"Add":"async fn handle_merge<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized + PartialEq,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" p0: usize,"},{"Add":" k0v0: &Option,"},{"Add":" incr_other: Option,"},{"Add":" incr_mid: Option<(&K, &V)>,"},{"Add":""},{"Add":" mod_is_left: bool, // The modified page in the `merge` is the left one."},{"Add":""},{"Add":" merge: Op<'a, T, K, V>,"},{"Add":" free: &mut [[u64; 2]; N_CURSORS],"},{"Add":") -> Result, T::Error> {"},{"Add":" let mutable = cursor.len() < cursor.first_rc_len();"},{"Add":" let mut last_op = {"},{"Add":" // Beware, a stack pop happens here, all subsequent references"},{"Add":" // to the pointer must be updated."},{"Add":" let curs = cursor.pop().unwrap();"},{"Add":" let (c0, c1) = P::split_at(&curs.cursor);"},{"Add":" ModifiedPage {"},{"Add":" page: curs.page,"},{"Add":" mutable,"},{"Add":" c0,"},{"Add":" l: 0,"},{"Add":" r: 0,"},{"Add":" ins: None,"},{"Add":" ins2: None,"},{"Add":" c1,"},{"Add":" skip_first: true,"},{"Add":" mod_is_left,"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" // For merges and rebalances, take care of the reference counts of"},{"Add":" // pages and key/values."},{"Add":" match merge {"},{"Add":" Op::Merged {.. } | Op::Rebalanced { .. } => {"},{"Add":" // Increase the RC of the \"other page's\" descendants. In"},{"Add":" // the case of a rebalance, this has the effect of"},{"Add":" // increasing the RC of the new middle entry if that entry"},{"Add":" // comes from a shared page, which is what we want."},{"Add":" if let Some(other) = incr_other {"},{"Add":" let mut curs = P::cursor_first(&other);"},{"Add":" let left = P::left_child(other.as_page(), &curs);"},{"Add":" if left > 0 {"},{"Add":" txn.incr_rc(left).await?;"},{"Add":" }"},{"Add":" while let Some((k0, v0, r)) = P::next(other.as_page(), &mut curs) {"},{"Add":" for o in k0.page_references().chain(v0.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" if r != 0 {"},{"Add":" txn.incr_rc(r).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // If the middle element comes from a shared page,"},{"Add":" // increment its references."},{"Add":" if let Some((ref k, ref v)) = incr_mid {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" _ => {}"},{"Add":" }"},{"Add":""},{"Add":" // Here, we match on `merge`, the operation that just happened at"},{"Add":" // level `cursor.len() + 1`, and build the modification plan"},{"Add":" // for the page at the current level (i.e. at level"},{"Add":" // `cursor.len()`)."},{"Add":" let freed = match merge {"},{"Add":" Op::Merged {"},{"Add":" page,"},{"Add":" freed,"},{"Add":" marker: _,"},{"Add":" } => {"},{"Add":" // If we're deleting at an internal node, the"},{"Add":" // replacement has already been included in the merged"},{"Add":" // page."},{"Add":" last_op.l = page.0.offset;"},{"Add":" freed"},{"Add":" }"},{"Add":" Op::Rebalanced {"},{"Add":" k,"},{"Add":" v,"},{"Add":" l,"},{"Add":" r,"},{"Add":" freed,"},{"Add":" } => {"},{"Add":" // If we're deleting at an internal node, the"},{"Add":" // replacement is already in pages `l` or `r`."},{"Add":" last_op.l = l;"},{"Add":" last_op.r = r;"},{"Add":" last_op.ins = Some((k, v));"},{"Add":" freed"},{"Add":" }"},{"Add":" Op::Put(Put::Ok(Ok { page, freed })) => {"},{"Add":" // No merge, split or rebalance has happened. If we're"},{"Add":" // deleting at an internal node (i.e. if cursor.len =="},{"Add":" // p0), we need to mark the replacement here."},{"Add":" if cursor.len() + 1 == p0 {"},{"Add":" // We have already incremented the references of the"},{"Add":" // replacement at the leaf."},{"Add":" if let Some(k0v0) = k0v0 {"},{"Add":" last_op.ins = Some(unsafe { P::from_saved(k0v0) });"},{"Add":" }"},{"Add":" last_op.r = page.0.offset;"},{"Add":" } else {"},{"Add":" last_op.skip_first = false;"},{"Add":" if mod_is_left {"},{"Add":" last_op.l = page.0.offset;"},{"Add":" } else {"},{"Add":" last_op.r = page.0.offset;"},{"Add":" }"},{"Add":" }"},{"Add":" [freed, 0]"},{"Add":" }"},{"Add":" Op::Put(Put::Split {"},{"Add":" left,"},{"Add":" right,"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" freed,"},{"Add":" }) => {"},{"Add":" // This case only happens if `(K, V)` is not `Sized`, when"},{"Add":" // either (1) a rebalance replaces a key/value pair with a"},{"Add":" // larger one or (2) another split has happened in a page"},{"Add":" // below."},{"Add":" let split_key_is_k0 = if cursor.len() == p0 {"},{"Add":" // In this case, ins2 comes after ins, since the"},{"Add":" // replacement is in the right child of the deleted"},{"Add":" // key."},{"Add":" if let Some(k0v0) = k0v0 {"},{"Add":" last_op.ins = Some(unsafe { P::from_saved(k0v0) });"},{"Add":" }"},{"Add":" last_op.ins2 = Some((split_key, split_value));"},{"Add":" false"},{"Add":" } else {"},{"Add":" last_op.ins = Some((split_key, split_value));"},{"Add":" last_op.skip_first = false;"},{"Add":""},{"Add":" // If the page modified in the last step is the one on"},{"Add":" // the right of the current entry, move right one step"},{"Add":" // before inserting the split key/value."},{"Add":" //"},{"Add":" // (remember that we popped the stack upon entering"},{"Add":" // this function)."},{"Add":" //"},{"Add":" // We need to do this because the split key/value is"},{"Add":" // inserted immediately *before* the current cursor"},{"Add":" // position, which is incorrect if the split key/value"},{"Add":" // comes from the right-hand side of the current"},{"Add":" // cursor position."},{"Add":" //"},{"Add":" // This can happen in exactly two situations:"},{"Add":" // - when the element we are deleting is the one we are"},{"Add":" // skipping here."},{"Add":" // - when we are deleting in the rightmost child of a"},{"Add":" // page."},{"Add":" if cursor.len() > 0 && !mod_is_left {"},{"Add":" P::move_next(&mut last_op.c1);"},{"Add":" }"},{"Add":" // If the split key is the replacement element, we have"},{"Add":" // already increased its counter when we deleted it from"},{"Add":" // its original position at the bottom of the tree."},{"Add":" //"},{"Add":" // This can happen if we replaced an element and that"},{"Add":" // replacement caused a split with the replacement as the"},{"Add":" // middle element."},{"Add":" if let Some(k0v0) = k0v0 {"},{"Add":" assert!(cursor.len() + 1 < p0);"},{"Add":" let (k0, _) = unsafe { P::from_saved(k0v0) };"},{"Add":" core::ptr::eq(k0, split_key)"},{"Add":" } else {"},{"Add":" false"},{"Add":" }"},{"Add":" };"},{"Add":" // The `l` and `r` fields are relative to `ins2` if"},{"Add":" // `ins2.is_some()` or to `ins` else."},{"Add":" last_op.l = left.0.offset;"},{"Add":" last_op.r = right.0.offset;"},{"Add":" if cursor.len() + 2 >= cursor.first_rc_len() && !split_key_is_k0 {"},{"Add":" for o in split_key"},{"Add":" .page_references()"},{"Add":" .chain(split_value.page_references())"},{"Add":" {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" [freed, 0]"},{"Add":" }"},{"Add":" };"},{"Add":" // Free the page(s) at level `cursor.len() + 1` if it isn't"},{"Add":" // shared with another tree, or if it is the first level shared"},{"Add":" // with another tree."},{"Add":" if cursor.len() + 1 < cursor.first_rc_len() {"},{"Add":" free[cursor.len() + 1] = freed;"},{"Add":" }"},{"Add":" Ok(last_op)"},{"Add":"}"},{"Add":""},{"Add":"// This function modifies the reference counts of references of the"},{"Add":"// modified page, which is the page *about to be* modified."},{"Add":"//"},{"Add":"// This function is always called when `m` is an internal node."},{"Add":"async fn modify_rc<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreePage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" m: &ModifiedPage<'a, K, V, P>,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" let mut c0 = m.c0.clone();"},{"Add":" let mut c1 = m.c1.clone();"},{"Add":" let mut left = P::left_child(m.page.as_page(), &c0);"},{"Add":" while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c0) {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" if left != 0 {"},{"Add":" txn.incr_rc(left).await?;"},{"Add":" }"},{"Add":" left = r;"},{"Add":" }"},{"Add":" // The insertions are taken care of in `handle_merge` above,"},{"Add":" // so we can directly move to the `c1` part of the"},{"Add":" // modification."},{"Add":" if m.skip_first {"},{"Add":" P::move_next(&mut c1);"},{"Add":" }"},{"Add":" // If we are not updating the left child of c1's first"},{"Add":" // element, increment that left child."},{"Add":" if m.l == 0 {"},{"Add":" if left != 0 {"},{"Add":" txn.incr_rc(left).await?;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // If we are not updating the right child of the first"},{"Add":" // element of `c1`, increment that right child's RC."},{"Add":" if let Some((k, v, r)) = P::next(m.page.as_page(), &mut c1) {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" // If `m.skip_first`, we have already skipped the entry above,"},{"Add":" // so this `r` has nothing to do with any update."},{"Add":" //"},{"Add":" // Else, if we aren't skipping, but also aren't updating the"},{"Add":" // right child of the current entry, also increase the RC."},{"Add":" if (m.skip_first || m.r == 0) && r != 0 {"},{"Add":" txn.incr_rc(r).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" // Finally, increment the RCs of all other elements in `c1`."},{"Add":" while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c1) {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" if r != 0 {"},{"Add":" txn.incr_rc(r).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"},{"Add":""},{"Add":"async fn update_root<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db_,"},{"Add":" last_op: ModifiedPage<'a, K, V, P>,"},{"Add":" k0v0: Option,"},{"Add":" is_rc: bool,"},{"Add":" free: &mut [[u64; 2]; N_CURSORS],"},{"Add":") -> Result<(), T::Error> {"},{"Add":" if let Some(d) = single_child(&last_op) {"},{"Add":" // If the root had only one element, and the last operation"},{"Add":" // was a merge, this decreases the depth of the tree."},{"Add":" //"},{"Add":" // We don't do this if the table is empty (i.e. if `d == 0`),"},{"Add":" // in order to be consistent with put and drop."},{"Add":" if d > 0 {"},{"Add":" if last_op.page.is_dirty() {"},{"Add":" txn.decr_rc_owned(last_op.page.offset).await?;"},{"Add":" } else {"},{"Add":" txn.decr_rc(last_op.page.offset).await?;"},{"Add":" }"},{"Add":" db.db = d;"},{"Add":" } else {"},{"Add":" // The page becomes empty."},{"Add":" let (page, freed) = P::del(txn, last_op.page, last_op.mutable, &last_op.c1, d).await?;"},{"Add":" free[0][0] = freed;"},{"Add":" db.db = page.0.offset"},{"Add":" }"},{"Add":" return Ok(());"},{"Add":" }"},{"Add":""},{"Add":" // Else, the last operation `last_op` was relative to the root,"},{"Add":" // but it hasn't been applied yet. We apply it now:"},{"Add":" match modify::<_, K, V, P>(txn, last_op).await? {"},{"Add":" Put::Ok(Ok { page, freed }) => {"},{"Add":" // Here, the root was simply updated (i.e. some elements"},{"Add":" // might have been deleted/inserted/updated), so we just"},{"Add":" // need to update the Db."},{"Add":" free[0][0] = freed;"},{"Add":" db.db = page.0.offset"},{"Add":" }"},{"Add":" Put::Split {"},{"Add":" split_key: k,"},{"Add":" split_value: v,"},{"Add":" left: MutPage(CowPage { offset: l, .. }),"},{"Add":" right: MutPage(CowPage { offset: r, .. }),"},{"Add":" freed,"},{"Add":" } => {"},{"Add":" // Else, the root has split, and we need to allocate a new"},{"Add":" // page to hold the split key/value and the two sides of"},{"Add":" // the split."},{"Add":" free[0][0] = freed;"},{"Add":" let mut page = txn.alloc_page().await?;"},{"Add":" P::init(&mut page);"},{"Add":" let mut c = P::cursor_before(&page.0);"},{"Add":" P::move_next(&mut c);"},{"Add":" let page = if let Put::Ok(p) = P::put(txn, page.0, true, false, &c, k, v, None, l, r).await? {"},{"Add":" p.page"},{"Add":" } else {"},{"Add":" unreachable!()"},{"Add":" };"},{"Add":" let split_key_is_k0 = if let Some(ref k0v0) = k0v0 {"},{"Add":" let (k0, _) = unsafe { P::from_saved(k0v0) };"},{"Add":" core::ptr::eq(k0, k)"},{"Add":" } else {"},{"Add":" false"},{"Add":" };"},{"Add":" // If the root isn't shared with another tree, and the"},{"Add":" // split key is different from the replacement, increment"},{"Add":" // the RCs of the references contained in the split"},{"Add":" // key/value."},{"Add":" //"},{"Add":" // The replacement need not be incremented again, since it"},{"Add":" // was already increment when we took it from the page in"},{"Add":" // `leaf_delete`."},{"Add":" if is_rc && !split_key_is_k0 {"},{"Add":" for o in k.page_references().chain(v.page_references()) {"},{"Add":" txn.incr_rc(o).await?;"},{"Add":" }"},{"Add":" }"},{"Add":" // Finally, update the database."},{"Add":" db.db = page.0.offset"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"},{"Add":""},{"Add":"fn single_child>("},{"Add":" m: &ModifiedPage,"},{"Add":") -> Option {"},{"Add":" let mut c1 = m.c1.clone();"},{"Add":" if m.skip_first {"},{"Add":" P::move_next(&mut c1);"},{"Add":" }"},{"Add":" if P::is_empty(&m.c0) && m.ins.is_none() && P::is_empty(&c1) {"},{"Add":" Some(m.l)"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Apply the modifications to a page. This is exclusively used for"},{"Add":"/// the root page, because other modifications are applied during a"},{"Add":"/// merge/rebalance attempts."},{"Add":"async fn modify<'a, T: AllocPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreeMutPage>("},{"Add":" txn: &mut T,"},{"Add":" m: ModifiedPage<'a, K, V, P>,"},{"Add":") -> Result, T::Error> {"},{"Add":" if let Some((k, v)) = m.ins {"},{"Add":" // The following call might actually replace the first element"},{"Add":" // of `m.c1` if `m.skip_first`."},{"Add":" let mut c1 = m.c1.clone();"},{"Add":" if !m.skip_first && !m.mod_is_left {"},{"Add":" // This means that the page below just split, since we"},{"Add":" // have to insert an extra entry on the root page."},{"Add":" //"},{"Add":" // However, the extra entry is to be inserted (by"},{"Add":" // `P::put`) *before* `c1`'s first element, which is"},{"Add":" // incorrect since the page that split is the right child"},{"Add":" // of `c1`'s first element. Therefore, we need to move"},{"Add":" // `c1` one notch to the right."},{"Add":" assert!(m.ins2.is_none());"},{"Add":" P::move_next(&mut c1);"},{"Add":" }"},{"Add":" P::put("},{"Add":" txn,"},{"Add":" m.page,"},{"Add":" m.mutable,"},{"Add":" m.skip_first,"},{"Add":" &c1,"},{"Add":" k,"},{"Add":" v,"},{"Add":" m.ins2,"},{"Add":" m.l,"},{"Add":" m.r,"},{"Add":" ).await"},{"Add":" } else {"},{"Add":" // If there's no insertion to do, we might still need to"},{"Add":" // delete elements, or update children."},{"Add":" if m.skip_first {"},{"Add":" let (page, freed) = P::del(txn, m.page, m.mutable, &m.c1, m.l).await?;"},{"Add":" Ok(Put::Ok(Ok { freed, page }))"},{"Add":" } else if m.l > 0 {"},{"Add":" // If the left page of the current entry has changed,"},{"Add":" // update it."},{"Add":" Ok(Put::Ok(P::update_left_child("},{"Add":" txn, m.page, m.mutable, &m.c1, m.l,"},{"Add":" ).await?))"},{"Add":" } else {"},{"Add":" // If there's no insertion, and `m.l == 0`, we need to"},{"Add":" // update the right child of the current entry. The"},{"Add":" // following moves one step to the right and updates the"},{"Add":" // left child:"},{"Add":" let mut c1 = m.c1.clone();"},{"Add":" P::move_next(&mut c1);"},{"Add":" Ok(Put::Ok(P::update_left_child("},{"Add":" txn, m.page, m.mutable, &c1, m.r,"},{"Add":" ).await?))"},{"Add":" }"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"cursor.rs","metadata":0},"context":[{"change":0,"pos":12617}],"contents":[{"Add":"use super::*;"},{"Add":"use crate::{CowPage, LoadPage};"},{"Add":"use core::mem::MaybeUninit;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub(super) struct PageCursor> {"},{"Add":" pub page: CowPage,"},{"Add":" pub cursor: P::Cursor,"},{"Add":"}"},{"Add":"unsafe impl> Send for PageCursor{}"},{"Add":"unsafe impl> Sync for PageCursor{}"},{"Add":""},{"Add":"// This is 1 + the maximal depth of a tree."},{"Add":"//"},{"Add":"// Since pages are of size 2^12, there are at most 2^52 addressable"},{"Add":"// pages (potentially less depending on the platform). Since each page"},{"Add":"// of a B tree below the root has at least 2 elements (because each"},{"Add":"// page is at least half-full, and elements are at most 1/4th of a"},{"Add":"// page), the arity is at least 3, except for the root. Since 3^33 is"},{"Add":"// the smallest power of 3 larger than 2^52, the maximum depth is 33."},{"Add":"pub(crate) const N_CURSORS: usize = 33;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"/// A position in a B tree."},{"Add":"pub struct Cursor> {"},{"Add":" /// Invariant: the first `len` items are initialised."},{"Add":" stack: [core::mem::MaybeUninit>; N_CURSORS],"},{"Add":" /// The length of the stack at the position of the first page"},{"Add":" /// shared with another tree. This definition is a little bit"},{"Add":" /// convoluted, but allows for efficient comparisons between"},{"Add":" /// `first_rc_len` and `len` to check whether a page is shared"},{"Add":" /// with another tree."},{"Add":" first_rc_len: usize,"},{"Add":" /// Number of initialised items on the stack."},{"Add":" len: usize,"},{"Add":"}"},{"Add":""},{"Add":"unsafe impl> Send for Cursor{}"},{"Add":"unsafe impl> Sync for Cursor{}"},{"Add":""},{"Add":"impl<'a, K: 'a + ?Sized + Storable, V: 'a + ?Sized + Storable, P: BTreePage> Cursor {"},{"Add":" /// Create a new cursor, initialised to the first entry of the B tree."},{"Add":" pub async fn new(txn: &T, db: &Db_) -> Result {"},{"Add":" // Looking forward to getting array initialisation stabilised :)"},{"Add":" let mut stack = ["},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" core::mem::MaybeUninit::uninit(),"},{"Add":" ];"},{"Add":" let page = txn.load_page(db.db).await?;"},{"Add":" stack[0] = MaybeUninit::new(PageCursor {"},{"Add":" cursor: P::cursor_before(&page),"},{"Add":" page,"},{"Add":" });"},{"Add":" Ok(Cursor {"},{"Add":" stack,"},{"Add":" first_rc_len: N_CURSORS,"},{"Add":" len: 1,"},{"Add":" })"},{"Add":" }"},{"Add":""},{"Add":" pub(super) fn push(&mut self, p: PageCursor) {"},{"Add":" self.stack[self.len] = MaybeUninit::new(p);"},{"Add":" self.len += 1;"},{"Add":" }"},{"Add":""},{"Add":" pub(super) fn cur(&self) -> &PageCursor {"},{"Add":" assert!(self.len > 0);"},{"Add":" unsafe { &*self.stack[self.len - 1].as_ptr() }"},{"Add":" }"},{"Add":""},{"Add":" pub(super) fn len(&self) -> usize {"},{"Add":" self.len"},{"Add":" }"},{"Add":""},{"Add":" pub(super) fn first_rc_len(&self) -> usize {"},{"Add":" self.first_rc_len"},{"Add":" }"},{"Add":""},{"Add":" pub(super) fn pop(&mut self) -> Option> {"},{"Add":" if self.len > 0 {"},{"Add":" self.len -= 1;"},{"Add":" let result = core::mem::replace(&mut self.stack[self.len], MaybeUninit::uninit());"},{"Add":" Some(unsafe { result.assume_init() })"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" pub(super) fn current_mut(&mut self) -> &mut PageCursor {"},{"Add":" assert!(self.len > 0);"},{"Add":" unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() }"},{"Add":" }"},{"Add":""},{"Add":" /// Push the leftmost path starting at page `left_page` onto the"},{"Add":" /// stack."},{"Add":" pub(super) async fn set_first_leaf("},{"Add":" &mut self,"},{"Add":" txn: &T,"},{"Add":" mut left_page: u64,"},{"Add":" ) -> Result<(), T::Error> {"},{"Add":" while left_page > 0 {"},{"Add":" if self.first_rc_len >= N_CURSORS && txn.rc(left_page).await? >= 2 {"},{"Add":" self.first_rc_len = self.len + 1"},{"Add":" }"},{"Add":" let page = txn.load_page(left_page).await?;"},{"Add":" let curs = P::cursor_first(&page);"},{"Add":" left_page = P::left_child(page.as_page(), &curs);"},{"Add":" self.push(PageCursor { page, cursor: curs });"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" /// Reset the cursor to the first element of the database."},{"Add":" pub fn reset(&mut self) {"},{"Add":" self.len = 1;"},{"Add":" let init = unsafe { &mut *self.stack[0].as_mut_ptr() };"},{"Add":" init.cursor = P::cursor_before(&init.page);"},{"Add":" }"},{"Add":""},{"Add":" // An invariant of cursors, fundamental to understanding the"},{"Add":" // `next` and `prev` functions below, is that the lower levels (in"},{"Add":" // the tree, upper levels on the stack) are the left children of"},{"Add":" // the cursor's position on a page."},{"Add":""},{"Add":" /// Set the cursor to the first position larger than or equal to"},{"Add":" /// the specified key and value."},{"Add":" pub async fn set("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" k: &K,"},{"Add":" v: Option<&V>,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" // Set the \"cursor stack\" by setting a cursor in each page"},{"Add":" // on a path from the root to the appropriate leaf."},{"Add":""},{"Add":" // Start from the bottom of the stack, which is also the root"},{"Add":" // of the tree."},{"Add":" self.len = 1;"},{"Add":" self.first_rc_len = N_CURSORS;"},{"Add":" let init = unsafe { &mut *self.stack[0].as_mut_ptr() };"},{"Add":" init.cursor = P::cursor_before(&init.page);"},{"Add":""},{"Add":" let mut last_matching_page = N_CURSORS;"},{"Add":" let mut last_match = None;"},{"Add":" while self.len < N_CURSORS {"},{"Add":" let current = unsafe { &mut *self.stack.get_unchecked_mut(self.len - 1).as_mut_ptr() };"},{"Add":" if self.first_rc_len >= N_CURSORS && txn.rc(current.page.offset).await? >= 2 {"},{"Add":" self.first_rc_len = self.len"},{"Add":" }"},{"Add":" let ref mut cursor = current.cursor;"},{"Add":" if let Ok((kk, vv, _)) = P::set_cursor(txn, current.page.as_page(), cursor, k, v).await {"},{"Add":" if v.is_some() {"},{"Add":" return Ok(Some((kk, vv)));"},{"Add":" }"},{"Add":" last_match = Some((kk, vv));"},{"Add":" last_matching_page = self.len"},{"Add":" }"},{"Add":" let next_page = P::left_child(current.page.as_page(), cursor);"},{"Add":" if next_page > 0 {"},{"Add":" let page = txn.load_page(next_page).await?;"},{"Add":" self.push(PageCursor {"},{"Add":" cursor: P::cursor_before(&page),"},{"Add":" page,"},{"Add":" });"},{"Add":" } else {"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" if last_matching_page < N_CURSORS {"},{"Add":" self.len = last_matching_page;"},{"Add":" Ok(last_match)"},{"Add":" } else {"},{"Add":" Ok(None)"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Set the cursor after the last element, so that [`Self::next`]"},{"Add":" /// returns `None`, and [`Self::prev`] returns the last element."},{"Add":" pub async fn set_last< T: LoadPage>("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" ) -> Result<(), T::Error> {"},{"Add":" self.len = 1;"},{"Add":" self.first_rc_len = N_CURSORS;"},{"Add":" let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };"},{"Add":" current.cursor = P::cursor_after(¤t.page);"},{"Add":" loop {"},{"Add":" let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };"},{"Add":" if self.first_rc_len >= N_CURSORS && txn.rc(current.page.offset).await? >= 2 {"},{"Add":" self.first_rc_len = self.len"},{"Add":" }"},{"Add":" let l = P::left_child(current.page.as_page(), ¤t.cursor);"},{"Add":" if l > 0 {"},{"Add":" let page = txn.load_page(l).await?;"},{"Add":" self.push(PageCursor {"},{"Add":" cursor: P::cursor_after(&page),"},{"Add":" page,"},{"Add":" })"},{"Add":" } else {"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" /// Return the current position of the cursor."},{"Add":" pub fn current("},{"Add":" &mut self,"},{"Add":" _txn: &'a T,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" loop {"},{"Add":" let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };"},{"Add":" if P::is_init(¤t.cursor) {"},{"Add":" // The cursor hasn't been set."},{"Add":" return Ok(None)"},{"Add":" } else if let Some((k, v, _)) = P::current(current.page.as_page(), ¤t.cursor)"},{"Add":" {"},{"Add":" unsafe {"},{"Add":" return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));"},{"Add":" }"},{"Add":" } else if self.len > 1 {"},{"Add":" self.len -= 1"},{"Add":" } else {"},{"Add":" // We're past the last element at the root."},{"Add":" return Ok(None);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Return the current position of the cursor, and move the cursor"},{"Add":" /// to the next position."},{"Add":" pub async fn next< T: LoadPage>("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" loop {"},{"Add":" let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };"},{"Add":" if P::is_empty(¤t.cursor) {"},{"Add":" if self.len > 1 {"},{"Add":" if self.first_rc_len == self.len {"},{"Add":" self.first_rc_len = N_CURSORS"},{"Add":" }"},{"Add":" self.len -= 1"},{"Add":" } else {"},{"Add":" return Ok(None);"},{"Add":" }"},{"Add":" } else {"},{"Add":" let (cur_entry, r) = if let Some((k, v, r)) = P::current(current.page.as_page(), ¤t.cursor) {"},{"Add":" (Some((k, v)), r)"},{"Add":" } else {"},{"Add":" (None, P::right_child(current.page.as_page(), ¤t.cursor))"},{"Add":" };"},{"Add":" P::move_next(&mut current.cursor);"},{"Add":" if r != 0 {"},{"Add":" let page = txn.load_page(r).await?;"},{"Add":" self.push(PageCursor {"},{"Add":" cursor: P::cursor_before(&page),"},{"Add":" page,"},{"Add":" });"},{"Add":" if self.first_rc_len >= N_CURSORS && txn.rc(r).await? >= 2 {"},{"Add":" self.first_rc_len = self.len"},{"Add":" }"},{"Add":" }"},{"Add":" if let Some((k, v)) = cur_entry {"},{"Add":" unsafe {"},{"Add":" return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Move the cursor to the previous entry, and return the entry"},{"Add":" /// that was current before the move. If the cursor is initially"},{"Add":" /// after all the entries, this moves it back by two steps."},{"Add":" pub async fn prev< T: LoadPage>("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" loop {"},{"Add":" let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };"},{"Add":""},{"Add":" if P::is_init(¤t.cursor) {"},{"Add":" if self.len > 1 {"},{"Add":" if self.first_rc_len == self.len {"},{"Add":" self.first_rc_len = N_CURSORS"},{"Add":" }"},{"Add":" self.len -= 1;"},{"Add":" let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };"},{"Add":" P::move_prev(&mut current.cursor);"},{"Add":" } else {"},{"Add":" return Ok(None);"},{"Add":" }"},{"Add":" } else {"},{"Add":" let cur_entry = P::current(current.page.as_page(), ¤t.cursor);"},{"Add":" let left = P::left_child(current.page.as_page(), ¤t.cursor);"},{"Add":" if left != 0 {"},{"Add":" let page = txn.load_page(left).await?;"},{"Add":" self.push(PageCursor {"},{"Add":" cursor: P::cursor_after(&page),"},{"Add":" page,"},{"Add":" });"},{"Add":" if self.first_rc_len >= N_CURSORS && txn.rc(left).await? >= 2 {"},{"Add":" self.first_rc_len = self.len"},{"Add":" }"},{"Add":" } else {"},{"Add":" // We are at a leaf."},{"Add":" P::move_prev(&mut current.cursor);"},{"Add":" }"},{"Add":" if let Some((k, v, _)) = cur_entry {"},{"Add":" unsafe {"},{"Add":" return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub struct Iter<'a, T: LoadPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage> {"},{"Add":" txn: &'a T,"},{"Add":" cursor: Cursor,"},{"Add":"}"},{"Add":""},{"Add":"pub async fn iter<'a, T, K, V, P>("},{"Add":" txn: &'a T,"},{"Add":" db: &super::Db_,"},{"Add":" origin: Option<(&K, Option<&V>)>,"},{"Add":") -> Result, T::Error>"},{"Add":"where"},{"Add":" T: LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreePage,"},{"Add":"{"},{"Add":" let mut cursor = Cursor::new(txn, db).await?;"},{"Add":" if let Some((k, v)) = origin {"},{"Add":" cursor.set(txn, k, v).await?;"},{"Add":" }"},{"Add":" Ok(Iter { cursor, txn })"},{"Add":"}"},{"Add":""},{"Add":"impl<"},{"Add":" 'a,"},{"Add":" T: LoadPage,"},{"Add":" K: Storable + ?Sized + 'a,"},{"Add":" V: Storable + ?Sized + 'a,"},{"Add":" P: BTreePage + 'a,"},{"Add":" > Iter<'a, T, K, V, P>"},{"Add":"{"},{"Add":" pub async fn next(&mut self) -> Result, T::Error>{"},{"Add":" self.cursor.prev(self.txn).await"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"pub struct RevIter<'a, T: LoadPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage>"},{"Add":"{"},{"Add":" txn: &'a T,"},{"Add":" cursor: Cursor,"},{"Add":"}"},{"Add":""},{"Add":"pub async fn rev_iter<'a, T, K, V, P>("},{"Add":" txn: &'a T,"},{"Add":" db: &super::Db_,"},{"Add":" origin: Option<(&K, Option<&V>)>,"},{"Add":") -> Result, T::Error>"},{"Add":"where"},{"Add":" T: LoadPage,"},{"Add":" K: Storable + ?Sized,"},{"Add":" V: Storable + ?Sized,"},{"Add":" P: BTreePage,"},{"Add":"{"},{"Add":" let mut cursor = Cursor::new(txn, db).await?;"},{"Add":" if let Some((k, v)) = origin {"},{"Add":" cursor.set(txn, k, v).await?;"},{"Add":" } else {"},{"Add":" cursor.set_last(txn).await?;"},{"Add":" }"},{"Add":" Ok(RevIter { cursor, txn })"},{"Add":"}"},{"Add":""},{"Add":"impl<"},{"Add":" 'a,"},{"Add":" T: LoadPage,"},{"Add":" K: Storable + ?Sized + 'a,"},{"Add":" V: Storable + ?Sized + 'a,"},{"Add":" P: BTreePage + 'a,"},{"Add":" > RevIter<'a, T, K, V, P>"},{"Add":"{"},{"Add":" pub async fn next(&mut self) -> Result, T::Error>{"},{"Add":" self.cursor.prev(self.txn).await"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"Cargo.toml","metadata":0},"context":[{"change":0,"pos":32}],"contents":[{"Add":"[package]"},{"Add":"name = \"sanakirja-core-async\""},{"Add":"version = \"0.0.1\""},{"Add":"edition = \"2018\""},{"Add":"description = \"Copy-on-write datastructures, storable on disk (or elsewhere) with a stable format.\""},{"Add":"authors = [\"Pierre-Étienne Meunier\", \"Florent Becker\"]"},{"Add":"license = \"MIT/Apache-2.0\""},{"Add":"documentation = \"https://docs.rs/sanakirja-core-async\""},{"Add":"repository = \"https://nest.pijul.com/pijul/sanakirja\""},{"Add":"include = ["},{"Add":"\"Cargo.toml\","},{"Add":"\"src/lib.rs\","},{"Add":"\"src\","},{"Add":"\"src/btree\","},{"Add":"\"src/btree/page_cursor.rs\","},{"Add":"\"src/btree/page_unsized\","},{"Add":"\"src/btree/page_unsized/alloc.rs\","},{"Add":"\"src/btree/page_unsized/rebalance.rs\","},{"Add":"\"src/btree/page_unsized/header.rs\","},{"Add":"\"src/btree/page_unsized/put.rs\","},{"Add":"\"src/btree/page_unsized/cursor.rs\","},{"Add":"\"src/btree/put.rs\","},{"Add":"\"src/btree/page\","},{"Add":"\"src/btree/page/alloc.rs\","},{"Add":"\"src/btree/page/rebalance.rs\","},{"Add":"\"src/btree/page/put.rs\","},{"Add":"\"src/btree/del.rs\","},{"Add":"\"src/btree/mod.rs\","},{"Add":"\"src/btree/page_unsized.rs\","},{"Add":"\"src/btree/cursor.rs\","},{"Add":"\"src/btree/page.rs\""},{"Add":"]"},{"Add":""},{"Add":"[features]"},{"Add":"crc32 = [ \"crc32fast\" ]"},{"Add":"std = []"},{"Add":"ed25519 = [ \"ed25519-zebra\", \"ed25519-zebra/serde\" ]"},{"Add":""},{"Add":"[dependencies]"},{"Add":"crc32fast = { version = \"1.2\", optional = true, default-features = false }"},{"Add":"uuid = { version = \"0.8\", optional = true }"},{"Add":"ed25519-zebra = { version = \"2.2\", optional = true }"},{"Add":"async-trait = \"0.1\""}]}},{"Replacement":{"inode":{"change":3,"pos":108835},"path":"Cargo.toml","line":2,"ins":{"up_context":[{"change":3,"pos":108848}],"down_context":[],"flag":"BLOCK","start":221929,"end":221996,"inode":{"change":3,"pos":108835}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":108848},"to":{"change":3,"start":108848,"end":108891},"introduced_by":3}],"inode":{"change":3,"pos":108835}},"ins_contents":[{"Add":"members = [ \"sanakirja-core\", \"sanakirja\", \"sanakirja-core-async\" ]"}],"del_contents":[{"Del":"members = [ \"sanakirja-core\", \"sanakirja\" ]"}]}}],"owner":"pijul","repo":"sanakirja","token":"b0Ak90GyH9cFZJsMtQmPEaRP+kQCkHC/qWyquh/0NUo=","login":null}

…

Dependencies

Change contents