ic_storage/adapter/map.rs
1//! Governed map collection implementation.
2use super::{MapIter, Memory, Storable};
3use crate::substrate::{self, DefaultMemoryImpl};
4use ic_memory::RuntimeMemory;
5use std::ops::RangeBounds;
6
7/// Governed upstream `BTreeMap`; initialization and failures follow upstream contracts.
8pub struct StableBTreeMap<K: Storable + Ord + Clone, V: Storable, M: Memory = DefaultMemoryImpl> {
9 inner: substrate::BTreeMap<K, V, RuntimeMemory<M>>,
10}
11impl<K: Storable + Ord + Clone, V: Storable, M: Memory> StableBTreeMap<K, V, M> {
12 /// Create a new collection, replacing any prior collection in the selected memory.
13 /// This is destructive even when a valid collection already exists.
14 ///
15 /// # Panics
16 /// Panics on insufficient memory or codec/backing failure.
17 pub fn new(memory: RuntimeMemory<M>) -> Self {
18 Self {
19 inner: substrate::BTreeMap::new(memory),
20 }
21 }
22 /// Open a recognized retained collection; initialize a new one when memory
23 /// is empty or has foreign magic. Foreign contents may be overwritten.
24 /// This is not a corruption-recovery or schema-admission operation.
25 ///
26 /// # Panics
27 /// Panics for unsupported recognized layouts, invalid retained contents,
28 /// insufficient memory or codec/backing failure.
29 pub fn init(memory: RuntimeMemory<M>) -> Self {
30 Self {
31 inner: substrate::BTreeMap::init(memory),
32 }
33 }
34 /// Load an existing tree without initializing a replacement.
35 ///
36 /// # Panics
37 /// Panics for missing/foreign headers, unsupported layouts or backing failure.
38 /// Record decoding can also panic when records are subsequently accessed.
39 pub fn load(memory: RuntimeMemory<M>) -> Self {
40 Self {
41 inner: substrate::BTreeMap::load(memory),
42 }
43 }
44 /// Clear entries while retaining this allocation's exclusive lease.
45 pub fn clear(&mut self) {
46 self.inner.clear_new();
47 }
48 /// Reserve a minimum virtual extent without exposing or duplicating the lease.
49 ///
50 /// Returns the map on both success and ordinary growth refusal. Entries are
51 /// preserved; reloading the upstream header refreshes its cached allocator.
52 /// Backing traps retain the upstream panic contract.
53 ///
54 /// `minimum` is an absolute virtual extent in 65,536-byte Wasm pages, not an
55 /// entry count or additional pages. Existing extents never shrink. A request
56 /// already covered performs no growth or writes. This reserves backing only:
57 /// it does not promise that any particular number or encoding of entries fits.
58 /// Callers own their byte/page budget and must qualify it for their codecs;
59 /// upstream node-layout constants are not a supported capacity contract.
60 pub fn reserve_pages(self, minimum: u64) -> (Self, Result<(), ic_memory::RuntimeGrowError>) {
61 let memory = self.inner.into_memory();
62 let additional = minimum.saturating_sub(memory.size());
63 let result = memory.grow(additional).map(|_| ());
64 (Self::load(memory), result)
65 }
66 /// Observe the virtual extent in 65,536-byte pages while retaining the lease.
67 ///
68 /// Consumes and returns the map because upstream exposes memory only through
69 /// ownership transfer. Reloading reads the header without writing or growing.
70 /// This is allocated extent, not free space or guaranteed entry capacity.
71 #[must_use]
72 pub fn allocated_pages(self) -> (Self, u64) {
73 let memory = self.inner.into_memory();
74 let pages = memory.size();
75 (Self::load(memory), pages)
76 }
77 /// Delegates to upstream `BTreeMap::insert` with the governed allocation.
78 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
79 self.inner.insert(key, value)
80 }
81 /// Delegates to upstream `BTreeMap::get` with the governed allocation.
82 pub fn get(&self, key: &K) -> Option<V> {
83 self.inner.get(key)
84 }
85 /// Delegates to upstream `BTreeMap::contains_key` with the governed allocation.
86 pub fn contains_key(&self, key: &K) -> bool {
87 self.inner.contains_key(key)
88 }
89 /// Delegates to upstream `BTreeMap::is_empty` with the governed allocation.
90 pub fn is_empty(&self) -> bool {
91 self.inner.is_empty()
92 }
93 /// Delegates to upstream `BTreeMap::len` with the governed allocation.
94 pub fn len(&self) -> u64 {
95 self.inner.len()
96 }
97 /// Delegates to upstream `BTreeMap::remove` with the governed allocation.
98 pub fn remove(&mut self, key: &K) -> Option<V> {
99 self.inner.remove(key)
100 }
101 /// Delegates to upstream `BTreeMap::first_key_value` with the governed allocation.
102 pub fn first_key_value(&self) -> Option<(K, V)> {
103 self.inner.first_key_value()
104 }
105 /// Delegates to upstream `BTreeMap::last_key_value` with the governed allocation.
106 pub fn last_key_value(&self) -> Option<(K, V)> {
107 self.inner.last_key_value()
108 }
109 /// Delegates to upstream `BTreeMap::pop_first` with the governed allocation.
110 pub fn pop_first(&mut self) -> Option<(K, V)> {
111 self.inner.pop_first()
112 }
113 /// Delegates to upstream `BTreeMap::pop_last` with the governed allocation.
114 pub fn pop_last(&mut self) -> Option<(K, V)> {
115 self.inner.pop_last()
116 }
117 /// Delegates to upstream `BTreeMap::iter` with the governed allocation.
118 pub fn iter(&self) -> MapIter<'_, K, V, M> {
119 self.inner.iter()
120 }
121 /// Delegates to upstream `BTreeMap::range` with the governed allocation.
122 pub fn range(&self, key_range: impl RangeBounds<K>) -> MapIter<'_, K, V, M> {
123 self.inner.range(key_range)
124 }
125 /// Delegates to upstream `BTreeMap::keys` with the governed allocation.
126 pub fn keys(&self) -> impl DoubleEndedIterator<Item = K> + '_ {
127 self.inner.keys()
128 }
129 /// Delegates to upstream `BTreeMap::values` with the governed allocation.
130 pub fn values(&self) -> impl DoubleEndedIterator<Item = V> + '_ {
131 self.inner.values()
132 }
133}
134
135impl<'a, K: Storable + Ord + Clone, V: Storable, M: Memory> IntoIterator
136 for &'a StableBTreeMap<K, V, M>
137{
138 type Item = <MapIter<'a, K, V, M> as Iterator>::Item;
139 type IntoIter = MapIter<'a, K, V, M>;
140 fn into_iter(self) -> Self::IntoIter {
141 self.iter()
142 }
143}