use log::*;

    // Set the cursor to the first element larger than or equal to
    // `(key, value)`. We will insert at that position (where "insert"
    // is meant in the sense of Rust's `Vec::insert`.

        // If `(key, value)` already exists in the tree, return.

    // Else, we are at a leaf, since cursors that don't find an
    // element go all the way to the leaves.
    //
    // We put on the leaf page, resulting in a `Put`, i.e. either
    // `Put::Ok` or `Put::Split`.

    // In both cases (`Ok` and `Split`), we need to walk up the tree
    // and update each node.
    // Moreover, since the middle elements of the splits may be on
    // pages that must be freed at the end of this call, we collect
    // them in the `free` array below, and free them only at the end
    // of this function.
    //
    // If we didn't hold on to these pages, they could be reallocated
    // in subsequent splits, and the middle element could be
    // lost. This is important when the middle element climbs up more
    // than one level (i.e. the middle element of the split of a leaf
    // is also the middle element of the split of the leaf's parent,
    // etc).

    let p = cursor.pointer(); // Save the position of cursor at the leaf.

    for f in free.iter() {

    for f in &free[..p] {

    for _ in 0..N_CURSORS {

    loop {

                incr_descendants::<T, K, V, P>(txn, cursor, free, freed, last_freed)?;
                last_freed = freed & !1;

                // Here, we are copying all children of the freed
                // page, except possibly the last freed page (which is
                // a child of the current node, if we aren't at a
                // leaf). This includes the split key/value, also
                // incremented in the following call:
                incr_descendants::<T, K, V, P>(txn, cursor, free, freed, &mut last_freed)?;
                // Then, insert the split key/value in the relevant page:

                    // If we aren't at the root, just pop the cursor
                    // stack and insert a new entry in the page above.

                    // Splitting the root.
                    debug!("split root {:?} {:?}", split_key, split_value);
                    debug!("{:?} {:?}", left, right);

                    // If we are at the root, the root has
                    // split. Insert the split key/value in a new page
                    // above the entire tree.

                    // Return the new root.

                incr_descendants::<T, K, V, P>(txn, cursor, free, freed, last_freed)?;
                last_freed = freed & !1;

                // Same as above: increment the relevant reference
                // counters.
                incr_descendants::<T, K, V, P>(txn, cursor, free, freed, &mut last_freed)?;
                // And update the left child of the current cursor,
                // since the main invariant of cursors is that we're
                // always visiting the left child (if we're visiting
                // the last child of a page, the cursor is set to the
                // position strictly after the entries).

                    // If we aren't at the root, just update the child.

                    // If we are at the root, `page` is the updated root.

    unreachable!()

/// This function does all the memory management for `put`.

    last_freed: u64,

    last_freed: &mut u64,

    debug!(
        "incr_descendants {:?} {:?} {:?} {:?}",
        cursor.current().page,
        freed,
        cursor.pointer(),
        cursor.first_rc_level
    );

        // This also includes the case where cursor.pointer == 0.

        // If a page has split or was immutable (allocated by a
        // previous transaction) and has been updated, we need to free
        // the old page.

        if let Ok(rc) = txn.rc(freed & !1) {
            debug!("rc = {:?}", rc);
        }
        debug!("pointer {:?} {:?}", cursor.pointer(), cursor.first_rc_level);

        // Else, the "freed" page is shared with another tree, and
        // hence we just need to decrement its RC.

        debug!("free child: {:?}", last_freed);

        // This means that the new version of the page (either split
        // or not) contains references to all the children of the
        // freed page, except the last freed page (because the new
        // version of that page isn't shared).

        let mut c = P::cursor_before(cur.page.as_page());
        P::move_next(&mut c);

        // Start a cursor at the leftmost position and increase the
        // leftmost child page's RC (if we aren't at a leaf, and if
        // that child isn't the last freed page).
        let mut c = P::cursor_first(cur.page.as_page());

        if left != 0 && left != last_freed {
            debug!("incr {:?}", left);

        if left != 0 && left != *last_freed {

        // Then, for each entry of the page, increase the RCs of
        // references contained in the keys and values, and increase
        // the RC of the right child.

            if r != 0 && r != last_freed {
                debug!("incr {:?}", r);

            if r != 0 && r != *last_freed {

    // Finally, update the last freed page to be the page we just
    // freed (the `&!1` is here because `freed` might have its LSB set
    // to indicate that `freed` was allocated by the current
    // transaction, but that bit isn't set in references to page
    // `freed` on the parent page).
    *last_freed = freed & !1;

    /// cursor isn't at the end of the page already).

    /// cursor isn't already after the last element).

    // This is a for loop, to allow the compiler to unroll (maybe).

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

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

    // In order to make this function tail-recursive, we simulate a
    // stack with the following:

    let mut ptr = 0;
    // Push the root page of `db` onto the stack.

    let mut ptr = 0;

    // Then perform a DFS:

        // Look at the top element of the stack.

        // If it needs to be dropped (i.e. if its RC is <= 1), iterate
        // its cursor and drop all its referenced pages.

            // if there's a current element in the cursor (i.e. we
            // aren't before or after the elements), decrease its RC.

            // In all cases, move next and push the left child onto
            // the stack. This works because pushed cursors are
            // initially set to before the page's elements.

        // Here, either rc > 1, or else `P::move_next` returned
        // `false`, meaning that the cursor is after the last element.

        // If this was the bottom element of the stack, stop, else, pop.