stash.rs 9.55 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright 2018-2019 Parity Technologies (UK) Ltd.
// This file is part of pDSL.
//
// pDSL is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// pDSL is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with pDSL.  If not, see <http://www.gnu.org/licenses/>.

17
use crate::storage::{
18
	self,
19
20
	Key,
	chunk::SyncChunk,
21
	Allocator,
22
23
};

24
use parity_codec::{Encode, Decode};
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/// A stash collection.
///
/// Provides O(1) random insertion, deletion and access of its elements.
///
/// # Details
///
/// An `O(1)` amortized table that reuses keys.
///
/// ## Guarantees and non-guarantees:
///
/// 1. `Stash` is deterministic and keys do not depend on the inserted values.
///    This means you can update two stashes in tandem and get the same keys
///    back. This could be useful for, e.g., primary/secondary replication.
/// 2. Keys will always be less than the maximum number of items that have ever
///    been present in the `Stash` at any single point in time. In other words,
///    if you never store more than `n` items in a `Stash`, the stash will only
///    assign keys less than `n`. You can take advantage of this guarantee to
///    truncate the key from a `usize` to some smaller type.
/// 3. Except the guarantees noted above, you can assume nothing about key
///    assignment or iteration order. They can change at any time.
#[derive(Debug)]
pub struct Stash<T> {
	/// The latest vacant index.
49
	next_vacant: storage::Value<u32>,
50
51
52
53
54
55
	/// The number of items stored in the stash.
	///
	/// # Note
	///
	/// We cannot simply use the underlying length of the vector
	/// since it would include vacant slots as well.
56
	len: storage::Value<u32>,
Hero Bird's avatar
Hero Bird committed
57
	/// The maximum length the stash ever had.
58
	max_len: storage::Value<u32>,
59
60
61
62
	/// The entries of the stash.
	entries: SyncChunk<Entry<T>>,
}

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/// Iterator over the values of a stash.
#[derive(Debug)]
pub struct Values<'a, T> {
	/// The underlying iterator.
	iter: Iter<'a, T>,
}

impl<'a, T> Values<'a, T> {
	/// Creates a new iterator for the given storage stash.
	pub(crate) fn new(stash: &'a Stash<T>) -> Self {
		Self{iter: stash.iter()}
	}
}

impl<'a, T> Iterator for Values<'a, T>
where
	T: parity_codec::Codec
{
	type Item = &'a T;

	fn next(&mut self) -> Option<Self::Item> {
		self.iter.next().map(|(_index, value)| value)
	}

	fn size_hint(&self) -> (usize, Option<usize>) {
		self.iter.size_hint()
	}
}

impl<'a, T> ExactSizeIterator for Values<'a, T>
where
	T: parity_codec::Codec
{}

impl<'a, T> DoubleEndedIterator for Values<'a, T>
where
	T: parity_codec::Codec
{
	fn next_back(&mut self) -> Option<Self::Item> {
		self.iter.next_back().map(|(_index, value)| value)
	}
}

/// Iterator over the entries of a stash.
#[derive(Debug)]
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
pub struct Iter<'a, T> {
	/// The stash that is iterated over.
	stash: &'a Stash<T>,
	/// The index of the current start item of the iteration.
	begin: u32,
	/// The index of the current end item of the iteration.
	end: u32,
	/// The amount of already yielded items.
	///
	/// Required to offer an exact `size_hint` implementation.
	/// Also can be used to exit iteration as early as possible.
	yielded: u32,
}

impl<'a, T> Iter<'a, T> {
	/// Creates a new iterator for the given storage stash.
124
	pub(crate) fn new(stash: &'a Stash<T>) -> Self {
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
		Self{
			stash,
			begin: 0,
			end: stash.max_len(),
			yielded: 0,
		}
	}
}

impl<'a, T> Iterator for Iter<'a, T>
where
	T: parity_codec::Codec
{
	type Item = (u32, &'a T);

	fn next(&mut self) -> Option<Self::Item> {
		debug_assert!(self.begin <= self.end);
		if self.yielded == self.stash.len() {
			return None
		}
		while self.begin < self.end {
			let cur = self.begin;
			self.begin += 1;
			if let Some(elem) = self.stash.get(cur) {
				self.yielded += 1;
				return Some((cur, elem))
			}
		}
		None
	}

	fn size_hint(&self) -> (usize, Option<usize>) {
		let remaining = (self.stash.len() - self.yielded) as usize;
		(remaining, Some(remaining))
	}
}

162
163
164
165
166
impl<'a, T> ExactSizeIterator for Iter<'a, T>
where
	T: parity_codec::Codec
{}

167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
impl<'a, T> DoubleEndedIterator for Iter<'a, T>
where
	T: parity_codec::Codec
{
	fn next_back(&mut self) -> Option<Self::Item> {
		debug_assert!(self.begin <= self.end);
		if self.yielded == self.stash.len() {
			return None
		}
		while self.begin < self.end {
			self.end -= 1;
			if let Some(elem) = self.stash.get(self.end) {
				self.yielded += 1;
				return Some((self.end, elem))
			}
		}
		None
	}
}

187
188
189
190
191
192
193
194
195
196
197
198
199
/// An entry within a stash collection.
///
/// This represents either an occupied entry with its associated value
/// or a vacant entry pointing to the next vacant entry.
#[derive(Debug)]
#[derive(Encode, Decode)]
enum Entry<T> {
	/// A vacant entry pointing to the next vacant index.
	Vacant(u32),
	/// An occupied entry containing the value.
	Occupied(T),
}

200
201
202
203
impl<T> parity_codec::Encode for Stash<T> {
	fn encode_to<W: parity_codec::Output>(&self, dest: &mut W) {
		self.next_vacant.encode_to(dest);
		self.len.encode_to(dest);
Hero Bird's avatar
Hero Bird committed
204
		self.max_len.encode_to(dest);
205
206
207
208
209
210
		self.entries.encode_to(dest);
	}
}

impl<T> parity_codec::Decode for Stash<T> {
	fn decode<I: parity_codec::Input>(input: &mut I) -> Option<Self> {
211
212
213
		let next_vacant = storage::Value::decode(input)?;
		let len = storage::Value::decode(input)?;
		let max_len = storage::Value::decode(input)?;
214
		let entries = SyncChunk::decode(input)?;
Hero Bird's avatar
Hero Bird committed
215
		Some(Self{next_vacant, len, max_len, entries})
216
217
218
	}
}

219
impl<T> Stash<T> {
220
	/// Allocates a new storage stash using the given storage allocator.
221
222
223
224
225
226
227
228
229
230
	///
	/// # Safety
	///
	/// The is unsafe because it does not check if the associated storage
	/// does not alias with storage allocated by other storage allocators.
	pub unsafe fn new_using_alloc<A>(alloc: &mut A) -> Self
	where
		A: Allocator
	{
		Self{
231
232
233
			next_vacant: storage::Value::new_using_alloc(alloc, 0),
			len: storage::Value::new_using_alloc(alloc, 0),
			max_len: storage::Value::new_using_alloc(alloc, 0),
234
235
236
237
			entries: SyncChunk::new_using_alloc(alloc),
		}
	}

238
	/// Returns an iterator over the references of all entries of the stash.
239
240
241
242
243
244
245
246
247
248
	///
	/// # Note
	///
	/// - It is **not** recommended to iterate over all elements of a storage stash.
	/// - Try to avoid this if possible or iterate only over a minimal subset of
	///   all elements using e.g. `Iterator::take(n)`.
	pub fn iter(&self) -> Iter<T> {
		Iter::new(self)
	}

249
250
251
252
253
254
255
256
257
258
259
	/// Returns an iterator over the references of all values of the stash.
	///
	/// # Note
	///
	/// - It is **not** recommended to iterate over all elements of a storage stash.
	/// - Try to avoid this if possible or iterate only over a minimal subset of
	///   all elements using e.g. `Iterator::take(n)`.
	pub fn values(&self) -> Values<T> {
		Values::new(self)
	}

260
261
262
263
264
265
266
267
268
269
	/// Returns the unterlying key to the cells.
	///
	/// # Note
	///
	/// This is a low-level utility getter and should
	/// normally not be required by users.
	pub fn entries_key(&self) -> Key {
		self.entries.cells_key()
	}

270
271
	/// Returns the number of elements stored in the stash.
	pub fn len(&self) -> u32 {
272
		*self.len.get()
273
274
	}

Hero Bird's avatar
Hero Bird committed
275
276
277
	/// Returns the maximum number of element stored in the
	/// stash at the same time.
	pub fn max_len(&self) -> u32 {
278
		*self.max_len.get()
Hero Bird's avatar
Hero Bird committed
279
280
	}

281
282
283
284
285
286
287
	/// Returns `true` if the stash contains no elements.
	pub fn is_empty(&self) -> bool {
		self.len() == 0
	}

	/// Returns the next vacant index.
	fn next_vacant(&self) -> u32 {
288
		*self.next_vacant.get()
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
	}

}

impl<T> Stash<T>
where
	T: parity_codec::Codec,
{
	/// Returns the element stored at index `n` if any.
	pub fn get(&self, n: u32) -> Option<&T> {
		self
			.entries
			.get(n)
			.and_then(|entry| match entry {
				Entry::Occupied(val) => Some(val),
				Entry::Vacant(_) => None,
			})
	}

	/// Put the element into the stash at the next vacant position.
	///
	/// Returns the stash index that the element was put into.
	pub fn put(&mut self, val: T) -> u32 {
		let current_vacant = *self
			.next_vacant
314
			.get();
315
316
317
318
		debug_assert!(current_vacant <= self.len());
		if current_vacant == self.len() {
			self.entries.set(current_vacant, Entry::Occupied(val));
			self.next_vacant.set(current_vacant + 1);
Hero Bird's avatar
Hero Bird committed
319
			self.max_len.set(self.max_len() + 1);
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
		} else {
			let next_vacant = match
				self
					.entries
					.replace(current_vacant, Entry::Occupied(val))
					.expect(
						"[pdsl_core::Stash::put] Error: \
						expected a vacant entry here, but no entry was found"
					)
				{
					Entry::Vacant(next_vacant) => next_vacant,
					Entry::Occupied(_) => unreachable!(
						"[pdsl_core::Stash::put] Error: \
						a next_vacant index can never point to an occupied entry"
					)
				};
			self.next_vacant.set(next_vacant);
		}
		self.len.set(self.len() + 1);
		current_vacant
	}

	/// Takes the element stored at index `n`-th if any.
	pub fn take(&mut self, n: u32) -> Option<T> {
		match self.entries.get(n) {
			| None
			| Some(Entry::Vacant(_)) => None,
			| Some(Entry::Occupied(_)) => {
				match self.entries.replace(n, Entry::Vacant(self.next_vacant())).expect(
					"[pdsl_core::Stash::take] Error: \
					 we already asserted that the entry at `n` exists"
				) {
					Entry::Occupied(val) => {
						self.next_vacant.set(n);
						debug_assert!(self.len() >= 1);
						self.len.set(self.len() - 1);
						Some(val)
					},
					Entry::Vacant(_) => unreachable!(
						"[pdsl_core::Stash::take] Error: \
						 we already asserted that the entry is occupied"
					)
				}
			}
		}
	}
}