miden-crypto/src/merkle/tiered_smt/values.rs
src/merkle/tiered_smt/values.rsRaw
1use super::{get_key_prefix, BTreeMap, LeafNodeIndex, RpoDigest, StarkField, Vec, Word};
2use crate::utils::vec;
3use core::{
4 cmp::{Ord, Ordering},
5 ops::RangeBounds,
6};
7use winter_utils::collections::btree_map::Entry;
8
9// CONSTANTS
10// ================================================================================================
11
12/// Depths at which leaves can exist in a tiered SMT.
13const TIER_DEPTHS: [u8; 4] = super::TieredSmt::TIER_DEPTHS;
14
15/// Maximum node depth. This is also the bottom tier of the tree.
16const MAX_DEPTH: u8 = super::TieredSmt::MAX_DEPTH;
17
18// VALUE STORE
19// ================================================================================================
20/// A store for key-value pairs for a Tiered Sparse Merkle tree.
21///
22/// The store is organized in a [BTreeMap] where keys are 64 most significant bits of a key, and
23/// the values are the corresponding key-value pairs (or a list of key-value pairs if more that
24/// a single key-value pair shares the same 64-bit prefix).
25///
26/// The store supports lookup by the full key (i.e. [RpoDigest]) as well as by the 64-bit key
27/// prefix.
28#[derive(Debug, Default, Clone, PartialEq, Eq)]
29#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
30pub struct ValueStore {
31 values: BTreeMap<u64, StoreEntry>,
32}
33
34impl ValueStore {
35 // PUBLIC ACCESSORS
36 // --------------------------------------------------------------------------------------------
37
38 /// Returns a reference to the value stored under the specified key, or None if there is no
39 /// value associated with the specified key.
40 pub fn get(&self, key: &RpoDigest) -> Option<&Word> {
41 let prefix = get_key_prefix(key);
42 self.values.get(&prefix).and_then(|entry| entry.get(key))
43 }
44
45 /// Returns the first key-value pair such that the key prefix is greater than or equal to the
46 /// specified prefix.
47 pub fn get_first(&self, prefix: u64) -> Option<&(RpoDigest, Word)> {
48 self.range(prefix..).next()
49 }
50
51 /// Returns the first key-value pair such that the key prefix is greater than or equal to the
52 /// specified prefix and the key value is not equal to the exclude_key value.
53 pub fn get_first_filtered(
54 &self,
55 prefix: u64,
56 exclude_key: &RpoDigest,
57 ) -> Option<&(RpoDigest, Word)> {
58 self.range(prefix..).find(|(key, _)| key != exclude_key)
59 }
60
61 /// Returns a vector with key-value pairs for all keys with the specified 64-bit prefix, or
62 /// None if no keys with the specified prefix are present in this store.
63 pub fn get_all(&self, prefix: u64) -> Option<Vec<(RpoDigest, Word)>> {
64 self.values.get(&prefix).map(|entry| match entry {
65 StoreEntry::Single(kv_pair) => vec![*kv_pair],
66 StoreEntry::List(kv_pairs) => kv_pairs.clone(),
67 })
68 }
69
70 /// Returns information about a sibling of a leaf node with the specified index, but only if
71 /// this is the only sibling the leaf has in some subtree starting at the first tier.
72 ///
73 /// For example, if `index` is an index at depth 32, and there is a leaf node at depth 32 with
74 /// the same root at depth 16 as `index`, we say that this leaf is a lone sibling.
75 ///
76 /// The returned tuple contains: they key-value pair of the sibling as well as the index of
77 /// the node for the root of the common subtree in which both nodes are leaves.
78 ///
79 /// This method assumes that the key-value pair for the specified index has already been
80 /// removed from the store.
81 pub fn get_lone_sibling(
82 &self,
83 index: LeafNodeIndex,
84 ) -> Option<(&RpoDigest, &Word, LeafNodeIndex)> {
85 // iterate over tiers from top to bottom, looking at the tiers which are strictly above
86 // the depth of the index. This implies that only tiers at depth 32 and 48 will be
87 // considered. For each tier, check if the parent of the index at the higher tier
88 // contains a single node. The fist tier (depth 16) is excluded because we cannot move
89 // nodes at depth 16 to a higher tier. This implies that nodes at the first tier will
90 // never have "lone siblings".
91 for &tier_depth in TIER_DEPTHS.iter().filter(|&t| index.depth() > *t) {
92 // compute the index of the root at a higher tier
93 let mut parent_index = index;
94 parent_index.move_up_to(tier_depth);
95
96 // find the lone sibling, if any; we need to handle the "last node" at a given tier
97 // separately specify the bounds for the search correctly.
98 let start_prefix = parent_index.value() << (MAX_DEPTH - tier_depth);
99 let sibling = if start_prefix.leading_ones() as u8 == tier_depth {
100 let mut iter = self.range(start_prefix..);
101 iter.next().filter(|_| iter.next().is_none())
102 } else {
103 let end_prefix = (parent_index.value() + 1) << (MAX_DEPTH - tier_depth);
104 let mut iter = self.range(start_prefix..end_prefix);
105 iter.next().filter(|_| iter.next().is_none())
106 };
107
108 if let Some((key, value)) = sibling {
109 return Some((key, value, parent_index));
110 }
111 }
112
113 None
114 }
115
116 /// Returns an iterator over all key-value pairs in this store.
117 pub fn iter(&self) -> impl Iterator<Item = &(RpoDigest, Word)> {
118 self.values.iter().flat_map(|(_, entry)| entry.iter())
119 }
120
121 // STATE MUTATORS
122 // --------------------------------------------------------------------------------------------
123
124 /// Inserts the specified key-value pair into this store and returns the value previously
125 /// associated with the specified key.
126 ///
127 /// If no value was previously associated with the specified key, None is returned.
128 pub fn insert(&mut self, key: RpoDigest, value: Word) -> Option<Word> {
129 let prefix = get_key_prefix(&key);
130 match self.values.entry(prefix) {
131 Entry::Occupied(mut entry) => entry.get_mut().insert(key, value),
132 Entry::Vacant(entry) => {
133 entry.insert(StoreEntry::new(key, value));
134 None
135 }
136 }
137 }
138
139 /// Removes the key-value pair for the specified key from this store and returns the value
140 /// associated with this key.
141 ///
142 /// If no value was associated with the specified key, None is returned.
143 pub fn remove(&mut self, key: &RpoDigest) -> Option<Word> {
144 let prefix = get_key_prefix(key);
145 match self.values.entry(prefix) {
146 Entry::Occupied(mut entry) => {
147 let (value, remove_entry) = entry.get_mut().remove(key);
148 if remove_entry {
149 entry.remove_entry();
150 }
151 value
152 }
153 Entry::Vacant(_) => None,
154 }
155 }
156
157 // HELPER METHODS
158 // --------------------------------------------------------------------------------------------
159
160 /// Returns an iterator over all key-value pairs contained in this store such that the most
161 /// significant 64 bits of the key lay within the specified bounds.
162 ///
163 /// The order of iteration is from the smallest to the largest key.
164 fn range<R: RangeBounds<u64>>(&self, bounds: R) -> impl Iterator<Item = &(RpoDigest, Word)> {
165 self.values.range(bounds).flat_map(|(_, entry)| entry.iter())
166 }
167}
168
169// VALUE NODE
170// ================================================================================================
171
172/// An entry in the [ValueStore].
173///
174/// An entry can contain either a single key-value pair or a vector of key-value pairs sorted by
175/// key.
176#[derive(Debug, Clone, PartialEq, Eq)]
177#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
178pub enum StoreEntry {
179 Single((RpoDigest, Word)),
180 List(Vec<(RpoDigest, Word)>),
181}
182
183impl StoreEntry {
184 // CONSTRUCTOR
185 // --------------------------------------------------------------------------------------------
186 /// Returns a new [StoreEntry] instantiated with a single key-value pair.
187 pub fn new(key: RpoDigest, value: Word) -> Self {
188 Self::Single((key, value))
189 }
190
191 // PUBLIC ACCESSORS
192 // --------------------------------------------------------------------------------------------
193
194 /// Returns the value associated with the specified key, or None if this entry does not contain
195 /// a value associated with the specified key.
196 pub fn get(&self, key: &RpoDigest) -> Option<&Word> {
197 match self {
198 StoreEntry::Single(kv_pair) => {
199 if kv_pair.0 == *key {
200 Some(&kv_pair.1)
201 } else {
202 None
203 }
204 }
205 StoreEntry::List(kv_pairs) => {
206 match kv_pairs.binary_search_by(|kv_pair| cmp_digests(&kv_pair.0, key)) {
207 Ok(pos) => Some(&kv_pairs[pos].1),
208 Err(_) => None,
209 }
210 }
211 }
212 }
213
214 /// Returns an iterator over all key-value pairs in this entry.
215 pub fn iter(&self) -> impl Iterator<Item = &(RpoDigest, Word)> {
216 EntryIterator { entry: self, pos: 0 }
217 }
218
219 // STATE MUTATORS
220 // --------------------------------------------------------------------------------------------
221
222 /// Inserts the specified key-value pair into this entry and returns the value previously
223 /// associated with the specified key, or None if no value was associated with the specified
224 /// key.
225 ///
226 /// If a new key is inserted, this will also transform a `SingleEntry` into a `ListEntry`.
227 pub fn insert(&mut self, key: RpoDigest, value: Word) -> Option<Word> {
228 match self {
229 StoreEntry::Single(kv_pair) => {
230 // if the key is already in this entry, update the value and return
231 if kv_pair.0 == key {
232 let old_value = kv_pair.1;
233 kv_pair.1 = value;
234 return Some(old_value);
235 }
236
237 // transform the entry into a list entry, and make sure the key-value pairs
238 // are sorted by key
239 let mut pairs = vec![*kv_pair, (key, value)];
240 pairs.sort_by(|a, b| cmp_digests(&a.0, &b.0));
241
242 *self = StoreEntry::List(pairs);
243 None
244 }
245 StoreEntry::List(pairs) => {
246 match pairs.binary_search_by(|kv_pair| cmp_digests(&kv_pair.0, &key)) {
247 Ok(pos) => {
248 let old_value = pairs[pos].1;
249 pairs[pos].1 = value;
250 Some(old_value)
251 }
252 Err(pos) => {
253 pairs.insert(pos, (key, value));
254 None
255 }
256 }
257 }
258 }
259 }
260
261 /// Removes the key-value pair with the specified key from this entry, and returns the value
262 /// of the removed pair. If the entry did not contain a key-value pair for the specified key,
263 /// None is returned.
264 ///
265 /// If the last last key-value pair was removed from the entry, the second tuple value will
266 /// be set to true.
267 pub fn remove(&mut self, key: &RpoDigest) -> (Option<Word>, bool) {
268 match self {
269 StoreEntry::Single(kv_pair) => {
270 if kv_pair.0 == *key {
271 (Some(kv_pair.1), true)
272 } else {
273 (None, false)
274 }
275 }
276 StoreEntry::List(kv_pairs) => {
277 match kv_pairs.binary_search_by(|kv_pair| cmp_digests(&kv_pair.0, key)) {
278 Ok(pos) => {
279 let kv_pair = kv_pairs.remove(pos);
280 if kv_pairs.len() == 1 {
281 *self = StoreEntry::Single(kv_pairs[0]);
282 }
283 (Some(kv_pair.1), false)
284 }
285 Err(_) => (None, false),
286 }
287 }
288 }
289 }
290}
291
292/// A custom iterator over key-value pairs of a [StoreEntry].
293///
294/// For a `SingleEntry` this returns only one value, but for `ListEntry`, this iterates over the
295/// entire list of key-value pairs.
296pub struct EntryIterator<'a> {
297 entry: &'a StoreEntry,
298 pos: usize,
299}
300
301impl<'a> Iterator for EntryIterator<'a> {
302 type Item = &'a (RpoDigest, Word);
303
304 fn next(&mut self) -> Option<Self::Item> {
305 match self.entry {
306 StoreEntry::Single(kv_pair) => {
307 if self.pos == 0 {
308 self.pos = 1;
309 Some(kv_pair)
310 } else {
311 None
312 }
313 }
314 StoreEntry::List(kv_pairs) => {
315 if self.pos >= kv_pairs.len() {
316 None
317 } else {
318 let kv_pair = &kv_pairs[self.pos];
319 self.pos += 1;
320 Some(kv_pair)
321 }
322 }
323 }
324 }
325}
326
327// HELPER FUNCTIONS
328// ================================================================================================
329
330/// Compares two digests element-by-element using their integer representations starting with the
331/// most significant element.
332fn cmp_digests(d1: &RpoDigest, d2: &RpoDigest) -> Ordering {
333 let d1 = Word::from(d1);
334 let d2 = Word::from(d2);
335
336 for (v1, v2) in d1.iter().zip(d2.iter()).rev() {
337 let v1 = v1.as_int();
338 let v2 = v2.as_int();
339 if v1 != v2 {
340 return v1.cmp(&v2);
341 }
342 }
343
344 Ordering::Equal
345}
346
347// TESTS
348// ================================================================================================
349
350#[cfg(test)]
351mod tests {
352 use super::{LeafNodeIndex, RpoDigest, StoreEntry, ValueStore};
353 use crate::{Felt, ONE, WORD_SIZE, ZERO};
354
355 #[test]
356 fn test_insert() {
357 let mut store = ValueStore::default();
358
359 // insert the first key-value pair into the store
360 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
361 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
362 let value_a = [ONE; WORD_SIZE];
363
364 assert!(store.insert(key_a, value_a).is_none());
365 assert_eq!(store.values.len(), 1);
366
367 let entry = store.values.get(&raw_a).unwrap();
368 let expected_entry = StoreEntry::Single((key_a, value_a));
369 assert_eq!(entry, &expected_entry);
370
371 // insert a key-value pair with a different key into the store; since the keys are
372 // different, another entry is added to the values map
373 let raw_b = 0b_11111110_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
374 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
375 let value_b = [ONE, ZERO, ONE, ZERO];
376
377 assert!(store.insert(key_b, value_b).is_none());
378 assert_eq!(store.values.len(), 2);
379
380 let entry1 = store.values.get(&raw_a).unwrap();
381 let expected_entry1 = StoreEntry::Single((key_a, value_a));
382 assert_eq!(entry1, &expected_entry1);
383
384 let entry2 = store.values.get(&raw_b).unwrap();
385 let expected_entry2 = StoreEntry::Single((key_b, value_b));
386 assert_eq!(entry2, &expected_entry2);
387
388 // insert a key-value pair with the same 64-bit key prefix as the first key; this should
389 // transform the first entry into a List entry
390 let key_c = RpoDigest::from([ONE, ONE, ZERO, Felt::new(raw_a)]);
391 let value_c = [ONE, ONE, ZERO, ZERO];
392
393 assert!(store.insert(key_c, value_c).is_none());
394 assert_eq!(store.values.len(), 2);
395
396 let entry1 = store.values.get(&raw_a).unwrap();
397 let expected_entry1 = StoreEntry::List(vec![(key_c, value_c), (key_a, value_a)]);
398 assert_eq!(entry1, &expected_entry1);
399
400 let entry2 = store.values.get(&raw_b).unwrap();
401 let expected_entry2 = StoreEntry::Single((key_b, value_b));
402 assert_eq!(entry2, &expected_entry2);
403
404 // replace values for keys a and b
405 let value_a2 = [ONE, ONE, ONE, ZERO];
406 let value_b2 = [ZERO, ZERO, ZERO, ONE];
407
408 assert_eq!(store.insert(key_a, value_a2), Some(value_a));
409 assert_eq!(store.values.len(), 2);
410
411 assert_eq!(store.insert(key_b, value_b2), Some(value_b));
412 assert_eq!(store.values.len(), 2);
413
414 let entry1 = store.values.get(&raw_a).unwrap();
415 let expected_entry1 = StoreEntry::List(vec![(key_c, value_c), (key_a, value_a2)]);
416 assert_eq!(entry1, &expected_entry1);
417
418 let entry2 = store.values.get(&raw_b).unwrap();
419 let expected_entry2 = StoreEntry::Single((key_b, value_b2));
420 assert_eq!(entry2, &expected_entry2);
421
422 // insert one more key-value pair with the same 64-bit key-prefix as the first key
423 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
424 let value_d = [ZERO, ONE, ZERO, ZERO];
425
426 assert!(store.insert(key_d, value_d).is_none());
427 assert_eq!(store.values.len(), 2);
428
429 let entry1 = store.values.get(&raw_a).unwrap();
430 let expected_entry1 =
431 StoreEntry::List(vec![(key_c, value_c), (key_a, value_a2), (key_d, value_d)]);
432 assert_eq!(entry1, &expected_entry1);
433
434 let entry2 = store.values.get(&raw_b).unwrap();
435 let expected_entry2 = StoreEntry::Single((key_b, value_b2));
436 assert_eq!(entry2, &expected_entry2);
437 }
438
439 #[test]
440 fn test_remove() {
441 // populate the value store
442 let mut store = ValueStore::default();
443
444 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
445 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
446 let value_a = [ONE; WORD_SIZE];
447 store.insert(key_a, value_a);
448
449 let raw_b = 0b_11111110_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
450 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
451 let value_b = [ONE, ZERO, ONE, ZERO];
452 store.insert(key_b, value_b);
453
454 let key_c = RpoDigest::from([ONE, ONE, ZERO, Felt::new(raw_a)]);
455 let value_c = [ONE, ONE, ZERO, ZERO];
456 store.insert(key_c, value_c);
457
458 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
459 let value_d = [ZERO, ONE, ZERO, ZERO];
460 store.insert(key_d, value_d);
461
462 assert_eq!(store.values.len(), 2);
463
464 let entry1 = store.values.get(&raw_a).unwrap();
465 let expected_entry1 =
466 StoreEntry::List(vec![(key_c, value_c), (key_a, value_a), (key_d, value_d)]);
467 assert_eq!(entry1, &expected_entry1);
468
469 let entry2 = store.values.get(&raw_b).unwrap();
470 let expected_entry2 = StoreEntry::Single((key_b, value_b));
471 assert_eq!(entry2, &expected_entry2);
472
473 // remove non-existent keys
474 let key_e = RpoDigest::from([ZERO, ZERO, ONE, Felt::new(raw_a)]);
475 assert!(store.remove(&key_e).is_none());
476
477 let raw_f = 0b_11111110_11111111_00011111_11111111_10010110_10010011_11100000_00000000_u64;
478 let key_f = RpoDigest::from([ZERO, ZERO, ONE, Felt::new(raw_f)]);
479 assert!(store.remove(&key_f).is_none());
480
481 // remove keys from the list entry
482 assert_eq!(store.remove(&key_c).unwrap(), value_c);
483 let entry1 = store.values.get(&raw_a).unwrap();
484 let expected_entry1 = StoreEntry::List(vec![(key_a, value_a), (key_d, value_d)]);
485 assert_eq!(entry1, &expected_entry1);
486
487 assert_eq!(store.remove(&key_a).unwrap(), value_a);
488 let entry1 = store.values.get(&raw_a).unwrap();
489 let expected_entry1 = StoreEntry::Single((key_d, value_d));
490 assert_eq!(entry1, &expected_entry1);
491
492 assert_eq!(store.remove(&key_d).unwrap(), value_d);
493 assert!(store.values.get(&raw_a).is_none());
494 assert_eq!(store.values.len(), 1);
495
496 // remove a key from a single entry
497 assert_eq!(store.remove(&key_b).unwrap(), value_b);
498 assert!(store.values.get(&raw_b).is_none());
499 assert_eq!(store.values.len(), 0);
500 }
501
502 #[test]
503 fn test_range() {
504 // populate the value store
505 let mut store = ValueStore::default();
506
507 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
508 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
509 let value_a = [ONE; WORD_SIZE];
510 store.insert(key_a, value_a);
511
512 let raw_b = 0b_11111110_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
513 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
514 let value_b = [ONE, ZERO, ONE, ZERO];
515 store.insert(key_b, value_b);
516
517 let key_c = RpoDigest::from([ONE, ONE, ZERO, Felt::new(raw_a)]);
518 let value_c = [ONE, ONE, ZERO, ZERO];
519 store.insert(key_c, value_c);
520
521 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
522 let value_d = [ZERO, ONE, ZERO, ZERO];
523 store.insert(key_d, value_d);
524
525 let raw_e = 0b_10101000_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
526 let key_e = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_e)]);
527 let value_e = [ZERO, ZERO, ZERO, ONE];
528 store.insert(key_e, value_e);
529
530 // check the entire range
531 let mut iter = store.range(..u64::MAX);
532 assert_eq!(iter.next(), Some(&(key_e, value_e)));
533 assert_eq!(iter.next(), Some(&(key_c, value_c)));
534 assert_eq!(iter.next(), Some(&(key_a, value_a)));
535 assert_eq!(iter.next(), Some(&(key_d, value_d)));
536 assert_eq!(iter.next(), Some(&(key_b, value_b)));
537 assert_eq!(iter.next(), None);
538
539 // check all but e
540 let mut iter = store.range(raw_a..u64::MAX);
541 assert_eq!(iter.next(), Some(&(key_c, value_c)));
542 assert_eq!(iter.next(), Some(&(key_a, value_a)));
543 assert_eq!(iter.next(), Some(&(key_d, value_d)));
544 assert_eq!(iter.next(), Some(&(key_b, value_b)));
545 assert_eq!(iter.next(), None);
546
547 // check all but e and b
548 let mut iter = store.range(raw_a..raw_b);
549 assert_eq!(iter.next(), Some(&(key_c, value_c)));
550 assert_eq!(iter.next(), Some(&(key_a, value_a)));
551 assert_eq!(iter.next(), Some(&(key_d, value_d)));
552 assert_eq!(iter.next(), None);
553 }
554
555 #[test]
556 fn test_get_lone_sibling() {
557 // populate the value store
558 let mut store = ValueStore::default();
559
560 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
561 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
562 let value_a = [ONE; WORD_SIZE];
563 store.insert(key_a, value_a);
564
565 let raw_b = 0b_11111111_11111111_00011111_11111111_10010110_10010011_11100000_00000000_u64;
566 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
567 let value_b = [ONE, ZERO, ONE, ZERO];
568 store.insert(key_b, value_b);
569
570 // check sibling node for `a`
571 let index = LeafNodeIndex::make(32, 0b_10101010_10101010_00011111_11111110);
572 let parent_index = LeafNodeIndex::make(16, 0b_10101010_10101010);
573 assert_eq!(store.get_lone_sibling(index), Some((&key_a, &value_a, parent_index)));
574
575 // check sibling node for `b`
576 let index = LeafNodeIndex::make(32, 0b_11111111_11111111_00011111_11111111);
577 let parent_index = LeafNodeIndex::make(16, 0b_11111111_11111111);
578 assert_eq!(store.get_lone_sibling(index), Some((&key_b, &value_b, parent_index)));
579
580 // check some other sibling for some other index
581 let index = LeafNodeIndex::make(32, 0b_11101010_10101010);
582 assert_eq!(store.get_lone_sibling(index), None);
583 }
584}