1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

use super::*;

use pagecache::PageGet;
use epoch::pin;

/// An iterator over keys and values in a `Tree`.
pub struct Iter<'a> {
    pub(super) id: PageID,
    pub(super) inner:
        &'a PageCache<BLinkMaterializer, Frag, Vec<(PageID, PageID)>>,
    pub(super) last_key: Bound,
    pub(super) broken: Option<Error<()>>,
    pub(super) done: bool,
    // TODO we have to refactor this in light of pages being deleted
}

impl<'a> Iterator for Iter<'a> {
    type Item = DbResult<(Vec<u8>, Vec<u8>), ()>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.done {
            return None;
        } else if let Some(broken) = self.broken.take() {
            self.done = true;
            return Some(Err(broken));
        };

        let guard = pin();
        loop {
            let res = self.inner.get(self.id, &guard);

            let node = match res {
                Ok(PageGet::Materialized(Frag::Base(base, _), _)) => base,
                Err(e) => {
                    // TODO(when implementing merge support) this could
                    // be None if the node was removed since the last
                    // iteration, and we need to just get the inner
                    // node again...
                    error!("iteration failed: {:?}", e);
                    self.done = true;
                    return Some(Err(e.danger_cast()));
                }
                other => {
                    panic!(
                        "the pagecache returned an unexpected value \
                        to the Tree iterator: {:?}",
                        other
                    )
                }
            };

            let prefix = node.lo.inner();
            for (ref k, ref v) in node.data.leaf().expect(
                "node should be a leaf",
            )
            {
                let decoded_k = prefix_decode(prefix, k);
                if Bound::Inclusive(decoded_k.clone()) > self.last_key {
                    self.last_key = Bound::Inclusive(decoded_k.to_vec());
                    let ret = Ok((decoded_k, v.clone()));
                    return Some(ret);
                }
            }
            match node.next {
                Some(id) => self.id = id,
                None => return None,
            }
        }
    }
}