pmeunier/sanakirja-1.0 - Change DV4A2LR7Q5LAEGAQHLO34PZCHGJUHPAMRZFGT7GUFNKVQKPJNOYQC

Double-inserts (rebalancing near an internal deletion)

Created by pmeunier on February 2, 2021

DV4A2LR7Q5LAEGAQHLO34PZCHGJUHPAMRZFGT7GUFNKVQKPJNOYQC

Dependencies

In channels

main

Change contents

Replacement in sanakirja-core/src/lib.rs at line 11 [3.91]

B:BD[3.444] → [3.444:505]

    type Ord: Ord;
    fn ord(&self, txn: &T) -> &Self::Ord;

[3.444]

[3.505]

    fn compare(&self, txn: &T, b: &Self) -> core::cmp::Ordering;

Replacement in sanakirja-core/src/lib.rs at line 31 [3.91]

B:BD[3.1154] → [3.1154:1253]

            type Ord = Self;
            fn ord(&self, _: &T) -> &Self::Ord {
                self

[3.1154]

[3.1253]

            fn compare(&self, _: &T, b: &Self) -> core::cmp::Ordering {
                self.cmp(b)

Insertion in sanakirja-core/src/btree/put.rs at line 37 [3.3448]
[3.4653]
[3.4653]
```
        None,
```
Insertion in sanakirja-core/src/btree/put.rs at line 81 [3.3448]
[4.405]
[4.405]
```
                        None,
```
Insertion in sanakirja-core/src/btree/put.rs at line 97 [3.3448]
[3.5999]
[3.5999]
```
                        None,
```
Insertion in sanakirja-core/src/btree/page.rs at line 2 [3.8623]
[3.8638]
[5.0]
```
use core::cmp::Ordering;
use core::mem::MaybeUninit;
```
Deletion in sanakirja-core/src/btree/page.rs at line 5 [3.8623]
B:BD[5.12] → [2.0:28]
```
use core::mem::MaybeUninit;
```

Replacement in sanakirja-core/src/btree/page.rs at line 65 [3.8623]

B:BD[3.9723] → [6.0:147]

∅:D[6.147] → [3.9813:9832]

B:BD[3.9813] → [3.9813:9832]

impl<T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug> super::BTreeMutPage<T, K, V>
    for Page<K, V>

[3.9723]

[3.9832]

impl<
        T: AllocPage + core::fmt::Debug,
        K: Representable<T> + core::fmt::Debug,
        V: Representable<T> + core::fmt::Debug,
    > super::BTreeMutPage<T, K, V> for Page<K, V>

Insertion in sanakirja-core/src/btree/page.rs at line 99 [3.8623]

[7.1799]

[3.10687]

            if let Some((k, v)) = m.ins2 {
                occupied += crate::alloc_size(k, v) as usize;
            }

Replacement in sanakirja-core/src/btree/page.rs at line 104 [3.8623]

B:BD[3.10772] → [3.10772:10806]

                    occupied += 2

[3.10772]

[3.10806]

                    if m.ins2.is_some() {
                        occupied += 4;
                    } else {
                        occupied += 2;
                    }

Insertion in sanakirja-core/src/btree/page.rs at line 110 [3.8623]

[3.10824]

            } else if m.ins2.is_some() {
                occupied += 16

Insertion in sanakirja-core/src/btree/page.rs at line 126 [3.8623]
[3.11068]
[3.11068]
```
        k1v1: Option<(&'a K, &'a V)>,
```

Replacement in sanakirja-core/src/btree/page.rs at line 131 [3.8623]

B:BD[7.1844] → [7.1844:1918]

            put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, 0, 0)

[7.1844]

[7.1918]

            put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, k1v1, 0, 0)

Replacement in sanakirja-core/src/btree/page.rs at line 133 [3.8623]

B:BD[7.1935] → [7.1935:2013]

            put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, l, r)

[7.1935]

[3.11455]

            put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, k1v1, l, r)

Insertion in sanakirja-core/src/btree/page.rs at line 137 [3.8623]

[3.11472]

    fn replace<'a>(
        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.
        assert!(l > 0);
        let new = Self::del(txn, page, c, l)?;
        Self::put(txn, new.0, mutable, c, k0, v0, k1v1, l, r)
    }

Replacement in sanakirja-core/src/btree/page.rs at line 163 [3.8623]

B:BD[3.11691] → [7.2038:2130]

        debug!("update_left_child: {:?} {:?} {:?}", page, mutable, header(page.as_page()));

[3.11691]

[7.2130]

        debug!(
            "update_left_child: {:?} {:?} {:?}",
            page,
            mutable,
            header(page.as_page())
        );

Replacement in sanakirja-core/src/btree/page.rs at line 201 [3.8623]

B:BD[7.2954] → [7.2954:4160]

             unsafe { if c.is_leaf {
                 let n = hdr.n() as usize;
                 if let Some(f) = fixed_size::<T, 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::<T, 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::<T, K, V>(kv_ptr);
                 core::ptr::copy(ptr.offset(1), ptr, (&*hdr).n() as usize - c.cur);
                 (&mut *hdr).decr(size);
             }};

[7.2954]

[7.4160]

            unsafe {
                if c.is_leaf {
                    let n = hdr.n() as usize;
                    if let Some(f) = fixed_size::<T, 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::<T, 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::<T, K, V>(kv_ptr);
                    core::ptr::copy(ptr.offset(1), ptr, (&*hdr).n() as usize - c.cur);
                    (&mut *hdr).decr(size);
                }
            };

Replacement in sanakirja-core/src/btree/page.rs at line 277 [3.8623]
B:BD[3.16292] → [3.16292:16341]
```
        let left_size = Self::size(&m.modified);
```
[3.16292]
[7.5228]
```
        let mod_size = Self::size(&m.modified);
```

Replacement in sanakirja-core/src/btree/page.rs at line 282 [3.8623]

B:BD[3.16473] → [3.16473:16536]

B:BD[3.16536] → [7.5303:5401]

        let size = left_size + mid_size + occupied - hdr_size;
        debug!("size = {:?} {:?} {:?} {:?} {:?}", left_size, mid_size, occupied, hdr_size, size);

[3.16473]

[3.16536]

        let size = mod_size + mid_size + occupied - hdr_size;
        debug!(
            "size = {:?} {:?} {:?} {:?} {:?}",
            mod_size, mid_size, occupied, hdr_size, size
        );

Replacement in sanakirja-core/src/btree/page.rs at line 303 [3.8623]

B:BD[3.17048] → [7.5702:5778]

            let b1 = if Self::is_dirty(m.other.as_page()) { 1 } else { 0 };

[3.17048]

[3.17114]

            let b1 = if Self::is_dirty(m.other.as_page()) {
                1
            } else {
                0
            };

Replacement in sanakirja-core/src/btree/page.rs at line 316 [3.8623]

∅:D[7.5920] → [3.17451:17574]

B:BD[3.17451] → [3.17451:17574]

B:BD[3.17574] → [2.118:187]

∅:D[2.187] → [7.5993:6024]

B:BD[7.5993] → [7.5993:6024]

        // If we can't rebalance, return.
        if left_size >= PAGE_SIZE / 2 || occupied - first_size < PAGE_SIZE / 2 {
            return Ok(Op::Put(if let Some((k, v)) = m.modified.ins {
                Self::replace(

[7.5920]

[7.6024]

        // 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(

Replacement in sanakirja-core/src/btree/page.rs at line 324 [3.8623]

B:BD[7.6162] → [7.6162:6212]

                    &*k,
                    &*v,

[7.6162]

[7.6212]

                    k,
                    v,
                    m.modified.ins2,

Replacement in sanakirja-core/src/btree/page.rs at line 329 [3.8623]
∅:D[2.222] → [7.6269:6288]
B:BD[7.6269] → [7.6269:6288]
```
                )?
```
[2.222]
[7.6288]
```
                )?));
```
Replacement in sanakirja-core/src/btree/page.rs at line 331 [3.8623]
B:BD[7.6309] → [7.6309:6338]
```
                Put::Ok(Ok {
```
[7.6309]
[7.6338]
```
                return Ok(Op::Put(Put::Ok(Ok {
```

Replacement in sanakirja-core/src/btree/page.rs at line 334 [3.8623]

B:BD[7.6458] → [7.6458:6494]

                })
            }));

[7.6458]

[3.18250]

                })));
            }

Replacement in sanakirja-core/src/btree/page.rs at line 381 [3.8623]

B:BD[3.19408] → [7.7155:7257]

    unsafe fn unchecked_current<'a>(page: crate::Page<'a>, c: &Self::Cursor) -> (&'a K, &'a V, u64) {

[3.19408]

[3.19505]

    unsafe fn unchecked_current<'a>(
        page: crate::Page<'a>,
        c: &Self::Cursor,
    ) -> (&'a K, &'a V, u64) {

Replacement in sanakirja-core/src/btree/page.rs at line 411 [3.8623]

B:BD[3.20628] → [7.7915:8017]

            (u64::from_le(*(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64)) & 0xfff) as usize

[3.20628]

[3.20721]

            (u64::from_le(*(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64)) & 0xfff)
                as usize

Replacement in sanakirja-core/src/btree/page.rs at line 421 [3.8623]

B:BD[3.20957] → [3.20957:21038]

B:BD[3.21038] → [7.8087:8228]

∅:D[7.8228] → [3.21132:21175]

B:BD[3.21132] → [3.21132:21175]

                    2 + entry_size::<T, 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.20957]

[3.21175]

                    2 + entry_size::<T, K, V>(page.data.as_ptr().add(u16::from_le(
                        *(page.data.as_ptr().add(HDR) as *const u16).add(c.cur),

Insertion in sanakirja-core/src/btree/page.rs at line 424 [3.8623]
[3.21197]
[3.21197]
```
                        as usize))
```

Replacement in sanakirja-core/src/btree/page.rs at line 428 [3.8623]

B:BD[7.8295] → [7.8295:8405]

                    (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur)) & 0xfff) as usize,

[7.8295]

[3.21394]

                    (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur)) & 0xfff)
                        as usize,

Replacement in sanakirja-core/src/btree/page.rs at line 485 [3.8623]

B:BD[3.24989] → [7.9112:9218]

                            let off = u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));

[3.24989]

[3.25086]

                            let off =
                                u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));

Replacement in sanakirja-core/src/btree/page.rs at line 491 [3.8623]

B:BD[3.25228] → [7.9268:9370]

                        let off = u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));

[3.25228]

[7.9370]

                        let off =
                            u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));

Deletion in sanakirja-core/src/btree/page.rs at line 528 [3.8623]
B:BD[7.9543] → [7.9543:9544]
∅:D[7.9544] → [3.26192:26193]
B:BD[3.26192] → [3.26192:26193]

Replacement in sanakirja-core/src/btree/page.rs at line 547 [3.8623]

B:BD[7.10186] → [7.10186:10315]

                s.binary_search_by(|tup| {
                    (tup.k.ord(txn), tup.v.ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))

[7.10186]

[7.10315]

                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 552 [3.8623]

B:BD[7.10355] → [7.10355:10471]

                s.binary_search_by(|tup| {
                    (tup.k.ord(txn)).cmp(k0.ord(txn))
                })

[7.10355]

[7.10471]

                s.binary_search_by(|tup| tup.k.compare(txn, k0))

Replacement in sanakirja-core/src/btree/page.rs at line 563 [3.8623]

B:BD[7.10878] → [7.10878:10964]

                    ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))

[7.10878]

[7.10964]

                    match (&*k).compare(txn, k0) {
                        Ordering::Equal => (&*v).compare(txn, v0),
                        cmp => cmp,
                    }

Replacement in sanakirja-core/src/btree/page.rs at line 572 [3.8623]

B:BD[7.11188] → [7.11188:11242]

                    ((&*k).ord(txn)).cmp(k0.ord(txn))

[7.11188]

[7.11242]

                    (&*k).compare(txn, k0)

Replacement in sanakirja-core/src/btree/page.rs at line 577 [3.8623]

B:BD[7.11298] → [7.11298:11416]

        let s =
            core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const u64, hdr.n() as usize);

[7.11298]

[7.11416]

        let s = core::slice::from_raw_parts(
            page.data.as_ptr().add(HDR) as *const u64,
            hdr.n() as usize,
        );

Replacement in sanakirja-core/src/btree/page.rs at line 585 [3.8623]

B:BD[7.11635] → [7.11635:11717]

                ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))

[7.11635]

[7.11717]

                match (&*k).compare(txn, k0) {
                    Ordering::Equal => (&*v).compare(txn, v0),
                    cmp => cmp,
                }

Replacement in sanakirja-core/src/btree/page.rs at line 594 [3.8623]

B:BD[7.11937] → [7.11937:11987]

                ((&*k).ord(txn)).cmp(k0.ord(txn))

[7.11937]

[7.11987]

                (&*k).compare(txn, k0)

Deletion in sanakirja-core/src/btree/page.rs at line 600 [3.8623]
B:BD[7.12021] → [7.12021:12029]

Replacement in sanakirja-core/src/btree/page.rs at line 608 [3.8623]

B:BD[7.12083] → [7.12083:12150]

    unsafe {
        &*(page.data.as_ptr() as *const Header)
    }

[7.12083]

[3.26386]

    unsafe { &*(page.data.as_ptr() as *const Header) }

Replacement in sanakirja-core/src/btree/page.rs at line 612 [3.8623]

B:BD[7.12210] → [7.12210:12272]

    unsafe {
        &mut *(page.0.data as *mut Header)
    }

[7.12210]

[3.26479]

    unsafe { &mut *(page.0.data as *mut Header) }

Replacement in sanakirja-core/src/btree/page.rs at line 616 [3.8623]

B:BD[3.26496] → [7.12273:12336]

∅:D[7.12336] → [3.26566:26624]

B:BD[3.26566] → [3.26566:26624]

B:BD[3.26624] → [7.12337:12402]

∅:D[7.12402] → [3.26696:26754]

B:BD[3.26696] → [3.26696:26754]

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(
        hdr: &Header,
        size: usize,
    ) -> bool;
    fn can_compact<T, K: Representable<T>, V: Representable<T>>(
        hdr: &Header,
        size: usize,
    ) -> bool;

[3.26496]

[7.12403]

    fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize;
    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool;
    fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool;

Replacement in sanakirja-core/src/btree/page.rs at line 622 [3.8623]

B:BD[7.12507] → [6.313:442]

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) -> Option<(*const K, *const V)>;

[7.12507]

[7.12604]

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(
        page: &mut MutPage,
        n: usize,
    ) -> Option<(*const K, *const V)>;

Replacement in sanakirja-core/src/btree/page.rs at line 686 [3.8623]

B:BD[3.28732] → [7.13294:13357]

∅:D[7.13357] → [3.28802:28861]

B:BD[3.28802] → [3.28802:28861]

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(
        hdr: &Header,
        size: usize,
    ) -> bool {

[3.28732]

[3.28861]

    fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize {
        if fixed_size::<T, K, V>().is_some() {
            0
        } else {
            2
        }
    }
    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {

Replacement in sanakirja-core/src/btree/page.rs at line 697 [3.8623]

B:BD[3.29015] → [7.13358:13442]

            debug!("Leaf::can_alloc: {:?} {:?} {:?}", header_size, size, hdr.data);

[3.29015]

            debug!(
                "Leaf::can_alloc: {:?} {:?} {:?}",
                header_size, size, hdr.data
            );

Replacement in sanakirja-core/src/btree/page.rs at line 706 [3.8623]

B:BD[3.29224] → [7.13443:13508]

∅:D[7.13508] → [3.29296:29355]

B:BD[3.29296] → [3.29296:29355]

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(
        hdr: &Header,
        size: usize,
    ) -> bool {

[3.29224]

[3.29355]

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {

Replacement in sanakirja-core/src/btree/page.rs at line 716 [3.8623]

B:BD[3.29731] → [6.443:573]

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) -> Option<(*const K, *const V)> {

[3.29731]

[7.13607]

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(
        page: &mut MutPage,
        n: usize,
    ) -> Option<(*const K, *const V)> {

Deletion in sanakirja-core/src/btree/page.rs at line 727 [3.8623]
B:BD[6.575] → [6.575:576]

Replacement in sanakirja-core/src/btree/page.rs at line 728 [3.8623]

B:BD[7.13936] → [6.577:679]

                let mut swap: core::mem::MaybeUninit<Tuple<K, V>> = core::mem::MaybeUninit::uninit();

[7.13936]

[6.679]

                let mut swap: core::mem::MaybeUninit<Tuple<K, V>> =
                    core::mem::MaybeUninit::uninit();

Replacement in sanakirja-core/src/btree/page.rs at line 731 [3.8623]

B:BD[6.712] → [6.712:771]

                    page.0.data.add(hdr_size + (n-1) * f),

[6.712]

[6.771]

                    page.0.data.add(hdr_size + (n - 1) * f),

Replacement in sanakirja-core/src/btree/page.rs at line 751 [3.8623]

B:BD[6.1173] → [6.1173:1265]

                Some(read::<T, K, V>(page.0.data.add(hdr_size + (hdr_n as usize - n) * f)))

[6.1173]

[6.1265]

                Some(read::<T, K, V>(
                    page.0.data.add(hdr_size + (hdr_n as usize - n) * f),
                ))

Replacement in sanakirja-core/src/btree/page.rs at line 765 [3.8623]

B:BD[7.14639] → [7.14639:14790]

                core::slice::from_raw_parts(
                    page.0.data.add(HDR) as *const u16,
                    n as usize,
                )

[7.14639]

[7.14790]

                core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize)

Replacement in sanakirja-core/src/btree/page.rs at line 767 [3.8623]

B:BD[7.14805] → [7.14805:14990]

            let deleted_size: u64 = deleted_offsets.iter().map(|&off| {
                2 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64
            }).sum();

[7.14805]

[7.14990]

            let deleted_size: u64 = deleted_offsets
                .iter()
                .map(|&off| {
                    2 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64
                })
                .sum();

Replacement in sanakirja-core/src/btree/page.rs at line 812 [3.8623]

B:BD[7.15805] → [7.15805:15873]

                (hdr.n(), Self::alloc(&mut *hdr, 2+size, K::ALIGN))

[7.15805]

[7.15873]

                (
                    hdr.n(),
                    Self::alloc(&mut *hdr, 2 + size, K::ALIGN.max(V::ALIGN)),
                )

Replacement in sanakirja-core/src/btree/page.rs at line 855 [3.8623]
B:BD[3.32088] → [7.16895:16928]
```
    ) -> (&'a  K, &'a  V, u64) {
```
[3.32088]
[7.16928]
```
    ) -> (&'a K, &'a V, u64) {
```
Replacement in sanakirja-core/src/btree/page.rs at line 858 [3.8623]
B:BD[7.17025] → [7.17025:17053]
```
            (& *k, & *v, 0)
```
[7.17025]
[7.17053]
```
            (&*k, &*v, 0)
```

Replacement in sanakirja-core/src/btree/page.rs at line 864 [3.8623]

B:BD[3.32259] → [7.17064:17127]

∅:D[7.17127] → [3.32329:32388]

B:BD[3.32329] → [3.32329:32388]

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(
        hdr: &Header,
        size: usize,
    ) -> bool {

[3.32259]

[7.17128]

    fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize {
        8
    }
    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {

Replacement in sanakirja-core/src/btree/page.rs at line 871 [3.8623]

B:BD[3.32487] → [7.17198:17263]

∅:D[7.17263] → [3.32559:32618]

B:BD[3.32559] → [3.32559:32618]

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(
        hdr: &Header,
        size: usize,
    ) -> bool {

[3.32487]

[3.32618]

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {

Replacement in sanakirja-core/src/btree/page.rs at line 874 [3.8623]

B:BD[3.32704] → [6.1345:1475]

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) -> Option<(*const K, *const V)> {

[3.32704]

[7.17362]

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(
        page: &mut MutPage,
        n: usize,
    ) -> Option<(*const K, *const V)> {

Replacement in sanakirja-core/src/btree/page.rs at line 897 [3.8623]

B:BD[7.18064] → [7.18064:18216]

            offsets.iter().map(|&off| {
                8 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64
            }).sum()

[7.18064]

[7.18216]

            offsets
                .iter()
                .map(|&off| {
                    8 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64
                })
                .sum()

Replacement in sanakirja-core/src/btree/page.rs at line 927 [3.8623]

B:BD[7.18670] → [7.18670:18746]

            (hdr.n(), Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN)))

[7.18670]

[7.18746]

            (
                hdr.n(),
                Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN)),
            )

Replacement in sanakirja-core/src/btree/page.rs at line 971 [3.8623]
B:BD[3.34486] → [7.19924:19957]
```
    ) -> (&'a  K, &'a  V, u64) {
```
[3.34486]
[7.19957]
```
    ) -> (&'a K, &'a V, u64) {
```
Replacement in sanakirja-core/src/btree/page.rs at line 974 [3.8623]
B:BD[7.20054] → [7.20054:20082]
```
            (& *k, & *v, r)
```
[7.20054]
[7.20082]
```
            (&*k, &*v, r)
```

Replacement in sanakirja-core/src/btree/page.rs at line 979 [3.8623]

B:BD[3.34631] → [6.1647:1787]

unsafe fn modify<T: LoadPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

[3.34631]

[7.20093]

unsafe fn modify<
    T: LoadPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    L: Alloc,
>(

Replacement in sanakirja-core/src/btree/page.rs at line 996 [3.8623]

B:BD[2.744] → [2.744:801]

        alloc::<_, _, _, L>(new, &*k, &*v, m.l, m.r, n);

[2.744]

[3.35142]

        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);
        }

Replacement in sanakirja-core/src/btree/page.rs at line 1016 [3.8623]

B:BD[3.35449] → [6.1819:1958]

unsafe fn merge<T: LoadPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

[3.35449]

[7.20505]

unsafe fn merge<
    T: LoadPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    L: Alloc,
>(

Replacement in sanakirja-core/src/btree/page.rs at line 1046 [3.8623]

B:BD[3.36508] → [2.802:948]

fn rebalance_left<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

[3.36508]

[3.36599]

fn rebalance_left<
    'a,
    T: AllocPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    L: Alloc,
>(

Replacement in sanakirja-core/src/btree/page.rs at line 1064 [3.8623]

B:BD[3.36942] → [2.1059:1137]

    let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };

[3.36942]

[2.1137]

    let b = if header(m.modified.page.as_page()).is_dirty() {
        1
    } else {
        0
    };

Replacement in sanakirja-core/src/btree/page.rs at line 1077 [3.8623]

B:BD[2.1414] → [2.1414:1448]

            &*k,
            &*v,

[2.1414]

[2.1448]

            k,
            v,
            m.modified.ins2,

Deletion in sanakirja-core/src/btree/page.rs at line 1092 [3.8623]
B:BD[2.1803] → [2.1803:1805]
Replacement in sanakirja-core/src/btree/page.rs at line 1111 [3.8623]
B:BD[2.2679] → [2.2679:2701]
```
                    1
```
[2.2679]
[2.2701]
```
                    1,
```
Replacement in sanakirja-core/src/btree/page.rs at line 1116 [3.8623]
B:BD[2.2879] → [2.2879:2903]
```
                    n-1
```
[2.2879]
[2.2903]
```
                    n - 1,
```

Replacement in sanakirja-core/src/btree/page.rs at line 1118 [3.8623]

B:BD[2.2922] → [2.2922:3148]

                let last = data.add(hdr_size + f * (n-1)) as *mut Tuple<K, V>;
                core::ptr::copy_nonoverlapping(
                    t.as_ptr(),
                    last,
                    1
                );

[2.2922]

[2.3148]

                let last = data.add(hdr_size + f * (n - 1)) as *mut Tuple<K, V>;
                core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);

Replacement in sanakirja-core/src/btree/page.rs at line 1125 [3.8623]

B:BD[2.3301] → [2.3301:3442]

            (<Page<K, V>>::del(txn, m.other, &rc, r)?,
             core::mem::transmute(k),
             core::mem::transmute(v))
        }

[2.3301]

[3.37695]

            (
                <Page<K, V>>::del(txn, m.other, &rc, r)?,
                core::mem::transmute(k),
                core::mem::transmute(v),
            )
        },

Replacement in sanakirja-core/src/btree/page.rs at line 1146 [3.8623]

B:BD[2.3444] → [2.3444:3594]


fn rebalance_right<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

[2.3444]

[2.3594]

fn rebalance_right<
    'a,
    T: AllocPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    L: Alloc,
>(

Deletion in sanakirja-core/src/btree/page.rs at line 1164 [3.8623]
B:BD[2.4103] → [2.4103:4104]

Replacement in sanakirja-core/src/btree/page.rs at line 1166 [3.8623]

B:BD[2.4133] → [2.4133:4211]

    let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };

[2.4133]

[2.4211]

    let b = if header(m.modified.page.as_page()).is_dirty() {
        1
    } else {
        0
    };

Replacement in sanakirja-core/src/btree/page.rs at line 1179 [3.8623]

B:BD[2.4489] → [2.4489:4523]

            &*k,
            &*v,

[2.4489]

[2.4523]

            k,
            v,
            m.modified.ins2,

Replacement in sanakirja-core/src/btree/page.rs at line 1192 [3.8623]

B:BD[2.4758] → [2.4758:4943]

    if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::put(
        txn,
        new_right.0,
        true,
        &rc,
        m.mid.0,
        m.mid.1,
        r0,
        rl,
    )? {

[2.4758]

[2.4943]

    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)?
    {

Deletion in sanakirja-core/src/btree/page.rs at line 1214 [3.8623]
B:BD[2.5466] → [2.5466:5467]

Replacement in sanakirja-core/src/btree/page.rs at line 1263 [3.8623]

B:BD[7.22851] → [7.22851:22916]

                    let off_new = L::alloc(hdr, size, K::ALIGN);

[7.22851]

[7.22916]

                    let off_new = L::alloc(hdr, size, K::ALIGN.max(V::ALIGN));

Replacement in sanakirja-core/src/btree/page.rs at line 1314 [3.8623]

B:BD[3.40625] → [6.2101:2236]

fn put<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

[3.40625]

[3.40710]

fn put<
    'a,
    T: AllocPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    L: Alloc,
>(

Insertion in sanakirja-core/src/btree/page.rs at line 1327 [3.8623]
[3.40813]
[3.40813]
```
    k1v1: Option<(&'a K, &'a V)>,
```

Replacement in sanakirja-core/src/btree/page.rs at line 1331 [3.8623]

B:BD[3.40876] → [3.40876:40911]

    let size = alloc_size(k0, v0);

[3.40876]

[7.24178]

    let size = alloc_size(k0, v0)
        + if let Some((k1, v1)) = k1v1 {
            alloc_size(k1, v1)
        } else {
            0
        };

Replacement in sanakirja-core/src/btree/page.rs at line 1344 [3.8623]

B:BD[3.41135] → [7.24485:24547]

        alloc::<_, _, _, L>(&mut page, k0, v0, l, r, &mut n);

[3.41135]

[3.41197]

        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);
        }

Replacement in sanakirja-core/src/btree/page.rs at line 1360 [3.8623]

B:BD[7.24888] → [7.24888:24949]

        alloc::<T, K, V, L>(&mut new, k0, v0, l, r, &mut n);

[7.24888]

[7.24949]

        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);
        }

Replacement in sanakirja-core/src/btree/page.rs at line 1378 [3.8623]

B:BD[3.42042] → [7.25091:25186]

            return split_unsized::<_, _, _, L>(txn, page.as_page(), mutable, u, k0, v0, l, r);

[3.42042]

[3.42127]

            return split_unsized::<_, _, _, L>(txn, page.as_page(), u, k0, v0, k1v1, l, r);

Replacement in sanakirja-core/src/btree/page.rs at line 1383 [3.8623]

B:BD[3.42146] → [6.2237:2374]

fn split<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

[3.42146]

[3.42233]

fn split<
    'a,
    T: AllocPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    L: Alloc,
>(

Replacement in sanakirja-core/src/btree/page.rs at line 1507 [3.8623]

B:BD[3.45433] → [7.28226:28314]

∅:D[7.28314] → [3.45528:45663]

B:BD[3.45528] → [3.45528:45663]

fn split_unsized<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(
    _txn: &mut T,
    _page: crate::Page,
    _mutable: bool,
    _u: usize,
    _k0: &'a K,
    _v0: &'a V,
    _l: u64,
    _r: u64,

[3.45433]

[3.45663]

fn split_unsized<
    'a,
    T: AllocPage+ core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + 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,

Replacement in sanakirja-core/src/btree/page.rs at line 1523 [3.8623]

B:BD[3.45702] → [3.45702:45723]

    unimplemented!()

[3.45702]

[3.45723]

    let hdr = header(page);
    let n0 = hdr.n();
    let mut left = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);
    let mut right = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<T, 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();
    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::<T, K, V>(ptr) + L::extra_size::<T, K, V>();
            total += size;
            if is_left && total >= PAGE_SIZE / 2 {
                is_left = false;
                split = ptr as *const Tuple<K, V>;
                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::<T, K, V, L>(current_page, k0, v0, 0, l0, &mut n);
                total += alloc_size(k0, v0) + L::extra_size::<T, K, V>();
                alloc::<T, 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::<T, 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.is_null());
    let split = unsafe { &*split };
    Ok(Put::Split {
        split_key: &split.k,
        split_value: &split.v,
        left,
        right,
        freed: page.offset,
    })

Insertion in sanakirja-core/src/btree/mod.rs at line 111 [3.45735]
[3.48426]
[3.48426]
```
        k1v1: Option<(&'a K, &'a V)>,
```
Insertion in sanakirja-core/src/btree/mod.rs at line 133 [3.45735]
[3.48906]
[3.48906]
```
        k1v1: Option<(&'a K, &'a V)>,
```

Replacement in sanakirja-core/src/btree/mod.rs at line 136 [3.45735]

B:BD[3.48938] → [3.48938:49207]

    ) -> Result<Put<'a, K, V>, T::Error> {
        // TODO: optimise this for page::Page<K, V>, since this moves
        // all the offsets twice in this case.
        let new = Self::del(txn, page, c, l)?;
        Self::put(txn, new.0, mutable, c, k0, v0, l, r)
    }

[3.48938]

[3.49207]

    ) -> Result<Put<'a, K, V>, T::Error>;

Replacement in sanakirja-core/src/btree/mod.rs at line 149 [3.45735]

B:BD[7.30159] → [2.5508:5589]

                Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r)

[7.30159]

[3.49773]

                Self::replace(txn, m.page, m.mutable, &m.c1, k, v, m.ins2, m.l, m.r)

Replacement in sanakirja-core/src/btree/mod.rs at line 151 [3.45735]

B:BD[3.49794] → [2.5590:5667]

                Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r)

[3.49794]

[3.50115]

                Self::put(txn, m.page, m.mutable, &m.c1, k, v, m.ins2, m.l, m.r)

Replacement in sanakirja-core/src/btree/mod.rs at line 207 [3.45735]

B:BD[3.50858] → [3.50858:50920]

    // Replace the right child of c0's last element with `l`.

[3.50858]

[3.50920]

    // If > 0, replace the right child of c0's last element with `l`.

Replacement in sanakirja-core/src/btree/mod.rs at line 209 [3.45735]

B:BD[3.50936] → [2.5914:5975]

    // Replace the left child of c1's last element with `r`.

[3.50936]

[2.5975]

    // If > 0, replace the left child of c1's last element with `r`.

Insertion in sanakirja-core/src/btree/mod.rs at line 213 [3.45735]
[2.6029]
[3.51022]
```
    pub ins2: Option<(&'a K, &'a V)>,
```
Insertion in sanakirja-core/src/btree/del.rs at line 68 [3.52511]
[3.54649]
[3.54649]
```
        ins2: None,
```

Insertion in sanakirja-core/src/btree/del.rs at line 139 [3.52511]

[3.56145]

                // If we're deleting at an internal node, the
                // replacement has already been included in the merged
                // page.

Insertion in sanakirja-core/src/btree/del.rs at line 149 [3.52511]
[3.56385]
[3.56385]
```
                    ins2: None,
```

Insertion in sanakirja-core/src/btree/del.rs at line 163 [3.52511]

[3.56877]

[3.57005]

                // If we're deleting at an internal node, the
                // replacement is already in pages `l` or `r`.

Insertion in sanakirja-core/src/btree/del.rs at line 172 [3.52511]
[2.7092]
[3.57241]
```
                    ins2: None,
```

Insertion in sanakirja-core/src/btree/del.rs at line 186 [3.52511]

[3.57733]

[2.7093]

                // Here, no merge, split or rebalance has happened. If
                // we're deleting at an internal node (i.e. if
                // cursor.pointer == p0), we need to mark the
                // replacement here.

Deletion in sanakirja-core/src/btree/del.rs at line 191 [3.52511]
B:BD[2.7165] → [2.7165:7231]
```
                    let l = P::left_child(page.0.as_page(), &c1);
```

Replacement in sanakirja-core/src/btree/del.rs at line 193 [3.52511]

B:BD[2.7339] → [2.7339:7398]

                    (l, page.0.offset, Some((k, v)), true)

[2.7339]

[2.7398]

                    (0, page.0.offset, Some((k, v)), true)

Insertion in sanakirja-core/src/btree/del.rs at line 206 [3.52511]
[2.7665]
[3.57973]
```
                    ins2: None,
```

Replacement in sanakirja-core/src/btree/del.rs at line 226 [3.52511]

B:BD[3.58592] → [2.7699:8057]

                // Here, if we are at cursor.pointer == p0, the
                // replacement has been either inserted into one of
                // {left, right}, or is the split key/value
                // itself. Therefore, we just have to delete the
                // key/value selected for deletion in page p0 (the
                // current page).

[3.58592]

                let (ins, ins2, skip_first) = if cursor.pointer == p0 {
                    let k = unsafe { &*k0.as_ptr() };
                    let v = unsafe { &*v0.as_ptr() };
                    (Some((k, v)), Some((split_key, split_value)), true)
                } else {
                    (Some((split_key, split_value)), None, false)
                };

Replacement in sanakirja-core/src/btree/del.rs at line 239 [3.52511]

B:BD[2.8097] → [2.8097:8154]

                    ins: Some((split_key, split_value)),

[2.8097]

[3.58874]

                    ins,
                    ins2,

Replacement in sanakirja-core/src/btree/del.rs at line 242 [3.52511]

B:BD[3.58898] → [2.8155:8209]

                    skip_first: cursor.pointer == p0,

[3.58898]

[3.58937]

                    skip_first,

Insertion in sanakirja-core/src/btree/del.rs at line 294 [3.52511]
[3.60399]
[3.60399]
```
                    None,
```