trie_standardmap/
lib.rs

1// Copyright 2017, 2018 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Key-value datastore with a modified Merkle tree.
16
17use hash_db::Hasher;
18use keccak_hasher::KeccakHasher;
19
20type H256 = <KeccakHasher as hash_db::Hasher>::Out;
21
22/// Alphabet to use when creating words for insertion into tries.
23pub enum Alphabet {
24	/// All values are allowed in each bytes of the key.
25	All,
26	/// Only a 6 values ('a' - 'f') are chosen to compose the key.
27	Low,
28	/// Quite a few values (around 32) are chosen to compose the key.
29	Mid,
30	/// A set of bytes given is used to compose the key.
31	Custom(Vec<u8>),
32}
33
34/// Means of determining the value.
35pub enum ValueMode {
36	/// Same as the key.
37	Mirror,
38	/// Randomly (50:50) 1 or 32 byte randomly string.
39	Random,
40	/// RLP-encoded index.
41	Index,
42}
43
44/// Standard test map for profiling tries.
45pub struct StandardMap {
46	/// The alphabet to use for keys.
47	pub alphabet: Alphabet,
48	/// Minimum size of key.
49	pub min_key: usize,
50	/// Delta size of key.
51	pub journal_key: usize,
52	/// Mode of value generation.
53	pub value_mode: ValueMode,
54	/// Number of keys.
55	pub count: u32,
56}
57
58impl StandardMap {
59	/// Get a bunch of random bytes, at least `min_count` bytes, at most `min_count` +
60	/// `journal_count` bytes. `seed` is mutated pseudoramdonly and used.
61	fn random_bytes(min_count: usize, journal_count: usize, seed: &mut H256) -> Vec<u8> {
62		assert!(min_count + journal_count <= 32);
63		*seed = KeccakHasher::hash(&seed[..]);
64		let r = min_count + (seed[31] as usize % (journal_count + 1));
65		seed[0..r].to_vec()
66	}
67
68	/// Get a random value. Equal chance of being 1 byte as of 32. `seed` is mutated pseudoramdonly
69	/// and used.
70	fn random_value(seed: &mut H256) -> Vec<u8> {
71		*seed = KeccakHasher::hash(&seed[..]);
72		match seed[0] % 2 {
73			1 => vec![seed[31]; 1],
74			_ => seed.to_vec(),
75		}
76	}
77
78	/// Get a random word of, at least `min_count` bytes, at most `min_count` + `journal_count`
79	/// bytes. Each byte is an item from `alphabet`. `seed` is mutated pseudoramdonly and used.
80	fn random_word(
81		alphabet: &[u8],
82		min_count: usize,
83		journal_count: usize,
84		seed: &mut H256,
85	) -> Vec<u8> {
86		assert!(min_count + journal_count <= 32);
87		*seed = KeccakHasher::hash(&seed[..]);
88		let r = min_count + (seed[31] as usize % (journal_count + 1));
89		let mut ret: Vec<u8> = Vec::with_capacity(r);
90		for i in 0..r {
91			ret.push(alphabet[seed[i] as usize % alphabet.len()]);
92		}
93		ret
94	}
95
96	/// Create the standard map (set of keys and values) for the object's fields.
97	pub fn make(&self) -> Vec<(Vec<u8>, Vec<u8>)> {
98		self.make_with(&mut H256::default())
99	}
100
101	/// Create the standard map (set of keys and values) for the object's fields, using the given
102	/// seed.
103	pub fn make_with(&self, seed: &mut H256) -> Vec<(Vec<u8>, Vec<u8>)> {
104		let low = b"abcdef";
105		let mid = b"@QWERTYUIOPASDFGHJKLZXCVBNM[/]^_";
106
107		let mut d: Vec<(Vec<u8>, Vec<u8>)> = Vec::new();
108		for index in 0..self.count {
109			let k = match self.alphabet {
110				Alphabet::All => Self::random_bytes(self.min_key, self.journal_key, seed),
111				Alphabet::Low => Self::random_word(low, self.min_key, self.journal_key, seed),
112				Alphabet::Mid => Self::random_word(mid, self.min_key, self.journal_key, seed),
113				Alphabet::Custom(ref a) =>
114					Self::random_word(a, self.min_key, self.journal_key, seed),
115			};
116			let v = match self.value_mode {
117				ValueMode::Mirror => k.clone(),
118				ValueMode::Random => Self::random_value(seed),
119				ValueMode::Index =>
120					vec![index as u8, (index >> 8) as u8, (index >> 16) as u8, (index >> 24) as u8],
121			};
122			d.push((k, v))
123		}
124		d
125	}
126}
trie_standardmap/lib.rs

trie_standardmap/
lib.rs
