pub trait Representable<T> {

pub trait Representable {

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

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

    unsafe fn from_raw_ptr<'a, T>(txn: &T, p: *const u8) -> &'a Self;

        impl<T> Representable<T> for $t {

        impl Representable for $t {

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

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

            unsafe fn from_raw_ptr<'a, T>(_: &T, p: *const u8) -> &'a Self {
                &*(p as *const Self)
            }

direct_repr!(u32);
direct_repr!(i32);

direct_repr!(i64);

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

unsafe fn read<T, K: Representable, V: Representable>(txn: &T, k: *const u8) -> (*const u8, *const u8) {
    let s = K::size(K::from_raw_ptr(txn, k));

    (k, v as *const V)

    (k, v)

fn alloc_size<T, K: Representable<T>, V: Representable<T>>(k: &K, v: &V) -> usize {

fn alloc_size<K: Representable, V: Representable>(k: &K, v: &V) -> usize {

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

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

pub fn put<T: AllocPage, K: Representable<T>, V: Representable<T>, P: BTreeMutPage<T, K, V>>(

pub fn put<T: AllocPage, K: Representable, V: Representable, P: BTreeMutPage<K, V>>(

    db: &mut Db_<T, K, V, P>,

    db: &mut Db_<K, V, P>,

fn put_cascade<T: AllocPage, K: Representable<T>, V: Representable<T>, P: BTreeMutPage<T, K, V>>(

fn put_cascade<T: AllocPage, K: Representable, V: Representable, P: BTreeMutPage<K, V>>(

    cursor: &mut Cursor<T, K, V, P>,

    cursor: &mut Cursor<K, V, P>,

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

    K: Representable,
    V: Representable,
    P: BTreePage<K, V>,

    cursor: &mut Cursor<T, K, V, P>,

    cursor: &mut Cursor<K, V, P>,

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

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

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
#[repr(C)]
struct Tuple<K, V> {
    k: K,
    v: V,
}

        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>

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

    fn size(m: &ModifiedPage<T, K, V, Self>) -> usize {

    fn size(m: &ModifiedPage<K, V, Self>) -> usize {

        if fixed_size::<T, K, V>().is_some() && m.c1.is_leaf {

        if fixed_size::<K, V>().is_some() && m.c1.is_leaf {

                if fixed_size::<T, K, V>().is_none() {

                if fixed_size::<K, V>().is_none() {

    fn put<'a>(

    fn put<'a, T: AllocPage>(

    fn replace<'a>(

    fn replace<'a, T: AllocPage>(

    fn update_left_child(

    fn update_left_child<T: AllocPage>(

            <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);

            <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);

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

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

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

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

                    if let Some(f) = fixed_size::<T, K, V>() {

                    if let Some(f) = fixed_size::<K, V>() {

                        let size = entry_size::<T, K, V>(kv_ptr);

                        let size = entry_size::<K, V>(kv_ptr);

                    let size = entry_size::<T, K, V>(kv_ptr);
                    core::ptr::copy(ptr.offset(1), ptr, (&*hdr).n() as usize - c.cur);

                    let size = entry_size::<K, V>(kv_ptr);
                    core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur);

                <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);

                <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);

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

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

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

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

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

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

    fn merge_or_rebalance<'a>(

    fn merge_or_rebalance<'a, T: AllocPage>(

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

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

            if let Some(f) = fixed_size::<T, K, V>() {

            if let Some(f) = fixed_size::<K, V>() {

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

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

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

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

            <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);

            <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);

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

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

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

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

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

impl<K: Representable, V: Representable> super::BTreePage<K, V>

    unsafe fn unchecked_current<'a>(

    unsafe fn unchecked_current<'a, T: LoadPage>(
        txn: &T,

            let off = if let Some(f) = fixed_size::<T, K, V>() {

            let off = if let Some(f) = fixed_size::<K, V>() {

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

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

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

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

            if let Some(f) = fixed_size::<T, K, V>() {

            if let Some(f) = fixed_size::<K, V>() {

                if let Some(f) = fixed_size::<T, K, V>() {

                if let Some(f) = fixed_size::<K, V>() {

                    2 + entry_size::<T, K, V>(page.data.as_ptr().add(u16::from_le(

                    2 + entry_size::<K, V>(page.data.as_ptr().add(u16::from_le(

                8 + entry_size::<T, K, V>(page.data.as_ptr().add(

                8 + entry_size::<K, V>(page.data.as_ptr().add(

    fn set_cursor<'a>(

    fn set_cursor<'a, T: LoadPage>(

                        let off = if let Some(f) = fixed_size::<T, K, V>() {

                        let off = if let Some(f) = fixed_size::<K, V>() {

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

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

                        Ok(Internal::kv(page, (off & !0xfff, (off & 0xfff) as u16)))

                        Ok(Internal::kv(txn, page, (off & !0xfff, (off & 0xfff) as u16)))

fn fixed_size<T, K: Representable<T>, V: Representable<T>>() -> Option<usize> {

fn fixed_size<K: Representable, V: Representable>() -> Option<usize> {

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

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

        if fixed_size::<T, K, V>().is_some() {

        if fixed_size::<K, V>().is_some() {

                    let (k, v) = read::<T, K, V>(page.data.as_ptr().offset(off as isize));
                    match (&*k).compare(txn, k0) {
                        Ordering::Equal => (&*v).compare(txn, v0),

                    let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
                    let k = K::from_raw_ptr(txn, k as *const u8);
                    match k.compare(txn, k0) {
                        Ordering::Equal => {
                            let v = V::from_raw_ptr(txn, v as *const u8);
                            v.compare(txn, v0)
                        },

                    let (k, _) = read::<T, K, V>(page.data.as_ptr().offset(off as isize));
                    (&*k).compare(txn, k0)

                    let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
                    let k = K::from_raw_ptr(txn, k);
                    k.compare(txn, k0)

                let (k, v) = read::<T, K, V>(page.data.as_ptr().offset(off as isize & 0xfff));
                match (&*k).compare(txn, k0) {
                    Ordering::Equal => (&*v).compare(txn, v0),

                let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
                let k = K::from_raw_ptr(txn, k);
                match k.compare(txn, k0) {
                    Ordering::Equal => {
                        let v = V::from_raw_ptr(txn, v);
                        v.compare(txn, v0)
                    },

                let (k, _) = read::<T, K, V>(page.data.as_ptr().offset(off as isize & 0xfff));
                (&*k).compare(txn, k0)

                let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
                let k = K::from_raw_ptr(txn, k);
                k.compare(txn, k0)

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

    T: LoadPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

>(

    >(
    txn: &T,

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

    m: &mut ModifiedPage<K, V, Page<K, V>>,

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

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

            alloc::<_, _, _, L>(new, k, v, 0, 0, n);
            alloc::<_, _, _, L>(new, k2, v2, m.l, m.r, n);

            alloc::<_, _, L>(new, k, v, 0, 0, n);
            alloc::<_, _, L>(new, k2, v2, m.l, m.r, n);

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

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

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

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

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

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

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

    T: LoadPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

>(

    >(
    txn: &T,

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

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

        modify::<_, _, _, L>(new, &mut m.modified, &mut n);

        modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);

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

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

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

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

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

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

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

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

                    let size = entry_size::<T, K, V>(ptr);

                    let size = entry_size::<K, V>(ptr);

            let size = fixed_size::<T, K, V>().unwrap();

            let size = fixed_size::<K, V>().unwrap();

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

fn alloc<K: Representable, V: Representable, L: Alloc>(

    let off_new = L::alloc_insert::<T, K, V>(new, n, size, r);

    let off_new = L::alloc_insert::<K, V>(new, n, size, r);

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

    T: AllocPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

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

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

    let (k, v, r) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &rc) };

    let (k, v, r) = unsafe { <Page<K, V>>::unchecked_current(txn, m.other.as_page(), &rc) };

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

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

    let (new_right, k, v) = match fixed_size::<T, K, V>() {

    let (new_right, k, v) = match fixed_size::<K, V>() {

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

    T: AllocPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

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

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

    let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &lc) };

    let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(txn, m.other.as_page(), &lc) };

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

    T: AllocPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

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

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

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

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

        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);

        <Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);

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

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

            alloc::<_, _, _, L>(&mut new, k0, v0, 0, 0, &mut n);
            alloc::<_, _, _, L>(&mut new, k1, v1, l, r, &mut n);

            alloc::<_, _, L>(&mut new, k0, v0, 0, 0, &mut n);
            alloc::<_, _, L>(&mut new, k1, v1, l, r, &mut n);

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

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

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

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

        if let Some(s) = fixed_size::<T, K, V>() {

        if let Some(s) = fixed_size::<K, V>() {

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

    T: AllocPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

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

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

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

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

        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut right);

        <Page<K, V> as BTreeMutPage<K, V>>::init(&mut right);

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

            clone::<K, V, L>(page.as_page(), &mut right, s1a, &mut n);
            alloc::<K, V, L>(&mut right, k0, v0, l, r, &mut n);
            clone::<K, V, L>(page.as_page(), &mut right, s1b, &mut n);

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

            clone::<K, V, L>(page.as_page(), &mut right, s1, &mut n);

        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);

        <Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);

        clone::<T, K, V, L>(page.as_page(), &mut left, s0a, &mut n);
        alloc::<T, K, V, L>(&mut left, k0, v0, l, r, &mut n);
        clone::<T, K, V, L>(page.as_page(), &mut left, s0b, &mut n);

        clone::<K, V, L>(page.as_page(), &mut left, s0a, &mut n);
        alloc::<K, V, L>(&mut left, k0, v0, l, r, &mut n);
        clone::<K, V, L>(page.as_page(), &mut left, s0b, &mut n);

            if let Some((k, v)) = L::truncate_left::<T, K, V>(&mut right, k as usize + 1) {

            if let Some((k, v)) = L::truncate_left::<T, K, V>(txn, &mut right, k as usize + 1) {

                    split_key = &*k;
                    split_value = &*v;

                    split_key = K::from_raw_ptr(txn, k as *const u8);
                    split_value = V::from_raw_ptr(txn, v as *const u8);

            <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut right);

            <Page<K, V> as BTreeMutPage<K, V>>::init(&mut right);

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

            clone::<K, V, L>(page.as_page(), &mut right, s1, &mut n);

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

    T: AllocPage,
    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

    <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);

    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);

    <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);

    <Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);

    let mut split = core::ptr::null();

    let mut split = (core::ptr::null(), core::ptr::null());

            let size = entry_size::<T, K, V>(ptr) + L::extra_size::<T, K, V>();

            let size = entry_size::<K, V>(ptr) + L::extra_size::<T, K, V>();

                split = ptr as *const Tuple<K, V>;

                split = read::<T, K, V>(txn, ptr);

                alloc::<T, K, V, L>(current_page, k0, v0, 0, l0, &mut n);

                alloc::<K, V, L>(current_page, k0, v0, 0, l0, &mut n);

                alloc::<T, K, V, L>(current_page, k1, v1, 0, r0, &mut n);

                alloc::<K, V, L>(current_page, k1, v1, 0, r0, &mut n);

                alloc::<T, K, V, L>(current_page, k0, v0, l0, r0, &mut n);

                alloc::<K, V, L>(current_page, k0, v0, l0, r0, &mut n);

    assert!(!split.is_null());
    let split = unsafe { &*split };

    assert!(!split.0.is_null());

        split_key: &split.k,
        split_value: &split.v,

        split_key: unsafe { K::from_raw_ptr(txn, split.0) },
        split_value: unsafe { V::from_raw_ptr(txn, split.1) },

    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;

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

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

    fn truncate_left<T, K: Representable, V: Representable>(
        txn: &T,

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

    fn alloc_insert<K: Representable, V: Representable>(

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

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

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

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

    pub fn first<T, K: Representable<T>, V: Representable<T>>(&self) -> (u64, u16) {

    pub fn first<T, K: Representable, V: Representable>(&self) -> (u64, u16) {

                let size = fixed_size::<T, K, V>().unwrap();

                let size = fixed_size::<K, V>().unwrap();

    fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize {
        if fixed_size::<T, K, V>().is_some() {

    fn extra_size<T, K: Representable, V: Representable>() -> usize {
        if fixed_size::<K, V>().is_some() {

    fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {
        if let Some(f) = fixed_size::<T, K, V>() {

    fn can_alloc<T, K: Representable, V: Representable>(hdr: &Header, size: usize) -> bool {
        if let Some(f) = fixed_size::<K, V>() {

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

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

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

    fn truncate_left<T, K: Representable, V: Representable>(
        txn: &T,

        if let Some(f) = fixed_size::<T, K, V>() {

        if let Some(f) = fixed_size::<K, V>() {

                Some(read::<T, K, V>(

                let (k, v) = read::<T, K, V>(
                    txn,

                ))

                );
                Some((K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v)))

                    2 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64

                    2 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64

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

    fn alloc_insert<K: Representable, V: Representable>(

        if let Some(f) = fixed_size::<T, K, V>() {

        if let Some(f) = fixed_size::<K, V>() {

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

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

        if fixed_size::<T, K, V>().is_some() {

        if fixed_size::<K, V>().is_some() {

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

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

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

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

    fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize {

    fn extra_size<T, K: Representable, V: Representable>() -> usize {

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

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

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

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

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

    fn truncate_left<T, K: Representable, V: Representable>(
        _txn: &T,

        let size = if let Some(f) = fixed_size::<T, K, V>() {

        let size = if let Some(f) = fixed_size::<K, V>() {

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

                    8 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64

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

    fn alloc_insert<K: Representable, V: Representable>(

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

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

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

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

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

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

pub trait BTreePage<T: LoadPage, K: Representable<T>, V: Representable<T>> {

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
#[repr(C)]
pub struct Tuple<K, V> {
    k: K,
    v: V,
}
pub trait BTreePage<K: Representable, V: Representable> {

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

    fn next<'b, T: LoadPage>(txn: &T, p: Page<'b>, c: &mut Self::Cursor) -> Option<(&'b K, &'b V, u64)> {
        if let Some((k, v, r)) = Self::current(txn, p, c) {

    fn prev<'b>(p: Page<'b>, c: &mut Self::Cursor) -> Option<(&'b K, &'b V, u64)> {

    fn prev<'b, T: LoadPage>(txn: &T, p: Page<'b>, c: &mut Self::Cursor) -> Option<(&'b K, &'b V, u64)> {

            Self::current(p, c)

            Self::current(txn, p, c)

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

    unsafe fn unchecked_current<'a, T: LoadPage>(txn: &T, p: Page<'a>, c: &Self::Cursor) -> (&'a K, &'a V, u64);
    fn current<'a, T: LoadPage>(txn: &T, p: Page<'a>, c: &Self::Cursor) -> Option<(&'a K, &'a V, u64)> {

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

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

    fn set_cursor<'a>(

    fn set_cursor<'a, T: LoadPage>(

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

    K: Representable,
    V: Representable,
    P: BTreePage<K, V>,

    txn: &'a T,

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

        K: Representable + 'a,
        V: Representable + 'a,
        P: BTreePage<K, V>,

        P::next(self.page, &mut self.cursor)

        P::next(self.txn, self.page, &mut self.cursor)

pub trait BTreeMutPage<T: AllocPage, K: Representable<T>, V: Representable<T>>:
    BTreePage<T, K, V> + Sized

pub trait BTreeMutPage<K: Representable, V: Representable>:
    BTreePage<K, V> + Sized

    fn put<'a>(

    fn put<'a, T: AllocPage>(

    fn update_left_child(

    fn update_left_child<T: AllocPage>(

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

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

    fn replace<'a>(

    fn replace<'a, T: AllocPage>(

    fn merge_or_rebalance<'a, 'b>(

    fn merge_or_rebalance<'a, 'b, T: AllocPage>(

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

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

    fn modify<'a>(

    fn modify<'a, T: AllocPage>(

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

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

    fn size(m: &ModifiedPage<T, K, V, Self>) -> usize;

    fn size(m: &ModifiedPage<K, V, Self>) -> usize;

pub enum Op<'a, T, K: Representable<T>, V: Representable<T>> {

pub enum Op<'a, T, K: Representable, V: Representable> {

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

    K: Representable,
    V: Representable,
    P: BTreePage<K, V>,

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

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

pub struct Concat<'a, T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>

pub struct Concat<'a, K: Representable, V: Representable, P: BTreePage<K, V>>

    pub modified: ModifiedPage<'a, T, K, V, P>,

    pub modified: ModifiedPage<'a, K, V, P>,

pub struct Db_<T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>> {

pub struct Db_<K: Representable, V: Representable, P: BTreePage<K, V>> {

    pub marker: core::marker::PhantomData<(T, K, V, P)>,

    pub marker: core::marker::PhantomData<(K, V, P)>,

pub type Db<T, K, V> = Db_<T, K, V, page::Page<K, V>>;

pub type Db<K, V> = Db_<K, V, page::Page<K, V>>;

    K: Representable<T>,
    V: Representable<T>,
    P: BTreeMutPage<T, K, V>,

    K: Representable,
    V: Representable,
    P: BTreeMutPage<K, V>,

) -> Result<Db_<T, K, V, P>, T::Error> {

) -> Result<Db_<K, V, P>, T::Error> {

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

    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

) -> Result<Db_<T, K, V, page::Page<K, V>>, T::Error> {

) -> Result<Db_<K, V, page::Page<K, V>>, T::Error> {

    K: Representable<T>,
    V: Representable<T>,
    P: BTreeMutPage<T, K, V>,

    K: Representable,
    V: Representable,
    P: BTreeMutPage<K, V>,

    db: &Db_<T, K, V, P>,
) -> Result<Db_<T, K, V, P>, T::Error> {

    db: &Db_<K, V, P>,
) -> Result<Db_<K, V, P>, T::Error> {

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

    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,

    db: &Db<T, K, V>,
) -> Result<Db<T, K, V>, T::Error> {

    db: &Db<K, V>,
) -> Result<Db<K, V>, T::Error> {

pub fn get<'a, T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>(

pub fn get<'a, T: LoadPage, K: Representable, V: Representable, P: BTreePage<K, V>>(

    db: &Db_<T, K, V, P>,

    db: &Db_<K, V, P>,

        } else if let Some((k, v, _)) = P::current(page.as_page(), &cursor) {

        } else if let Some((k, v, _)) = P::current(txn, page.as_page(), &cursor) {

    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,
    P: BTreeMutPage<K, V> + core::fmt::Debug,

    db: &mut Db_<T, K, V, P>,

    db: &mut Db_<K, V, P>,

    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,
    P: BTreeMutPage<K, V> + core::fmt::Debug,

    db: &mut Db_<T, K, V, P>,
    cursor: &mut Cursor<T, K, V, P>,

    db: &mut Db_<K, V, P>,
    cursor: &mut Cursor<K, V, P>,

    // If p0 < cursor.first_rc_level, the page containing the deleted
    // element is not shared with another table. Therefore, the RC of
    // the pages referenced by the deleted element needs to be
    // decreased.
    if p0 < cursor.first_rc_level {
        unsafe {
            let cur = cursor.current();
            let (delk, delv, _) =
                P::unchecked_current(txn, cur.page.as_page(), cur.cursor.as_ref().unwrap());
            for o in delk.page_offsets().chain(delv.page_offsets()) {
                txn.incr_rc(o)?;
            }
        }
    }

    // "replacement" is.

    // "replacement" element is.

    // (k0, v0) if we're in an internal node.
    let (mut last_op, k0, v0) = leaf_delete(txn, cursor, p0)?;

    // (k0, v0) if the deletion happens in an internal node (`(k0,
    // v0)` is uninitialized else).
    let mut k0 = MaybeUninit::uninit();
    let mut v0 = MaybeUninit::uninit();
    let (mut last_op, k0v0) = leaf_delete(txn, cursor, p0, &mut k0, &mut v0)?;

    // Then, climb up the stack, and perform the lazy operations.

    // Then, climb up the stack, performing the operations lazily.

        // Compute the need for merge/rebalancing
        let mut concat = concat(txn, cursor, p0, &k0, &v0, last_op)?;

        // Prepare a plan for merging the current modified page (that
        // page is at level cursor.pointer + 1) with one of its
        // neighbours.
        //
        // This is a little bit convoluted, but we do have to get up
        // one level in order to fetch the right or left sibling of
        // the modified page.
        let mut concat = concat(txn, cursor, p0, k0v0, last_op)?;

        // Execute the plan, resulting in one of four different
        // outcomes.

        // Prepare a description (`last_op`) of the page modification
        // to be performed at the current level (i.e. at level
        // `cursor.pointer`).

        last_op = handle_merge(txn, cursor, p0, &k0, &v0, mil, merge, &mut free)?;

        last_op = handle_merge(txn, cursor, p0, k0v0, mil, merge, &mut free)?;

    // The root was merged or rebalanced.
    if let Some(d) = last_op.single_child() {
        debug!("single child {:?}", d);
        if P::is_dirty(last_op.page.as_page()) {
            txn.decr_rc_owned(last_op.page.offset)?
        } else {
            txn.decr_rc(last_op.page.offset)?
        }
        db.db = txn.load_page(d)?
    } else {
        update_root(txn, db, last_op, &k0, cursor.first_rc_level <= 1, &mut free)?
    }

    // The last operation was on the root (i.e. at level 1), and that
    // operation still needs to be executed.
    update_root(txn, db, last_op, k0v0, cursor.first_rc_level <= 1, &mut free)?;
    // Finally, free all the freed pages, now that we don't need to
    // read them anymore.

    K: Representable<T>,
    V: Representable<T>,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable,
    V: Representable,
    P: BTreeMutPage<K, V> + core::fmt::Debug,

    cursor: &mut Cursor<T, K, V, P>,

    cursor: &mut Cursor<K, V, P>,

    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,
    P: BTreeMutPage<K, V> + core::fmt::Debug + 'a,

    cursor: &mut Cursor<T, K, V, P>,

    cursor: &mut Cursor<K, V, P>,

) -> Result<(ModifiedPage<'a, T, K, V, P>, MaybeUninit<K>, MaybeUninit<V>), T::Error> {
    let ref mut curs0 = unsafe { cursor.stack[cursor.pointer].assume_init() };

    k0: &'a mut MaybeUninit<K>,
    v0: &'a mut MaybeUninit<V>,
) -> Result<(ModifiedPage<'a, K, V, P>, Option<(&'a K, &'a V)>), T::Error> {
    let curs0 = unsafe { &mut *cursor.stack[cursor.pointer].as_mut_ptr() };

    if cursor.pointer == cursor.first_rc_level {
        debug!("decr_rc");
        txn.decr_rc(curs0.page.offset)?;
        debug!("/decr_rc");
    }

        while let Some((k, v, _)) = P::next(curs0.page.as_page(), &mut c0)
            .or_else(|| P::next(curs0.page.as_page(), &mut c1))

        while let Some((k, v, _)) = P::next(txn, curs0.page.as_page(), &mut c0)
            .or_else(|| P::next(txn, curs0.page.as_page(), &mut c1))

    debug!("pointer = {:?}", cursor.pointer);
    let mut k0 = MaybeUninit::uninit();
    let mut v0 = MaybeUninit::uninit();

    let mut deleted = None;

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

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

            core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);
            core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1);

            if K::SIZE.is_some() && V::SIZE.is_some() {
                core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);
                core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1);
                deleted = Some((&*k0.as_ptr(), &*v0.as_ptr()))
            } else {
                deleted = Some((k, v))
            }

        k0,
        v0,

        deleted,

    K: Representable<T>,
    V: Representable<T>,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable,
    V: Representable,
    P: BTreeMutPage<K, V> + core::fmt::Debug,

    cursor: &mut Cursor<T, K, V, P>,

    cursor: &mut Cursor<K, V, P>,

    k0: &MaybeUninit<K>,
    v0: &MaybeUninit<V>,
    last_op: ModifiedPage<'a, T, K, V, P>,
) -> Result<Concat<'a, T, K, V, P>, T::Error> {

    k0v0: Option<(&'a K, &'a V)>,
    last_op: ModifiedPage<'a, K, V, P>,
) -> Result<Concat<'a, K, V, P>, T::Error> {

        let other = txn.load_page(P::left_child(curs.page.as_page(), c))?;
        Ok(Concat {
            modified: last_op,
            mid: unsafe { (&*k0.as_ptr(), &*v0.as_ptr()) },
            other,
            mod_is_left: false,
        })

        if let Some((k0, v0)) = k0v0 {
            let other = txn.load_page(P::left_child(curs.page.as_page(), c))?;
            Ok(Concat {
                modified: last_op,
                mid: (k0, v0),
                other,
                mod_is_left: false,
            })
        } else {
            unreachable!()
        }

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

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

            let (k, v, _) = P::prev(curs.page.as_page(), c).unwrap();

            let (k, v, _) = P::prev(txn, curs.page.as_page(), c).unwrap();

    K: Representable<T>,
    V: Representable<T>,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable,
    V: Representable,
    P: BTreeMutPage<K, V> + core::fmt::Debug,

    cursor: &mut Cursor<T, K, V, P>,

    cursor: &mut Cursor<K, V, P>,

    k0: &MaybeUninit<K>,
    v0: &MaybeUninit<V>,

    k0v0: Option<(&'a K, &'a V)>,

) -> Result<ModifiedPage<'a, T, K, V, P>, T::Error> {

) -> Result<ModifiedPage<'a, K, V, P>, T::Error> {

                last_op.ins = unsafe { Some((&*k0.as_ptr(), &*v0.as_ptr())) };

                last_op.ins = k0v0;

                last_op.ins = unsafe { Some((&*k0.as_ptr(), &*v0.as_ptr())) };

                last_op.ins = k0v0;

            if cursor.pointer + 1 >= cursor.first_rc_level && (split_key as *const K) != k0.as_ptr()

            let split_key_is_k0 = if let Some((k0, _)) = k0v0 {
                (k0 as *const K) == (split_key as *const K)
            } else {
                false
            };
            if cursor.pointer + 1 >= cursor.first_rc_level && !split_key_is_k0

    } else {
        if cursor.pointer == cursor.first_rc_level {
            txn.decr_rc(last_op.page.offset)?;
        }
        modify_rc(txn, &last_op)?;

    modify_rc(txn, &last_op, cursor.pointer, cursor.first_rc_level)?;

// This function modifies the reference counts of references of the
// modified page, which is the page *about to be* modified.
//
// This function is always called when `m` is an internal node.

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

    K: Representable,
    V: Representable,
    P: BTreePage<K, V>,

    m: &ModifiedPage<T, K, V, P>,

    m: &ModifiedPage<K, V, P>,
    p: usize,
    first_rc_level: usize,

    if p == first_rc_level {
        txn.decr_rc(m.page.offset)?;
    }

    while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c0) {
        for o in k.page_offsets().chain(v.page_offsets()) {
            txn.incr_rc(o)?;

    assert_ne!(left, 0);
    if p >= first_rc_level {
        while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c0) {
            for o in k.page_offsets().chain(v.page_offsets()) {
                txn.incr_rc(o)?;
            }
            assert_ne!(left, 0);
            txn.incr_rc(left)?;
            left = r;

        txn.incr_rc(left)?;
        left = r;

    if m.skip_first {
        P::move_next(m.page.as_page(), &mut c1);
    } else {
        txn.incr_rc(left)?;

    // The insertions come from pages strictly below the page at
    // cursor.pointer, so if `incr_ins`, we increment them here,
    // except the replacement, already incremented in `leaf_delete`
    // above
    if p + 1 >= first_rc_level {
        if let Some((k, v)) = m.ins {
            // If this is the replacement, it has already been
            // incremented in `leaf_delete`, so we don't need to
            // increment it again.
            if m.skip_first {
                for o in k.page_offsets().chain(v.page_offsets()) {
                    txn.incr_rc(o)?;
                }
            }
            if let Some((k, v)) = m.ins2 {
                for o in k.page_offsets().chain(v.page_offsets()) {
                    txn.incr_rc(o)?;
                }
            }
        }

    while let Some((k, v, r)) = P::next(m.page.as_page(), &mut c1) {
        for o in k.page_offsets().chain(v.page_offsets()) {
            txn.incr_rc(o)?;

    if p >= first_rc_level {
        if m.skip_first {
            P::move_next(m.page.as_page(), &mut c1);
        }
        // If we are not updating the left child of c1's first
        // element, increment that left child.
        if m.l == 0 {
            assert_ne!(left, 0);
            txn.incr_rc(left)?;
        }
        // Moving on to the first non-deleted element of `c1`: if we
        // are not updating the right child of the first element,
        // increment that right child's RC.
        if let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {
            for o in k.page_offsets().chain(v.page_offsets()) {
                txn.incr_rc(o)?;
            }
            if m.r == 0 {
                assert_ne!(r, 0);
                txn.incr_rc(r)?;
            }
        }
        // Finally, increment the RCs of all other elements in `c1`.
        while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {
            for o in k.page_offsets().chain(v.page_offsets()) {
                txn.incr_rc(o)?;
            }
            if r != 0 {
                assert_ne!(r, 0);
                txn.incr_rc(r)?;
            }

        txn.incr_rc(r)?;

    'a,

    K: Representable<T> + core::fmt::Debug,
    V: Representable<T> + core::fmt::Debug,
    P: BTreeMutPage<T, K, V> + core::fmt::Debug,

    K: Representable + core::fmt::Debug,
    V: Representable + core::fmt::Debug,
    P: BTreeMutPage<K, V> + core::fmt::Debug,

    db: &mut Db_<T, K, V, P>,
    mut last_op: ModifiedPage<T, K, V, P>,
    k0: &MaybeUninit<K>,

    db: &mut Db_<K, V, P>,
    mut last_op: ModifiedPage<K, V, P>,
    k0v0: Option<(&K, &V)>,

    if let Some(d) = last_op.single_child() {
        // If the root had only one element, and the last operation
        // was a merge, this decreases the depth of the tree.
        debug!("single child {:?}", d);
        if P::is_dirty(last_op.page.as_page()) {
            txn.decr_rc_owned(last_op.page.offset)?
        } else {
            txn.decr_rc(last_op.page.offset)?
        }
        db.db = txn.load_page(d)?;
        return Ok(())
    }
    // Else, we execute the last operation

            if is_rc && (split_key as *const K) != k0.as_ptr() {

            let split_key_is_k0 = if let Some((k0, _)) = k0v0 {
                (k0 as *const K) == (split_key as *const K)
            } else {
                false
            };
            if is_rc && !split_key_is_k0 {

pub struct PageCursor<T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>

pub struct PageCursor<K: Representable, V: Representable, P: BTreePage<K, V>>

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

impl<K: Representable, V: Representable, P: BTreePage<K, V>> Clone
    for PageCursor<K, V, P>

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

impl<K: Representable, V: Representable, P: BTreePage<K, V>> Copy
    for PageCursor<K, V, P>

pub struct Cursor<T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>> {
    pub stack: [core::mem::MaybeUninit<PageCursor<T, K, V, P>>; N_CURSORS],

pub struct Cursor<K: Representable, V: Representable, P: BTreePage<K, V>> {
    pub stack: [core::mem::MaybeUninit<PageCursor<K, V, P>>; N_CURSORS],

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

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

    pub fn new(db: &Db_<T, K, V, P>) -> Self {

    pub fn new(db: &Db_<K, V, P>) -> Self {

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

impl<K: Representable, V: Representable, P: BTreePage<K, V>>
    Cursor<K, V, P>

    pub fn current(&self) -> &PageCursor<T, K, V, P> {

    pub fn current(&self) -> &PageCursor<K, V, P> {

    pub fn current_mut(&mut self) -> &mut PageCursor<T, K, V, P> {

    pub fn current_mut(&mut self) -> &mut PageCursor<K, V, P> {

    pub fn set<'a>(

    pub fn set<'a, T: LoadPage>(

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

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

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

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

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

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

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

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

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

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

struct A<T>([u64; 100], std::marker::PhantomData<T>);

struct A([u64; 100]);

impl<T> std::fmt::Debug for A<T> {

impl std::fmt::Debug for A {

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>());
    fn compare(&self, _: &T, b: &Self) -> std::cmp::Ordering {
        self.0.cmp(&b.0)
    }
    fn size(&self) -> usize {
        core::mem::size_of::<Self>()
    }
}

direct_repr!(A);

type T<'a> = MutTxn<&'a Env, ()>;

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

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

        let a = A([i * i * i; 100], std::marker::PhantomData);

        let a = A([i * i * i; 100]);

    let a = A([0; 100], std::marker::PhantomData);

    let a = A([0; 100]);

    let a = A([i0 * i0 * i0; 100], std::marker::PhantomData);

    let a = A([i0 * i0 * i0; 100]);

    let mut db: Db<_, u64, ()> = create_db(&mut txn).unwrap();

    let mut db: Db<u64, ()> = create_db(&mut txn).unwrap();

    let mut db: Db<_, u64, ()> = create_db(&mut txn).unwrap();

    let mut db: Db<u64, ()> = create_db(&mut txn).unwrap();

    let mut db: Db<_, u64, ()> = create_db(&mut txn).unwrap();

    let mut db: Db<u64, ()> = create_db(&mut txn).unwrap();

    let mut db: Db<_, u64, ()> = create_db(&mut txn).unwrap();
    let n = 2_000 as u64;

    let mut db: Db<u64, A> = create_db(&mut txn).unwrap();
    let n = 20 as u64;

    let a = A([0; 100]);

        if put(&mut txn, &mut db, &i, &()).unwrap() {

        if put(&mut txn, &mut db, &i, &a).unwrap() {

    debug!("==========");

        if put(&mut txn, &mut db, &i, &()).unwrap() {

        if put(&mut txn, &mut db, &i, &a).unwrap() {

    curs.set(&txn, Some((&500, Some(&())))).unwrap();

    curs.set(&txn, Some((&500, Some(&a)))).unwrap();

    unimplemented!();
    del(&mut txn, &mut db, &1019, None).unwrap();

    debug!("==============");
    del(&mut txn, &mut db, &11, None).unwrap();
    debug!("free_owned_pages = {:?}", txn.free_owned_pages);
    crate::debug::debug(&txn, &[&db, &db2], "debug1", true);

    for i in 0..0 { // 512 {

    for i in 0..1 {

    /*for i in 1530..1531 {
        del(&mut txn, &mut db, &i, None).unwrap();
    }*/

    // for i in 1530..1531 {
    //     del(&mut txn, &mut db, &i, None).unwrap();
    // }

    let mut err = 0;

            assert_eq!(txn.rc(*p).unwrap(), *r as u64);

            if txn.rc(*p).unwrap() != *r as u64 {
                error!("{:?} {:?} {:?}", p, txn.rc(*p).unwrap(), *r);
                err += 1;
            }

            assert_eq!(txn.rc(*p).unwrap(), 0);

            if txn.rc(*p).unwrap() != 0 {
                error!("{:?} {:?} 0", p, txn.rc(*p).unwrap());
                err += 1;
            }

    assert_eq!(err, 0);

        let mut curs: btree::cursor::Cursor<T, _, _, B> = btree::cursor::Cursor::new(&db_free);

        let mut curs: btree::cursor::Cursor<_, _, B> = btree::cursor::Cursor::new(&db_free);

fn add_refs<T: LoadPage, K: Representable<T>, V: Representable<T>, P: BTreePage<T, K, V>>(

fn add_refs<T: LoadPage, K: Representable, V: Representable, P: BTreePage<K, V>>(

    db: &Db_<T, K, V, P>,

    db: &Db_<K, V, P>,

    debug!("------ add_refs {:?}", db.db.offset);

        debug!("-- p = {:?}", p);

                debug!("l = {:?}", l);

                    while let Some((_, _, r)) = P::next(p.as_page(), &mut c) {

                    while let Some((_, _, r)) = P::next(txn, p.as_page(), &mut c) {
                        debug!("r = {:?}", r);

                debug!("already there");

    let db: Db<_, u64, ()> = txn.root_db(0).unwrap().unwrap();

    let db: Db<u64, ()> = txn.root_db(0).unwrap().unwrap();

    rc: Option<btree::Db<Self, u64, ()>>,

    rc: Option<btree::Db<u64, ()>>,

            let mut free_db: btree::Db<Self, u64, ()> = btree::Db {

            let mut free_db: btree::Db<u64, ()> = btree::Db {

        let mut db: btree::Db<Self, u64, ()> = btree::Db {

        let mut db: btree::Db<u64, ()> = btree::Db {

        K: Representable<Self>,
        V: Representable<Self>,

        K: Representable,
        V: Representable,

    ) -> Result<Option<sanakirja_core::btree::Db<Self, K, V>>, Error> {

    ) -> Result<Option<sanakirja_core::btree::Db<K, V>>, Error> {

        K: Representable<Self>,
        V: Representable<Self>,

        K: Representable,
        V: Representable,

    ) -> Result<Option<sanakirja_core::btree::Db<Self, K, V>>, Self::Error>;

    ) -> Result<Option<sanakirja_core::btree::Db<K, V>>, Self::Error>;