fn build_from_leaves<I: Iterator<Item = Result<LeafRef<T>>>>(
        leaves: I,
        store: NodeStore<T>,
        comparator: C
    ) -> Result<DurableTree<T, C>> {
        // As we build up the tree, we need to keep track of the
        // rightmost interior node on each level, so that we can
        // append to it. At the beginning, that's just the empty root.
        // The levels are ordered from highest to lowest, so the root
        // of the tree is always last.
        let mut open_nodes: Vec<InteriorNode<T>> = vec![InteriorNode { links: vec![], keys: vec![] }];

        let leaves = leaves.collect::<Vec<_>>();
        // error handling makes this a bit awkward; we need to process
        // the leaf links lazily, but return an error if we encounter
        // an error in the iterator, so instead of folding or
        // something we have to use for loops and a bunch of mutable
        // references
        // TODO: failable iterators?
        for result in leaves {
            let LeafRef { node, mut db_key } = result.expect("no leaf ref");
            let mut key = node.items[0].clone();
            let mut layer = 0;
            loop {
                if open_nodes.len() < layer + 1 {
                    // The tree is full. We need to add a new root node before proceeding.
                    open_nodes.push(InteriorNode { links: vec![], keys: vec![] });
                }


                let parent = &mut open_nodes[layer];
                parent.keys.push(key);
                parent.links.push(Link::DbKey(db_key));

                if parent.links.len() == NODE_CAPACITY {
                    // This node is full, so we need to replace it
                    // with a new empty one, persist it, and add a
                    // link to it to its own parent.
                    let old_node = std::mem::replace(parent, InteriorNode { links: vec![], keys: vec![] });
                    key = old_node.keys[0].clone();
                    db_key = store.add_node(&Node::Interior(old_node)).expect("could not add node");
                    layer += 1;
                    continue;
                } else {
                    break;
                }
            }
        }

        // Now that the tree is built, we need to persist the remaining open nodes.
        let mut open_node_iter = open_nodes.into_iter();
        let first_open_node = open_node_iter.next().unwrap();

        if first_open_node.keys.len() == 0 {
            // an empty directory node means a root
            let root_ref = store.add_node(&Node::Interior(first_open_node))?;
            return Ok(
                DurableTree {
                    store: store,
                    root: root_ref,
                    _comparator: comparator,
                }
            )
        }

        let mut key = first_open_node.keys[0].clone();
        // FIXME: should be able to avoid this clone, I think, maybe requiring
        // a change in the signature of add_node.
        let mut link = store.add_node(&Node::Interior(first_open_node.clone()))?;

        for mut node in open_node_iter {
            if node.keys.len() == 0 {
                // nothing ever got added to this node so it's not needed
                continue;
            }
            node.keys.push(key.clone());
            node.links.push(Link::DbKey(link));
            key = (&node.keys[0]).clone();
            link = store.add_node(&Node::Interior(node))?;
        }

        Ok(DurableTree {
            store: store,
            root: link,
            _comparator: comparator,
        })
    }
/// Builds a new durable store from an iterator of leaf nodes by
/// constructing a new directory tree on top.  The leaves iterator
/// must return items of type Result<(T, Link<T>)>, where the
/// first element of the tuple is the first item in the leaf and
/// the second element is a link to the persisted leaf. This
/// allows unchanged leaves to be preserved if rebuilding a tree.
Builds a new durable store from an iterator of leaf nodes by
constructing a new directory tree on top.  The leaves iterator
must return items of type Result<(T, Link)>, where the
first element of the tuple is the first item in the leaf and
the second element is a link to the persisted leaf. This
allows unchanged leaves to be preserved if rebuilding a tree.
Builds a new durable store from an iterator of leaf nodes by constructing a new directory tree on top . The leaves iterator must return items of type Result< ( T Link ) > where the first element of the tuple is the first item in the leaf and the second element is a link to the persisted leaf . This allows unchanged leaves to be preserved if rebuilding a tree .
fn build_from_leaves<I: Iterator<Item = Result<LeafRef<T>>>>(
        leaves: I,
        store: NodeStore<T>,
        comparator: C
    ) -> Result<DurableTree<T, C>> {
        // As we build up the tree, we need to keep track of the
        // rightmost interior node on each level, so that we can
        // append to it. At the beginning, that's just the empty root.
        // The levels are ordered from highest to lowest, so the root
        // of the tree is always last.
        let mut open_nodes: Vec<InteriorNode<T>> = vec![InteriorNode { links: vec![], keys: vec![] }];
        let leaves = leaves.collect::<Vec<_>>();
        // error handling makes this a bit awkward; we need to process
        // the leaf links lazily, but return an error if we encounter
        // an error in the iterator, so instead of folding or
        // something we have to use for loops and a bunch of mutable
        // references
        // TODO: failable iterators?
        for result in leaves {
            let LeafRef { node, mut db_key } = result.expect("no leaf ref");
            let mut key = node.items[0].clone();
            let mut layer = 0;
            loop {
                if open_nodes.len() < layer + 1 {
                    // The tree is full. We need to add a new root node before proceeding.
                    open_nodes.push(InteriorNode { links: vec![], keys: vec![] });
                }
                let parent = &mut open_nodes[layer];
                parent.keys.push(key);
                parent.links.push(Link::DbKey(db_key));
                if parent.links.len() == NODE_CAPACITY {
                    // This node is full, so we need to replace it
                    // with a new empty one, persist it, and add a
                    // link to it to its own parent.
                    let old_node = std::mem::replace(parent, InteriorNode { links: vec![], keys: vec![] });
                    key = old_node.keys[0].clone();
                    db_key = store.add_node(&Node::Interior(old_node)).expect("could not add node");
                    layer += 1;
                    continue;
                } else {
                    break;
                }
            }
        }
        // Now that the tree is built, we need to persist the remaining open nodes.
        let mut open_node_iter = open_nodes.into_iter();
        let first_open_node = open_node_iter.next().unwrap();
        if first_open_node.keys.len() == 0 {
            // an empty directory node means a root
            let root_ref = store.add_node(&Node::Interior(first_open_node))?;
            return Ok(
                DurableTree {
                    store: store,
                    root: root_ref,
                    _comparator: comparator,
                }
            )
        }
        let mut key = first_open_node.keys[0].clone();
        // FIXME: should be able to avoid this clone, I think, maybe requiring
        // a change in the signature of add_node.
        let mut link = store.add_node(&Node::Interior(first_open_node.clone()))?;
        for mut node in open_node_iter {
            if node.keys.len() == 0 {
                // nothing ever got added to this node so it's not needed
                continue;
            }
            node.keys.push(key.clone());
            node.links.push(Link::DbKey(link));
            key = (&node.keys[0]).clone();
            link = store.add_node(&Node::Interior(node))?;
        }
        Ok(DurableTree {
            store: store,
            root: link,
            _comparator: comparator,
        })
    }
fn build_from_leaves < I : Iterator < Item = Result < LeafRef < T > > > > ( leaves : I , store : NodeStore < T > , comparator : C ) -> Result < DurableTree < T , C > > { // As we build up the tree, we need to keep track of the // rightmost interior node on each level, so that we can // append to it. At the beginning, that's just the empty root. // The levels are ordered from highest to lowest, so the root // of the tree is always last. let mut open_nodes : Vec < InteriorNode < T > > = vec ! [ InteriorNode { links vec [ ] keys vec [ ] } ] ; let leaves = leaves . collect :: < Vec < _ > > ( ) ; // error handling makes this a bit awkward; we need to process // the leaf links lazily, but return an error if we encounter // an error in the iterator, so instead of folding or // something we have to use for loops and a bunch of mutable // references // TODO: failable iterators? for result in leaves { let LeafRef { node , mut db_key } = result . expect ( " " ) ; let mut key = node . items [ 0 ] . clone ( ) ; let mut layer = 0 ; loop { if open_nodes . len ( ) < layer + 1 { // The tree is full. We need to add a new root node before proceeding. open_nodes . push ( InteriorNode { links : vec ! [ ] , keys : vec ! [ ] } ) ; } let parent = & mut open_nodes [ layer ] ; parent . keys . push ( key ) ; parent . links . push ( Link :: DbKey ( db_key ) ) ; if parent . links . len ( ) == NODE_CAPACITY { // This node is full, so we need to replace it // with a new empty one, persist it, and add a // link to it to its own parent. let old_node = std :: mem :: replace ( parent , InteriorNode { links : vec ! [ ] , keys : vec ! [ ] } ) ; key = old_node . keys [ 0 ] . clone ( ) ; db_key = store . add_node ( & Node :: Interior ( old_node ) ) . expect ( " " ) ; layer += 1 ; continue ; } else { break ; } } } // Now that the tree is built, we need to persist the remaining open nodes. let mut open_node_iter = open_nodes . into_iter ( ) ; let first_open_node = open_node_iter . next ( ) . unwrap ( ) ; if first_open_node . keys . len ( ) == 0 { // an empty directory node means a root let root_ref = store . add_node ( & Node :: Interior ( first_open_node ) ) ? ; return Ok ( DurableTree { store : store , root : root_ref , _comparator : comparator , } ) } let mut key = first_open_node . keys [ 0 ] . clone ( ) ; // FIXME: should be able to avoid this clone, I think, maybe requiring // a change in the signature of add_node. let mut link = store . add_node ( & Node :: Interior ( first_open_node . clone ( ) ) ) ? ; for mut node in open_node_iter { if node . keys . len ( ) == 0 { // nothing ever got added to this node so it's not needed continue ; } node . keys . push ( key . clone ( ) ) ; node . links . push ( Link :: DbKey ( link ) ) ; key = ( & node . keys [ 0 ] ) . clone ( ) ; link = store . add_node ( & Node :: Interior ( node ) ) ? ; } Ok ( DurableTree { store : store , root : link , _comparator : comparator , } ) }
Builds a new durable store from an iterator of leaf nodes by
constructing a new directory tree on top.
Builds a new durable store from an iterator of leaf nodes by constructing a new directory tree on top .
leaves
I
store
NodeStore<T>
comparator
C
leaves
I
store
NodeStore<T>
comparator
C