leveldb/database/
iterator.rs

1//! leveldb iterators
2//!
3//! Iteration is one of the most important parts of leveldb. This module provides
4//! Iterators to iterate over key, values and pairs of both.
5use super::options::{c_readoptions, ReadOptions};
6use super::Database;
7use crate::database::snapshots::Snapshot;
8use cruzbit_leveldb_sys::*;
9use libc::{c_char, size_t};
10use std::iter;
11use std::marker::PhantomData;
12use std::slice::from_raw_parts;
13
14#[allow(missing_docs)]
15struct RawIterator {
16    ptr: *mut leveldb_iterator_t,
17}
18
19#[allow(missing_docs)]
20impl Drop for RawIterator {
21    fn drop(&mut self) {
22        unsafe { leveldb_iter_destroy(self.ptr) }
23    }
24}
25
26/// An iterator over the leveldb keyspace.
27///
28/// Returns key and value as a tuple.
29pub struct Iterator<'a> {
30    iter: RawIterator,
31    start: bool,
32    // Iterator accesses the Database through a leveldb_iter_t pointer
33    // but needs to hold the reference for lifetime tracking
34    #[allow(dead_code)]
35    database: PhantomData<&'a Database>,
36    from: Option<&'a [u8]>,
37    to: Option<&'a [u8]>,
38    prefix: Option<&'a [u8]>,
39}
40
41/// An iterator over the leveldb keyspace  that browses the keys backwards.
42///
43/// Returns key and value as a tuple.
44pub struct RevIterator<'a> {
45    iter: RawIterator,
46    start: bool,
47    // Iterator accesses the Database through a leveldb_iter_t pointer
48    // but needs to hold the reference for lifetime tracking
49    #[allow(dead_code)]
50    database: PhantomData<&'a Database>,
51    from: Option<&'a [u8]>,
52    to: Option<&'a [u8]>,
53    prefix: Option<&'a [u8]>,
54}
55
56/// An iterator over the leveldb keyspace.
57///
58/// Returns just the keys.
59pub struct KeyIterator<'a> {
60    inner: Iterator<'a>,
61}
62
63/// An iterator over the leveldb keyspace that browses the keys backwards.
64///
65/// Returns just the keys.
66pub struct RevKeyIterator<'a> {
67    inner: RevIterator<'a>,
68}
69
70/// An iterator over the leveldb keyspace.
71///
72/// Returns just the value.
73pub struct ValueIterator<'a> {
74    inner: Iterator<'a>,
75}
76
77/// An iterator over the leveldb keyspace that browses the keys backwards.
78///
79/// Returns just the value.
80pub struct RevValueIterator<'a> {
81    inner: RevIterator<'a>,
82}
83
84/// A trait to allow access to the three main iteration styles of leveldb.
85pub trait Iterable<'a> {
86    /// Return an Iterator iterating over (Key,Value) pairs
87    fn iter(&'a self, options: &ReadOptions) -> Iterator<'a>;
88    /// Returns an Iterator iterating over Keys only.
89    fn keys_iter(&'a self, options: &ReadOptions) -> KeyIterator<'a>;
90    /// Returns an Iterator iterating over Values only.
91    fn value_iter(&'a self, options: &ReadOptions) -> ValueIterator<'a>;
92}
93
94impl<'a> Iterable<'a> for Database {
95    fn iter(&'a self, options: &ReadOptions) -> Iterator<'a> {
96        Iterator::new(self, options, None)
97    }
98
99    fn keys_iter(&'a self, options: &ReadOptions) -> KeyIterator<'a> {
100        KeyIterator::new(self, options, None)
101    }
102
103    fn value_iter(&'a self, options: &ReadOptions) -> ValueIterator<'a> {
104        ValueIterator::new(self, options, None)
105    }
106}
107
108pub trait LevelDBIterator<'a> {
109    type RevIter: LevelDBIterator<'a>;
110
111    fn raw_iterator(&self) -> *mut leveldb_iterator_t;
112
113    fn start(&self) -> bool;
114    fn started(&mut self);
115
116    fn reverse(self) -> Self::RevIter;
117
118    fn from(self, key: &'a [u8]) -> Self;
119    fn to(self, key: &'a [u8]) -> Self;
120    fn prefix(self, key: &'a [u8]) -> Self;
121
122    #[allow(clippy::wrong_self_convention)]
123    fn from_key(&self) -> Option<&'a [u8]>;
124    fn to_key(&self) -> Option<&'a [u8]>;
125    fn prefix_key(&self) -> Option<&'a [u8]>;
126
127    fn valid(&self, reverse: bool) -> bool {
128        if unsafe { leveldb_iter_valid(self.raw_iterator()) != 0 } {
129            if let Some(k) = self.prefix_key() {
130                // match the key with a byte prefix
131                if self.key()[..].starts_with(k) {
132                    return true;
133                }
134            } else {
135                let from = if let Some(k) = self.from_key() {
136                    let comparator: fn(&[u8], &[u8]) -> bool = if reverse {
137                        |a: &[u8], b: &[u8]| -> bool { a <= b }
138                    } else {
139                        |a: &[u8], b: &[u8]| -> bool { a >= b }
140                    };
141                    comparator(&self.key()[..], k)
142                } else {
143                    true
144                };
145
146                let to = if let Some(k) = self.to_key() {
147                    let comparator: fn(&[u8], &[u8]) -> bool = if reverse {
148                        |a: &[u8], b: &[u8]| -> bool { a >= b }
149                    } else {
150                        |a: &[u8], b: &[u8]| -> bool { a <= b }
151                    };
152                    comparator(&self.key()[..], k)
153                } else {
154                    true
155                };
156
157                return from && to;
158            }
159        }
160
161        false
162    }
163
164    /// # Safety
165    unsafe fn advance_raw(&mut self);
166
167    fn advance(&mut self, reverse: bool) -> bool {
168        if !self.start() {
169            unsafe {
170                self.advance_raw();
171            }
172        } else {
173            if let Some(k) = self.prefix_key() {
174                self.seek(k)
175            } else if let Some(k) = self.from_key() {
176                self.seek(k);
177                if !self.valid(reverse) && reverse {
178                    // if from doesn't exist we seeked past it so go back
179                    unsafe {
180                        if leveldb_iter_valid(self.raw_iterator()) != 0 {
181                            self.advance_raw();
182                        }
183                    }
184                }
185            }
186            self.started();
187        }
188
189        self.valid(reverse)
190    }
191
192    fn key(&self) -> Vec<u8> {
193        unsafe {
194            let length: size_t = 0;
195            let value = leveldb_iter_key(self.raw_iterator(), &length) as *const u8;
196            from_raw_parts(value, length as usize).to_vec()
197        }
198    }
199
200    fn value(&self) -> Vec<u8> {
201        unsafe {
202            let length: size_t = 0;
203            let value = leveldb_iter_value(self.raw_iterator(), &length) as *const u8;
204            from_raw_parts(value, length as usize).to_vec()
205        }
206    }
207
208    fn entry(&self) -> (Vec<u8>, Vec<u8>) {
209        (self.key(), self.value())
210    }
211
212    fn seek_to_first(&self) {
213        unsafe {
214            leveldb_iter_seek_to_first(self.raw_iterator());
215        }
216    }
217
218    fn seek_to_last(&self) {
219        if let Some(k) = self.to_key() {
220            self.seek(k);
221        } else {
222            unsafe {
223                leveldb_iter_seek_to_last(self.raw_iterator());
224            }
225        }
226    }
227
228    fn seek(&self, key: &[u8]) {
229        unsafe {
230            leveldb_iter_seek(
231                self.raw_iterator(),
232                key.as_ptr() as *mut c_char,
233                key.len() as size_t,
234            );
235        }
236    }
237}
238
239impl<'a> Iterator<'a> {
240    pub fn new(
241        database: &'a Database,
242        options: &ReadOptions,
243        snapshot: Option<&'a Snapshot>,
244    ) -> Iterator<'a> {
245        unsafe {
246            let c_read_options = c_readoptions(options);
247
248            if let Some(snapshot) = snapshot {
249                leveldb_readoptions_set_snapshot(c_read_options, snapshot.raw_ptr());
250            }
251
252            let ptr = leveldb_create_iterator(database.database.ptr, c_read_options);
253
254            leveldb_readoptions_destroy(c_read_options);
255            leveldb_iter_seek_to_first(ptr);
256
257            Iterator {
258                start: true,
259                iter: RawIterator { ptr },
260                database: PhantomData,
261                from: None,
262                to: None,
263                prefix: None,
264            }
265        }
266    }
267
268    /// return the last element of the iterator
269    pub fn last(&self) -> Option<(Vec<u8>, Vec<u8>)> {
270        self.seek_to_last();
271        Some((self.key(), self.value()))
272    }
273}
274
275impl<'a> LevelDBIterator<'a> for Iterator<'a> {
276    type RevIter = RevIterator<'a>;
277
278    #[inline]
279    fn raw_iterator(&self) -> *mut leveldb_iterator_t {
280        self.iter.ptr
281    }
282
283    #[inline]
284    fn start(&self) -> bool {
285        self.start
286    }
287
288    #[inline]
289    fn started(&mut self) {
290        self.start = false
291    }
292
293    #[inline]
294    unsafe fn advance_raw(&mut self) {
295        leveldb_iter_next(self.raw_iterator());
296    }
297
298    #[inline]
299    fn reverse(self) -> Self::RevIter {
300        if self.start {
301            unsafe {
302                leveldb_iter_seek_to_last(self.iter.ptr);
303            }
304        }
305        RevIterator {
306            start: self.start,
307            database: self.database,
308            iter: self.iter,
309            from: self.from,
310            to: self.to,
311            prefix: self.prefix,
312        }
313    }
314
315    fn from(mut self, key: &'a [u8]) -> Self {
316        self.from = Some(key);
317        self
318    }
319
320    fn to(mut self, key: &'a [u8]) -> Self {
321        self.to = Some(key);
322        self
323    }
324
325    fn prefix(mut self, key: &'a [u8]) -> Self {
326        self.prefix = Some(key);
327        self
328    }
329
330    fn from_key(&self) -> Option<&'a [u8]> {
331        self.from
332    }
333
334    fn to_key(&self) -> Option<&'a [u8]> {
335        self.to
336    }
337
338    fn prefix_key(&self) -> Option<&'a [u8]> {
339        self.prefix
340    }
341}
342
343impl<'a> LevelDBIterator<'a> for RevIterator<'a> {
344    type RevIter = Iterator<'a>;
345
346    #[inline]
347    fn raw_iterator(&self) -> *mut leveldb_iterator_t {
348        self.iter.ptr
349    }
350
351    #[inline]
352    fn start(&self) -> bool {
353        self.start
354    }
355
356    #[inline]
357    fn started(&mut self) {
358        self.start = false
359    }
360
361    #[inline]
362    unsafe fn advance_raw(&mut self) {
363        leveldb_iter_prev(self.raw_iterator());
364    }
365
366    #[inline]
367    fn reverse(self) -> Self::RevIter {
368        if self.start {
369            unsafe {
370                leveldb_iter_seek_to_first(self.iter.ptr);
371            }
372        }
373        Iterator {
374            start: self.start,
375            database: self.database,
376            iter: self.iter,
377            from: self.from,
378            to: self.to,
379            prefix: self.prefix,
380        }
381    }
382
383    fn from(mut self, key: &'a [u8]) -> Self {
384        self.from = Some(key);
385        self
386    }
387
388    fn to(mut self, key: &'a [u8]) -> Self {
389        self.to = Some(key);
390        self
391    }
392
393    fn prefix(mut self, key: &'a [u8]) -> Self {
394        self.prefix = Some(key);
395        self
396    }
397
398    fn from_key(&self) -> Option<&'a [u8]> {
399        self.from
400    }
401
402    fn to_key(&self) -> Option<&'a [u8]> {
403        self.to
404    }
405
406    fn prefix_key(&self) -> Option<&'a [u8]> {
407        self.prefix
408    }
409}
410
411impl<'a> KeyIterator<'a> {
412    pub fn new(
413        database: &'a Database,
414        options: &ReadOptions,
415        snapshot: Option<&'a Snapshot>,
416    ) -> KeyIterator<'a> {
417        KeyIterator {
418            inner: Iterator::new(database, options, snapshot),
419        }
420    }
421
422    /// return the last element of the iterator
423    pub fn last(self) -> Option<Vec<u8>> {
424        self.seek_to_last();
425        Some(self.key())
426    }
427}
428
429impl<'a> ValueIterator<'a> {
430    pub fn new(
431        database: &'a Database,
432        options: &ReadOptions,
433        snapshot: Option<&'a Snapshot>,
434    ) -> ValueIterator<'a> {
435        ValueIterator {
436            inner: Iterator::new(database, options, snapshot),
437        }
438    }
439
440    /// return the last element of the iterator
441    pub fn last(self) -> Option<Vec<u8>> {
442        self.seek_to_last();
443        Some(self.value())
444    }
445}
446
447macro_rules! impl_leveldb_iterator {
448    ($T:ty, $RevT:ty) => {
449        impl<'a> LevelDBIterator<'a> for $T {
450            type RevIter = $RevT;
451
452            #[inline]
453            fn raw_iterator(&self) -> *mut leveldb_iterator_t {
454                self.inner.iter.ptr
455            }
456
457            #[inline]
458            fn start(&self) -> bool {
459                self.inner.start
460            }
461
462            #[inline]
463            fn started(&mut self) {
464                self.inner.start = false
465            }
466
467            #[inline]
468            unsafe fn advance_raw(&mut self) {
469                self.inner.advance_raw();
470            }
471
472            #[inline]
473            fn reverse(self) -> Self::RevIter {
474                Self::RevIter {
475                    inner: self.inner.reverse(),
476                }
477            }
478
479            fn from(mut self, key: &'a [u8]) -> Self {
480                self.inner.from = Some(key);
481                self
482            }
483
484            fn to(mut self, key: &'a [u8]) -> Self {
485                self.inner.to = Some(key);
486                self
487            }
488
489            fn prefix(mut self, key: &'a [u8]) -> Self {
490                self.inner.prefix = Some(key);
491                self
492            }
493
494            fn from_key(&self) -> Option<&'a [u8]> {
495                self.inner.from
496            }
497
498            fn to_key(&self) -> Option<&'a [u8]> {
499                self.inner.to
500            }
501
502            fn prefix_key(&self) -> Option<&'a [u8]> {
503                self.inner.prefix
504            }
505        }
506    };
507}
508
509impl_leveldb_iterator!(KeyIterator<'a>, RevKeyIterator<'a>);
510impl_leveldb_iterator!(RevKeyIterator<'a>, KeyIterator<'a>);
511impl_leveldb_iterator!(ValueIterator<'a>, RevValueIterator<'a>);
512impl_leveldb_iterator!(RevValueIterator<'a>, ValueIterator<'a>);
513
514macro_rules! impl_iterator {
515    ($T:ty, $Item:ty, $ItemMethod:ident, $Rev:expr) => {
516        impl<'a> iter::Iterator for $T {
517            type Item = $Item;
518
519            fn next(&mut self) -> Option<Self::Item> {
520                if self.advance($Rev) {
521                    Some(self.$ItemMethod())
522                } else {
523                    None
524                }
525            }
526        }
527    };
528}
529
530impl_iterator!(Iterator<'a>, (Vec<u8>, Vec<u8>), entry, false);
531impl_iterator!(RevIterator<'a>, (Vec<u8>, Vec<u8>), entry, true);
532impl_iterator!(KeyIterator<'a>, Vec<u8>, key, false);
533impl_iterator!(RevKeyIterator<'a>, Vec<u8>, key, true);
534impl_iterator!(ValueIterator<'a>, Vec<u8>, value, false);
535impl_iterator!(RevValueIterator<'a>, Vec<u8>, key, true);
leveldb/database/iterator.rs

leveldb/database/
iterator.rs
