multiversx_sc/storage/mappers/
unordered_set_mapper.rs

1use core::marker::PhantomData;
2
3pub use super::vec_mapper::Iter;
4use super::{
5    StorageClearable, StorageMapper, StorageMapperFromAddress, VecMapper,
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,
14    },
15    storage::StorageKey,
16    storage_clear, storage_set,
17    types::{ManagedAddress, ManagedType, MultiValueEncoded},
18};
19
20const ITEM_INDEX: &[u8] = b".index";
21const NULL_ENTRY: usize = 0;
22
23/// A storage mapper for managing an unordered set of items with efficient membership testing.
24///
25/// # Storage Layout
26///
27/// The `UnorderedSetMapper` uses two storage patterns:
28///
29/// 1. **Value storage** (via `VecMapper`):
30///    - `base_key + ".len"` → count of items
31///    - `base_key + ".item" + index` → value at index (1-based indexing)
32///
33/// 2. **Index lookup** (for fast membership testing):
34///    - `base_key + ".index" + encoded_value` → index of value (0 means not present)
35///
36/// # Main Operations
37///
38/// - **Insert**: `insert(value)` - Adds a value if not already present. O(1) with storage writes.
39/// - **Remove**: `swap_remove(value)` - Removes a value by swapping with the last element. O(1) with storage writes.
40/// - **Contains**: `contains(value)` - Checks membership by looking up the index. O(1) with one storage read.
41/// - **Iteration**: `iter()` - Iterates over all values in arbitrary order.
42/// - **Random Access**: `get_by_index(index)` - Gets value at a specific position (1-based).
43///
44/// # Trade-offs
45///
46/// - **Pros**: O(1) insert, remove, and contains operations; efficient for membership testing.
47/// - **Cons**: No ordering guarantees; removal changes element positions; uses more storage than `SetMapper`.
48///
49/// # Example
50///
51/// ```rust
52/// # use multiversx_sc::storage::mappers::{StorageMapper, UnorderedSetMapper};
53/// # use multiversx_sc::api::ManagedTypeApi;
54/// # fn example<SA: multiversx_sc::api::StorageMapperApi>() {
55/// # let mut mapper = UnorderedSetMapper::<SA, u32>::new(
56/// #     multiversx_sc::storage::StorageKey::new(&b"my_set"[..])
57/// # );
58/// mapper.insert(10);
59/// mapper.insert(20);
60/// mapper.insert(30);
61///
62/// assert!(mapper.contains(&20));
63/// assert_eq!(mapper.len(), 3);
64///
65/// mapper.swap_remove(&20);
66/// assert!(!mapper.contains(&20));
67/// assert_eq!(mapper.len(), 2);
68/// # }
69/// ```
70pub struct UnorderedSetMapper<SA, T, A = CurrentStorage>
71where
72    SA: StorageMapperApi,
73    A: StorageAddress<SA>,
74    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
75{
76    _phantom_api: PhantomData<SA>,
77    address: A,
78    base_key: StorageKey<SA>,
79    vec_mapper: VecMapper<SA, T, A>,
80}
81
82impl<SA, T> StorageMapper<SA> for UnorderedSetMapper<SA, T, CurrentStorage>
83where
84    SA: StorageMapperApi,
85    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
86{
87    fn new(base_key: StorageKey<SA>) -> Self {
88        UnorderedSetMapper {
89            _phantom_api: PhantomData,
90            address: CurrentStorage,
91            base_key: base_key.clone(),
92            vec_mapper: VecMapper::<SA, T>::new(base_key),
93        }
94    }
95}
96
97impl<SA, T> StorageMapperFromAddress<SA> for UnorderedSetMapper<SA, T, ManagedAddress<SA>>
98where
99    SA: StorageMapperApi,
100    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
101{
102    fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
103        UnorderedSetMapper {
104            _phantom_api: PhantomData,
105            address: address.clone(),
106            base_key: base_key.clone(),
107            vec_mapper: VecMapper::new_from_address(address, base_key),
108        }
109    }
110}
111
112impl<SA, T> StorageClearable for UnorderedSetMapper<SA, T, CurrentStorage>
113where
114    SA: StorageMapperApi,
115    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
116{
117    fn clear(&mut self) {
118        for value in self.vec_mapper.iter() {
119            self.clear_index(&value);
120        }
121        self.vec_mapper.clear();
122    }
123}
124
125impl<SA, T, A> UnorderedSetMapper<SA, T, A>
126where
127    SA: StorageMapperApi,
128    A: StorageAddress<SA>,
129    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
130{
131    fn item_index_key(&self, value: &T) -> StorageKey<SA> {
132        let mut item_key = self.base_key.clone();
133        item_key.append_bytes(ITEM_INDEX);
134        item_key.append_item(value);
135        item_key
136    }
137
138    /// Gets the item's index at the given address' mapper.
139    /// Returns `0` if the item is not in the list.
140    pub fn get_index(&self, value: &T) -> usize {
141        self.address
142            .address_storage_get(self.item_index_key(value).as_ref())
143    }
144
145    /// Get item at index from the given address.
146    /// Index must be valid (1 <= index <= count).
147    pub fn get_by_index(&self, index: usize) -> T {
148        self.vec_mapper.get(index)
149    }
150
151    /// Returns `true` if the set contains no elements.
152    pub fn is_empty(&self) -> bool {
153        self.vec_mapper.is_empty()
154    }
155
156    /// Returns the number of elements in the set.
157    pub fn len(&self) -> usize {
158        self.vec_mapper.len()
159    }
160
161    /// Returns `true` if the set contains a value.
162    pub fn contains(&self, value: &T) -> bool {
163        self.get_index(value) != NULL_ENTRY
164    }
165
166    /// An iterator visiting all elements in arbitrary order.
167    /// The iterator element type is `&'a T`.
168    pub fn iter(&self) -> Iter<'_, SA, T, A> {
169        self.vec_mapper.iter()
170    }
171}
172
173impl<SA, T> UnorderedSetMapper<SA, T, CurrentStorage>
174where
175    SA: StorageMapperApi,
176    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
177{
178    fn set_index(&self, value: &T, index: usize) {
179        storage_set(self.item_index_key(value).as_ref(), &index);
180    }
181
182    fn clear_index(&self, value: &T) {
183        storage_clear(self.item_index_key(value).as_ref());
184    }
185
186    /// Adds a value to the set.
187    ///
188    /// If the set did not have this value present, `true` is returned.
189    ///
190    /// If the set did have this value present, `false` is returned.
191    pub fn insert(&mut self, value: T) -> bool {
192        if self.contains(&value) {
193            return false;
194        }
195        self.vec_mapper.push(&value);
196        self.set_index(&value, self.len());
197        true
198    }
199
200    /// Removes a value from the set. Returns whether the value was
201    /// present in the set.
202    pub fn swap_remove(&mut self, value: &T) -> bool {
203        let index = self.get_index(value);
204        if index == NULL_ENTRY {
205            return false;
206        }
207        if let Some(last_item) = self.vec_mapper.swap_remove_and_get_old_last(index) {
208            self.set_index(&last_item, index);
209        }
210        self.clear_index(value);
211        true
212    }
213
214    /// Exchanges the indexes of two values. Returns whether the operation was
215    /// successful.
216    pub fn swap_indexes(&mut self, index1: usize, index2: usize) -> bool {
217        if index1 == NULL_ENTRY || index2 == NULL_ENTRY {
218            return false;
219        }
220        let value1 = self.get_by_index(index1);
221        let value2 = self.get_by_index(index2);
222        self.vec_mapper.set(index2, &value1);
223        self.vec_mapper.set(index1, &value2);
224        self.set_index(&value1, index2);
225        self.set_index(&value2, index1);
226        true
227    }
228}
229
230impl<'a, SA, T, A> IntoIterator for &'a UnorderedSetMapper<SA, T, A>
231where
232    SA: StorageMapperApi,
233    A: StorageAddress<SA>,
234    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
235{
236    type Item = T;
237
238    type IntoIter = Iter<'a, SA, T, A>;
239
240    fn into_iter(self) -> Self::IntoIter {
241        self.iter()
242    }
243}
244
245impl<SA, T> Extend<T> for UnorderedSetMapper<SA, T>
246where
247    SA: StorageMapperApi,
248    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
249{
250    fn extend<I>(&mut self, iter: I)
251    where
252        I: IntoIterator<Item = T>,
253    {
254        for item in iter {
255            self.insert(item);
256        }
257    }
258}
259
260/// Behaves like a MultiResultVec when an endpoint result.
261impl<SA, T> TopEncodeMulti for UnorderedSetMapper<SA, T>
262where
263    SA: StorageMapperApi,
264    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
265{
266    fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
267    where
268        O: TopEncodeMultiOutput,
269        H: EncodeErrorHandler,
270    {
271        multi_encode_iter_or_handle_err(self.iter(), output, h)
272    }
273}
274
275impl<SA, T> TypeAbiFrom<UnorderedSetMapper<SA, T>> for MultiValueEncoded<SA, T>
276where
277    SA: StorageMapperApi,
278    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
279{
280}
281
282impl<SA, T> TypeAbiFrom<Self> for UnorderedSetMapper<SA, T>
283where
284    SA: StorageMapperApi,
285    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
286{
287}
288
289/// Behaves like a MultiResultVec when an endpoint result.
290impl<SA, T> TypeAbi for UnorderedSetMapper<SA, T>
291where
292    SA: StorageMapperApi,
293    T: TopEncode + TopDecode + NestedEncode + NestedDecode + TypeAbi,
294{
295    type Unmanaged = Self;
296
297    fn type_name() -> TypeName {
298        crate::abi::type_name_variadic::<T>()
299    }
300
301    fn type_name_rust() -> TypeName {
302        crate::abi::type_name_multi_value_encoded::<T>()
303    }
304
305    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
306        T::provide_type_descriptions(accumulator);
307    }
308
309    fn is_variadic() -> bool {
310        true
311    }
312}
multiversx_sc/storage/mappers/unordered_set_mapper.rs

multiversx_sc/storage/mappers/
unordered_set_mapper.rs
