fj_core/storage/
store.rs

1//! Append-only object storage
2//!
3//! So, why a custom data structure? Well, for two reasons:
4//!
5//! 1. No limitations on performance.
6//! 2. Best possible convenience.
7//!
8//! Please note that I'm deliberately saying "no limitations" on performance. So
9//! far, performance has not been a priority, so this might not be that fast.
10//! But by having a custom data structure, we should be able to make performance
11//! as good as we need it, within the limits of the practical.
12//!
13//! The second point, best possible convenience, is already realized.
14//! [`Handle`]s can be owned, cloned, and dereference to the object they are
15//! referencing. This is made possible by the append-only nature of our object
16//! storage, and our immutable objects.
17//!
18//! There are other append-only data structures on `crates.io`. Some of them
19//! look interesting, but none of them quite fit our needs and possibilities, so
20//! a custom development seemed justified.
21//!
22//! But in any case, this was fun to write, and not that much work.
23
24use std::{marker::PhantomData, sync::Arc};
25
26use parking_lot::RwLock;
27
28use super::{
29    blocks::{Blocks, Index},
30    Handle,
31};
32
33/// Append-only object storage
34#[derive(Debug)]
35pub struct Store<T> {
36    inner: StoreInner<T>,
37}
38
39impl<T> Store<T> {
40    /// Construct a new instance of `Store`
41    ///
42    /// Equivalent to calling [`Store::with_block_size`] with a default block
43    /// size.
44    pub fn new() -> Self {
45        Self::with_block_size(16384)
46    }
47
48    /// Construct a new instance of `Store` using the provided block size
49    pub fn with_block_size(block_size: usize) -> Self {
50        let inner = Arc::new(RwLock::new(StoreInnerInner {
51            blocks: Blocks::new(block_size),
52        }));
53
54        Self { inner }
55    }
56
57    /// Reserve a slot for an object in the store
58    ///
59    /// This method returns a [`Handle`] that references the reserved slot. That
60    /// `Handle` does not refer to an object yet! Attempting to dereference the
61    /// `Handle` before it has been used to insert an object into the store will
62    /// result in a panic.
63    ///
64    /// Usually, you'd acquire a `Handle`, then immediately use it to insert an
65    /// object using [`Store::insert`]. The methods are separate to support more
66    /// advanced use cases, like inserting objects that reference each other.
67    pub fn reserve(&self) -> Handle<T> {
68        let mut inner = self.inner.write();
69
70        let (index, ptr) = inner.blocks.reserve();
71
72        Handle {
73            store: self.inner.clone(),
74            index,
75            ptr,
76        }
77    }
78
79    /// Insert an object into the store
80    ///
81    /// # Panics
82    ///
83    /// Panics, if the passed `Handle` does not refer to a reserved slot. This
84    /// can only be the case, if the handle has been used to insert an object
85    /// before.
86    pub fn insert(&mut self, handle: Handle<T>, object: T) {
87        let mut inner = self.inner.write();
88        inner.blocks.insert(handle.index, object);
89    }
90
91    /// Iterate over all objects in this store
92    pub fn iter(&self) -> Iter<T> {
93        Iter {
94            store: self.inner.clone(),
95            next_index: Index::zero(),
96            _a: PhantomData,
97        }
98    }
99}
100
101impl<T> Default for Store<T> {
102    fn default() -> Self {
103        Self::new()
104    }
105}
106
107impl<'a, T> IntoIterator for &'a Store<T> {
108    type Item = Handle<T>;
109    type IntoIter = Iter<'a, T>;
110
111    fn into_iter(self) -> Self::IntoIter {
112        self.iter()
113    }
114}
115
116/// An iterator over objects in a [`Store`]
117pub struct Iter<'a, T> {
118    store: StoreInner<T>,
119    next_index: Index,
120    _a: PhantomData<&'a ()>,
121}
122
123impl<'a, T: 'a> Iterator for Iter<'a, T> {
124    type Item = Handle<T>;
125
126    fn next(&mut self) -> Option<Self::Item> {
127        let inner = self.store.read();
128
129        loop {
130            let index = self.next_index;
131            let ptr = inner.blocks.get_and_inc(&mut self.next_index)?;
132
133            if ptr.is_none() {
134                // This is a reserved slot.
135                continue;
136            }
137
138            return Some(Handle {
139                store: self.store.clone(),
140                index,
141                ptr,
142            });
143        }
144    }
145}
146
147pub type StoreInner<T> = Arc<RwLock<StoreInnerInner<T>>>;
148
149#[derive(Debug)]
150pub struct StoreInnerInner<T> {
151    blocks: Blocks<T>,
152}
153
154#[cfg(test)]
155mod tests {
156    use crate::storage::Handle;
157
158    use super::Store;
159
160    #[test]
161    fn insert_and_handle() {
162        let mut store = Store::with_block_size(1);
163
164        let handle: Handle<i32> = store.reserve();
165        let object = 0;
166
167        store.insert(handle.clone(), object);
168
169        assert_eq!(*handle, object);
170    }
171
172    #[test]
173    fn insert_and_iter() {
174        let mut store = Store::with_block_size(1);
175
176        let a: Handle<i32> = store.reserve();
177        let b = store.reserve();
178        store.insert(a.clone(), 0);
179        store.insert(b.clone(), 1);
180
181        let objects = store.iter().collect::<Vec<_>>();
182        assert_eq!(objects, [a, b]);
183    }
184}
fj_core/storage/store.rs

fj_core/storage/
store.rs
