sefer_region/
region.rs

1//! [`Region`] — a handle-addressed store of `T` backed by `slotmap`.
2
3use crate::Handle;
4
5/// A handle-addressed store of `T`.
6///
7/// A thin typed membrane over `slotmap::SlotMap<slotmap::DefaultKey, T>`:
8/// values live in `slotmap`'s dense, cache-friendly, always-compact backing
9/// store, and every operation delegates to `slotmap` while exposing only typed
10/// [`Handle<T>`] values (raw `DefaultKey`s never escape). All operations are
11/// `O(1)`.
12///
13/// ## Invariants upheld
14///
15/// - **I1 — resolution:** a fresh handle resolves via [`get`](Self::get) to the
16///   inserted value until it is [`remove`](Self::remove)d.
17/// - **I2 — tombstone:** after `remove(h)`, `get(h)` is `None` forever and a
18///   second `remove(h)` is a no-op `None`.
19/// - **I3 — no ABA:** a stale handle — one whose slot has since been reused —
20///   never resolves to a live value. `slotmap`'s `DefaultKey` carries a
21///   generation that is bumped on removal, so the old handle fails the version
22///   check and yields `None`.
23/// - **I4 — accounting:** [`len`](Self::len) equals the number of live entries
24///   and [`is_empty`](Self::is_empty) agrees.
25/// - **I5 — drop-once:** every live value is dropped exactly once — on
26///   `remove` (returned to the caller) or on `Region` drop — never twice,
27///   never leaked. `slotmap` owns the storage and therefore the drops.
28///
29/// ## Generation saturation
30///
31/// Version saturation (a slot whose generation would have to wrap) is
32/// `slotmap`'s responsibility: `DefaultKey` retires such a slot rather than
33/// wrapping a generation into alias, so a handle can never alias a future value
34/// — the classic generational-arena ABA caveat stays closed at the
35/// astronomically rare cost of one slot per `2^32` reuses. There is no
36/// hand-rolled retirement code in this crate.
37pub struct Region<T> {
38    inner: slotmap::SlotMap<slotmap::DefaultKey, T>,
39}
40
41impl<T> Region<T> {
42    /// Creates an empty region that allocates nothing until first use.
43    #[must_use]
44    pub fn new() -> Self {
45        Self {
46            inner: slotmap::SlotMap::new(),
47        }
48    }
49
50    /// Creates an empty region with space pre-reserved for `capacity` entries.
51    #[must_use]
52    pub fn with_capacity(capacity: usize) -> Self {
53        Self {
54            inner: slotmap::SlotMap::with_capacity(capacity),
55        }
56    }
57
58    /// Number of live values (I4).
59    #[must_use]
60    pub fn len(&self) -> usize {
61        self.inner.len()
62    }
63
64    /// Whether the region holds no live values (I4).
65    #[must_use]
66    pub fn is_empty(&self) -> bool {
67        self.inner.is_empty()
68    }
69
70    /// Current value-storage capacity, in entries.
71    #[must_use]
72    pub fn capacity(&self) -> usize {
73        self.inner.capacity()
74    }
75
76    /// Reserves capacity for at least `additional` more insertions.
77    ///
78    /// Does nothing if the backing store already has room. After a churn that
79    /// removes entries, the freed slots live on the free list, so re-inserting
80    /// reuses existing capacity and does not grow unboundedly (the backing
81    /// stays bounded by the high-water mark of live entries). Delegates to
82    /// `slotmap`'s `reserve`; may allocate more than asked to avoid frequent
83    /// reallocations. Panics if the new allocation size overflows `usize`.
84    pub fn reserve(&mut self, additional: usize) {
85        self.inner.reserve(additional);
86    }
87
88    /// Inserts `value`, returning a fresh handle that resolves to it (I1).
89    pub fn insert(&mut self, value: T) -> Handle<T> {
90        Handle::from_key(self.inner.insert(value))
91    }
92
93    /// Borrows the value for `handle`, or `None` if the handle is stale or
94    /// removed (I1, I2, I3).
95    #[must_use]
96    pub fn get(&self, handle: Handle<T>) -> Option<&T> {
97        self.inner.get(handle.key)
98    }
99
100    /// Mutably borrows the value for `handle`, or `None` if stale/removed.
101    #[must_use]
102    pub fn get_mut(&mut self, handle: Handle<T>) -> Option<&mut T> {
103        self.inner.get_mut(handle.key)
104    }
105
106    /// Whether `handle` currently resolves to a live value.
107    #[must_use]
108    pub fn contains(&self, handle: Handle<T>) -> bool {
109        self.inner.contains_key(handle.key)
110    }
111
112    /// Removes and returns the value for `handle`, or `None` if it is already
113    /// stale/removed. After this, `handle` resolves to `None` forever (I2).
114    pub fn remove(&mut self, handle: Handle<T>) -> Option<T> {
115        self.inner.remove(handle.key)
116    }
117
118    /// Iterates the live values in dense (cache-friendly) order. The order is
119    /// unspecified and changes as elements are removed.
120    pub fn iter(&self) -> impl Iterator<Item = &T> {
121        self.inner.values()
122    }
123
124    /// Mutably iterates the live values in dense order.
125    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
126        self.inner.values_mut()
127    }
128
129    /// Removes every value, invalidating all outstanding handles, while
130    /// retaining allocated capacity. The region is reusable afterwards.
131    pub fn clear(&mut self) {
132        self.inner.clear();
133    }
134}
135
136impl<T> Default for Region<T> {
137    fn default() -> Self {
138        Self::new()
139    }
140}
sefer_region/region.rs

sefer_region/
region.rs
