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