{"header":{"message":"Resetting history","description":null,"timestamp":"2021-01-30T18:47:25.011809332Z","authors":[{"full_name":"Pierre-Étienne Meunier","name":"pmeunier"}]},"hash":"OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","authors":[],"deps":{"hashes":[["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","Resetting history"],["AA",null]],"deps":[],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"sanakirja-core","metadata":1005},"context":[{"change":1,"pos":0}],"contents":[]}},{"FileAdd":{"meta":{"basename":"src","metadata":1005},"context":[{"change":0,"pos":17}],"contents":[]}},{"FileAdd":{"meta":{"basename":"main.rs","metadata":420},"context":[{"change":0,"pos":24}],"contents":[{"Add":"fn main() {"},{"Add":" println!(\"Hello, world!\");"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"lib.rs","metadata":420},"context":[{"change":0,"pos":24}],"contents":[{"Add":"#![no_std]"},{"Add":"pub mod btree;"},{"Add":""},{"Add":"pub trait Representable {"},{"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 PageOffsets: Iterator;"},{"Add":""},{"Add":" type Ord: Ord;"},{"Add":" fn ord(&self, txn: &T) -> &Self::Ord;"},{"Add":""},{"Add":" /// If this value is an offset to another page at offset `offset`,"},{"Add":" /// return `Some(offset)`. Return `None` else."},{"Add":" fn page_offsets(&self) -> Self::PageOffsets;"},{"Add":" const ALIGN: usize;"},{"Add":" const SIZE: Option;"},{"Add":" fn size(&self) -> usize;"},{"Add":"}"},{"Add":""},{"Add":"macro_rules! direct_repr {"},{"Add":" ($t: ty) => {"},{"Add":" impl Representable for $t {"},{"Add":" type PageOffsets = core::iter::Empty;"},{"Add":" fn page_offsets(&self) -> Self::PageOffsets {"},{"Add":" core::iter::empty()"},{"Add":" }"},{"Add":" const ALIGN: usize = core::mem::align_of::();"},{"Add":" const SIZE: Option = Some(core::mem::size_of::());"},{"Add":" type Ord = Self;"},{"Add":" fn ord(&self, _: &T) -> &Self::Ord {"},{"Add":" self"},{"Add":" }"},{"Add":" fn size(&self) -> usize {"},{"Add":" core::mem::size_of::()"},{"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!(u64);"},{"Add":""},{"Add":"unsafe fn read, V: Representable>(p: *mut u8) -> (*mut K, *mut V) {"},{"Add":" let k = p as *mut K;"},{"Add":" let s = K::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 as *mut V)"},{"Add":"}"},{"Add":""},{"Add":"fn alloc_size, V: Representable>(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":"unsafe fn entry_size, V: Representable>(k: *mut u8) -> usize {"},{"Add":" let ks = (&*(k as *const K)).size();"},{"Add":" // next multiple of va, assuming va is a power of 2."},{"Add":" let va = V::ALIGN;"},{"Add":" let v_off = (ks + va - 1) & !(va - 1);"},{"Add":" let v_ptr = k.add(v_off);"},{"Add":" let vs = (&*(v_ptr as *const V)).size();"},{"Add":" let ka = K::ALIGN.max(V::ALIGN);"},{"Add":" let size = v_off + vs;"},{"Add":" (size + ka - 1) & !(ka - 1)"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"pub struct Page {"},{"Add":" pub data: *mut u8,"},{"Add":" pub offset: u64,"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"pub struct MutPage(pub Page);"},{"Add":""},{"Add":"impl MutPage {"},{"Add":" pub fn clear_dirty(&mut self) {"},{"Add":" unsafe {"},{"Add":" let d = *self.0.data.offset(8);"},{"Add":" *self.0.data.offset(8) = d & (!1)"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Trait for loading a page and a root. Base trait to implement"},{"Add":"/// \"storage engines\" under Sanakirja."},{"Add":"pub trait LoadPage {"},{"Add":" type Error;"},{"Add":" /// Loading a page."},{"Add":" fn load_page(&self, off: u64) -> Result;"},{"Add":" /// RC"},{"Add":" fn rc(&self, off: u64) -> Result;"},{"Add":"}"},{"Add":""},{"Add":"/// Trait for loading a page and a root. Base trait to implement"},{"Add":"/// \"storage engines\" under Sanakirja."},{"Add":"pub trait AllocPage: LoadPage {"},{"Add":" fn alloc_page(&mut self) -> Result;"},{"Add":" fn incr_rc(&mut self, off: u64) -> Result<(), Self::Error>;"},{"Add":" fn decr_rc(&mut self, off: u64) -> Result<(), Self::Error>;"},{"Add":" fn decr_rc_owned(&mut self, off: u64) -> Result<(), Self::Error>;"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"btree","metadata":1005},"context":[{"change":0,"pos":24}],"contents":[]}},{"FileAdd":{"meta":{"basename":"put.rs","metadata":420},"context":[{"change":0,"pos":3438}],"contents":[{"Add":"// Copyright 2015 Pierre-Étienne Meunier and Florent Becker. See the"},{"Add":"// COPYRIGHT file at the top-level directory of this distribution and"},{"Add":"// at http://pijul.org/COPYRIGHT."},{"Add":"//"},{"Add":"// Licensed under the Apache License, Version 2.0 or the MIT license"},{"Add":"// , at your"},{"Add":"// option. This file may not be copied, modified, or distributed"},{"Add":"// except according to those terms."},{"Add":""},{"Add":"use super::cursor::*;"},{"Add":"use super::*;"},{"Add":"use log::*;"},{"Add":""},{"Add":"/// Insert a binding to a database, returning `false` if and only"},{"Add":"/// if the exact same binding (key *and* value) was already in the database."},{"Add":"pub fn put, V: Representable, P: BTreeMutPage>("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db,"},{"Add":" key: &K,"},{"Add":" value: &V,"},{"Add":") -> Result {"},{"Add":" let mut cursor = Cursor::new(db);"},{"Add":" if cursor.set(txn, Some((key, Some(value))))?.is_some() {"},{"Add":" return Ok(false);"},{"Add":" }"},{"Add":" let ref cur = cursor.current();"},{"Add":" let put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" cursor.pointer <= cursor.first_rc_level,"},{"Add":" cur.cursor.as_ref().unwrap(),"},{"Add":" key,"},{"Add":" value,"},{"Add":" 0,"},{"Add":" 0,"},{"Add":" )?;"},{"Add":" let mut free = [0; N_CURSORS];"},{"Add":" db.db = put_cascade(txn, &mut cursor, put, &mut free)?.0;"},{"Add":" for f in free.iter() {"},{"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":"fn put_cascade, V: Representable, P: BTreeMutPage>("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" mut put: Put,"},{"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":" cursor.pointer -= 1;"},{"Add":" incr_descendants::(txn, cursor, free, freed)?;"},{"Add":" if cursor.pointer == 0 {"},{"Add":" debug!(\"Split root: {:?} {:?}\", left.0.offset, right.0.offset);"},{"Add":" // Splitting the root."},{"Add":" let p = txn.alloc_page()?;"},{"Add":" P::init(p);"},{"Add":" P::put("},{"Add":" txn,"},{"Add":" p.0,"},{"Add":" true,"},{"Add":" &P::first_cursor(&p.0),"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" )?;"},{"Add":" return Ok(p);"},{"Add":" } else {"},{"Add":" debug!(\"put cascade\");"},{"Add":" let cur = cursor.current();"},{"Add":" put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" cursor.pointer < cursor.first_rc_level,"},{"Add":" cur.cursor.as_ref().unwrap(),"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" )?"},{"Add":" }"},{"Add":" }"},{"Add":" Put::Ok(Ok { page, freed }) if cursor.pointer > 1 => {"},{"Add":" debug!(\"put update\");"},{"Add":" cursor.pointer -= 1;"},{"Add":" incr_descendants::(txn, cursor, free, freed)?;"},{"Add":" // update"},{"Add":" let ref curs = cursor.current();"},{"Add":" put = Put::Ok(P::update_left_child("},{"Add":" txn,"},{"Add":" curs.page,"},{"Add":" cursor.pointer < cursor.first_rc_level,"},{"Add":" curs.cursor.as_ref().unwrap(),"},{"Add":" page.0.offset,"},{"Add":" )?)"},{"Add":" }"},{"Add":" Put::Ok(Ok { page, freed }) => {"},{"Add":" incr_descendants::(txn, cursor, free, freed)?;"},{"Add":" return Ok(page);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"fn incr_descendants<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreePage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":" free: &mut [u64; N_CURSORS],"},{"Add":" freed: u64,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" if cursor.pointer < cursor.first_rc_level {"},{"Add":" // This also includes the case where cursor.pointer == 0."},{"Add":" free[cursor.pointer] = freed;"},{"Add":" } else {"},{"Add":" if cursor.pointer == cursor.first_rc_level {"},{"Add":" debug_assert_ne!(freed, 0);"},{"Add":" if freed & 1 != 0 {"},{"Add":" txn.decr_rc_owned(freed ^ 1)?;"},{"Add":" } else {"},{"Add":" txn.decr_rc(freed ^ 1)?;"},{"Add":" }"},{"Add":" }"},{"Add":" let cur = cursor.current();"},{"Add":" let mut c = P::first_cursor(&cur.page);"},{"Add":" let left = P::left_child(&cur.page, &c);"},{"Add":" if left != (freed & !1) {"},{"Add":" txn.incr_rc(left)?;"},{"Add":" }"},{"Add":" while let Some((k, v, r)) = P::next(&cur.page, &mut c) {"},{"Add":" for o in k.page_offsets().chain(v.page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" if r != freed {"},{"Add":" txn.incr_rc(r)?;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"page.rs","metadata":420},"context":[{"change":0,"pos":3438}],"contents":[{"Add":"use super::*;"},{"Add":"use log::*;"},{"Add":""},{"Add":"const PAGE_SIZE: usize = 4096;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Page {"},{"Add":" kv: core::marker::PhantomData<(K, V)>,"},{"Add":"}"},{"Add":""},{"Add":"#[derive(PartialEq, Eq, PartialOrd, Ord)]"},{"Add":"#[repr(C)]"},{"Add":"struct Tuple {"},{"Add":" k: K,"},{"Add":" v: V,"},{"Add":"}"},{"Add":""},{"Add":"#[repr(C)]"},{"Add":"struct Header {"},{"Add":" n: u16,"},{"Add":" data: u16,"},{"Add":" crc: u32,"},{"Add":" left_page: u64,"},{"Add":"}"},{"Add":""},{"Add":"impl Header {"},{"Add":" fn init(&mut self) {"},{"Add":" self.n = 1; // dirty page"},{"Add":" self.data = 4096_u16.to_le();"},{"Add":" self.crc = 0;"},{"Add":" self.left_page = 0;"},{"Add":" }"},{"Add":""},{"Add":" fn n(&self) -> u16 {"},{"Add":" u16::from_le(self.n) >> 4"},{"Add":" }"},{"Add":""},{"Add":" fn set_n(&mut self, n: u16) {"},{"Add":" let dirty = u16::from_le(self.n) & 1;"},{"Add":" self.n = ((n << 4) | dirty).to_le()"},{"Add":" }"},{"Add":""},{"Add":" fn is_dirty(&self) -> bool {"},{"Add":" u16::from_le(self.n) & 1 != 0"},{"Add":" }"},{"Add":""},{"Add":" fn left_page(&self) -> u64 {"},{"Add":" u64::from_le(self.left_page)"},{"Add":" }"},{"Add":""},{"Add":" fn decr(&mut self, s: usize) {"},{"Add":" self.left_page = (self.left_page() - s as u64).to_le();"},{"Add":" }"},{"Add":""},{"Add":" fn is_leaf(&self) -> bool {"},{"Add":" u64::from_le(self.left_page) <= 0xfff"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"const HDR: usize = core::mem::size_of::

();"},{"Add":""},{"Add":"impl, V: Representable> super::BTreeMutPage"},{"Add":" for Page"},{"Add":"{"},{"Add":" fn init(page: MutPage) {"},{"Add":" unsafe { (&mut *(page.0.data as *mut Header)).init() }"},{"Add":" }"},{"Add":""},{"Add":" fn clean(page: MutPage) {"},{"Add":" unsafe {"},{"Add":" let hdr = &mut *header_mut(page);"},{"Add":" hdr.n = (u16::from_le(hdr.n) & 0xfff).to_le()"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn size(m: &ModifiedPage) -> usize {"},{"Add":" let mut occupied = unsafe {"},{"Add":" let hdr = &*header(&m.page);"},{"Add":" (hdr.left_page() & 0xfff) as usize"},{"Add":" };"},{"Add":" if fixed_size::().is_some() && m.c1.is_leaf {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" occupied += (HDR + al - 1) & (!al - 1);"},{"Add":" } else {"},{"Add":" occupied += HDR"},{"Add":" };"},{"Add":" occupied -= Self::current_size(&m.page, &m.c1) as usize;"},{"Add":" if let Some((k, v, _)) = m.ins {"},{"Add":" occupied += unsafe { crate::alloc_size(&*k, &*v) as usize };"},{"Add":" if m.c1.is_leaf {"},{"Add":" if fixed_size::().is_none() {"},{"Add":" occupied += 2"},{"Add":" }"},{"Add":" } else {"},{"Add":" occupied += 8"},{"Add":" }"},{"Add":" }"},{"Add":" occupied"},{"Add":" }"},{"Add":""},{"Add":" fn put<'a>("},{"Add":" txn: &mut T,"},{"Add":" page: crate::Page,"},{"Add":" mutable: bool,"},{"Add":" c: &Cursor,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" unsafe {"},{"Add":" if r == 0 {"},{"Add":" debug!(\"leaf put\");"},{"Add":" put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, 0, 0)"},{"Add":" } else {"},{"Add":" debug!(\"internal put\");"},{"Add":" put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, l, r)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn update_left_child("},{"Add":" txn: &mut T,"},{"Add":" page: crate::Page,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" r: u64,"},{"Add":" ) -> Result {"},{"Add":" assert!(!c.is_leaf);"},{"Add":" let freed;"},{"Add":" let page = if mutable && Self::is_dirty(page) {"},{"Add":" freed = 0;"},{"Add":" MutPage(page)"},{"Add":" } else {"},{"Add":" unsafe {"},{"Add":" let new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(new);"},{"Add":" let s = Internal::offset_slice::(page);"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut n = 0;"},{"Add":" clone::(hdr, page, new, s, &mut n);"},{"Add":" let b = if Self::is_dirty(page) { 1 } else { 0 };"},{"Add":" freed = page.offset | b;"},{"Add":" new"},{"Add":" }"},{"Add":" };"},{"Add":" assert!(c.cur - 1 < c.total);"},{"Add":" unsafe {"},{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur as isize - 1);"},{"Add":" *off = (r | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"},{"Add":" Ok(Ok { page, freed })"},{"Add":" }"},{"Add":""},{"Add":" fn del(txn: &mut T, page: crate::Page, c: &Cursor, l: u64) -> Result {"},{"Add":" assert!(c.cur < c.total);"},{"Add":" if Self::is_dirty(page) {"},{"Add":" let page = MutPage(page);"},{"Add":" unsafe {"},{"Add":" let hdr = header_mut(page);"},{"Add":" if c.is_leaf {"},{"Add":" let n = (&*hdr).n() as usize;"},{"Add":" if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let off = c.cur * f;"},{"Add":" let kv_ptr = page.0.data.add(hdr_size + off);"},{"Add":" core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur - 1));"},{"Add":" (&mut *hdr).decr(f);"},{"Add":" } else {"},{"Add":" let ptr = page.0.data.add(HDR + c.cur * 2) as *mut u16;"},{"Add":" let kv_ptr = page.0.data.add((*ptr) as usize);"},{"Add":" let size = entry_size::(kv_ptr);"},{"Add":" core::ptr::copy(ptr.offset(1), ptr, n - c.cur);"},{"Add":" (&mut *hdr).decr(size);"},{"Add":" }"},{"Add":" } else {"},{"Add":" let ptr = page.0.data.add(HDR + c.cur * 8) as *mut u64;"},{"Add":" let off = (u64::from_le(*ptr) & 0xfff) as usize;"},{"Add":" let kv_ptr = page.0.data.add(off);"},{"Add":" let size = entry_size::(kv_ptr);"},{"Add":" core::ptr::copy(ptr.offset(1), ptr, (&*hdr).n() as usize - c.cur);"},{"Add":" (&mut *hdr).decr(size);"},{"Add":" };"},{"Add":" if l > 0 {"},{"Add":" assert!(!c.is_leaf);"},{"Add":" // Updating the left page if necessary."},{"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":" (&mut *hdr).set_n(u16::from_le((&*hdr).n) - 1);"},{"Add":" Ok(page)"},{"Add":" }"},{"Add":" } else {"},{"Add":" unsafe {"},{"Add":" let new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(new);"},{"Add":" if c.is_leaf {"},{"Add":" let s = Leaf::offset_slice::(page);"},{"Add":" let (s0, s1) = s.split_at(c.cur);"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut n = 0;"},{"Add":" clone::(hdr, page, new, s0, &mut n);"},{"Add":" clone::(hdr, page, new, s1, &mut n);"},{"Add":" } else {"},{"Add":" let s = Internal::offset_slice::(page);"},{"Add":" let (s0, s1) = s.split_at(c.cur);"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut n = 0;"},{"Add":" clone::(hdr, page, new, s0, &mut n);"},{"Add":" let off = (page.data.add(HDR) as *mut u64).offset(n - 1);"},{"Add":" *off = l.to_le();"},{"Add":" clone::(hdr, page, new, s1, &mut n);"},{"Add":" }"},{"Add":" Ok(new)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn merge_or_rebalance<'a>("},{"Add":" txn: &mut T,"},{"Add":" m: &mut Concat,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" let mut hdr_size = HDR;"},{"Add":" let mid_size = if m.modified.c0.is_leaf {"},{"Add":" if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" f"},{"Add":" } else {"},{"Add":" 2 + unsafe { alloc_size::(&*m.mid.0, &*m.mid.1) }"},{"Add":" }"},{"Add":" } else {"},{"Add":" 8 + unsafe { alloc_size::(&*m.mid.0, &*m.mid.1) }"},{"Add":" };"},{"Add":" let left_size = Self::size(&m.modified);"},{"Add":" let occupied = unsafe {"},{"Add":" let hdr = &*header(&m.other);"},{"Add":" (hdr.left_page() & 0xfff) as usize"},{"Add":" };"},{"Add":" let size = left_size + mid_size + occupied - hdr_size;"},{"Add":" if size <= PAGE_SIZE {"},{"Add":" // merge"},{"Add":" let new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(new);"},{"Add":" unsafe {"},{"Add":" if m.modified.c0.is_leaf {"},{"Add":" merge::<_, _, _, Leaf>(new, m)"},{"Add":" } else {"},{"Add":" merge::<_, _, _, Internal>(new, m)"},{"Add":" }"},{"Add":" }"},{"Add":" let b0 = if Self::is_dirty(m.modified.page) {"},{"Add":" 1"},{"Add":" } else {"},{"Add":" 0"},{"Add":" };"},{"Add":" let b1 = if Self::is_dirty(m.other) { 1 } else { 0 };"},{"Add":" return 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":" let rc = >::first_cursor(&m.other);"},{"Add":" let first_size = >::current_size(&m.other, &rc);"},{"Add":" // If we can't rebalance, return."},{"Add":" if left_size >= PAGE_SIZE / 2 || occupied - first_size < PAGE_SIZE / 2 {"},{"Add":" unsafe {"},{"Add":" return Ok(Op::Put(if let Some((k, v, r)) = m.modified.ins {"},{"Add":" Self::replace("},{"Add":" txn,"},{"Add":" m.modified.page,"},{"Add":" m.modified.mutable,"},{"Add":" &m.modified.c1,"},{"Add":" &*k,"},{"Add":" &*v,"},{"Add":" m.modified.l,"},{"Add":" r,"},{"Add":" )?"},{"Add":" } else {"},{"Add":" Put::Ok(Ok {"},{"Add":" page: Self::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?,"},{"Add":" freed: 0,"},{"Add":" })"},{"Add":" }));"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe {"},{"Add":" if m.modified.c0.is_leaf {"},{"Add":" rebalance::<_, _, _, Leaf>(txn, m)"},{"Add":" } else {"},{"Add":" rebalance::<_, _, _, Internal>(txn, m)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl, V: Representable> super::BTreePage"},{"Add":" for Page"},{"Add":"{"},{"Add":" fn is_dirty(page: crate::Page) -> bool {"},{"Add":" unsafe {"},{"Add":" let hdr = &*header(&page);"},{"Add":" hdr.n & 0x8000 != 0"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn is_empty(_: &crate::Page, c: &Self::Cursor) -> bool {"},{"Add":" c.cur >= c.total"},{"Add":" }"},{"Add":" type Cursor = Cursor;"},{"Add":" fn first_cursor(p: &crate::Page) -> Self::Cursor {"},{"Add":" unsafe {"},{"Add":" let hdr = &*header(p);"},{"Add":" Cursor {"},{"Add":" cur: 0,"},{"Add":" total: hdr.n() as usize,"},{"Add":" is_leaf: hdr.is_leaf(),"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" fn last_cursor(p: &crate::Page) -> Self::Cursor {"},{"Add":" unsafe {"},{"Add":" let hdr = &*header(p);"},{"Add":" let total = hdr.n() as usize;"},{"Add":" Cursor {"},{"Add":" cur: total - 1,"},{"Add":" total,"},{"Add":" is_leaf: hdr.is_leaf(),"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn unchecked_current(page: &crate::Page, c: &Self::Cursor) -> (*mut K, *mut V, u64) {"},{"Add":" if c.is_leaf {"},{"Add":" let off = if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr = (HDR + al - 1) & !(al - 1);"},{"Add":" hdr + c.cur * f"},{"Add":" } else {"},{"Add":" u16::from_le(*(page.data.add(HDR + c.cur * 2) as *const u16)) as usize"},{"Add":" };"},{"Add":" let (k, v) = read::(page.data.add(off as usize));"},{"Add":" (k, v, 0)"},{"Add":" } else {"},{"Add":" let off = u64::from_le(*(page.data.add(HDR) as *const u64).add(c.cur));"},{"Add":" let (k, v) = read::(page.data.add((off & 0xfff) as usize));"},{"Add":" (k, v, off & !0xfff)"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn unchecked_current_ptr(page: &crate::Page, c: &Self::Cursor) -> *mut u8 {"},{"Add":" page.data.add(if c.is_leaf {"},{"Add":" if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr = (HDR + al - 1) & !(al - 1);"},{"Add":" hdr + c.cur * f"},{"Add":" } else {"},{"Add":" u16::from_le(*(page.data.add(HDR + c.cur * 2) as *const u16)) as usize"},{"Add":" }"},{"Add":" } else {"},{"Add":" (u64::from_le(*(page.data.add(HDR + c.cur * 8) as *const u64)) & 0xfff) as usize"},{"Add":" })"},{"Add":" }"},{"Add":" fn current_size(page: &crate::Page, c: &Self::Cursor) -> usize {"},{"Add":" unsafe {"},{"Add":" if c.is_leaf {"},{"Add":" if let Some(f) = fixed_size::() {"},{"Add":" f"},{"Add":" } else {"},{"Add":" 2 + entry_size::("},{"Add":" page.data"},{"Add":" .add(u16::from_le(*(page.data.add(HDR) as *const u16).add(c.cur))"},{"Add":" as usize),"},{"Add":" )"},{"Add":" }"},{"Add":" } else {"},{"Add":" 8 + entry_size::(page.data.add("},{"Add":" (u64::from_le(*(page.data.add(HDR) as *const u64).add(c.cur)) & 0xfff) as usize,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" fn move_next(_page: &crate::Page, c: &mut Self::Cursor) -> bool {"},{"Add":" if c.cur < c.total {"},{"Add":" c.cur += 1;"},{"Add":" true"},{"Add":" } else {"},{"Add":" false"},{"Add":" }"},{"Add":" }"},{"Add":" fn left_child(page: &crate::Page, c: &Self::Cursor) -> u64 {"},{"Add":" if c.is_leaf {"},{"Add":" 0"},{"Add":" } else {"},{"Add":" let off = unsafe { *(page.data.add((HDR + 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":" let off = unsafe { *(page.data.add(HDR + c.cur * 8) as *const u64) };"},{"Add":" u64::from_le(off) & !0xfff"},{"Add":" }"},{"Add":" }"},{"Add":" fn set_cursor<'a>("},{"Add":" txn: &T,"},{"Add":" page: &crate::Page,"},{"Add":" c: &mut Cursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" ) -> Result<(&'a mut K, &'a mut V, u64), usize> {"},{"Add":" unsafe {"},{"Add":" let hdr = &*header(&page);"},{"Add":" c.total = hdr.n() as usize;"},{"Add":" let result;"},{"Add":" c.is_leaf = hdr.is_leaf();"},{"Add":""},{"Add":" let hdr = &*header(&page);"},{"Add":" let lookup = if c.is_leaf {"},{"Add":" if fixed_size::().is_some() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let s = core::slice::from_raw_parts("},{"Add":" page.data.add(hdr_size) as *const Tuple,"},{"Add":" hdr.n() as usize,"},{"Add":" );"},{"Add":" s.binary_search_by(|tup| {"},{"Add":" if let Some(v0) = v0 {"},{"Add":" (tup.k.ord(txn), tup.v.ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))"},{"Add":" } else {"},{"Add":" (tup.k.ord(txn)).cmp(k0.ord(txn))"},{"Add":" }"},{"Add":" })"},{"Add":" } else {"},{"Add":" let s = core::slice::from_raw_parts("},{"Add":" page.data.add(HDR) as *const u16,"},{"Add":" hdr.n() as usize,"},{"Add":" );"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u16::from_le(off);"},{"Add":" let (k, v) = read::(page.data.offset(off as isize));"},{"Add":" if let Some(v0) = v0 {"},{"Add":" ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))"},{"Add":" } else {"},{"Add":" ((&*k).ord(txn)).cmp(k0.ord(txn))"},{"Add":" }"},{"Add":" })"},{"Add":" }"},{"Add":" } else {"},{"Add":" let s ="},{"Add":" core::slice::from_raw_parts(page.data.add(HDR) as *const u64, hdr.n() as usize);"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u64::from_le(off) & 0xfff;"},{"Add":" let (k, v) = read::(page.data.offset(off as isize & 0xfff));"},{"Add":" if let Some(v0) = v0 {"},{"Add":" ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))"},{"Add":" } else {"},{"Add":" ((&*k).ord(txn)).cmp(k0.ord(txn))"},{"Add":" }"},{"Add":" })"},{"Add":" };"},{"Add":" c.cur = match lookup {"},{"Add":" Ok(n) => {"},{"Add":" result = if c.is_leaf {"},{"Add":" let off = if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" (0, (hdr_size + f * n) as u16)"},{"Add":" } else {"},{"Add":" let off = u16::from_le(*(page.data.add(HDR + n * 2) as *const u16));"},{"Add":" (0, off)"},{"Add":" };"},{"Add":" Ok(Leaf::kv(*page, off))"},{"Add":" } else {"},{"Add":" let off = u64::from_le(*(page.data.add(HDR + n * 8) as *const u64));"},{"Add":" Ok(Internal::kv(*page, (off & !0xfff, (off & 0xfff) as u16)))"},{"Add":" };"},{"Add":" n"},{"Add":" }"},{"Add":" Err(n) => {"},{"Add":" result = Err(n);"},{"Add":" n"},{"Add":" }"},{"Add":" };"},{"Add":" result"},{"Add":" }"},{"Add":" }"},{"Add":" fn split_at(_: &crate::Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {"},{"Add":" ("},{"Add":" Cursor {"},{"Add":" cur: 0,"},{"Add":" total: c.cur,"},{"Add":" is_leaf: c.is_leaf,"},{"Add":" },"},{"Add":" *c,"},{"Add":" )"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"fn fixed_size, V: Representable>() -> Option {"},{"Add":" if let (Some(ks), Some(vs)) = (K::SIZE, V::SIZE) {"},{"Add":" let s = ((ks + V::ALIGN - 1) & !(V::ALIGN - 1)) + vs;"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" Some((s + al - 1) & !(al - 1))"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"pub struct Cursor {"},{"Add":" cur: usize,"},{"Add":" total: usize,"},{"Add":" is_leaf: bool,"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn header(page: &crate::Page) -> *const Header {"},{"Add":" page.data as *const Header"},{"Add":"}"},{"Add":"unsafe fn header_mut(page: crate::MutPage) -> *mut Header {"},{"Add":" page.0.data as *mut Header"},{"Add":"}"},{"Add":""},{"Add":"trait Alloc {"},{"Add":" unsafe fn can_alloc, V: Representable>("},{"Add":" hdr: &Header,"},{"Add":" size: usize,"},{"Add":" ) -> bool;"},{"Add":" unsafe fn can_compact, V: Representable>("},{"Add":" hdr: &Header,"},{"Add":" size: usize,"},{"Add":" ) -> bool;"},{"Add":" unsafe fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16;"},{"Add":" unsafe fn alloc_insert, V: Representable>("},{"Add":" hdr: &mut Header,"},{"Add":" new: &MutPage,"},{"Add":" n: &mut isize,"},{"Add":" size: usize,"},{"Add":" r: u64,"},{"Add":" ) -> usize;"},{"Add":" unsafe fn set_offset(new: MutPage, n: isize, r: u64, off: u16);"},{"Add":" unsafe fn set_right_child(new: MutPage, n: isize, r: u64);"},{"Add":" type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;"},{"Add":" unsafe fn offset_slice<'a, T, K: Representable, V: Representable>("},{"Add":" page: crate::Page,"},{"Add":" ) -> Offsets<'a, Self::Offset>;"},{"Add":" unsafe fn kv<'a, T, K: Representable, V: Representable>("},{"Add":" page: crate::Page,"},{"Add":" off: (u64, u16),"},{"Add":" ) -> (&'a mut K, &'a mut V, u64);"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone)]"},{"Add":"enum Offsets<'a, A> {"},{"Add":" Slice(&'a [A]),"},{"Add":" Range(core::ops::Range),"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {"},{"Add":" fn split_at(&self, mid: usize) -> (Self, Self) {"},{"Add":" match self {"},{"Add":" Offsets::Slice(s) => {"},{"Add":" let (a, b) = s.split_at(mid);"},{"Add":" (Offsets::Slice(a), Offsets::Slice(b))"},{"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":" fn len(&self) -> usize {"},{"Add":" match self {"},{"Add":" Offsets::Slice(s) => s.len(),"},{"Add":" Offsets::Range(r) => r.end - r.start,"},{"Add":" }"},{"Add":" }"},{"Add":" fn first, V: Representable>(&self) -> (u64, u16) {"},{"Add":" match self {"},{"Add":" Offsets::Slice(s) => s[0].into(),"},{"Add":" Offsets::Range(r) => {"},{"Add":" let size = fixed_size::().unwrap();"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" (0, (hdr_size + r.start * size) as u16)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"struct Leaf {}"},{"Add":"struct Internal {}"},{"Add":""},{"Add":"impl Alloc for Leaf {"},{"Add":" unsafe fn can_alloc, V: Representable>("},{"Add":" hdr: &Header,"},{"Add":" size: usize,"},{"Add":" ) -> bool {"},{"Add":" if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let header_size = (HDR + al - 1) & !(al - 1);"},{"Add":" header_size + (hdr.n() as usize) * f + size < u16::from_le(hdr.data) as usize"},{"Add":" } else {"},{"Add":" HDR + (hdr.n() as usize) * 2 + 2 + size < u16::from_le(hdr.data) as usize"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn can_compact, V: Representable>("},{"Add":" hdr: &Header,"},{"Add":" size: usize,"},{"Add":" ) -> bool {"},{"Add":" if fixed_size::().is_some() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let header_size = (HDR + al - 1) & !(al - 1);"},{"Add":" header_size + ((hdr.left_page() & 0xfff) as usize) + size"},{"Add":" < u16::from_le(hdr.data) as usize"},{"Add":" } else {"},{"Add":" HDR + ((hdr.left_page() & 0xfff) as usize) + 2 + size < 4096"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {"},{"Add":" let mut data = u16::from_le(hdr.data) - size as u16;"},{"Add":" data -= data % (align as u16);"},{"Add":" hdr.data = data.to_le();"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.left_page = (hdr.left_page() + size as u64).to_le();"},{"Add":" data"},{"Add":" }"},{"Add":" unsafe fn alloc_insert, V: Representable>("},{"Add":" hdr: &mut Header,"},{"Add":" new: &MutPage,"},{"Add":" n: &mut isize,"},{"Add":" size: usize,"},{"Add":" _: u64,"},{"Add":" ) -> usize {"},{"Add":" if let Some(f) = fixed_size::() {"},{"Add":" let al = K::ALIGN.max(V::ALIGN);"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" debug!(\"{:?} {:?} {:?}\", new, hdr.n(), *n);"},{"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":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.left_page = (hdr.left_page() + f as u64).to_le();"},{"Add":" hdr_size + (*n as usize) * f"},{"Add":" } else {"},{"Add":" let off_new = Self::alloc(&mut *hdr, size, K::ALIGN);"},{"Add":" core::ptr::copy("},{"Add":" new.0.data.add(HDR + (*n as usize) * 2),"},{"Add":" new.0.data.add(HDR + (*n as usize) * 2 + 2),"},{"Add":" (hdr.n() as usize - (*n as usize)) * 2,"},{"Add":" );"},{"Add":" Self::set_offset(*new, *n, 0, off_new);"},{"Add":" off_new as usize"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn set_offset(new: MutPage, n: isize, _: u64, off: u16) {"},{"Add":" let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;"},{"Add":" *ptr = off.to_le();"},{"Add":" }"},{"Add":" unsafe fn set_right_child(_: MutPage, _: isize, _: u64) {}"},{"Add":" type Offset = LeafOffset;"},{"Add":" unsafe fn offset_slice<'a, T, K: Representable, V: Representable>("},{"Add":" page: crate::Page,"},{"Add":" ) -> Offsets<'a, Self::Offset> {"},{"Add":" let hdr = &*header(&page);"},{"Add":" if fixed_size::().is_some() {"},{"Add":" Offsets::Range(0..(hdr.n() as usize))"},{"Add":" } else {"},{"Add":" Offsets::Slice(core::slice::from_raw_parts("},{"Add":" page.data.add(HDR) as *const LeafOffset,"},{"Add":" hdr.n() as usize,"},{"Add":" ))"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn kv<'a, T, K: Representable, V: Representable>("},{"Add":" page: crate::Page,"},{"Add":" (_, off): (u64, u16),"},{"Add":" ) -> (&'a mut K, &'a mut V, u64) {"},{"Add":" let (k, v) = read::(page.data.add(off as usize));"},{"Add":" (&mut *k, &mut *v, 0)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Alloc for Internal {"},{"Add":" unsafe fn can_alloc, V: Representable>("},{"Add":" hdr: &Header,"},{"Add":" size: usize,"},{"Add":" ) -> bool {"},{"Add":" (HDR as usize) + (hdr.n() as usize) * 8 + 8 + size < u16::from_le(hdr.data) as usize"},{"Add":" }"},{"Add":" unsafe fn can_compact, V: Representable>("},{"Add":" hdr: &Header,"},{"Add":" size: usize,"},{"Add":" ) -> bool {"},{"Add":" (HDR as usize) + ((hdr.left_page() & 0xfff) as usize) + 8 + size < 4096"},{"Add":" }"},{"Add":" unsafe fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {"},{"Add":" let mut data = u16::from_le(hdr.data) - size as u16;"},{"Add":" data -= data % (align as u16);"},{"Add":" hdr.data = data.to_le();"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.left_page = (hdr.left_page() + size as u64).to_le();"},{"Add":" data"},{"Add":" }"},{"Add":" unsafe fn alloc_insert, V: Representable>("},{"Add":" hdr: &mut Header,"},{"Add":" new: &MutPage,"},{"Add":" n: &mut isize,"},{"Add":" size: usize,"},{"Add":" r: u64,"},{"Add":" ) -> usize {"},{"Add":" let off_new = Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN));"},{"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":" Self::set_offset(*new, *n, r, off_new);"},{"Add":" off_new as usize"},{"Add":" }"},{"Add":" unsafe fn set_offset(new: MutPage, n: isize, r: u64, off: u16) {"},{"Add":" let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;"},{"Add":" *ptr = (r | off as u64).to_le();"},{"Add":" }"},{"Add":" unsafe fn set_right_child(page: MutPage, n: isize, r: u64) {"},{"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":" type Offset = InternalOffset;"},{"Add":" unsafe fn offset_slice<'a, T, K: Representable, V: Representable>("},{"Add":" page: crate::Page,"},{"Add":" ) -> Offsets<'a, Self::Offset> {"},{"Add":" let hdr = &*header(&page);"},{"Add":" Offsets::Slice(core::slice::from_raw_parts("},{"Add":" page.data.add(HDR) as *const InternalOffset,"},{"Add":" hdr.n() as usize,"},{"Add":" ))"},{"Add":" }"},{"Add":" unsafe fn kv<'a, T, K: Representable, V: Representable>("},{"Add":" page: crate::Page,"},{"Add":" (r, off): (u64, u16),"},{"Add":" ) -> (&'a mut K, &'a mut V, u64) {"},{"Add":" let (k, v) = read::(page.data.add(off as usize));"},{"Add":" (&mut *k, &mut *v, r)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn modify, V: Representable, L: Alloc>("},{"Add":" new: MutPage,"},{"Add":" m: &mut ModifiedPage>,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut l = >::left_child(&m.page, &m.c0);"},{"Add":" while let Some((k, v, r)) = >::next(&m.page, &mut m.c0) {"},{"Add":" alloc::<_, _, _, L>(hdr, new, k, v, l, r, n);"},{"Add":" l = 0;"},{"Add":" }"},{"Add":" if let Some((k, v, r)) = m.ins {"},{"Add":" alloc::<_, _, _, L>(hdr, new, &*k, &*v, m.l, r, n);"},{"Add":" } else {"},{"Add":" l = m.l"},{"Add":" }"},{"Add":" let mut is_first = m.skip_first;"},{"Add":" while let Some((k, v, r)) = >::next(&m.page, &mut m.c1) {"},{"Add":" if is_first {"},{"Add":" is_first = false;"},{"Add":" continue;"},{"Add":" }"},{"Add":" alloc::<_, _, _, L>(hdr, new, k, v, l, r, n);"},{"Add":" l = 0;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn merge, V: Representable, L: Alloc>("},{"Add":" new: MutPage,"},{"Add":" m: &mut Concat>,"},{"Add":") {"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut n = 0;"},{"Add":" if m.mod_is_left {"},{"Add":" modify::<_, _, _, L>(new, m.modified, &mut n);"},{"Add":" let mut rc = >::first_cursor(&m.other);"},{"Add":" let l = >::left_child(&m.other, &rc);"},{"Add":" alloc::<_, _, _, L>(hdr, new, &*m.mid.0, &*m.mid.1, 0, l, &mut n);"},{"Add":" while let Some((k, v, r)) = >::next(&m.other, &mut rc) {"},{"Add":" alloc::<_, _, _, L>(hdr, new, k, v, 0, r, &mut n);"},{"Add":" }"},{"Add":" } else {"},{"Add":" let mut rc = >::first_cursor(&m.other);"},{"Add":" let mut l = >::left_child(&m.other, &rc);"},{"Add":" while let Some((k, v, r)) = >::next(&m.other, &mut rc) {"},{"Add":" alloc::<_, _, _, L>(hdr, new, k, v, l, r, &mut n);"},{"Add":" l = 0;"},{"Add":" }"},{"Add":" alloc::<_, _, _, L>(hdr, new, &*m.mid.0, &*m.mid.1, 0, 0, &mut n);"},{"Add":" modify::<_, _, _, L>(new, m.modified, &mut n);"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn rebalance<'a, T: AllocPage, K: Representable, V: Representable, L: Alloc>("},{"Add":" txn: &mut T,"},{"Add":" m: &mut Concat>,"},{"Add":") -> Result, T::Error> {"},{"Add":" let rc = >::first_cursor(&m.other);"},{"Add":" let rl = >::left_child(&m.other, &rc);"},{"Add":" let (k, v, r) = >::unchecked_current(&m.other, &rc);"},{"Add":""},{"Add":" let hdr = &*header(&m.modified.page);"},{"Add":" let mut freed = [0, 0];"},{"Add":" let new_left = if hdr.is_dirty() {"},{"Add":" let page = MutPage(m.modified.page);"},{"Add":" let hdr = &mut *header_mut(page);"},{"Add":" let mut n = m.modified.c1.total as isize;"},{"Add":" alloc::(hdr, page, &*m.mid.0, &*m.mid.1, 0, rl, &mut n);"},{"Add":" page"},{"Add":" } else {"},{"Add":" let new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(new);"},{"Add":" let s = L::offset_slice::(m.modified.page);"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut n = 0;"},{"Add":" clone::(hdr, m.modified.page, new, s, &mut n);"},{"Add":" alloc::(hdr, new, &*m.mid.0, &*m.mid.1, 0, rl, &mut n);"},{"Add":" let b = if hdr.is_dirty() { 1 } else { 0 };"},{"Add":" freed[0] = m.modified.page.offset | b;"},{"Add":" new"},{"Add":" };"},{"Add":" let new_right = >::del(txn, m.other, &rc, r)?;"},{"Add":" if new_right.0.offset != m.other.offset {"},{"Add":" let hdr = &*header(&m.other);"},{"Add":" let b = if hdr.is_dirty() { 1 } else { 0 };"},{"Add":" freed[1] = m.other.offset | b"},{"Add":" }"},{"Add":" Ok(Op::Rebalanced {"},{"Add":" l: new_left.0.offset,"},{"Add":" r: new_right.0.offset,"},{"Add":" k,"},{"Add":" v,"},{"Add":" freed,"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"#[repr(C)]"},{"Add":"struct LeafOffset(u16);"},{"Add":""},{"Add":"impl Into<(u64, u16)> for LeafOffset {"},{"Add":" fn into(self) -> (u64, u16) {"},{"Add":" (0, self.0)"},{"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":"struct InternalOffset(u64);"},{"Add":""},{"Add":"impl Into<(u64, u16)> for InternalOffset {"},{"Add":" fn into(self) -> (u64, u16) {"},{"Add":" (self.0 & !0xfff, (self.0 & 0xfff) as u16)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Into for InternalOffset {"},{"Add":" fn into(self) -> usize {"},{"Add":" self.0 as usize"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn clone, V: Representable, L: Alloc>("},{"Add":" hdr: &mut Header,"},{"Add":" page: crate::Page,"},{"Add":" new: MutPage,"},{"Add":" s: Offsets,"},{"Add":" n: &mut isize,"},{"Add":") {"},{"Add":" match s {"},{"Add":" Offsets::Slice(s) => {"},{"Add":" for off in s.iter() {"},{"Add":" let (r, off): (u64, u16) = (*off).into();"},{"Add":" let off = u16::from_le(off);"},{"Add":" let ptr = page.data.add(off as usize);"},{"Add":" let size = entry_size::(ptr);"},{"Add":" let off_new = L::alloc(&mut *hdr, size, K::ALIGN);"},{"Add":" core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);"},{"Add":" L::set_offset(new, *n, r, off_new);"},{"Add":" *n += 1;"},{"Add":" }"},{"Add":" }"},{"Add":" Offsets::Range(r) => {"},{"Add":" let size = fixed_size::().unwrap();"},{"Add":" let a = K::ALIGN.max(V::ALIGN);"},{"Add":" let header_size = (HDR + a - 1) & !(a - 1);"},{"Add":" for off in r {"},{"Add":" let ptr = page.data.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":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.left_page = (hdr.left_page() + size as u64).to_le();"},{"Add":" *n += 1;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn alloc, V: Representable, L: Alloc>("},{"Add":" hdr: &mut Header,"},{"Add":" new: 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 = L::alloc_insert::(hdr, &new, n, size, r);"},{"Add":" let new_ptr = new.0.data.add(off_new as usize);"},{"Add":" core::ptr::copy_nonoverlapping(k0, new_ptr as *mut K, 1);"},{"Add":" let ks = k0.size();"},{"Add":" let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));"},{"Add":" core::ptr::copy_nonoverlapping(v0, v_ptr as *mut V, 1);"},{"Add":" if l > 0 {"},{"Add":" L::set_right_child(new, *n - 1, l);"},{"Add":" }"},{"Add":" *n += 1;"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn put<'a, T: AllocPage, K: Representable, V: Representable, L: Alloc>("},{"Add":" txn: &mut T,"},{"Add":" page: crate::Page,"},{"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 size = alloc_size(k0, v0);"},{"Add":" let hdr = &*header(&page);"},{"Add":" if mutable && hdr.is_dirty() && L::can_alloc::(&*header(&page), size) {"},{"Add":" let page = MutPage(page);"},{"Add":" let hdr = &mut *header_mut(page);"},{"Add":" let mut n = u as isize;"},{"Add":" alloc::<_, _, _, L>(hdr, page, k0, v0, l, r, &mut n);"},{"Add":" Ok(Put::Ok(Ok { page, freed: 0 }))"},{"Add":" } else if L::can_compact::(hdr, size) {"},{"Add":" let new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(new);"},{"Add":" let s = L::offset_slice::(page);"},{"Add":" let (s0, s1) = s.split_at(u as usize);"},{"Add":" let hdr = &mut *header_mut(new);"},{"Add":" let mut n = 0;"},{"Add":" clone::(hdr, page, new, s0, &mut n);"},{"Add":" alloc::(hdr, new, k0, v0, l, r, &mut n);"},{"Add":" clone::(hdr, page, new, s1, &mut n);"},{"Add":" let b0 = if hdr.is_dirty() { 1 } else { 0 };"},{"Add":" return Ok(Put::Ok(Ok {"},{"Add":" page: new,"},{"Add":" freed: page.offset | b0,"},{"Add":" }));"},{"Add":" } else {"},{"Add":" if let Some(s) = fixed_size::() {"},{"Add":" return split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r);"},{"Add":" } else {"},{"Add":" return split_unsized::<_, _, _, L>(txn, page, mutable, u, k0, v0, l, r);"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn split<'a, T: AllocPage, K: Representable, V: Representable, L: Alloc>("},{"Add":" txn: &mut T,"},{"Add":" page: crate::Page,"},{"Add":" mutable: bool,"},{"Add":" size: usize,"},{"Add":" u: usize,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":") -> Result, T::Error> {"},{"Add":" let left;"},{"Add":" let right = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(right);"},{"Add":" let hdr = &*header(&page);"},{"Add":""},{"Add":" let page_is_dirty = if hdr.is_dirty() { 1 } else { 0 };"},{"Add":""},{"Add":" let n = hdr.n() + 1;"},{"Add":" let s = L::offset_slice::(page);"},{"Add":" let k = n / 2;"},{"Add":" debug!(\"s = {:?}\", s);"},{"Add":" let (s0, s1) = s.split_at(k as usize);"},{"Add":" debug!(\"s0 = {:?} s1 = {:?}\", s0, s1);"},{"Add":" let (split_key, 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":" let (s1a, s1b) = s1.split_at(1);"},{"Add":" let (k, v, r) = L::kv(page, s1a.first::());"},{"Add":" (&*k, &*v, r, s1b)"},{"Add":" };"},{"Add":" let mut freed = 0;"},{"Add":" if mutable && hdr.is_dirty() && u >= k as usize {"},{"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":" let hdr = &mut *header_mut(MutPage(page));"},{"Add":" left = MutPage(page);"},{"Add":" hdr.set_n(k);"},{"Add":" hdr.decr((n - 1 - k) as usize * size);"},{"Add":" } else {"},{"Add":" left = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(left);"},{"Add":" if u < k as usize {"},{"Add":" let mut n = 0;"},{"Add":" let hdr = &mut *header_mut(left);"},{"Add":" let (s0a, s0b) = s1.split_at(u as usize - k as usize);"},{"Add":" clone::(hdr, page, left, s0a, &mut n);"},{"Add":" alloc::(hdr, left, k0, v0, r, l, &mut n);"},{"Add":" clone::(hdr, page, left, s0b, &mut n);"},{"Add":" let hdr = &mut *header_mut(right);"},{"Add":" let mut n = 0;"},{"Add":" L::set_right_child(right, -1, mid_child);"},{"Add":" clone::(hdr, page, right, s1, &mut n);"},{"Add":" return Ok(Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed: page.offset | page_is_dirty,"},{"Add":" });"},{"Add":" } else {"},{"Add":" let hdr = &mut *header_mut(left);"},{"Add":" let mut n = 0;"},{"Add":" clone::(hdr, page, left, s0, &mut n);"},{"Add":" freed = page.offset | page_is_dirty"},{"Add":" }"},{"Add":" }"},{"Add":" // If we are here, u > k, i.e. the insertion is in the right-hand"},{"Add":" // side of the split."},{"Add":" let hdr = &mut *header_mut(right);"},{"Add":" let mut n = 0;"},{"Add":" let kk = u as usize - k as usize;"},{"Add":" let (s1a, s1b) = if kk < s1.len() {"},{"Add":" debug!(\"s1 = {:?}, kk = {:?}\", s1, kk);"},{"Add":" s1.split_at(kk)"},{"Add":" } else {"},{"Add":" (s1, Offsets::Slice(&[][..]))"},{"Add":" };"},{"Add":" debug!(\"s1a = {:?} s1b = {:?}\", s1a, s1b);"},{"Add":" L::set_right_child(right, -1, mid_child);"},{"Add":" debug!(\"clone {:?} {:?}\", n, s1a);"},{"Add":" clone::(hdr, page, right, s1a, &mut n);"},{"Add":" debug!(\"alloc {:?}\", n);"},{"Add":" alloc::(hdr, right, k0, v0, l, r, &mut n);"},{"Add":" debug!(\"clone 2 {:?}\", n);"},{"Add":" clone::(hdr, page, right, s1b, &mut n);"},{"Add":" Ok(Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed,"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"unsafe fn split_unsized<'a, T: AllocPage, K: Representable, V: Representable, L: Alloc>("},{"Add":" _txn: &mut T,"},{"Add":" _page: crate::Page,"},{"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":" unimplemented!()"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"mod.rs","metadata":420},"context":[{"change":0,"pos":3438}],"contents":[{"Add":"use crate::*;"},{"Add":"pub mod cursor;"},{"Add":"mod del;"},{"Add":"pub use del::*;"},{"Add":"mod put;"},{"Add":"pub use put::*;"},{"Add":"pub mod page;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Ok {"},{"Add":" page: MutPage,"},{"Add":" freed: u64,"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub enum Put<'a, K, V> {"},{"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":"pub trait BTreePage, V: Representable> {"},{"Add":" type Cursor: Clone + Copy + core::fmt::Debug;"},{"Add":" fn is_dirty(page: Page) -> bool;"},{"Add":" fn first_cursor(p: &Page) -> Self::Cursor;"},{"Add":" fn last_cursor(p: &Page) -> Self::Cursor;"},{"Add":" fn next<'b>(p: &Page, c: &mut Self::Cursor) -> Option<(&'b mut K, &'b mut V, u64)> {"},{"Add":" unsafe {"},{"Add":" if let Some((k, v, r)) = Self::current(p, c) {"},{"Add":" Self::move_next(p, c);"},{"Add":" Some((&mut *k, &mut *v, r))"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" fn move_next<'b>(p: &Page, c: &mut Self::Cursor) -> bool;"},{"Add":" unsafe fn unchecked_current(p: &Page, c: &Self::Cursor) -> (*mut K, *mut V, u64);"},{"Add":" unsafe fn current(p: &Page, c: &Self::Cursor) -> Option<(*mut K, *mut V, u64)> {"},{"Add":" if Self::is_empty(p, c) {"},{"Add":" None"},{"Add":" } else {"},{"Add":" Some(Self::unchecked_current(p, c))"},{"Add":" }"},{"Add":" }"},{"Add":" unsafe fn unchecked_current_ptr(p: &Page, c: &Self::Cursor) -> *mut u8;"},{"Add":" fn current_size(p: &Page, c: &Self::Cursor) -> usize;"},{"Add":" fn left_child(p: &Page, c: &Self::Cursor) -> u64;"},{"Add":" fn right_child(p: &Page, c: &Self::Cursor) -> u64;"},{"Add":" fn set_cursor<'a>("},{"Add":" txn: &T,"},{"Add":" page: &Page,"},{"Add":" c: &mut Self::Cursor,"},{"Add":" k0: &K,"},{"Add":" v0: Option<&V>,"},{"Add":" ) -> Result<(&'a mut K, &'a mut V, u64), usize>;"},{"Add":" fn split_at(p: &Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor);"},{"Add":" fn is_empty(p: &Page, c: &Self::Cursor) -> bool;"},{"Add":"}"},{"Add":""},{"Add":"pub struct PageIterator<"},{"Add":" 'a,"},{"Add":" T: LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreePage,"},{"Add":"> {"},{"Add":" cursor: P::Cursor,"},{"Add":" page: &'a Page,"},{"Add":"}"},{"Add":""},{"Add":"impl<"},{"Add":" 'a,"},{"Add":" T: LoadPage,"},{"Add":" K: Representable + 'a,"},{"Add":" V: Representable + 'a,"},{"Add":" P: BTreePage,"},{"Add":" > Iterator for PageIterator<'a, T, K, V, P>"},{"Add":"{"},{"Add":" type Item = (&'a mut K, &'a mut V, u64);"},{"Add":" fn next(&mut self) -> Option {"},{"Add":" P::next(self.page, &mut self.cursor)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub trait BTreeMutPage, V: Representable>:"},{"Add":" BTreePage + Sized"},{"Add":"{"},{"Add":" fn init(page: MutPage);"},{"Add":" fn clean(page: MutPage);"},{"Add":" fn put<'a>("},{"Add":" txn: &mut T,"},{"Add":" page: Page,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" ) -> Result, T::Error>;"},{"Add":""},{"Add":" fn update_left_child("},{"Add":" txn: &mut T,"},{"Add":" page: Page,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" r: u64,"},{"Add":" ) -> Result;"},{"Add":""},{"Add":" fn del(txn: &mut T, page: Page, c: &Self::Cursor, l: u64) -> Result;"},{"Add":""},{"Add":" fn replace<'a>("},{"Add":" txn: &mut T,"},{"Add":" page: Page,"},{"Add":" mutable: bool,"},{"Add":" c: &Self::Cursor,"},{"Add":" k0: &'a K,"},{"Add":" v0: &'a V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" // TODO: optimise this for page::Page, since this moves"},{"Add":" // all the offsets twice in this case."},{"Add":" let new = Self::del(txn, page, c, l)?;"},{"Add":" Self::put(txn, new.0, mutable, c, k0, v0, l, r)"},{"Add":" }"},{"Add":""},{"Add":" fn merge_or_rebalance<'a>("},{"Add":" txn: &mut T,"},{"Add":" m: &mut Concat,"},{"Add":" ) -> Result, T::Error>;"},{"Add":""},{"Add":" fn modify<'a>("},{"Add":" txn: &mut T,"},{"Add":" m: &mut ModifiedPage,"},{"Add":" ) -> Result, T::Error> {"},{"Add":" unsafe {"},{"Add":" if let Some((k, v, r)) = m.ins {"},{"Add":" if m.skip_first {"},{"Add":" Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)"},{"Add":" } else {"},{"Add":" Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)"},{"Add":" }"},{"Add":" } else {"},{"Add":" let page = Self::del(txn, m.page, &m.c1, m.l)?;"},{"Add":" Ok(Put::Ok(Ok {"},{"Add":" page,"},{"Add":" freed: if page.0.offset != m.page.offset {"},{"Add":" m.page.offset"},{"Add":" } else {"},{"Add":" 0"},{"Add":" },"},{"Add":" }))"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn size(m: &ModifiedPage) -> usize;"},{"Add":"}"},{"Add":""},{"Add":"pub enum Op<'a, T, K: Representable, V: Representable> {"},{"Add":" Merged {"},{"Add":" page: MutPage,"},{"Add":" freed: [u64; 2],"},{"Add":" marker: core::marker::PhantomData,"},{"Add":" },"},{"Add":" Rebalanced {"},{"Add":" k: *mut K,"},{"Add":" v: *mut V,"},{"Add":" l: u64,"},{"Add":" r: u64,"},{"Add":" freed: [u64; 2],"},{"Add":" },"},{"Add":" Put(Put<'a, K, V>),"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"pub struct ModifiedPage<"},{"Add":" T: LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreePage,"},{"Add":"> {"},{"Add":" pub page: Page,"},{"Add":" /// Whether the page can be written to (useful for RC)."},{"Add":" pub mutable: bool,"},{"Add":" // Start copying c0 (keep `page`'s left child)."},{"Add":" pub c0: P::Cursor,"},{"Add":" // Replace the right child of c0's last element with `l`."},{"Add":" pub l: u64,"},{"Add":" // Possibly insert a new binding."},{"Add":" pub ins: Option<(*const K, *const V, u64)>,"},{"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":"}"},{"Add":""},{"Add":"impl, V: Representable, P: BTreePage>"},{"Add":" ModifiedPage"},{"Add":"{"},{"Add":" pub fn single_child(&self) -> Option {"},{"Add":" let mut c1 = self.c1.clone();"},{"Add":" if self.skip_first {"},{"Add":" P::move_next(&self.page, &mut c1);"},{"Add":" }"},{"Add":" if P::is_empty(&self.page, &self.c0) && self.ins.is_none() && P::is_empty(&self.page, &c1) {"},{"Add":" Some(self.l)"},{"Add":" } else {"},{"Add":" None"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Concat<'a, T: LoadPage, K: Representable, V: Representable, P: BTreePage>"},{"Add":"{"},{"Add":" pub mid: (*mut K, *mut V),"},{"Add":" pub modified: &'a mut ModifiedPage,"},{"Add":" pub other: Page,"},{"Add":" // Is the modified field on the left or on the right of the"},{"Add":" // concatenation?"},{"Add":" pub mod_is_left: bool,"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Db, V: Representable, P: BTreePage> {"},{"Add":" pub db: Page,"},{"Add":" pub marker: core::marker::PhantomData<(T, K, V, P)>,"},{"Add":"}"},{"Add":""},{"Add":"pub fn create_db<"},{"Add":" T: AllocPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreeMutPage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":") -> Result, T::Error> {"},{"Add":" let page = txn.alloc_page()?;"},{"Add":" P::init(page);"},{"Add":" Ok(Db {"},{"Add":" db: page.0,"},{"Add":" marker: core::marker::PhantomData,"},{"Add":" })"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"del.rs","metadata":420},"context":[{"change":0,"pos":3438}],"contents":[{"Add":"// Copyright 2015 Pierre-Étienne Meunier and Florent Becker. See the"},{"Add":"// COPYRIGHT file at the top-level directory of this distribution and"},{"Add":"// at http://pijul.org/COPYRIGHT."},{"Add":"//"},{"Add":"// Licensed under the Apache License, Version 2.0 or the MIT license"},{"Add":"// , at your"},{"Add":"// option. This file may not be copied, modified, or distributed"},{"Add":"// except according to those terms."},{"Add":"use super::cursor::*;"},{"Add":"use super::*;"},{"Add":"use crate::LoadPage;"},{"Add":"use core::mem::MaybeUninit;"},{"Add":""},{"Add":"/// If `value` is `None`, delete one of the bindings associated to"},{"Add":"/// `key` from the database (without any specific"},{"Add":"/// preference). Else, delete the specified binding if present."},{"Add":"pub fn del<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreeMutPage + core::fmt::Debug,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db,"},{"Add":" key: &K,"},{"Add":" value: Option<&V>,"},{"Add":") -> Result {"},{"Add":" let mut cursor = Cursor::new(db);"},{"Add":" let found = cursor.set(txn, Some((key, value)))?;"},{"Add":" if found.is_none() {"},{"Add":" return Ok(false);"},{"Add":" }"},{"Add":" del_at_cursor(txn, db, &mut cursor)"},{"Add":"}"},{"Add":""},{"Add":"pub fn del_at_cursor<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreeMutPage + core::fmt::Debug,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" db: &mut Db,"},{"Add":" cursor: &mut Cursor,"},{"Add":") -> Result {"},{"Add":" let p0 = cursor.pointer;"},{"Add":""},{"Add":" // Find the leftmost page in the right subtree, that is where"},{"Add":" // the \"replacement\" is."},{"Add":" find_min(txn, cursor)?;"},{"Add":""},{"Add":" // Mark the replacement for deletion in the leaf. This is all"},{"Add":" // lazy, so we don't do anything for now, in order to avoid"},{"Add":" // duplicate work in case the page can be merged or"},{"Add":" // rebalanced."},{"Add":" let ref mut curs0 = unsafe { cursor.stack[cursor.pointer].assume_init() };"},{"Add":" let (c0, c1) = P::split_at(&curs0.page, curs0.cursor.as_ref().unwrap());"},{"Add":" let mut last_op = ModifiedPage {"},{"Add":" page: curs0.page,"},{"Add":" mutable: cursor.pointer < cursor.first_rc_level,"},{"Add":" c0,"},{"Add":" l: 0,"},{"Add":" ins: None,"},{"Add":" c1,"},{"Add":" skip_first: true,"},{"Add":" };"},{"Add":" if cursor.pointer == cursor.first_rc_level {"},{"Add":" txn.decr_rc(curs0.page.offset)?;"},{"Add":" }"},{"Add":" if cursor.pointer >= cursor.first_rc_level {"},{"Add":" let mut c0 = c0.clone();"},{"Add":" let mut c1 = c1.clone();"},{"Add":" P::move_next(&curs0.page, &mut c1);"},{"Add":" while let Some((k, v, _)) ="},{"Add":" P::next(&curs0.page, &mut c0).or_else(|| P::next(&curs0.page, &mut c1))"},{"Add":" {"},{"Add":" for o in k.page_offsets().chain(v.page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" if p0 < cursor.pointer && cursor.pointer >= cursor.first_rc_level {"},{"Add":" // increase the RC of the replacement."},{"Add":" unsafe {"},{"Add":" let (k, v, _) = P::unchecked_current(&curs0.page, &c0);"},{"Add":" for o in (&*k).page_offsets().chain((&*v).page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" let mut free = [[0, 0]; N_CURSORS];"},{"Add":""},{"Add":" // Then, climb up the stack, and perform the lazy operations."},{"Add":" cursor.pointer -= 1;"},{"Add":" while cursor.pointer > 0 {"},{"Add":" // Compute the need for merge/rebalancing"},{"Add":" let ref curs = cursor.current();"},{"Add":" let c = curs.cursor.as_ref().unwrap();"},{"Add":" let mut concat = concat(txn, &cursor, &curs0, p0, &mut last_op)?;"},{"Add":" let (c0, c1) = P::split_at(&curs.page, c);"},{"Add":" match P::merge_or_rebalance(txn, &mut concat)? {"},{"Add":" Op::Merged {"},{"Add":" page,"},{"Add":" freed,"},{"Add":" marker: _,"},{"Add":" } => {"},{"Add":" last_op = ModifiedPage {"},{"Add":" page: curs.page,"},{"Add":" mutable: cursor.pointer < cursor.first_rc_level,"},{"Add":" c0,"},{"Add":" l: page.0.offset,"},{"Add":" ins: None,"},{"Add":" c1,"},{"Add":" skip_first: true,"},{"Add":" };"},{"Add":" if cursor.pointer < cursor.first_rc_level {"},{"Add":" free[cursor.pointer] = freed;"},{"Add":" } else {"},{"Add":" if cursor.pointer == cursor.first_rc_level {"},{"Add":" txn.decr_rc(curs.page.offset)?;"},{"Add":" }"},{"Add":" modify_rc(txn, &last_op)?;"},{"Add":" }"},{"Add":" }"},{"Add":" Op::Rebalanced { k, v, l, r, freed } => {"},{"Add":" if cursor.pointer < cursor.first_rc_level {"},{"Add":" free[cursor.pointer] = freed;"},{"Add":" }"},{"Add":" last_op = ModifiedPage {"},{"Add":" page: curs.page,"},{"Add":" mutable: cursor.pointer < cursor.first_rc_level,"},{"Add":" c0,"},{"Add":" l,"},{"Add":" ins: Some((k, v, r)),"},{"Add":" c1,"},{"Add":" skip_first: true,"},{"Add":" };"},{"Add":" if cursor.pointer < cursor.first_rc_level {"},{"Add":" free[cursor.pointer] = freed;"},{"Add":" } else {"},{"Add":" if cursor.pointer == cursor.first_rc_level {"},{"Add":" txn.decr_rc(curs.page.offset)?;"},{"Add":" }"},{"Add":" modify_rc(txn, &last_op)?;"},{"Add":" }"},{"Add":" }"},{"Add":" Op::Put(Put::Ok(Ok { page, freed })) => {"},{"Add":" last_op = ModifiedPage {"},{"Add":" page: curs.page,"},{"Add":" mutable: cursor.pointer < cursor.first_rc_level,"},{"Add":" c0,"},{"Add":" l: page.0.offset,"},{"Add":" ins: None,"},{"Add":" c1,"},{"Add":" skip_first: false,"},{"Add":" };"},{"Add":" if cursor.pointer < cursor.first_rc_level {"},{"Add":" free[cursor.pointer][0] = freed;"},{"Add":" } else {"},{"Add":" if cursor.pointer == cursor.first_rc_level {"},{"Add":" txn.decr_rc(curs.page.offset)?;"},{"Add":" }"},{"Add":" modify_rc(txn, &last_op)?;"},{"Add":" }"},{"Add":" }"},{"Add":" Op::Put(Put::Split {"},{"Add":" left,"},{"Add":" right,"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" freed,"},{"Add":" }) => {"},{"Add":" last_op = ModifiedPage {"},{"Add":" page: curs.page,"},{"Add":" mutable: cursor.pointer < cursor.first_rc_level,"},{"Add":" c0,"},{"Add":" l: left.0.offset,"},{"Add":" ins: Some((split_key, split_value, right.0.offset)),"},{"Add":" c1,"},{"Add":" skip_first: false,"},{"Add":" };"},{"Add":" if cursor.pointer < cursor.first_rc_level {"},{"Add":" free[cursor.pointer][0] = freed;"},{"Add":" } else {"},{"Add":" if cursor.pointer == cursor.first_rc_level {"},{"Add":" txn.decr_rc(curs.page.offset)?;"},{"Add":" }"},{"Add":" modify_rc(txn, &last_op)?;"},{"Add":" }"},{"Add":" if cursor.pointer + 1 >= cursor.first_rc_level {"},{"Add":" for o in split_key.page_offsets().chain(split_value.page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" cursor.pointer -= 1;"},{"Add":" }"},{"Add":" // The root was merged or rebalanced."},{"Add":" if let Some(d) = last_op.single_child() {"},{"Add":" db.db = txn.load_page(d)?"},{"Add":" } else {"},{"Add":" match P::modify(txn, &mut last_op)? {"},{"Add":" Put::Ok(Ok { page, freed }) => {"},{"Add":" free[0][0] = freed;"},{"Add":" db.db = page.0"},{"Add":" }"},{"Add":" Put::Split {"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left,"},{"Add":" right,"},{"Add":" freed,"},{"Add":" } => {"},{"Add":" free[0][0] = freed;"},{"Add":" let page = txn.alloc_page()?;"},{"Add":" P::init(page);"},{"Add":" P::put("},{"Add":" txn,"},{"Add":" page.0,"},{"Add":" true,"},{"Add":" &P::first_cursor(&page.0),"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" )?;"},{"Add":" if cursor.first_rc_level <= 1 {"},{"Add":" for o in split_key.page_offsets().chain(split_value.page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" }"},{"Add":" db.db = page.0"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" for p in free.iter() {"},{"Add":" if p[0] & 1 == 1 {"},{"Add":" txn.decr_rc_owned(p[0] ^ 1)?"},{"Add":" } else if p[0] > 0 {"},{"Add":" txn.decr_rc_owned(p[0])?"},{"Add":" }"},{"Add":" if p[1] & 1 == 1 {"},{"Add":" txn.decr_rc_owned(p[1] ^ 1)?"},{"Add":" } else if p[1] > 0 {"},{"Add":" txn.decr_rc_owned(p[1])?"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(true)"},{"Add":"}"},{"Add":""},{"Add":"fn find_min<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreeMutPage + core::fmt::Debug,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &mut Cursor,"},{"Add":") -> Result<(), T::Error> {"},{"Add":" let cur = cursor.current();"},{"Add":" let mut left_page = P::right_child(&cur.page, cur.cursor.as_ref().unwrap());"},{"Add":" while left_page > 0 {"},{"Add":" cursor.pointer += 1;"},{"Add":" let page = txn.load_page(left_page)?;"},{"Add":" let curs = P::first_cursor(&page);"},{"Add":" left_page = P::left_child(&page, &curs);"},{"Add":" cursor.stack[cursor.pointer] = MaybeUninit::new(PageCursor {"},{"Add":" page,"},{"Add":" cursor: Some(curs),"},{"Add":" });"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"},{"Add":""},{"Add":"fn concat<"},{"Add":" 'a,"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreeMutPage + core::fmt::Debug,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" cursor: &Cursor,"},{"Add":" curs0: &PageCursor,"},{"Add":" p0: usize,"},{"Add":" last_op: &'a mut ModifiedPage,"},{"Add":") -> Result, T::Error> {"},{"Add":" let ref curs = cursor.current();"},{"Add":" let c = curs.cursor.as_ref().unwrap();"},{"Add":" if cursor.pointer == p0 {"},{"Add":" let other = txn.load_page(P::left_child(&curs.page, c))?;"},{"Add":" let (k, v, _) ="},{"Add":" unsafe { P::unchecked_current(&curs0.page, curs0.cursor.as_ref().unwrap()) };"},{"Add":" Ok(Concat {"},{"Add":" modified: last_op,"},{"Add":" mid: (k, v),"},{"Add":" other,"},{"Add":" mod_is_left: false,"},{"Add":" })"},{"Add":" } else {"},{"Add":" let (k, v, r) = unsafe { P::unchecked_current(&curs.page, c) };"},{"Add":" let other = txn.load_page(r)?;"},{"Add":" Ok(Concat {"},{"Add":" modified: last_op,"},{"Add":" mid: (k, v),"},{"Add":" other,"},{"Add":" mod_is_left: true,"},{"Add":" })"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"fn modify_rc<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Representable,"},{"Add":" V: Representable,"},{"Add":" P: BTreePage,"},{"Add":">("},{"Add":" txn: &mut T,"},{"Add":" m: &ModifiedPage,"},{"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, &c0);"},{"Add":" while let Some((k, v, r)) = P::next(&m.page, &mut c0) {"},{"Add":" for o in k.page_offsets().chain(v.page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" txn.incr_rc(left)?;"},{"Add":" left = r;"},{"Add":" }"},{"Add":" if m.skip_first {"},{"Add":" P::move_next(&m.page, &mut c1);"},{"Add":" } else {"},{"Add":" txn.incr_rc(left)?;"},{"Add":" }"},{"Add":" while let Some((k, v, r)) = P::next(&m.page, &mut c1) {"},{"Add":" for o in k.page_offsets().chain(v.page_offsets()) {"},{"Add":" txn.incr_rc(o)?;"},{"Add":" }"},{"Add":" txn.incr_rc(r)?;"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"cursor.rs","metadata":420},"context":[{"change":0,"pos":3438}],"contents":[{"Add":"use super::*;"},{"Add":"use crate::{LoadPage, Page};"},{"Add":"use core::mem::MaybeUninit;"},{"Add":"use log::*;"},{"Add":""},{"Add":"#[doc(hidden)]"},{"Add":"#[derive(Debug)]"},{"Add":"pub struct PageCursor, V: Representable, P: BTreePage>"},{"Add":"{"},{"Add":" pub page: Page,"},{"Add":" pub cursor: Option,"},{"Add":"}"},{"Add":""},{"Add":"impl, V: Representable, P: BTreePage> Clone"},{"Add":" for PageCursor"},{"Add":"{"},{"Add":" fn clone(&self) -> Self {"},{"Add":" PageCursor {"},{"Add":" page: self.page,"},{"Add":" cursor: self.cursor.clone(),"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":"impl, V: Representable, P: BTreePage> Copy"},{"Add":" for PageCursor"},{"Add":"{"},{"Add":"}"},{"Add":""},{"Add":"// This is 1 + the maximal depth of a tree. Cursors start at 1 to"},{"Add":"// allow for splitting the root on an insertion."},{"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 4 elements, the arity is at"},{"Add":"// least 5, except for the root. Since 5^23 is the smallest power of 5"},{"Add":"// larger than 2^52, the maximum depth is 24, and we add the extra"},{"Add":"// room to allow for splitting."},{"Add":"pub(crate) const N_CURSORS: usize = 25;"},{"Add":""},{"Add":"#[derive(Debug, Clone)]"},{"Add":"/// A position in a database (mostly for internal use)."},{"Add":"pub struct Cursor, V: Representable, P: BTreePage> {"},{"Add":" pub stack: [core::mem::MaybeUninit>; N_CURSORS],"},{"Add":" pub first_rc_level: usize,"},{"Add":" pub pointer: usize,"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, T: LoadPage, K: Representable, V: Representable, P: BTreePage>"},{"Add":" Cursor"},{"Add":"{"},{"Add":" pub fn new(db: &Db) -> Self {"},{"Add":" let mut stack = [core::mem::MaybeUninit::uninit(); N_CURSORS];"},{"Add":" stack[1] = MaybeUninit::new(PageCursor {"},{"Add":" page: db.db,"},{"Add":" cursor: None,"},{"Add":" });"},{"Add":" Cursor {"},{"Add":" stack,"},{"Add":" first_rc_level: N_CURSORS,"},{"Add":" pointer: 1,"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, T: LoadPage, K: Representable, V: Representable, P: BTreePage>"},{"Add":" Cursor"},{"Add":"{"},{"Add":" pub fn current(&self) -> &PageCursor {"},{"Add":" unsafe { &*self.stack[self.pointer].as_ptr() }"},{"Add":" }"},{"Add":""},{"Add":" pub fn set("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" k: Option<(&K, Option<&V>)>,"},{"Add":" ) -> Result, T::Error> {"},{"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_matching_page = 0;"},{"Add":" let mut last_match = None;"},{"Add":" loop {"},{"Add":" let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };"},{"Add":" let page = current.page;"},{"Add":" if self.first_rc_level >= N_CURSORS && txn.rc(page.offset)? >= 2 {"},{"Add":" self.first_rc_level = self.pointer"},{"Add":" }"},{"Add":" if current.cursor.is_none() {"},{"Add":" current.cursor = Some(P::first_cursor(&page));"},{"Add":" }"},{"Add":" let cursor = current.cursor.as_mut().unwrap();"},{"Add":" if let Some((k, v)) = k {"},{"Add":" if let Ok((kk, vv, _)) = P::set_cursor(txn, &page, cursor, k, v) {"},{"Add":" if v.is_some() {"},{"Add":" return Ok(Some((kk, vv)));"},{"Add":" }"},{"Add":" last_match = Some((kk, vv));"},{"Add":" last_matching_page = self.pointer"},{"Add":" }"},{"Add":" }"},{"Add":" let next_page = P::left_child(&page, cursor);"},{"Add":" debug!(\"next = {:?}\", next_page);"},{"Add":" if next_page > 0 {"},{"Add":" self.pointer += 1;"},{"Add":" self.stack[self.pointer] = MaybeUninit::new(PageCursor {"},{"Add":" page: txn.load_page(next_page)?,"},{"Add":" cursor: None,"},{"Add":" });"},{"Add":" } else {"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" if last_matching_page > 0 {"},{"Add":" self.pointer = last_matching_page;"},{"Add":" Ok(last_match)"},{"Add":" } else {"},{"Add":" Ok(None)"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" pub fn set_last(&mut self, txn: &'a T) -> Result, T::Error> {"},{"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;"},{"Add":" loop {"},{"Add":" let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };"},{"Add":" if self.first_rc_level >= N_CURSORS && txn.rc(current.page.offset)? >= 2 {"},{"Add":" self.first_rc_level = self.pointer"},{"Add":" }"},{"Add":" if current.cursor.is_none() {"},{"Add":" current.cursor = Some(P::last_cursor(¤t.page));"},{"Add":" }"},{"Add":" let cursor = current.cursor.as_mut().unwrap();"},{"Add":" let (k, v, r) = unsafe { P::unchecked_current(¤t.page, cursor) };"},{"Add":" last_match = Some((k, v));"},{"Add":" if r > 0 {"},{"Add":" self.pointer += 1;"},{"Add":" self.stack[self.pointer] = MaybeUninit::new(PageCursor {"},{"Add":" page: txn.load_page(r)?,"},{"Add":" cursor: None,"},{"Add":" })"},{"Add":" } else {"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(last_match.map(|(k, v)| unsafe { (&*k, &*v) }))"},{"Add":" }"},{"Add":""},{"Add":" pub fn next("},{"Add":" &mut self,"},{"Add":" txn: &'a mut L,"},{"Add":" ) -> Result, L::Error> {"},{"Add":" loop {"},{"Add":" if self.pointer == 0 {"},{"Add":" return Ok(None);"},{"Add":" } else {"},{"Add":" let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };"},{"Add":" if let Some(ref mut c) = current.cursor {"},{"Add":" // We're inside the page, and have already"},{"Add":" // processed the left child of the current page"},{"Add":" // cursor."},{"Add":" if let Some((k, v, r)) = P::next(¤t.page, c) {"},{"Add":" if r > 0 {"},{"Add":" self.pointer += 1;"},{"Add":" self.stack[self.pointer] = MaybeUninit::new(PageCursor {"},{"Add":" page: txn.load_page(r)?,"},{"Add":" cursor: None,"},{"Add":" })"},{"Add":" }"},{"Add":" return Ok(Some((&mut *k, &mut *v)));"},{"Add":" } else if self.pointer > 1 {"},{"Add":" self.pointer -= 1"},{"Add":" } else {"},{"Add":" return Ok(None);"},{"Add":" }"},{"Add":" } else {"},{"Add":" current.cursor = Some(P::first_cursor(¤t.page));"},{"Add":" // First element of a page (not a binding)."},{"Add":" let cursor = current.cursor.as_ref().unwrap();"},{"Add":" let left = P::left_child(¤t.page, cursor);"},{"Add":" debug!(\"left = {:?}\", left);"},{"Add":" // Then visit the right child (if any), i.e. push."},{"Add":" if left != 0 {"},{"Add":" self.pointer += 1;"},{"Add":" self.stack[self.pointer] = MaybeUninit::new(PageCursor {"},{"Add":" page: txn.load_page(left)?,"},{"Add":" cursor: None,"},{"Add":" })"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"Cargo.toml","metadata":420},"context":[{"change":0,"pos":17}],"contents":[{"Add":"[package]"},{"Add":"name = \"sanakirja-core\""},{"Add":"version = \"0.1.0\""},{"Add":"authors = [\"pe\"]"},{"Add":"edition = \"2018\""},{"Add":""},{"Add":"# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html"},{"Add":""},{"Add":"[dependencies]"},{"Add":"log = \"*\""}]}},{"FileAdd":{"meta":{"basename":"sanakirja","metadata":1005},"context":[{"change":1,"pos":0}],"contents":[]}},{"FileAdd":{"meta":{"basename":"src","metadata":1005},"context":[{"change":0,"pos":71001}],"contents":[]}},{"FileAdd":{"meta":{"basename":"parallel_benchmark.rs","metadata":420},"context":[{"change":0,"pos":71008}],"contents":[{"Add":"use sanakirja_core::*;"},{"Add":"use std::sync::atomic::{AtomicUsize, Ordering};"},{"Add":"use std::sync::Arc;"},{"Add":""},{"Add":"pub fn parallel_benchmark() {"},{"Add":" let mut stack: [[u64; 512]; N] = [TESTPAGE; N];"},{"Add":" let stack: [SafePage; N] = ["},{"Add":" SafePage::from_buf(&mut stack[0], 4096),"},{"Add":" SafePage::from_buf(&mut stack[1], 4096 * 2),"},{"Add":" SafePage::from_buf(&mut stack[2], 4096 * 3),"},{"Add":" SafePage::from_buf(&mut stack[3], 4096 * 4),"},{"Add":" /*SafePage::from_buf(&mut stack[4], 4096 * 5),"},{"Add":" SafePage::from_buf(&mut stack[5], 4096 * 6),"},{"Add":" SafePage::from_buf(&mut stack[6], 4096 * 7),"},{"Add":" SafePage::from_buf(&mut stack[7], 4096 * 8),"},{"Add":" SafePage::from_buf(&mut stack[8], 4096 * 9),"},{"Add":" SafePage::from_buf(&mut stack[9], 4096 * 10),"},{"Add":" SafePage::from_buf(&mut stack[10], 4096 * 11),"},{"Add":" SafePage::from_buf(&mut stack[11], 4096 * 12),*/"},{"Add":" ];"},{"Add":""},{"Add":" let pointer_clone = Arc::new(AtomicUsize::new(0));"},{"Add":" let result = Arc::new(AtomicUsize::new(0));"},{"Add":" ["},{"Add":" start_thread(pointer_clone.clone(), result.clone(), stack.clone()),"},{"Add":" start_thread(pointer_clone.clone(), result.clone(), stack.clone()),"},{"Add":" start_thread(pointer_clone.clone(), result.clone(), stack.clone()),"},{"Add":" start_thread(pointer_clone.clone(), result.clone(), stack.clone()),"},{"Add":" ];"},{"Add":""},{"Add":" // Wait for the other thread to release the lock"},{"Add":" while result.load(Ordering::SeqCst) != 0 {}"},{"Add":""},{"Add":" let mut total = std::time::Duration::from_secs(0);"},{"Add":" let mut total_seq = std::time::Duration::from_secs(0);"},{"Add":" for _ in 0..100_000 {"},{"Add":" let time = std::time::SystemTime::now();"},{"Add":" pointer_clone.store(4, Ordering::Release);"},{"Add":" result.store(4, Ordering::Release);"},{"Add":" while result.load(Ordering::Acquire) > 0 {"},{"Add":" std::hint::spin_loop();"},{"Add":" }"},{"Add":" total += time.elapsed().unwrap();"},{"Add":""},{"Add":" let time = std::time::SystemTime::now();"},{"Add":" for &s in stack.iter() {"},{"Add":" let s: MutPage = s.into();"},{"Add":" let header_size = 16;"},{"Add":" let size = 8;"},{"Add":" for off in 0..500 {"},{"Add":" unsafe {"},{"Add":" let ptr = (TESTPAGE.as_ptr() as *const u8).add(header_size + off * size);"},{"Add":" let new_ptr = s.0.data.add(header_size + off * size);"},{"Add":" std::ptr::copy_nonoverlapping(ptr, new_ptr, size);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" total_seq += time.elapsed().unwrap();"},{"Add":" }"},{"Add":" println!(\"{:?} {:?}\", total, total_seq);"},{"Add":"}"},{"Add":""},{"Add":"#[derive(Debug, Clone, Copy)]"},{"Add":"struct SafePage {"},{"Add":" data: *mut u8,"},{"Add":" offset: u64,"},{"Add":"}"},{"Add":""},{"Add":"impl From for SafePage {"},{"Add":" fn from(m: MutPage) -> Self {"},{"Add":" SafePage {"},{"Add":" data: m.0.data,"},{"Add":" offset: m.0.offset,"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl From for MutPage {"},{"Add":" fn from(m: SafePage) -> Self {"},{"Add":" MutPage(Page {"},{"Add":" data: m.data,"},{"Add":" offset: m.offset,"},{"Add":" })"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl SafePage {"},{"Add":" fn from_buf(b: &mut [u64], offset: u64) -> Self {"},{"Add":" SafePage {"},{"Add":" data: b.as_mut_ptr() as *mut u8,"},{"Add":" offset,"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"unsafe impl Sync for SafePage {}"},{"Add":"unsafe impl Send for SafePage {}"},{"Add":""},{"Add":"fn start_thread("},{"Add":" n: Arc,"},{"Add":" result: Arc,"},{"Add":" stack: [SafePage; N],"},{"Add":") -> std::thread::JoinHandle<()> {"},{"Add":" std::thread::spawn(move || loop {"},{"Add":" let mut current = 0;"},{"Add":" while current == 0 {"},{"Add":" current = n.load(Ordering::Acquire);"},{"Add":" std::hint::spin_loop();"},{"Add":" }"},{"Add":" while current > 0 {"},{"Add":" let mut cur = n.compare_and_swap(current, current - 1, Ordering::Acquire);"},{"Add":" if cur != current {"},{"Add":" current -= 1;"},{"Add":" continue;"},{"Add":" }"},{"Add":" cur -= 1;"},{"Add":" let s: MutPage = stack[cur].into();"},{"Add":" let header_size = 16;"},{"Add":" let size = 8;"},{"Add":" for off in 0..500 {"},{"Add":" unsafe {"},{"Add":" let ptr = (TESTPAGE.as_ptr() as *const u8).add(header_size + off * size);"},{"Add":" let new_ptr = s.0.data.add(header_size + off * size);"},{"Add":" std::ptr::copy_nonoverlapping(ptr, new_ptr, size);"},{"Add":" }"},{"Add":" }"},{"Add":" result.fetch_sub(1, Ordering::Release);"},{"Add":" current = cur;"},{"Add":" }"},{"Add":" })"},{"Add":"}"},{"Add":""},{"Add":"const N: usize = 4;"},{"Add":""},{"Add":"const TESTPAGE: [u64; 512] = ["},{"Add":" 268435955, 3992, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,"},{"Add":" 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,"},{"Add":" 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69,"},{"Add":" 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93,"},{"Add":" 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113,"},{"Add":" 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132,"},{"Add":" 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151,"},{"Add":" 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170,"},{"Add":" 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189,"},{"Add":" 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208,"},{"Add":" 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227,"},{"Add":" 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246,"},{"Add":" 247, 248, 249, 250, 251, 252, 253, 254, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266,"},{"Add":" 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285,"},{"Add":" 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304,"},{"Add":" 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323,"},{"Add":" 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342,"},{"Add":" 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361,"},{"Add":" 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380,"},{"Add":" 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399,"},{"Add":" 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418,"},{"Add":" 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437,"},{"Add":" 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456,"},{"Add":" 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475,"},{"Add":" 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494,"},{"Add":" 495, 496, 497, 498, 499, 499, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,"},{"Add":"];"}]}},{"FileAdd":{"meta":{"basename":"main.rs","metadata":420},"context":[{"change":0,"pos":71008}],"contents":[{"Add":"use lmdb_rs::*;"},{"Add":"use log::*;"},{"Add":"use sanakirja::environment::*;"},{"Add":"use sanakirja_core::btree::*;"},{"Add":""},{"Add":"// mod parallel_benchmark;"},{"Add":""},{"Add":"type B = sanakirja_core::btree::page::Page;"},{"Add":""},{"Add":"fn main() {"},{"Add":" env_logger::init();"},{"Add":" main::main();"},{"Add":" // main::parallel_benchmark();"},{"Add":"}"},{"Add":""},{"Add":"mod main {"},{"Add":" use super::*;"},{"Add":" pub fn main() {"},{"Add":" let env = Env::new_anon(409600000).unwrap();"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut db = create_db::, ()>, u64, u64, B>(&mut txn).unwrap();"},{"Add":" let n = 1_000_000u64;"},{"Add":" let now = std::time::SystemTime::now();"},{"Add":" for i in 0..n {"},{"Add":" debug!(\"put {:?}\", i);"},{"Add":" put(&mut txn, &mut db, &(i * i), &(i * i * i)).unwrap();"},{"Add":" }"},{"Add":" println!(\"moi: {:?}\", now.elapsed());"},{"Add":""},{"Add":" /*"},{"Add":" let mut btree = std::collections::BTreeMap::new();"},{"Add":" let now = std::time::SystemTime::now();"},{"Add":" for i in 0..n {"},{"Add":" debug!(\"put {:?}\", i);"},{"Add":" btree.insert(i*i, i*i*i);"},{"Add":" }"},{"Add":" println!(\"std: {:?}\", now.elapsed());"},{"Add":""},{"Add":""},{"Add":" std::mem::forget(txn);"},{"Add":" {"},{"Add":" let env = EnvBuilder::new()"},{"Add":" .map_size(1 << 27)"},{"Add":" .open(\"test-lmdb\", 0o777)"},{"Add":" .unwrap();"},{"Add":""},{"Add":" let db_handle = env.get_default_db(DbFlags::empty()).unwrap();"},{"Add":" let txn = env.new_transaction().unwrap();"},{"Add":" {"},{"Add":" let db = txn.bind(&db_handle); // get a database bound to this transaction"},{"Add":" let now = std::time::SystemTime::now();"},{"Add":" for i in 0..n {"},{"Add":" db.set(&(i * i), &(i * i * i)).unwrap();"},{"Add":" }"},{"Add":" println!(\"lmdb: {:?}\", now.elapsed());"},{"Add":" }"},{"Add":" }"},{"Add":" */"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"lib.rs","metadata":420},"context":[{"change":0,"pos":71008}],"contents":[{"Add":"use thiserror::*;"},{"Add":""},{"Add":"pub mod environment;"},{"Add":""},{"Add":"/// Errors that can occur while transacting."},{"Add":"#[derive(Debug, Error)]"},{"Add":"pub enum Error {"},{"Add":" /// IO errors, from the `std::io` module."},{"Add":" #[error(transparent)]"},{"Add":" IO(#[from] std::io::Error),"},{"Add":" /// Lock poisoning error."},{"Add":" #[error(\"Lock poisoning\")]"},{"Add":" Poison,"},{"Add":" /// Version mismatch"},{"Add":" #[error(\"Version mismatch\")]"},{"Add":" VersionMismatch,"},{"Add":" /// CRC check failed"},{"Add":" #[error(transparent)]"},{"Add":" CRC(#[from] CRCError),"},{"Add":"}"},{"Add":""},{"Add":"/// A CRC check failed"},{"Add":"#[derive(Debug, Error)]"},{"Add":"#[error(\"CRC check failed\")]"},{"Add":"pub struct CRCError {}"}]}},{"FileAdd":{"meta":{"basename":"environment","metadata":1005},"context":[{"change":0,"pos":71008}],"contents":[]}},{"FileAdd":{"meta":{"basename":"muttxn.rs","metadata":420},"context":[{"change":0,"pos":80153}],"contents":[{"Add":"use super::*;"},{"Add":"use log::*;"},{"Add":"use sanakirja_core::{btree, MutPage, Page};"},{"Add":"use std::borrow::Borrow;"},{"Add":""},{"Add":"/// A mutable transaction."},{"Add":"pub struct MutTxn>, T> {"},{"Add":" env: E,"},{"Add":" parent: T,"},{"Add":" length: u64,"},{"Add":" free: Page,"},{"Add":" rc: Option>>,"},{"Add":" /// Offsets of pages that were allocated by this transaction, and"},{"Add":" /// have not been freed since."},{"Add":" occupied_owned_pages: Vec,"},{"Add":""},{"Add":" /// Offsets of pages that were allocated by this transaction, and"},{"Add":" /// then freed."},{"Add":" free_owned_pages: Vec,"},{"Add":""},{"Add":" /// Offsets of old pages freed by this transaction. These were"},{"Add":" /// *not* allocated by this transaction."},{"Add":" free_pages: Vec,"},{"Add":" roots: [u64; 508],"},{"Add":"}"},{"Add":""},{"Add":"impl>, T> Drop for MutTxn {"},{"Add":" fn drop(&mut self) {"},{"Add":" let env = self.env.borrow();"},{"Add":" unsafe {"},{"Add":" let root = env.root.lock();"},{"Add":" env.roots[*root].unlock_exclusive()"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Transactions that can be committed."},{"Add":"pub trait Commit {"},{"Add":" /// Commit the transaction."},{"Add":" fn commit(self) -> Result<(), Error>;"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, E: Borrow>, T> Commit for MutTxn> {"},{"Add":" fn commit(self) -> Result<(), Error> {"},{"Add":" self.parent.length = self.length;"},{"Add":" self.parent.free = self.free;"},{"Add":" self.parent"},{"Add":" .occupied_owned_pages"},{"Add":" .extend(self.occupied_owned_pages.iter().cloned());"},{"Add":" self.parent"},{"Add":" .free_owned_pages"},{"Add":" .extend(self.free_owned_pages.iter());"},{"Add":" self.parent.free_pages.extend(self.free_pages.iter());"},{"Add":" for (u, v) in self.roots.iter().enumerate() {"},{"Add":" if *v != 0 {"},{"Add":" self.parent.roots[u] = *v"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Env {"},{"Add":" /// Start a mutable transaction. Mutable transactions that go out"},{"Add":" /// of scope are automatically aborted."},{"Add":" pub fn mut_txn_begin>(env: E) -> Result, Error> {"},{"Add":" unsafe {"},{"Add":" let (header, free, rc) = {"},{"Add":" let env_ = env.borrow();"},{"Add":" let maps = env_.mmaps.lock()[0].ptr;"},{"Add":" let v = env_.root.lock();"},{"Add":" let n = env_.roots.len();"},{"Add":" env_.roots[(*v + 1) % n].lock_exclusive();"},{"Add":" debug!(\"{:?} {:?}\", v, env_.roots.len());"},{"Add":" // Copy the roots of the last transaction onto this one."},{"Add":" let page_ptr = maps.offset((*v * PAGE_SIZE) as isize);"},{"Add":" let next_page_ptr = maps.offset((((*v + 1) % n) * PAGE_SIZE) as isize);"},{"Add":" std::ptr::copy_nonoverlapping(page_ptr, next_page_ptr, PAGE_SIZE);"},{"Add":""},{"Add":" let header = GlobalHeader::from_le(&*(page_ptr as *const GlobalHeader));"},{"Add":" let free = Page {"},{"Add":" data: env_.find_offset(header.free_db),"},{"Add":" offset: header.free_db,"},{"Add":" };"},{"Add":" let rc = if header.rc_db == 0 {"},{"Add":" None"},{"Add":" } else {"},{"Add":" Some(btree::Db {"},{"Add":" db: Page {"},{"Add":" offset: header.rc_db,"},{"Add":" data: env_.find_offset(header.rc_db),"},{"Add":" },"},{"Add":" marker: std::marker::PhantomData,"},{"Add":" })"},{"Add":" };"},{"Add":" (header, free, rc)"},{"Add":" };"},{"Add":" Ok(MutTxn {"},{"Add":" env,"},{"Add":" parent: (),"},{"Add":" rc,"},{"Add":" length: if header.length == 0 {"},{"Add":" (PAGE_SIZE as u64) * (header.n_roots as u64)"},{"Add":" } else {"},{"Add":" header.length"},{"Add":" },"},{"Add":" free,"},{"Add":" occupied_owned_pages: Vec::with_capacity(100),"},{"Add":" free_owned_pages: Vec::new(),"},{"Add":" free_pages: Vec::new(),"},{"Add":" roots: [0; 508],"},{"Add":" })"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl>> Commit for MutTxn {"},{"Add":" fn commit(mut self) -> Result<(), Error> {"},{"Add":" unsafe {"},{"Add":" let mut free_db: btree::Db> = btree::Db {"},{"Add":" db: std::mem::replace("},{"Add":" &mut self.free,"},{"Add":" Page {"},{"Add":" data: std::ptr::null_mut(),"},{"Add":" offset: 0,"},{"Add":" },"},{"Add":" ),"},{"Add":" marker: std::marker::PhantomData,"},{"Add":" };"},{"Add":" while !self.free_owned_pages.is_empty() || !self.free_pages.is_empty() {"},{"Add":" let mut free_owned_pages ="},{"Add":" std::mem::replace(&mut self.free_owned_pages, Vec::new());"},{"Add":" let mut free_pages = std::mem::replace(&mut self.free_pages, Vec::new());"},{"Add":" for p in free_owned_pages.drain(..).chain(free_pages.drain(..)) {"},{"Add":" btree::put(&mut self, &mut free_db, &p, &())?;"},{"Add":" }"},{"Add":" }"},{"Add":" for p in self.occupied_owned_pages.iter_mut() {"},{"Add":" p.clear_dirty();"},{"Add":" }"},{"Add":" let env = self.env.borrow();"},{"Add":" let mut maps = env.mmaps.lock();"},{"Add":" let root = env.root.lock();"},{"Add":" let globptr = maps[0].ptr.offset((PAGE_SIZE * *root) as isize) as *mut GlobalHeader;"},{"Add":" (&mut *globptr).length = self.length.to_le();"},{"Add":" (&mut *globptr).free_db = free_db.db.offset.to_le();"},{"Add":""},{"Add":" // Moving the root page, both on page 0, and on the environment."},{"Add":" let globptr = maps[0].ptr as *mut GlobalHeader;"},{"Add":" (&mut *globptr).root = ((&mut *globptr).root + 1) % (&mut *globptr).n_roots;"},{"Add":" let mut root = env.root.lock();"},{"Add":" *root = (*root + 1) % env.roots.len();"},{"Add":""},{"Add":" for m in maps.iter_mut() {"},{"Add":" m.flush()?"},{"Add":" }"},{"Add":" *env.first_unused_page.lock() = self.length;"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl>, T> MutTxn {"},{"Add":" pub fn set_root(&mut self, num: usize, value: u64) {"},{"Add":" self.roots[num] = value;"},{"Add":" }"},{"Add":""},{"Add":" fn free_owned_page(&mut self, offset: u64) {"},{"Add":" self.free_owned_pages.push(offset);"},{"Add":" }"},{"Add":""},{"Add":" fn free_page(&mut self, offset: u64) {"},{"Add":" self.free_pages.push(offset)"},{"Add":" }"},{"Add":""},{"Add":" /// Pop a free page from the list of free pages."},{"Add":" fn free_pages_pop(&mut self) -> Result, crate::Error> {"},{"Add":" if self.free.offset == 0 {"},{"Add":" return Ok(None);"},{"Add":" }"},{"Add":" let mut db: btree::Db> = btree::Db {"},{"Add":" db: self.free,"},{"Add":" marker: std::marker::PhantomData,"},{"Add":" };"},{"Add":" let mut curs = btree::cursor::Cursor::new(&db);"},{"Add":" let f = if let Some((f, ())) = curs.set_last(self)? {"},{"Add":" *f"},{"Add":" } else {"},{"Add":" return Ok(None);"},{"Add":" };"},{"Add":" btree::del_at_cursor(self, &mut db, &mut curs)?;"},{"Add":" self.free = db.db;"},{"Add":" Ok(Some(f))"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl>, T> sanakirja_core::AllocPage for MutTxn {"},{"Add":" /// Allocate a single page."},{"Add":" fn alloc_page(&mut self) -> Result {"},{"Add":" // If we have allocated and freed a page in this transaction, use it first."},{"Add":" if let Some(page) = self.free_owned_pages.pop() {"},{"Add":" let page = MutPage(Page {"},{"Add":" data: unsafe { self.env.borrow().find_offset(page) },"},{"Add":" offset: page,"},{"Add":" });"},{"Add":" self.occupied_owned_pages.push(page);"},{"Add":" Ok(page)"},{"Add":" } else {"},{"Add":" // Else, if there are free pages, take one."},{"Add":" if let Some(page) = self.free_pages_pop()? {"},{"Add":" let page = MutPage(Page {"},{"Add":" data: unsafe { self.env.borrow().find_offset(page) },"},{"Add":" offset: page,"},{"Add":" });"},{"Add":" self.occupied_owned_pages.push(page);"},{"Add":" Ok(page)"},{"Add":" } else {"},{"Add":" // Else, allocate in the free space."},{"Add":" debug!(\"allocate in the free space {:?}\", self.length);"},{"Add":" let last = self.length;"},{"Add":" self.length += PAGE_SIZE as u64;"},{"Add":" let page = MutPage(Page {"},{"Add":" data: unsafe { self.env.borrow().find_offset(last) },"},{"Add":" offset: last,"},{"Add":" });"},{"Add":" self.occupied_owned_pages.push(page);"},{"Add":" Ok(page)"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn decr_rc(&mut self, off: u64) -> Result<(), Error> {"},{"Add":" if let Some(mut rc_) = self.rc.take() {"},{"Add":" let mut curs = btree::cursor::Cursor::new(&rc_);"},{"Add":" curs.set(self, Some((&off, None)))?;"},{"Add":" if let Some((rc, ())) = curs.next(self)? {"},{"Add":" let off_ = *rc & !0xfff;"},{"Add":" if off_ == off {"},{"Add":" let r = *rc & 0xfff;"},{"Add":" if r > 2 {"},{"Add":" *rc = off_ | (r - 1);"},{"Add":" } else {"},{"Add":" btree::del(self, &mut rc_, rc, None)?;"},{"Add":" }"},{"Add":" self.rc = Some(rc_);"},{"Add":" return Ok(());"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" self.free_page(off);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" fn decr_rc_owned(&mut self, off: u64) -> Result<(), Error> {"},{"Add":" let mut rc_del = 0;"},{"Add":" if let Some(mut rc_) = self.rc.take() {"},{"Add":" let mut curs = btree::cursor::Cursor::new(&rc_);"},{"Add":" if let Some((rc, _)) = curs.set(self, Some((&off, None)))? {"},{"Add":" let off_ = *rc & !0xfff;"},{"Add":" if off_ == off {"},{"Add":" let r = *rc & 0xfff;"},{"Add":" if r > 2 {"},{"Add":" *rc = off_ | (r - 1);"},{"Add":" self.rc = Some(rc_);"},{"Add":" return Ok(());"},{"Add":" } else {"},{"Add":" rc_del = *rc;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" if rc_del != 0 {"},{"Add":" btree::del(self, &mut rc_, &rc_del, None)?;"},{"Add":" }"},{"Add":" self.rc = Some(rc_);"},{"Add":" }"},{"Add":" self.free_owned_page(off);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" fn incr_rc(&mut self, off: u64) -> Result<(), Error> {"},{"Add":" if let Some(mut rc_) = self.rc.take() {"},{"Add":" let mut curs = btree::cursor::Cursor::new(&rc_);"},{"Add":" if let Some((rc, _)) = curs.set(self, Some((&off, None)))? {"},{"Add":" let off_ = *rc & !0xfff;"},{"Add":" if off_ == off {"},{"Add":" let r = *rc & 0xfff;"},{"Add":" *rc = off_ | (r + 1);"},{"Add":" } else {"},{"Add":" btree::put(self, &mut rc_, &(off | 2), &())?;"},{"Add":" }"},{"Add":" } else {"},{"Add":" btree::put(self, &mut rc_, &(off | 2), &())?;"},{"Add":" }"},{"Add":" self.rc = Some(rc_)"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl>, A> sanakirja_core::LoadPage for MutTxn {"},{"Add":" type Error = crate::Error;"},{"Add":" fn load_page(&self, off: u64) -> Result {"},{"Add":" unsafe {"},{"Add":" let data = self.env.borrow().find_offset(off);"},{"Add":" Ok(Page { data, offset: off })"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" fn rc(&self, page: u64) -> Result {"},{"Add":" if let Some(ref rc) = self.rc {"},{"Add":" let mut curs: btree::cursor::Cursor> ="},{"Add":" btree::cursor::Cursor::new(rc);"},{"Add":" if let Some((rc, _)) = curs.set(self, Some((&page, None)))? {"},{"Add":" if *rc & !0xfff == page {"},{"Add":" let r = *rc & 0xfff;"},{"Add":" if r >= 2 {"},{"Add":" return Ok(r);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" Ok(0)"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"mod.rs","metadata":420},"context":[{"change":0,"pos":80153}],"contents":[{"Add":"use crate::Error;"},{"Add":"use parking_lot::lock_api::RawRwLock;"},{"Add":"use parking_lot::Mutex;"},{"Add":"use std::borrow::Borrow;"},{"Add":"use std::path::Path;"},{"Add":""},{"Add":"use sanakirja_core::Page;"},{"Add":""},{"Add":"mod muttxn;"},{"Add":"pub use muttxn::*;"},{"Add":"mod global_header;"},{"Add":"use global_header::*;"},{"Add":""},{"Add":"pub(crate) const PAGE_SIZE: usize = 4096;"},{"Add":"const CURRENT_VERSION: u16 = 3;"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"pub(crate) struct Map {"},{"Add":" pub(crate) ptr: *mut u8,"},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" file: Option,"},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" mmap: memmap::MmapMut,"},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" layout: std::alloc::Layout,"},{"Add":" length: u64,"},{"Add":"}"},{"Add":""},{"Add":"impl Map {"},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" fn flush(&self) -> Result<(), Error> {"},{"Add":" Ok(self.mmap.flush()?)"},{"Add":" }"},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" fn flush(&self) -> Result<(), Error> {"},{"Add":" Ok(())"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Represents an exclusive lock taken on the environment."},{"Add":"pub struct Exclusive(std::fs::File);"},{"Add":""},{"Add":"#[cfg(feature = \"mmap\")]"},{"Add":"impl Drop for Exclusive {"},{"Add":" fn drop(&mut self) {"},{"Add":" self.0.unlock().unwrap_or(());"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Represents a shared lock taken on the environment."},{"Add":"pub struct Shared(std::fs::File);"},{"Add":""},{"Add":"#[cfg(feature = \"mmap\")]"},{"Add":"impl Drop for Shared {"},{"Add":" fn drop(&mut self) {"},{"Add":" self.0.unlock().unwrap_or(());"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// Lock order: first take thread locks, then process locks."},{"Add":""},{"Add":"// Why are there two synchronization mechanisms?"},{"Add":"// Because we would need to upgrade the read lock into a write lock,"},{"Add":"// and there is no real way to do this with standard mechanisms."},{"Add":"// So, we take a mutex to make sure no other mutable transaction can start,"},{"Add":"// and then at the time of writing, we also take the RwLock."},{"Add":""},{"Add":"/// Environment, required to start any transactions. Thread-safe, but"},{"Add":"/// opening the same database several times in the same process is not"},{"Add":"/// cross-platform."},{"Add":"pub struct Env {"},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" path: Option,"},{"Add":" /// It is undefined behavior to have a file mmapped for than once."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" lock_file: Option,"},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" lock_file: std::marker::PhantomData,"},{"Add":""},{"Add":" pub(crate) mmaps: Mutex>,"},{"Add":" first_unused_page: Mutex,"},{"Add":""},{"Add":" roots: Vec,"},{"Add":" root: Mutex,"},{"Add":"}"},{"Add":""},{"Add":"unsafe impl Send for Env {}"},{"Add":"unsafe impl Sync for Env {}"},{"Add":""},{"Add":"#[cfg(feature = \"mmap\")]"},{"Add":"impl Drop for Env {"},{"Add":" fn drop(&mut self) {"},{"Add":" for map in self.mmaps.lock().unwrap().drain(..) {"},{"Add":" drop(map.mmap);"},{"Add":" drop(map.file);"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[cfg(not(feature = \"mmap\"))]"},{"Add":"impl Drop for Env {"},{"Add":" fn drop(&mut self) {"},{"Add":" let mut mmaps = self.mmaps.lock();"},{"Add":" for map in mmaps.drain(..) {"},{"Add":" unsafe { std::alloc::dealloc(map.ptr, map.layout) }"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// An immutable transaction."},{"Add":"pub struct Txn>> {"},{"Add":" env: E,"},{"Add":" lock: std::marker::PhantomData,"},{"Add":" root: usize,"},{"Add":"}"},{"Add":""},{"Add":"impl Env {"},{"Add":" /// std::fs::File size of the database path, if it exists."},{"Add":" pub fn file_size>(path: P) -> Result {"},{"Add":" let db_path = path.as_ref().join(\"db\");"},{"Add":" Ok(std::fs::metadata(&db_path)?.len())"},{"Add":" }"},{"Add":""},{"Add":" /// Same as [`new`](#new), but does not take a lock on the file"},{"Add":" /// system."},{"Add":" ///"},{"Add":" /// This method is provided because waiting for a lock on the file"},{"Add":" /// system may block the whole process, whereas."},{"Add":" ///"},{"Add":" /// However, the database is very likely to get corrupted if open"},{"Add":" /// more than once at the same time, even within the same process."},{"Add":" ///"},{"Add":" /// Therefore, do not use this method without another locking"},{"Add":" /// mechanism in place to avoid that situation."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub unsafe fn new_nolock>(path: P, length: u64) -> Result {"},{"Add":" // let length = (1 as u64).shl(log_length);"},{"Add":" let mut db_path = path.as_ref().join(\"db0\");"},{"Add":" let db_exists = std::fs::metadata(&db_path).is_ok();"},{"Add":" let length = if let Ok(meta) = std::fs::metadata(&db_path) {"},{"Add":" std::cmp::max(meta.len(), length)"},{"Add":" } else {"},{"Add":" std::cmp::max(length, 4096)"},{"Add":" };"},{"Add":" let length = length.next_power_of_two();"},{"Add":" let file = OpenOptions::new()"},{"Add":" .read(true)"},{"Add":" .write(true)"},{"Add":" .truncate(false)"},{"Add":" .create(true)"},{"Add":" .open(&db_path)?;"},{"Add":" file.set_len(length)?;"},{"Add":" let mmap = memmap::MmapMut::map_mut(&file)?;"},{"Add":" let mut env = Self::new_nolock_mmap(Some(file), length, mmap, !db_exists)?;"},{"Add":" db_path.pop();"},{"Add":" env.path = Some(db_path);"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":""},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" unsafe fn new_nolock_mmap("},{"Add":" file: Option,"},{"Add":" length: u64,"},{"Add":" mut mmap: memmap::MmapMut,"},{"Add":" initialise: bool,"},{"Add":" ) -> Result {"},{"Add":" let map = mmap.as_mut_ptr();"},{"Add":" let n_roots = 2;"},{"Add":" let glob = if initialise {"},{"Add":" for i in 0..n_roots {"},{"Add":" *(map.offset(i * PAGE_SIZE) as *mut GlobalHeader) = GlobalHeader {"},{"Add":" version: CURRENT_VERSION,"},{"Add":" root: 0,"},{"Add":" n_roots,"},{"Add":" crc: 0,"},{"Add":" length: n_roots * PAGE_SIZE,"},{"Add":" free_db: 0,"},{"Add":" rc_db: 0,"},{"Add":" };"},{"Add":" }"},{"Add":" GlobalHeader::from_le(*(map as *const GlobalHeader))"},{"Add":" } else {"},{"Add":" GlobalHeader::from_le(*(map as *const GlobalHeader))"},{"Add":" };"},{"Add":" let mut versions = Vec::with_capacity(glob.n_versions as usize);"},{"Add":" for _ in 0..glob.n_versions {"},{"Add":" versions.push(Mutex::new(()))"},{"Add":" }"},{"Add":" let env = Env {"},{"Add":" path: None,"},{"Add":" mmaps: Mutex::new(vec![Map {"},{"Add":" ptr: map,"},{"Add":" mmap,"},{"Add":" file,"},{"Add":" length,"},{"Add":" }]),"},{"Add":" lock_file: None,"},{"Add":" first_unused_page: Mutex::new(2),"},{"Add":" mutable: parking_lot::RawMutex::INIT,"},{"Add":" versions,"},{"Add":" };"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":""},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" unsafe fn new_nolock_mmap(length: u64, initialise: bool) -> Result, Error> {"},{"Add":" assert!(initialise);"},{"Add":" let layout = std::alloc::Layout::from_size_align(length as usize, 64).unwrap();"},{"Add":" let map = std::alloc::alloc(layout);"},{"Add":" let n_roots = 2;"},{"Add":" for i in 0..n_roots {"},{"Add":" *(map.offset((i * PAGE_SIZE) as isize) as *mut GlobalHeader) = (GlobalHeader {"},{"Add":" version: CURRENT_VERSION,"},{"Add":" root: 0,"},{"Add":" n_roots: n_roots as u8,"},{"Add":" crc: 0,"},{"Add":" length: n_roots as u64 * PAGE_SIZE as u64,"},{"Add":" free_db: 0,"},{"Add":" rc_db: 0,"},{"Add":" })"},{"Add":" .to_le();"},{"Add":" }"},{"Add":" let glob = GlobalHeader::from_le(&*(map as *const GlobalHeader));"},{"Add":" let mut roots = Vec::with_capacity(glob.n_roots as usize);"},{"Add":" for _ in 0..glob.n_roots {"},{"Add":" roots.push(::INIT)"},{"Add":" }"},{"Add":" let env = Env {"},{"Add":" mmaps: Mutex::new(vec![Map {"},{"Add":" ptr: map,"},{"Add":" layout,"},{"Add":" length,"},{"Add":" }]),"},{"Add":" lock_file: std::marker::PhantomData,"},{"Add":" first_unused_page: Mutex::new(2),"},{"Add":" roots,"},{"Add":" root: Mutex::new(glob.root as usize),"},{"Add":" };"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Env {"},{"Add":" /// Initialize an environment. `length` must be a strictly"},{"Add":" /// positive multiple of 4096. The same file can only be open in"},{"Add":" /// one process or thread at the same time, and this is enforced"},{"Add":" /// by a locked file."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub fn new_shared>(path: P, length: u64) -> Result, Error> {"},{"Add":" let lock_file = OpenOptions::new()"},{"Add":" .read(true)"},{"Add":" .write(true)"},{"Add":" .truncate(false)"},{"Add":" .create(true)"},{"Add":" .open(path.as_ref().join(\"db\").with_extension(\"lock\"))?;"},{"Add":" lock_file.lock_shared()?;"},{"Add":" let mut env = unsafe { Self::new_nolock(path, length)? };"},{"Add":" env.lock_file = Some(Shared(lock_file));"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":""},{"Add":" /// Initialize an environment. `length` must be a strictly"},{"Add":" /// positive multiple of 4096. Returns an error if the database is"},{"Add":" /// locked by another process or thread."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub fn try_new_shared>(path: P, length: u64) -> Result, Error> {"},{"Add":" let lock_file = OpenOptions::new()"},{"Add":" .read(true)"},{"Add":" .write(true)"},{"Add":" .truncate(false)"},{"Add":" .create(true)"},{"Add":" .open(path.as_ref().join(\"db\").with_extension(\"lock\"))?;"},{"Add":" lock_file.try_lock_shared()?;"},{"Add":" let mut env = unsafe { Self::new_nolock(path, length)? };"},{"Add":" env.lock_file = Some(Shared(lock_file));"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Env {"},{"Add":" /// Initialize an environment. `length` must be a strictly"},{"Add":" /// positive multiple of 4096. The same file can only be open in"},{"Add":" /// one process or thread at the same time, and this is enforced"},{"Add":" /// by a locked file."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub fn new>(path: P, length: u64) -> Result, Error> {"},{"Add":" let lock_file = OpenOptions::new()"},{"Add":" .read(true)"},{"Add":" .write(true)"},{"Add":" .truncate(false)"},{"Add":" .create(true)"},{"Add":" .open(path.as_ref().join(\"db\").with_extension(\"lock\"))?;"},{"Add":" lock_file.lock_exclusive()?;"},{"Add":" let mut env = unsafe { Self::new_nolock(path, length)? };"},{"Add":" env.lock_file = Some(Exclusive(lock_file));"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":""},{"Add":" /// Initialize an environment. `length` must be a strictly"},{"Add":" /// positive multiple of 4096. Returns an error if the database is"},{"Add":" /// locked by another process or thread."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub fn try_new>(path: P, length: u64) -> Result, Error> {"},{"Add":" let lock_file = OpenOptions::new()"},{"Add":" .read(true)"},{"Add":" .write(true)"},{"Add":" .truncate(false)"},{"Add":" .create(true)"},{"Add":" .open(path.as_ref().join(\"db\").with_extension(\"lock\"))?;"},{"Add":" lock_file.try_lock_exclusive()?;"},{"Add":" let mut env = unsafe { Self::new_nolock(path, length)? };"},{"Add":" env.lock_file = Some(Exclusive(lock_file));"},{"Add":" Ok(env)"},{"Add":" }"},{"Add":""},{"Add":" /// Create a new anonymous database, backed by memory. The length"},{"Add":" /// is the total size in bytes of the database."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub fn new_anon(length: u64) -> Result, Error> {"},{"Add":" let length = std::cmp::max(length, 4096).next_power_of_two();"},{"Add":" let mmap = memmap::MmapMut::map_anon(length as usize)?;"},{"Add":" unsafe { Self::new_nolock_mmap(None, length, mmap, true) }"},{"Add":" }"},{"Add":""},{"Add":" /// Create a new anonymous database, backed by memory. The length"},{"Add":" /// is the total size in bytes of the database."},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" pub fn new_anon(length: u64) -> Result, Error> {"},{"Add":" let length = std::cmp::max(length, 4096).next_power_of_two();"},{"Add":" unsafe { Self::new_nolock_mmap(length, true) }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Env {"},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" fn open_mmap(&self, i: usize, length0: u64) -> Result {"},{"Add":" let length = length0 << i;"},{"Add":" let layout = std::alloc::Layout::from_size_align(length as usize, 64).unwrap();"},{"Add":" let map = unsafe { std::alloc::alloc(layout) };"},{"Add":" Ok(Map {"},{"Add":" ptr: map,"},{"Add":" layout,"},{"Add":" length,"},{"Add":" })"},{"Add":" }"},{"Add":""},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" fn open_mmap(&self, i: usize, length0: u64) -> Result {"},{"Add":" let length = length0 << i;"},{"Add":" if let Some(ref path) = self.path {"},{"Add":" let mut db_path = path.join(&format!(\"db{}\", i));"},{"Add":" let file = OpenOptions::new()"},{"Add":" .read(true)"},{"Add":" .write(true)"},{"Add":" .truncate(false)"},{"Add":" .create(true)"},{"Add":" .open(&db_path)?;"},{"Add":" file.set_len(length)?;"},{"Add":" db_path.pop();"},{"Add":" let mut mmap = unsafe { memmap::MmapMut::map_mut(&file)? };"},{"Add":" Ok(Map {"},{"Add":" ptr: mmap.as_mut_ptr(),"},{"Add":" mmap,"},{"Add":" file: Some(file),"},{"Add":" length,"},{"Add":" })"},{"Add":" } else {"},{"Add":" let mut mmap = memmap::MmapMut::map_anon(length as usize)?;"},{"Add":" Ok(Map {"},{"Add":" ptr: mmap.as_mut_ptr(),"},{"Add":" mmap,"},{"Add":" file: None,"},{"Add":" length,"},{"Add":" })"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unsafe fn find_offset(&self, mut offset: u64) -> *mut u8 {"},{"Add":" let mut i = 0;"},{"Add":" let mut mmaps = self.mmaps.lock();"},{"Add":" loop {"},{"Add":" if i >= mmaps.len() {"},{"Add":" let length0 = mmaps[0].length;"},{"Add":" mmaps.push(self.open_mmap(i, length0).unwrap());"},{"Add":" }"},{"Add":" if offset < mmaps[i].length {"},{"Add":" return mmaps[i].ptr.offset(offset as isize);"},{"Add":" }"},{"Add":" offset -= mmaps[i].length;"},{"Add":" i += 1"},{"Add":" }"},{"Add":" }"},{"Add":" /// Close this repository, releasing the locks. It is undefined"},{"Add":" /// behaviour to use the environment afterwards. This method can"},{"Add":" /// be used for instance to release the locks before allocating a"},{"Add":" /// new environment (note that `std::mem::replace` followed by"},{"Add":" /// `Drop::drop` of the previous value would not release the locks"},{"Add":" /// in the correct order)."},{"Add":" ///"},{"Add":" /// The safe alternative to this method is to use an `Option`"},{"Add":" /// instead of an `Env`."},{"Add":" #[cfg(feature = \"mmap\")]"},{"Add":" pub unsafe fn close(&mut self) {"},{"Add":" for m in self.mmaps.lock().unwrap().drain(..) {"},{"Add":" drop(m.mmap);"},{"Add":" }"},{"Add":" if let Some(lock_file) = self.lock_file.take() {"},{"Add":" drop(lock_file)"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Close this repository."},{"Add":" ///"},{"Add":" /// The safe alternative to this method is to use an `Option`"},{"Add":" /// instead of an `Env`."},{"Add":" #[cfg(not(feature = \"mmap\"))]"},{"Add":" pub unsafe fn close(&mut self) {"},{"Add":" let mut mmaps = self.mmaps.lock();"},{"Add":" for m in mmaps.drain(..) {"},{"Add":" std::alloc::dealloc(m.ptr, m.layout)"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Env {"},{"Add":" /// Start a read-only transaction."},{"Add":" pub fn txn_begin>(env: E) -> Result, Error> {"},{"Add":" let root = {"},{"Add":" let env_ = env.borrow();"},{"Add":" let root = env_.root.lock();"},{"Add":" let root = (*root + env_.roots.len() - 1) % env_.roots.len();"},{"Add":" env_.roots[root].lock_shared();"},{"Add":" root"},{"Add":" };"},{"Add":" Ok(Txn {"},{"Add":" env,"},{"Add":" lock: std::marker::PhantomData,"},{"Add":" root,"},{"Add":" })"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl>> Drop for Txn {"},{"Add":" fn drop(&mut self) {"},{"Add":" let env = self.env.borrow();"},{"Add":" unsafe { env.roots[self.root].unlock_shared() }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl>> sanakirja_core::LoadPage for Txn {"},{"Add":" type Error = crate::Error;"},{"Add":""},{"Add":" /// Find the appropriate map segment"},{"Add":" fn load_page(&self, off: u64) -> Result {"},{"Add":" unsafe {"},{"Add":" let data = self.env.borrow().find_offset(off);"},{"Add":" check_crc(data)?;"},{"Add":" Ok(Page { data, offset: off })"},{"Add":" }"},{"Add":" }"},{"Add":" fn rc(&self, _: u64) -> Result {"},{"Add":" Ok(0)"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[cfg(feature = \"crc32\")]"},{"Add":"unsafe fn check_crc(p: *const u8) -> Result<(), crate::CRCError> {"},{"Add":" let crc = u32::from_le(*(p as *const u32));"},{"Add":" let mut h = crc32fast::Hasher::new();"},{"Add":" let data = std::slice::from_raw_parts(p.offset(4), PAGE_SIZE - 4);"},{"Add":" h.update(data);"},{"Add":" let crc_ = h.finalize();"},{"Add":" if crc_ == crc {"},{"Add":" Ok(())"},{"Add":" } else {"},{"Add":" Err(CRCError {})"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[cfg(not(feature = \"crc32\"))]"},{"Add":"unsafe fn check_crc(_: *const u8) -> Result<(), crate::CRCError> {"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"global_header.rs","metadata":420},"context":[{"change":0,"pos":80153}],"contents":[{"Add":"#[derive(Debug)]"},{"Add":"pub struct GlobalHeader {"},{"Add":" /// Version of Sanakirja"},{"Add":" pub version: u16,"},{"Add":" /// Which page is currently the root page? (only valid for page 0)"},{"Add":" pub root: u8,"},{"Add":" pub n_roots: u8,"},{"Add":" /// CRC of this page"},{"Add":" pub crc: u32,"},{"Add":""},{"Add":" /// First free page at the end of the file (only valid for page 0)"},{"Add":" pub length: u64,"},{"Add":""},{"Add":" /// Offset of the free list"},{"Add":" pub free_db: u64,"},{"Add":""},{"Add":" /// Offset of the RC db,"},{"Add":" pub rc_db: u64,"},{"Add":"}"},{"Add":""},{"Add":"impl GlobalHeader {"},{"Add":" pub fn from_le(&self) -> Self {"},{"Add":" GlobalHeader {"},{"Add":" version: u16::from_le(self.version),"},{"Add":" root: self.root,"},{"Add":" n_roots: self.n_roots,"},{"Add":" crc: u32::from_le(self.crc),"},{"Add":" free_db: u64::from_le(self.free_db),"},{"Add":" length: u64::from_le(self.length),"},{"Add":" rc_db: u64::from_le(self.rc_db),"},{"Add":" }"},{"Add":" }"},{"Add":" pub fn to_le(&self) -> Self {"},{"Add":" GlobalHeader {"},{"Add":" version: self.version.to_le(),"},{"Add":" root: self.root,"},{"Add":" n_roots: self.n_roots,"},{"Add":" crc: self.crc.to_le(),"},{"Add":" free_db: self.free_db.to_le(),"},{"Add":" length: self.length.to_le(),"},{"Add":" rc_db: self.rc_db.to_le(),"},{"Add":" }"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"Cargo.toml","metadata":420},"context":[{"change":0,"pos":71001}],"contents":[{"Add":"[package]"},{"Add":"name = \"sanakirja\""},{"Add":"version = \"0.1.0\""},{"Add":"authors = [ \"Pierre-Étienne Meunier\" ]"},{"Add":"edition = \"2018\""},{"Add":""},{"Add":"# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html"},{"Add":""},{"Add":"[dependencies]"},{"Add":"parking_lot = \"*\""},{"Add":"thiserror = \"*\""},{"Add":"log = { version = \"*\", features = [ \"release_max_level_off\" ] }"},{"Add":"env_logger = \"*\""},{"Add":"lmdb-rs = \"*\""},{"Add":"sanakirja-core = { path = \"../sanakirja-core\", version = \"*\" }"}]}},{"FileAdd":{"meta":{"basename":"Cargo.toml","metadata":420},"context":[{"change":1,"pos":0}],"contents":[{"Add":"[workspace]"},{"Add":"members = [ \"sanakirja-core\", \"sanakirja\" ]"}]}}],"owner":"pijul","repo":"sanakirja","token":"jlDrL/bPtoiNsMsVDjw54iq2HTzUFu4rqnckVwax/Nk=","login":null}

…

Dependencies

Change contents