//! This crate defines tools to implement datastructures that can live
//! in main memory or on-disk, meaning that their natural habitat is
//! memory-mapped files, but if that environment is threatened, might
//! seek refuge in lower-level environments.
//!
//! One core building block of this library is the notion of virtual
//! memory pages, which are allocated and freed by an
//! externally-provided allocator (see how the `sanakirja` crate does
//! this). The particular implementation used here is meant to allow a
//! transactional system with readers reading the structures
//! concurrently with one writer at a time.
//!
//! At the moment, only B trees are implemented, as well as three
//! important traits:
//!
//! - [`Representable`] is the trait of types that can be written to
//! disk and read from the disk.
//! - [`LoadPage`] is a trait used to get a pointer to a page. In the
//! most basic version, this may just return a pointer to the file,
//! offset by the requested offset. In more sophisticated versions,
//! this can be used to encrypt and compress pages.
//! - [`AllocPage`] allocates and frees pages, because as
//! datastructures need to be persisted on disk, we can't rely on
//! Rust's memory management to do it for us. Users of this crate
//! don't have to worry about this though.

/// A macro to implement [`Representable`] on "plain" types,
/// i.e. fixed-sized types that are `repr(C)` and don't hold
/// references to out-of-tree pages.

/// Representation of a page.

        unsafe { core::mem::transmute(*self) }

        Page {
            data: unsafe { &*(self.data as *const [u8; PAGE_SIZE]) },
            offset: self.offset,
        }

    }
}
impl CowPage {
    pub fn is_dirty(&self) -> bool {
        unsafe { (*self.data) & 1 != 0 }

// Copyright 2015 Pierre-Étienne Meunier and Florent Becker. See the
// COPYRIGHT file at the top-level directory of this distribution and
// at http://pijul.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

                    let cursor = P::cursor_first(&p.0);

                    P::put(

                    if let Put::Ok(p) = P::put(

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

                        &cursor,

                    )?;
                    // Return the new root.
                    return Ok(p);

                    )? {
                        // Return the new root.
                        return Ok(p.page);
                    } else {
                        unreachable!()
                    }

        let mut c = P::cursor_first(cur.page.as_page());

        let mut c = P::cursor_first(&cur.page);

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

        let page = if mutable && page.is_dirty() {

            let b = if Self::is_dirty(page.as_page()) { 1 } else { 0 };

            let b = if page.is_dirty() { 1 } else { 0 };

        if mutable && Self::is_dirty(page.as_page()) {

        if mutable && page.is_dirty() {

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

            let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };
            let b1 = if m.other.is_dirty() { 1 } else { 0 };

        let rc = PageCursor::new(m.other.as_page(), 0);

        let rc = PageCursor::new(&m.other, 0);

    fn is_dirty(page: crate::Page) -> bool {
        header(page).is_dirty()
    }
    fn is_empty(_: crate::Page, c: &Self::Cursor) -> bool {

    fn is_empty(c: &Self::Cursor) -> bool {

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

    fn is_init(c: &Self::Cursor) -> bool {

    fn cursor_before(p: crate::Page) -> Self::Cursor {

    fn cursor_before(p: &crate::CowPage) -> Self::Cursor {

    fn cursor_after(p: crate::Page) -> Self::Cursor {

    fn cursor_after(p: &crate::CowPage) -> Self::Cursor {

    pub(super) fn new(p: crate::Page, cur: isize) -> Self {
        let hdr = header(p);

    pub(super) fn new(p: &crate::CowPage, cur: isize) -> Self {
        let hdr = unsafe { &*(p.data as *const Header) };

    pub(super) fn after(p: crate::Page) -> Self {
        let hdr = header(p);

    pub(super) fn after(p: &crate::CowPage) -> Self {
        let hdr = unsafe { &*(p.data as *const Header) };

        let mut rc = PageCursor::new(m.other.as_page(), 0);

        let mut rc = PageCursor::new(&m.other, 0);

        let mut rc = PageCursor::new(m.other.as_page(), 0);

        let mut rc = PageCursor::new(&m.other, 0);

    let rc = super::PageCursor::new(m.other.as_page(), 0);

    let rc = super::PageCursor::new(&m.other, 0);

    let lc = PageCursor::after(m.modified.page.as_page());

    let lc = PageCursor::after(&m.modified.page);

    let rc = super::PageCursor::new(m.modified.page.as_page(), 0);

    let rc = super::PageCursor::new(&m.modified.page, 0);

    if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

    if let Put::Ok(Ok { freed, .. }) = <Page<K, V>>::put(

        assert_eq!(new_right.0.offset, page.0.offset);

    debug!("split_unsized");

        }
        if replace {
            continue;

            if replace {
                continue;
            }

        debug!("{:?} {:?} {:?} {:?}", r, off, is_left, total);

pub fn header<'a>(page: crate::Page<'a>) -> &'a Header {

pub(crate) fn header<'a>(page: crate::Page<'a>) -> &'a Header {

    fn is_dirty(page: crate::Page) -> bool {
        header(page).is_dirty()
    }

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

    fn is_empty(c: &Self::Cursor) -> bool {

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

    fn is_init(c: &Self::Cursor) -> bool {

    fn cursor_before(p: crate::Page) -> Self::Cursor {

    fn cursor_before(p: &crate::CowPage) -> Self::Cursor {

    fn cursor_after(p: crate::Page) -> Self::Cursor {

    fn cursor_after(p: &crate::CowPage) -> Self::Cursor {

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

        let page = if mutable && page.is_dirty() {

            freed = page.offset | if Self::is_dirty(page.as_page()) { 1 } else { 0 };

            freed = page.offset | if page.is_dirty() { 1 } else { 0 };

        if mutable && Self::is_dirty(page.as_page()) {

        if mutable && page.is_dirty() {

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

            let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };
            let b1 = if m.other.is_dirty() { 1 } else { 0 };

        let rc = PageCursor::new(m.other.as_page(), 0);

        let rc = PageCursor::new(&m.other, 0);

    v0: Option<&V>,

            Ordering::Less => n += 1,
            Ordering::Greater => return Err(n),
            Ordering::Equal => {
                if let Some(v0) = v0 {
                    match sm.v.compare(txn, v0) {
                        Ordering::Less => n += 1,
                        Ordering::Greater => return Err(n),
                        Ordering::Equal => return Ok(n),
                    }
                } else {
                    return Ok(n);
                }
            }
        }
    }
    Err(n)
}
unsafe fn cmp<T: LoadPage, K: Representable, V: Representable>(
    txn: &T,
    k0: &K,
    v0: Option<&V>,
    p: &[u8; 4096],
    off: u64,
) -> Ordering {
    let off = u64::from_le(off) & 0xfff;
    let (k, v) = read::<T, K, V>(txn, p.as_ptr().offset(off as isize & 0xfff));
    let k = K::from_raw_ptr(txn, k);
    match k.compare(txn, k0) {
        Ordering::Equal => {
            if let Some(v0) = v0 {
                let v = V::from_raw_ptr(txn, v);
                v.compare(txn, v0)
            } else {
                Ordering::Equal
            }
        }
        o => o,
    }
}
unsafe fn internal_search<T: LoadPage, K: Representable, V: Representable>(
    txn: &T,
    k0: &K,
    v0: Option<&V>,
    s: &[u64],
    p: &[u8; 4096],
) -> Result<usize, usize> {
    let mut a = 0;
    let mut b = s.len();
    for _ in 0..4 {
        let mid = (a + b) / 2;
        match cmp(txn, k0, v0, p, s[mid]) {
            Ordering::Less => a = mid,
            Ordering::Greater => b = mid,
            Ordering::Equal => b = mid + 1,
        }
    }
    let mut n = a;
    for &off in &s[a..b] {
        match cmp(txn, k0, v0, p, off) {

        if let Some(v0) = v0 {
            s.binary_search_by(|tup| match tup.k.compare(txn, &k0) {
                Ordering::Equal => tup.v.compare(txn, &v0),
                c => c,
            })
        } else {
            // leaf_binary_search(txn, k0, s)
            leaf_linear_search(txn, k0, s)
        }

        leaf_linear_search(txn, k0, v0, s)

        if let Some(v0) = v0 {
            s.binary_search_by(|&off| {
                let off = u64::from_le(off) & 0xfff;
                let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
                let k = K::from_raw_ptr(txn, k);
                match k.compare(txn, k0) {
                    Ordering::Equal => {
                        let v = V::from_raw_ptr(txn, v);
                        v.compare(txn, v0)
                    }
                    cmp => cmp,
                }
            })
        } else {
            s.binary_search_by(|&off| {
                let off = u64::from_le(off) & 0xfff;
                let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
                let k = K::from_raw_ptr(txn, k);
                k.compare(txn, k0)
            })
        }

        internal_search(txn, k0, v0, s, page.data)

        let mut rc = PageCursor::new(m.other.as_page(), 0);

        let mut rc = PageCursor::new(&m.other, 0);

        let mut rc = PageCursor::new(m.other.as_page(), 0);

        let mut rc = PageCursor::new(&m.other, 0);

    let rc = super::PageCursor::new(m.other.as_page(), 0);

    let rc = super::PageCursor::new(&m.other, 0);

    let lc = PageCursor::after(m.modified.page.as_page());

    let lc = PageCursor::after(&m.modified.page);

    let rc = super::PageCursor::new(m.modified.page.as_page(), 0);

    let rc = super::PageCursor::new(&m.modified.page, 0);

            left = unsafe { core::mem::transmute(page) };

            left = MutPage(page);

//! An implementation of B trees.

    fn is_dirty(page: Page) -> bool;

    fn is_empty(p: Page, c: &Self::Cursor) -> bool;

    fn is_empty(c: &Self::Cursor) -> bool;

    fn is_init(p: Page, c: &Self::Cursor) -> bool;

    fn is_init(c: &Self::Cursor) -> bool;

    fn cursor_before(p: Page) -> Self::Cursor;

    fn cursor_before(p: &CowPage) -> Self::Cursor;

    fn cursor_first(p: Page) -> Self::Cursor {

    fn cursor_first(p: &CowPage) -> Self::Cursor {

    fn cursor_after(p: Page) -> Self::Cursor;

    fn cursor_after(p: &CowPage) -> Self::Cursor;

    fn cursor_last(p: Page) -> Self::Cursor {

    fn cursor_last(p: &CowPage) -> Self::Cursor {

#[derive(Debug, Clone, Copy)]

#[derive(Debug)]

        let mut cursor = P::cursor_before(page.as_page());

        let mut cursor = P::cursor_before(&page);

    let mut stack: [MaybeUninit<cursor::PageCursor<K, V, P>>; cursor::N_CURSORS] =
        [MaybeUninit::uninit(); cursor::N_CURSORS];

    let mut stack: [MaybeUninit<cursor::PageCursor<K, V, P>>; cursor::N_CURSORS] = [
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
        MaybeUninit::uninit(),
    ];

        cursor: P::cursor_before(&page),

        cursor: P::cursor_before(page.as_page()),

                        cursor: P::cursor_before(&page),

                        cursor: P::cursor_before(page.as_page()),

                continue

                continue;

        if P::is_dirty(cur.page.as_page()) {

        if cur.page.is_dirty() {

            break

            break;

// Copyright 2015 Pierre-Étienne Meunier and Florent Becker. See the
// COPYRIGHT file at the top-level directory of this distribution and
// at http://pijul.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use log::*;

    let found = cursor.set(txn, Some((key, value)))?;
    if found.is_none() {
        debug!("not found");

    if cursor.set(txn, Some((key, value)))?.is_none() {
        // If the key and value weren't found, return.

    // Else, the cursor is set on `(key, value)` if `value.is_some()`
    // or on the first entry with key `key` else.
    //
    // We delete that position, which might be in a leaf or in an
    // internal node.

    //
    // Else, that RC doesn't need to be changed, since it's still
    // referenced by the same pages as before, just not by the pages
    // that are cloned by this deletion.

    find_min(txn, cursor)?;

    let cur = cursor.current();
    let mut left_page = P::right_child(cur.page.as_page(), &cur.cursor);
    while left_page > 0 {
        let page = txn.load_page(left_page)?;
        let curs = P::cursor_first(&page);
        left_page = P::left_child(page.as_page(), &curs);
        cursor.push(PageCursor { page, cursor: curs });
    }

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

    // If the leaf is shared with another tree, then since we're
    // cloning the leaf, update the reference counts of all the
    // references contained in the leaf.
    if cursor.pointer() >= cursor.first_rc_level {
        modify_rc(txn, &last_op)?;
    }

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

        debug!("merge: {:?}", merge);

        // Update the reference counts, potentially freeing the page
        // at the current level.
        modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;

        // If the modified page is shared with another tree, we will
        // clone it in the next round. Therefore, update the reference
        // counts of all the references in the modified page.
        if cursor.pointer() >= cursor.first_rc_level {
            modify_rc(txn, &last_op)?;
        }

    update_root(
        txn,
        db,
        last_op,
        k0v0,
        cursor.first_rc_level == 0,
        &mut free,
    )?;

    let root_is_shared = cursor.first_rc_level == 0;
    update_root(txn, db, last_op, k0v0, root_is_shared, &mut free)?;

    // Finally, free all the freed pages, now that we don't need to
    // read them anymore.
    for (n, p) in free.iter().enumerate() {
        if p[0] > 0 || p[1] > 0 {
            debug!("freeing at level {:?}: {:?}", n, p);
        }

    // Finally, free all the pages marked as free during the deletion,
    // now that we don't need to read them anymore.
    for p in free.iter() {

    debug!("/del");

/// Follow the leftmost pages of each page until the leftmost leaf of
/// the subtree starting at `cursor.pointer()`, and set `cursor` to
/// point to the leftmost element of that subtree.
fn find_min<
    T: AllocPage + LoadPage,
    K: Representable + ?Sized,
    V: Representable + ?Sized,
    P: BTreeMutPage<K, V> + core::fmt::Debug,
>(
    txn: &mut T,
    cursor: &mut Cursor<K, V, P>,
) -> Result<(), T::Error> {
    let cur = cursor.current();
    let mut left_page = P::right_child(cur.page.as_page(), &cur.cursor);
    while left_page > 0 {
        let page = txn.load_page(left_page)?;
        let curs = P::cursor_first(page.as_page());
        left_page = P::left_child(page.as_page(), &curs);
        cursor.push(PageCursor { page, cursor: curs });
    }
    Ok(())
}

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

        // In this case, we need to save the replacement. If the
        // replacement has references, we will increment them later,
        // when updating the page where the deletion happens.

        // In this case, we need to save the replacement, and if this
        // leaf is shared with another tree, we also need increment
        // the replacement's references, since we are copying it.

            c1,
            skip_first: true,

            c1,
            skip_first: true,

            // The middle element comes from the page above this
            // concatenation, and hence has the same lifetime as that
            // page. However, our choice of lifetimes can't express
            // this, but we also know that we are not going to mutate
            // the parent before rebalancing or merging the
            // concatenation, and hence this pointer will be alive
            // during these operations (i.e. during the merge or
            // rebalance).

    debug!(
        "handle_merge for level {:?}, freed {:?}",
        cursor.pointer(),
        freed
    );

    p: usize,
    first_rc_level: usize,

    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)?;
            }
            if left != 0 {
                txn.incr_rc(left)?;
            }
            left = r;

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

        // The insertions are taken care of in `handle_merge` above,
        // so we can directly move to the `c1` part of the
        // modification.
        if m.skip_first {
            P::move_next(&mut c1);

        if left != 0 {
            txn.incr_rc(left)?;

        // If we are not updating the left child of c1's first
        // element, increment that left child.
        if m.l == 0 {
            if left != 0 {
                txn.incr_rc(left)?;
            }

        left = r;
    }
    // The insertions are taken care of in `handle_merge` above,
    // so we can directly move to the `c1` part of the
    // modification.
    if m.skip_first {
        P::move_next(&mut c1);
    }
    // If we are not updating the left child of c1's first
    // element, increment that left child.
    if m.l == 0 {
        if left != 0 {
            txn.incr_rc(left)?;

    }

        // If we are not updating the right child of the first
        // element of `c1`, 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 && r != 0 {
                txn.incr_rc(r)?;
            }

    // If we are not updating the right child of the first
    // element of `c1`, 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)?;

        // 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 {
                txn.incr_rc(r)?;
            }

        if m.r == 0 && 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 {
            txn.incr_rc(r)?;

    mut last_op: ModifiedPage<K, V, P>,

    last_op: ModifiedPage<K, V, P>,

        // We don't do this if the table is empty, in order to be
        // consistent with put and drop.
        debug!("single child {:?} {:?}", d, is_rc);

        // We don't do this if the table is empty (i.e. if `d == 0`),
        // in order to be consistent with put and drop.

            if P::is_dirty(last_op.page.as_page()) {

            if last_op.page.is_dirty() {

            if freed > 0 {
                if P::is_dirty(last_op.page.as_page()) {
                    txn.decr_rc_owned(freed)?;
                } else {
                    txn.decr_rc(freed)?;
                }
            }

            free[0][0] = freed;

    match modify::<_, K, V, P>(txn, &mut last_op)? {

    match modify::<_, K, V, P>(txn, last_op)? {

            // Here, the root was simply updated (i.e. some elements
            // might have been deleted/inserted/updated), so we just
            // need to update the Db.

            left: l,
            right: r,

            left: MutPage(CowPage { offset: l, .. }),
            right: MutPage(CowPage { offset: r, .. }),

            // Else, the root has split, and we need to allocate a new
            // page to hold the split key/value and the two sides of
            // the split.

            let mut c = P::cursor_before(page.0.as_page());

            let mut c = P::cursor_before(&page.0);

            P::put(
                txn, page.0, true, false, &c, k, v, None, l.0.offset, r.0.offset,
            )?;

            let page = if let Put::Ok(p) = P::put(txn, page.0, true, false, &c, k, v, None, l, r)? {
                p.page
            } else {
                unreachable!()
            };

                (k0 as *const K) == (k as *const K)

                core::ptr::eq(k0, k)

            // If the root isn't shared with another tree, and the
            // split key is different from the replacement, increment
            // the RCs of the references contained in the split
            // key/value.
            //
            // The replacement need not be incremented again, since it
            // was already increment when we took it from the page in
            // `leaf_delete`.

            // Finally, update the database.

fn single_child<K: Representable+?Sized, V: Representable+?Sized, P: BTreeMutPage<K, V>>(m: &ModifiedPage<K, V, P>) -> Option<u64> {

fn single_child<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreeMutPage<K, V>>(
    m: &ModifiedPage<K, V, P>,
) -> Option<u64> {

    debug!(
        "single_child: {:?} {:?} {:?} {:?}",
        m.page,
        m.c0, c1, m.ins
    );
    if P::is_empty(m.page.as_page(), &m.c0)
        && m.ins.is_none()
        && P::is_empty(m.page.as_page(), &c1)
    {

    if P::is_empty(&m.c0) && m.ins.is_none() && P::is_empty(&c1) {

/// Apply the modifications to a page.

/// Apply the modifications to a page. This is exclusively used for
/// the root page, because other modifications are applied during a
/// merge/rebalance attempts.

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

    m: ModifiedPage<'a, K, V, P>,

    debug!("modify: {:?}", m);

        // The following call might actually replace the first element
        // of `m.c1` if `m.skip_first`.

        // If there's no insertion to do, we might still need to
        // delete elements, or update children.

            // If the left page of the current entry has changed,
            // update it.

            // If there's no insertion, and `m.l == 0`, we are
            // actually deleting an entry of the root, and so we need
            // to update the right child of the current entry. The
            // following moves one step to the right and updates:

}
impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> Clone
    for PageCursor<K, V, P>
{
    fn clone(&self) -> Self {
        PageCursor {
            page: self.page,
            cursor: self.cursor.clone(),
        }
    }
}
impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> Copy
    for PageCursor<K, V, P>
{

// This is 1 + the maximal depth of a tree. Cursors start at 1 to
// allow for splitting the root on an insertion.

// This is 1 + the maximal depth of a tree.

// larger than 2^52, the maximum depth is 24, and we add the extra
// room to allow for splitting.
pub(crate) const N_CURSORS: usize = 25;

// larger than 2^52, the maximum depth is 24.
pub(crate) const N_CURSORS: usize = 24;

#[derive(Debug, Clone)]

#[derive(Debug)]

        let mut stack = [core::mem::MaybeUninit::uninit(); N_CURSORS];

        let mut stack = [
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
            core::mem::MaybeUninit::uninit(),
        ];

            cursor: P::cursor_before(&page),

            cursor: P::cursor_before(page.as_page()),

        init.cursor = P::cursor_before(init.page.as_page());

        init.cursor = P::cursor_before(&init.page);

            let page = current.page;
            if self.first_rc_level >= N_CURSORS && txn.rc(page.offset)? >= 2 {

            // let page = current.page;
            if self.first_rc_level >= N_CURSORS && txn.rc(current.page.offset)? >= 2 {

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

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

                    debug!("not found on page {:?}", page)

                    debug!("not found on page {:?}", current.page)

                *cursor = P::cursor_first(page.as_page());

                *cursor = P::cursor_first(&current.page);

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

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

                    cursor: P::cursor_before(&page),

                    cursor: P::cursor_before(page.as_page()),

        current.cursor = P::cursor_last(current.page.as_page());

        current.cursor = P::cursor_last(&current.page);

                    cursor: P::cursor_last(&page),

                    cursor: P::cursor_last(page.as_page()),

            if P::is_init(current.page.as_page(), &current.cursor) {

            if P::is_init(&current.cursor) {

                        cursor: P::cursor_before(&page),

                        cursor: P::cursor_before(page.as_page()),

                        cursor: P::cursor_before(&page),

                        cursor: P::cursor_before(page.as_page()),

            if P::is_empty(current.page.as_page(), &current.cursor) {

            if P::is_empty(&current.cursor) {

                        cursor: P::cursor_after(&page),

                        cursor: P::cursor_after(page.as_page()),

                        cursor: P::cursor_after(&page),

                        cursor: P::cursor_after(page.as_page()),

        let n = i * 128; // _000_000;

        let n = i * 1_000_000;

        /*

        */

        /*

        */

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