rocksdb/
iter_range.rs

Help
1/// A range which can be set as iterate bounds on [`crate::ReadOptions`].
2///
3/// See [`crate::ReadOptions::set_iterate_range`] for documentation and
4/// examples.
5pub trait IterateBounds {
6    /// Converts object into lower and upper bounds pair.
7    ///
8    /// If this object represents range with one of the bounds unset,
9    /// corresponding element is returned as `None`.  For example, `..upper`
10    /// range would be converted into `(None, Some(upper))` pair.
11    fn into_bounds(self) -> (Option<Vec<u8>>, Option<Vec<u8>>);
12}
13
14impl IterateBounds for std::ops::RangeFull {
15    fn into_bounds(self) -> (Option<Vec<u8>>, Option<Vec<u8>>) {
16        (None, None)
17    }
18}
19
20impl<K: Into<Vec<u8>>> IterateBounds for std::ops::Range<K> {
21    fn into_bounds(self) -> (Option<Vec<u8>>, Option<Vec<u8>>) {
22        (Some(self.start.into()), Some(self.end.into()))
23    }
24}
25
26impl<K: Into<Vec<u8>>> IterateBounds for std::ops::RangeFrom<K> {
27    fn into_bounds(self) -> (Option<Vec<u8>>, Option<Vec<u8>>) {
28        (Some(self.start.into()), None)
29    }
30}
31
32impl<K: Into<Vec<u8>>> IterateBounds for std::ops::RangeTo<K> {
33    fn into_bounds(self) -> (Option<Vec<u8>>, Option<Vec<u8>>) {
34        (None, Some(self.end.into()))
35    }
36}
37
38/// Representation of a range of keys starting with given prefix.
39///
40/// Can be used as argument of [`crate::ReadOptions::set_iterate_range`] method
41/// to set iterate bounds.
42#[derive(Clone, Copy)]
43pub struct PrefixRange<K>(pub K);
44
45impl<K: Into<Vec<u8>>> IterateBounds for PrefixRange<K> {
46    /// Converts the prefix range representation into pair of bounds.
47    ///
48    /// The conversion assumes lexicographical sorting on `u8` values.  For
49    /// example, `PrefixRange("a")` is equivalent to `"a".."b"` range.  Note
50    /// that for some prefixes, either of the bounds may be `None`.  For
51    /// example, an empty prefix is equivalent to a full range (i.e. both bounds
52    /// being `None`).
53    fn into_bounds(self) -> (Option<Vec<u8>>, Option<Vec<u8>>) {
54        let start = self.0.into();
55        if start.is_empty() {
56            (None, None)
57        } else {
58            let end = next_prefix(&start);
59            (Some(start), end)
60        }
61    }
62}
63
64/// Returns lowest value following largest value with given prefix.
65///
66/// In other words, computes upper bound for a prefix scan over list of keys
67/// sorted in lexicographical order.  This means that a prefix scan can be
68/// expressed as range scan over a right-open `[prefix, next_prefix(prefix))`
69/// range.
70///
71/// For example, for prefix `foo` the function returns `fop`.
72///
73/// Returns `None` if there is no value which can follow value with given
74/// prefix.  This happens when prefix consists entirely of `'\xff'` bytes (or is
75/// empty).
76fn next_prefix(prefix: &[u8]) -> Option<Vec<u8>> {
77    let ffs = prefix
78        .iter()
79        .rev()
80        .take_while(|&&byte| byte == u8::MAX)
81        .count();
82    let next = &prefix[..(prefix.len() - ffs)];
83    if next.is_empty() {
84        // Prefix consisted of \xff bytes.  There is no prefix that
85        // follows it.
86        None
87    } else {
88        let mut next = next.to_vec();
89        *next.last_mut().unwrap() += 1;
90        Some(next)
91    }
92}
93
94#[test]
95fn test_prefix_range() {
96    fn test(start: &[u8], end: Option<&[u8]>) {
97        let got = PrefixRange(start).into_bounds();
98        assert_eq!((Some(start), end), (got.0.as_deref(), got.1.as_deref()));
99    }
100
101    let empty: &[u8] = &[];
102    assert_eq!((None, None), PrefixRange(empty).into_bounds());
103    test(b"\xff", None);
104    test(b"\xff\xff\xff\xff", None);
105    test(b"a", Some(b"b"));
106    test(b"a\xff\xff\xff", Some(b"b"));
107}
rocksdb/iter_range.rs

rocksdb/
iter_range.rs
