#[macro_export]

unsafe fn read<T, K: Representable<T>, V: Representable<T>>(p: *mut u8) -> (*mut K, *mut V) {
    let k = p as *mut K;

unsafe fn read<T, K: Representable<T>, V: Representable<T>>(p: *const u8) -> (*const K, *const V) {
    let k = p as *const K;

    (k, v as *mut V)

    (k, v as *const V)

unsafe fn entry_size<T, K: Representable<T>, V: Representable<T>>(k: *mut u8) -> usize {

unsafe fn entry_size<T, K: Representable<T>, V: Representable<T>>(k: *const u8) -> usize {

pub struct Page {

pub struct CowPage {

const PAGE_SIZE: usize = 4096;

pub struct MutPage(pub Page);

pub struct Page<'a> {
    pub data: &'a [u8; PAGE_SIZE],
    pub offset: u64,
}
impl CowPage {
    pub fn as_page(&self) -> Page {
        unsafe { core::mem::transmute(*self) }
    }
}

#[derive(Debug)]
pub struct MutPage(pub CowPage);

    fn load_page(&self, off: u64) -> Result<Page, Self::Error>;

    fn load_page(&self, off: u64) -> Result<CowPage, Self::Error>;

use log::*;

    debug!("{:?}", cursor.pointer);

        debug!("pointer: {:?}", cursor.pointer);

                    debug!("splitting {:?}", cur.page);

                    let p = txn.alloc_page()?;
                    P::init(p);

                    debug!("splitting the root");
                    let mut p = txn.alloc_page()?;
                    P::init(&mut p);

                        &P::first_cursor(&p.0),

                        &P::first_cursor(p.0.as_page()),

                debug!("ok");

        let mut c = P::first_cursor(&cur.page);
        let left = P::left_child(&cur.page, &c);

        let mut c = P::first_cursor(cur.page.as_page());
        let left = P::left_child(cur.page.as_page(), &c);

        while let Some((k, v, r)) = P::next(&cur.page, &mut c) {

        while let Some((k, v, r)) = P::next(cur.page.as_page(), &mut c) {

#[derive(Debug)]

        self.n = 1; // dirty page

        self.n = (1u16).to_le(); // dirty page

    fn init(page: MutPage) {
        unsafe { (&mut *(page.0.data as *mut Header)).init() }

    fn init(page: &mut MutPage) {
        debug!("init {:?}", page);
        let h = header_mut(page);
        h.init();
        debug!("init: {:?}", h);

    fn clean(page: MutPage) {
        unsafe {
            let hdr = &mut *header_mut(page);
            hdr.n = (u16::from_le(hdr.n) & 0xfff).to_le()
        }

    fn clean(page: &mut MutPage) {
        let hdr = header_mut(page);
        hdr.n = (u16::from_le(hdr.n) & 0xfff).to_le()

        let mut occupied = unsafe {
            let hdr = &*header(&m.page);

        let mut occupied = {
            let hdr = header(m.page.as_page());

        occupied -= Self::current_size(&m.page, &m.c1) as usize;

        if m.skip_first {
            occupied -= Self::current_size(m.page.as_page(), &m.c1) as usize;
        }

            occupied += unsafe { crate::alloc_size(&*k, &*v) as usize };

            occupied += crate::alloc_size(k, v) as usize;

        page: crate::Page,

        page: CowPage,

        unsafe {
            if r == 0 {
                put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, 0, 0)
            } else {
                put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, l, r)
            }

        if r == 0 {
            put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, 0, 0)
        } else {
            put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, l, r)

        page: crate::Page,

        page: CowPage,

        let page = if mutable && Self::is_dirty(page) {

        debug!("update_left_child: {:?} {:?} {:?}", page, mutable, header(page.as_page()));
        let page = if mutable && Self::is_dirty(page.as_page()) {

            MutPage(page)

            unsafe { core::mem::transmute(page) }

            unsafe {
                let new = txn.alloc_page()?;
                <Page<K, V> as BTreeMutPage<T, K, V>>::init(new);
                let s = Internal::offset_slice::<T, K, V>(page);
                let hdr = &mut *header_mut(new);
                let mut n = 0;
                clone::<T, K, V, Internal>(hdr, page, new, s, &mut n);
                let b = if Self::is_dirty(page) { 1 } else { 0 };
                freed = page.offset | b;
                new
            }

            let mut new = txn.alloc_page()?;
            <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);
            let s = Internal::offset_slice::<T, K, V>(page.as_page());
            let mut n = 0;
            clone::<T, 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

    fn del(txn: &mut T, page: crate::Page, c: &Cursor, l: u64) -> Result<MutPage, T::Error> {

    fn del(txn: &mut T, page: crate::CowPage, c: &Cursor, l: u64) -> Result<MutPage, T::Error> {

        if Self::is_dirty(page) {
            let page = MutPage(page);
            unsafe {
                let hdr = header_mut(page);
                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 = page.0.data.add(hdr_size + off);
                        core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur - 1));
                        (&mut *hdr).decr(f);
                    } else {
                        let ptr = page.0.data.add(HDR + c.cur * 2) as *mut u16;
                        let kv_ptr = page.0.data.add((*ptr) as usize);
                        let size = entry_size::<T, K, V>(kv_ptr);
                        core::ptr::copy(ptr.offset(1), ptr, n - c.cur);
                        (&mut *hdr).decr(size);
                    }
                } else {
                    let ptr = page.0.data.add(HDR + c.cur * 8) as *mut u64;
                    let off = (u64::from_le(*ptr) & 0xfff) as usize;
                    let kv_ptr = page.0.data.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);
                };
                if l > 0 {
                    assert!(!c.is_leaf);
                    // Updating the left page if necessary.
                    let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur as isize - 1);

        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;
                 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);
             }};
            if l > 0 {
                assert!(!c.is_leaf);
                // Updating the left page if necessary.
                unsafe {
                    let off = (p as *mut u64).offset(c.cur as isize - 1);

                (&mut *hdr).set_n(u16::from_le((&*hdr).n) - 1);
                Ok(page)

            hdr.set_n(u16::from_le((&*hdr).n) - 1);
            Ok(page)

                let new = txn.alloc_page()?;
                <Page<K, V> as BTreeMutPage<T, K, V>>::init(new);

                let mut new = txn.alloc_page()?;
                <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);

                    let s = Leaf::offset_slice::<T, K, V>(page);

                    let s = Leaf::offset_slice::<T, K, V>(page.as_page());

                    let hdr = &mut *header_mut(new);

                    clone::<T, K, V, Leaf>(hdr, page, new, s0, &mut n);
                    clone::<T, K, V, Leaf>(hdr, page, new, s1, &mut n);

                    clone::<T, K, V, Leaf>(page.as_page(), &mut new, s0, &mut n);
                    clone::<T, K, V, Leaf>(page.as_page(), &mut new, s1, &mut n);

                    let s = Internal::offset_slice::<T, K, V>(page);

                    let s = Internal::offset_slice::<T, K, V>(page.as_page());

                    let hdr = &mut *header_mut(new);

                    clone::<T, K, V, Internal>(hdr, page, new, s0, &mut n);

                    clone::<T, K, V, Internal>(page.as_page(), &mut new, s0, &mut n);

                    clone::<T, K, V, Internal>(hdr, page, new, s1, &mut n);

                    clone::<T, K, V, Internal>(page.as_page(), &mut new, s1, &mut n);

        m: &mut Concat<T, K, V, Self>,

        m: &mut Concat<'a, T, K, V, Self>,

                2 + unsafe { alloc_size::<T, K, V>(&*m.mid.0, &*m.mid.1) }

                2 + alloc_size::<T, K, V>(m.mid.0, m.mid.1)

            8 + unsafe { alloc_size::<T, K, V>(&*m.mid.0, &*m.mid.1) }

            8 + alloc_size::<T, K, V>(m.mid.0, m.mid.1)

        let occupied = unsafe {
            let hdr = &*header(&m.other);

        let occupied = {
            let hdr = header(m.other.as_page());

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

            let new = txn.alloc_page()?;
            <Page<K, V> as BTreeMutPage<T, K, V>>::init(new);

            let mut new = txn.alloc_page()?;
            <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);

                    merge::<_, _, _, Leaf>(new, m)

                    merge::<_, _, _, Leaf>(&mut new, m)

                    merge::<_, _, _, Internal>(new, m)

                    merge::<_, _, _, Internal>(&mut new, m)

            let b0 = if Self::is_dirty(m.modified.page) {

            let b0 = if Self::is_dirty(m.modified.page.as_page()) {

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

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

        let rc = <Page<K, V>>::first_cursor(&m.other);
        let first_size = <Page<K, V>>::current_size(&m.other, &rc);

        let rc = <Page<K, V>>::first_cursor(m.other.as_page());
        let first_size = <Page<K, V>>::current_size(m.other.as_page(), &rc);

            unsafe {
                return Ok(Op::Put(if let Some((k, v, r)) = m.modified.ins {
                    Self::replace(
                        txn,
                        m.modified.page,
                        m.modified.mutable,
                        &m.modified.c1,
                        &*k,
                        &*v,
                        m.modified.l,
                        r,
                    )?
                } else {
                    Put::Ok(Ok {
                        page: Self::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?,
                        freed: 0,
                    })
                }));
            }

            return Ok(Op::Put(if let Some((k, v, r)) = m.modified.ins {
                Self::replace(
                    txn,
                    m.modified.page,
                    m.modified.mutable,
                    &m.modified.c1,
                    &*k,
                    &*v,
                    m.modified.l,
                    r,
                )?
            } else {
                Put::Ok(Ok {
                    page: Self::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?,
                    freed: 0,
                })
            }));

        unsafe {
            if m.modified.c0.is_leaf {
                rebalance::<_, _, _, Leaf>(txn, m)
            } else {
                rebalance::<_, _, _, Internal>(txn, m)
            }

        if m.modified.c0.is_leaf {
            rebalance::<_, _, _, Leaf>(txn, m)
        } else {
            rebalance::<_, _, _, Internal>(txn, m)

        unsafe {
            let hdr = &*header(&page);
            hdr.n & 0x8000 != 0
        }

        header(page).is_dirty()

    fn is_empty(_: &crate::Page, c: &Self::Cursor) -> bool {

    fn is_empty(_: crate::Page, c: &Self::Cursor) -> bool {

    fn first_cursor(p: &crate::Page) -> Self::Cursor {
        unsafe {
            let hdr = &*header(p);
            Cursor {
                cur: 0,
                total: hdr.n() as usize,
                is_leaf: hdr.is_leaf(),
            }

    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 {
        unsafe {
            let hdr = &*header(p);
            let total = hdr.n() as usize;
            Cursor {
                cur: total - 1,
                total,
                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(page: &crate::Page, c: &Self::Cursor) -> (*mut K, *mut V, u64) {

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

                u16::from_le(*(page.data.add(HDR + c.cur * 2) as *const u16)) as usize

                u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize

            let (k, v) = read::<T, K, V>(page.data.add(off as usize));
            (k, v, 0)

            let (k, v) = read::<T, K, V>(page.data.as_ptr().add(off as usize));
            (&*k, &*v, 0)

            let off = u64::from_le(*(page.data.add(HDR) as *const u64).add(c.cur));
            let (k, v) = read::<T, K, V>(page.data.add((off & 0xfff) as usize));
            (k, v, off & !0xfff)

            let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur));
            let (k, v) = read::<T, K, V>(page.data.as_ptr().add((off & 0xfff) as usize));
            (&*k, &*v, off & !0xfff)

    unsafe fn unchecked_current_ptr(page: &crate::Page, c: &Self::Cursor) -> *mut u8 {
        page.data.add(if c.is_leaf {

    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.add(HDR + c.cur * 2) as *const u16)) as usize

                u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize

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

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

    fn current_size(page: crate::Page, c: &Self::Cursor) -> usize {

                            .add(u16::from_le(*(page.data.add(HDR) as *const u16).add(c.cur))

                            .as_ptr()
                            .add(u16::from_le(*(page.data.as_ptr().add(HDR) as *const u16).add(c.cur))

                8 + entry_size::<T, K, V>(page.data.add(
                    (u64::from_le(*(page.data.add(HDR) as *const u64).add(c.cur)) & 0xfff) as usize,

                8 + entry_size::<T, 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 {

    fn move_next(_page: crate::Page, c: &mut Self::Cursor) -> bool {

    fn left_child(page: &crate::Page, c: &Self::Cursor) -> u64 {

    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 {

            let off = unsafe { *(page.data.add((HDR + c.cur * 8) - 8) as *const u64) };

            let off = unsafe { *(page.data.as_ptr().add((HDR + c.cur * 8) - 8) as *const u64) };

    fn right_child(page: &crate::Page, c: &Self::Cursor) -> u64 {

    fn right_child(page: crate::Page, c: &Self::Cursor) -> u64 {

            let off = unsafe { *(page.data.add(HDR + c.cur * 8) as *const u64) };

            let off = unsafe { *(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64) };

        page: &crate::Page,

        page: crate::Page,

    ) -> Result<(&'a mut K, &'a mut V, u64), usize> {

    ) -> Result<(&'a K, &'a V, u64), usize> {

            let hdr = &*header(&page);
            c.total = hdr.n() as usize;

            let lookup = lookup(txn, page, c, k0, v0);

            c.is_leaf = hdr.is_leaf();
            let lookup = if c.is_leaf {
                if fixed_size::<T, 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.add(hdr_size) as *const Tuple<K, V>,
                        hdr.n() as usize,
                    );
                    if let Some(v0) = v0 {
                        s.binary_search_by(|tup| {
                            (tup.k.ord(txn), tup.v.ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
                        })
                    } else {
                        s.binary_search_by(|tup| {
                            (tup.k.ord(txn)).cmp(k0.ord(txn))
                        })
                    }
                } else {
                    let s = core::slice::from_raw_parts(
                        page.data.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>(page.data.offset(off as isize));
                            ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
                        })
                    } else {
                        s.binary_search_by(|&off| {
                            let off = u16::from_le(off);
                            let (k, _) = read::<T, K, V>(page.data.offset(off as isize));
                            ((&*k).ord(txn)).cmp(k0.ord(txn))
                        })
                    }
                }
            } else {
                let s =
                    core::slice::from_raw_parts(page.data.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>(page.data.offset(off as isize & 0xfff));
                        ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
                    })
                } else {
                    s.binary_search_by(|&off| {
                        let off = u64::from_le(off) & 0xfff;
                        let (k, _) = read::<T, K, V>(page.data.offset(off as isize & 0xfff));
                        ((&*k).ord(txn)).cmp(k0.ord(txn))
                    })
                }
            };

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

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

                        Ok(Leaf::kv(*page, off))

                        Ok(Leaf::kv(page, off))

                        let off = u64::from_le(*(page.data.add(HDR + n * 8) as *const u64));
                        Ok(Internal::kv(*page, (off & !0xfff, (off & 0xfff) as u16)))

                        let off = u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));
                        Ok(Internal::kv(page, (off & !0xfff, (off & 0xfff) as u16)))

    fn split_at(_: &crate::Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {

    fn split_at(_: crate::Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {

unsafe fn lookup<T, K: Representable<T>, V: Representable<T>>(
    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 {
        if fixed_size::<T, 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| {
                    (tup.k.ord(txn), tup.v.ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
                })
            } else {
                s.binary_search_by(|tup| {
                    (tup.k.ord(txn)).cmp(k0.ord(txn))
                })
            }
        } else {
            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>(page.data.as_ptr().offset(off as isize));
                    ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
                })
            } else {
                s.binary_search_by(|&off| {
                    let off = u16::from_le(off);
                    let (k, _) = read::<T, K, V>(page.data.as_ptr().offset(off as isize));
                    ((&*k).ord(txn)).cmp(k0.ord(txn))
                })
            }
        }
    } 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>(page.data.as_ptr().offset(off as isize & 0xfff));
                ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
            })
        } else {
            s.binary_search_by(|&off| {
                let off = u64::from_le(off) & 0xfff;
                let (k, _) = read::<T, K, V>(page.data.as_ptr().offset(off as isize & 0xfff));
                ((&*k).ord(txn)).cmp(k0.ord(txn))
            })
        }
    }
}

unsafe fn header(page: &crate::Page) -> *const Header {
    page.data as *const Header

fn header<'a>(page: crate::Page<'a>) -> &'a Header {
    unsafe {
        &*(page.data.as_ptr() as *const Header)
    }

unsafe fn header_mut(page: crate::MutPage) -> *mut Header {
    page.0.data as *mut Header

fn header_mut(page: &mut crate::MutPage) -> &mut Header {
    unsafe {
        &mut *(page.0.data as *mut Header)
    }

    unsafe fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

    unsafe fn can_compact<T, K: Representable<T>, V: Representable<T>>(

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(

    unsafe fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16;
    unsafe fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(
        hdr: &mut Header,
        new: &MutPage,

    fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16;
    // n = number of items to remove
    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize);
    fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(
        new: &mut MutPage,

    unsafe fn set_offset(new: MutPage, n: isize, r: u64, off: u16);
    unsafe fn set_right_child(new: MutPage, n: isize, r: u64);

    fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16);
    fn set_right_child(new: &mut MutPage, n: isize, r: u64);

    unsafe fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(
        page: crate::Page,

    fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(
        page: crate::Page<'a>,

    unsafe fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

    fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

    ) -> (&'a mut K, &'a mut V, u64);

    ) -> (&'a K, &'a V, u64);

            Offsets::Slice(s) => {

            Offsets::Slice(s) if mid < s.len() => {
                debug!("split_at: {:?} {:?}", s.len(), mid);

            }
            Offsets::Slice(s) => {
                debug_assert_eq!(mid, s.len());
                (Offsets::Slice(s), Offsets::Slice(&[][..]))

        }
    }
    fn len(&self) -> usize {
        match self {
            Offsets::Slice(s) => s.len(),
            Offsets::Range(r) => r.end - r.start,

    unsafe fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

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

    unsafe fn can_compact<T, K: Representable<T>, V: Representable<T>>(

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(

    unsafe fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) {
        debug!("truncate_left {:?} {:?}", page, n);
        if let Some(f) = fixed_size::<T, 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();
            unsafe {
                core::ptr::copy(
                    page.0.data.add(hdr_size + n * f),
                    page.0.data.add(hdr_size),
                    n * f,
                );
            }
            debug!("{:?}-{:?}", hdr_n, n);
            let hdr = header_mut(page);
            hdr.set_n(hdr_n - n as u16);
            hdr.left_page = (hdr.left_page() - (n * f) as u64).to_le();
        } else {
            let hdr_n = header_mut(page).n();
            unsafe {
                core::ptr::copy(
                    page.0.data.add(HDR + n * 2),
                    page.0.data.add(HDR),
                    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::<T, 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.left_page = (hdr.left_page() - deleted_size).to_le();
        }
    }
    fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {

        data -= data & ((align - 1) as u16);

        data &= !((align - 1) as u16);

    unsafe fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(
        hdr: &mut Header,
        new: &MutPage,

    fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(
        new: &mut MutPage,

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

            let off_new = Self::alloc(&mut *hdr, size, K::ALIGN);
            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);

            let (hdr_n, off_new) = {
                let hdr = header_mut(new);
                (hdr.n(), Self::alloc(&mut *hdr, 2+size, K::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);

    unsafe fn set_offset(new: MutPage, n: isize, _: u64, off: u16) {
        let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;
        *ptr = off.to_le();

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

    unsafe fn set_right_child(_: MutPage, _: isize, _: u64) {}

    fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}

    unsafe fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(
        page: crate::Page,

    fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(
        page: crate::Page<'a>,

        let hdr = &*header(&page);

        let hdr = header(page);

            Offsets::Slice(core::slice::from_raw_parts(
                page.data.add(HDR) as *const LeafOffset,
                hdr.n() as usize,
            ))

            unsafe {
                Offsets::Slice(core::slice::from_raw_parts(
                    page.data.as_ptr().add(HDR) as *const LeafOffset,
                    hdr.n() as usize,
                ))
            }

    unsafe fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

    fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

    ) -> (&'a mut K, &'a mut V, u64) {
        let (k, v) = read::<T, K, V>(page.data.add(off as usize));
        (&mut *k, &mut *v, 0)

    ) -> (&'a  K, &'a  V, u64) {
        unsafe {
            let (k, v) = read::<T, K, V>(page.data.as_ptr().add(off as usize));
            (& *k, & *v, 0)
        }

    unsafe fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

        debug!("Internal::can_alloc: {:?} {:?}", hdr.n(), hdr.data);

    unsafe fn can_compact<T, K: Representable<T>, V: Representable<T>>(

    fn can_compact<T, K: Representable<T>, V: Representable<T>>(

    unsafe fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {

    fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) {
        // The following line copies the left child of the last entry
        // (hence the `- 8` and `- 1`)
        unsafe {
            core::ptr::copy(
                page.0.data.add(HDR + (n - 1) * 8),
                page.0.data.add(HDR - 8),
                (n + 1) * 8,
            );
        }
        let hdr_n = header_mut(page).n();
        let size = if let Some(f) = fixed_size::<T, K, V>() {
            ((8 + f) * (hdr_n as usize - n)) as u64
        } 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::<T, 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.left_page = ((hdr.left_page() & !0xfff) | size).to_le();
    }
    fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {
        debug!("data = {:?}, size = {:?}", hdr.data, size);

    unsafe fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(
        hdr: &mut Header,
        new: &MutPage,

    fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(
        new: &mut MutPage,

        let off_new = Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN));
        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);

        let (hdr_n, off_new) = {
            let hdr = header_mut(new);
            (hdr.n(), Self::alloc(&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);

    unsafe fn set_offset(new: MutPage, n: isize, r: u64, off: u16) {
        let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;
        *ptr = (r | off as u64).to_le();

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

    unsafe fn set_right_child(page: MutPage, n: isize, r: u64) {
        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();

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

    unsafe fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(
        page: crate::Page,

    fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(
        page: crate::Page<'a>,

        let hdr = &*header(&page);
        Offsets::Slice(core::slice::from_raw_parts(
            page.data.add(HDR) as *const InternalOffset,
            hdr.n() as usize,
        ))

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

    unsafe fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

    fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

    ) -> (&'a mut K, &'a mut V, u64) {
        let (k, v) = read::<T, K, V>(page.data.add(off as usize));
        (&mut *k, &mut *v, r)

    ) -> (&'a  K, &'a  V, u64) {
        unsafe {
            let (k, v) = read::<T, K, V>(page.data.as_ptr().add(off as usize));
            (& *k, & *v, r)
        }

    new: MutPage,

    new: &mut MutPage,

    let hdr = &mut *header_mut(new);
    let mut l = <Page<K, V>>::left_child(&m.page, &m.c0);
    while let Some((k, v, r)) = <Page<K, V>>::next(&m.page, &mut m.c0) {
        alloc::<_, _, _, L>(hdr, new, k, v, l, r, n);

    let mut l = <Page<K, V>>::left_child(m.page.as_page(), &m.c0);
    while let Some((k, v, r)) = <Page<K, V>>::next(m.page.as_page(), &mut m.c0) {
        alloc::<_, _, _, L>(new, k, v, l, r, n);

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

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

    while let Some((k, v, r)) = <Page<K, V>>::next(&m.page, &mut m.c1) {

    while let Some((k, v, r)) = <Page<K, V>>::next(m.page.as_page(), &mut m.c1) {

        alloc::<_, _, _, L>(hdr, new, k, v, l, r, n);

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

    new: MutPage,

    new: &mut MutPage,

    let hdr = &mut *header_mut(new);

        modify::<_, _, _, L>(new, m.modified, &mut n);
        let mut rc = <Page<K, V>>::first_cursor(&m.other);
        let l = <Page<K, V>>::left_child(&m.other, &rc);
        alloc::<_, _, _, L>(hdr, new, &*m.mid.0, &*m.mid.1, 0, l, &mut n);
        while let Some((k, v, r)) = <Page<K, V>>::next(&m.other, &mut rc) {
            alloc::<_, _, _, L>(hdr, new, k, v, 0, r, &mut n);

        modify::<_, _, _, L>(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(m.other.as_page(), &mut rc) {
            alloc::<_, _, _, L>(new, k, v, 0, r, &mut n);

        let mut rc = <Page<K, V>>::first_cursor(&m.other);
        let mut l = <Page<K, V>>::left_child(&m.other, &rc);
        while let Some((k, v, r)) = <Page<K, V>>::next(&m.other, &mut rc) {
            alloc::<_, _, _, L>(hdr, new, k, v, l, r, &mut n);

        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(m.other.as_page(), &mut rc) {
            alloc::<_, _, _, L>(new, k, v, l, r, &mut n);

        alloc::<_, _, _, L>(hdr, new, &*m.mid.0, &*m.mid.1, 0, 0, &mut n);
        modify::<_, _, _, L>(new, m.modified, &mut n);

        alloc::<_, _, _, L>(new, &*m.mid.0, &*m.mid.1, 0, 0, &mut n);
        modify::<_, _, _, L>(new, &mut m.modified, &mut n);

unsafe fn rebalance<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

fn rebalance<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

    m: &mut Concat<T, K, V, Page<K, V>>,

    m: &mut Concat<'a, T, K, V, Page<K, V>>,

    let rc = <Page<K, V>>::first_cursor(&m.other);
    let rl = <Page<K, V>>::left_child(&m.other, &rc);
    let (k, v, r) = <Page<K, V>>::unchecked_current(&m.other, &rc);

    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(m.other.as_page(), &rc) };

    let hdr = &*header(&m.modified.page);

    let new_left = if hdr.is_dirty() {
        let page = MutPage(m.modified.page);
        let hdr = &mut *header_mut(page);

    let new_left = if header(m.modified.page.as_page()).is_dirty() {
        let mut page = unsafe { core::mem::transmute(m.modified.page) };

        alloc::<T, K, V, L>(hdr, page, &*m.mid.0, &*m.mid.1, 0, rl, &mut n);

        alloc::<T, K, V, L>(&mut page, m.mid.0, m.mid.1, 0, rl, &mut n);

        let new = txn.alloc_page()?;
        <Page<K, V> as BTreeMutPage<T, K, V>>::init(new);
        let s = L::offset_slice::<T, K, V>(m.modified.page);
        let hdr = &mut *header_mut(new);

        let mut new = txn.alloc_page()?;
        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);
        let s = L::offset_slice::<T, K, V>(m.modified.page.as_page());

        clone::<T, K, V, L>(hdr, m.modified.page, new, s, &mut n);
        alloc::<T, K, V, L>(hdr, new, &*m.mid.0, &*m.mid.1, 0, rl, &mut n);
        let b = if hdr.is_dirty() { 1 } else { 0 };

        clone::<T, K, V, L>(m.modified.page.as_page(), &mut new, s, &mut n);
        alloc::<T, K, V, L>(&mut new, m.mid.0, m.mid.1, 0, rl, &mut n);
        let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };

        let hdr = &*header(&m.other);

        let hdr = &*header(m.other.as_page());

        k,
        v,

        k: unsafe { core::mem::transmute(k) },
        v: unsafe { core::mem::transmute(v) },

unsafe fn clone<T, K: Representable<T>, V: Representable<T>, L: Alloc>(
    hdr: &mut Header,

fn clone<T, K: Representable<T>, V: Representable<T>, L: Alloc>(

    new: MutPage,

    new: &mut MutPage,

                let off = u16::from_le(off);
                let ptr = page.data.add(off as usize);
                let size = entry_size::<T, K, V>(ptr);
                let off_new = L::alloc(&mut *hdr, size, K::ALIGN);
                core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);
                L::set_offset(new, *n, r, off_new);

                debug!("clone: {:?} {:?}", r, off);
                unsafe {
                    let ptr = page.data.as_ptr().add(off as usize);
                    let size = entry_size::<T, K, V>(ptr);
                    debug!("size: {:?}", size);
                    let hdr = header_mut(new);
                    let off_new = L::alloc(hdr, size, K::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);
                }

            let len = r.len();

                let ptr = page.data.add(header_size + off * size);
                let new_ptr = new.0.data.add(header_size + (*n as usize) * size);
                core::ptr::copy_nonoverlapping(ptr, new_ptr, size);
                hdr.set_n(hdr.n() + 1);
                hdr.left_page = (hdr.left_page() + size as u64).to_le();

                unsafe {
                    let ptr = page.data.as_ptr().add(header_size + off * size);
                    let new_ptr = new.0.data.add(header_size + (*n as usize) * size);
                    core::ptr::copy_nonoverlapping(ptr, new_ptr, size);
                }

            let hdr = header_mut(new);
            hdr.set_n(hdr.n() + len as u16);
            hdr.left_page = (hdr.left_page() + (size * len) as u64).to_le();

unsafe fn alloc<T, K: Representable<T>, V: Representable<T>, L: Alloc>(
    hdr: &mut Header,
    new: MutPage,

fn alloc<T, K: Representable<T>, V: Representable<T>, L: Alloc>(
    new: &mut MutPage,

    let off_new = L::alloc_insert::<T, K, V>(hdr, &new, n, size, r);
    let new_ptr = new.0.data.add(off_new as usize);
    core::ptr::copy_nonoverlapping(k0, new_ptr as *mut K, 1);
    let ks = k0.size();
    let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));
    core::ptr::copy_nonoverlapping(v0, v_ptr as *mut V, 1);

    let off_new = L::alloc_insert::<T, K, V>(new, n, size, r);
    unsafe {
        let new_ptr = new.0.data.add(off_new as usize);
        core::ptr::copy_nonoverlapping(k0, new_ptr as *mut K, 1);
        let ks = k0.size();
        let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));
        core::ptr::copy_nonoverlapping(v0, v_ptr as *mut V, 1);
    }

unsafe fn put<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

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

    page: crate::Page,

    page: CowPage,

    let hdr = &*header(&page);
    if mutable && hdr.is_dirty() && L::can_alloc::<T, K, V>(&*header(&page), size) {
        let page = MutPage(page);
        let hdr = &mut *header_mut(page);

    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::<T, K, V>(header(page.as_page()), size) {
        debug!("can alloc");
        let mut page = unsafe { core::mem::transmute(page) };

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

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

        let new = txn.alloc_page()?;
        <Page<K, V> as BTreeMutPage<T, K, V>>::init(new);
        let s = L::offset_slice::<T, K, V>(page);

        let mut new = txn.alloc_page()?;
        debug!("can compact: {:?}", new);
        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);
        L::set_right_child(&mut new, -1, hdr.left_page & !0xfff);
        let s = L::offset_slice::<T, K, V>(page.as_page());

        let hdr = &mut *header_mut(new);

        clone::<T, K, V, L>(hdr, page, new, s0, &mut n);
        alloc::<T, K, V, L>(hdr, new, k0, v0, l, r, &mut n);
        clone::<T, K, V, L>(hdr, page, new, s1, &mut n);
        let b0 = if hdr.is_dirty() { 1 } else { 0 };

        clone::<T, K, V, L>(page.as_page(), &mut new, s0, &mut n);
        alloc::<T, K, V, L>(&mut new, k0, v0, l, r, &mut n);
        clone::<T, K, V, L>(page.as_page(), &mut new, s1, &mut n);
        let b0 = if is_dirty { 1 } else { 0 };

        debug!("split");

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

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

unsafe fn split<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

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

    page: crate::Page,

    page: CowPage,

    let left;
    let right = txn.alloc_page()?;
    <Page<K, V> as BTreeMutPage<T, K, V>>::init(right);
    let hdr = &*header(&page);

    let mut left;
    let hdr = header(page.as_page());

    let s = L::offset_slice::<T, K, V>(page);

    let s = L::offset_slice::<T, K, V>(page.as_page());

        let (k, v, r) = L::kv(page, s1a.first::<T, K, V>());

        let (k, v, r) = L::kv(page.as_page(), s1a.first::<T, K, V>());

    if mutable && hdr.is_dirty() && u >= k as usize {
        // (k0, v0) is to be inserted on the right-hand side of
        // the split, hence we don't have to clone the left-hand
        // side, we can just truncate it.
        let hdr = &mut *header_mut(MutPage(page));
        left = MutPage(page);
        hdr.set_n(k);
        hdr.decr((n - 1 - k) as usize * size);

    if u >= k as usize {
        if mutable && hdr.is_dirty() {
            debug!("mutable dirty {:?} >= {:?}", u, k);
            // (k0, v0) is to be inserted on the right-hand side of
            // the split, hence we don't have to clone the left-hand
            // side, we can just truncate it.
            left = unsafe { core::mem::transmute(page) };
            let hdr = header_mut(&mut left);
            hdr.set_n(k);
            hdr.decr((n - 1 - k) as usize * size);
        } else {
            left = txn.alloc_page()?;
            debug!("immutable {:?} >= {:?}", u, k);
            let mut n = 0;
            clone::<T, K, V, L>(page.as_page(), &mut left, s0, &mut n);
            freed = page.offset | page_is_dirty
        }
        // If we are here, u >= k, i.e. the insertion is in the right-hand
        // side of the split.
        let mut n = 0;
        let mut right = txn.alloc_page()?;
        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut right);
        if u > k as usize {
            let kk = u as usize - k as usize - 1;
            let (s1a, s1b) = s1.split_at(kk);
            L::set_right_child(&mut right, -1, mid_child);
            clone::<T, K, V, L>(page.as_page(), &mut right, s1a, &mut n);
            alloc::<T, K, V, L>(&mut right, k0, v0, l, r, &mut n);
            clone::<T, K, V, L>(page.as_page(), &mut right, s1b, &mut n);
        } else {
            // Insertion in the middle.
            L::set_right_child(&mut right, -1, mid_child);
            clone::<T, K, V, L>(page.as_page(), &mut right, s1, &mut n);
        }
        Ok(Put::Split {
            split_key,
            split_value,
            left,
            right,
            freed,
        })

        <Page<K, V> as BTreeMutPage<T, K, V>>::init(left);
        if u < k as usize {
            let mut n = 0;
            let hdr = &mut *header_mut(left);
            // debug!("{:?} {:?}", u, k);
            let (s0a, s0b) = s1.split_at(k as usize - u as usize);
            clone::<T, K, V, L>(hdr, page, left, s0a, &mut n);
            alloc::<T, K, V, L>(hdr, left, k0, v0, r, l, &mut n);
            clone::<T, K, V, L>(hdr, page, left, s0b, &mut n);
            let hdr = &mut *header_mut(right);
            let mut n = 0;
            L::set_right_child(right, -1, mid_child);
            clone::<T, K, V, L>(hdr, page, right, s1, &mut n);
            return Ok(Put::Split {
                split_key,
                split_value,
                left,
                right,
                freed: page.offset | page_is_dirty,
            });

        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);
        debug!("{:?} < {:?}", u, k);
        let mut n = 0;
        let mid = k as usize - u as usize;
        let (s0a, s0b) = s0.split_at(mid);
        clone::<T, K, V, L>(page.as_page(), &mut left, s0a, &mut n);
        alloc::<T, K, V, L>(&mut left, k0, v0, r, l, &mut n);
        clone::<T, K, V, L>(page.as_page(), &mut left, s0b, &mut n);
        let mut right: MutPage;
        let freed;
        if mutable && hdr.is_dirty() {
            right = unsafe { core::mem::transmute(page) };
            L::truncate_left::<T, K, V>(&mut right, k as usize);
            freed = 0;

            let hdr = &mut *header_mut(left);

            right = txn.alloc_page()?;
            <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut right);

            clone::<T, K, V, L>(hdr, page, left, s0, &mut n);

            L::set_right_child(&mut right, -1, mid_child);
            clone::<T, K, V, L>(page.as_page(), &mut right, s1, &mut n);

        Ok(Put::Split {
            split_key,
            split_value,
            left,
            right,
            freed,
        })

    // If we are here, u > k, i.e. the insertion is in the right-hand
    // side of the split.
    let hdr = &mut *header_mut(right);
    let mut n = 0;
    let kk = u as usize - k as usize;
    let (s1a, s1b) = if kk < s1.len() {
        s1.split_at(kk)
    } else {
        (s1, Offsets::Slice(&[][..]))
    };
    L::set_right_child(right, -1, mid_child);
    clone::<T, K, V, L>(hdr, page, right, s1a, &mut n);
    alloc::<T, K, V, L>(hdr, right, k0, v0, l, r, &mut n);
    clone::<T, K, V, L>(hdr, page, right, s1b, &mut n);
    Ok(Put::Split {
        split_key,
        split_value,
        left,
        right,
        freed,
    })

unsafe fn split_unsized<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

fn split_unsized<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

    fn first_cursor(p: &Page) -> Self::Cursor;
    fn last_cursor(p: &Page) -> Self::Cursor;
    fn next<'b>(p: &Page, c: &mut Self::Cursor) -> Option<(&'b mut K, &'b mut V, u64)> {
        unsafe {
            if let Some((k, v, r)) = Self::current(p, c) {
                Self::move_next(p, c);
                Some((&mut *k, &mut *v, r))
            } else {
                None
            }

    fn first_cursor(p: Page) -> Self::Cursor;
    fn last_cursor(p: Page) -> Self::Cursor;
    fn next<'b>(p: Page<'b>, c: &mut Self::Cursor) -> Option<(&'b K, &'b V, u64)> {
        if let Some((k, v, r)) = Self::current(p, c) {
            Self::move_next(p, c);
            Some((k, v, r))
        } else {
            None

    fn move_next<'b>(p: &Page, c: &mut Self::Cursor) -> bool;
    unsafe fn unchecked_current(p: &Page, c: &Self::Cursor) -> (*mut K, *mut V, u64);
    unsafe fn current(p: &Page, c: &Self::Cursor) -> Option<(*mut K, *mut V, u64)> {

    fn prev<'b>(p: Page<'b>, c: &mut Self::Cursor) -> Option<(&'b K, &'b V, u64)> {
        if Self::move_prev(p, c) {
            Self::current(p, c)
        } else {
            None
        }
    }
    fn move_next(p: Page, c: &mut Self::Cursor) -> bool;
    fn move_prev(p: Page, c: &mut Self::Cursor) -> bool;
    unsafe fn unchecked_current<'a>(p: Page<'a>, c: &Self::Cursor) -> (&'a K, &'a V, u64);
    fn current<'a>(p: Page<'a>, c: &Self::Cursor) -> Option<(&'a K, &'a V, u64)> {

            Some(Self::unchecked_current(p, c))

            unsafe {
                Some(Self::unchecked_current(p, c))
            }

    unsafe fn unchecked_current_ptr(p: &Page, c: &Self::Cursor) -> *mut u8;
    fn current_size(p: &Page, c: &Self::Cursor) -> usize;
    fn left_child(p: &Page, c: &Self::Cursor) -> u64;
    fn right_child(p: &Page, c: &Self::Cursor) -> u64;

    unsafe fn unchecked_current_ptr(p: Page, c: &Self::Cursor) -> *const u8;
    fn current_size(p: Page, c: &Self::Cursor) -> usize;
    fn left_child(p: Page, c: &Self::Cursor) -> u64;
    fn right_child(p: Page, c: &Self::Cursor) -> u64;

        page: &Page,

        page: Page,

    ) -> Result<(&'a mut K, &'a mut V, u64), usize>;
    fn split_at(p: &Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor);
    fn is_empty(p: &Page, c: &Self::Cursor) -> bool;

    ) -> Result<(&'a  K, &'a  V, u64), usize>;
    fn split_at(p: Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor);
    fn is_empty(p: Page, c: &Self::Cursor) -> bool;

    page: &'a Page,

    page: Page<'a>,

    type Item = (&'a mut K, &'a mut V, u64);

    type Item = (&'a K, &'a V, u64);

    fn init(page: MutPage);
    fn clean(page: MutPage);

    fn init(page: &mut MutPage);
    fn clean(page: &mut MutPage);

        page: Page,

        page: CowPage,

        page: Page,

        page: CowPage,

    fn del(txn: &mut T, page: Page, c: &Self::Cursor, l: u64) -> Result<MutPage, T::Error>;

    fn del(txn: &mut T, page: CowPage, c: &Self::Cursor, l: u64) -> Result<MutPage, T::Error>;

        page: Page,

        page: CowPage,

    fn merge_or_rebalance<'a>(

    fn merge_or_rebalance<'a, 'b>(

        m: &mut Concat<T, K, V, Self>,

        m: &'b mut Concat<'a, T, K, V, Self>,

        m: &mut ModifiedPage<T, K, V, Self>,

        m: &mut ModifiedPage<'a, T, K, V, Self>,

        unsafe {
            if let Some((k, v, r)) = m.ins {
                if m.skip_first {
                    Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)
                } else {
                    Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)
                }

        if let Some((k, v, r)) = m.ins {
            if m.skip_first {
                Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)

                let page = Self::del(txn, m.page, &m.c1, m.l)?;
                Ok(Put::Ok(Ok {
                    page,
                    freed: if page.0.offset != m.page.offset {
                        m.page.offset
                    } else {
                        0
                    },
                }))

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

        } else {
            let page = Self::del(txn, m.page, &m.c1, m.l)?;
            Ok(Put::Ok(Ok {
                freed: if page.0.offset != m.page.offset {
                    m.page.offset
                } else {
                    0
                },
                page,
            }))

        k: *mut K,
        v: *mut V,

        k: &'a K,
        v: &'a V,

        'a,

    pub page: Page,

    pub page: CowPage,

    pub ins: Option<(*const K, *const V, u64)>,

    pub ins: Option<(&'a K, &'a V, u64)>,

impl<T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>
    ModifiedPage<T, K, V, P>

impl<'a, T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>
    ModifiedPage<'a, T, K, V, P>

            P::move_next(&self.page, &mut c1);

            P::move_next(self.page.as_page(), &mut c1);

        if P::is_empty(&self.page, &self.c0) && self.ins.is_none() && P::is_empty(&self.page, &c1) {

        if P::is_empty(self.page.as_page(), &self.c0) && self.ins.is_none() && P::is_empty(self.page.as_page(), &c1) {

    pub mid: (*mut K, *mut V),
    pub modified: &'a mut ModifiedPage<T, K, V, P>,
    pub other: Page,

    pub mid: (&'a K, &'a V),
    pub modified: ModifiedPage<'a, T, K, V, P>,
    pub other: CowPage,

    pub db: Page,

    pub db: CowPage,

    let page = txn.alloc_page()?;
    P::init(page);

    let mut page = txn.alloc_page()?;
    P::init(&mut page);

use log::*;

    T: AllocPage + LoadPage,
    K: Representable<T>,
    V: Representable<T>,

    T: AllocPage + LoadPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,

    T: AllocPage + LoadPage,
    K: Representable<T>,
    V: Representable<T>,

    T: AllocPage + LoadPage + core::fmt::Debug,
    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,

    let (c0, c1) = P::split_at(&curs0.page, curs0.cursor.as_ref().unwrap());

    let (c0, c1) = P::split_at(curs0.page.as_page(), curs0.cursor.as_ref().unwrap());

        P::move_next(&curs0.page, &mut c1);

        P::move_next(curs0.page.as_page(), &mut c1);

            P::next(&curs0.page, &mut c0).or_else(|| P::next(&curs0.page, &mut c1))

            P::next(curs0.page.as_page(), &mut c0).or_else(|| P::next(curs0.page.as_page(), &mut c1))

            let (k, v, _) = P::unchecked_current(&curs0.page, &c0);

            let (k, v, _) = P::unchecked_current(curs0.page.as_page(), &c0);

    debug!("cursor.pointer = {:?}", cursor.pointer);

        let ref curs = cursor.current();

        let mut concat = {
            let p = cursor.pointer;
            let curs = cursor.current_mut();
            concat(txn, curs, if p == p0 { Some(&curs0) } else { None }, last_op)?
        };
        let curs = cursor.current();
        debug!("candidate: {:?}", concat);

        let mut concat = concat(txn, &cursor, &curs0, p0, &mut last_op)?;
        let (c0, c1) = P::split_at(&curs.page, c);

        let (c0, c1) = P::split_at(curs.page.as_page(), c);

                if cursor.pointer < cursor.first_rc_level {
                    free[cursor.pointer] = freed;
                }

                let page = txn.alloc_page()?;
                P::init(page);

                let mut page = txn.alloc_page()?;
                P::init(&mut page);

                    &P::first_cursor(&page.0),

                    &P::first_cursor(page.0.as_page()),

    let mut left_page = P::right_child(&cur.page, cur.cursor.as_ref().unwrap());

    let mut left_page = P::right_child(cur.page.as_page(), cur.cursor.as_ref().unwrap());

        let curs = P::first_cursor(&page);
        left_page = P::left_child(&page, &curs);

        let curs = P::first_cursor(page.as_page());
        left_page = P::left_child(page.as_page(), &curs);

    cursor: &Cursor<T, K, V, P>,
    curs0: &PageCursor<T, K, V, P>,
    p0: usize,
    last_op: &'a mut ModifiedPage<T, K, V, P>,

    curs: &mut PageCursor<T, K, V, P>,
    curs0: Option<&PageCursor<T, K, V, P>>,
    last_op: ModifiedPage<'a, T, K, V, P>,

    let ref curs = cursor.current();
    let c = curs.cursor.as_ref().unwrap();
    if cursor.pointer == p0 {
        let other = txn.load_page(P::left_child(&curs.page, c))?;

    let c = curs.cursor.as_mut().unwrap();
    if let Some(curs0) = curs0 {
        let other = txn.load_page(P::left_child(curs.page.as_page(), c))?;

            unsafe { P::unchecked_current(&curs0.page, curs0.cursor.as_ref().unwrap()) };

            unsafe { P::unchecked_current(curs0.page.as_page(), curs0.cursor.as_ref().unwrap()) };

            mid: (k, v),

            mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v)) },

        let (k, v, r) = unsafe { P::unchecked_current(&curs.page, c) };

        let mut mod_is_left = true;
        let (k, v, r) = if let Some(x) = P::current(curs.page.as_page(), c) {
            x
        } else {
            mod_is_left = false;
            let (k, v, _) = P::prev(curs.page.as_page(), c).unwrap();
            let l = P::left_child(curs.page.as_page(), c);
            debug!("prev: {:?}", l);
            (k, v, l)
        };

            mid: (k, v),

            mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v))},

            mod_is_left: true,

            mod_is_left,

    let mut left = P::left_child(&m.page, &c0);
    while let Some((k, v, r)) = P::next(&m.page, &mut c0) {

    let mut left = P::left_child(m.page.as_page(), &c0);
    while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c0) {

        P::move_next(&m.page, &mut c1);

        P::move_next(m.page.as_page(), &mut c1);

    while let Some((k, v, r)) = P::next(&m.page, &mut c1) {

    while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c1) {

use crate::{LoadPage, Page};

use crate::{LoadPage, CowPage};

    pub page: Page,

    pub page: CowPage,

impl<'a, T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>

impl<T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>

    pub fn set(

    pub fn current_mut(&mut self) -> &mut PageCursor<T, K, V, P> {
        unsafe { &mut *self.stack[self.pointer].as_mut_ptr() }
    }
    pub fn set<'a>(

    ) -> Result<Option<(&'a mut K, &'a mut V)>, T::Error> {

    ) -> Result<Option<(&'a K, &'a V)>, T::Error> {

            debug!("p: {:?}", self.pointer);

                current.cursor = Some(P::first_cursor(&page));

                current.cursor = Some(P::first_cursor(page.as_page()));

                if let Ok((kk, vv, _)) = P::set_cursor(txn, &page, cursor, k, v) {

                if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), cursor, k, v) {

            let next_page = P::left_child(&page, cursor);

            let next_page = P::left_child(page.as_page(), cursor);
            debug!("next_page = {:?}", next_page);

                unsafe {
                    *self.stack.get_unchecked_mut(self.pointer) = MaybeUninit::new(PageCursor {
                        page: txn.load_page(next_page)?,
                        cursor: None,
                    });
                }

                debug!("p+ = {:?}", self.pointer);
                self.stack[self.pointer] = MaybeUninit::new(PageCursor {
                    page: txn.load_page(next_page)?,
                    cursor: None,
                });

                debug!("last p = {:?}", self.pointer);

            debug!("last_matching {:?}", last_matching_page);

            debug!("pointer {:?}", self.pointer);

    pub fn set_last(&mut self, txn: &'a T) -> Result<Option<(&'a K, &'a V)>, T::Error> {

    pub fn set_last<'a>(&mut self, txn: &'a T) -> Result<Option<(&'a K, &'a V)>, T::Error> {

                current.cursor = Some(P::last_cursor(&current.page));

                current.cursor = Some(P::last_cursor(current.page.as_page()));

            let (k, v, r) = unsafe { P::unchecked_current(&current.page, cursor) };

            let (k, v, r) = unsafe { P::unchecked_current(current.page.as_page(), cursor) };

        Ok(last_match.map(|(k, v)| unsafe { (&*k, &*v) }))

        Ok(last_match.map(|(k, v)| unsafe { (core::mem::transmute(k), core::mem::transmute(v)) }))

    pub fn next<L: LoadPage>(

    pub fn next<'a, L: LoadPage>(

    ) -> Result<Option<(&mut K, &mut V)>, L::Error> {

    ) -> Result<Option<(&K, &V)>, L::Error> {

                    if let Some((k, v, r)) = P::next(&current.page, c) {

                    if let Some((k, v, r)) = P::next(current.page.as_page(), c) {

                        return Ok(Some((&mut *k, &mut *v)));

                        return Ok(Some((& *k, & *v)));

                    current.cursor = Some(P::first_cursor(&current.page));

                    current.cursor = Some(P::first_cursor(current.page.as_page()));

                    let left = P::left_child(&current.page, cursor);

                    let left = P::left_child(current.page.as_page(), cursor);

use lmdb_rs::*;

use sanakirja_core::btree;
use sanakirja_core::*;

mod debug;

type B = sanakirja_core::btree::page::Page<u64, u64>;

type B<T> = btree::page::Page<u64, A<T>>;

#[derive(Eq, PartialEq, PartialOrd, Ord)]
struct A<T>([u64; 100], std::marker::PhantomData<T>);
impl<T> std::fmt::Debug for A<T> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(fmt, "A(…)")?;
        Ok(())
    }
}
impl<T> Representable<T> for A<T> {
    type PageOffsets = core::iter::Empty<u64>;
    fn page_offsets(&self) -> Self::PageOffsets {
        core::iter::empty()
    }
    const ALIGN: usize = core::mem::align_of::<Self>();
    const SIZE: Option<usize> = Some(core::mem::size_of::<Self>());
    type Ord = [u64; 100];
    fn ord(&self, _: &T) -> &Self::Ord {
        &self.0
    }
    fn size(&self) -> usize {
        core::mem::size_of::<Self>()
    }
}
type T<'a> = MutTxn<&'a Env<Exclusive>, ()>;

    #[test]

        env_logger::try_init().unwrap_or(());

        let mut db = create_db::<MutTxn<&Env<Exclusive>, ()>, u64, u64, B>(&mut txn).unwrap();
        let n = 1_000_000u64;

        let mut db = create_db::<MutTxn<&Env<Exclusive>, ()>, u64, A<T>, B<T>>(&mut txn).unwrap();
        let n = 501;

            put(&mut txn, &mut db, &((i * i) % 1_000_000), &(i * i * i)).unwrap();

            let a = A([i * i * i; 100], std::marker::PhantomData);
            put(&mut txn, &mut db, &((i * i) % 1_000_000), &a).unwrap();

        for i in 0..n {
            debug!("put {:?}", i);
            put(&mut txn, &mut db, &((i * i) % 1_000_000), &(i * i * i)).unwrap();
        }

        let i = 500;
        debug!("deleting {:?}", (i*i)%1_000_000);
        del(&mut txn, &mut db, &((i * i) % 1_000_000), None).unwrap();
        debug::debug(&txn, &db, "debug", true);
        /*

            debug!("put {:?}", i);
            btree.insert(i*i, i*i*i);

            btree.insert(i * i, i * i * i);

        */

use sanakirja_core::{btree, MutPage, Page};

use sanakirja_core::{btree, CowPage, MutPage};

impl<E:Borrow<Env<Exclusive>>, T> std::fmt::Debug for MutTxn<E, T> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(fmt, "MutTxn {{ }}")
    }
}

    free: Page,

    free: CowPage,

    fn commit(self) -> Result<(), Error> {

    fn commit(mut self) -> Result<(), Error> {

            .extend(self.occupied_owned_pages.iter().cloned());

            .extend(self.occupied_owned_pages.drain(..));

                let free = Page {

                let free = CowPage {

                        db: Page {

                        db: CowPage {

                    Page {

                    CowPage {

        if let Some(page) = self.free_owned_pages.pop() {
            let page = MutPage(Page {
                data: unsafe { self.env.borrow().find_offset(page) },
                offset: page,
            });
            self.occupied_owned_pages.push(page);

        if let Some(offset) = self.free_owned_pages.pop() {
            let data = unsafe { self.env.borrow().find_offset(offset) };
            let page = MutPage(CowPage { data, offset });
            self.occupied_owned_pages
                .push(MutPage(CowPage { data, offset }));

            if let Some(page) = self.free_pages_pop()? {
                let page = MutPage(Page {
                    data: unsafe { self.env.borrow().find_offset(page) },
                    offset: page,
                });
                self.occupied_owned_pages.push(page);

            if let Some(offset) = self.free_pages_pop()? {
                let data = unsafe { self.env.borrow().find_offset(offset) };
                let page = MutPage(CowPage { data, offset });
                self.occupied_owned_pages
                    .push(MutPage(CowPage { offset, data }));

                let last = self.length;

                let offset = self.length;

                let page = MutPage(Page {
                    data: unsafe { self.env.borrow().find_offset(last) },
                    offset: last,

                let data = unsafe { self.env.borrow().find_offset(offset) };
                let page = MutPage(CowPage {
                    data,
                    offset,

                self.occupied_owned_pages.push(page);

                self.occupied_owned_pages.push(MutPage(CowPage { data, offset }));

            if let Some((rc, ())) = curs.next(self)? {
                let off_ = *rc & !0xfff;
                if off_ == off {
                    let r = *rc & 0xfff;
                    if r > 2 {
                        *rc = off_ | (r - 1);
                    } else {
                        btree::del(self, &mut rc_, rc, None)?;
                    }
                    self.rc = Some(rc_);
                    return Ok(());

            let rc = if let Some((rc, ())) = curs.next(self)? {
                if *rc & !0xfff == off {
                    *rc
                } else {
                    1

            } else {
                1
            };
            if rc & 0xfff >= 2 {
                btree::del(self, &mut rc_, &rc, None)?;
                if rc > 2 {
                    btree::put(self, &mut rc_, &(rc - 1), &())?;
                }
                return Ok(())

        let mut rc_del = 0;