multiversx_sc/storage/mappers/
linked_list_mapper.rs

1use core::marker::PhantomData;
2
3use super::{
4    StorageClearable, StorageMapper, StorageMapperFromAddress,
5    source::{CurrentStorage, StorageAddress},
6};
7use crate::{
8    abi::{TypeAbi, TypeAbiFrom, TypeDescriptionContainer, TypeName},
9    api::StorageMapperApi,
10    codec::{
11        self, DecodeDefault, EncodeDefault, EncodeErrorHandler, NestedDecode, NestedEncode,
12        TopDecode, TopEncode, TopEncodeMulti, TopEncodeMultiOutput,
13        derive::{
14            NestedDecode, NestedEncode, TopDecode, TopDecodeOrDefault, TopEncode,
15            TopEncodeOrDefault,
16        },
17    },
18    storage::{StorageKey, storage_set},
19    types::{ManagedAddress, ManagedType, MultiValueEncoded, heap::BoxedBytes},
20};
21use alloc::vec::Vec;
22
23const NULL_ENTRY: u32 = 0;
24const INFO_IDENTIFIER: &[u8] = b".info";
25const NODE_IDENTIFIER: &[u8] = b".node";
26
27#[derive(NestedEncode, NestedDecode, TopEncode, TopDecode, PartialEq, Eq, Clone, Copy)]
28pub struct LinkedListNode<T: NestedEncode + NestedDecode + TopEncode + TopDecode + Clone> {
29    pub(crate) value: T,
30    pub(crate) node_id: u32,
31    pub(crate) next_id: u32,
32    pub(crate) prev_id: u32,
33}
34
35impl<T: NestedEncode + NestedDecode + TopEncode + TopDecode + Clone> LinkedListNode<T> {
36    pub fn get_value_cloned(&self) -> T {
37        self.value.clone()
38    }
39
40    pub fn get_value_as_ref(&self) -> &T {
41        &self.value
42    }
43
44    pub fn into_value(self) -> T {
45        self.value
46    }
47
48    pub fn get_node_id(&self) -> u32 {
49        self.node_id
50    }
51
52    pub fn get_next_node_id(&self) -> u32 {
53        self.next_id
54    }
55
56    pub fn get_prev_node_id(&self) -> u32 {
57        self.prev_id
58    }
59}
60
61#[derive(TopEncodeOrDefault, TopDecodeOrDefault, PartialEq, Eq, Clone, Copy)]
62pub struct LinkedListInfo {
63    pub len: u32,
64    pub front: u32,
65    pub back: u32,
66    pub new: u32,
67}
68
69impl EncodeDefault for LinkedListInfo {
70    fn is_default(&self) -> bool {
71        self.len == 0
72    }
73}
74
75impl DecodeDefault for LinkedListInfo {
76    fn default() -> Self {
77        Self {
78            len: 0,
79            front: 0,
80            back: 0,
81            new: 0,
82        }
83    }
84}
85
86impl LinkedListInfo {
87    pub fn generate_new_node_id(&mut self) -> u32 {
88        self.new += 1;
89        self.new
90    }
91}
92
93/// A storage mapper implementing a doubly-linked list with efficient insertion and removal at any position.
94///
95/// # Storage Layout
96///
97/// The `LinkedListMapper` stores metadata and individual nodes separately:
98///
99/// 1. **Metadata**:
100///    - `base_key + ".info"` → `LinkedListInfo` struct containing:
101///      - `len`: number of elements
102///      - `front`: node ID of the first element
103///      - `back`: node ID of the last element
104///      - `new`: counter for generating unique node IDs
105///
106/// 2. **Nodes**:
107///    - `base_key + ".node" + node_id` → `LinkedListNode<T>` containing:
108///      - `value`: the stored item
109///      - `node_id`: this node's unique ID
110///      - `next_id`: ID of the next node (0 if none)
111///      - `prev_id`: ID of the previous node (0 if none)
112///
113/// # Main Operations
114///
115/// - **Append**: `push_back(item)` - Adds to the end. O(1) with constant storage writes.
116/// - **Prepend**: `push_front(item)` - Adds to the beginning. O(1) with constant storage writes.
117/// - **Insert**: `push_after(node, item)` / `push_before(node, item)` - Inserts at specific position. O(1).
118/// - **Remove**: `pop_front()` / `pop_back()` / `remove_node(node)` - Removes from any position. O(1).
119/// - **Access**: `front()` / `back()` / `get_node_by_id(id)` - Retrieves nodes. O(1).
120/// - **Iteration**: `iter()` - Traverses from front to back; `iter_from_node_id(id)` - starts from specific node.
121///
122/// # Trade-offs
123///
124/// - **Pros**: O(1) insertion/removal at any position; maintains insertion order; efficient for queue/deque patterns.
125/// - **Cons**: No random access by index; higher storage overhead per element (stores prev/next pointers);
126///   iteration requires following links; removed nodes leave "gaps" in node ID space.
127///
128/// # Use Cases
129///
130/// - Task queues where items can be added/removed at any position
131/// - Priority management where items move positions frequently
132/// - Scenarios requiring both ordered iteration and arbitrary insertion/removal
133///
134/// # Example
135///
136/// ```rust
137/// # use multiversx_sc::storage::mappers::{StorageMapper, LinkedListMapper};
138/// # fn example<SA: multiversx_sc::api::StorageMapperApi>() {
139/// # let mut mapper = LinkedListMapper::<SA, u64>::new(
140/// #     multiversx_sc::storage::StorageKey::new(&b"tasks"[..])
141/// # );
142/// // Add elements
143/// let node1 = mapper.push_back(100);
144/// let node2 = mapper.push_back(200);
145/// let node3 = mapper.push_back(300);
146///
147/// assert_eq!(mapper.len(), 3);
148/// assert_eq!(mapper.front().unwrap().into_value(), 100);
149/// assert_eq!(mapper.back().unwrap().into_value(), 300);
150///
151/// // Insert in the middle
152/// let mut node2_mut = node2.clone();
153/// mapper.push_after(&mut node2_mut, 250);
154/// assert_eq!(mapper.len(), 4);
155///
156/// // Remove from front
157/// let removed = mapper.pop_front().unwrap();
158/// assert_eq!(removed.into_value(), 100);
159/// assert_eq!(mapper.len(), 3);
160///
161/// // Remove specific node
162/// mapper.remove_node(&node2);
163/// assert_eq!(mapper.len(), 2);
164///
165/// // Iterate through remaining elements
166/// for node in mapper.iter() {
167///     let value = node.into_value();
168///     // Process value
169/// }
170/// # }
171/// ```
172pub struct LinkedListMapper<SA, T, A = CurrentStorage>
173where
174    SA: StorageMapperApi,
175    A: StorageAddress<SA>,
176    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
177{
178    _phantom_api: PhantomData<SA>,
179    address: A,
180    base_key: StorageKey<SA>,
181    _phantom_item: PhantomData<T>,
182}
183
184impl<SA, T> StorageMapper<SA> for LinkedListMapper<SA, T, CurrentStorage>
185where
186    SA: StorageMapperApi,
187    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
188{
189    fn new(base_key: StorageKey<SA>) -> Self {
190        LinkedListMapper {
191            _phantom_api: PhantomData,
192            address: CurrentStorage,
193            base_key,
194            _phantom_item: PhantomData,
195        }
196    }
197}
198
199impl<SA, T> StorageMapperFromAddress<SA> for LinkedListMapper<SA, T, ManagedAddress<SA>>
200where
201    SA: StorageMapperApi,
202    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
203{
204    fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
205        LinkedListMapper {
206            _phantom_api: PhantomData,
207            address,
208            base_key,
209            _phantom_item: PhantomData,
210        }
211    }
212}
213
214impl<SA, T> StorageClearable for LinkedListMapper<SA, T>
215where
216    SA: StorageMapperApi,
217    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
218{
219    fn clear(&mut self) {
220        let info = self.get_info();
221        let mut node_id = info.front;
222
223        while node_id != NULL_ENTRY {
224            let node = self.get_node(node_id);
225            self.clear_node(node_id);
226            node_id = node.next_id;
227        }
228
229        self.set_info(LinkedListInfo::default());
230    }
231}
232
233impl<SA, T, A> LinkedListMapper<SA, T, A>
234where
235    SA: StorageMapperApi,
236    A: StorageAddress<SA>,
237    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
238{
239    fn build_node_id_named_key(&self, name: &[u8], node_id: u32) -> StorageKey<SA> {
240        let mut named_key = self.base_key.clone();
241        named_key.append_bytes(name);
242        named_key.append_item(&node_id);
243        named_key
244    }
245
246    fn build_name_key(&self, name: &[u8]) -> StorageKey<SA> {
247        let mut name_key = self.base_key.clone();
248        name_key.append_bytes(name);
249        name_key
250    }
251
252    fn get_info(&self) -> LinkedListInfo {
253        self.address
254            .address_storage_get(self.build_name_key(INFO_IDENTIFIER).as_ref())
255    }
256
257    fn get_node(&self, node_id: u32) -> LinkedListNode<T> {
258        self.address.address_storage_get(
259            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
260                .as_ref(),
261        )
262    }
263
264    fn is_empty_node(&self, node_id: u32) -> bool {
265        self.address.address_storage_get_len(
266            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
267                .as_ref(),
268        ) == 0
269    }
270
271    pub fn is_empty(&self) -> bool {
272        self.get_info().len == 0
273    }
274
275    pub fn len(&self) -> usize {
276        self.get_info().len as usize
277    }
278
279    pub fn front(&self) -> Option<LinkedListNode<T>> {
280        let info = self.get_info();
281
282        self.get_node_by_id(info.front)
283    }
284
285    pub fn back(&self) -> Option<LinkedListNode<T>> {
286        let info = self.get_info();
287
288        self.get_node_by_id(info.back)
289    }
290
291    pub fn get_node_by_id(&self, node_id: u32) -> Option<LinkedListNode<T>> {
292        if self.is_empty_node(node_id) {
293            return None;
294        }
295
296        Some(self.get_node(node_id))
297    }
298
299    pub fn iter(&self) -> Iter<'_, SA, T, A> {
300        Iter::new(self)
301    }
302
303    pub fn iter_from_node_id(&self, node_id: u32) -> Iter<'_, SA, T, A> {
304        Iter::new_from_node_id(self, node_id)
305    }
306
307    pub fn check_internal_consistency(&self) -> bool {
308        let info = self.get_info();
309        let mut front = info.front;
310        let mut back = info.back;
311
312        if info.len == 0 {
313            if front != NULL_ENTRY {
314                return false;
315            }
316            if back != NULL_ENTRY {
317                return false;
318            }
319            true
320        } else {
321            if front == NULL_ENTRY {
322                return false;
323            }
324            if back == NULL_ENTRY {
325                return false;
326            }
327
328            if self.get_node(front).prev_id != NULL_ENTRY {
329                return false;
330            }
331            if self.get_node(back).next_id != NULL_ENTRY {
332                return false;
333            }
334
335            let mut forwards = Vec::new();
336            while front != NULL_ENTRY {
337                forwards.push(front);
338                front = self.get_node(front).next_id;
339            }
340            if forwards.len() != info.len as usize {
341                return false;
342            }
343
344            let mut backwards = Vec::new();
345            while back != NULL_ENTRY {
346                backwards.push(back);
347                back = self.get_node(back).prev_id;
348            }
349            if backwards.len() != info.len as usize {
350                return false;
351            }
352
353            let backwards_reversed: Vec<u32> = backwards.iter().rev().cloned().collect();
354            if forwards != backwards_reversed {
355                return false;
356            }
357
358            forwards.sort_unstable();
359            forwards.dedup();
360            if forwards.len() != info.len as usize {
361                return false;
362            }
363            true
364        }
365    }
366}
367
368impl<SA, T> LinkedListMapper<SA, T, CurrentStorage>
369where
370    SA: StorageMapperApi,
371    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
372{
373    fn set_info(&mut self, value: LinkedListInfo) {
374        storage_set(self.build_name_key(INFO_IDENTIFIER).as_ref(), &value);
375    }
376
377    fn set_node(&mut self, node_id: u32, item: &LinkedListNode<T>) {
378        storage_set(
379            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
380                .as_ref(),
381            item,
382        );
383    }
384
385    fn clear_node(&mut self, node_id: u32) {
386        storage_set(
387            self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
388                .as_ref(),
389            &BoxedBytes::empty(),
390        );
391    }
392
393    pub fn pop_back(&mut self) -> Option<LinkedListNode<T>> {
394        let info = self.get_info();
395
396        self.remove_node_by_id(info.back)
397    }
398
399    pub fn pop_front(&mut self) -> Option<LinkedListNode<T>> {
400        let info = self.get_info();
401
402        self.remove_node_by_id(info.front)
403    }
404
405    pub fn push_after(
406        &mut self,
407        node: &mut LinkedListNode<T>,
408        element: T,
409    ) -> Option<LinkedListNode<T>> {
410        if self.is_empty_node(node.node_id) {
411            return None;
412        }
413
414        let mut info = self.get_info();
415        let new_node_id = info.generate_new_node_id();
416
417        let new_node_next_id = node.next_id;
418        node.next_id = new_node_id;
419        self.set_node(node.node_id, node);
420
421        if new_node_next_id == NULL_ENTRY {
422            info.back = new_node_id;
423        } else {
424            let mut next_node = self.get_node(new_node_next_id);
425            next_node.prev_id = new_node_id;
426            self.set_node(new_node_next_id, &next_node);
427        }
428
429        let new_node = LinkedListNode {
430            value: element,
431            node_id: new_node_id,
432            next_id: new_node_next_id,
433            prev_id: node.node_id,
434        };
435        self.set_node(new_node_id, &new_node);
436
437        info.len += 1;
438        self.set_info(info);
439        Some(new_node)
440    }
441
442    pub fn push_before(
443        &mut self,
444        node: &mut LinkedListNode<T>,
445        element: T,
446    ) -> Option<LinkedListNode<T>> {
447        if self.is_empty_node(node.node_id) {
448            return None;
449        }
450
451        let mut info = self.get_info();
452        let new_node_id = info.generate_new_node_id();
453
454        let new_node_prev_id = node.prev_id;
455        node.prev_id = new_node_id;
456        self.set_node(node.node_id, node);
457
458        if new_node_prev_id == NULL_ENTRY {
459            info.front = new_node_id;
460        } else {
461            let mut previous_node = self.get_node(new_node_prev_id);
462            previous_node.next_id = new_node_id;
463            self.set_node(new_node_prev_id, &previous_node);
464        }
465
466        let new_node = LinkedListNode {
467            value: element,
468            node_id: new_node_id,
469            next_id: node.node_id,
470            prev_id: new_node_prev_id,
471        };
472        self.set_node(new_node_id, &new_node);
473
474        info.len += 1;
475        self.set_info(info);
476        Some(new_node)
477    }
478
479    pub fn push_after_node_id(&mut self, node_id: u32, element: T) -> Option<LinkedListNode<T>> {
480        if !self.is_empty_node(node_id) {
481            let mut node = self.get_node(node_id);
482            self.push_after(&mut node, element)
483        } else {
484            None
485        }
486    }
487
488    pub fn push_before_node_id(&mut self, node_id: u32, element: T) -> Option<LinkedListNode<T>> {
489        if !self.is_empty_node(node_id) {
490            let mut node = self.get_node(node_id);
491            self.push_before(&mut node, element)
492        } else {
493            None
494        }
495    }
496
497    pub fn push_back(&mut self, element: T) -> LinkedListNode<T> {
498        let mut info = self.get_info();
499        let new_node_id = info.generate_new_node_id();
500        let mut previous = NULL_ENTRY;
501
502        if info.len == 0 {
503            info.front = new_node_id;
504        } else {
505            let back = info.back;
506            let mut back_node = self.get_node(back);
507            back_node.next_id = new_node_id;
508            previous = back;
509            self.set_node(back, &back_node);
510        }
511
512        let node = LinkedListNode {
513            value: element,
514            node_id: new_node_id,
515            prev_id: previous,
516            next_id: NULL_ENTRY,
517        };
518        self.set_node(new_node_id, &node);
519
520        info.back = new_node_id;
521        info.len += 1;
522        self.set_info(info);
523        node
524    }
525
526    pub fn push_front(&mut self, element: T) -> LinkedListNode<T> {
527        let mut info = self.get_info();
528        let new_node_id = info.generate_new_node_id();
529        let mut next = NULL_ENTRY;
530
531        if info.len == 0 {
532            info.back = new_node_id;
533        } else {
534            let front = info.front;
535            let mut front_node = self.get_node(front);
536            front_node.prev_id = new_node_id;
537            next = front;
538            self.set_node(front, &front_node);
539        }
540
541        let node = LinkedListNode {
542            value: element,
543            node_id: new_node_id,
544            prev_id: NULL_ENTRY,
545            next_id: next,
546        };
547        self.set_node(new_node_id, &node);
548
549        info.front = new_node_id;
550        info.len += 1;
551        self.set_info(info);
552        node
553    }
554
555    pub fn set_node_value(&mut self, mut node: LinkedListNode<T>, new_value: T) {
556        if self.is_empty_node(node.node_id) {
557            return;
558        }
559
560        node.value = new_value;
561        self.set_node(node.node_id, &node);
562    }
563
564    pub fn set_node_value_by_id(&mut self, node_id: u32, new_value: T) {
565        if let Some(node) = self.get_node_by_id(node_id) {
566            self.set_node_value(node, new_value)
567        }
568    }
569
570    pub fn remove_node(&mut self, node: &LinkedListNode<T>) {
571        let node_id = node.node_id;
572
573        if self.is_empty_node(node_id) {
574            return;
575        }
576
577        let mut info = self.get_info();
578        if node.prev_id == NULL_ENTRY {
579            info.front = node.next_id;
580        } else {
581            let mut previous = self.get_node(node.prev_id);
582            previous.next_id = node.next_id;
583            self.set_node(node.prev_id, &previous);
584        }
585
586        if node.next_id == NULL_ENTRY {
587            info.back = node.prev_id;
588        } else {
589            let mut next = self.get_node(node.next_id);
590            next.prev_id = node.prev_id;
591            self.set_node(node.next_id, &next);
592        }
593
594        self.clear_node(node_id);
595        info.len -= 1;
596        self.set_info(info);
597    }
598
599    pub fn remove_node_by_id(&mut self, node_id: u32) -> Option<LinkedListNode<T>> {
600        if self.is_empty_node(node_id) {
601            return None;
602        }
603
604        let node = self.get_node_by_id(node_id).unwrap();
605        self.remove_node(&node);
606        Some(node)
607    }
608}
609
610impl<'a, SA, T, A> IntoIterator for &'a LinkedListMapper<SA, T, A>
611where
612    SA: StorageMapperApi,
613    A: StorageAddress<SA>,
614    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
615{
616    type Item = LinkedListNode<T>;
617
618    type IntoIter = Iter<'a, SA, T, A>;
619
620    fn into_iter(self) -> Self::IntoIter {
621        self.iter()
622    }
623}
624
625pub struct Iter<'a, SA, T, A>
626where
627    SA: StorageMapperApi,
628    A: StorageAddress<SA>,
629    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
630{
631    node_opt: Option<LinkedListNode<T>>,
632    linked_list: &'a LinkedListMapper<SA, T, A>,
633}
634
635impl<'a, SA, T, A> Iter<'a, SA, T, A>
636where
637    SA: StorageMapperApi,
638    A: StorageAddress<SA>,
639    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
640{
641    fn new(linked_list: &'a LinkedListMapper<SA, T, A>) -> Iter<'a, SA, T, A> {
642        Iter {
643            node_opt: linked_list.front(),
644            linked_list,
645        }
646    }
647
648    fn new_from_node_id(
649        linked_list: &'a LinkedListMapper<SA, T, A>,
650        node_id: u32,
651    ) -> Iter<'a, SA, T, A> {
652        Iter {
653            node_opt: linked_list.get_node_by_id(node_id),
654            linked_list,
655        }
656    }
657}
658
659impl<SA, T, A> Iterator for Iter<'_, SA, T, A>
660where
661    SA: StorageMapperApi,
662    A: StorageAddress<SA>,
663    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
664{
665    type Item = LinkedListNode<T>;
666
667    #[inline]
668    fn next(&mut self) -> Option<LinkedListNode<T>> {
669        self.node_opt.as_ref()?;
670        let node = self.node_opt.clone().unwrap();
671        self.node_opt = self.linked_list.get_node_by_id(node.next_id);
672        Some(node)
673    }
674}
675
676impl<SA, T> TopEncodeMulti for LinkedListMapper<SA, T>
677where
678    SA: StorageMapperApi,
679    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
680{
681    fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
682    where
683        O: TopEncodeMultiOutput,
684        H: EncodeErrorHandler,
685    {
686        for elem in self.iter() {
687            elem.into_value().multi_encode_or_handle_err(output, h)?;
688        }
689        Ok(())
690    }
691}
692
693impl<SA, T, U> TypeAbiFrom<LinkedListMapper<SA, T>> for MultiValueEncoded<SA, U>
694where
695    SA: StorageMapperApi,
696    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
697    U: TypeAbiFrom<T>,
698{
699}
700
701impl<SA, T> TypeAbiFrom<Self> for LinkedListMapper<SA, T>
702where
703    SA: StorageMapperApi,
704    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
705{
706}
707
708impl<SA, T> TypeAbi for LinkedListMapper<SA, T>
709where
710    SA: StorageMapperApi,
711    T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + TypeAbi,
712{
713    type Unmanaged = Self;
714
715    fn type_name() -> TypeName {
716        crate::abi::type_name_variadic::<T>()
717    }
718
719    fn type_name_rust() -> TypeName {
720        crate::abi::type_name_multi_value_encoded::<T>()
721    }
722
723    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
724        T::provide_type_descriptions(accumulator);
725    }
726
727    fn is_variadic() -> bool {
728        true
729    }
730}
multiversx_sc/storage/mappers/linked_list_mapper.rs

multiversx_sc/storage/mappers/
linked_list_mapper.rs
