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
93pub struct LinkedListMapper<SA, T, A = CurrentStorage>
94where
95 SA: StorageMapperApi,
96 A: StorageAddress<SA>,
97 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
98{
99 _phantom_api: PhantomData<SA>,
100 address: A,
101 base_key: StorageKey<SA>,
102 _phantom_item: PhantomData<T>,
103}
104
105impl<SA, T> StorageMapper<SA> for LinkedListMapper<SA, T, CurrentStorage>
106where
107 SA: StorageMapperApi,
108 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
109{
110 fn new(base_key: StorageKey<SA>) -> Self {
111 LinkedListMapper {
112 _phantom_api: PhantomData,
113 address: CurrentStorage,
114 base_key,
115 _phantom_item: PhantomData,
116 }
117 }
118}
119
120impl<SA, T> StorageMapperFromAddress<SA> for LinkedListMapper<SA, T, ManagedAddress<SA>>
121where
122 SA: StorageMapperApi,
123 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
124{
125 fn new_from_address(address: ManagedAddress<SA>, base_key: StorageKey<SA>) -> Self {
126 LinkedListMapper {
127 _phantom_api: PhantomData,
128 address,
129 base_key,
130 _phantom_item: PhantomData,
131 }
132 }
133}
134
135impl<SA, T> StorageClearable for LinkedListMapper<SA, T>
136where
137 SA: StorageMapperApi,
138 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
139{
140 fn clear(&mut self) {
141 let info = self.get_info();
142 let mut node_id = info.front;
143
144 while node_id != NULL_ENTRY {
145 let node = self.get_node(node_id);
146 self.clear_node(node_id);
147 node_id = node.next_id;
148 }
149
150 self.set_info(LinkedListInfo::default());
151 }
152}
153
154impl<SA, T, A> LinkedListMapper<SA, T, A>
155where
156 SA: StorageMapperApi,
157 A: StorageAddress<SA>,
158 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
159{
160 fn build_node_id_named_key(&self, name: &[u8], node_id: u32) -> StorageKey<SA> {
161 let mut named_key = self.base_key.clone();
162 named_key.append_bytes(name);
163 named_key.append_item(&node_id);
164 named_key
165 }
166
167 fn build_name_key(&self, name: &[u8]) -> StorageKey<SA> {
168 let mut name_key = self.base_key.clone();
169 name_key.append_bytes(name);
170 name_key
171 }
172
173 fn get_info(&self) -> LinkedListInfo {
174 self.address
175 .address_storage_get(self.build_name_key(INFO_IDENTIFIER).as_ref())
176 }
177
178 fn get_node(&self, node_id: u32) -> LinkedListNode<T> {
179 self.address.address_storage_get(
180 self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
181 .as_ref(),
182 )
183 }
184
185 fn is_empty_node(&self, node_id: u32) -> bool {
186 self.address.address_storage_get_len(
187 self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
188 .as_ref(),
189 ) == 0
190 }
191
192 pub fn is_empty(&self) -> bool {
193 self.get_info().len == 0
194 }
195
196 pub fn len(&self) -> usize {
197 self.get_info().len as usize
198 }
199
200 pub fn front(&self) -> Option<LinkedListNode<T>> {
201 let info = self.get_info();
202
203 self.get_node_by_id(info.front)
204 }
205
206 pub fn back(&self) -> Option<LinkedListNode<T>> {
207 let info = self.get_info();
208
209 self.get_node_by_id(info.back)
210 }
211
212 pub fn get_node_by_id(&self, node_id: u32) -> Option<LinkedListNode<T>> {
213 if self.is_empty_node(node_id) {
214 return None;
215 }
216
217 Some(self.get_node(node_id))
218 }
219
220 pub fn iter(&self) -> Iter<'_, SA, T, A> {
221 Iter::new(self)
222 }
223
224 pub fn iter_from_node_id(&self, node_id: u32) -> Iter<'_, SA, T, A> {
225 Iter::new_from_node_id(self, node_id)
226 }
227
228 pub fn check_internal_consistency(&self) -> bool {
229 let info = self.get_info();
230 let mut front = info.front;
231 let mut back = info.back;
232
233 if info.len == 0 {
234 if front != NULL_ENTRY {
235 return false;
236 }
237 if back != NULL_ENTRY {
238 return false;
239 }
240 true
241 } else {
242 if front == NULL_ENTRY {
243 return false;
244 }
245 if back == NULL_ENTRY {
246 return false;
247 }
248
249 if self.get_node(front).prev_id != NULL_ENTRY {
250 return false;
251 }
252 if self.get_node(back).next_id != NULL_ENTRY {
253 return false;
254 }
255
256 let mut forwards = Vec::new();
257 while front != NULL_ENTRY {
258 forwards.push(front);
259 front = self.get_node(front).next_id;
260 }
261 if forwards.len() != info.len as usize {
262 return false;
263 }
264
265 let mut backwards = Vec::new();
266 while back != NULL_ENTRY {
267 backwards.push(back);
268 back = self.get_node(back).prev_id;
269 }
270 if backwards.len() != info.len as usize {
271 return false;
272 }
273
274 let backwards_reversed: Vec<u32> = backwards.iter().rev().cloned().collect();
275 if forwards != backwards_reversed {
276 return false;
277 }
278
279 forwards.sort_unstable();
280 forwards.dedup();
281 if forwards.len() != info.len as usize {
282 return false;
283 }
284 true
285 }
286 }
287}
288
289impl<SA, T> LinkedListMapper<SA, T, CurrentStorage>
290where
291 SA: StorageMapperApi,
292 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
293{
294 fn set_info(&mut self, value: LinkedListInfo) {
295 storage_set(self.build_name_key(INFO_IDENTIFIER).as_ref(), &value);
296 }
297
298 fn set_node(&mut self, node_id: u32, item: &LinkedListNode<T>) {
299 storage_set(
300 self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
301 .as_ref(),
302 item,
303 );
304 }
305
306 fn clear_node(&mut self, node_id: u32) {
307 storage_set(
308 self.build_node_id_named_key(NODE_IDENTIFIER, node_id)
309 .as_ref(),
310 &BoxedBytes::empty(),
311 );
312 }
313
314 pub fn pop_back(&mut self) -> Option<LinkedListNode<T>> {
315 let info = self.get_info();
316
317 self.remove_node_by_id(info.back)
318 }
319
320 pub fn pop_front(&mut self) -> Option<LinkedListNode<T>> {
321 let info = self.get_info();
322
323 self.remove_node_by_id(info.front)
324 }
325
326 pub fn push_after(
327 &mut self,
328 node: &mut LinkedListNode<T>,
329 element: T,
330 ) -> Option<LinkedListNode<T>> {
331 if self.is_empty_node(node.node_id) {
332 return None;
333 }
334
335 let mut info = self.get_info();
336 let new_node_id = info.generate_new_node_id();
337
338 let new_node_next_id = node.next_id;
339 node.next_id = new_node_id;
340 self.set_node(node.node_id, node);
341
342 if new_node_next_id == NULL_ENTRY {
343 info.back = new_node_id;
344 } else {
345 let mut next_node = self.get_node(new_node_next_id);
346 next_node.prev_id = new_node_id;
347 self.set_node(new_node_next_id, &next_node);
348 }
349
350 let new_node = LinkedListNode {
351 value: element,
352 node_id: new_node_id,
353 next_id: new_node_next_id,
354 prev_id: node.node_id,
355 };
356 self.set_node(new_node_id, &new_node);
357
358 info.len += 1;
359 self.set_info(info);
360 Some(new_node)
361 }
362
363 pub fn push_before(
364 &mut self,
365 node: &mut LinkedListNode<T>,
366 element: T,
367 ) -> Option<LinkedListNode<T>> {
368 if self.is_empty_node(node.node_id) {
369 return None;
370 }
371
372 let mut info = self.get_info();
373 let new_node_id = info.generate_new_node_id();
374
375 let new_node_prev_id = node.prev_id;
376 node.prev_id = new_node_id;
377 self.set_node(node.node_id, node);
378
379 if new_node_prev_id == NULL_ENTRY {
380 info.front = new_node_id;
381 } else {
382 let mut previous_node = self.get_node(new_node_prev_id);
383 previous_node.next_id = new_node_id;
384 self.set_node(new_node_prev_id, &previous_node);
385 }
386
387 let new_node = LinkedListNode {
388 value: element,
389 node_id: new_node_id,
390 next_id: node.node_id,
391 prev_id: new_node_prev_id,
392 };
393 self.set_node(new_node_id, &new_node);
394
395 info.len += 1;
396 self.set_info(info);
397 Some(new_node)
398 }
399
400 pub fn push_after_node_id(&mut self, node_id: u32, element: T) -> Option<LinkedListNode<T>> {
401 if !self.is_empty_node(node_id) {
402 let mut node = self.get_node(node_id);
403 self.push_after(&mut node, element)
404 } else {
405 None
406 }
407 }
408
409 pub fn push_before_node_id(&mut self, node_id: u32, element: T) -> Option<LinkedListNode<T>> {
410 if !self.is_empty_node(node_id) {
411 let mut node = self.get_node(node_id);
412 self.push_before(&mut node, element)
413 } else {
414 None
415 }
416 }
417
418 pub fn push_back(&mut self, element: T) -> LinkedListNode<T> {
419 let mut info = self.get_info();
420 let new_node_id = info.generate_new_node_id();
421 let mut previous = NULL_ENTRY;
422
423 if info.len == 0 {
424 info.front = new_node_id;
425 } else {
426 let back = info.back;
427 let mut back_node = self.get_node(back);
428 back_node.next_id = new_node_id;
429 previous = back;
430 self.set_node(back, &back_node);
431 }
432
433 let node = LinkedListNode {
434 value: element,
435 node_id: new_node_id,
436 prev_id: previous,
437 next_id: NULL_ENTRY,
438 };
439 self.set_node(new_node_id, &node);
440
441 info.back = new_node_id;
442 info.len += 1;
443 self.set_info(info);
444 node
445 }
446
447 pub fn push_front(&mut self, element: T) -> LinkedListNode<T> {
448 let mut info = self.get_info();
449 let new_node_id = info.generate_new_node_id();
450 let mut next = NULL_ENTRY;
451
452 if info.len == 0 {
453 info.back = new_node_id;
454 } else {
455 let front = info.front;
456 let mut front_node = self.get_node(front);
457 front_node.prev_id = new_node_id;
458 next = front;
459 self.set_node(front, &front_node);
460 }
461
462 let node = LinkedListNode {
463 value: element,
464 node_id: new_node_id,
465 prev_id: NULL_ENTRY,
466 next_id: next,
467 };
468 self.set_node(new_node_id, &node);
469
470 info.front = new_node_id;
471 info.len += 1;
472 self.set_info(info);
473 node
474 }
475
476 pub fn set_node_value(&mut self, mut node: LinkedListNode<T>, new_value: T) {
477 if self.is_empty_node(node.node_id) {
478 return;
479 }
480
481 node.value = new_value;
482 self.set_node(node.node_id, &node);
483 }
484
485 pub fn set_node_value_by_id(&mut self, node_id: u32, new_value: T) {
486 if let Some(node) = self.get_node_by_id(node_id) {
487 self.set_node_value(node, new_value)
488 }
489 }
490
491 pub fn remove_node(&mut self, node: &LinkedListNode<T>) {
492 let node_id = node.node_id;
493
494 if self.is_empty_node(node_id) {
495 return;
496 }
497
498 let mut info = self.get_info();
499 if node.prev_id == NULL_ENTRY {
500 info.front = node.next_id;
501 } else {
502 let mut previous = self.get_node(node.prev_id);
503 previous.next_id = node.next_id;
504 self.set_node(node.prev_id, &previous);
505 }
506
507 if node.next_id == NULL_ENTRY {
508 info.back = node.prev_id;
509 } else {
510 let mut next = self.get_node(node.next_id);
511 next.prev_id = node.prev_id;
512 self.set_node(node.next_id, &next);
513 }
514
515 self.clear_node(node_id);
516 info.len -= 1;
517 self.set_info(info);
518 }
519
520 pub fn remove_node_by_id(&mut self, node_id: u32) -> Option<LinkedListNode<T>> {
521 if self.is_empty_node(node_id) {
522 return None;
523 }
524
525 let node = self.get_node_by_id(node_id).unwrap();
526 self.remove_node(&node);
527 Some(node)
528 }
529}
530
531impl<'a, SA, T, A> IntoIterator for &'a LinkedListMapper<SA, T, A>
532where
533 SA: StorageMapperApi,
534 A: StorageAddress<SA>,
535 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
536{
537 type Item = LinkedListNode<T>;
538
539 type IntoIter = Iter<'a, SA, T, A>;
540
541 fn into_iter(self) -> Self::IntoIter {
542 self.iter()
543 }
544}
545
546pub struct Iter<'a, SA, T, A>
547where
548 SA: StorageMapperApi,
549 A: StorageAddress<SA>,
550 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
551{
552 node_opt: Option<LinkedListNode<T>>,
553 linked_list: &'a LinkedListMapper<SA, T, A>,
554}
555
556impl<'a, SA, T, A> Iter<'a, SA, T, A>
557where
558 SA: StorageMapperApi,
559 A: StorageAddress<SA>,
560 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
561{
562 fn new(linked_list: &'a LinkedListMapper<SA, T, A>) -> Iter<'a, SA, T, A> {
563 Iter {
564 node_opt: linked_list.front(),
565 linked_list,
566 }
567 }
568
569 fn new_from_node_id(
570 linked_list: &'a LinkedListMapper<SA, T, A>,
571 node_id: u32,
572 ) -> Iter<'a, SA, T, A> {
573 Iter {
574 node_opt: linked_list.get_node_by_id(node_id),
575 linked_list,
576 }
577 }
578}
579
580impl<SA, T, A> Iterator for Iter<'_, SA, T, A>
581where
582 SA: StorageMapperApi,
583 A: StorageAddress<SA>,
584 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + 'static,
585{
586 type Item = LinkedListNode<T>;
587
588 #[inline]
589 fn next(&mut self) -> Option<LinkedListNode<T>> {
590 self.node_opt.as_ref()?;
591 let node = self.node_opt.clone().unwrap();
592 self.node_opt = self.linked_list.get_node_by_id(node.next_id);
593 Some(node)
594 }
595}
596
597impl<SA, T> TopEncodeMulti for LinkedListMapper<SA, T>
598where
599 SA: StorageMapperApi,
600 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
601{
602 fn multi_encode_or_handle_err<O, H>(&self, output: &mut O, h: H) -> Result<(), H::HandledErr>
603 where
604 O: TopEncodeMultiOutput,
605 H: EncodeErrorHandler,
606 {
607 for elem in self.iter() {
608 elem.into_value().multi_encode_or_handle_err(output, h)?;
609 }
610 Ok(())
611 }
612}
613
614impl<SA, T, U> TypeAbiFrom<LinkedListMapper<SA, T>> for MultiValueEncoded<SA, U>
615where
616 SA: StorageMapperApi,
617 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
618 U: TypeAbiFrom<T>,
619{
620}
621
622impl<SA, T> TypeAbiFrom<Self> for LinkedListMapper<SA, T>
623where
624 SA: StorageMapperApi,
625 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone,
626{
627}
628
629impl<SA, T> TypeAbi for LinkedListMapper<SA, T>
630where
631 SA: StorageMapperApi,
632 T: TopEncode + TopDecode + NestedEncode + NestedDecode + Clone + TypeAbi,
633{
634 type Unmanaged = Self;
635
636 fn type_name() -> TypeName {
637 crate::abi::type_name_variadic::<T>()
638 }
639
640 fn type_name_rust() -> TypeName {
641 crate::abi::type_name_multi_value_encoded::<T>()
642 }
643
644 fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
645 T::provide_type_descriptions(accumulator);
646 }
647
648 fn is_variadic() -> bool {
649 true
650 }
651}