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

leveldb/database/
iterator.rs
