Struct pallet_paged_list::StoragePagedList
source · pub struct StoragePagedList<Prefix, Value, ValuesPerNewPage> { /* private fields */ }
Expand description
A paginated storage list.
Motivation
This type replaces StorageValue<Vec<V>>
in situations where only iteration and appending is
needed. There are a few places where this is the case. A paginated structure reduces the memory
usage when a storage transactions needs to be rolled back. The main motivation is therefore a
reduction of runtime memory on storage transaction rollback. Should be configured such that the
size of a page is about 64KiB. This can only be ensured when V
implements MaxEncodedLen
.
Implementation
The metadata of this struct is stored in [StoragePagedListMeta
]. The data is stored in
[Page
]s.
Each [Page
] holds at most ValuesPerNewPage
values in its values
vector. The last page is
the only one that could have less than ValuesPerNewPage
values.
Iteration happens by starting
at [first_page
][StoragePagedListMeta::first_page]/
[first_value_offset
][StoragePagedListMeta::first_value_offset] and incrementing these indices
as long as there are elements in the page and there are pages in storage. All elements of a page
are loaded once a page is read from storage. Iteration then happens on the cached elements. This
reduces the number of storage read
calls on the overlay. Appending to the list happens by
appending to the last page by utilizing sp_io::storage::append
. It allows to directly extend
the elements of values
vector of the page without loading the whole vector from storage. A new
page is instantiated once [Page::next
] overflows ValuesPerNewPage
. Its vector will also be
created through sp_io::storage::append
. Draining advances the internal indices identical
to Iteration. It additionally persists the increments to storage and thereby ‘drains’ elements.
Completely drained pages are deleted from storage.
Further Observations
- The encoded layout of a page is exactly its [
Page::values
]. The [Page::next
] offset is stored in the [StoragePagedListMeta
] instead. There is no particular reason for this, besides having all management state handy in one location. - The PoV complexity of iterating compared to a
StorageValue<Vec<V>>
is improved for “shortish” iterations and worse for total iteration. The append complexity is identical in the asymptotic case when using anAppender
, and worse in all. For example when appending just one value. - It does incur a read overhead on the host side as compared to a
StorageValue<Vec<V>>
.
Trait Implementations§
source§impl<Prefix, Value, ValuesPerNewPage> StorageList<Value> for StoragePagedList<Prefix, Value, ValuesPerNewPage>where
Prefix: StorageInstance,
Value: FullCodec,
ValuesPerNewPage: Get<u32>,
impl<Prefix, Value, ValuesPerNewPage> StorageList<Value> for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: StorageInstance, Value: FullCodec, ValuesPerNewPage: Get<u32>,
§type Iterator = StoragePagedListIterator<Prefix, Value, ValuesPerNewPage>
type Iterator = StoragePagedListIterator<Prefix, Value, ValuesPerNewPage>
§type Appender = StoragePagedListMeta<Prefix, Value, ValuesPerNewPage>
type Appender = StoragePagedListMeta<Prefix, Value, ValuesPerNewPage>
source§fn append_one<EncodeLikeValue>(item: EncodeLikeValue)where
EncodeLikeValue: EncodeLike<V>,
fn append_one<EncodeLikeValue>(item: EncodeLikeValue)where EncodeLikeValue: EncodeLike<V>,
source§fn append_many<EncodeLikeValue, I>(items: I)where
EncodeLikeValue: EncodeLike<V>,
I: IntoIterator<Item = EncodeLikeValue>,
fn append_many<EncodeLikeValue, I>(items: I)where EncodeLikeValue: EncodeLike<V>, I: IntoIterator<Item = EncodeLikeValue>,
source§impl<Prefix, Value, ValuesPerNewPage> StoragePrefixedContainer for StoragePagedList<Prefix, Value, ValuesPerNewPage>where
Prefix: StorageInstance,
Value: FullCodec,
ValuesPerNewPage: Get<u32>,
impl<Prefix, Value, ValuesPerNewPage> StoragePrefixedContainer for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: StorageInstance, Value: FullCodec, ValuesPerNewPage: Get<u32>,
source§fn module_prefix() -> &'static [u8] ⓘ
fn module_prefix() -> &'static [u8] ⓘ
source§fn storage_prefix() -> &'static [u8] ⓘ
fn storage_prefix() -> &'static [u8] ⓘ
source§fn final_prefix() -> [u8; 32]
fn final_prefix() -> [u8; 32]
Auto Trait Implementations§
impl<Prefix, Value, ValuesPerNewPage> RefUnwindSafe for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: RefUnwindSafe, Value: RefUnwindSafe, ValuesPerNewPage: RefUnwindSafe,
impl<Prefix, Value, ValuesPerNewPage> Send for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: Send, Value: Send, ValuesPerNewPage: Send,
impl<Prefix, Value, ValuesPerNewPage> Sync for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: Sync, Value: Sync, ValuesPerNewPage: Sync,
impl<Prefix, Value, ValuesPerNewPage> Unpin for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: Unpin, Value: Unpin, ValuesPerNewPage: Unpin,
impl<Prefix, Value, ValuesPerNewPage> UnwindSafe for StoragePagedList<Prefix, Value, ValuesPerNewPage>where Prefix: UnwindSafe, Value: UnwindSafe, ValuesPerNewPage: UnwindSafe,
Blanket Implementations§
source§impl<T> CheckedConversion for T
impl<T> CheckedConversion for T
source§impl<T> Instrument for T
impl<T> Instrument for T
source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T, Outer> IsWrappedBy<Outer> for Twhere
Outer: AsRef<T> + AsMut<T> + From<T>,
T: From<Outer>,
impl<T, Outer> IsWrappedBy<Outer> for Twhere Outer: AsRef<T> + AsMut<T> + From<T>, T: From<Outer>,
§impl<T> Pointable for T
impl<T> Pointable for T
source§impl<T> SaturatedConversion for T
impl<T> SaturatedConversion for T
source§fn saturated_from<T>(t: T) -> Selfwhere
Self: UniqueSaturatedFrom<T>,
fn saturated_from<T>(t: T) -> Selfwhere Self: UniqueSaturatedFrom<T>,
source§fn saturated_into<T>(self) -> Twhere
Self: UniqueSaturatedInto<T>,
fn saturated_into<T>(self) -> Twhere Self: UniqueSaturatedInto<T>,
T
. Read moresource§impl<S, T> UncheckedInto<T> for Swhere
T: UncheckedFrom<S>,
impl<S, T> UncheckedInto<T> for Swhere T: UncheckedFrom<S>,
source§fn unchecked_into(self) -> T
fn unchecked_into(self) -> T
unchecked_from
.source§impl<T, S> UniqueSaturatedInto<T> for Swhere
T: Bounded,
S: TryInto<T>,
impl<T, S> UniqueSaturatedInto<T> for Swhere T: Bounded, S: TryInto<T>,
source§fn unique_saturated_into(self) -> T
fn unique_saturated_into(self) -> T
T
.