gear_common/storage/complicated/
dequeue.rs

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

gear_common/storage/complicated/
dequeue.rs
