gear_common/storage/complicated/
dequeue.rs

1// This file is part of Gear.
2
3// Copyright (C) 2022-2025 Gear Technologies Inc.
4// SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0
5
6// This program is free software: you can redistribute it and/or modify
7// it under the terms of the GNU General Public License as published by
8// the Free Software Foundation, either version 3 of the License, or
9// (at your option) any later version.
10
11// This program is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License
17// along with this program. If not, see <https://www.gnu.org/licenses/>.
18
19//! Module for dequeue implementation.
20//!
21//! Dequeue based on dequeue implementation over key value map.
22//! This dequeue algorithm has main invariants:
23//! - If dequeue is empty, it's head and tail should be empty.
24//! - If dequeue contains the only one elements, is'ts head and tail
25//!   should equal this element's key.
26//! - Based on above specified points, head and tail should
27//!   both be set or be empty.
28//! - Inner map should contain values under keys, set in head and tail,
29//!   if they present.
30
31use crate::storage::{Callback, Counted, EmptyCallback, IterableMap, MapStorage, ValueStorage};
32use core::marker::PhantomData;
33use sp_runtime::{
34    codec::{self, Decode, Encode},
35    scale_info::{self, TypeInfo},
36};
37
38/// Represents dequeue implementation.
39pub trait Dequeue {
40    /// Dequeue's elements stored key.
41    type Key;
42    /// Dequeue's elements stored value.
43    type Value;
44    /// Dequeue error type.
45    type Error;
46
47    /// Mutates all stored value with given function.
48    fn mutate_values<F: FnMut(Self::Value) -> Self::Value>(f: F);
49
50    /// Removes and returns tail value of the dequeue, if present.
51    fn pop_back() -> Result<Option<Self::Value>, Self::Error>;
52
53    /// Removes and returns head value of the dequeue, if present.
54    fn pop_front() -> Result<Option<Self::Value>, Self::Error>;
55
56    /// Inserts value to the end of dequeue with given key.
57    fn push_back(key: Self::Key, value: Self::Value) -> Result<(), Self::Error>;
58
59    /// Inserts value to the beginning of dequeue with given key.
60    fn push_front(key: Self::Key, value: Self::Value) -> Result<(), Self::Error>;
61
62    /// Removes all values.
63    fn clear();
64}
65
66/// Represents store of dequeue's action callbacks.
67pub trait DequeueCallbacks {
68    /// Callback relative type.
69    ///
70    /// This value should be the main item of dequeue,
71    /// which uses this callbacks store.
72    type Value;
73
74    /// Callback on success `pop_back`.
75    type OnPopBack: Callback<Self::Value>;
76    /// Callback on success `pop_front`.
77    type OnPopFront: Callback<Self::Value>;
78    /// Callback on success `push_back`.
79    type OnPushBack: Callback<Self::Value>;
80    /// Callback on success `push_front`.
81    type OnPushFront: Callback<Self::Value>;
82    /// Callback on success `clear`.
83    type OnClear: EmptyCallback;
84}
85
86/// Represents dequeue error type.
87///
88/// Contains constructors for all existing errors.
89pub trait DequeueError {
90    /// Occurs when given key already exists in dequeue.
91    fn duplicate_key() -> Self;
92
93    /// Occurs when element wasn't found in storage.
94    fn element_not_found() -> Self;
95
96    /// Occurs when head should contain value,
97    /// but it's empty for some reason.
98    fn head_should_be_set() -> Self;
99
100    /// Occurs when head should be empty,
101    /// but it contains value for some reason.
102    fn head_should_not_be_set() -> Self;
103
104    /// Occurs when tail element of the dequeue
105    /// contains link to the next element.
106    fn tail_has_next_key() -> Self;
107
108    /// Occurs when while searching pre-tail,
109    /// element wasn't found.
110    fn tail_parent_not_found() -> Self;
111
112    /// Occurs when tail should contain value,
113    /// but it's empty for some reason.
114    fn tail_should_be_set() -> Self;
115
116    /// Occurs when tail should be empty,
117    /// but it contains value for some reason.
118    fn tail_should_not_be_set() -> Self;
119}
120
121/// `Dequeue` implementation based on `MapStorage` and `ValueStorage`s.
122///
123/// Generic parameters `Key` and `Value` specify data and keys for storing.
124/// Generic parameter `Error` requires `DequeueError` implementation.
125/// Generic parameter `Callbacks` presents actions for success operations
126/// over dequeue.
127pub struct DequeueImpl<Key, Value, Error, HVS, TVS, MS, Callbacks>(
128    PhantomData<(Error, HVS, TVS, MS, Callbacks)>,
129)
130where
131    Key: Clone + PartialEq,
132    Error: DequeueError,
133    HVS: ValueStorage<Value = Key>,
134    TVS: ValueStorage<Value = Key>,
135    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>,
136    Callbacks: DequeueCallbacks<Value = Value>;
137
138/// Represents node of the dequeue.
139///
140/// Contains value and link to the next node.
141#[derive(Encode, Decode, TypeInfo)]
142#[codec(crate = codec)]
143#[scale_info(crate = scale_info)]
144pub struct LinkedNode<K, V> {
145    /// Key of the next node of dequeue,
146    /// if present.
147    pub next: Option<K>,
148    /// Stored value of current node.
149    pub value: V,
150}
151
152// Implementation of `Counted` trait for `DequeueImpl` in case,
153// when inner `MapStorage` implements `Counted`.
154impl<Key, Value, Error, HVS, TVS, MS, Callbacks> Counted
155    for DequeueImpl<Key, Value, Error, HVS, TVS, MS, Callbacks>
156where
157    Key: Clone + PartialEq,
158    Error: DequeueError,
159    HVS: ValueStorage<Value = Key>,
160    TVS: ValueStorage<Value = Key>,
161    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>> + Counted,
162    Callbacks: DequeueCallbacks<Value = Value>,
163{
164    type Length = MS::Length;
165
166    fn len() -> Self::Length {
167        MS::len()
168    }
169}
170
171// Implementation of `Dequeue` for `DequeueImpl`.
172impl<Key, Value, Error, HVS, TVS, MS, Callbacks> Dequeue
173    for DequeueImpl<Key, Value, Error, HVS, TVS, MS, Callbacks>
174where
175    Key: Clone + PartialEq,
176    Error: DequeueError,
177    HVS: ValueStorage<Value = Key>,
178    TVS: ValueStorage<Value = Key>,
179    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>,
180    Callbacks: DequeueCallbacks<Value = Value>,
181{
182    type Key = Key;
183    type Value = Value;
184    type Error = Error;
185
186    fn mutate_values<F: FnMut(Self::Value) -> Self::Value>(mut f: F) {
187        MS::mutate_values(|n| LinkedNode {
188            next: n.next,
189            value: f(n.value),
190        })
191    }
192
193    /// Very expensive operation!
194    /// Use dequeue based on double linked list instead!
195    fn pop_back() -> Result<Option<Self::Value>, Self::Error> {
196        if let Some(head_key) = HVS::get() {
197            let tail_key = TVS::take().ok_or_else(Self::Error::tail_should_be_set)?;
198            let tail = MS::take(tail_key.clone()).ok_or_else(Self::Error::element_not_found)?;
199
200            let mut next_key = head_key;
201
202            loop {
203                let node = MS::get(&next_key).ok_or_else(Self::Error::element_not_found)?;
204
205                if let Some(nodes_next) = node.next {
206                    if nodes_next == tail_key {
207                        break;
208                    }
209
210                    next_key = nodes_next;
211                } else {
212                    return Err(Self::Error::tail_parent_not_found());
213                }
214            }
215
216            let mut node = MS::take(next_key.clone()).ok_or_else(Self::Error::element_not_found)?;
217
218            TVS::put(next_key.clone());
219
220            node.next = None;
221            MS::insert(next_key, node);
222
223            Callbacks::OnPopBack::call(&tail.value);
224            Ok(Some(tail.value))
225        } else if TVS::exists() {
226            Err(Self::Error::tail_should_not_be_set())
227        } else {
228            Ok(None)
229        }
230    }
231
232    fn pop_front() -> Result<Option<Self::Value>, Self::Error> {
233        if let Some(head_key) = HVS::take() {
234            let LinkedNode { next, value } =
235                MS::take(head_key).ok_or_else(Self::Error::element_not_found)?;
236
237            if let Some(next) = next {
238                HVS::put(next)
239            } else if TVS::take().is_none() {
240                return Err(Self::Error::tail_should_be_set());
241            }
242
243            Callbacks::OnPopFront::call(&value);
244            Ok(Some(value))
245        } else if TVS::exists() {
246            Err(Self::Error::tail_should_not_be_set())
247        } else {
248            Ok(None)
249        }
250    }
251
252    fn push_back(key: Self::Key, value: Self::Value) -> Result<(), Self::Error> {
253        if MS::contains_key(&key) {
254            Err(Self::Error::duplicate_key())
255        } else if let Some(tail_key) = TVS::take() {
256            if let Some(mut tail) = MS::take(tail_key.clone()) {
257                if tail.next.is_some() {
258                    Err(Self::Error::tail_has_next_key())
259                } else {
260                    TVS::put(key.clone());
261
262                    tail.next = Some(key.clone());
263                    MS::insert(tail_key, tail);
264
265                    Callbacks::OnPushBack::call(&value);
266                    MS::insert(key, LinkedNode { next: None, value });
267
268                    Ok(())
269                }
270            } else {
271                Err(Self::Error::element_not_found())
272            }
273        } else if HVS::exists() {
274            Err(Self::Error::head_should_not_be_set())
275        } else {
276            HVS::put(key.clone());
277            TVS::put(key.clone());
278
279            Callbacks::OnPushBack::call(&value);
280            MS::insert(key, LinkedNode { next: None, value });
281
282            Ok(())
283        }
284    }
285
286    fn push_front(key: Self::Key, value: Self::Value) -> Result<(), Self::Error> {
287        if MS::contains_key(&key) {
288            Err(Self::Error::duplicate_key())
289        } else if let Some(head_key) = HVS::take() {
290            HVS::put(key.clone());
291
292            Callbacks::OnPushFront::call(&value);
293            MS::insert(
294                key,
295                LinkedNode {
296                    next: Some(head_key),
297                    value,
298                },
299            );
300
301            Ok(())
302        } else if TVS::exists() {
303            Err(Self::Error::tail_should_not_be_set())
304        } else {
305            HVS::put(key.clone());
306            TVS::put(key.clone());
307
308            Callbacks::OnPushFront::call(&value);
309            MS::insert(key, LinkedNode { next: None, value });
310
311            Ok(())
312        }
313    }
314
315    fn clear() {
316        HVS::kill();
317        TVS::kill();
318        MS::clear();
319        Callbacks::OnClear::call();
320    }
321}
322
323/// Drain iterator over dequeue's values.
324///
325/// Removes element on each iteration.
326pub struct DequeueDrainIter<Key, Value, Error, HVS, TVS, MS, Callbacks>(
327    Option<Key>,
328    PhantomData<(Error, HVS, TVS, MS, Callbacks)>,
329)
330where
331    Key: Clone + PartialEq,
332    Error: DequeueError,
333    HVS: ValueStorage<Value = Key>,
334    TVS: ValueStorage<Value = Key>,
335    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>,
336    Callbacks: DequeueCallbacks<Value = Value>;
337
338// `Iterator` implementation for `DequeueDrainIter`.
339impl<Key, Value, Error, HVS, TVS, MS, Callbacks> Iterator
340    for DequeueDrainIter<Key, Value, Error, HVS, TVS, MS, Callbacks>
341where
342    Key: Clone + PartialEq,
343    Error: DequeueError,
344    HVS: ValueStorage<Value = Key>,
345    TVS: ValueStorage<Value = Key>,
346    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>,
347    Callbacks: DequeueCallbacks<Value = Value>,
348{
349    type Item = Result<Value, Error>;
350
351    fn next(&mut self) -> Option<Self::Item> {
352        let current = self.0.take()?;
353
354        if let Some(node) = MS::take(current) {
355            if let Some(k) = node.next.as_ref() {
356                HVS::put(k.clone())
357            }
358
359            self.0 = node.next;
360
361            Callbacks::OnPopFront::call(&node.value);
362            Some(Ok(node.value))
363        } else {
364            HVS::kill();
365            TVS::kill();
366            self.0 = None;
367
368            Some(Err(Error::element_not_found()))
369        }
370    }
371}
372
373/// Common iterator over dequeue's values.
374pub struct DequeueIter<Key, Value, Error, HVS, TVS, MS>(
375    Option<Key>,
376    PhantomData<(Error, HVS, TVS, MS)>,
377)
378where
379    Key: Clone + PartialEq,
380    Error: DequeueError,
381    HVS: ValueStorage<Value = Key>,
382    TVS: ValueStorage<Value = Key>,
383    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>;
384
385// `Iterator` implementation for `DequeueIter`.
386impl<Key, Value, Error, HVS, TVS, MS> Iterator for DequeueIter<Key, Value, Error, HVS, TVS, MS>
387where
388    Key: Clone + PartialEq,
389    Error: DequeueError,
390    HVS: ValueStorage<Value = Key>,
391    TVS: ValueStorage<Value = Key>,
392    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>,
393{
394    type Item = Result<Value, Error>;
395
396    fn next(&mut self) -> Option<Self::Item> {
397        let current = self.0.take()?;
398
399        if let Some(node) = MS::get(&current) {
400            self.0 = node.next;
401
402            Some(Ok(node.value))
403        } else {
404            self.0 = None;
405
406            Some(Err(Error::element_not_found()))
407        }
408    }
409}
410
411// `IterableMap` implementation for `DequeueImpl`, returning iterators,
412// presented with `DequeueIter` and `DequeueDrainIter`.
413impl<Key, Value, Error, HVS, TVS, MS, Callbacks> IterableMap<Result<Value, Error>>
414    for DequeueImpl<Key, Value, Error, HVS, TVS, MS, Callbacks>
415where
416    Key: Clone + PartialEq,
417    Error: DequeueError,
418    HVS: ValueStorage<Value = Key>,
419    TVS: ValueStorage<Value = Key>,
420    MS: MapStorage<Key = Key, Value = LinkedNode<Key, Value>>,
421    Callbacks: DequeueCallbacks<Value = Value>,
422{
423    type DrainIter = DequeueDrainIter<Key, Value, Error, HVS, TVS, MS, Callbacks>;
424    type Iter = DequeueIter<Key, Value, Error, HVS, TVS, MS>;
425
426    fn drain() -> Self::DrainIter {
427        DequeueDrainIter(HVS::get(), PhantomData::<(Error, HVS, TVS, MS, Callbacks)>)
428    }
429
430    fn iter() -> Self::Iter {
431        DequeueIter(HVS::get(), PhantomData::<(Error, HVS, TVS, MS)>)
432    }
433}
gear_common/storage/complicated/dequeue.rs

gear_common/storage/complicated/
dequeue.rs
