multiversx_sc/storage/mappers/
map_mapper.rs

1use core::marker::PhantomData;
2
3use super::{
4    SetMapper, StorageClearable, StorageMapper, StorageMapperFromAddress,
5    set_mapper::{self},
6    source::{CurrentStorage, StorageAddress},
7};
8use crate::{
9    abi::{TypeAbi, TypeAbiFrom, TypeDescriptionContainer, TypeName},
10    api::StorageMapperApi,
11    codec::{
12        EncodeErrorHandler, NestedDecode, NestedEncode, TopDecode, TopEncode, TopEncodeMulti,
13        TopEncodeMultiOutput, multi_encode_iter_or_handle_err, multi_types::MultiValue2,
14    },
15    storage::{StorageKey, storage_clear, storage_set},
16    types::{ManagedAddress, ManagedType, MultiValueEncoded},
17};
18
19const MAPPED_VALUE_IDENTIFIER: &str = ".mapped";
20type Keys<'a, SA, A, T> = set_mapper::Iter<'a, SA, A, T>;
21
22/// A storage mapper implementing a key-value map with efficient lookup and iteration.
23///
24/// # Storage Layout
25///
26/// The `MapMapper` uses a `SetMapper` to track keys and stores values separately:
27///
28/// 1. **Key tracking** (via `SetMapper`):
29///    - `base_key + ".info"` → `QueueMapperInfo` (length, front, back, new node counter)
30///    - `base_key + ".node_links" + node_id` → `Node` structure (previous, next)
31///    - `base_key + ".value" + node_id` → key value
32///    - `base_key + ".node_id" + encoded_key` → node ID lookup
33///
34/// 2. **Value storage**:
35///    - `base_key + ".mapped" + encoded_key` → value associated with the key
36///
37/// # Main Operations
38///
39/// - **Insert**: `insert(key, value)` - Adds or updates a key-value pair. Returns old value if key existed. O(1).
40/// - **Remove**: `remove(key)` - Removes a key-value pair. Returns the value if it existed. O(1).
41/// - **Lookup**: `get(key)` - Retrieves the value for a key. O(1) with one storage read.
42/// - **Contains**: `contains_key(key)` - Checks if a key exists. O(1) with one storage read.
43/// - **Entry API**: `entry(key)` - Provides entry-based manipulation (or_insert, and_modify, etc.).
44/// - **Iteration**: `iter()` - Iterates over (key, value) pairs; `keys()` - keys only; `values()` - values only.
45///
46/// # Trade-offs
47///
48/// - **Pros**: Familiar HashMap-like API; efficient lookups; supports entry pattern for conditional updates.
49/// - **Cons**: Uses more storage than simple key-value pairs (overhead from SetMapper); iteration order is arbitrary.
50///
51/// # Example
52///
53/// ```rust
54/// # use multiversx_sc::storage::mappers::{StorageMapper, MapMapper};
55/// # fn example<SA: multiversx_sc::api::StorageMapperApi>() {
56/// # let mut mapper = MapMapper::<SA, u32, u64>::new(
57/// #     multiversx_sc::storage::StorageKey::new(&b"balances"[..])
58/// # );
59/// // Insert key-value pairs
60/// mapper.insert(1, 100);
61/// mapper.insert(2, 200);
62/// mapper.insert(3, 300);
63///
64/// assert_eq!(mapper.get(&2), Some(200));
65/// assert_eq!(mapper.len(), 3);
66///
67/// // Update using entry API
68/// mapper.entry(2).and_modify(|v| *v += 50);
69/// assert_eq!(mapper.get(&2), Some(250));
70///
71/// // Remove a key
72/// let removed = mapper.remove(&1);
73/// assert_eq!(removed, Some(100));
74/// assert_eq!(mapper.len(), 2);
75///
76/// // Iterate over key-value pairs
77/// for (key, value) in mapper.iter() {
78///     // Process pairs
79/// }
80/// # }
81/// ```
82pub struct MapMapper<SA, K, V, A = CurrentStorage>
83where
84    SA: StorageMapperApi,
85    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
86    A: StorageAddress<SA>,
87    V: TopEncode + TopDecode + 'static,
88{
89    _phantom_api: PhantomData<SA>,
90    address: A,
91    base_key: StorageKey<SA>,
92    keys_set: SetMapper<SA, K, A>,
93    _phantom_value: PhantomData<V>,
94}
95
96impl<SA, K, V> StorageMapper<SA> for MapMapper<SA, K, V, CurrentStorage>
97where
98    SA: StorageMapperApi,
99    K: TopEncode + TopDecode + NestedEncode + NestedDecode,
100    V: TopEncode + TopDecode,
101{
102    fn new(base_key: StorageKey<SA>) -> Self {
103        MapMapper {
104            _phantom_api: PhantomData,
105            address: CurrentStorage,
106            base_key: base_key.clone(),
107            keys_set: SetMapper::new(base_key),
108            _phantom_value: PhantomData,
109        }
110    }
111}
112
113impl<SA, K, V> StorageClearable for MapMapper<SA, K, V, CurrentStorage>
114where
115    SA: StorageMapperApi,
116    K: TopEncode + TopDecode + NestedEncode + NestedDecode,
117    V: TopEncode + TopDecode,
118{
119    fn clear(&mut self) {
120        for key in self.keys_set.iter() {
121            self.clear_mapped_value(&key);
122        }
123        self.keys_set.clear();
124    }
125}
126
127impl<SA, K, V> MapMapper<SA, K, V, CurrentStorage>
128where
129    SA: StorageMapperApi,
130    K: TopEncode + TopDecode + NestedEncode + NestedDecode,
131    V: TopEncode + TopDecode,
132{
133    fn set_mapped_value(&self, key: &K, value: &V) {
134        storage_set(
135            self.build_named_key(MAPPED_VALUE_IDENTIFIER, key).as_ref(),
136            &value,
137        );
138    }
139
140    fn clear_mapped_value(&self, key: &K) {
141        storage_clear(self.build_named_key(MAPPED_VALUE_IDENTIFIER, key).as_ref());
142    }
143
144    /// Sets the value of the entry, and returns the entry's old value.
145    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
146        let old_value = self.get(&k);
147        self.set_mapped_value(&k, &v);
148        self.keys_set.insert(k);
149        old_value
150    }
151
152    /// Takes the value out of the entry, and returns it.
153    pub fn remove(&mut self, k: &K) -> Option<V> {
154        if self.keys_set.remove(k) {
155            let value = self.get_mapped_value(k);
156            self.clear_mapped_value(k);
157            return Some(value);
158        }
159        None
160    }
161}
162
163impl<SA, K, V> StorageMapperFromAddress<SA> for MapMapper<SA, K, V, ManagedAddress<SA>>
164where
165    SA: StorageMapperApi,
166    K: TopEncode + TopDecode + NestedEncode + NestedDecode,
167    V: TopEncode + TopDecode,
168{
169    fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
170        MapMapper {
171            _phantom_api: PhantomData,
172            address: address.clone(),
173            base_key: base_key.clone(),
174            keys_set: SetMapper::new_from_address(address, base_key),
175            _phantom_value: PhantomData,
176        }
177    }
178}
179
180impl<'a, SA, A, K, V> IntoIterator for &'a MapMapper<SA, K, V, A>
181where
182    SA: StorageMapperApi,
183    A: StorageAddress<SA>,
184    K: TopEncode + TopDecode + NestedEncode + NestedDecode,
185    V: TopEncode + TopDecode,
186{
187    type Item = (K, V);
188
189    type IntoIter = Iter<'a, SA, A, K, V>;
190
191    fn into_iter(self) -> Self::IntoIter {
192        self.iter()
193    }
194}
195
196impl<SA, A, K, V> MapMapper<SA, K, V, A>
197where
198    SA: StorageMapperApi,
199    K: TopEncode + TopDecode + NestedEncode + NestedDecode,
200    A: StorageAddress<SA>,
201    V: TopEncode + TopDecode,
202{
203    /// Returns `true` if the map contains a value for the specified key.
204    pub fn contains_key(&self, k: &K) -> bool {
205        self.keys_set.contains(k)
206    }
207
208    fn build_named_key(&self, name: &str, key: &K) -> StorageKey<SA> {
209        let mut named_key = self.base_key.clone();
210        named_key.append_bytes(name.as_bytes());
211        named_key.append_item(key);
212        named_key
213    }
214
215    fn get_mapped_value(&self, key: &K) -> V {
216        self.address
217            .address_storage_get(self.build_named_key(MAPPED_VALUE_IDENTIFIER, key).as_ref())
218    }
219
220    /// Gets a reference to the value in the entry.
221    pub fn get(&self, k: &K) -> Option<V> {
222        if self.keys_set.contains(k) {
223            return Some(self.get_mapped_value(k));
224        }
225        None
226    }
227
228    pub fn keys(&self) -> Keys<'_, SA, A, K> {
229        self.keys_set.iter()
230    }
231
232    /// Returns `true` if the map contains no elements.
233    pub fn is_empty(&self) -> bool {
234        self.keys_set.is_empty()
235    }
236
237    /// Returns the number of elements in the map.
238    pub fn len(&self) -> usize {
239        self.keys_set.len()
240    }
241
242    /// Gets the given key's corresponding entry in the map for in-place manipulation.
243    pub fn entry(&mut self, key: K) -> Entry<'_, SA, A, K, V> {
244        if self.contains_key(&key) {
245            Entry::Occupied(OccupiedEntry {
246                key,
247                map: self,
248                _marker: PhantomData,
249            })
250        } else {
251            Entry::Vacant(VacantEntry {
252                key,
253                map: self,
254                _marker: PhantomData,
255            })
256        }
257    }
258
259    /// An iterator visiting all values in arbitrary order.
260    /// The iterator element type is `&'a V`.
261    pub fn values(&self) -> Values<'_, SA, A, K, V> {
262        Values::new(self)
263    }
264
265    /// An iterator visiting all key-value pairs in arbitrary order.
266    /// The iterator element type is `(&'a K, &'a V)`.
267    pub fn iter(&self) -> Iter<'_, SA, A, K, V> {
268        Iter::new(self)
269    }
270}
271
272pub struct Iter<'a, SA, A, K, V>
273where
274    SA: StorageMapperApi,
275    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
276    A: StorageAddress<SA>,
277    V: TopEncode + TopDecode + 'static,
278{
279    key_iter: Keys<'a, SA, A, K>,
280    hash_map: &'a MapMapper<SA, K, V, A>,
281}
282
283impl<'a, SA, A, K, V> Iter<'a, SA, A, K, V>
284where
285    SA: StorageMapperApi,
286    A: StorageAddress<SA>,
287    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
288    V: TopEncode + TopDecode + 'static,
289{
290    fn new(hash_map: &'a MapMapper<SA, K, V, A>) -> Iter<'a, SA, A, K, V> {
291        Iter {
292            key_iter: hash_map.keys(),
293            hash_map,
294        }
295    }
296}
297
298impl<SA, A, K, V> Iterator for Iter<'_, SA, A, K, V>
299where
300    SA: StorageMapperApi,
301    A: StorageAddress<SA>,
302    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
303    V: TopEncode + TopDecode + 'static,
304{
305    type Item = (K, V);
306
307    #[inline]
308    fn next(&mut self) -> Option<(K, V)> {
309        if let Some(key) = self.key_iter.next() {
310            let value = self.hash_map.get(&key).unwrap();
311            return Some((key, value));
312        }
313        None
314    }
315}
316
317pub struct Values<'a, SA, A, K, V>
318where
319    SA: StorageMapperApi,
320    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
321    A: StorageAddress<SA>,
322    V: TopEncode + TopDecode + 'static,
323{
324    key_iter: Keys<'a, SA, A, K>,
325    hash_map: &'a MapMapper<SA, K, V, A>,
326}
327
328impl<'a, SA, A, K, V> Values<'a, SA, A, K, V>
329where
330    SA: StorageMapperApi,
331    A: StorageAddress<SA>,
332    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
333    V: TopEncode + TopDecode + 'static,
334{
335    fn new(hash_map: &'a MapMapper<SA, K, V, A>) -> Values<'a, SA, A, K, V> {
336        Values {
337            key_iter: hash_map.keys(),
338            hash_map,
339        }
340    }
341}
342
343impl<SA, A, K, V> Iterator for Values<'_, SA, A, K, V>
344where
345    SA: StorageMapperApi,
346    A: StorageAddress<SA>,
347    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
348    V: TopEncode + TopDecode + 'static,
349{
350    type Item = V;
351
352    #[inline]
353    fn next(&mut self) -> Option<V> {
354        if let Some(key) = self.key_iter.next() {
355            let value = self.hash_map.get(&key).unwrap();
356            return Some(value);
357        }
358        None
359    }
360}
361
362pub enum Entry<'a, SA, A, K: 'a, V: 'a>
363where
364    SA: StorageMapperApi,
365    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
366    A: StorageAddress<SA>,
367    V: TopEncode + TopDecode + 'static,
368{
369    /// A vacant entry.
370    Vacant(VacantEntry<'a, SA, A, K, V>),
371
372    /// An occupied entry.
373    Occupied(OccupiedEntry<'a, SA, A, K, V>),
374}
375
376/// A view into a vacant entry in a `MapMapper`.
377/// It is part of the [`Entry`] enum.
378pub struct VacantEntry<'a, SA, A, K: 'a, V: 'a>
379where
380    SA: StorageMapperApi,
381    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
382    A: StorageAddress<SA>,
383    V: TopEncode + TopDecode + 'static,
384{
385    pub(super) key: K,
386    pub(super) map: &'a mut MapMapper<SA, K, V, A>,
387
388    // Be invariant in `K` and `V`
389    pub(super) _marker: PhantomData<&'a mut (K, V)>,
390}
391
392/// A view into an occupied entry in a `MapMapper`.
393/// It is part of the [`Entry`] enum.
394pub struct OccupiedEntry<'a, SA, A, K: 'a, V: 'a>
395where
396    SA: StorageMapperApi,
397    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
398    A: StorageAddress<SA>,
399    V: TopEncode + TopDecode + 'static,
400{
401    pub(super) key: K,
402    pub(super) map: &'a mut MapMapper<SA, K, V, A>,
403
404    // Be invariant in `K` and `V`
405    pub(super) _marker: PhantomData<&'a mut (K, V)>,
406}
407
408impl<SA, A, K, V> Entry<'_, SA, A, K, V>
409where
410    SA: StorageMapperApi,
411    A: StorageAddress<SA>,
412    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
413    V: TopEncode + TopDecode + 'static,
414{
415    /// Returns a reference to this entry's key.
416    pub fn key(&self) -> &K {
417        match *self {
418            Entry::Occupied(ref entry) => entry.key(),
419            Entry::Vacant(ref entry) => entry.key(),
420        }
421    }
422}
423
424impl<'a, SA, K, V> Entry<'a, SA, CurrentStorage, K, V>
425where
426    SA: StorageMapperApi,
427    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
428    V: TopEncode + TopDecode + 'static,
429{
430    /// Ensures a value is in the entry by inserting the default if empty, and returns
431    /// an `OccupiedEntry`.
432    pub fn or_insert(self, default: V) -> OccupiedEntry<'a, SA, CurrentStorage, K, V> {
433        match self {
434            Entry::Occupied(entry) => entry,
435            Entry::Vacant(entry) => entry.insert(default),
436        }
437    }
438
439    /// Ensures a value is in the entry by inserting the result of the default function if empty,
440    /// and returns an `OccupiedEntry`.
441    pub fn or_insert_with<F: FnOnce() -> V>(
442        self,
443        default: F,
444    ) -> OccupiedEntry<'a, SA, CurrentStorage, K, V> {
445        match self {
446            Entry::Occupied(entry) => entry,
447            Entry::Vacant(entry) => entry.insert(default()),
448        }
449    }
450
451    /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
452    /// This method allows for generating key-derived values for insertion by providing the default
453    /// function a reference to the key that was moved during the `.entry(key)` method call.
454    ///
455    /// The reference to the moved key is provided so that cloning or copying the key is
456    /// unnecessary, unlike with `.or_insert_with(|| ... )`.
457    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(
458        self,
459        default: F,
460    ) -> OccupiedEntry<'a, SA, CurrentStorage, K, V> {
461        match self {
462            Entry::Occupied(entry) => entry,
463            Entry::Vacant(entry) => {
464                let value = default(entry.key());
465                entry.insert(value)
466            }
467        }
468    }
469
470    /// Provides in-place mutable access to an occupied entry before any
471    /// potential inserts into the map.
472    pub fn and_modify<F>(self, f: F) -> Self
473    where
474        F: FnOnce(&mut V),
475    {
476        match self {
477            Entry::Occupied(mut entry) => {
478                entry.update(f);
479                Entry::Occupied(entry)
480            }
481            Entry::Vacant(entry) => Entry::Vacant(entry),
482        }
483    }
484}
485
486impl<'a, SA, K, V: Default> Entry<'a, SA, CurrentStorage, K, V>
487where
488    SA: StorageMapperApi,
489    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
490    V: TopEncode + TopDecode + 'static,
491{
492    /// Ensures a value is in the entry by inserting the default value if empty,
493    /// and returns an `OccupiedEntry`.
494    pub fn or_default(self) -> OccupiedEntry<'a, SA, CurrentStorage, K, V> {
495        match self {
496            Entry::Occupied(entry) => entry,
497            Entry::Vacant(entry) => entry.insert(Default::default()),
498        }
499    }
500}
501
502impl<SA, A, K, V> VacantEntry<'_, SA, A, K, V>
503where
504    SA: StorageMapperApi,
505    A: StorageAddress<SA>,
506    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
507    V: TopEncode + TopDecode + 'static,
508{
509    /// Gets a reference to the key that would be used when inserting a value
510    /// through the VacantEntry.
511    pub fn key(&self) -> &K {
512        &self.key
513    }
514}
515
516impl<'a, SA, K, V> VacantEntry<'a, SA, CurrentStorage, K, V>
517where
518    SA: StorageMapperApi,
519    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
520    V: TopEncode + TopDecode + 'static,
521{
522    /// Sets the value of the entry with the `VacantEntry`'s key,
523    /// and returns an `OccupiedEntry`.
524    pub fn insert(self, value: V) -> OccupiedEntry<'a, SA, CurrentStorage, K, V> {
525        self.map.insert(self.key.clone(), value);
526        OccupiedEntry {
527            key: self.key,
528            map: self.map,
529            _marker: PhantomData,
530        }
531    }
532}
533
534impl<SA, A, K, V> OccupiedEntry<'_, SA, A, K, V>
535where
536    SA: StorageMapperApi,
537    A: StorageAddress<SA>,
538    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
539    V: TopEncode + TopDecode + 'static,
540{
541    /// Gets a reference to the key in the entry.
542    pub fn key(&self) -> &K {
543        &self.key
544    }
545
546    /// Gets the value in the entry.
547    pub fn get(&self) -> V {
548        self.map.get(&self.key).unwrap()
549    }
550}
551
552impl<SA, K, V> OccupiedEntry<'_, SA, CurrentStorage, K, V>
553where
554    SA: StorageMapperApi,
555    K: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
556    V: TopEncode + TopDecode + 'static,
557{
558    /// Take ownership of the key and value from the map.
559    pub fn remove_entry(self) -> (K, V) {
560        let value = self.map.remove(&self.key).unwrap();
561        (self.key, value)
562    }
563
564    /// Syntactic sugar, to more compactly express a get, update and set in one line.
565    /// Takes whatever lies in storage, apples the given closure and saves the final value back to storage.
566    /// Propagates the return value of the given function.
567    pub fn update<R, F: FnOnce(&mut V) -> R>(&mut self, f: F) -> R {
568        let mut value = self.get();
569        let result = f(&mut value);
570        self.map.insert(self.key.clone(), value);
571        result
572    }
573
574    /// Sets the value of the entry with the `OccupiedEntry`'s key,
575    /// and returns the entry's old value.
576    pub fn insert(self, value: V) -> V {
577        self.map.insert(self.key, value).unwrap()
578    }
579
580    /// Takes the value of the entry out of the map, and returns it.
581    pub fn remove(self) -> V {
582        self.map.remove(&self.key).unwrap()
583    }
584}
585
586/// Behaves like a MultiResultVec<MultiValue2<K, V>> when an endpoint result.
587impl<SA, K, V> TopEncodeMulti for MapMapper<SA, K, V, CurrentStorage>
588where
589    SA: StorageMapperApi,
590    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
591    V: TopEncode + TopDecode + 'static,
592{
593    fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
594    where
595        O: TopEncodeMultiOutput,
596        H: EncodeErrorHandler,
597    {
598        let iter = self.iter().map(MultiValue2::<K, V>::from);
599        multi_encode_iter_or_handle_err(iter, output, h)
600    }
601}
602
603impl<SA, K, V> TypeAbiFrom<MapMapper<SA, K, V, CurrentStorage>>
604    for MultiValueEncoded<SA, MultiValue2<K, V>>
605where
606    SA: StorageMapperApi,
607    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
608    V: TopEncode + TopDecode + 'static,
609{
610}
611
612impl<SA, K, V> TypeAbiFrom<Self> for MapMapper<SA, K, V, CurrentStorage>
613where
614    SA: StorageMapperApi,
615    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
616    V: TopEncode + TopDecode + 'static,
617{
618}
619
620/// Behaves like a MultiResultVec<MultiValue<K, V>> when an endpoint result.
621impl<SA, K, V> TypeAbi for MapMapper<SA, K, V, CurrentStorage>
622where
623    SA: StorageMapperApi,
624    K: TopEncode + TopDecode + NestedEncode + NestedDecode + TypeAbi + 'static,
625    V: TopEncode + TopDecode + TypeAbi + 'static,
626{
627    type Unmanaged = Self;
628
629    fn type_name() -> TypeName {
630        MultiValueEncoded::<SA, MultiValue2<K, V>>::type_name()
631    }
632
633    fn type_name_rust() -> TypeName {
634        MultiValueEncoded::<SA, MultiValue2<K, V>>::type_name_rust()
635    }
636
637    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
638        K::provide_type_descriptions(accumulator);
639        V::provide_type_descriptions(accumulator);
640    }
641
642    fn is_variadic() -> bool {
643        true
644    }
645}
multiversx_sc/storage/mappers/map_mapper.rs

multiversx_sc/storage/mappers/
map_mapper.rs
