2888892874

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/google/OpenSK/commit/<a class=hub.com/google/OpenSK/commit/<a class="double-link" href="https://git"><a class=hub.com/google/OpenSK/commit/<a class="double-link" href="https://git"><a class=hub.com/google/OpenSK/commit/<a class="double-link" href="https://git"><a class=hub.com/google/OpenSK/commit/ef44f8f337c1dbe5249dee848b5cce3b1734c188">ef44f8f33">&lt;a href=&quot;https://github.com/google/OpenSK/commit/</a><a class="double-link" href="https://github.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/ef44f8f337c1dbe5249dee848b5cce3b1734c188">ef44f8f33</a><a href="https://github.com/google/OpenSK/commit/ef44f8f337c1dbe5249dee848b5cce3b1734c188">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/google/OpenSK/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/ef44f8f337c1dbe5249dee848b5cce3b1734c188&quot;&gt;ef44f8f33&lt;/a&gt;&lt;a href=&quot;https://github.com/google/OpenSK/commit/ef44f8f337c1dbe5249dee848b5cce3b1734c188&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/google/OpenSK/commit/&amp;lt;/a&amp;gt;&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://github.com/google/OpenSK/commit/&amp;amp;lt;a class=&amp;amp;quot;double-link&amp;amp;quot; href=&amp;amp;quot;htt... (continued)

Pull Request Pull Request #531: Add support for concatenated values

Run Details

70 of 70 new or added lines in 1 file covered. (100.0%)

14273 of 16166 relevant lines covered (88.29%)

516041.49 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/libraries/persistent_store/src/concat.rs

// Copyright 2022 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Support for concatenated entries.
//!
//! This module permits to store multiple indexed values under the same key by concatenation. Such
//! values must be at most 255 bytes and there can't be more than 255 such values under the same
//! key (they are indexed with a `u8`).
//!
//! The rationale for using those particular constraints is that we want the number of bits to store
//! the index and the number of bits to store the length to fit in an integer number of bytes
//! (because the values are an integer number of bytes). Using only one byte is too restrictive
//! (e.g. 8 values of at most 31 bytes or 16 values of at most 15 bytes). Using 2 bytes is plenty of
//! space, so using one byte for each field makes parsing simpler and faster.
//!
//! The format is thus `(index:u8 length:u8 payload:[u8; length])*`. The concatenation is not
//! particularly sorted.

use crate::{Storage, Store, StoreError, StoreResult};
use alloc::vec::Vec;
use core::cmp::Ordering;
use core::ops::Range;

/// Reads a value from a concatenated entry.
pub fn read(store: &Store<impl Storage>, key: usize, index: u8) -> StoreResult<Option<Vec<u8>>> {
    let values = match store.find(key)? {
        None => return Ok(None),
        Some(x) => x,
    };
    Ok(find(&values, index)?.map(|range| values[range].to_vec()))
}

/// Writes a value to a concatenated entry.
pub fn write(
    store: &mut Store<impl Storage>,
    key: usize,
    index: u8,
    value: &[u8],
) -> StoreResult<()> {
    if value.len() > 255 {
        return Err(StoreError::InvalidArgument);
    }
    let mut values = store.find(key)?.unwrap_or(vec![]);
    match find(&values, index)? {
        None => {
            values.push(index);
            values.push(value.len() as u8);
            values.extend_from_slice(value);
        }
        Some(mut range) => {
            values[range.start - 1] = value.len() as u8;
            match range.len().cmp(&value.len()) {
                Ordering::Less => {
                    let diff = value.len() - range.len();
                    values.resize(values.len() + diff, 0);
                    values[range.end..].rotate_right(diff);
                    range.end += diff;
                }
                Ordering::Equal => (),
                Ordering::Greater => {
                    let diff = range.len() - value.len();
                    range.end -= diff;
                    values[range.end..].rotate_left(diff);
                    values.truncate(values.len() - diff);
                }
            }
            values[range].copy_from_slice(value);
        }
    }
    store.insert(key, &values)
}

/// Deletes the value from a concatenated entry.
pub fn delete(store: &mut Store<impl Storage>, key: usize, index: u8) -> StoreResult<()> {
    let mut values = match store.find(key)? {
        None => return Ok(()),
        Some(x) => x,
    };
    let mut range = match find(&values, index)? {
        None => return Ok(()),
        Some(x) => x,
    };
    range.start -= 2;
    values[range.start..].rotate_left(range.len());
    values.truncate(values.len() - range.len());
    store.insert(key, &values)
}

fn find(values: &[u8], index: u8) -> StoreResult<Option<Range<usize>>> {
    let mut pos = 0;
    while pos < values.len() {
        if pos == values.len() - 1 {
            return Err(StoreError::InvalidStorage);
        }
        let len = values[pos + 1] as usize;
        if len > values.len() - 2 || pos > values.len() - 2 - len {
            return Err(StoreError::InvalidStorage);
        }
        if index == values[pos] {
            return Ok(Some(pos + 2..pos + 2 + len));
        }
        pos += 2 + len;
    }
    Ok(None)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::test::MINIMAL;

    #[test]
    fn read_empty_entry() {
        let store = MINIMAL.new_store();
        assert_eq!(read(&store, 0, 0), Ok(None));
        assert_eq!(read(&store, 0, 1), Ok(None));
    }

    #[test]
    fn read_missing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 1), Ok(None));
    }

    #[test]
    fn read_existing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 0), Ok(Some(b"foo".to_vec())));
        assert_eq!(read(&store, 0, 2), Ok(Some(b"hello".to_vec())));
    }

    #[test]
    fn read_invalid_entry_too_long() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x08hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
    }

    #[test]
    fn read_invalid_entry_too_short() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
    }

    #[test]
    fn write_empty_entry() {
        let mut store = MINIMAL.new_store();
        assert_eq!(write(&mut store, 0, 0, b"foo"), Ok(()));
        assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo".to_vec())));
    }

    #[test]
    fn write_missing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 1, b"bar"), Ok(()));
        assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo\x01\x03bar".to_vec())));
    }

    #[test]
    fn write_existing_value_same_size() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn write_existing_value_longer() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 0, b"barrage"), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x07barrage\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn write_existing_value_shorter() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x08football\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn delete_empty_entry() {
        let mut store = MINIMAL.new_store();
        assert_eq!(delete(&mut store, 0, 0), Ok(()));
        assert_eq!(delete(&mut store, 0, 1), Ok(()));
    }

    #[test]
    fn delete_missing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(delete(&mut store, 0, 1), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x03foo\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn delete_existing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(delete(&mut store, 0, 0), Ok(()));
        assert_eq!(store.find(0), Ok(Some(b"\x02\x05hello".to_vec())));
    }
}

1	// Copyright 2022 Google LLC
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	//! Support for concatenated entries.
16	//!
17	//! This module permits to store multiple indexed values under the same key by concatenation. Such
18	//! values must be at most 255 bytes and there can't be more than 255 such values under the same
19	//! key (they are indexed with a `u8`).
20	//!
21	//! The rationale for using those particular constraints is that we want the number of bits to store
22	//! the index and the number of bits to store the length to fit in an integer number of bytes
23	//! (because the values are an integer number of bytes). Using only one byte is too restrictive
24	//! (e.g. 8 values of at most 31 bytes or 16 values of at most 15 bytes). Using 2 bytes is plenty of
25	//! space, so using one byte for each field makes parsing simpler and faster.
26	//!
27	//! The format is thus `(index:u8 length:u8 payload:[u8; length])*`. The concatenation is not
28	//! particularly sorted.
29
30	use crate::{Storage, Store, StoreError, StoreResult};
31	use alloc::vec::Vec;
32	use core::cmp::Ordering;
33	use core::ops::Range;
34
35	/// Reads a value from a concatenated entry.
36	pub fn read(store: &Store<impl Storage>, key: usize, index: u8) -> StoreResult<Option<Vec<u8>>> {	×
37	let values = match store.find(key)? {	×
38	None => return Ok(None),	×
39	Some(x) => x,	×
40	};
41	Ok(find(&values, index)?.map(\|range\| values[range].to_vec()))	×
42	}	×
43
44	/// Writes a value to a concatenated entry.
45	pub fn write(	×
46	store: &mut Store<impl Storage>,	×
47	key: usize,	×
48	index: u8,	×
49	value: &[u8],	×
50	) -> StoreResult<()> {	×
51	if value.len() > 255 {	×
52	return Err(StoreError::InvalidArgument);	×
53	}	×
54	let mut values = store.find(key)?.unwrap_or(vec![]);	×
55	match find(&values, index)? {	×
56	None => {	×
57	values.push(index);	×
58	values.push(value.len() as u8);	×
59	values.extend_from_slice(value);	×
60	}	×
61	Some(mut range) => {	×
62	values[range.start - 1] = value.len() as u8;	×
63	match range.len().cmp(&value.len()) {	×
64	Ordering::Less => {	×
65	let diff = value.len() - range.len();	×
66	values.resize(values.len() + diff, 0);	×
67	values[range.end..].rotate_right(diff);	×
68	range.end += diff;	×
69	}	×
70	Ordering::Equal => (),	×
71	Ordering::Greater => {	×
72	let diff = range.len() - value.len();	×
73	range.end -= diff;	×
74	values[range.end..].rotate_left(diff);	×
75	values.truncate(values.len() - diff);	×
76	}	×
77	}
78	values[range].copy_from_slice(value);	×
79	}
80	}
81	store.insert(key, &values)	×
82	}	×
83
84	/// Deletes the value from a concatenated entry.
85	pub fn delete(store: &mut Store<impl Storage>, key: usize, index: u8) -> StoreResult<()> {	×
86	let mut values = match store.find(key)? {	×
87	None => return Ok(()),	×
88	Some(x) => x,	×
89	};
90	let mut range = match find(&values, index)? {	×
91	None => return Ok(()),	×
92	Some(x) => x,	×
93	};	×
94	range.start -= 2;	×
95	values[range.start..].rotate_left(range.len());	×
96	values.truncate(values.len() - range.len());	×
97	store.insert(key, &values)	×
98	}	×
99
100	fn find(values: &[u8], index: u8) -> StoreResult<Option<Range<usize>>> {	×
101	let mut pos = 0;	×
102	while pos < values.len() {	×
103	if pos == values.len() - 1 {	×
104	return Err(StoreError::InvalidStorage);	×
105	}	×
106	let len = values[pos + 1] as usize;	×
107	if len > values.len() - 2 \|\| pos > values.len() - 2 - len {	×
108	return Err(StoreError::InvalidStorage);	×
109	}	×
110	if index == values[pos] {	×
111	return Ok(Some(pos + 2..pos + 2 + len));	×
112	}	×
113	pos += 2 + len;	×
114	}
115	Ok(None)	×
116	}	×
117
118	#[cfg(test)]
119	mod tests {
120	use super::*;
121	use crate::test::MINIMAL;
122
123	#[test]
124	fn read_empty_entry() {
125	let store = MINIMAL.new_store();
126	assert_eq!(read(&store, 0, 0), Ok(None));
127	assert_eq!(read(&store, 0, 1), Ok(None));
128	}
129
130	#[test]
131	fn read_missing_value() {
132	let mut store = MINIMAL.new_store();
133	let value = b"\x00\x03foo\x02\x05hello".to_vec();
134	store.insert(0, &value).unwrap();
135	assert_eq!(read(&store, 0, 1), Ok(None));
136	}
137
138	#[test]
139	fn read_existing_value() {
140	let mut store = MINIMAL.new_store();
141	let value = b"\x00\x03foo\x02\x05hello".to_vec();
142	store.insert(0, &value).unwrap();
143	assert_eq!(read(&store, 0, 0), Ok(Some(b"foo".to_vec())));
144	assert_eq!(read(&store, 0, 2), Ok(Some(b"hello".to_vec())));
145	}
146
147	#[test]
148	fn read_invalid_entry_too_long() {
149	let mut store = MINIMAL.new_store();
150	let value = b"\x00\x03foo\x02\x08hello".to_vec();
151	store.insert(0, &value).unwrap();
152	assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
153	}
154
155	#[test]
156	fn read_invalid_entry_too_short() {
157	let mut store = MINIMAL.new_store();
158	let value = b"\x00\x03foo\x02".to_vec();
159	store.insert(0, &value).unwrap();
160	assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
161	}
162
163	#[test]
164	fn write_empty_entry() {
165	let mut store = MINIMAL.new_store();
166	assert_eq!(write(&mut store, 0, 0, b"foo"), Ok(()));
167	assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo".to_vec())));
168	}
169
170	#[test]
171	fn write_missing_value() {
172	let mut store = MINIMAL.new_store();
173	let value = b"\x00\x03foo".to_vec();
174	store.insert(0, &value).unwrap();
175	assert_eq!(write(&mut store, 0, 1, b"bar"), Ok(()));
176	assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo\x01\x03bar".to_vec())));
177	}
178
179	#[test]
180	fn write_existing_value_same_size() {
181	let mut store = MINIMAL.new_store();
182	let value = b"\x00\x03foo\x02\x05hello".to_vec();
183	store.insert(0, &value).unwrap();
184	assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
185	assert_eq!(
186	store.find(0),
187	Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
188	);
189	}
190
191	#[test]
192	fn write_existing_value_longer() {
193	let mut store = MINIMAL.new_store();
194	let value = b"\x00\x03foo\x02\x05hello".to_vec();
195	store.insert(0, &value).unwrap();
196	assert_eq!(write(&mut store, 0, 0, b"barrage"), Ok(()));
197	assert_eq!(
198	store.find(0),
199	Ok(Some(b"\x00\x07barrage\x02\x05hello".to_vec()))
200	);
201	}
202
203	#[test]
204	fn write_existing_value_shorter() {
205	let mut store = MINIMAL.new_store();
206	let value = b"\x00\x08football\x02\x05hello".to_vec();
207	store.insert(0, &value).unwrap();
208	assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
209	assert_eq!(
210	store.find(0),
211	Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
212	);
213	}
214
215	#[test]
216	fn delete_empty_entry() {
217	let mut store = MINIMAL.new_store();
218	assert_eq!(delete(&mut store, 0, 0), Ok(()));
219	assert_eq!(delete(&mut store, 0, 1), Ok(()));
220	}
221
222	#[test]
223	fn delete_missing_value() {
224	let mut store = MINIMAL.new_store();
225	let value = b"\x00\x03foo\x02\x05hello".to_vec();
226	store.insert(0, &value).unwrap();
227	assert_eq!(delete(&mut store, 0, 1), Ok(()));
228	assert_eq!(
229	store.find(0),
230	Ok(Some(b"\x00\x03foo\x02\x05hello".to_vec()))
231	);
232	}
233
234	#[test]
235	fn delete_existing_value() {
236	let mut store = MINIMAL.new_store();
237	let value = b"\x00\x03foo\x02\x05hello".to_vec();
238	store.insert(0, &value).unwrap();
239	assert_eq!(delete(&mut store, 0, 0), Ok(()));
240	assert_eq!(store.find(0), Ok(Some(b"\x02\x05hello".to_vec())));
241	}
242	}

google / OpenSK / 2888892874

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous