/// If this value is an offset to another page at offset `offset`,
    /// return `Some(offset)`. Return `None` else.
    fn drop<T: AllocPage>(&self, txn: &mut T) -> Result<(), T::Error> {
        for p in self.page_references() {
            txn.decr_rc(p)?;
        }
        Ok(())
    }

        let s = core::slice::from_raw_parts(
            page.data.as_ptr().add(HDR) as *const u16,
            hdr.n() as usize,
        );
        if let Some(v0) = v0 {
            s.binary_search_by(|&off| {
                let off = u16::from_le(off);
                let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
                let k = K::from_raw_ptr(txn, k as *const u8);
                match k.compare(txn, k0) {
                    Ordering::Equal => {
                        let v = V::from_raw_ptr(txn, v as *const u8);
                        v.compare(txn, v0)
                    }
                    cmp => cmp,

        lookup_leaf(txn, page, k0, v0, hdr)
    } else {
        lookup_internal(txn, page, k0, v0, hdr)
    }
}
unsafe fn lookup_internal<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(
    txn: &T,
    page: crate::Page,
    k0: &K,
    v0: Option<&V>,
    hdr: &header::Header,
) -> Result<usize, usize> {
    let s = core::slice::from_raw_parts(
        page.data.as_ptr().add(HDR) as *const u64,
        hdr.n() as usize,
    );
    if let Some(v0) = v0 {
        s.binary_search_by(|&off| {
            let off = u64::from_le(off) & 0xfff;
            let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
            let k = K::from_raw_ptr(txn, k);
            match k.compare(txn, k0) {
                Ordering::Equal => {
                    let v = V::from_raw_ptr(txn, v);
                    v.compare(txn, v0)

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

                cmp => cmp,
            }
        })
    } else {
        match 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)
        }) {
            Err(i) => Err(i),
            Ok(mut i) => {
                // Rewind if there are multiple matching keys.
                while i > 0 {
                    let off = u64::from_le(s[i-1]) & 0xfff;
                    let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
                    let k = K::from_raw_ptr(txn, k);
                    if let Ordering::Equal = k.compare(txn, k0) {
                        i -= 1
                    } else {
                        break
                    }

            })

                Ok(i)
            }

    }
}
unsafe fn lookup_leaf<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(
    txn: &T,
    page: crate::Page,
    k0: &K,
    v0: Option<&V>,
    hdr: &header::Header,
) -> Result<usize, usize> {
    let s = core::slice::from_raw_parts(
        page.data.as_ptr().add(HDR) as *const u16,
        hdr.n() as usize,
    );
    if let Some(v0) = v0 {
        s.binary_search_by(|&off| {
            let off = u16::from_le(off);
            let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
            let k = K::from_raw_ptr(txn, k as *const u8);
            match k.compare(txn, k0) {
                Ordering::Equal => {
                    let v = V::from_raw_ptr(txn, v as *const u8);
                    v.compare(txn, v0)
                }
                cmp => cmp,
            }
        })

        let s = core::slice::from_raw_parts(
            page.data.as_ptr().add(HDR) as *const u64,
            hdr.n() as usize,
        );
        if let Some(v0) = v0 {
            s.binary_search_by(|&off| {
                let off = u64::from_le(off) & 0xfff;
                let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));
                let k = K::from_raw_ptr(txn, k);
                match k.compare(txn, k0) {
                    Ordering::Equal => {
                        let v = V::from_raw_ptr(txn, v);
                        v.compare(txn, v0)

        match s.binary_search_by(|&off| {
            let off = u16::from_le(off);
            let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
            let k = K::from_raw_ptr(txn, k);
            k.compare(txn, k0)
        }) {
            Err(e) => Err(e),
            Ok(mut i) => {
                // Rewind if there are multiple matching keys.
                while i > 0 {
                    let off = u16::from_le(s[i-1]);
                    let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));
                    let k = K::from_raw_ptr(txn, k);
                    if let Ordering::Equal = k.compare(txn, k0) {
                        i -= 1
                    } else {
                        break

                    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);
                match k.compare(txn, k0) {
                    Ordering::Equal => Ordering::Greater,
                    cmp => cmp

            })

                Ok(i)
            }

pub use del::del;

pub use del::{del, del_no_decr};

impl<K:Storable, V:Storable, P: BTreePage<K, V> + core::fmt::Debug> Storable for Db_<K, V, P> {
    type PageReferences = core::iter::Once<u64>;
    fn page_references(&self) -> Self::PageReferences {
        core::iter::once(self.db)
    }
    fn drop<T: AllocPage>(&self, t: &mut T) -> Result<(), T::Error> {
        drop_(t, self)
    }
}

/// to `(k, v)` if `v.is_some()`).

/// to `(k, v)` if `v.is_some()`), and return `true` if this entry is
/// shared with another structure (i.e. the RC of at least one page
/// along a path to the entry is at least 2).
pub fn get_shared<'a, T: LoadPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>(
    txn: &'a T,
    db: &Db_<K, V, P>,
    k: &K,
    v: Option<&V>,
) -> Result<Option<(&'a K, &'a V, bool)>, T::Error> {
    // Set the "cursor stack" by setting a skip list cursor in
    // each page from the root to the appropriate leaf.
    let mut last_match = None;
    let mut page = txn.load_page(db.db)?;
    let mut is_shared = txn.rc(db.db)? >= 2;
    // This is a for loop, to allow the compiler to unroll (maybe).
    for _ in 0..cursor::N_CURSORS {
        let mut cursor = P::cursor_before(&page);
        if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), &mut cursor, k, v) {
            if v.is_some() {
                return Ok(Some((kk, vv, is_shared)));
            }
            last_match = Some((kk, vv, is_shared));
        } else if let Some((k, v, _)) = P::current(txn, page.as_page(), &cursor) {
            // Here, Rust says that `k` and `v` have the same lifetime
            // as `page`, but we actually know that they're alive for
            // as long as `txn` doesn't change, so we can safely
            // extend their lifetimes:
            unsafe { last_match = Some((core::mem::transmute(k), core::mem::transmute(v), is_shared)) }
        }
        // The cursor is set to the first element greater than or
        // equal to the (k, v) we're looking for, so we need to
        // explore the left subtree.
        let next_page = P::left_child(page.as_page(), &cursor);
        if next_page > 0 {
            page = txn.load_page(next_page)?;
            is_shared |= txn.rc(db.db)? >= 2;
        } else {
            break;
        }
    }
    Ok(last_match)
}
/// Get the first entry of a database greater than or equal to `k` (or
/// to `(k, v)` if `v.is_some()`), and return `true` if this entry is
/// shared with another structure (i.e. the RC of at least one page
/// along a path to the entry is at least 2).

    // Unfortunately, since the above function `get_shared` uses this
    // one in order to get the RC of pages, we can't really refactor,
    // so this is mostly a copy of the other function.

) -> Result<(), T::Error> {
    drop_(txn, &db)
}
fn drop_<T: AllocPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>(
    txn: &mut T,
    db: &Db_<K, V, P>,

                for o in k.page_references().chain(v.page_references()) {
                    txn.decr_rc(o)?;
                }

                k.drop(txn)?;
                v.drop(txn)?;

    del_at_cursor(txn, db, &mut cursor)

    del_at_cursor(txn, db, &mut cursor, true)
}
/// If `value` is `None`, delete the first entry for `key` from the
/// database, if present. Else, delete the entry for `(key, value)`,
/// if present.
pub fn del_no_decr<
    T: AllocPage + LoadPage,
    K: Storable + ?Sized + PartialEq,
    V: Storable + ?Sized + PartialEq,
    P: BTreeMutPage<K, V>,
>(
    txn: &mut T,
    db: &mut Db_<K, V, P>,
    key: &K,
    value: Option<&V>,
) -> Result<bool, T::Error> {
    let mut cursor = Cursor::new(txn, db)?;
    // If the key and value weren't found, return.
    match (cursor.set(txn, key, value)?, value) {
        (Some((k, v)), Some(value)) if k == key && v == value => {}
        (Some((k, _)), None) if k == key => {}
        _ => return Ok(false),
    }
    // 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.
    del_at_cursor(txn, db, &mut cursor, false)

    decr_del_rc: bool,

    if p0 < cursor.first_rc_len() {

    //
    // Note in particular that if p0 == cursor.first_rc_len(), then we
    // don't need to touch the RC, since we're cloning this page, but
    // without including a reference to the deleted entry.
    if decr_del_rc && p0 < cursor.first_rc_len() {

        for o in delk.page_references().chain(delv.page_references()) {
            txn.decr_rc(o)?;
        }

        delk.drop(txn)?;
        delv.drop(txn)?;

version = "1.2.14"

version = "1.2.16"

    /// Offsets of pages free at the start of the transaction.
    initial_free: (usize, Vec<u64>),

  /// Borrow env
  pub fn env_borrow(&self) -> &Env {
    self.env.borrow()
  }

    /// Borrow env
    pub fn env_borrow(&self) -> &Env {
        self.env.borrow()
    }

        parent.initial_free.0 = self.initial_free.0;

            Ok(MutTxn {

            let mut txn = MutTxn {

                initial_free: (0, Vec::new()),

            })

            };
            if txn.free > 0 {
                let free_db: btree::Db<u64, ()> = btree::Db::from_page(txn.free);
                let mut init = Vec::new();
                for p in btree::rev_iter(&txn, &free_db, None)? {
                    let (p, _) = p?;
                    init.push(*p)
                }
                txn.initial_free = (init.len(), init)
            }
            Ok(txn)

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

                debug!("free_db = {:x}", free_db.db);
                {
                    for p in btree::iter(&self, &free_db, None).unwrap() {
                        debug!("was free: p = {:x}", p.unwrap().0);
                    }
                    for p in self.free_pages.iter().chain(self.free_owned_pages.iter()) {
                        debug!("free_pages {:x}", p);
                    }
                }
                // Deleting the pages allocated during this transaction.
                let mut f = self.initial_free.1.len();
                while f > self.initial_free.0 {
                    f -= 1;
                    let p = self.initial_free.1[f];
                    btree::del(&mut self, &mut free_db, &p.to_le(), None)?;
                }

                // First, set the free table to 0 in this transaction, to
                // avoid recursing in the calls to `put` below (indeed,
                // the table of free pages is used when allocating new
                // pages, which may happen in a call to `put`).
                self.free = 0;
                // Then, while there are pages to free, free them. Since
                // the calls to `put` below might free pages (and add
                // pages to these two vectors), the (outer) loop might run
                // for more than one iteration.

            }
            unsafe {
                debug!(
                    "commit page {:x}: {:?}",
                    p.0.offset,
                    std::slice::from_raw_parts(p.0.data, 32)
                );

            debug!("root_db: {:?}", rr);
            debug!("committing root: {:?} {:?}", r, rr);

        if self.free == 0 {
            debug!("self.free = 0");
            return Ok(None);
        }
        let mut db: btree::Db<u64, ()> = btree::Db::from_page(self.free);
        let mut curs = btree::cursor::Cursor::new(self, &db)?;
        curs.set_last(self)?;
        let mut f = if let Some((f, ())) = curs.prev(self)? {
            *f
        } else {
            return Ok(None);
        };
        // Get the last page that is also free in all other versions.
        loop {
            debug!("trying 0x{:x}", f);

        while self.initial_free.0 > 0 {
            self.initial_free.0 -= 1;
            let f = self.initial_free.1[self.initial_free.0];

                break;
            } else if let Some((f_, ())) = curs.prev(self)? {
                f = *f_
            } else {
                debug!("no more candidate");
                return Ok(None);

                return Ok(Some(f));

        self.free = 0;
        assert!(btree::del::del(self, &mut db, &f, None)?);
        self.free = db.db;
        Ok(Some(f))

        Ok(None)

                btree::del::del_at_cursor(self, &mut rc_, &mut curs)?;

                btree::del::del_at_cursor(self, &mut rc_, &mut curs, true)?;

            debug!("incr rc 0x{:x} {:?}", off, rc+1);

            debug!("incr rc 0x{:x} {:?}", off, rc + 1);

    }
}
pub trait Check: core::fmt::Debug {
    fn add_refs<T: LoadPage>(
        &self,
        _txn: &T,
        _refs: &mut std::collections::BTreeMap<u64, usize>,
    ) -> Result<(), T::Error>
    where
        T::Error: std::fmt::Debug,
    {
        Ok(())

impl Check for u64 {}
impl Check for () {}

impl<K: Check + Ord + UnsizedStorable + ?Sized, V: Check + Ord + UnsizedStorable + ?Sized, P: BTreePage<K, V> + std::fmt::Debug> Check
    for Db_<K, V, P>
{
    fn add_refs<T: LoadPage>(
        &self,
        txn: &T,
        pages: &mut std::collections::BTreeMap<u64, usize>,
    ) -> Result<(), T::Error>
    where
        T::Error: std::fmt::Debug,
    {
        use std::collections::btree_map::Entry;
        let mut stack = vec![self.db];
        while let Some(p) = stack.pop() {
            match pages.entry(p) {
                Entry::Vacant(e) => {
                    debug!("add_refs: 0x{:x}", p);
                    e.insert(1);
                    let p = txn.load_page(p)?;
                    let mut c = P::cursor_first(&p);
                    let l = P::left_child(p.as_page(), &c);
                    if l > 0 {
                        stack.push(l);
                    }
                    let mut kv = None;
                    while let Some((k, v, r)) = P::next(txn, p.as_page(), &mut c) {
                        debug!("{:?} {:?} {:?}", k, v, kv);
                        if let Some((k_, v_)) = kv {
                            debug!("{:?} {:?} {:?}", k_ > k, k_ == k, v_ > v);
                            if k_ > k || (k_ == k && v_ > v) {
                                debug(txn, &[self], "debug_ord", true);
                                panic!("{:?} {:?} {:?} {:?} {:?}", kv, k_, v_, k_ > k, v_ > v);
                            }
                        }
                        k.add_refs(txn, pages)?;
                        v.add_refs(txn, pages)?;
                        kv = Some((k, v));
                        if r > 0 {
                            stack.push(r);
                        }
                    }
                }
                Entry::Occupied(mut e) => {
                    e.insert(e.get() + 1);
                }
            }
        }
        Ok(())
    }
}

    }
}
pub fn add_refs<T: LoadPage, K: Storable + Ord + ?Sized + std::fmt::Debug, V: Storable + Ord + ?Sized + std::fmt::Debug, P: BTreePage<K, V>>(
    txn: &T,
    db: &Db_<K, V, P>,
    pages: &mut std::collections::BTreeMap<u64, usize>,
) -> Result<(), T::Error>
where
    T::Error: std::fmt::Debug
{
    use std::collections::btree_map::Entry;
    let mut stack = vec![db.db];
    while let Some(p) = stack.pop() {
        match pages.entry(p) {
            Entry::Vacant(e) => {
                debug!("add_refs: 0x{:x}", p);
                e.insert(1);
                let p = txn.load_page(p)?;
                let mut c = P::cursor_first(&p);
                let l = P::left_child(p.as_page(), &c);
                if l > 0 {
                    stack.push(l);
                }
                let mut kv = None;
                while let Some((k, v, r)) = P::next(txn, p.as_page(), &mut c) {
                    debug!("{:?} {:?} {:?}", k, v, kv);
                    if let Some((k_, v_)) = kv {
                        debug!("{:?} {:?} {:?}", k_ > k, k_ == k, v_ > v);
                        if k_ > k || (k_ == k && v_ > v) {
                            debug(txn, &[db], "debug_ord", true);
                            panic!("{:?} {:?} {:?} {:?} {:?}", kv, k_, v_, k_>k, v_>v);
                        }
                    }
                    kv = Some((k, v));
                    if r > 0 {
                        stack.push(r);
                    }
                }
            }
            Entry::Occupied(mut e) => {
                e.insert(e.get() + 1);
            }
        }

    Ok(())

            add_refs(txn, &free_db, pages)?;

            free_db.add_refs(txn, pages)?;

            add_refs(txn, &rc_db, pages)?;

            rc_db.add_refs(txn, pages)?;

        add_refs(txn, &free_db, pages)?;

        free_db.add_refs(txn, pages)?;

        add_refs(txn, &rc, pages)?;

        rc.add_refs(txn, pages)?;

pub fn check_refs<B: std::borrow::Borrow<crate::Env>, T>(txn: &crate::MutTxn<B, T>, refs: &std::collections::BTreeMap<u64, usize>) {

pub fn check_refs<B: std::borrow::Borrow<crate::Env>, T>(
    txn: &crate::MutTxn<B, T>,
    refs: &std::collections::BTreeMap<u64, usize>,
) {