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