1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
//! Governed map collection implementation.
use super::error::{CollectionError as Error, Result, ensure};
use super::tree::Tree;
use super::{MapIter, Memory, Storable};
use crate::DefaultMemoryImpl;
use crate::RuntimeMemory;
use std::ops::RangeBounds;
/// Governed ordered map backed by Storage’s owned B-tree and reusable blocks.
pub struct StableBTreeMap<K: Storable + Ord + Clone, V: Storable, M: Memory = DefaultMemoryImpl> {
inner: Tree<K, V, RuntimeMemory<M>>,
}
impl<K: Storable + Ord + Clone, V: Storable, M: Memory> StableBTreeMap<K, V, M> {
/// Create a collection only in zero-page memory.
///
/// # Errors
/// Refuses nonempty memory, invalid encoding or capacity exhaustion before writes.
pub fn create(memory: RuntimeMemory<M>) -> Result<Self> {
ensure(memory.size() == 0, Error::NotEmpty)?;
Self::reset(memory)
}
/// Deliberately replace any contents in this admitted allocation.
///
/// # Errors
/// Returns encoding, capacity or structural admission errors.
pub fn reset(memory: RuntimeMemory<M>) -> Result<Self> {
Ok(Self {
inner: Tree::reset(memory)?,
})
}
/// Load retained collection state without initializing a replacement.
///
/// # Errors
/// Refuses empty, foreign or corrupt memory and incompatible bounds without writing.
pub fn load(memory: RuntimeMemory<M>) -> Result<Self> {
Ok(Self {
inner: Tree::load(memory)?,
})
}
/// Clear entries while retaining this allocation's exclusive lease.
///
/// # Errors
/// Reports a poisoned owner or metadata encoding/capacity refusal.
pub fn clear(&mut self) -> Result<()> {
self.inner.clear()
}
/// Set the heap budget for cached, validated routing nodes; zero disables it.
///
/// Caching is disabled initially. Changing the budget discards cached nodes.
/// The budget accounts for buffer capacities and cache bookkeeping, excluding
/// allocator overhead and nodes retained by an active iterator. External
/// values are never cached. Writes invalidate affected nodes; reloads start
/// cold. The exclusive backing-custody contract applies while caching.
pub fn set_node_cache_budget(&mut self, bytes: usize) {
self.inner.set_cache_budget(bytes);
}
/// Reserve a minimum virtual extent without exposing or duplicating the lease.
///
/// Returns the map on both success and ordinary growth refusal. Entries are
/// preserved; the cached tree remains unchanged.
/// Backing traps follow the host transaction contract.
///
/// `minimum` is an absolute virtual extent in 65,536-byte Wasm pages, not an
/// entry count or additional pages. Existing extents never shrink. A request
/// already covered performs no growth or writes. This reserves backing only:
/// it does not promise that any particular number or encoding of entries fits.
/// Callers own their byte/page budget and must qualify it for their codecs;
/// internal node-layout constants are not a supported capacity contract.
pub fn reserve_pages(
self,
minimum: u64,
) -> (Self, std::result::Result<(), crate::RuntimeGrowError>) {
let additional = minimum.saturating_sub(self.inner.memory.size());
let result = self.inner.memory.grow(additional).map(|_| ());
(self, result)
}
/// Observe the virtual extent in 65,536-byte pages while retaining the lease.
///
/// Consumes and returns the map while retaining the exclusive lease.
/// Observing the allocation performs no writes or growth.
/// This is allocated extent, not free space or guaranteed entry capacity.
#[must_use]
pub fn allocated_pages(self) -> (Self, u64) {
let pages = self.inner.memory.size();
(self, pages)
}
/// Perform `insert` on the governed ordered map.
///
/// # Errors
/// Rejects encoding, decoding, structural or capacity errors before committing writes.
pub fn insert(&mut self, key: K, value: V) -> Result<Option<V>> {
self.inner.insert(key, value)
}
/// Perform `get` on the governed ordered map.
///
/// # Errors
/// Reports structural, integrity or application decoding failures without writing.
pub fn get(&self, key: &K) -> Result<Option<V>> {
self.inner.get(key)
}
/// Perform `contains_key` on the governed ordered map.
///
/// # Errors
/// Reports structural, integrity or application decoding failures without writing.
pub fn contains_key(&self, key: &K) -> Result<bool> {
self.inner.contains_key(key)
}
/// Perform `is_empty` on the governed ordered map.
///
/// # Errors
/// Reports invalid region metadata or incompatible codec bounds.
pub fn is_empty(&self) -> bool {
self.inner.len() == 0
}
/// Perform `len` on the governed ordered map.
pub fn len(&self) -> u64 {
self.inner.len()
}
/// Perform `remove` on the governed ordered map.
///
/// # Errors
/// Rejects decoding or structural errors before committing removal.
pub fn remove(&mut self, key: &K) -> Result<Option<V>> {
self.inner.remove(key)
}
/// Perform `first_key_value` on the governed ordered map.
///
/// # Errors
/// Reports invalid structure, integrity failures or application codec errors.
pub fn first_key_value(&self) -> Result<Option<(K, V)>> {
self.iter()
.next()
.map(|entry| entry?.into_pair())
.transpose()
}
/// Perform `last_key_value` on the governed ordered map.
///
/// # Errors
/// Reports invalid structure, integrity failures or application codec errors.
pub fn last_key_value(&self) -> Result<Option<(K, V)>> {
self.iter()
.next_back()
.map(|entry| entry?.into_pair())
.transpose()
}
/// Perform `iter` on the governed ordered map.
pub fn iter(&self) -> MapIter<'_, K, V, M> {
self.inner.range(..)
}
/// Perform `range` on the governed ordered map.
pub fn range(&self, key_range: impl RangeBounds<K>) -> MapIter<'_, K, V, M> {
self.inner.range(key_range)
}
/// Perform `keys` on the governed ordered map.
pub fn keys(&self) -> impl DoubleEndedIterator<Item = Result<K>> + '_ {
self.inner.keys_range(..)
}
/// Traverse bounded keys without reading external value records.
///
/// Routing records and key codecs remain checked. External value integrity
/// is checked only by operations that request values.
pub fn keys_range(
&self,
bounds: impl RangeBounds<K>,
) -> impl DoubleEndedIterator<Item = Result<K>> + '_ {
self.inner.keys_range(bounds)
}
/// Perform `values` on the governed ordered map.
pub fn values(&self) -> impl DoubleEndedIterator<Item = Result<V>> + '_ {
self.iter().map(|entry| entry?.into_value())
}
}
impl<'a, K: Storable + Ord + Clone, V: Storable, M: Memory> IntoIterator
for &'a StableBTreeMap<K, V, M>
{
type Item = <MapIter<'a, K, V, M> as Iterator>::Item;
type IntoIter = MapIter<'a, K, V, M>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}