pijul nest
guest › [sign in]

Unsized pages

[?]
Feb 3, 2021, 4:25 PM
H3FVSQIQGFCFKCPXVOSFHP4OSUOBBURJESCZNGQTNDAAD3WQSBEQC

Dependencies

  • [2] OTWDDJE7 Trait/type cleanup
  • [3] YWFYZNLZ Cleanup + inter-process concurrency
  • [4] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
  • [5] UAQX27N4 Tests
  • [6] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap
  • [7] OP6SVMOD Resetting history
  • [8] NQBEOCFO Tests cleanup
  • [9] WS4ZQM4R Debugging, tests, etc.
  • [10] QEUTVAZ4 Splitting btree::page
  • [11] X3QVVQIS More debugging (del seems to work now)
  • [12] S4V4QZ5C Debugging reference-counting for put
  • [13] EAAYH6BQ Debugging put
  • [14] ONES3V46 reference counting works for put
  • [15] YXKP4AIW New file locks, with multiple sets of free pages
  • [16] 6DMPXOAT More debugging

Change contents

  • edit in sanakirja-core/src/lib.rs at line 20
    [2.166]
    [3.761]
    unsafe fn onpage_size(p: *const u8) -> usize;
    unsafe fn write_to_page(&self, p: *mut u8);
  • edit in sanakirja-core/src/lib.rs at line 42
    [2.394]
    [2.394]
    }
    unsafe fn onpage_size(_: *const u8) -> usize {
    core::mem::size_of::<Self>()
    }
    unsafe fn write_to_page(&self, p: *mut u8) {
    core::ptr::copy_nonoverlapping(self, p as *mut Self, 1)
  • edit in sanakirja-core/src/lib.rs at line 62
    [2.467]
    [2.467]
    impl Representable for [u8] {
    type PageOffsets = core::iter::Empty<u64>;
    fn page_offsets(&self) -> Self::PageOffsets {
    core::iter::empty()
    }
    const ALIGN: usize = 2;
    const SIZE: Option<usize> = None;
    fn compare<T>(&self, _: &T, b: &Self) -> core::cmp::Ordering {
    self.cmp(b)
    }
    fn size(&self) -> usize {
    2 + self.len()
    }
    unsafe fn from_raw_ptr<'a, T>(_: &T, p: *const u8) -> &'a Self {
    let len = u16::from_le(*(p as *const u16));
    assert_ne!(len, 0);
    assert_eq!(len & 0xf000, 0);
    core::slice::from_raw_parts(p.add(2), len as usize)
    }
    unsafe fn onpage_size(p: *const u8) -> usize {
    let len = u16::from_le(*(p as *const u16));
    2 + len as usize
    }
    unsafe fn write_to_page(&self, p: *mut u8) {
    assert!(self.len() <= 510);
    *(p as *mut u16) = (self.len() as u16).to_le();
    core::ptr::copy_nonoverlapping(self.as_ptr(), p.add(2), self.len())
    }
    }
  • replacement in sanakirja-core/src/lib.rs at line 95
    [3.1496]→[2.470:575](∅→∅)
    unsafe fn read<T, K: Representable, V: Representable>(txn: &T, k: *const u8) -> (*const u8, *const u8) {
    [3.1496]
    [2.575]
    unsafe fn read<T, K: Representable + ?Sized, V: Representable + ?Sized>(txn: &T, k: *const u8) -> (*const u8, *const u8) {
  • replacement in sanakirja-core/src/lib.rs at line 103
    [3.1749]→[2.634:709](∅→∅)
    fn alloc_size<K: Representable, V: Representable>(k: &K, v: &V) -> usize {
    [3.1749]
    [3.1833]
    fn alloc_size<K: Representable+?Sized, V: Representable+?Sized>(k: &K, v: &V) -> usize {
  • replacement in sanakirja-core/src/lib.rs at line 109
    [3.1972]→[2.710:792](∅→∅),[3.260]→[3.2061:2102](∅→∅),[2.792]→[3.2061:2102](∅→∅),[3.2061]→[3.2061:2102](∅→∅)
    unsafe fn entry_size<K: Representable, V: Representable>(k: *const u8) -> usize {
    let ks = (&*(k as *const K)).size();
    [3.1972]
    [3.2102]
    unsafe fn entry_size<K: Representable+?Sized, V: Representable+?Sized>(k: *const u8) -> usize {
    let ks = K::onpage_size(k);
  • replacement in sanakirja-core/src/lib.rs at line 115
    [3.2255]→[3.2255:2300](∅→∅)
    let vs = (&*(v_ptr as *const V)).size();
    [3.2255]
    [3.2300]
    let vs = V::onpage_size(v_ptr);
  • replacement in sanakirja-core/src/btree/put.rs at line 18
    [3.146]→[2.793:878](∅→∅)
    pub fn put<T: AllocPage, K: Representable, V: Representable, P: BTreeMutPage<K, V>>(
    [3.146]
    [3.4213]
    pub fn put<T: AllocPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreeMutPage<K, V>>(
  • replacement in sanakirja-core/src/btree/put.rs at line 52
    [3.4963]→[2.907:996](∅→∅)
    fn put_cascade<T: AllocPage, K: Representable, V: Representable, P: BTreeMutPage<K, V>>(
    [3.4963]
    [3.5061]
    fn put_cascade<T: AllocPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreeMutPage<K, V>>(
  • replacement in sanakirja-core/src/btree/put.rs at line 125
    [3.7489]→[2.1032:1076](∅→∅)
    K: Representable,
    V: Representable,
    [3.7489]
    [2.1076]
    K: Representable+?Sized,
    V: Representable+?Sized,
  • file addition: page_unsized.rs (-xw-x--x--)
    [3.3438]
    use super::*;
    use core::cmp::Ordering;
    use log::*;
    mod put;
    mod alloc;
    use alloc::*;
    mod header;
    use header::*;
    mod rebalance;
    use rebalance::*;
    const PAGE_SIZE: usize = 4096;
    #[derive(Debug)]
    pub struct Page<K: ?Sized, V: ?Sized> {
    k: core::marker::PhantomData<K>,
    v: core::marker::PhantomData<V>,
    }
    impl<
    K: Representable+?Sized + core::fmt::Debug,
    V: Representable+?Sized + core::fmt::Debug,
    > super::BTreeMutPage<K, V> for Page<K, V>
    {
    fn init(page: &mut MutPage) {
    debug!("init {:?}", page);
    let h = header_mut(page);
    h.init();
    debug!("init: {:?}", h);
    }
    fn clean(page: &mut MutPage) {
    let hdr = header_mut(page);
    hdr.clean();
    }
    fn size(m: &ModifiedPage<K, V, Self>) -> usize {
    let mut occupied = {
    let hdr = header(m.page.as_page());
    (hdr.left_page() & 0xfff) as usize
    };
    occupied += HDR;
    if m.skip_first {
    occupied -= Self::current_size(m.page.as_page(), &m.c1) as usize;
    }
    if let Some((k, v)) = m.ins {
    occupied += crate::alloc_size(k, v) as usize;
    if let Some((k, v)) = m.ins2 {
    occupied += crate::alloc_size(k, v) as usize;
    }
    if m.c1.is_leaf {
    if m.ins2.is_some() {
    occupied += 4;
    } else {
    occupied += 2;
    }
    } else if m.ins2.is_some() {
    occupied += 16
    } else {
    occupied += 8
    }
    }
    occupied
    }
    fn put<'a, T: AllocPage>(
    txn: &mut T,
    page: CowPage,
    mutable: bool,
    c: &Cursor,
    k0: &'a K,
    v0: &'a V,
    k1v1: Option<(&'a K, &'a V)>,
    l: u64,
    r: u64,
    ) -> Result<Put<'a, K, V>, T::Error> {
    if r == 0 {
    put::put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, k1v1, 0, 0)
    } else {
    put::put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, k1v1, l, r)
    }
    }
    fn replace<'a, T: AllocPage>(
    txn: &mut T,
    page: CowPage,
    mutable: bool,
    c: &Self::Cursor,
    k0: &'a K,
    v0: &'a V,
    k1v1: Option<(&'a K, &'a V)>,
    l: u64,
    r: u64,
    ) -> Result<Put<'a, K, V>, T::Error> {
    // We're never in a leaf if we're doing this.
    let new = Self::del(txn, page, c, l)?;
    Self::put(txn, new.0, mutable, c, k0, v0, k1v1, l, r)
    }
    fn update_left_child<T: AllocPage>(
    txn: &mut T,
    page: CowPage,
    mutable: bool,
    c: &Self::Cursor,
    r: u64,
    ) -> Result<Ok, T::Error> {
    assert!(!c.is_leaf);
    let freed;
    debug!(
    "update_left_child: {:?} {:?} {:?}",
    page,
    mutable,
    header(page.as_page())
    );
    let page = if mutable && Self::is_dirty(page.as_page()) {
    freed = 0;
    unsafe { core::mem::transmute(page) }
    } else {
    let mut new = txn.alloc_page()?;
    debug!("new = {:?}", new);
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);
    let l = header(page.as_page()).left_page() & !0xfff;
    let hdr = header_mut(&mut new);
    hdr.set_left_page(l);
    let s = Internal::offset_slice::<K, V>(page.as_page());
    let mut n = 0;
    clone::<K, V, Internal>(page.as_page(), &mut new, s, &mut n);
    let b = if Self::is_dirty(page.as_page()) { 1 } else { 0 };
    freed = page.offset | b;
    new
    };
    assert!(c.cur < c.total + 1);
    unsafe {
    let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur as isize - 1);
    *off = (r | (u64::from_le(*off) & 0xfff)).to_le();
    }
    Ok(Ok { page, freed })
    }
    fn del<T: AllocPage>(txn: &mut T, page: crate::CowPage, c: &Cursor, l: u64) -> Result<MutPage, T::Error> {
    debug!("del: {:?} {:?}", page, l);
    assert!(c.cur < c.total);
    if Self::is_dirty(page.as_page()) {
    let p = page.data;
    let mut page: MutPage = unsafe { core::mem::transmute(page) };
    let hdr = header_mut(&mut page);
    unsafe {
    if c.is_leaf {
    let n = hdr.n() as usize;
    let ptr = p.add(HDR + c.cur * 2) as *mut u16;
    let kv_ptr = p.add((*ptr) as usize);
    let size = entry_size::<K, V>(kv_ptr);
    core::ptr::copy(ptr.offset(1), ptr, n - c.cur);
    hdr.decr(size);
    } else {
    let ptr = p.add(HDR + c.cur * 8) as *mut u64;
    let off = (u64::from_le(*ptr) & 0xfff) as usize;
    let kv_ptr = p.add(off);
    let size = entry_size::<K, V>(kv_ptr);
    core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur);
    (&mut *hdr).decr(size);
    }
    };
    if l > 0 {
    assert!(!c.is_leaf);
    // Updating the left page if necessary.
    unsafe {
    let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);
    *off = (l | (u64::from_le(*off) & 0xfff)).to_le();
    }
    }
    hdr.set_n(hdr.n() - 1);
    Ok(page)
    } else {
    unsafe {
    let mut new = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);
    if c.is_leaf {
    let s = Leaf::offset_slice::<K, V>(page.as_page());
    let (s0, s1) = s.split_at(c.cur);
    let mut n = 0;
    clone::<K, V, Leaf>(page.as_page(), &mut new, s0, &mut n);
    clone::<K, V, Leaf>(page.as_page(), &mut new, s1, &mut n);
    } else {
    let s = Internal::offset_slice::<K, V>(page.as_page());
    let (s0, s1) = s.split_at(c.cur);
    let mut n = 0;
    clone::<K, V, Internal>(page.as_page(), &mut new, s0, &mut n);
    let off = (page.data.add(HDR) as *mut u64).offset(n - 1);
    *off = l.to_le();
    clone::<K, V, Internal>(page.as_page(), &mut new, s1, &mut n);
    }
    Ok(new)
    }
    }
    }
    fn merge_or_rebalance<'a, T: AllocPage>(
    txn: &mut T,
    m: &mut Concat<'a, K, V, Self>,
    ) -> Result<Op<'a, T, K, V>, T::Error> {
    let hdr_size = HDR;
    let mid_size = if m.modified.c0.is_leaf {
    2 + alloc_size::<K, V>(m.mid.0, m.mid.1)
    } else {
    8 + alloc_size::<K, V>(m.mid.0, m.mid.1)
    };
    let mod_size = Self::size(&m.modified);
    let occupied = {
    let hdr = header(m.other.as_page());
    (hdr.left_page() & 0xfff) as usize
    };
    let size = mod_size + mid_size + occupied - hdr_size;
    debug!(
    "size = {:?} {:?} {:?} {:?} {:?}",
    mod_size, mid_size, occupied, hdr_size, size
    );
    if size <= PAGE_SIZE {
    // merge
    let mut new = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);
    unsafe {
    if m.modified.c0.is_leaf {
    merge::<_, _, _, Leaf>(txn, &mut new, m)
    } else {
    merge::<_, _, _, Internal>(txn, &mut new, m)
    }
    }
    let b0 = if Self::is_dirty(m.modified.page.as_page()) {
    1
    } else {
    0
    };
    let b1 = if Self::is_dirty(m.other.as_page()) {
    1
    } else {
    0
    };
    return Ok(Op::Merged {
    page: new,
    freed: [m.modified.page.offset | b0, m.other.offset | b1],
    marker: core::marker::PhantomData,
    });
    }
    let rc = <Page<K, V>>::first_cursor(m.other.as_page());
    let first_size = <Page<K, V>>::current_size(m.other.as_page(), &rc);
    // If we can't rebalance, modify and return.
    if mod_size >= PAGE_SIZE / 2 || occupied - first_size < PAGE_SIZE / 2 {
    if let Some((k, v)) = m.modified.ins {
    return Ok(Op::Put(Self::replace(
    txn,
    m.modified.page,
    m.modified.mutable,
    &m.modified.c1,
    k,
    v,
    m.modified.ins2,
    m.modified.l,
    m.modified.r,
    )?));
    } else {
    return Ok(Op::Put(Put::Ok(Ok {
    page: Self::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?,
    freed: 0,
    })));
    }
    }
    if m.mod_is_left {
    if m.modified.c0.is_leaf {
    rebalance_left::<_, _, _, Leaf>(txn, m)
    } else {
    rebalance_left::<_, _, _, Internal>(txn, m)
    }
    } else {
    if m.modified.c0.is_leaf {
    rebalance_right::<_, _, _, Leaf>(txn, m)
    } else {
    rebalance_right::<_, _, _, Internal>(txn, m)
    }
    }
    }
    }
    impl<K: Representable + ?Sized, V: Representable + ?Sized> super::BTreePage<K, V>
    for Page<K, V>
    {
    fn is_dirty(page: crate::Page) -> bool {
    header(page).is_dirty()
    }
    fn is_empty(_: crate::Page, c: &Self::Cursor) -> bool {
    c.cur >= c.total
    }
    type Cursor = Cursor;
    fn first_cursor(p: crate::Page) -> Self::Cursor {
    let hdr = header(p);
    Cursor {
    cur: 0,
    total: hdr.n() as usize,
    is_leaf: hdr.is_leaf(),
    }
    }
    fn last_cursor(p: crate::Page) -> Self::Cursor {
    let hdr = header(p);
    let total = hdr.n() as usize;
    Cursor {
    cur: total - 1,
    total,
    is_leaf: hdr.is_leaf(),
    }
    }
    unsafe fn unchecked_current<'a, T: LoadPage>(
    txn: &T,
    page: crate::Page<'a>,
    c: &Self::Cursor,
    ) -> (&'a K, &'a V, u64) {
    if c.is_leaf {
    let off = {
    u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize
    };
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));
    (K::from_raw_ptr(txn, k as *const u8), V::from_raw_ptr(txn, v as *const u8), 0)
    } else {
    let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur));
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));
    (K::from_raw_ptr(txn, k as *const u8), V::from_raw_ptr(txn, v as *const u8), off & !0xfff)
    }
    }
    unsafe fn unchecked_current_ptr(page: crate::Page, c: &Self::Cursor) -> *const u8 {
    page.data.as_ptr().add(if c.is_leaf {
    u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize
    } else {
    (u64::from_le(*(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64)) & 0xfff)
    as usize
    })
    }
    fn current_size(page: crate::Page, c: &Self::Cursor) -> usize {
    unsafe {
    if c.is_leaf {
    2 + entry_size::<K, V>(page.data.as_ptr().add(u16::from_le(
    *(page.data.as_ptr().add(HDR) as *const u16).add(c.cur),
    )
    as usize))
    } else {
    8 + entry_size::<K, V>(page.data.as_ptr().add(
    (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur)) & 0xfff)
    as usize,
    ))
    }
    }
    }
    fn move_next(_page: crate::Page, c: &mut Self::Cursor) -> bool {
    if c.cur < c.total {
    c.cur += 1;
    true
    } else {
    false
    }
    }
    fn move_prev(_page: crate::Page, c: &mut Self::Cursor) -> bool {
    if c.cur > 0 {
    c.cur -= 1;
    true
    } else {
    false
    }
    }
    fn left_child(page: crate::Page, c: &Self::Cursor) -> u64 {
    if c.is_leaf {
    0
    } else {
    let off = unsafe { *(page.data.as_ptr().add((HDR + c.cur * 8) - 8) as *const u64) };
    u64::from_le(off) & !0xfff
    }
    }
    fn right_child(page: crate::Page, c: &Self::Cursor) -> u64 {
    if c.is_leaf {
    0
    } else {
    let off = unsafe { *(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64) };
    u64::from_le(off) & !0xfff
    }
    }
    fn set_cursor<'a, T: LoadPage>(
    txn: &T,
    page: crate::Page,
    c: &mut Cursor,
    k0: &K,
    v0: Option<&V>,
    ) -> Result<(&'a K, &'a V, u64), usize> {
    unsafe {
    let lookup = lookup(txn, page, c, k0, v0);
    debug!("set_cursor, {:?} lookup = {:?}", page.offset, lookup);
    let result;
    c.cur = match lookup {
    Ok(n) => {
    result = if c.is_leaf {
    let off = {
    let off =
    u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));
    (0, off)
    };
    Ok(Leaf::kv(txn, page, off))
    } else {
    let off =
    u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));
    Ok(Internal::kv(txn, page, (off & !0xfff, (off & 0xfff) as u16)))
    };
    n
    }
    Err(n) => {
    result = Err(n);
    n
    }
    };
    result
    }
    }
    fn split_at(_: crate::Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {
    (
    Cursor {
    cur: 0,
    total: c.cur,
    is_leaf: c.is_leaf,
    },
    *c,
    )
    }
    }
    unsafe fn lookup<T, K: Representable + ?Sized, V: Representable + ?Sized>(
    txn: &T,
    page: crate::Page,
    c: &mut Cursor,
    k0: &K,
    v0: Option<&V>,
    ) -> Result<usize, usize> {
    let hdr = header(page);
    c.total = hdr.n() as usize;
    c.is_leaf = hdr.is_leaf();
    if c.is_leaf {
    let s = core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const u16,
    hdr.n() as usize,
    );
    if let Some(v0) = v0 {
    s.binary_search_by(|&off| {
    let off = u16::from_le(off);
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
    let k = K::from_raw_ptr(txn, k as *const u8);
    match k.compare(txn, k0) {
    Ordering::Equal => {
    let v = V::from_raw_ptr(txn, v as *const u8);
    v.compare(txn, v0)
    },
    cmp => cmp,
    }
    })
    } else {
    s.binary_search_by(|&off| {
    let off = u16::from_le(off);
    let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
    let k = K::from_raw_ptr(txn, k);
    k.compare(txn, k0)
    })
    }
    } else {
    let s = core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const u64,
    hdr.n() as usize,
    );
    if let Some(v0) = v0 {
    s.binary_search_by(|&off| {
    let off = u64::from_le(off) & 0xfff;
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
    let k = K::from_raw_ptr(txn, k);
    match k.compare(txn, k0) {
    Ordering::Equal => {
    let v = V::from_raw_ptr(txn, v);
    v.compare(txn, v0)
    },
    cmp => cmp,
    }
    })
    } else {
    s.binary_search_by(|&off| {
    let off = u64::from_le(off) & 0xfff;
    let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
    let k = K::from_raw_ptr(txn, k);
    k.compare(txn, k0)
    })
    }
    }
    }
    #[derive(Debug, Clone, Copy)]
    pub struct Cursor {
    cur: usize,
    total: usize,
    is_leaf: bool,
    }
    unsafe fn modify<
    T: LoadPage,
    K: Representable + ?Sized + core::fmt::Debug,
    V: Representable + ?Sized + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &T,
    new: &mut MutPage,
    m: &mut ModifiedPage<K, V, Page<K, V>>,
    n: &mut isize,
    ) {
    debug!("modify {:?}", m);
    let mut l = <Page<K, V>>::left_child(m.page.as_page(), &m.c0);
    while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.page.as_page(), &mut m.c0) {
    alloc::<_, _, L>(new, k, v, l, r, n);
    l = 0;
    }
    if let Some((k, v)) = m.ins {
    if let Some((k2, v2)) = m.ins2 {
    alloc::<_, _, L>(new, k, v, 0, 0, n);
    alloc::<_, _, L>(new, k2, v2, m.l, m.r, n);
    } else {
    alloc::<_, _, L>(new, k, v, m.l, m.r, n);
    }
    } else {
    l = m.l
    }
    let mut is_first = m.skip_first;
    while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.page.as_page(), &mut m.c1) {
    if is_first {
    is_first = false;
    continue;
    }
    alloc::< _, _, L>(new, k, v, l, r, n);
    l = 0;
    }
    }
    unsafe fn merge<
    T: LoadPage,
    K: Representable + ?Sized + core::fmt::Debug,
    V: Representable + ?Sized + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &T,
    new: &mut MutPage,
    m: &mut Concat<K, V, Page<K, V>>,
    ) {
    let mut n = 0;
    if m.mod_is_left {
    modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);
    let mut rc = <Page<K, V>>::first_cursor(m.other.as_page());
    let l = <Page<K, V>>::left_child(m.other.as_page(), &rc);
    alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, l, &mut n);
    while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.other.as_page(), &mut rc) {
    alloc::<_, _, L>(new, k, v, 0, r, &mut n);
    }
    } else {
    let mut rc = <Page<K, V>>::first_cursor(m.other.as_page());
    let mut l = <Page<K, V>>::left_child(m.other.as_page(), &rc);
    while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.other.as_page(), &mut rc) {
    alloc::<_, _, L>(new, k, v, l, r, &mut n);
    l = 0;
    }
    alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, 0, &mut n);
    modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);
    }
    }
    fn clone<K: Representable + ?Sized, V: Representable + ?Sized, L: Alloc>(
    page: crate::Page,
    new: &mut MutPage,
    s: Offsets<L::Offset>,
    n: &mut isize,
    ) {
    match s {
    Offsets::Slice(s) => {
    debug!("clone: {:?}", s);
    for off in s.iter() {
    let (r, off): (u64, u16) = (*off).into();
    debug!("clone: {:?} {:?}", r, off);
    unsafe {
    let ptr = page.data.as_ptr().add(off as usize);
    debug!("ptr = {:?}", core::slice::from_raw_parts(ptr, 24));
    let size = entry_size::<K, V>(ptr);
    debug!("size: {:?}", size);
    let hdr = header_mut(new);
    let off_new = L::alloc::<K, V>(hdr, size, K::ALIGN.max(V::ALIGN));
    debug!("off_new: {:?}", off_new);
    core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);
    L::set_offset(new, *n, r, off_new);
    }
    *n += 1;
    }
    }
    }
    }
    fn alloc<K: Representable + ?Sized, V: Representable + ?Sized, L: Alloc>(
    new: &mut MutPage,
    k0: &K,
    v0: &V,
    l: u64,
    r: u64,
    n: &mut isize,
    ) {
    let size = alloc_size(k0, v0);
    let off_new = L::alloc_insert::<K, V>(new, n, size, r);
    unsafe {
    let new_ptr = new.0.data.add(off_new as usize);
    k0.write_to_page(new_ptr);
    let ks = k0.size();
    let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));
    v0.write_to_page(v_ptr);
    }
    if l > 0 {
    L::set_right_child(new, *n - 1, l);
    }
    *n += 1;
    }
  • file addition: page_unsized (dxwrx-rx-r)
    [3.3438]
  • file addition: rebalance.rs (-xw-x--x--)
    [0.22910]
    use super::*;
    pub(crate) fn rebalance_left<
    'a,
    T: AllocPage,
    K: Representable + ?Sized + core::fmt::Debug,
    V: Representable + ?Sized + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &mut T,
    m: &mut Concat<'a, K, V, Page<K, V>>,
    ) -> Result<Op<'a, T, K, V>, T::Error> {
    assert!(m.mod_is_left);
    // First element of the right page. We'll rotate it to the left
    // page.
    let rc = <Page<K, V>>::first_cursor(m.other.as_page());
    let rl = <Page<K, V>>::left_child(m.other.as_page(), &rc);
    let (k, v, r) = unsafe { <Page<K, V>>::unchecked_current(txn, m.other.as_page(), &rc) };
    let mut freed = [0, 0];
    let b = if header(m.modified.page.as_page()).is_dirty() {
    1
    } else {
    0
    };
    freed[0] = m.modified.page.offset | b;
    let mut new_left = if let Some((k, v)) = m.modified.ins {
    if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(
    txn,
    m.modified.page,
    m.modified.mutable,
    &m.modified.c1,
    k,
    v,
    m.modified.ins2,
    m.modified.l,
    m.modified.r,
    )? {
    page
    } else {
    unreachable!()
    }
    } else {
    <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?
    };
    let mut n = header(new_left.0.as_page()).n() as isize;
    alloc::<K, V, L>(&mut new_left, m.mid.0, m.mid.1, 0, rl, &mut n);
    let (new_right, k, v): (_, &K, &V) = unsafe {
    (
    <Page<K, V>>::del(txn, m.other, &rc, r)?,
    core::mem::transmute(k),
    core::mem::transmute(v),
    )
    };
    if new_right.0.offset != m.other.offset {
    let hdr = &*header(m.other.as_page());
    let b = if hdr.is_dirty() { 1 } else { 0 };
    freed[1] = m.other.offset | b
    }
    Ok(Op::Rebalanced {
    l: new_left.0.offset,
    r: new_right.0.offset,
    k: unsafe { core::mem::transmute(k) },
    v: unsafe { core::mem::transmute(v) },
    freed,
    })
    }
    pub(crate) fn rebalance_right<
    'a,
    T: AllocPage,
    K: Representable + ?Sized + core::fmt::Debug,
    V: Representable + ?Sized + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &mut T,
    m: &mut Concat<'a, K, V, Page<K, V>>,
    ) -> Result<Op<'a, T, K, V>, T::Error> {
    assert!(!m.mod_is_left);
    // Take the last element of the left page.
    let lc = <Page<K, V>>::last_cursor(m.other.as_page());
    let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(txn, m.other.as_page(), &lc) };
    // First element of the right page.
    let rc = <Page<K, V>>::first_cursor(m.modified.page.as_page());
    let rl = <Page<K, V>>::left_child(m.modified.page.as_page(), &rc);
    let mut freed = [0, 0];
    let b = if header(m.modified.page.as_page()).is_dirty() {
    1
    } else {
    0
    };
    freed[0] = m.modified.page.offset | b;
    let mut new_right = if let Some((k, v)) = m.modified.ins {
    if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(
    txn,
    m.modified.page,
    m.modified.mutable,
    &m.modified.c1,
    k,
    v,
    m.modified.ins2,
    m.modified.l,
    m.modified.r,
    )? {
    page
    } else {
    unreachable!()
    }
    } else {
    <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?
    };
    if let Put::Ok(Ok { page, .. }) =
    <Page<K, V>>::put(txn, new_right.0, true, &rc, m.mid.0, m.mid.1, None, r0, rl)?
    {
    new_right = page
    } else {
    unreachable!()
    };
    let new_left = <Page<K, V>>::del(txn, m.other, &lc, 0)?;
    if new_left.0.offset != m.other.offset {
    let hdr = &*header(m.other.as_page());
    let b = if hdr.is_dirty() { 1 } else { 0 };
    freed[1] = m.other.offset | b
    }
    Ok(Op::Rebalanced {
    l: new_left.0.offset,
    r: new_right.0.offset,
    k: unsafe { core::mem::transmute(k0) },
    v: unsafe { core::mem::transmute(v0) },
    freed,
    })
    }
  • file addition: put.rs (-xw-x--x--)
    [0.22910]
    use super::*;
    pub(crate) fn put<
    'a,
    T: AllocPage,
    K: Representable + ?Sized + core::fmt::Debug,
    V: Representable + ?Sized + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &mut T,
    page: CowPage,
    mutable: bool,
    u: usize,
    k0: &'a K,
    v0: &'a V,
    k1v1: Option<(&'a K, &'a V)>,
    l: u64,
    r: u64,
    ) -> Result<Put<'a, K, V>, T::Error> {
    let size = alloc_size(k0, v0)
    + if let Some((k1, v1)) = k1v1 {
    alloc_size(k1, v1)
    } else {
    0
    };
    let hdr = header(page.as_page());
    let is_dirty = hdr.is_dirty();
    debug!("put {:?} {:?} {:?}", u, mutable, is_dirty);
    if mutable && is_dirty && L::can_alloc::<K, V>(header(page.as_page()), size) {
    debug!("can alloc");
    let mut page = unsafe { core::mem::transmute(page) };
    let mut n = u as isize;
    if let Some((k1, v1)) = k1v1 {
    alloc::<_, _, L>(&mut page, k0, v0, 0, 0, &mut n);
    alloc::<_, _, L>(&mut page, k1, v1, l, r, &mut n);
    } else {
    alloc::<_, _, L>(&mut page, k0, v0, l, r, &mut n);
    }
    Ok(Put::Ok(Ok { page, freed: 0 }))
    } else if L::can_compact::<K, V>(hdr, size) {
    let mut new = txn.alloc_page()?;
    debug!("can compact: {:?}", new);
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);
    L::set_right_child(&mut new, -1, hdr.left_page() & !0xfff);
    let s = L::offset_slice::<K, V>(page.as_page());
    let (s0, s1) = s.split_at(u as usize);
    let mut n = 0;
    clone::<K, V, L>(page.as_page(), &mut new, s0, &mut n);
    if let Some((k1, v1)) = k1v1 {
    alloc::<_, _, L>(&mut new, k0, v0, 0, 0, &mut n);
    alloc::<_, _, L>(&mut new, k1, v1, l, r, &mut n);
    } else {
    alloc::<_, _, L>(&mut new, k0, v0, l, r, &mut n);
    }
    clone::<K, V, L>(page.as_page(), &mut new, s1, &mut n);
    let b0 = if is_dirty { 1 } else { 0 };
    return Ok(Put::Ok(Ok {
    page: new,
    freed: page.offset | b0,
    }));
    } else {
    debug!("split");
    return split_unsized::<_, _, _, L>(txn, page.as_page(), u, k0, v0, k1v1, l, r);
    }
    }
    fn split_unsized<
    'a,
    T: AllocPage,
    K: Representable + ?Sized + core::fmt::Debug,
    V: Representable + ?Sized + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &mut T,
    page: crate::Page,
    u: usize,
    k0: &'a K,
    v0: &'a V,
    k1v1: Option<(&'a K, &'a V)>,
    l0: u64,
    r0: u64,
    ) -> Result<Put<'a, K, V>, T::Error> {
    let hdr = header(page);
    let n0 = hdr.n();
    let mut left = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);
    let mut right = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut right);
    let left_child = header(page).left_page() & !0xfff;
    L::set_right_child(&mut left, -1, left_child);
    let mut split = (core::ptr::null(), core::ptr::null());
    let mut current_page = &mut left;
    let mut n = 0;
    let s = unsafe {
    core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const LeafOffset,
    n0 as usize,
    )
    };
    let mut total = HDR;
    let mut is_left = true;
    for (uu, off) in s.iter().enumerate() {
    let (r, off): (u64, u16) = (*off).into();
    unsafe {
    let ptr = page.data.as_ptr().add(off as usize);
    let size = entry_size::<K, V>(ptr) + L::extra_size::<K, V>();
    total += size;
    if is_left && total >= PAGE_SIZE / 2 {
    is_left = false;
    split = read::<T, K, V>(txn, ptr);
    L::set_right_child(&mut right, -1, r);
    current_page = &mut right;
    n = 0;
    } else {
    let off_new = L::alloc::<K, V>(header_mut(current_page), size, K::ALIGN.max(V::ALIGN));
    core::ptr::copy_nonoverlapping(
    ptr,
    current_page.0.data.offset(off_new as isize),
    size,
    );
    L::set_offset(current_page, n, r, off_new);
    n += 1;
    }
    }
    if uu == u {
    if let Some((k1, v1)) = k1v1 {
    alloc::<K, V, L>(current_page, k0, v0, 0, l0, &mut n);
    total += alloc_size(k0, v0) + L::extra_size::<K, V>();
    alloc::<K, V, L>(current_page, k1, v1, 0, r0, &mut n);
    total += alloc_size(k1, v1) + L::extra_size::<K, V>();
    } else {
    alloc::<K, V, L>(current_page, k0, v0, l0, r0, &mut n);
    total += alloc_size(k0, v0) + L::extra_size::<K, V>();
    }
    }
    }
    assert!(!split.0.is_null());
    Ok(Put::Split {
    split_key: unsafe { K::from_raw_ptr(txn, split.0) },
    split_value: unsafe { V::from_raw_ptr(txn, split.1) },
    left,
    right,
    freed: if hdr.is_dirty() {
    page.offset | 1
    } else {
    page.offset
    },
    })
    }
  • file addition: header.rs (-xw-x--x--)
    [0.22910]
    #[derive(Debug)]
    #[repr(C)]
    pub struct Header {
    n: u16,
    data: u16,
    crc: u32,
    left_page: u64,
    }
    impl Header {
    pub fn init(&mut self) {
    self.n = (1u16).to_le(); // dirty page
    self.data = 4096_u16.to_le();
    self.crc = 0;
    self.left_page = 0;
    }
    pub fn n(&self) -> u16 {
    u16::from_le(self.n) >> 4
    }
    pub fn set_n(&mut self, n: u16) {
    let dirty = u16::from_le(self.n) & 1;
    self.n = ((n << 4) | dirty).to_le()
    }
    pub fn is_dirty(&self) -> bool {
    u16::from_le(self.n) & 1 != 0
    }
    pub fn left_page(&self) -> u64 {
    u64::from_le(self.left_page)
    }
    pub fn set_left_page(&mut self, l: u64) {
    self.left_page = l.to_le()
    }
    pub fn data(&self) -> u16 {
    u16::from_le(self.data)
    }
    pub fn set_data(&mut self, d: u16) {
    self.data = d.to_le()
    }
    pub fn decr(&mut self, s: usize) {
    self.left_page = (self.left_page() - s as u64).to_le();
    }
    pub fn set_occupied(&mut self, size: u64) {
    self.left_page = ((self.left_page() & !0xfff) | size).to_le()
    }
    pub fn incr(&mut self, s: usize) {
    self.left_page = (self.left_page() + s as u64).to_le();
    }
    pub fn is_leaf(&self) -> bool {
    u64::from_le(self.left_page) <= 0xfff
    }
    pub fn clean(&mut self) {
    self.n = (u16::from_le(self.n) & 0xfff).to_le()
    }
    }
    pub const HDR: usize = core::mem::size_of::<Header>();
    pub fn header<'a>(page: crate::Page<'a>) -> &'a Header {
    unsafe { &*(page.data.as_ptr() as *const Header) }
    }
    pub fn header_mut(page: &mut crate::MutPage) -> &mut Header {
    unsafe { &mut *(page.0.data as *mut Header) }
    }
  • file addition: alloc.rs (-xw-x--x--)
    [0.22910]
    use super::*;
    pub(crate) trait Alloc {
    fn extra_size<K: Representable + ?Sized, V: Representable + ?Sized>() -> usize;
    fn can_alloc<K: Representable + ?Sized, V: Representable + ?Sized>(hdr: &Header, size: usize) -> bool;
    fn can_compact<K: Representable + ?Sized, V: Representable + ?Sized>(hdr: &Header, size: usize) -> bool;
    fn alloc<K: Representable+?Sized, V: Representable+?Sized>(hdr: &mut Header, size: usize, align: usize) -> u16;
    // n = number of items to remove
    fn truncate_left<T, K: Representable + ?Sized, V: Representable + ?Sized>(
    txn: &T,
    page: &mut MutPage,
    n: usize,
    ) -> Option<(*const K, *const V)>;
    fn alloc_insert<K: Representable + ?Sized, V: Representable + ?Sized>(
    new: &mut MutPage,
    n: &mut isize,
    size: usize,
    r: u64,
    ) -> usize;
    fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16);
    fn set_right_child(new: &mut MutPage, n: isize, r: u64);
    type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;
    fn offset_slice<'a, K: Representable + ?Sized, V: Representable + ?Sized>(
    page: crate::Page<'a>,
    ) -> Offsets<'a, Self::Offset>;
    fn kv<'a, T, K: Representable + ?Sized, V: Representable + ?Sized>(
    txn: &T,
    page: crate::Page,
    off: (u64, u16),
    ) -> (&'a K, &'a V, u64);
    }
    #[derive(Debug, Clone)]
    pub enum Offsets<'a, A> {
    Slice(&'a [A]),
    }
    impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {
    pub fn split_at(&self, mid: usize) -> (Self, Self) {
    match self {
    Offsets::Slice(s) if mid < s.len() => {
    debug!("split_at: {:?} {:?}", s.len(), mid);
    let (a, b) = s.split_at(mid);
    (Offsets::Slice(a), Offsets::Slice(b))
    }
    Offsets::Slice(s) => {
    debug_assert_eq!(mid, s.len());
    (Offsets::Slice(s), Offsets::Slice(&[][..]))
    }
    }
    }
    }
    pub struct Leaf {}
    pub struct Internal {}
    impl Alloc for Leaf {
    fn extra_size<K: Representable + ?Sized, V: Representable + ?Sized>() -> usize {
    2
    }
    fn can_alloc<K: Representable + ?Sized, V: Representable + ?Sized>(hdr: &Header, size: usize) -> bool {
    debug!("can_alloc: {:?} {:?} {:?}", hdr.n(), size, hdr.data());
    HDR + (hdr.n() as usize) * 2 + 2 + size <= hdr.data() as usize
    }
    fn can_compact<K: Representable + ?Sized, V: Representable + ?Sized>(hdr: &Header, size: usize) -> bool {
    debug!("can_compact: {:?} {:?}", hdr.left_page(), size);
    HDR + ((hdr.left_page() & 0xfff) as usize) + 2 + size <= 4096
    }
    fn truncate_left<T, K: Representable + ?Sized, V: Representable + ?Sized>(
    _txn: &T,
    page: &mut MutPage,
    n: usize,
    ) -> Option<(*const K, *const V)> {
    debug!("truncate_left {:?} {:?}", page, n);
    let hdr_n = header_mut(page).n();
    unsafe {
    core::ptr::copy(
    page.0.data.add(HDR + n * 2),
    page.0.data.add(HDR),
    (hdr_n as usize - n) * 2,
    );
    }
    let deleted_offsets = unsafe {
    core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize)
    };
    let deleted_size: u64 = deleted_offsets
    .iter()
    .map(|&off| {
    2 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64
    })
    .sum();
    let hdr = header_mut(page);
    hdr.set_n(hdr_n - n as u16);
    hdr.decr(deleted_size as usize);
    None
    }
    fn alloc<K: Representable+?Sized, V: Representable+?Sized>(hdr: &mut Header, size: usize, align: usize) -> u16 {
    debug!("alloc = {:?} {:?}", hdr.data(), size);
    let mut data = hdr.data() - size as u16;
    data &= !((align - 1) as u16);
    hdr.set_data(data);
    hdr.set_n(hdr.n() + 1);
    hdr.incr(size + Self::extra_size::<K, V>());
    data
    }
    fn alloc_insert<K: Representable + ?Sized, V: Representable + ?Sized>(
    new: &mut MutPage,
    n: &mut isize,
    size: usize,
    _: u64,
    ) -> usize {
    let (hdr_n, off_new) = {
    let hdr = header_mut(new);
    (
    hdr.n(),
    Self::alloc::<K, V>(&mut *hdr, size, K::ALIGN.max(V::ALIGN)),
    )
    };
    // Making space for the new offset
    unsafe {
    core::ptr::copy(
    new.0.data.add(HDR + (*n as usize) * 2),
    new.0.data.add(HDR + (*n as usize) * 2 + 2),
    (hdr_n as usize - (*n as usize)) * 2,
    );
    }
    Self::set_offset(new, *n, 0, off_new);
    off_new as usize
    }
    fn set_offset(new: &mut MutPage, n: isize, _: u64, off: u16) {
    unsafe {
    let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;
    *ptr = off.to_le();
    }
    }
    fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}
    type Offset = LeafOffset;
    fn offset_slice<'a, K: Representable + ?Sized, V: Representable + ?Sized>(
    page: crate::Page<'a>,
    ) -> Offsets<'a, Self::Offset> {
    let hdr = header(page);
    unsafe {
    Offsets::Slice(core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const LeafOffset,
    hdr.n() as usize,
    ))
    }
    }
    fn kv<'a, T, K: Representable + ?Sized, V: Representable + ?Sized>(
    txn: &T,
    page: crate::Page,
    (_, off): (u64, u16),
    ) -> (&'a K, &'a V, u64) {
    unsafe {
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));
    (K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v), 0)
    }
    }
    }
    impl Alloc for Internal {
    fn extra_size<K: Representable + ?Sized, V: Representable + ?Sized>() -> usize {
    8
    }
    fn can_alloc<K: Representable + ?Sized, V: Representable + ?Sized>(hdr: &Header, size: usize) -> bool {
    (HDR as usize) + (hdr.n() as usize) * 8 + 8 + size < hdr.data() as usize
    }
    fn can_compact<K: Representable + ?Sized, V: Representable + ?Sized>(hdr: &Header, size: usize) -> bool {
    debug!("can_compact: {:?} {:?}", hdr.left_page(), size);
    (HDR as usize) + ((hdr.left_page() & 0xfff) as usize) + 8 + size < 4096
    }
    fn truncate_left<T, K: Representable + ?Sized, V: Representable + ?Sized>(
    _txn: &T,
    page: &mut MutPage,
    n: usize,
    ) -> Option<(*const K, *const V)> {
    // The following line copies the left child of the last entry
    // (hence the `- 8` and `- 1`)
    let hdr_n = header_mut(page).n();
    unsafe {
    core::ptr::copy(
    page.0.data.add(HDR + (n - 1) * 8),
    page.0.data.add(HDR - 8),
    (hdr_n as usize - n + 1) * 8,
    );
    }
    let size = {
    let offsets = unsafe {
    core::slice::from_raw_parts(
    page.0.data.add(HDR + n * 8) as *const u16,
    hdr_n as usize - n as usize,
    )
    };
    offsets
    .iter()
    .map(|&off| {
    8 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64
    })
    .sum()
    };
    let hdr = header_mut(page);
    hdr.set_n(hdr_n - n as u16);
    debug!("truncate_left {:?} {:?}", hdr.left_page(), size);
    hdr.set_occupied(size);
    None
    }
    fn alloc<K: Representable+?Sized, V: Representable+?Sized>(hdr: &mut Header, size: usize, align: usize) -> u16 {
    let mut data = hdr.data() - size as u16;
    data -= data % (align as u16);
    hdr.set_data(data);
    hdr.set_n(hdr.n() + 1);
    hdr.incr(size + Self::extra_size::<K, V>());
    data
    }
    fn alloc_insert<K: Representable + ?Sized, V: Representable + ?Sized>(
    new: &mut MutPage,
    n: &mut isize,
    size: usize,
    r: u64,
    ) -> usize {
    let (hdr_n, off_new) = {
    let hdr = header_mut(new);
    (
    hdr.n(),
    Self::alloc::<K, V>(&mut *hdr, size, K::ALIGN.max(V::ALIGN)),
    )
    };
    unsafe {
    core::ptr::copy(
    new.0.data.add(HDR + (*n as usize) * 8),
    new.0.data.add(HDR + (*n as usize) * 8 + 8),
    (hdr_n as usize - (*n as usize)) * 8,
    );
    }
    Self::set_offset(new, *n, r, off_new);
    off_new as usize
    }
    fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16) {
    unsafe {
    let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;
    *ptr = (r | off as u64).to_le();
    }
    }
    fn set_right_child(page: &mut MutPage, n: isize, r: u64) {
    unsafe {
    let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;
    let off = u64::from_le(*ptr) & 0xfff;
    *ptr = (r | off as u64).to_le();
    }
    }
    type Offset = InternalOffset;
    fn offset_slice<'a, K: Representable + ?Sized, V: Representable + ?Sized>(
    page: crate::Page<'a>,
    ) -> Offsets<'a, Self::Offset> {
    let hdr = header(page);
    unsafe {
    Offsets::Slice(core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const InternalOffset,
    hdr.n() as usize,
    ))
    }
    }
    fn kv<'a, T, K: Representable + ?Sized, V: Representable + ?Sized>(
    txn: &T,
    page: crate::Page,
    (r, off): (u64, u16),
    ) -> (&'a K, &'a V, u64) {
    unsafe {
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));
    (K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v), r)
    }
    }
    }
    #[derive(Debug, Clone, Copy)]
    #[repr(C)]
    pub struct LeafOffset(u16);
    impl Into<(u64, u16)> for LeafOffset {
    fn into(self) -> (u64, u16) {
    (0, self.0)
    }
    }
    impl Into<usize> for LeafOffset {
    fn into(self) -> usize {
    self.0 as usize
    }
    }
    #[derive(Debug, Clone, Copy)]
    #[repr(C)]
    pub struct InternalOffset(u64);
    impl Into<(u64, u16)> for InternalOffset {
    fn into(self) -> (u64, u16) {
    (self.0 & !0xfff, (self.0 & 0xfff) as u16)
    }
    }
    impl Into<usize> for InternalOffset {
    fn into(self) -> usize {
    self.0 as usize
    }
    }
  • edit in sanakirja-core/src/btree/page.rs at line 14
    [3.8682]
    [3.8682]
    #[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
    #[repr(C)]
    struct Tuple<K, V> {
    k: K,
    v: V,
    }
  • replacement in sanakirja-core/src/btree/page.rs at line 49
    [3.10292]→[2.1408:1468](∅→∅)
    if fixed_size::<K, V>().is_some() && m.c1.is_leaf {
    [3.10292]
    [3.10355]
    if m.c1.is_leaf {
  • replacement in sanakirja-core/src/btree/page.rs at line 63
    [3.611]→[3.10687:10717](∅→∅),[3.1799]→[3.10687:10717](∅→∅),[3.10687]→[3.10687:10717](∅→∅),[3.10717]→[2.1469:1521](∅→∅),[2.1521]→[3.612:783](∅→∅),[3.10772]→[3.612:783](∅→∅)
    if m.c1.is_leaf {
    if fixed_size::<K, V>().is_none() {
    if m.ins2.is_some() {
    occupied += 4;
    } else {
    occupied += 2;
    }
    [3.611]
    [3.10806]
    if !m.c1.is_leaf {
    if m.ins2.is_some() {
    occupied += 16
    } else {
    occupied += 8
  • edit in sanakirja-core/src/btree/page.rs at line 69
    [3.10824]→[3.784:856](∅→∅),[3.856]→[3.10824:10875](∅→∅),[3.10824]→[3.10824:10875](∅→∅)
    } else if m.ins2.is_some() {
    occupied += 16
    } else {
    occupied += 8
  • replacement in sanakirja-core/src/btree/page.rs at line 158
    [3.1770]→[2.1881:1941](∅→∅),[2.1941]→[3.1833:2344](∅→∅),[3.1833]→[3.1833:2344](∅→∅),[3.2344]→[2.1942:2005](∅→∅),[2.2005]→[3.2410:2544](∅→∅),[3.2410]→[3.2410:2544](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    let off = c.cur * f;
    let kv_ptr = p.add(hdr_size + off);
    core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur - 1));
    hdr.decr(f);
    } else {
    let ptr = p.add(HDR + c.cur * 2) as *mut u16;
    let kv_ptr = p.add((*ptr) as usize);
    let size = entry_size::<K, V>(kv_ptr);
    core::ptr::copy(ptr.offset(1), ptr, n - c.cur);
    hdr.decr(size);
    }
    [3.1770]
    [3.2544]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    let off = c.cur * f;
    let kv_ptr = p.add(hdr_size + off);
    core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur - 1));
    hdr.decr(f);
  • replacement in sanakirja-core/src/btree/page.rs at line 214
    [3.15906]→[2.2632:2684](∅→∅),[2.2684]→[3.15961:16104](∅→∅),[3.15961]→[3.15961:16104](∅→∅),[3.16104]→[2.2685:2742](∅→∅),[3.5170]→[3.16179:16193](∅→∅),[2.2742]→[3.16179:16193](∅→∅),[3.16179]→[3.16179:16193](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    let al = K::ALIGN.max(V::ALIGN);
    hdr_size = (HDR + al - 1) & !(al - 1);
    f
    } else {
    2 + alloc_size::<K, V>(m.mid.0, m.mid.1)
    }
    [3.15906]
    [3.16193]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let al = K::ALIGN.max(V::ALIGN);
    hdr_size = (HDR + al - 1) & !(al - 1);
    f
  • replacement in sanakirja-core/src/btree/page.rs at line 331
    [3.19528]→[2.3123:3185](∅→∅)
    let off = if let Some(f) = fixed_size::<K, V>() {
    [3.19528]
    [3.19593]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let off = {
  • edit in sanakirja-core/src/btree/page.rs at line 336
    [3.19728]→[3.19728:19749](∅→∅),[3.19749]→[3.7258:7354](∅→∅)
    } else {
    u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize
  • replacement in sanakirja-core/src/btree/page.rs at line 347
    [3.7817]→[2.3563:3615](∅→∅),[2.3615]→[3.20354:20510](∅→∅),[3.20354]→[3.20354:20510](∅→∅),[3.20510]→[3.7818:7914](∅→∅),[3.7914]→[3.20597:20611](∅→∅),[3.20597]→[3.20597:20611](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    let al = K::ALIGN.max(V::ALIGN);
    let hdr = (HDR + al - 1) & !(al - 1);
    hdr + c.cur * f
    } else {
    u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize
    }
    [3.7817]
    [3.20611]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let al = K::ALIGN.max(V::ALIGN);
    let hdr = (HDR + al - 1) & !(al - 1);
    hdr + c.cur * f
  • replacement in sanakirja-core/src/btree/page.rs at line 359
    [3.20851]→[2.3616:3672](∅→∅),[2.3672]→[3.20910:20957](∅→∅),[3.20910]→[3.20910:20957](∅→∅),[3.20957]→[2.3673:3753](∅→∅),[2.3753]→[3.4106:4187](∅→∅),[3.4106]→[3.4106:4187](∅→∅),[3.4187]→[3.21175:21197](∅→∅),[3.21175]→[3.21175:21197](∅→∅),[3.21197]→[3.4188:4223](∅→∅),[3.4223]→[3.21197:21215](∅→∅),[3.21197]→[3.21197:21215](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    f
    } else {
    2 + entry_size::<K, V>(page.data.as_ptr().add(u16::from_le(
    *(page.data.as_ptr().add(HDR) as *const u16).add(c.cur),
    )
    as usize))
    }
    [3.20851]
    [3.21215]
    core::mem::size_of::<Tuple<K, V>>()
  • replacement in sanakirja-core/src/btree/page.rs at line 414
    [3.24688]→[2.3855:3929](∅→∅)
    let off = if let Some(f) = fixed_size::<K, V>() {
    [3.24688]
    [3.24765]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let off = {
  • edit in sanakirja-core/src/btree/page.rs at line 419
    [3.24956]→[3.24956:24989](∅→∅),[3.24989]→[3.4359:4497](∅→∅),[3.4497]→[3.25086:25123](∅→∅),[3.9218]→[3.25086:25123](∅→∅),[3.25086]→[3.25086:25123](∅→∅)
    } else {
    let off =
    u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));
    (0, off)
  • edit in sanakirja-core/src/btree/page.rs at line 446
    [3.25872]→[3.25872:25881](∅→∅),[3.25881]→[2.4075:4146](∅→∅),[2.4146]→[3.25961:26184](∅→∅),[3.25961]→[3.25961:26184](∅→∅)
    }
    }
    fn fixed_size<K: Representable, V: Representable>() -> Option<usize> {
    if let (Some(ks), Some(vs)) = (K::SIZE, V::SIZE) {
    let s = ((ks + V::ALIGN - 1) & !(V::ALIGN - 1)) + vs;
    let al = K::ALIGN.max(V::ALIGN);
    Some((s + al - 1) & !(al - 1))
    } else {
    None
  • replacement in sanakirja-core/src/btree/page.rs at line 460
    [3.9834]→[2.4205:4249](∅→∅),[2.4249]→[3.9881:10186](∅→∅),[3.9881]→[3.9881:10186](∅→∅),[3.10186]→[3.4629:4794](∅→∅),[3.4794]→[3.10315:10355](∅→∅),[3.10315]→[3.10315:10355](∅→∅),[3.10355]→[3.4795:4860](∅→∅),[3.4860]→[3.10471:10485](∅→∅),[3.10471]→[3.10471:10485](∅→∅)
    if fixed_size::<K, V>().is_some() {
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    let s = core::slice::from_raw_parts(
    page.data.as_ptr().add(hdr_size) as *const Tuple<K, V>,
    hdr.n() as usize,
    );
    if let Some(v0) = v0 {
    s.binary_search_by(|tup| match tup.k.compare(txn, &k0) {
    Ordering::Equal => tup.v.compare(txn, &v0),
    c => c,
    })
    } else {
    s.binary_search_by(|tup| tup.k.compare(txn, k0))
    }
    [3.9834]
    [3.10485]
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    let s = core::slice::from_raw_parts(
    page.data.as_ptr().add(hdr_size) as *const Tuple<K, V>,
    hdr.n() as usize,
    );
    if let Some(v0) = v0 {
    s.binary_search_by(|tup| match tup.k.compare(txn, &k0) {
    Ordering::Equal => tup.v.compare(txn, &v0),
    c => c,
    })
  • replacement in sanakirja-core/src/btree/page.rs at line 472
    [3.10502]→[3.10502:10787](∅→∅),[3.10787]→[2.4250:4652](∅→∅),[2.4652]→[3.4979:5037](∅→∅),[3.4979]→[3.4979:5037](∅→∅),[3.5037]→[3.10964:11097](∅→∅),[3.10964]→[3.10964:11097](∅→∅),[3.11097]→[2.4653:4841](∅→∅),[3.5081]→[3.11242:11275](∅→∅),[2.4841]→[3.11242:11275](∅→∅),[3.11242]→[3.11242:11275](∅→∅)
    let s = core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const u16,
    hdr.n() as usize,
    );
    if let Some(v0) = v0 {
    s.binary_search_by(|&off| {
    let off = u16::from_le(off);
    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
    let k = K::from_raw_ptr(txn, k as *const u8);
    match k.compare(txn, k0) {
    Ordering::Equal => {
    let v = V::from_raw_ptr(txn, v as *const u8);
    v.compare(txn, v0)
    },
    cmp => cmp,
    }
    })
    } else {
    s.binary_search_by(|&off| {
    let off = u16::from_le(off);
    let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
    let k = K::from_raw_ptr(txn, k);
    k.compare(txn, k0)
    })
    }
    [3.10502]
    [3.11275]
    s.binary_search_by(|tup| tup.k.compare(txn, k0))
  • replacement in sanakirja-core/src/btree/page.rs at line 605
    [3.39419]→[2.6806:6860](∅→∅)
    let size = fixed_size::<K, V>().unwrap();
    [3.39419]
    [3.39476]
    let size = core::mem::size_of::<Tuple<K, V>>();
  • replacement in sanakirja-core/src/btree/page/rebalance.rs at line 52
    [3.1916]→[2.7288:7345](∅→∅),[2.7345]→[3.1976:3260](∅→∅),[3.1976]→[3.1976:3260](∅→∅)
    let (new_right, k, v) = match fixed_size::<K, V>() {
    Some(f) if r == 0 && right_hdr.is_dirty() => {
    // Rewrite the deleted element at the end of the page, so that
    // the pointer is still valid.
    let data = m.other.data;
    let mut other = MutPage(m.other);
    let right_hdr = header_mut(&mut other);
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    let n = right_hdr.n() as usize;
    right_hdr.decr(f);
    right_hdr.set_n((n - 1) as u16);
    let mut t: MaybeUninit<Tuple<K, V>> = MaybeUninit::uninit();
    unsafe {
    core::ptr::copy_nonoverlapping(
    data.add(hdr_size) as *mut Tuple<K, V>,
    t.as_mut_ptr(),
    1,
    );
    core::ptr::copy(
    data.add(hdr_size + f) as *const Tuple<K, V>,
    data.add(hdr_size) as *mut Tuple<K, V>,
    n - 1,
    );
    let last = data.add(hdr_size + f * (n - 1)) as *mut Tuple<K, V>;
    core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);
    debug!("tuple = {:?}", t.assume_init());
    (other, &(&*last).k, &(&*last).v)
    }
    [3.1916]
    [3.3260]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let (new_right, k, v) = if r == 0 && right_hdr.is_dirty() {
    // Rewrite the deleted element at the end of the page, so that
    // the pointer is still valid.
    let data = m.other.data;
    let mut other = MutPage(m.other);
    let right_hdr = header_mut(&mut other);
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    let n = right_hdr.n() as usize;
    right_hdr.decr(f);
    right_hdr.set_n((n - 1) as u16);
    let mut t: MaybeUninit<Tuple<K, V>> = MaybeUninit::uninit();
    unsafe {
    core::ptr::copy_nonoverlapping(
    data.add(hdr_size) as *mut Tuple<K, V>,
    t.as_mut_ptr(),
    1,
    );
    core::ptr::copy(
    data.add(hdr_size + f) as *const Tuple<K, V>,
    data.add(hdr_size) as *mut Tuple<K, V>,
    n - 1,
    );
    let last = data.add(hdr_size + f * (n - 1)) as *mut Tuple<K, V>;
    core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);
    debug!("tuple = {:?}", t.assume_init());
    (other, &(&*last).k, &(&*last).v)
  • replacement in sanakirja-core/src/btree/page/rebalance.rs at line 81
    [3.3270]→[3.3270:3292](∅→∅)
    _ => unsafe {
    [3.3270]
    [3.3292]
    } else {
    unsafe {
  • replacement in sanakirja-core/src/btree/page/rebalance.rs at line 88
    [3.3460]→[3.3460:3471](∅→∅)
    },
    [3.3460]
    [3.3471]
    }
  • replacement in sanakirja-core/src/btree/page/put.rs at line 64
    [3.8085]→[2.8258:8306](∅→∅),[2.8306]→[3.8136:8372](∅→∅),[3.8136]→[3.8136:8372](∅→∅)
    if let Some(s) = fixed_size::<K, V>() {
    assert!(k1v1.is_none());
    return split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r);
    } else {
    return split_unsized::<_, _, _, L>(txn, page.as_page(), u, k0, v0, k1v1, l, r);
    }
    [3.8085]
    [3.8372]
    let s = core::mem::size_of::<Tuple<K, V>>();
    assert!(k1v1.is_none());
    return split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r);
  • edit in sanakirja-core/src/btree/page/put.rs at line 193
    [3.12851]→[3.12851:12878](∅→∅),[3.12878]→[2.9529:9629](∅→∅),[2.9629]→[3.13002:13291](∅→∅),[3.13002]→[3.13002:13291](∅→∅),[3.13291]→[2.9630:9687](∅→∅),[2.9687]→[3.13351:13391](∅→∅),[3.13351]→[3.13351:13391](∅→∅),[3.13391]→[2.9688:9745](∅→∅),[2.9745]→[3.13451:13560](∅→∅),[3.13451]→[3.13451:13560](∅→∅),[3.13560]→[2.9746:9806](∅→∅),[2.9806]→[3.13599:13657](∅→∅),[3.13599]→[3.13599:13657](∅→∅),[3.13657]→[3.1006:1168](∅→∅),[3.1168]→[3.13793:13999](∅→∅),[3.13793]→[3.13793:13999](∅→∅),[3.13999]→[2.9807:9884](∅→∅),[2.9884]→[3.14079:14190](∅→∅),[3.14079]→[3.14079:14190](∅→∅),[3.14190]→[2.9885:9936](∅→∅),[2.9936]→[3.14241:14456](∅→∅),[3.14241]→[3.14241:14456](∅→∅),[3.14456]→[3.1169:1353](∅→∅),[3.1353]→[3.14561:14733](∅→∅),[3.14561]→[3.14561:14733](∅→∅),[3.14733]→[2.9937:10008](∅→∅),[2.10008]→[3.14807:14881](∅→∅),[3.14807]→[3.14807:14881](∅→∅),[3.14881]→[2.10009:10080](∅→∅),[2.10080]→[3.14955:15074](∅→∅),[3.14955]→[3.14955:15074](∅→∅),[3.15074]→[2.10081:10153](∅→∅),[2.10153]→[3.15149:15277](∅→∅),[3.15149]→[3.15149:15277](∅→∅),[3.15277]→[2.10154:10187](∅→∅),[2.10187]→[3.15344:15364](∅→∅),[3.15344]→[3.15344:15364](∅→∅),[3.15364]→[2.10188:10312](∅→∅),[2.10312]→[3.15424:15453](∅→∅),[3.15424]→[3.15424:15453](∅→∅),[3.15453]→[3.1354:1469](∅→∅),[3.1469]→[3.15481:15490](∅→∅),[3.15481]→[3.15481:15490](∅→∅)
    fn split_unsized<
    'a,
    T: AllocPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,
    L: Alloc,
    >(
    txn: &mut T,
    page: crate::Page,
    u: usize,
    k0: &'a K,
    v0: &'a V,
    k1v1: Option<(&'a K, &'a V)>,
    l0: u64,
    r0: u64,
    ) -> Result<Put<'a, K, V>, T::Error> {
    let hdr = header(page);
    let n0 = hdr.n();
    let mut left = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);
    let mut right = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);
    let left_child = header(page).left_page() & !0xfff;
    L::set_right_child(&mut left, -1, left_child);
    let mut split = (core::ptr::null(), core::ptr::null());
    let mut current_page = &mut left;
    let mut n = 0;
    let s = unsafe {
    core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const LeafOffset,
    n0 as usize,
    )
    };
    let mut total = HDR;
    let mut is_left = true;
    for off in s.iter() {
    let (r, off): (u64, u16) = (*off).into();
    unsafe {
    let ptr = page.data.as_ptr().add(off as usize);
    let size = entry_size::<K, V>(ptr) + L::extra_size::<T, K, V>();
    total += size;
    if is_left && total >= PAGE_SIZE / 2 {
    is_left = false;
    split = read::<T, K, V>(txn, ptr);
    L::set_right_child(&mut right, -1, r);
    current_page = &mut right;
    } else {
    let off_new = L::alloc(header_mut(current_page), size, K::ALIGN.max(V::ALIGN));
    core::ptr::copy_nonoverlapping(
    ptr,
    current_page.0.data.offset(off_new as isize),
    size,
    );
    L::set_offset(current_page, n, r, off_new);
    }
    }
    n += 1;
    if n == u as isize {
    if let Some((k1, v1)) = k1v1 {
    alloc::<K, V, L>(current_page, k0, v0, 0, l0, &mut n);
    total += alloc_size(k0, v0) + L::extra_size::<T, K, V>();
    alloc::<K, V, L>(current_page, k1, v1, 0, r0, &mut n);
    total += alloc_size(k1, v1) + L::extra_size::<T, K, V>();
    n += 2;
    } else {
    alloc::<K, V, L>(current_page, k0, v0, l0, r0, &mut n);
    total += alloc_size(k0, v0) + L::extra_size::<T, K, V>();
    n += 1;
    }
    }
    }
    assert!(!split.0.is_null());
    Ok(Put::Split {
    split_key: unsafe { K::from_raw_ptr(txn, split.0) },
    split_value: unsafe { V::from_raw_ptr(txn, split.1) },
    left,
    right,
    freed: if hdr.is_dirty() {
    page.offset | 1
    } else {
    page.offset
    },
    })
    }
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 63
    [3.19432]→[2.10923:10981](∅→∅)
    let size = fixed_size::<K, V>().unwrap();
    [3.19432]
    [3.19493]
    let size = core::mem::size_of::<Tuple<K, V>>();
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 77
    [2.11052]→[2.11052:11096](∅→∅),[2.11096]→[3.19878:19933](∅→∅),[3.19878]→[3.19878:19933](∅→∅)
    if fixed_size::<K, V>().is_some() {
    0
    } else {
    2
    }
    [2.11052]
    [3.19933]
    0
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 80
    [2.11190]→[2.11190:11238](∅→∅),[2.11238]→[3.20089:20371](∅→∅),[3.20089]→[3.20089:20371](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    let al = K::ALIGN.max(V::ALIGN);
    let header_size = (HDR + al - 1) & !(al - 1);
    header_size + (hdr.n() as usize) * f + size < hdr.data() as usize
    } else {
    HDR + (hdr.n() as usize) * 2 + 2 + size < hdr.data() as usize
    }
    [2.11190]
    [3.20371]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let al = K::ALIGN.max(V::ALIGN);
    let header_size = (HDR + al - 1) & !(al - 1);
    header_size + (hdr.n() as usize) * f + size < hdr.data() as usize
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 86
    [2.11334]→[2.11334:11378](∅→∅),[2.11378]→[3.20525:20836](∅→∅),[3.20525]→[3.20525:20836](∅→∅)
    if fixed_size::<K, V>().is_some() {
    let al = K::ALIGN.max(V::ALIGN);
    let header_size = (HDR + al - 1) & !(al - 1);
    header_size + ((hdr.left_page() & 0xfff) as usize) + size
    < hdr.data() as usize
    } else {
    HDR + ((hdr.left_page() & 0xfff) as usize) + 2 + size < 4096
    }
    [2.11334]
    [3.20836]
    let al = K::ALIGN.max(V::ALIGN);
    let header_size = (HDR + al - 1) & !(al - 1);
    header_size + ((hdr.left_page() & 0xfff) as usize) + size
    < hdr.data() as usize
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 97
    [3.21047]→[2.11458:11506](∅→∅),[2.11506]→[3.21098:21303](∅→∅),[3.21098]→[3.21098:21303](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);
    let hdr_n = header_mut(page).n();
    [3.21047]
    [3.21303]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);
    let hdr_n = header_mut(page).n();
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 103
    [3.21304]→[3.21304:22218](∅→∅),[3.22218]→[2.11507:11578](∅→∅),[2.11578]→[3.22256:22330](∅→∅),[3.22256]→[3.22256:22330](∅→∅),[3.22330]→[2.11579:11671](∅→∅),[2.11671]→[3.22349:22907](∅→∅),[3.22349]→[3.22349:22907](∅→∅),[3.22907]→[2.11672:11764](∅→∅),[2.11764]→[3.23002:23188](∅→∅),[3.23002]→[3.23002:23188](∅→∅)
    unsafe {
    let mut swap: core::mem::MaybeUninit<Tuple<K, V>> =
    core::mem::MaybeUninit::uninit();
    core::ptr::copy(
    page.0.data.add(hdr_size + (n - 1) * f),
    swap.as_mut_ptr() as *mut u8,
    f,
    );
    core::ptr::copy(
    page.0.data.add(hdr_size + n * f),
    page.0.data.add(hdr_size),
    (hdr_n as usize - n) * f,
    );
    core::ptr::copy(
    swap.as_ptr() as *mut u8,
    page.0.data.add(hdr_size + (hdr_n as usize - n) * f),
    f,
    );
    }
    debug!("{:?} - {:?}", hdr_n, n);
    let hdr = header_mut(page);
    hdr.set_n(hdr_n - n as u16);
    hdr.decr(n * f);
    unsafe {
    let (k, v) = read::<T, K, V>(
    txn,
    page.0.data.add(hdr_size + (hdr_n as usize - n) * f),
    );
    Some((K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v)))
    }
    } else {
    let hdr_n = header_mut(page).n();
    unsafe {
    core::ptr::copy(
    page.0.data.add(HDR + n * 2),
    page.0.data.add(HDR),
    (hdr_n as usize - n) * 2,
    );
    }
    let deleted_offsets = unsafe {
    core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize)
    };
    let deleted_size: u64 = deleted_offsets
    .iter()
    .map(|&off| {
    2 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64
    })
    .sum();
    let hdr = header_mut(page);
    hdr.set_n(hdr_n - n as u16);
    hdr.decr(deleted_size as usize);
    None
    [3.21304]
    [3.23188]
    unsafe {
    let mut swap: core::mem::MaybeUninit<Tuple<K, V>> =
    core::mem::MaybeUninit::uninit();
    core::ptr::copy(
    page.0.data.add(hdr_size + (n - 1) * f),
    swap.as_mut_ptr() as *mut u8,
    f,
    );
    core::ptr::copy(
    page.0.data.add(hdr_size + n * f),
    page.0.data.add(hdr_size),
    (hdr_n as usize - n) * f,
    );
    core::ptr::copy(
    swap.as_ptr() as *mut u8,
    page.0.data.add(hdr_size + (hdr_n as usize - n) * f),
    f,
    );
    }
    debug!("{:?} - {:?}", hdr_n, n);
    let hdr = header_mut(page);
    hdr.set_n(hdr_n - n as u16);
    hdr.decr(n * f);
    unsafe {
    let (k, v) = read::<T, K, V>(
    txn,
    page.0.data.add(hdr_size + (hdr_n as usize - n) * f),
    );
    Some((K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v)))
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 145
    [3.23578]→[3.23578:23599](∅→∅)
    size: usize,
    [3.23578]
    [3.23599]
    _size: usize,
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 148
    [3.23632]→[2.11823:11871](∅→∅),[2.11871]→[3.23683:24915](∅→∅),[3.23683]→[3.23683:24915](∅→∅)
    if let Some(f) = fixed_size::<K, V>() {
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);
    let hdr_n = header_mut(new).n();
    unsafe {
    core::ptr::copy(
    new.0.data.add(hdr_size + (*n as usize) * f),
    new.0.data.add(hdr_size + (*n as usize) * f + f),
    (hdr_n as usize - (*n as usize)) * f,
    );
    }
    let hdr = header_mut(new);
    hdr.set_n(hdr.n() + 1);
    hdr.incr(f);
    hdr_size + (*n as usize) * f
    } else {
    let (hdr_n, off_new) = {
    let hdr = header_mut(new);
    (
    hdr.n(),
    Self::alloc(&mut *hdr, 2 + size, K::ALIGN.max(V::ALIGN)),
    )
    };
    unsafe {
    core::ptr::copy(
    new.0.data.add(HDR + (*n as usize) * 2),
    new.0.data.add(HDR + (*n as usize) * 2 + 2),
    (hdr_n as usize - (*n as usize)) * 2,
    );
    }
    Self::set_offset(new, *n, 0, off_new);
    off_new as usize
    [3.23632]
    [3.24915]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let al = K::ALIGN.max(V::ALIGN);
    let hdr_size = (HDR + al - 1) & !(al - 1);
    // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);
    let hdr_n = header_mut(new).n();
    unsafe {
    core::ptr::copy(
    new.0.data.add(hdr_size + (*n as usize) * f),
    new.0.data.add(hdr_size + (*n as usize) * f + f),
    (hdr_n as usize - (*n as usize)) * f,
    );
  • edit in sanakirja-core/src/btree/page/alloc.rs at line 160
    [3.24925]
    [3.24925]
    let hdr = header_mut(new);
    hdr.set_n(hdr.n() + 1);
    hdr.incr(f);
    hdr_size + (*n as usize) * f
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 178
    [3.25400]→[2.11937:11981](∅→∅),[2.11981]→[3.25447:25746](∅→∅),[3.25447]→[3.25447:25746](∅→∅)
    if fixed_size::<K, V>().is_some() {
    Offsets::Range(0..(hdr.n() as usize))
    } else {
    unsafe {
    Offsets::Slice(core::slice::from_raw_parts(
    page.data.as_ptr().add(HDR) as *const LeafOffset,
    hdr.n() as usize,
    ))
    }
    }
    [3.25400]
    [3.25746]
    Offsets::Range(0..(hdr.n() as usize))
  • replacement in sanakirja-core/src/btree/page/alloc.rs at line 217
    [3.27048]→[2.12547:12606](∅→∅)
    let size = if let Some(f) = fixed_size::<K, V>() {
    [3.27048]
    [3.27110]
    let f = core::mem::size_of::<Tuple<K, V>>();
    let size = {
  • edit in sanakirja-core/src/btree/page/alloc.rs at line 220
    [3.27162]→[3.27162:27479](∅→∅),[3.27479]→[2.12607:12699](∅→∅),[2.12699]→[3.27574:27616](∅→∅),[3.27574]→[3.27574:27616](∅→∅)
    } else {
    let offsets = unsafe {
    core::slice::from_raw_parts(
    page.0.data.add(HDR + n * 8) as *const u16,
    hdr_n as usize - n as usize,
    )
    };
    offsets
    .iter()
    .map(|&off| {
    8 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64
    })
    .sum()
  • edit in sanakirja-core/src/btree/mod.rs at line 8
    [3.45830]
    [3.45830]
    pub mod page_unsized;
  • replacement in sanakirja-core/src/btree/mod.rs at line 17
    [3.45919]→[3.45919:45944](∅→∅)
    pub enum Put<'a, K, V> {
    [3.45919]
    [3.45944]
    pub enum Put<'a, K: ?Sized, V: ?Sized> {
  • replacement in sanakirja-core/src/btree/mod.rs at line 28
    [3.46099]→[2.13047:13213](∅→∅)
    #[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
    #[repr(C)]
    pub struct Tuple<K, V> {
    k: K,
    v: V,
    }
    pub trait BTreePage<K: Representable, V: Representable> {
    [3.46099]
    [3.46176]
    pub trait BTreePage<K: Representable+?Sized, V: Representable+?Sized>: Sized {
  • replacement in sanakirja-core/src/btree/mod.rs at line 78
    [3.47651]→[2.13840:13884](∅→∅)
    K: Representable,
    V: Representable,
    [3.47651]
    [2.13884]
    K: Representable+?Sized,
    V: Representable+?Sized,
  • replacement in sanakirja-core/src/btree/mod.rs at line 90
    [3.47817]→[2.13926:13988](∅→∅)
    K: Representable + 'a,
    V: Representable + 'a,
    [3.47817]
    [2.13988]
    K: Representable+?Sized + 'a,
    V: Representable+?Sized + 'a,
  • replacement in sanakirja-core/src/btree/mod.rs at line 101
    [3.48112]→[2.14073:14161](∅→∅)
    pub trait BTreeMutPage<K: Representable, V: Representable>:
    BTreePage<K, V> + Sized
    [3.48112]
    [3.48223]
    pub trait BTreeMutPage<K: Representable+?Sized, V: Representable+?Sized>:
    BTreePage<K, V>
  • replacement in sanakirja-core/src/btree/mod.rs at line 180
    [3.3885]→[2.14607:14664](∅→∅)
    pub enum Op<'a, T, K: Representable, V: Representable> {
    [3.3885]
    [3.50267]
    pub enum Op<'a, T, K: Representable+?Sized, V: Representable+?Sized> {
  • replacement in sanakirja-core/src/btree/mod.rs at line 199
    [3.30667]→[2.14665:14709](∅→∅)
    K: Representable,
    V: Representable,
    [3.30667]
    [2.14709]
    K: Representable+?Sized,
    V: Representable+?Sized,
  • replacement in sanakirja-core/src/btree/mod.rs at line 221
    [3.51195]→[2.14734:14799](∅→∅)
    impl<'a, K: Representable, V: Representable, P: BTreePage<K, V>>
    [3.51195]
    [2.14799]
    impl<'a, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>
  • replacement in sanakirja-core/src/btree/mod.rs at line 238
    [3.51677]→[2.14830:14908](∅→∅)
    pub struct Concat<'a, K: Representable, V: Representable, P: BTreePage<K, V>>
    [3.51677]
    [3.51777]
    pub struct Concat<'a, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>
  • replacement in sanakirja-core/src/btree/mod.rs at line 249
    [3.52016]→[2.14955:15028](∅→∅)
    pub struct Db_<K: Representable, V: Representable, P: BTreePage<K, V>> {
    [3.52016]
    [3.31135]
    pub struct Db_<K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>> {
  • replacement in sanakirja-core/src/btree/mod.rs at line 251
    [3.31156]→[2.15029:15083](∅→∅)
    pub marker: core::marker::PhantomData<(K, V, P)>,
    [3.31156]
    [3.52185]
    pub k: core::marker::PhantomData<K>,
    pub v: core::marker::PhantomData<V>,
    pub p: core::marker::PhantomData<P>,
  • replacement in sanakirja-core/src/btree/mod.rs at line 260
    [3.52224]→[2.15134:15178](∅→∅)
    K: Representable,
    V: Representable,
    [3.52224]
    [2.15178]
    K: Representable+?Sized,
    V: Representable+?Sized,
  • replacement in sanakirja-core/src/btree/mod.rs at line 270
    [3.52449]→[3.52449:52492](∅→∅)
    marker: core::marker::PhantomData,
    [3.52449]
    [3.52492]
    k: core::marker::PhantomData,
    v: core::marker::PhantomData,
    p: core::marker::PhantomData,
  • replacement in sanakirja-core/src/btree/mod.rs at line 288
    [3.3921]→[2.15382:15426](∅→∅)
    K: Representable,
    V: Representable,
    [3.3921]
    [2.15426]
    K: Representable+?Sized,
    V: Representable+?Sized,
  • replacement in sanakirja-core/src/btree/mod.rs at line 298
    [3.4149]→[3.4149:4192](∅→∅)
    marker: core::marker::PhantomData,
    [3.4149]
    [3.4192]
    k: core::marker::PhantomData,
    v: core::marker::PhantomData,
    p: core::marker::PhantomData,
  • replacement in sanakirja-core/src/btree/mod.rs at line 316
    [3.408]→[2.15653:15738](∅→∅)
    pub fn get<'a, T: LoadPage, K: Representable, V: Representable, P: BTreePage<K, V>>(
    [3.408]
    [3.502]
    pub fn get<'a, T: LoadPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>(
  • replacement in sanakirja-core/src/btree/cursor.rs at line 7
    [3.63799]→[2.24322:24400](∅→∅)
    pub struct PageCursor<K: Representable, V: Representable, P: BTreePage<K, V>>
    [3.63799]
    [3.63899]
    pub struct PageCursor<K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>
  • replacement in sanakirja-core/src/btree/cursor.rs at line 13
    [3.63959]→[2.24401:24468](∅→∅)
    impl<K: Representable, V: Representable, P: BTreePage<K, V>> Clone
    [3.63959]
    [2.24468]
    impl<K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>> Clone
  • replacement in sanakirja-core/src/btree/cursor.rs at line 23
    [3.64220]→[2.24497:24563](∅→∅)
    impl<K: Representable, V: Representable, P: BTreePage<K, V>> Copy
    [3.64220]
    [2.24563]
    impl<K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>> Copy
  • replacement in sanakirja-core/src/btree/cursor.rs at line 41
    [3.64963]→[2.24592:24668](∅→∅)
    pub struct Cursor<K: Representable, V: Representable, P: BTreePage<K, V>> {
    [3.64963]
    [2.24668]
    pub struct Cursor<K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>> {
  • replacement in sanakirja-core/src/btree/cursor.rs at line 47
    [3.65195]→[2.24742:24807](∅→∅)
    impl<'a, K: Representable, V: Representable, P: BTreePage<K, V>>
    [3.65195]
    [2.24807]
    impl<'a, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>
  • replacement in sanakirja-core/src/btree/cursor.rs at line 64
    [3.65654]→[2.24873:24934](∅→∅)
    impl<K: Representable, V: Representable, P: BTreePage<K, V>>
    [3.65654]
    [2.24934]
    impl<K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>
  • edit in sanakirja/src/tests.rs at line 202
    [3.10295]→[3.307:357](∅→∅),[3.357]→[2.26428:26520](∅→∅)
    // let db3 = fork_db(&mut txn, &db).unwrap();
    // for i in 1530..1531 {
    // del(&mut txn, &mut db, &i, None).unwrap();
    // }
  • replacement in sanakirja/src/tests.rs at line 231
    [3.7540]→[3.7540:7586](∅→∅)
    marker: std::marker::PhantomData,
    [3.7540]
    [3.7586]
    k: std::marker::PhantomData,
    v: std::marker::PhantomData,
    p: std::marker::PhantomData,
  • edit in sanakirja/src/tests.rs at line 302
    [3.2690]
    type UP<K, V> = sanakirja_core::btree::page_unsized::Page<K, V>;
    #[test]
    fn slice() {
    env_logger::try_init().unwrap_or(());
    let env = Env::new_anon(409600000, 1).unwrap();
    let mut txn = Env::mut_txn_begin(&env).unwrap();
    let mut db = create_db_::<MutTxn<&Env, ()>, u64, [u8], UP<u64, [u8]>>(&mut txn).unwrap();
    let n = 1580u64;
    let m = 1000;
    let mut values = Vec::with_capacity(n as usize);
    for i in 0..n {
    debug!("=============== putting {:?}", i);
    let alpha = b"abcdefgihjklmnopqrstuvwxyz";
    let a = &alpha[..((i as usize * 7) % 25) + 1];
    if put(&mut txn, &mut db, &i, &a[..]).unwrap() {
    values.push((i * i) % m);
    }
    }
    values.sort();
    }
  • replacement in sanakirja/src/environment/muttxn.rs at line 115
    [3.83388]→[3.83388:83446](∅→∅)
    marker: std::marker::PhantomData,
    [3.83388]
    [3.83446]
    k: std::marker::PhantomData,
    v: std::marker::PhantomData,
    p: std::marker::PhantomData,
  • replacement in sanakirja/src/environment/muttxn.rs at line 152
    [3.84510]→[3.84510:84560](∅→∅)
    marker: std::marker::PhantomData,
    [3.84510]
    [3.84560]
    k: std::marker::PhantomData,
    v: std::marker::PhantomData,
    p: std::marker::PhantomData,
  • replacement in sanakirja/src/environment/muttxn.rs at line 225
    [3.86651]→[3.86651:86697](∅→∅)
    marker: std::marker::PhantomData,
    [3.86651]
    [3.86697]
    k: std::marker::PhantomData,
    v: std::marker::PhantomData,
    p: std::marker::PhantomData,
  • replacement in sanakirja/src/environment/muttxn.rs at line 405
    [3.4808]→[3.4808:4858](∅→∅)
    marker: std::marker::PhantomData,
    [3.4808]
    [3.4858]
    k: std::marker::PhantomData,
    v: std::marker::PhantomData,
    p: std::marker::PhantomData,
  • replacement in sanakirja/src/environment/muttxn.rs at line 420
    [3.5333]→[3.5333:5391](∅→∅)
    marker: std::marker::PhantomData,
    [3.5333]
    [3.5391]
    k: std::marker::PhantomData,
    v: std::marker::PhantomData,
    p: std::marker::PhantomData,