multiversx_sc/storage/mappers/
set_mapper.rs

1use core::marker::PhantomData;
2
3pub use super::queue_mapper::Iter;
4use super::{QueueMapper, StorageClearable, StorageMapper, StorageMapperFromAddress};
5use crate::{
6    abi::{TypeAbi, TypeAbiFrom, TypeDescriptionContainer, TypeName},
7    api::StorageMapperApi,
8    codec::{
9        self, EncodeErrorHandler, NestedDecode, NestedEncode, TopDecode, TopEncode, TopEncodeMulti,
10        TopEncodeMultiOutput, multi_encode_iter_or_handle_err,
11    },
12    storage::{
13        StorageKey,
14        mappers::source::{CurrentStorage, StorageAddress},
15        storage_set,
16    },
17    types::{ManagedAddress, ManagedType, MultiValueEncoded},
18};
19
20const NULL_ENTRY: u32 = 0;
21const NODE_ID_IDENTIFIER: &[u8] = b".node_id";
22
23/// A storage mapper implementing an ordered set with efficient membership testing and iteration.
24///
25/// # Storage Layout
26///
27/// The `SetMapper` uses a `QueueMapper` for ordering and separate storage for value-to-node mapping:
28///
29/// 1. **Ordered elements** (via `QueueMapper`):
30///    - `base_key + ".info"` → `QueueMapperInfo` (length, front, back, new node counter)
31///    - `base_key + ".node_links" + node_id` → `Node` structure (previous, next)
32///    - `base_key + ".value" + node_id` → the stored value
33///
34/// 2. **Value lookup** (for fast membership testing):
35///    - `base_key + ".node_id" + encoded_value` → node ID (0 means not present)
36///
37/// This dual structure enables both O(1) membership testing and ordered iteration.
38///
39/// # Main Operations
40///
41/// - **Insert**: `insert(value)` - Adds a value if not already present. O(1) with storage writes.
42/// - **Remove**: `remove(value)` - Removes a value from the set. O(1) with storage writes.
43/// - **Contains**: `contains(value)` - Checks membership. O(1) with one storage read.
44/// - **Iteration**: `iter()` - Iterates in insertion order; `iter_from(value)` - starts from specific value.
45/// - **Navigation**: `next(value)` / `previous(value)` - Gets adjacent elements in insertion order.
46/// - **Batch**: `remove_all(iter)` - Removes multiple values efficiently.
47///
48/// # Insertion Order
49///
50/// Unlike typical sets, `SetMapper` maintains **insertion order** - elements are stored in the order
51/// they were added. This makes it a hybrid between a set and a sequence.
52///
53/// # Trade-offs
54///
55/// - **Pros**: O(1) insert, remove, and contains; maintains insertion order; efficient iteration.
56/// - **Cons**: Higher storage overhead than `UnorderedSetMapper` (uses QueueMapper internally);
57///   no random access; removed elements leave gaps in node ID space.
58///
59/// # Comparison with UnorderedSetMapper
60///
61/// - **SetMapper**: Maintains insertion order, uses queue-based structure, slightly higher storage cost
62/// - **UnorderedSetMapper**: No ordering guarantees, uses vec-based structure, more compact storage
63///
64/// # Use Cases
65///
66/// - Whitelists/blacklists where insertion order matters
67/// - Unique collections requiring ordered iteration
68/// - Sets where you need to navigate between elements
69/// - Scenarios requiring both fast lookup and sequential processing
70///
71/// # Example
72///
73/// ```rust
74/// # use multiversx_sc::storage::mappers::{StorageMapper, SetMapper};
75/// # fn example<SA: multiversx_sc::api::StorageMapperApi>() {
76/// # let mut mapper = SetMapper::<SA, u32>::new(
77/// #     multiversx_sc::storage::StorageKey::new(&b"whitelist"[..])
78/// # );
79/// // Insert values
80/// assert!(mapper.insert(100));
81/// assert!(mapper.insert(200));
82/// assert!(mapper.insert(300));
83/// assert!(!mapper.insert(200));  // Already exists, returns false
84///
85/// assert_eq!(mapper.len(), 3);
86/// assert!(mapper.contains(&200));
87///
88/// // Navigate between elements
89/// let next = mapper.next(&200);
90/// assert_eq!(next, Some(300));
91///
92/// let prev = mapper.previous(&200);
93/// assert_eq!(prev, Some(100));
94///
95/// // Remove element
96/// assert!(mapper.remove(&200));
97/// assert!(!mapper.contains(&200));
98/// assert_eq!(mapper.len(), 2);
99///
100/// // Iterate in insertion order
101/// for value in mapper.iter() {
102///     // Process in order: 100, 300
103/// }
104///
105/// // Batch removal
106/// mapper.remove_all(vec![100, 300]);
107/// assert!(mapper.is_empty());
108/// # }
109/// ```
110pub struct SetMapper<SA, T, A = CurrentStorage>
111where
112    SA: StorageMapperApi,
113    A: StorageAddress<SA>,
114    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
115{
116    _phantom_api: PhantomData<SA>,
117    address: A,
118    base_key: StorageKey<SA>,
119    queue_mapper: QueueMapper<SA, T, A>,
120}
121
122impl<SA, T> StorageMapper<SA> for SetMapper<SA, T, CurrentStorage>
123where
124    SA: StorageMapperApi,
125    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
126{
127    fn new(base_key: StorageKey<SA>) -> Self {
128        SetMapper {
129            _phantom_api: PhantomData,
130            address: CurrentStorage,
131            base_key: base_key.clone(),
132            queue_mapper: QueueMapper::new(base_key),
133        }
134    }
135}
136
137impl<SA, T> StorageClearable for SetMapper<SA, T, CurrentStorage>
138where
139    SA: StorageMapperApi,
140    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
141{
142    fn clear(&mut self) {
143        for value in self.queue_mapper.iter() {
144            self.clear_node_id(&value);
145        }
146        self.queue_mapper.clear();
147    }
148}
149
150impl<SA, T> StorageMapperFromAddress<SA> for SetMapper<SA, T, ManagedAddress<SA>>
151where
152    SA: StorageMapperApi,
153    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
154{
155    fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
156        SetMapper {
157            _phantom_api: PhantomData,
158            address: address.clone(),
159            base_key: base_key.clone(),
160            queue_mapper: QueueMapper::new_from_address(address, base_key),
161        }
162    }
163}
164
165impl<SA, T> SetMapper<SA, T, CurrentStorage>
166where
167    SA: StorageMapperApi,
168    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
169{
170    fn set_node_id(&self, value: &T, node_id: u32) {
171        storage_set(
172            self.build_named_value_key(NODE_ID_IDENTIFIER, value)
173                .as_ref(),
174            &node_id,
175        );
176    }
177
178    fn clear_node_id(&self, value: &T) {
179        storage_set(
180            self.build_named_value_key(NODE_ID_IDENTIFIER, value)
181                .as_ref(),
182            &codec::Empty,
183        );
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        let new_node_id = self.queue_mapper.push_back_node_id(&value);
196        self.set_node_id(&value, new_node_id);
197        true
198    }
199
200    /// Removes a value from the set. Returns whether the value was
201    /// present in the set.
202    pub fn remove(&mut self, value: &T) -> bool {
203        let node_id = self.get_node_id(value);
204        if node_id == NULL_ENTRY {
205            return false;
206        }
207        self.queue_mapper.remove_by_node_id(node_id);
208        self.clear_node_id(value);
209        true
210    }
211
212    pub fn remove_all<I>(&mut self, iter: I)
213    where
214        I: IntoIterator<Item = T>,
215    {
216        for item in iter {
217            self.remove(&item);
218        }
219    }
220}
221
222impl<SA, A, T> SetMapper<SA, T, A>
223where
224    SA: StorageMapperApi,
225    A: StorageAddress<SA>,
226    T: TopEncode + TopDecode + NestedEncode + NestedDecode,
227{
228    pub fn build_named_value_key(&self, name: &[u8], value: &T) -> StorageKey<SA> {
229        let mut named_key = self.base_key.clone();
230        named_key.append_bytes(name);
231        named_key.append_item(value);
232        named_key
233    }
234
235    /// An iterator visiting all elements in arbitrary order.
236    /// The iterator element type is `&'a T`.
237    pub fn iter(&self) -> Iter<'_, SA, A, T> {
238        self.queue_mapper.iter()
239    }
240
241    pub fn iter_from(&self, value: &T) -> Iter<'_, SA, A, T> {
242        let node_id = self.get_node_id(value);
243        self.queue_mapper.iter_from_node_id(node_id)
244    }
245
246    fn get_node_id(&self, value: &T) -> u32 {
247        self.address.address_storage_get(
248            self.build_named_value_key(NODE_ID_IDENTIFIER, value)
249                .as_ref(),
250        )
251    }
252
253    /// Returns `true` if the set contains a value.
254    pub fn contains(&self, value: &T) -> bool {
255        self.get_node_id(value) != NULL_ENTRY
256    }
257
258    /// Returns `true` if the set contains no elements.
259    pub fn is_empty(&self) -> bool {
260        self.queue_mapper.is_empty()
261    }
262
263    /// Returns the number of elements in the set.
264    pub fn len(&self) -> usize {
265        self.queue_mapper.len()
266    }
267
268    /// Checks the internal consistency of the collection. Used for unit tests.
269    pub fn check_internal_consistency(&self) -> bool {
270        self.queue_mapper.check_internal_consistency()
271    }
272
273    pub fn next(&self, value: &T) -> Option<T> {
274        let node_id = self.get_node_id(value);
275        if node_id == NULL_ENTRY {
276            return None;
277        }
278
279        let next_node_id = self.queue_mapper.get_node(node_id).next;
280
281        self.queue_mapper.get_value_option(next_node_id)
282    }
283
284    pub fn previous(&self, value: &T) -> Option<T> {
285        let node_id = self.get_node_id(value);
286        if node_id == NULL_ENTRY {
287            return None;
288        }
289
290        let next_node_id = self.queue_mapper.get_node(node_id).previous;
291
292        self.queue_mapper.get_value_option(next_node_id)
293    }
294
295    pub fn front(&self) -> Option<T> {
296        self.queue_mapper.front()
297    }
298
299    pub fn back(&self) -> Option<T> {
300        self.queue_mapper.back()
301    }
302}
303
304impl<'a, SA, A, T> IntoIterator for &'a SetMapper<SA, T, A>
305where
306    SA: StorageMapperApi,
307    A: StorageAddress<SA>,
308    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
309{
310    type Item = T;
311
312    type IntoIter = Iter<'a, SA, A, T>;
313
314    fn into_iter(self) -> Self::IntoIter {
315        self.iter()
316    }
317}
318
319impl<SA, T> Extend<T> for SetMapper<SA, T, CurrentStorage>
320where
321    SA: StorageMapperApi,
322    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
323{
324    fn extend<I>(&mut self, iter: I)
325    where
326        I: IntoIterator<Item = T>,
327    {
328        for item in iter {
329            self.insert(item);
330        }
331    }
332}
333
334/// Behaves like a MultiResultVec when an endpoint result.
335impl<SA, T> TopEncodeMulti for SetMapper<SA, T, CurrentStorage>
336where
337    SA: StorageMapperApi,
338    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
339{
340    fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
341    where
342        O: TopEncodeMultiOutput,
343        H: EncodeErrorHandler,
344    {
345        multi_encode_iter_or_handle_err(self.iter(), output, h)
346    }
347}
348
349impl<SA, T> TypeAbiFrom<SetMapper<SA, T, CurrentStorage>> for MultiValueEncoded<SA, T>
350where
351    SA: StorageMapperApi,
352    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
353{
354}
355
356impl<SA, T> TypeAbiFrom<Self> for SetMapper<SA, T, CurrentStorage>
357where
358    SA: StorageMapperApi,
359    T: TopEncode + TopDecode + NestedEncode + NestedDecode + 'static,
360{
361}
362
363/// Behaves like a MultiResultVec when an endpoint result.
364impl<SA, T> TypeAbi for SetMapper<SA, T, CurrentStorage>
365where
366    SA: StorageMapperApi,
367    T: TopEncode + TopDecode + NestedEncode + NestedDecode + TypeAbi,
368{
369    type Unmanaged = Self;
370
371    fn type_name() -> TypeName {
372        crate::abi::type_name_variadic::<T>()
373    }
374
375    fn type_name_rust() -> TypeName {
376        crate::abi::type_name_multi_value_encoded::<T>()
377    }
378
379    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
380        T::provide_type_descriptions(accumulator);
381    }
382
383    fn is_variadic() -> bool {
384        true
385    }
386}
multiversx_sc/storage/mappers/set_mapper.rs

multiversx_sc/storage/mappers/
set_mapper.rs
