multiversx_sc/storage/mappers/
bi_di_mapper.rs

1use core::marker::PhantomData;
2
3use crate::{
4    abi::TypeAbiFrom,
5    codec::{
6        EncodeErrorHandler, NestedDecode, NestedEncode, TopDecode, TopEncode, TopEncodeMulti,
7        TopEncodeMultiOutput, multi_encode_iter_or_handle_err, multi_types::MultiValue2,
8    },
9    types::ManagedAddress,
10};
11
12use super::{
13    StorageMapper, StorageMapperFromAddress, UnorderedSetMapper,
14    source::{CurrentStorage, StorageAddress},
15    unordered_set_mapper,
16};
17use crate::{
18    abi::{TypeAbi, TypeDescriptionContainer, TypeName},
19    api::StorageMapperApi,
20    storage::{StorageKey, storage_set},
21    storage_clear,
22    types::{ManagedType, MultiValueEncoded},
23};
24
25const VALUE_SUFFIX: &[u8] = b"_value";
26const ID_SUFFIX: &[u8] = b"_id";
27const VALUE_TO_ID_SUFFIX: &[u8] = b"_value_to_id";
28const ID_TO_VALUE_SUFFIX: &[u8] = b"_id_to_value";
29
30type Keys<'a, SA, T, A> = unordered_set_mapper::Iter<'a, SA, T, A>;
31
32/// A storage mapper implementing a bidirectional map with one-to-one correspondence between IDs and values.
33///
34/// # Storage Layout
35///
36/// The `BiDiMapper` uses two `UnorderedSetMapper` instances and maintains bidirectional lookups:
37///
38/// 1. **ID set** (via `UnorderedSetMapper`):
39///    - `base_key + "_id.len"` → count of IDs
40///    - `base_key + "_id.item" + index` → ID at index (1-based)
41///    - `base_key + "_id.index" + encoded_id` → index of ID
42///
43/// 2. **Value set** (via `UnorderedSetMapper`):
44///    - `base_key + "_value.len"` → count of values
45///    - `base_key + "_value.item" + index` → value at index (1-based)
46///    - `base_key + "_value.index" + encoded_value` → index of value
47///
48/// 3. **Bidirectional mappings**:
49///    - `base_key + "_value_to_id" + encoded_value` → corresponding ID
50///    - `base_key + "_id_to_value" + encoded_id` → corresponding value
51///
52/// # Main Operations
53///
54/// - **Insert**: `insert(id, value)` - Adds bidirectional mapping. O(1). Fails if ID or value already exists.
55/// - **Lookup ID**: `get_id(value)` - Retrieves ID for a value. O(1) with one storage read.
56/// - **Lookup Value**: `get_value(id)` - Retrieves value for an ID. O(1) with one storage read.
57/// - **Contains**: `contains_id(id)` / `contains_value(value)` - Checks existence. O(1).
58/// - **Remove by ID**: `remove_by_id(id)` - Removes by ID, clears both directions. O(1).
59/// - **Remove by Value**: `remove_by_value(value)` - Removes by value, clears both directions. O(1).
60/// - **Batch Remove**: `remove_all_by_ids(iter)` / `remove_all_by_values(iter)` - Removes multiple entries.
61/// - **Iteration**: `iter()` - Iterates over (ID, value) pairs; `get_all_ids()` / `get_all_values()` - specific direction.
62///
63/// # Uniqueness Guarantee
64///
65/// Both IDs and values must be unique:
66/// - Each ID maps to exactly one value
67/// - Each value maps to exactly one ID
68/// - Inserting a duplicate ID or value fails and returns `false`
69///
70/// # Trade-offs
71///
72/// - **Pros**: O(1) bidirectional lookup; enforces one-to-one correspondence; efficient for reverse lookups.
73/// - **Cons**: Double storage overhead (two sets + two mappings); removal changes element positions (swap_remove);
74///   cannot have duplicate IDs or values; more complex than unidirectional maps.
75///
76/// # Use Cases
77///
78/// - Token ID ↔ Token name mappings
79/// - User address ↔ Username associations
80/// - NFT ID ↔ Metadata hash relationships
81/// - Any scenario requiring efficient lookup in both directions
82/// - Implementing invertible mappings
83///
84/// # Example
85///
86/// ```rust
87/// # use multiversx_sc::storage::mappers::{StorageMapper, BiDiMapper};
88/// # fn example<SA: multiversx_sc::api::StorageMapperApi>() {
89/// # let mut mapper = BiDiMapper::<SA, u32, u64>::new(
90/// #     multiversx_sc::storage::StorageKey::new(&b"token_mapping"[..])
91/// # );
92/// // Insert bidirectional mappings
93/// assert!(mapper.insert(1, 100));
94/// assert!(mapper.insert(2, 200));
95/// assert!(mapper.insert(3, 300));
96///
97/// // Cannot insert duplicate ID or value
98/// assert!(!mapper.insert(1, 400));  // ID 1 already exists
99/// assert!(!mapper.insert(4, 100));  // Value 100 already exists
100///
101/// assert_eq!(mapper.len(), 3);
102///
103/// // Bidirectional lookup
104/// assert_eq!(mapper.get_value(&2), 200);
105/// assert_eq!(mapper.get_id(&200), 2);
106///
107/// // Check existence in both directions
108/// assert!(mapper.contains_id(&1));
109/// assert!(mapper.contains_value(&300));
110///
111/// // Remove by ID
112/// assert!(mapper.remove_by_id(&2));
113/// assert!(!mapper.contains_id(&2));
114/// assert!(!mapper.contains_value(&200));  // Both directions removed
115/// assert_eq!(mapper.len(), 2);
116///
117/// // Remove by value
118/// assert!(mapper.remove_by_value(&100));
119/// assert!(!mapper.contains_id(&1));
120/// assert!(!mapper.contains_value(&100));
121///
122/// // Iterate over all mappings
123/// for (id, value) in mapper.iter() {
124///     // Process each bidirectional pair
125/// }
126///
127/// // Iterate only IDs or values
128/// for id in mapper.get_all_ids() {
129///     // Process IDs
130/// }
131/// for value in mapper.get_all_values() {
132///     // Process values
133/// }
134///
135/// // Batch removal
136/// mapper.remove_all_by_ids(vec![3]);
137/// assert!(mapper.is_empty());
138/// # }
139/// ```
140pub struct BiDiMapper<SA, K, V, A = CurrentStorage>
141where
142    SA: StorageMapperApi,
143    A: StorageAddress<SA>,
144    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
145    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
146{
147    _phantom_api: PhantomData<SA>,
148    address: A,
149    id_set_mapper: UnorderedSetMapper<SA, K, A>,
150    value_set_mapper: UnorderedSetMapper<SA, V, A>,
151    base_key: StorageKey<SA>,
152}
153
154impl<SA, K, V> StorageMapper<SA> for BiDiMapper<SA, K, V, CurrentStorage>
155where
156    SA: StorageMapperApi,
157    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
158    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
159{
160    fn new(base_key: StorageKey<SA>) -> Self {
161        let mut id_key = base_key.clone();
162        id_key.append_bytes(ID_SUFFIX);
163
164        let mut value_key = base_key.clone();
165        value_key.append_bytes(VALUE_SUFFIX);
166        BiDiMapper {
167            _phantom_api: PhantomData,
168            address: CurrentStorage,
169            id_set_mapper: UnorderedSetMapper::<SA, K>::new(id_key),
170            value_set_mapper: UnorderedSetMapper::<SA, V>::new(value_key),
171            base_key,
172        }
173    }
174}
175
176impl<SA, K, V> StorageMapperFromAddress<SA> for BiDiMapper<SA, K, V, ManagedAddress<SA>>
177where
178    SA: StorageMapperApi,
179    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
180    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
181{
182    fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
183        let mut id_key = base_key.clone();
184        id_key.append_bytes(ID_SUFFIX);
185
186        let mut value_key = base_key.clone();
187        value_key.append_bytes(VALUE_SUFFIX);
188        BiDiMapper {
189            _phantom_api: PhantomData,
190            address: address.clone(),
191            id_set_mapper: UnorderedSetMapper::new_from_address(address.clone(), id_key),
192            value_set_mapper: UnorderedSetMapper::new_from_address(address, value_key),
193            base_key,
194        }
195    }
196}
197
198impl<SA, K, V, A> BiDiMapper<SA, K, V, A>
199where
200    SA: StorageMapperApi,
201    A: StorageAddress<SA>,
202    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
203    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
204{
205    fn get_id_key(&self, value: &V) -> StorageKey<SA> {
206        let mut key = self.base_key.clone();
207        key.append_bytes(VALUE_TO_ID_SUFFIX);
208        key.append_item(value);
209        key
210    }
211
212    fn get_value_key(&self, key: &K) -> StorageKey<SA> {
213        let mut value = self.base_key.clone();
214        value.append_bytes(ID_TO_VALUE_SUFFIX);
215        value.append_item(&key);
216        value
217    }
218
219    pub fn get_id(&self, value: &V) -> K {
220        self.address
221            .address_storage_get(self.get_id_key(value).as_ref())
222    }
223
224    pub fn get_value(&self, id: &K) -> V {
225        self.address
226            .address_storage_get(self.get_value_key(id).as_ref())
227    }
228
229    pub fn contains_id(&self, id: &K) -> bool {
230        self.id_set_mapper.contains(id)
231    }
232
233    pub fn contains_value(&self, value: &V) -> bool {
234        self.value_set_mapper.contains(value)
235    }
236
237    pub fn get_all_values(&self) -> unordered_set_mapper::Iter<'_, SA, V, A> {
238        self.value_set_mapper.iter()
239    }
240
241    pub fn get_all_ids(&self) -> unordered_set_mapper::Iter<'_, SA, K, A> {
242        self.id_set_mapper.iter()
243    }
244
245    pub fn iter(&self) -> Iter<'_, SA, K, V, A> {
246        Iter::new(self)
247    }
248
249    pub fn is_empty(&self) -> bool {
250        self.value_set_mapper.is_empty()
251    }
252
253    pub fn len(&self) -> usize {
254        self.value_set_mapper.len()
255    }
256}
257
258impl<SA, K, V> BiDiMapper<SA, K, V, CurrentStorage>
259where
260    SA: StorageMapperApi,
261    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
262    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
263{
264    fn set_id(&mut self, value: &V, id: &K) {
265        storage_set(self.get_id_key(value).as_ref(), id);
266    }
267
268    fn set_value(&mut self, id: &K, value: &V) {
269        storage_set(self.get_value_key(id).as_ref(), value);
270    }
271
272    fn clear_id_by_value(&self, value: &V) {
273        storage_clear(self.get_id_key(value).as_ref());
274    }
275    fn clear_value_by_id(&self, id: &K) {
276        storage_clear(self.get_value_key(id).as_ref());
277    }
278
279    pub fn insert(&mut self, id: K, value: V) -> bool {
280        if self.contains_id(&id) || self.contains_value(&value) {
281            return false;
282        }
283        self.set_id(&value, &id);
284        self.set_value(&id, &value);
285
286        self.id_set_mapper.insert(id);
287        self.value_set_mapper.insert(value);
288        true
289    }
290
291    pub fn remove_by_id(&mut self, id: &K) -> bool {
292        if self.id_set_mapper.swap_remove(id) {
293            let value = self.get_value(id);
294            self.clear_id_by_value(&value);
295            self.clear_value_by_id(id);
296            storage_clear(self.get_value_key(id).as_ref());
297            self.value_set_mapper.swap_remove(&value);
298            return true;
299        }
300        false
301    }
302    pub fn remove_by_value(&mut self, value: &V) -> bool {
303        if self.value_set_mapper.swap_remove(value) {
304            let id = self.get_id(value);
305            self.clear_id_by_value(value);
306            self.clear_value_by_id(&id);
307            self.id_set_mapper.swap_remove(&id);
308            return true;
309        }
310        false
311    }
312
313    pub fn remove_all_by_ids<I>(&mut self, iter: I)
314    where
315        I: IntoIterator<Item = K>,
316    {
317        for item in iter {
318            self.remove_by_id(&item);
319        }
320    }
321
322    pub fn remove_all_by_values<I>(&mut self, iter: I)
323    where
324        I: IntoIterator<Item = V>,
325    {
326        for item in iter {
327            self.remove_by_value(&item);
328        }
329    }
330}
331
332impl<'a, SA, K, V, A> IntoIterator for &'a BiDiMapper<SA, K, V, A>
333where
334    SA: StorageMapperApi,
335    A: StorageAddress<SA>,
336    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
337    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
338{
339    type Item = (K, V);
340
341    type IntoIter = Iter<'a, SA, K, V, A>;
342
343    fn into_iter(self) -> Self::IntoIter {
344        self.iter()
345    }
346}
347
348pub struct Iter<'a, SA, K, V, A>
349where
350    SA: StorageMapperApi,
351    A: StorageAddress<SA>,
352    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
353    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
354{
355    key_iter: Keys<'a, SA, K, A>,
356    hash_map: &'a BiDiMapper<SA, K, V, A>,
357}
358
359impl<'a, SA, K, V, A> Iter<'a, SA, K, V, A>
360where
361    SA: StorageMapperApi,
362    A: StorageAddress<SA>,
363    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
364    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
365{
366    fn new(hash_map: &'a BiDiMapper<SA, K, V, A>) -> Iter<'a, SA, K, V, A> {
367        Iter {
368            key_iter: hash_map.get_all_ids(),
369            hash_map,
370        }
371    }
372}
373
374impl<SA, K, V, A> Iterator for Iter<'_, SA, K, V, A>
375where
376    SA: StorageMapperApi,
377    A: StorageAddress<SA>,
378    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
379    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
380{
381    type Item = (K, V);
382
383    #[inline]
384    fn next(&mut self) -> Option<(K, V)> {
385        if let Some(key) = self.key_iter.next() {
386            let value = self.hash_map.get_value(&key);
387            return Some((key, value));
388        }
389        None
390    }
391}
392
393impl<SA, K, V> TopEncodeMulti for BiDiMapper<SA, K, V, CurrentStorage>
394where
395    SA: StorageMapperApi,
396    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
397    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
398{
399    fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
400    where
401        O: TopEncodeMultiOutput,
402        H: EncodeErrorHandler,
403    {
404        let iter = self.iter().map(MultiValue2::<K, V>::from);
405        multi_encode_iter_or_handle_err(iter, output, h)
406    }
407}
408
409impl<SA, K, V> TypeAbiFrom<BiDiMapper<SA, K, V, CurrentStorage>>
410    for MultiValueEncoded<SA, MultiValue2<K, V>>
411where
412    SA: StorageMapperApi,
413    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
414    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
415{
416}
417
418impl<SA, K, V> TypeAbiFrom<Self> for BiDiMapper<SA, K, V, CurrentStorage>
419where
420    SA: StorageMapperApi,
421    K: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
422    V: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static + Default + PartialEq,
423{
424}
425
426impl<SA, K, V> TypeAbi for BiDiMapper<SA, K, V, CurrentStorage>
427where
428    SA: StorageMapperApi,
429    K: TopEncode
430        + TopDecode
431        + NestedEncode
432        + NestedDecode
433        + 'static
434        + Default
435        + PartialEq
436        + TypeAbi,
437    V: TopEncode
438        + TopDecode
439        + NestedEncode
440        + NestedDecode
441        + 'static
442        + Default
443        + PartialEq
444        + TypeAbi,
445{
446    type Unmanaged = Self;
447
448    fn type_name() -> TypeName {
449        MultiValueEncoded::<SA, MultiValue2<K, V>>::type_name()
450    }
451
452    fn type_name_rust() -> TypeName {
453        MultiValueEncoded::<SA, MultiValue2<K, V>>::type_name_rust()
454    }
455
456    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
457        K::provide_type_descriptions(accumulator);
458        V::provide_type_descriptions(accumulator);
459    }
460    fn is_variadic() -> bool {
461        true
462    }
463}
multiversx_sc/storage/mappers/bi_di_mapper.rs

multiversx_sc/storage/mappers/
bi_di_mapper.rs
