feoxdb/core/store/
range.rs

1use crossbeam_epoch as epoch;
2use std::ops::Bound;
3
4use crate::constants::MAX_KEY_SIZE;
5use crate::error::{FeoxError, Result};
6
7use super::FeoxStore;
8
9const RANGE_PREALLOC_LIMIT: usize = 1024;
10const RANGE_REPIN_INTERVAL: usize = 256;
11
12impl FeoxStore {
13    /// Perform a range query on the store.
14    ///
15    /// Returns all key-value pairs where the key is >= `start_key` and <= `end_key`.
16    /// Both bounds are inclusive.
17    ///
18    /// # Arguments
19    ///
20    /// * `start_key` - Inclusive lower bound
21    /// * `end_key` - Inclusive upper bound
22    /// * `limit` - Maximum number of results to return
23    ///
24    /// # Returns
25    ///
26    /// Returns a vector of (key, value) pairs in sorted order.
27    ///
28    /// # Example
29    ///
30    /// ```rust
31    /// # use feoxdb::FeoxStore;
32    /// # fn main() -> feoxdb::Result<()> {
33    /// # let store = FeoxStore::new(None)?;
34    /// store.insert(b"user:001", b"Alice")?;
35    /// store.insert(b"user:002", b"Bob")?;
36    /// store.insert(b"user:003", b"Charlie")?;
37    /// store.insert(b"user:004", b"David")?;
38    ///
39    /// // Get users 001 through 003 (inclusive)
40    /// let results = store.range_query(b"user:001", b"user:003", 10)?;
41    /// assert_eq!(results.len(), 3);
42    /// # Ok(())
43    /// # }
44    /// ```
45    pub fn range_query(
46        &self,
47        start_key: &[u8],
48        end_key: &[u8],
49        limit: usize,
50    ) -> Result<Vec<(Vec<u8>, Vec<u8>)>> {
51        if start_key.len() > MAX_KEY_SIZE || end_key.len() > MAX_KEY_SIZE {
52            return Err(FeoxError::InvalidKeySize);
53        }
54
55        if limit == 0 {
56            return Ok(Vec::new());
57        }
58        let mut results = Vec::with_capacity(limit.min(self.tree.len()).min(RANGE_PREALLOC_LIMIT));
59
60        let mut guard = epoch::pin();
61        let mut entries_since_repin = 0;
62        let mut cursor = self.tree.lower_bound(Bound::Included(start_key));
63
64        while let Some(entry) = cursor {
65            if results.len() >= limit || entry.key().as_slice() > end_key {
66                break;
67            }
68
69            let value = {
70                let record = entry.value().load(&guard);
71                self.resolve_value_ref(entry.key(), record)
72            };
73            entries_since_repin += 1;
74            if entries_since_repin == RANGE_REPIN_INTERVAL {
75                guard.repin();
76                entries_since_repin = 0;
77            }
78            let value = match value {
79                Ok(value) => value.to_vec(),
80                Err(FeoxError::StaleExtent) | Err(FeoxError::KeyNotFound) => {
81                    cursor = entry.next();
82                    continue;
83                }
84                Err(error) => return Err(error),
85            };
86
87            results.push((entry.key().clone(), value));
88            cursor = entry.next();
89        }
90
91        Ok(results)
92    }
93}
feoxdb/core/store/range.rs

feoxdb/core/store/
range.rs
