bbolt_rs/
iter.rs

1use crate::bucket::BucketIApi;
2use crate::common::page::tree::leaf::BUCKET_LEAF_FLAG;
3use crate::cursor::{CursorIApi, InnerCursor};
4use crate::tx::TxIApi;
5use crate::{BucketApi, BucketImpl, BucketRwImpl, TxImpl, TxRef, TxRwImpl, TxRwRef};
6use itertools::rev;
7use std::marker::PhantomData;
8
9#[derive(Clone)]
10struct KvIter<'tx: 'p, 'p> {
11  next: InnerCursor<'tx>,
12  next_started: bool,
13  back: InnerCursor<'tx>,
14  back_started: bool,
15  p: PhantomData<&'p u8>,
16}
17
18impl<'tx: 'p, 'p> KvIter<'tx, 'p> {
19  pub(crate) fn new(c: InnerCursor<'tx>) -> KvIter<'tx, 'p> {
20    KvIter {
21      next: c.clone(),
22      next_started: false,
23      back: c,
24      back_started: false,
25      p: PhantomData,
26    }
27  }
28}
29
30impl<'tx: 'p, 'p> Iterator for KvIter<'tx, 'p> {
31  type Item = (&'p [u8], &'p [u8], u32);
32
33  fn next(&mut self) -> Option<Self::Item> {
34    if self.next_started && self.back_started && self.next == self.back {
35      return None;
36    }
37    if self.next_started {
38      self.next.i_next()
39    } else {
40      self.next_started = true;
41      self.next.i_first()
42    }
43  }
44}
45
46impl<'tx: 'p, 'p> DoubleEndedIterator for KvIter<'tx, 'p> {
47  fn next_back(&mut self) -> Option<Self::Item> {
48    if self.next_started && self.back_started && self.next == self.back {
49      return None;
50    }
51    if self.back_started {
52      self.back.i_prev()
53    } else {
54      self.back_started = true;
55      self.back.api_last();
56      self.back.key_value()
57    }
58  }
59}
60
61#[derive(Clone)]
62pub struct EntryIter<'tx: 'p, 'p> {
63  i: KvIter<'tx, 'p>,
64}
65
66impl<'tx: 'p, 'p> EntryIter<'tx, 'p> {
67  pub(crate) fn new(c: InnerCursor<'tx>) -> EntryIter<'tx, 'p> {
68    EntryIter { i: KvIter::new(c) }
69  }
70}
71
72impl<'tx: 'p, 'p> Iterator for EntryIter<'tx, 'p> {
73  type Item = (&'p [u8], &'p [u8]);
74
75  fn next(&mut self) -> Option<Self::Item> {
76    while let Some((k, v, flags)) = self.i.next() {
77      if flags & BUCKET_LEAF_FLAG == 0 {
78        return Some((k, v));
79      }
80    }
81    None
82  }
83}
84
85impl<'tx: 'p, 'p> DoubleEndedIterator for EntryIter<'tx, 'p> {
86  fn next_back(&mut self) -> Option<Self::Item> {
87    while let Some((k, v, flags)) = self.i.next_back() {
88      if flags & BUCKET_LEAF_FLAG == 0 {
89        return Some((k, v));
90      }
91    }
92    None
93  }
94}
95
96pub struct BucketIter<'tx: 'p, 'p> {
97  i: KvIter<'tx, 'p>,
98}
99
100impl<'tx: 'p, 'p> BucketIter<'tx, 'p> {
101  pub(crate) fn new(c: InnerCursor<'tx>) -> BucketIter<'tx, 'p> {
102    BucketIter { i: KvIter::new(c) }
103  }
104}
105
106impl<'tx: 'p, 'p> Iterator for BucketIter<'tx, 'p> {
107  type Item = (&'p [u8], BucketImpl<'tx, 'p>);
108
109  fn next(&mut self) -> Option<Self::Item> {
110    while let Some((k, _, flags)) = self.i.next() {
111      if flags & BUCKET_LEAF_FLAG != 0 {
112        let bucket = BucketImpl::from(self.i.next.bucket.api_bucket(k).unwrap());
113        return Some((k, bucket));
114      }
115    }
116    None
117  }
118}
119
120impl<'tx: 'p, 'p> DoubleEndedIterator for BucketIter<'tx, 'p> {
121  fn next_back(&mut self) -> Option<Self::Item> {
122    while let Some((k, _, flags)) = self.i.next_back() {
123      if flags & BUCKET_LEAF_FLAG != 0 {
124        let bucket = BucketImpl::from(self.i.back.bucket.api_bucket(k).unwrap());
125        return Some((k, bucket));
126      }
127    }
128    None
129  }
130}
131
132impl<'tx: 'a, 'a> IntoIterator for &'a TxImpl<'tx> {
133  type Item = (&'a [u8], BucketImpl<'tx, 'a>);
134  type IntoIter = BucketIter<'tx, 'a>;
135
136  fn into_iter(self) -> Self::IntoIter {
137    BucketIter::new(self.tx.api_cursor())
138  }
139}
140
141impl<'tx: 'a, 'a> IntoIterator for &'a TxRwImpl<'tx> {
142  type Item = (&'a [u8], BucketImpl<'tx, 'a>);
143  type IntoIter = BucketIter<'tx, 'a>;
144
145  fn into_iter(self) -> Self::IntoIter {
146    BucketIter::new(self.tx.api_cursor())
147  }
148}
149
150impl<'tx: 'a, 'a> IntoIterator for &'a TxRef<'tx> {
151  type Item = (&'a [u8], BucketImpl<'tx, 'a>);
152  type IntoIter = BucketIter<'tx, 'a>;
153
154  fn into_iter(self) -> Self::IntoIter {
155    BucketIter::new(self.tx.api_cursor())
156  }
157}
158
159impl<'tx: 'a, 'a> IntoIterator for &'a TxRwRef<'tx> {
160  type Item = (&'a [u8], BucketImpl<'tx, 'a>);
161  type IntoIter = BucketIter<'tx, 'a>;
162
163  fn into_iter(self) -> Self::IntoIter {
164    BucketIter::new(self.tx.api_cursor())
165  }
166}
167
168pub struct BucketIterMut<'tx: 'p, 'p> {
169  i: KvIter<'tx, 'p>,
170}
171
172impl<'tx: 'p, 'p> BucketIterMut<'tx, 'p> {
173  pub(crate) fn new(c: InnerCursor<'tx>) -> BucketIterMut<'tx, 'p> {
174    BucketIterMut { i: KvIter::new(c) }
175  }
176}
177
178impl<'tx: 'p, 'p> Iterator for BucketIterMut<'tx, 'p> {
179  type Item = (&'p [u8], BucketRwImpl<'tx, 'p>);
180
181  fn next(&mut self) -> Option<Self::Item> {
182    while let Some((k, _, flags)) = self.i.next() {
183      if flags & BUCKET_LEAF_FLAG != 0 {
184        let bucket = BucketRwImpl::from(self.i.next.bucket.api_bucket(k).unwrap());
185        return Some((k, bucket));
186      }
187    }
188    None
189  }
190}
191
192impl<'tx: 'p, 'p> DoubleEndedIterator for BucketIterMut<'tx, 'p> {
193  fn next_back(&mut self) -> Option<Self::Item> {
194    while let Some((k, _, flags)) = self.i.next_back() {
195      if flags & BUCKET_LEAF_FLAG != 0 {
196        let bucket = BucketRwImpl::from(self.i.back.bucket.api_bucket(k).unwrap());
197        return Some((k, bucket));
198      }
199    }
200    None
201  }
202}
203
204impl<'tx: 'a, 'a> IntoIterator for &'a mut TxRwImpl<'tx> {
205  type Item = (&'a [u8], BucketRwImpl<'tx, 'a>);
206  type IntoIter = BucketIterMut<'tx, 'a>;
207
208  fn into_iter(self) -> Self::IntoIter {
209    BucketIterMut::new(self.tx.api_cursor())
210  }
211}
212
213impl<'tx: 'a, 'a> IntoIterator for &'a mut TxRwRef<'tx> {
214  type Item = (&'a [u8], BucketRwImpl<'tx, 'a>);
215  type IntoIter = BucketIterMut<'tx, 'a>;
216
217  fn into_iter(self) -> Self::IntoIter {
218    BucketIterMut::new(self.tx.api_cursor())
219  }
220}
221
222pub enum ValueBucket<'tx: 'p, 'p> {
223  Value(&'p [u8]),
224  Bucket(BucketImpl<'tx, 'p>),
225}
226
227pub struct ValueBucketIter<'tx: 'p, 'p> {
228  i: KvIter<'tx, 'p>,
229}
230
231impl<'tx: 'p, 'p> ValueBucketIter<'tx, 'p> {
232  pub(crate) fn new(c: InnerCursor<'tx>) -> ValueBucketIter<'tx, 'p> {
233    ValueBucketIter { i: KvIter::new(c) }
234  }
235}
236
237impl<'tx: 'p, 'p> Iterator for ValueBucketIter<'tx, 'p> {
238  type Item = (&'p [u8], ValueBucket<'tx, 'p>);
239
240  fn next(&mut self) -> Option<Self::Item> {
241    if let Some((k, v, flags)) = self.i.next() {
242      return if flags & BUCKET_LEAF_FLAG == 0 {
243        Some((k, ValueBucket::Value(v)))
244      } else {
245        let bucket = BucketImpl::from(self.i.next.bucket.api_bucket(k).unwrap());
246        Some((k, ValueBucket::Bucket(bucket)))
247      };
248    }
249    None
250  }
251}
252
253impl<'tx: 'p, 'p> DoubleEndedIterator for ValueBucketIter<'tx, 'p> {
254  fn next_back(&mut self) -> Option<Self::Item> {
255    if let Some((k, v, flags)) = self.i.next_back() {
256      return if flags & BUCKET_LEAF_FLAG == 0 {
257        Some((k, ValueBucket::Value(v)))
258      } else {
259        let bucket = BucketImpl::from(self.i.back.bucket.api_bucket(k).unwrap());
260        Some((k, ValueBucket::Bucket(bucket)))
261      };
262    }
263    None
264  }
265}
266
267#[derive(Debug)]
268pub enum ValueBucketSeq<'p> {
269  Value(&'p [u8]),
270  BucketSeq(u64),
271}
272
273impl<'p> ValueBucketSeq<'p> {
274  pub fn len(&self) -> usize {
275    match self {
276      ValueBucketSeq::Value(v) => v.len(),
277      ValueBucketSeq::BucketSeq(_) => 0,
278    }
279  }
280}
281
282pub struct DbWalker<'tx: 'p, 'p> {
283  root_buckets: BucketIter<'tx, 'p>,
284  path: Vec<&'p [u8]>,
285  cursors: Vec<ValueBucketIter<'tx, 'p>>,
286  bucket_seq: bool,
287  p: PhantomData<&'p u8>,
288}
289
290impl<'tx: 'p, 'p> DbWalker<'tx, 'p> {
291  pub(crate) fn new(root_cursor: InnerCursor<'tx>) -> DbWalker<'tx, 'p> {
292    DbWalker {
293      root_buckets: BucketIter::new(root_cursor),
294      path: Vec::new(),
295      cursors: Vec::new(),
296      bucket_seq: false,
297      p: PhantomData,
298    }
299  }
300
301  pub fn path(&self) -> &[&'p [u8]] {
302    if self.bucket_seq {
303      self.path.split_last().unwrap().1
304    } else {
305      &self.path
306    }
307  }
308}
309
310impl<'tx: 'p, 'p> Iterator for DbWalker<'tx, 'p> {
311  type Item = (&'p [u8], ValueBucketSeq<'p>);
312
313  fn next(&mut self) -> Option<Self::Item> {
314    self.bucket_seq = false;
315    loop {
316      if self.cursors.is_empty() {
317        return if let Some((k, b)) = self.root_buckets.next() {
318          let seq = b.sequence();
319          self.bucket_seq = true;
320          self.path.push(k);
321          let i = ValueBucketIter::new(b.b.i_cursor());
322          self.cursors.push(i);
323          Some((k, ValueBucketSeq::BucketSeq(seq)))
324        } else {
325          None
326        };
327      }
328      if let Some((k, vb)) = self.cursors.last_mut().and_then(|i| i.next()) {
329        return match vb {
330          ValueBucket::Value(v) => Some((k, ValueBucketSeq::Value(v))),
331          ValueBucket::Bucket(b) => {
332            let seq = b.sequence();
333            self.bucket_seq = true;
334            self.path.push(k);
335            let i = ValueBucketIter::new(b.b.i_cursor());
336            self.cursors.push(i);
337            Some((k, ValueBucketSeq::BucketSeq(seq)))
338          }
339        };
340      } else {
341        self.path.pop();
342        self.cursors.pop();
343      }
344    }
345  }
346}
347
348#[cfg(test)]
349mod test {
350  use crate::iter::DbWalker;
351  use crate::test_support::TestDb;
352  use crate::tx::TxIApi;
353  use crate::{BucketApi, BucketRwApi, DbRwAPI, TxRwRefApi};
354
355  #[test]
356  fn test_tx_for_each_no_error() -> crate::Result<()> {
357    let mut db = TestDb::new()?;
358    db.update(|mut tx| {
359      let mut b = tx.create_bucket("widgets")?;
360      b.put("foo", "bar")?;
361
362      for (k, mut b) in tx.iter_mut_buckets() {
363        let mut wb = b.create_bucket("woojits")?;
364        wb.put("fooz", "ball")?;
365        for (k, wb) in b.iter_buckets() {
366          println!("{:?}", k);
367          for (k, v) in wb.iter_entries() {
368            println!("{:?}", k);
369          }
370        }
371      }
372      Ok(())
373    })?;
374    Ok(())
375  }
376
377  #[test]
378  fn test_tx_walk_no_error() -> crate::Result<()> {
379    let mut db = TestDb::new()?;
380    db.update(|mut tx| {
381      let mut b = tx.create_bucket("widgets")?;
382      b.put("foo1", "bar")?;
383      b.put("foo2", "bar")?;
384      let mut wb = b.create_bucket("woojits")?;
385      wb.set_sequence(1)?;
386      wb.put("fooz1", "ball")?;
387      wb.put("fooz2", "ball")?;
388      let mut hb = wb.create_bucket("hoojits")?;
389      hb.set_sequence(2)?;
390      hb.put("fooz1", "bill")?;
391      hb.put("fooz2", "bill")?;
392      let mut wb = b.create_bucket("wajits")?;
393      wb.set_sequence(3)?;
394      wb.put("fooz1", "balls")?;
395      wb.put("fooz2", "balls")?;
396      let mut pb = tx.create_bucket_path(&["one", "two", "three", "four"])?;
397      pb.set_sequence(4)?;
398      pb.put("five", "six")?;
399      Ok(())
400    })?;
401    let tx = db.begin_tx()?;
402    let mut w = DbWalker::new(tx.tx.api_cursor());
403    while let Some(i) = w.next() {
404      let path = w.path();
405      println!("{:?}: {:?}", path, i);
406    }
407    drop(w);
408    let c = DbWalker::new(tx.tx.api_cursor()).count();
409    println!("{:?}", c);
410    Ok(())
411  }
412}
bbolt_rs/iter.rs

bbolt_rs/
iter.rs
