redb_32bit/
table.rs

1use crate::sealed::Sealed;
2use crate::tree_store::{
3    AccessGuardMut, Btree, BtreeDrain, BtreeDrainFilter, BtreeMut, BtreeRangeIter, Checksum,
4    PageHint, PageNumber, RawBtree, TransactionalMemory, MAX_VALUE_LENGTH,
5};
6use crate::types::{MutInPlaceValue, RedbKey, RedbValue};
7use crate::{AccessGuard, StorageError, WriteTransaction};
8use crate::{Result, TableHandle};
9use std::borrow::Borrow;
10use std::fmt::{Debug, Formatter};
11use std::ops::RangeBounds;
12use std::sync::{Arc, Mutex};
13
14/// Informational storage stats about a table
15#[derive(Debug)]
16pub struct TableStats {
17    pub(crate) tree_height: u32,
18    pub(crate) leaf_pages: u64,
19    pub(crate) branch_pages: u64,
20    pub(crate) stored_leaf_bytes: u64,
21    pub(crate) metadata_bytes: u64,
22    pub(crate) fragmented_bytes: u64,
23}
24
25impl TableStats {
26    /// Maximum traversal distance to reach the deepest (key, value) pair in the table
27    pub fn tree_height(&self) -> u32 {
28        self.tree_height
29    }
30
31    /// Number of leaf pages that store user data
32    pub fn leaf_pages(&self) -> u64 {
33        self.leaf_pages
34    }
35
36    /// Number of branch pages in the btree that store user data
37    pub fn branch_pages(&self) -> u64 {
38        self.branch_pages
39    }
40
41    /// Number of bytes consumed by keys and values that have been inserted.
42    /// Does not include indexing overhead
43    pub fn stored_bytes(&self) -> u64 {
44        self.stored_leaf_bytes
45    }
46
47    /// Number of bytes consumed by keys in internal branch pages, plus other metadata
48    pub fn metadata_bytes(&self) -> u64 {
49        self.metadata_bytes
50    }
51
52    /// Number of bytes consumed by fragmentation, both in data pages and internal metadata tables
53    pub fn fragmented_bytes(&self) -> u64 {
54        self.fragmented_bytes
55    }
56}
57
58/// A table containing key-value mappings
59pub struct Table<'db, 'txn, K: RedbKey + 'static, V: RedbValue + 'static> {
60    name: String,
61    transaction: &'txn WriteTransaction<'db>,
62    tree: BtreeMut<'txn, K, V>,
63}
64
65impl<K: RedbKey + 'static, V: RedbValue + 'static> TableHandle for Table<'_, '_, K, V> {
66    fn name(&self) -> &str {
67        &self.name
68    }
69}
70
71impl<'db, 'txn, K: RedbKey + 'static, V: RedbValue + 'static> Table<'db, 'txn, K, V> {
72    pub(crate) fn new(
73        name: &str,
74        table_root: Option<(PageNumber, Checksum)>,
75        freed_pages: Arc<Mutex<Vec<PageNumber>>>,
76        mem: &'db TransactionalMemory,
77        transaction: &'txn WriteTransaction<'db>,
78    ) -> Table<'db, 'txn, K, V> {
79        Table {
80            name: name.to_string(),
81            transaction,
82            tree: BtreeMut::new(table_root, mem, freed_pages),
83        }
84    }
85
86    #[allow(dead_code)]
87    pub(crate) fn print_debug(&self, include_values: bool) -> Result {
88        self.tree.print_debug(include_values)
89    }
90
91    /// Removes and returns the first key-value pair in the table
92    pub fn pop_first(&mut self) -> Result<Option<(AccessGuard<K>, AccessGuard<V>)>> {
93        // TODO: optimize this
94        let first = self
95            .iter()?
96            .next()
97            .map(|x| x.map(|(key, _)| K::as_bytes(&key.value()).as_ref().to_vec()));
98        if let Some(owned_key) = first {
99            let owned_key = owned_key?;
100            let key = K::from_bytes(&owned_key);
101            let value = self.remove(&key)?.unwrap();
102            drop(key);
103            Ok(Some((AccessGuard::with_owned_value(owned_key), value)))
104        } else {
105            Ok(None)
106        }
107    }
108
109    /// Removes and returns the last key-value pair in the table
110    pub fn pop_last(&mut self) -> Result<Option<(AccessGuard<K>, AccessGuard<V>)>> {
111        // TODO: optimize this
112        let last = self
113            .iter()?
114            .next_back()
115            .map(|x| x.map(|(key, _)| K::as_bytes(&key.value()).as_ref().to_vec()));
116        if let Some(owned_key) = last {
117            let owned_key = owned_key?;
118            let key = K::from_bytes(&owned_key);
119            let value = self.remove(&key)?.unwrap();
120            drop(key);
121            Ok(Some((AccessGuard::with_owned_value(owned_key), value)))
122        } else {
123            Ok(None)
124        }
125    }
126
127    /// Removes the specified range and returns the removed entries in an iterator
128    ///
129    /// The iterator will consume all items in the range on drop.
130    pub fn drain<'a, KR>(&mut self, range: impl RangeBounds<KR> + 'a) -> Result<Drain<K, V>>
131    where
132        K: 'a,
133        KR: Borrow<K::SelfType<'a>> + 'a,
134    {
135        self.tree.drain(&range).map(Drain::new)
136    }
137
138    /// Applies `predicate` to all key-value pairs in the specified range. All entries for which
139    /// `predicate` evaluates to `true` are removed and returned in an iterator
140    ///
141    /// The iterator will consume all items in the range matching the predicate on drop.
142    pub fn drain_filter<'a, KR, F: for<'f> Fn(K::SelfType<'f>, V::SelfType<'f>) -> bool>(
143        &mut self,
144        range: impl RangeBounds<KR> + 'a,
145        predicate: F,
146    ) -> Result<DrainFilter<K, V, F>>
147    where
148        K: 'a,
149        KR: Borrow<K::SelfType<'a>> + 'a,
150    {
151        self.tree
152            .drain_filter(&range, predicate)
153            .map(DrainFilter::new)
154    }
155
156    /// Insert mapping of the given key to the given value
157    ///
158    /// Returns the old value, if the key was present in the table
159    pub fn insert<'k, 'v>(
160        &mut self,
161        key: impl Borrow<K::SelfType<'k>>,
162        value: impl Borrow<V::SelfType<'v>>,
163    ) -> Result<Option<AccessGuard<V>>> {
164        let value_len = V::as_bytes(value.borrow()).as_ref().len();
165        if value_len > MAX_VALUE_LENGTH {
166            return Err(StorageError::ValueTooLarge(value_len));
167        }
168        let key_len = K::as_bytes(key.borrow()).as_ref().len();
169        if key_len > MAX_VALUE_LENGTH {
170            return Err(StorageError::ValueTooLarge(key_len));
171        }
172        self.tree.insert(key.borrow(), value.borrow())
173    }
174
175    /// Removes the given key
176    ///
177    /// Returns the old value, if the key was present in the table
178    pub fn remove<'a>(
179        &mut self,
180        key: impl Borrow<K::SelfType<'a>>,
181    ) -> Result<Option<AccessGuard<V>>>
182    where
183        K: 'a,
184    {
185        self.tree.remove(key.borrow())
186    }
187}
188
189impl<'db, 'txn, K: RedbKey + 'static, V: MutInPlaceValue + 'static> Table<'db, 'txn, K, V> {
190    /// Reserve space to insert a key-value pair
191    /// The returned reference will have length equal to value_length
192    pub fn insert_reserve<'a>(
193        &mut self,
194        key: impl Borrow<K::SelfType<'a>>,
195        value_length: u32,
196    ) -> Result<AccessGuardMut<V>>
197    where
198        K: 'a,
199    {
200        if value_length as usize > MAX_VALUE_LENGTH {
201            return Err(StorageError::ValueTooLarge(value_length as usize));
202        }
203        let key_len = K::as_bytes(key.borrow()).as_ref().len();
204        if key_len > MAX_VALUE_LENGTH {
205            return Err(StorageError::ValueTooLarge(key_len));
206        }
207        self.tree.insert_reserve(key.borrow(), value_length)
208    }
209}
210
211impl<'db, 'txn, K: RedbKey + 'static, V: RedbValue + 'static> ReadableTable<K, V>
212    for Table<'db, 'txn, K, V>
213{
214    fn get<'a>(&self, key: impl Borrow<K::SelfType<'a>>) -> Result<Option<AccessGuard<V>>>
215    where
216        K: 'a,
217    {
218        self.tree.get(key.borrow())
219    }
220
221    fn range<'a, KR>(&self, range: impl RangeBounds<KR> + 'a) -> Result<Range<K, V>>
222    where
223        K: 'a,
224        KR: Borrow<K::SelfType<'a>> + 'a,
225    {
226        self.tree.range(&range).map(Range::new)
227    }
228
229    fn stats(&self) -> Result<TableStats> {
230        let tree_stats = self.tree.stats()?;
231
232        Ok(TableStats {
233            tree_height: tree_stats.tree_height,
234            leaf_pages: tree_stats.leaf_pages,
235            branch_pages: tree_stats.branch_pages,
236            stored_leaf_bytes: tree_stats.stored_leaf_bytes,
237            metadata_bytes: tree_stats.metadata_bytes,
238            fragmented_bytes: tree_stats.fragmented_bytes,
239        })
240    }
241
242    fn len(&self) -> Result<u64> {
243        self.tree.len()
244    }
245
246    fn is_empty(&self) -> Result<bool> {
247        self.len().map(|x| x == 0)
248    }
249}
250
251impl<K: RedbKey, V: RedbValue> Sealed for Table<'_, '_, K, V> {}
252
253impl<'db, 'txn, K: RedbKey + 'static, V: RedbValue + 'static> Drop for Table<'db, 'txn, K, V> {
254    fn drop(&mut self) {
255        self.transaction.close_table(&self.name, &self.tree);
256    }
257}
258
259fn debug_helper<K: RedbKey + 'static, V: RedbValue + 'static>(
260    f: &mut Formatter<'_>,
261    name: &str,
262    len: Result<u64>,
263    first: Result<Option<(AccessGuard<K>, AccessGuard<V>)>>,
264    last: Result<Option<(AccessGuard<K>, AccessGuard<V>)>>,
265) -> std::fmt::Result {
266    write!(f, "Table [ name: \"{}\", ", name)?;
267    if let Ok(len) = len {
268        if len == 0 {
269            write!(f, "No entries")?;
270        } else if len == 1 {
271            if let Ok(first) = first {
272                let (key, value) = first.as_ref().unwrap();
273                write!(f, "One key-value: {:?} = {:?}", key.value(), value.value())?;
274            } else {
275                write!(f, "I/O Error accessing table!")?;
276            }
277        } else {
278            if let Ok(first) = first {
279                let (key, value) = first.as_ref().unwrap();
280                write!(f, "first: {:?} = {:?}, ", key.value(), value.value())?;
281            } else {
282                write!(f, "I/O Error accessing table!")?;
283            }
284            if len > 2 {
285                write!(f, "...{} more entries..., ", len - 2)?;
286            }
287            if let Ok(last) = last {
288                let (key, value) = last.as_ref().unwrap();
289                write!(f, "last: {:?} = {:?}", key.value(), value.value())?;
290            } else {
291                write!(f, "I/O Error accessing table!")?;
292            }
293        }
294    } else {
295        write!(f, "I/O Error accessing table!")?;
296    }
297    write!(f, " ]")?;
298
299    Ok(())
300}
301
302impl<K: RedbKey + 'static, V: RedbValue + 'static> Debug for Table<'_, '_, K, V> {
303    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
304        debug_helper(f, &self.name, self.len(), self.first(), self.last())
305    }
306}
307
308pub trait ReadableTable<K: RedbKey + 'static, V: RedbValue + 'static>: Sealed {
309    /// Returns the value corresponding to the given key
310    fn get<'a>(&self, key: impl Borrow<K::SelfType<'a>>) -> Result<Option<AccessGuard<V>>>
311    where
312        K: 'a;
313
314    /// Returns a double-ended iterator over a range of elements in the table
315    ///
316    /// # Examples
317    ///
318    /// Usage:
319    /// ```rust
320    /// use redb::*;
321    /// # use tempfile::NamedTempFile;
322    /// const TABLE: TableDefinition<&str, u64> = TableDefinition::new("my_data");
323    ///
324    /// # fn main() -> Result<(), Error> {
325    /// # let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();
326    /// # let filename = tmpfile.path();
327    /// let db = Database::create(filename)?;
328    /// let write_txn = db.begin_write()?;
329    /// {
330    ///     let mut table = write_txn.open_table(TABLE)?;
331    ///     table.insert("a", &0)?;
332    ///     table.insert("b", &1)?;
333    ///     table.insert("c", &2)?;
334    /// }
335    /// write_txn.commit()?;
336    ///
337    /// let read_txn = db.begin_read()?;
338    /// let table = read_txn.open_table(TABLE)?;
339    /// let mut iter = table.range("a".."c")?;
340    /// let (key, value) = iter.next().unwrap()?;
341    /// assert_eq!("a", key.value());
342    /// assert_eq!(0, value.value());
343    /// # Ok(())
344    /// # }
345    /// ```
346    fn range<'a, KR>(&self, range: impl RangeBounds<KR> + 'a) -> Result<Range<K, V>>
347    where
348        K: 'a,
349        KR: Borrow<K::SelfType<'a>> + 'a;
350
351    /// Returns the first key-value pair in the table, if it exists
352    fn first(&self) -> Result<Option<(AccessGuard<K>, AccessGuard<V>)>> {
353        self.iter()?.next().transpose()
354    }
355
356    /// Returns the last key-value pair in the table, if it exists
357    fn last(&self) -> Result<Option<(AccessGuard<K>, AccessGuard<V>)>> {
358        self.iter()?.next_back().transpose()
359    }
360
361    /// Retrieves information about storage usage for the table
362    fn stats(&self) -> Result<TableStats>;
363
364    /// Returns the number of entries in the table
365    fn len(&self) -> Result<u64>;
366
367    /// Returns `true` if the table is empty
368    fn is_empty(&self) -> Result<bool>;
369
370    /// Returns a double-ended iterator over all elements in the table
371    fn iter(&self) -> Result<Range<K, V>> {
372        self.range::<K::SelfType<'_>>(..)
373    }
374}
375
376/// A read-only untyped table
377pub struct ReadOnlyUntypedTable<'txn> {
378    tree: RawBtree<'txn>,
379}
380
381impl<'txn> ReadOnlyUntypedTable<'txn> {
382    pub(crate) fn new(
383        root_page: Option<(PageNumber, Checksum)>,
384        fixed_key_size: Option<usize>,
385        fixed_value_size: Option<usize>,
386        mem: &'txn TransactionalMemory,
387    ) -> Self {
388        Self {
389            tree: RawBtree::new(root_page, fixed_key_size, fixed_value_size, mem),
390        }
391    }
392
393    /// Retrieves information about storage usage for the table
394    pub fn stats(&self) -> Result<TableStats> {
395        let tree_stats = self.tree.stats()?;
396
397        Ok(TableStats {
398            tree_height: tree_stats.tree_height,
399            leaf_pages: tree_stats.leaf_pages,
400            branch_pages: tree_stats.branch_pages,
401            stored_leaf_bytes: tree_stats.stored_leaf_bytes,
402            metadata_bytes: tree_stats.metadata_bytes,
403            fragmented_bytes: tree_stats.fragmented_bytes,
404        })
405    }
406}
407
408/// A read-only table
409pub struct ReadOnlyTable<'txn, K: RedbKey + 'static, V: RedbValue + 'static> {
410    name: String,
411    tree: Btree<'txn, K, V>,
412}
413
414impl<'txn, K: RedbKey + 'static, V: RedbValue + 'static> ReadOnlyTable<'txn, K, V> {
415    pub(crate) fn new(
416        name: String,
417        root_page: Option<(PageNumber, Checksum)>,
418        hint: PageHint,
419        mem: &'txn TransactionalMemory,
420    ) -> Result<ReadOnlyTable<'txn, K, V>> {
421        Ok(ReadOnlyTable {
422            name,
423            tree: Btree::new(root_page, hint, mem)?,
424        })
425    }
426}
427
428impl<'txn, K: RedbKey + 'static, V: RedbValue + 'static> ReadableTable<K, V>
429    for ReadOnlyTable<'txn, K, V>
430{
431    fn get<'a>(&self, key: impl Borrow<K::SelfType<'a>>) -> Result<Option<AccessGuard<V>>>
432    where
433        K: 'a,
434    {
435        self.tree.get(key.borrow())
436    }
437
438    fn range<'a, KR>(&self, range: impl RangeBounds<KR> + 'a) -> Result<Range<K, V>>
439    where
440        K: 'a,
441        KR: Borrow<K::SelfType<'a>> + 'a,
442    {
443        self.tree.range(&range).map(Range::new)
444    }
445
446    fn stats(&self) -> Result<TableStats> {
447        let tree_stats = self.tree.stats()?;
448
449        Ok(TableStats {
450            tree_height: tree_stats.tree_height,
451            leaf_pages: tree_stats.leaf_pages,
452            branch_pages: tree_stats.branch_pages,
453            stored_leaf_bytes: tree_stats.stored_leaf_bytes,
454            metadata_bytes: tree_stats.metadata_bytes,
455            fragmented_bytes: tree_stats.fragmented_bytes,
456        })
457    }
458
459    fn len(&self) -> Result<u64> {
460        self.tree.len()
461    }
462
463    fn is_empty(&self) -> Result<bool> {
464        self.len().map(|x| x == 0)
465    }
466}
467
468impl<K: RedbKey, V: RedbValue> Sealed for ReadOnlyTable<'_, K, V> {}
469
470impl<K: RedbKey + 'static, V: RedbValue + 'static> Debug for ReadOnlyTable<'_, K, V> {
471    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
472        debug_helper(f, &self.name, self.len(), self.first(), self.last())
473    }
474}
475
476pub struct Drain<'a, K: RedbKey + 'static, V: RedbValue + 'static> {
477    inner: BtreeDrain<'a, K, V>,
478}
479
480impl<'a, K: RedbKey + 'static, V: RedbValue + 'static> Drain<'a, K, V> {
481    fn new(inner: BtreeDrain<'a, K, V>) -> Self {
482        Self { inner }
483    }
484}
485
486impl<'a, K: RedbKey + 'static, V: RedbValue + 'static> Iterator for Drain<'a, K, V> {
487    type Item = Result<(AccessGuard<'a, K>, AccessGuard<'a, V>)>;
488
489    fn next(&mut self) -> Option<Self::Item> {
490        let entry = self.inner.next()?;
491        Some(entry.map(|entry| {
492            let (page, key_range, value_range) = entry.into_raw();
493            let key = AccessGuard::with_page(page.clone(), key_range);
494            let value = AccessGuard::with_page(page, value_range);
495            (key, value)
496        }))
497    }
498}
499
500impl<'a, K: RedbKey + 'static, V: RedbValue + 'static> DoubleEndedIterator for Drain<'a, K, V> {
501    fn next_back(&mut self) -> Option<Self::Item> {
502        let entry = self.inner.next_back()?;
503        Some(entry.map(|entry| {
504            let (page, key_range, value_range) = entry.into_raw();
505            let key = AccessGuard::with_page(page.clone(), key_range);
506            let value = AccessGuard::with_page(page, value_range);
507            (key, value)
508        }))
509    }
510}
511
512pub struct DrainFilter<
513    'a,
514    K: RedbKey + 'static,
515    V: RedbValue + 'static,
516    F: for<'f> FnMut(K::SelfType<'f>, V::SelfType<'f>) -> bool,
517> {
518    inner: BtreeDrainFilter<'a, K, V, F>,
519}
520
521impl<
522        'a,
523        K: RedbKey + 'static,
524        V: RedbValue + 'static,
525        F: for<'f> FnMut(K::SelfType<'f>, V::SelfType<'f>) -> bool,
526    > DrainFilter<'a, K, V, F>
527{
528    fn new(inner: BtreeDrainFilter<'a, K, V, F>) -> Self {
529        Self { inner }
530    }
531}
532
533impl<
534        'a,
535        K: RedbKey + 'static,
536        V: RedbValue + 'static,
537        F: for<'f> FnMut(K::SelfType<'f>, V::SelfType<'f>) -> bool,
538    > Iterator for DrainFilter<'a, K, V, F>
539{
540    type Item = Result<(AccessGuard<'a, K>, AccessGuard<'a, V>)>;
541
542    fn next(&mut self) -> Option<Self::Item> {
543        let entry = self.inner.next()?;
544        Some(entry.map(|entry| {
545            let (page, key_range, value_range) = entry.into_raw();
546            let key = AccessGuard::with_page(page.clone(), key_range);
547            let value = AccessGuard::with_page(page, value_range);
548            (key, value)
549        }))
550    }
551}
552
553impl<
554        'a,
555        K: RedbKey + 'static,
556        V: RedbValue + 'static,
557        F: for<'f> FnMut(K::SelfType<'f>, V::SelfType<'f>) -> bool,
558    > DoubleEndedIterator for DrainFilter<'a, K, V, F>
559{
560    fn next_back(&mut self) -> Option<Self::Item> {
561        let entry = self.inner.next_back()?;
562        Some(entry.map(|entry| {
563            let (page, key_range, value_range) = entry.into_raw();
564            let key = AccessGuard::with_page(page.clone(), key_range);
565            let value = AccessGuard::with_page(page, value_range);
566            (key, value)
567        }))
568    }
569}
570
571pub struct Range<'a, K: RedbKey + 'static, V: RedbValue + 'static> {
572    inner: BtreeRangeIter<'a, K, V>,
573}
574
575impl<'a, K: RedbKey + 'static, V: RedbValue + 'static> Range<'a, K, V> {
576    pub(super) fn new(inner: BtreeRangeIter<'a, K, V>) -> Self {
577        Self { inner }
578    }
579}
580
581impl<'a, K: RedbKey + 'static, V: RedbValue + 'static> Iterator for Range<'a, K, V> {
582    type Item = Result<(AccessGuard<'a, K>, AccessGuard<'a, V>)>;
583
584    fn next(&mut self) -> Option<Self::Item> {
585        self.inner.next().map(|x| {
586            x.map(|entry| {
587                let (page, key_range, value_range) = entry.into_raw();
588                let key = AccessGuard::with_page(page.clone(), key_range);
589                let value = AccessGuard::with_page(page, value_range);
590                (key, value)
591            })
592        })
593    }
594}
595
596impl<'a, K: RedbKey + 'static, V: RedbValue + 'static> DoubleEndedIterator for Range<'a, K, V> {
597    fn next_back(&mut self) -> Option<Self::Item> {
598        self.inner.next_back().map(|x| {
599            x.map(|entry| {
600                let (page, key_range, value_range) = entry.into_raw();
601                let key = AccessGuard::with_page(page.clone(), key_range);
602                let value = AccessGuard::with_page(page, value_range);
603                (key, value)
604            })
605        })
606    }
607}
redb_32bit/table.rs

redb_32bit/
table.rs
