multiversx_sc/storage/mappers/
queue_mapper.rs

1use core::marker::PhantomData;
2
3use super::{
4    source::{CurrentStorage, StorageAddress},
5    StorageClearable, StorageMapper, StorageMapperFromAddress,
6};
7use crate::{
8    abi::{TypeAbi, TypeAbiFrom, TypeDescriptionContainer, TypeName},
9    api::StorageMapperApi,
10    codec::{
11        self,
12        derive::{TopDecode, TopDecodeOrDefault, TopEncode, TopEncodeOrDefault},
13        multi_encode_iter_or_handle_err, DecodeDefault, EncodeDefault, EncodeErrorHandler,
14        TopDecode, TopEncode, TopEncodeMulti, TopEncodeMultiOutput,
15    },
16    storage::{storage_set, StorageKey},
17    types::{ManagedAddress, ManagedType, MultiValueEncoded},
18};
19use alloc::vec::Vec;
20
21const NULL_ENTRY: u32 = 0;
22const INFO_IDENTIFIER: &[u8] = b".info";
23const NODE_IDENTIFIER: &[u8] = b".node_links";
24const VALUE_IDENTIFIER: &[u8] = b".value";
25
26#[derive(TopEncode, TopDecode, PartialEq, Eq, Clone, Copy)]
27pub struct Node {
28    pub previous: u32,
29    pub next: u32,
30}
31
32#[derive(TopEncodeOrDefault, TopDecodeOrDefault, PartialEq, Eq, Clone, Copy)]
33pub struct QueueMapperInfo {
34    pub len: u32,
35    pub front: u32,
36    pub back: u32,
37    pub new: u32,
38}
39
40impl EncodeDefault for QueueMapperInfo {
41    fn is_default(&self) -> bool {
42        self.len == 0
43    }
44}
45
46impl DecodeDefault for QueueMapperInfo {
47    fn default() -> Self {
48        Self {
49            len: 0,
50            front: 0,
51            back: 0,
52            new: 0,
53        }
54    }
55}
56
57impl QueueMapperInfo {
58    pub fn generate_new_node_id(&mut self) -> u32 {
59        self.new += 1;
60        self.new
61    }
62}
63
64/// A queue with owned nodes.
65///
66/// The `QueueMapper` allows pushing and popping elements at either end
67/// in constant time.
68pub struct QueueMapper<SA, T, A = CurrentStorage>
69where
70    SA: StorageMapperApi,
71    A: StorageAddress<SA>,
72    T: TopEncode + TopDecode + 'static,
73{
74    _phantom_api: PhantomData<SA>,
75    address: A,
76    base_key: StorageKey<SA>,
77    _phantom_item: PhantomData<T>,
78}
79
80impl<SA, T> StorageMapper<SA> for QueueMapper<SA, T, CurrentStorage>
81where
82    SA: StorageMapperApi,
83    T: TopEncode + TopDecode,
84{
85    fn new(base_key: StorageKey<SA>) -> Self {
86        QueueMapper {
87            _phantom_api: PhantomData,
88            address: CurrentStorage,
89            base_key,
90            _phantom_item: PhantomData,
91        }
92    }
93}
94
95impl<SA, T> StorageClearable for QueueMapper<SA, T, CurrentStorage>
96where
97    SA: StorageMapperApi,
98    T: TopEncode + TopDecode,
99{
100    fn clear(&mut self) {
101        let info = self.get_info();
102        let mut node_id = info.front;
103        while node_id != NULL_ENTRY {
104            let node = self.get_node(node_id);
105            self.clear_node(node_id);
106            self.clear_value(node_id);
107            node_id = node.next;
108        }
109        self.set_info(QueueMapperInfo::default());
110    }
111}
112
113impl<SA, T> QueueMapper<SA, T, CurrentStorage>
114where
115    SA: StorageMapperApi,
116    T: TopEncode + TopDecode,
117{
118    fn set_info(&mut self, value: QueueMapperInfo) {
119        storage_set(self.build_name_key(INFO_IDENTIFIER).as_ref(), &value);
120    }
121
122    fn set_node(&mut self, node_id: u32, item: Node) {
123        storage_set(
124            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
125                .as_ref(),
126            &item,
127        );
128    }
129
130    fn clear_node(&mut self, node_id: u32) {
131        storage_set(
132            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
133                .as_ref(),
134            &codec::Empty,
135        );
136    }
137
138    fn set_value(&mut self, node_id: u32, value: &T) {
139        storage_set(
140            self.build_node_id_named_key(VALUE_IDENTIFIER, node_id)
141                .as_ref(),
142            value,
143        )
144    }
145
146    fn clear_value(&mut self, node_id: u32) {
147        storage_set(
148            self.build_node_id_named_key(VALUE_IDENTIFIER, node_id)
149                .as_ref(),
150            &codec::Empty,
151        )
152    }
153
154    /// Appends an element to the back of a queue
155    /// and returns the node id of the newly added node.
156    ///
157    /// This operation should compute in *O*(1) time.
158    pub(crate) fn push_back_node_id(&mut self, elt: &T) -> u32 {
159        let mut info = self.get_info();
160        let new_node_id = info.generate_new_node_id();
161        let mut previous = NULL_ENTRY;
162        if info.len == 0 {
163            info.front = new_node_id;
164        } else {
165            let back = info.back;
166            let mut back_node = self.get_node(back);
167            back_node.next = new_node_id;
168            previous = back;
169            self.set_node(back, back_node);
170        }
171        self.set_node(
172            new_node_id,
173            Node {
174                previous,
175                next: NULL_ENTRY,
176            },
177        );
178        info.back = new_node_id;
179        self.set_value(new_node_id, elt);
180        info.len += 1;
181        self.set_info(info);
182        new_node_id
183    }
184
185    /// Appends an element to the back of a queue.
186    ///
187    /// This operation should compute in *O*(1) time.
188    pub fn push_back(&mut self, elt: T) {
189        let _ = self.push_back_node_id(&elt);
190    }
191
192    /// Adds an element first in the queue.
193    ///
194    /// This operation should compute in *O*(1) time.
195    pub fn push_front(&mut self, elt: T) {
196        let mut info = self.get_info();
197        let new_node_id = info.generate_new_node_id();
198        let mut next = NULL_ENTRY;
199        if info.len == 0 {
200            info.back = new_node_id;
201        } else {
202            let front = info.front;
203            let mut front_node = self.get_node(front);
204            front_node.previous = new_node_id;
205            next = front;
206            self.set_node(front, front_node);
207        }
208        self.set_node(
209            new_node_id,
210            Node {
211                previous: NULL_ENTRY,
212                next,
213            },
214        );
215        info.front = new_node_id;
216        self.set_value(new_node_id, &elt);
217        info.len += 1;
218        self.set_info(info);
219    }
220
221    /// Removes the last element from a queue and returns it, or `None` if
222    /// it is empty.
223    ///
224    /// This operation should compute in *O*(1) time.
225    pub fn pop_back(&mut self) -> Option<T> {
226        self.remove_by_node_id(self.get_info().back)
227    }
228
229    /// Removes the first element and returns it, or `None` if the queue is
230    /// empty.
231    ///
232    /// This operation should compute in *O*(1) time.
233    pub fn pop_front(&mut self) -> Option<T> {
234        self.remove_by_node_id(self.get_info().front)
235    }
236
237    /// Removes element with the given node id and returns it, or `None` if the queue is
238    /// empty.
239    /// Note: has undefined behavior if there's no node with the given node id in the queue
240    ///
241    /// This operation should compute in *O*(1) time.
242    pub(crate) fn remove_by_node_id(&mut self, node_id: u32) -> Option<T> {
243        if node_id == NULL_ENTRY {
244            return None;
245        }
246        let node = self.get_node(node_id);
247
248        let mut info = self.get_info();
249        if node.previous == NULL_ENTRY {
250            info.front = node.next;
251        } else {
252            let mut previous = self.get_node(node.previous);
253            previous.next = node.next;
254            self.set_node(node.previous, previous);
255        }
256
257        if node.next == NULL_ENTRY {
258            info.back = node.previous;
259        } else {
260            let mut next = self.get_node(node.next);
261            next.previous = node.previous;
262            self.set_node(node.next, next);
263        }
264
265        self.clear_node(node_id);
266        let removed_value = self.get_value(node_id);
267        self.clear_value(node_id);
268        info.len -= 1;
269        self.set_info(info);
270        Some(removed_value)
271    }
272}
273
274impl<SA, T> StorageMapperFromAddress<SA> for QueueMapper<SA, T, ManagedAddress<SA>>
275where
276    SA: StorageMapperApi,
277    T: TopEncode + TopDecode,
278{
279    fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
280        QueueMapper {
281            _phantom_api: PhantomData::<SA>,
282            address,
283            base_key,
284            _phantom_item: PhantomData::<T>,
285        }
286    }
287}
288
289impl<SA, A, T> QueueMapper<SA, T, A>
290where
291    SA: StorageMapperApi,
292    A: StorageAddress<SA>,
293    T: TopEncode + TopDecode + 'static,
294{
295    fn build_node_id_named_key(&self, name: &[u8], node_id: u32) -> StorageKey<SA> {
296        let mut named_key = self.base_key.clone();
297        named_key.append_bytes(name);
298        named_key.append_item(&node_id);
299        named_key
300    }
301
302    fn build_name_key(&self, name: &[u8]) -> StorageKey<SA> {
303        let mut name_key = self.base_key.clone();
304        name_key.append_bytes(name);
305        name_key
306    }
307
308    pub fn iter(&self) -> Iter<'_, SA, A, T> {
309        Iter::new(self)
310    }
311
312    pub fn iter_from_node_id(&self, node_id: u32) -> Iter<'_, SA, A, T> {
313        Iter::new_from_node_id(self, node_id)
314    }
315
316    fn get_info(&self) -> QueueMapperInfo {
317        self.address
318            .address_storage_get(self.build_name_key(INFO_IDENTIFIER).as_ref())
319    }
320
321    pub fn get_node(&self, node_id: u32) -> Node {
322        self.address.address_storage_get(
323            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
324                .as_ref(),
325        )
326    }
327
328    fn get_value(&self, node_id: u32) -> T {
329        self.address.address_storage_get(
330            self.build_node_id_named_key(VALUE_IDENTIFIER, node_id)
331                .as_ref(),
332        )
333    }
334
335    pub fn get_value_option(&self, node_id: u32) -> Option<T> {
336        if node_id == NULL_ENTRY {
337            return None;
338        }
339        Some(self.get_value(node_id))
340    }
341
342    /// Returns `true` if the `Queue` is empty.
343    ///
344    /// This operation should compute in *O*(1) time.
345    pub fn is_empty(&self) -> bool {
346        self.get_info().len == 0
347    }
348
349    /// Returns the length of the `Queue`.
350    ///
351    /// This operation should compute in *O*(1) time.
352    pub fn len(&self) -> usize {
353        self.get_info().len as usize
354    }
355
356    /// Provides a copy to the front element, or `None` if the queue is
357    /// empty.
358    pub fn front(&self) -> Option<T> {
359        self.get_value_option(self.get_info().front)
360    }
361
362    /// Provides a copy to the back element, or `None` if the queue is
363    /// empty.
364    pub fn back(&self) -> Option<T> {
365        self.get_value_option(self.get_info().back)
366    }
367
368    /// Runs several checks in order to verify that both forwards and backwards iteration
369    /// yields the same node entries and that the number of items in the queue is correct.
370    /// Used for unit testing.
371    ///
372    /// This operation should compute in *O*(n) time.
373    pub fn check_internal_consistency(&self) -> bool {
374        let info = self.get_info();
375        let mut front = info.front;
376        let mut back = info.back;
377        if info.len == 0 {
378            // if the queue is empty, both ends should point to null entries
379            if front != NULL_ENTRY {
380                return false;
381            }
382            if back != NULL_ENTRY {
383                return false;
384            }
385            true
386        } else {
387            // if the queue is non-empty, both ends should point to non-null entries
388            if front == NULL_ENTRY {
389                return false;
390            }
391            if back == NULL_ENTRY {
392                return false;
393            }
394
395            // the node before the first and the one after the last should both be null
396            if self.get_node(front).previous != NULL_ENTRY {
397                return false;
398            }
399            if self.get_node(back).next != NULL_ENTRY {
400                return false;
401            }
402
403            // iterate forwards
404            let mut forwards = Vec::new();
405            while front != NULL_ENTRY {
406                forwards.push(front);
407                front = self.get_node(front).next;
408            }
409            if forwards.len() != info.len as usize {
410                return false;
411            }
412
413            // iterate backwards
414            let mut backwards = Vec::new();
415            while back != NULL_ENTRY {
416                backwards.push(back);
417                back = self.get_node(back).previous;
418            }
419            if backwards.len() != info.len as usize {
420                return false;
421            }
422
423            // check that both iterations match element-wise
424            let backwards_reversed: Vec<u32> = backwards.iter().rev().cloned().collect();
425            if forwards != backwards_reversed {
426                return false;
427            }
428
429            // check that the node IDs are unique
430            forwards.sort_unstable();
431            forwards.dedup();
432            if forwards.len() != info.len as usize {
433                return false;
434            }
435            true
436        }
437    }
438}
439
440impl<'a, SA, A, T> IntoIterator for &'a QueueMapper<SA, T, A>
441where
442    SA: StorageMapperApi,
443    A: StorageAddress<SA>,
444    T: TopEncode + TopDecode + 'static,
445{
446    type Item = T;
447
448    type IntoIter = Iter<'a, SA, A, T>;
449
450    fn into_iter(self) -> Self::IntoIter {
451        self.iter()
452    }
453}
454
455/// An iterator over the elements of a `QueueMapper`.
456///
457/// This `struct` is created by [`QueueMapper::iter()`]. See its
458/// documentation for more.
459pub struct Iter<'a, SA, A, T>
460where
461    SA: StorageMapperApi,
462    A: StorageAddress<SA>,
463    T: TopEncode + TopDecode + 'static,
464{
465    node_id: u32,
466    queue: &'a QueueMapper<SA, T, A>,
467}
468
469impl<'a, SA, A, T> Iter<'a, SA, A, T>
470where
471    SA: StorageMapperApi,
472    A: StorageAddress<SA>,
473    T: TopEncode + TopDecode + 'static,
474{
475    fn new(queue: &'a QueueMapper<SA, T, A>) -> Iter<'a, SA, A, T> {
476        Iter {
477            node_id: queue.get_info().front,
478            queue,
479        }
480    }
481
482    pub fn new_from_node_id(queue: &'a QueueMapper<SA, T, A>, node_id: u32) -> Iter<'a, SA, A, T> {
483        Iter { node_id, queue }
484    }
485}
486
487impl<SA, A, T> Iterator for Iter<'_, SA, A, T>
488where
489    SA: StorageMapperApi,
490    A: StorageAddress<SA>,
491    T: TopEncode + TopDecode + 'static,
492{
493    type Item = T;
494
495    #[inline]
496    fn next(&mut self) -> Option<T> {
497        let current_node_id = self.node_id;
498        if current_node_id == NULL_ENTRY {
499            return None;
500        }
501        self.node_id = self.queue.get_node(current_node_id).next;
502        Some(self.queue.get_value(current_node_id))
503    }
504}
505
506/// Behaves like a MultiResultVec when an endpoint result.
507impl<SA, T> TopEncodeMulti for QueueMapper<SA, T, CurrentStorage>
508where
509    SA: StorageMapperApi,
510    T: TopEncode + TopDecode,
511{
512    fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
513    where
514        O: TopEncodeMultiOutput,
515        H: EncodeErrorHandler,
516    {
517        multi_encode_iter_or_handle_err(self.iter(), output, h)
518    }
519}
520
521impl<SA, T> TypeAbiFrom<QueueMapper<SA, T, CurrentStorage>> for MultiValueEncoded<SA, T>
522where
523    SA: StorageMapperApi,
524    T: TopEncode + TopDecode,
525{
526}
527
528impl<SA, T> TypeAbiFrom<Self> for QueueMapper<SA, T, CurrentStorage>
529where
530    SA: StorageMapperApi,
531    T: TopEncode + TopDecode,
532{
533}
534
535/// Behaves like a MultiResultVec when an endpoint result.
536impl<SA, T> TypeAbi for QueueMapper<SA, T, CurrentStorage>
537where
538    SA: StorageMapperApi,
539    T: TopEncode + TopDecode + TypeAbi,
540{
541    type Unmanaged = Self;
542
543    fn type_name() -> TypeName {
544        crate::abi::type_name_variadic::<T>()
545    }
546
547    fn type_name_rust() -> TypeName {
548        crate::abi::type_name_multi_value_encoded::<T>()
549    }
550
551    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
552        T::provide_type_descriptions(accumulator);
553    }
554
555    fn is_variadic() -> bool {
556        true
557    }
558}
multiversx_sc/storage/mappers/queue_mapper.rs

multiversx_sc/storage/mappers/
queue_mapper.rs
