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 {
217 entry: self,
218 pos: 0,
219 }
220 }
221
222 // STATE MUTATORS
223 // --------------------------------------------------------------------------------------------
224
225 /// Inserts the specified key-value pair into this entry and returns the value previously
226 /// associated with the specified key, or None if no value was associated with the specified
227 /// key.
228 ///
229 /// If a new key is inserted, this will also transform a `SingleEntry` into a `ListEntry`.
230 pub fn insert(&mut self, key: RpoDigest, value: Word) -> Option<Word> {
231 match self {
232 StoreEntry::Single(kv_pair) => {
233 // if the key is already in this entry, update the value and return
234 if kv_pair.0 == key {
235 let old_value = kv_pair.1;
236 kv_pair.1 = value;
237 return Some(old_value);
238 }
239
240 // transform the entry into a list entry, and make sure the key-value pairs
241 // are sorted by key
242 let mut pairs = vec![*kv_pair, (key, value)];
243 pairs.sort_by(|a, b| cmp_digests(&a.0, &b.0));
244
245 *self = StoreEntry::List(pairs);
246 None
247 }
248 StoreEntry::List(pairs) => {
249 match pairs.binary_search_by(|kv_pair| cmp_digests(&kv_pair.0, &key)) {
250 Ok(pos) => {
251 let old_value = pairs[pos].1;
252 pairs[pos].1 = value;
253 Some(old_value)
254 }
255 Err(pos) => {
256 pairs.insert(pos, (key, value));
257 None
258 }
259 }
260 }
261 }
262 }
263
264 /// Removes the key-value pair with the specified key from this entry, and returns the value
265 /// of the removed pair. If the entry did not contain a key-value pair for the specified key,
266 /// None is returned.
267 ///
268 /// If the last last key-value pair was removed from the entry, the second tuple value will
269 /// be set to true.
270 pub fn remove(&mut self, key: &RpoDigest) -> (Option<Word>, bool) {
271 match self {
272 StoreEntry::Single(kv_pair) => {
273 if kv_pair.0 == *key {
274 (Some(kv_pair.1), true)
275 } else {
276 (None, false)
277 }
278 }
279 StoreEntry::List(kv_pairs) => {
280 match kv_pairs.binary_search_by(|kv_pair| cmp_digests(&kv_pair.0, key)) {
281 Ok(pos) => {
282 let kv_pair = kv_pairs.remove(pos);
283 if kv_pairs.len() == 1 {
284 *self = StoreEntry::Single(kv_pairs[0]);
285 }
286 (Some(kv_pair.1), false)
287 }
288 Err(_) => (None, false),
289 }
290 }
291 }
292 }
293}
294
295/// A custom iterator over key-value pairs of a [StoreEntry].
296///
297/// For a `SingleEntry` this returns only one value, but for `ListEntry`, this iterates over the
298/// entire list of key-value pairs.
299pub struct EntryIterator<'a> {
300 entry: &'a StoreEntry,
301 pos: usize,
302}
303
304impl<'a> Iterator for EntryIterator<'a> {
305 type Item = &'a (RpoDigest, Word);
306
307 fn next(&mut self) -> Option<Self::Item> {
308 match self.entry {
309 StoreEntry::Single(kv_pair) => {
310 if self.pos == 0 {
311 self.pos = 1;
312 Some(kv_pair)
313 } else {
314 None
315 }
316 }
317 StoreEntry::List(kv_pairs) => {
318 if self.pos >= kv_pairs.len() {
319 None
320 } else {
321 let kv_pair = &kv_pairs[self.pos];
322 self.pos += 1;
323 Some(kv_pair)
324 }
325 }
326 }
327 }
328}
329
330// HELPER FUNCTIONS
331// ================================================================================================
332
333/// Compares two digests element-by-element using their integer representations starting with the
334/// most significant element.
335fn cmp_digests(d1: &RpoDigest, d2: &RpoDigest) -> Ordering {
336 let d1 = Word::from(d1);
337 let d2 = Word::from(d2);
338
339 for (v1, v2) in d1.iter().zip(d2.iter()).rev() {
340 let v1 = v1.as_int();
341 let v2 = v2.as_int();
342 if v1 != v2 {
343 return v1.cmp(&v2);
344 }
345 }
346
347 Ordering::Equal
348}
349
350// TESTS
351// ================================================================================================
352
353#[cfg(test)]
354mod tests {
355 use super::{LeafNodeIndex, RpoDigest, StoreEntry, ValueStore};
356 use crate::{Felt, ONE, WORD_SIZE, ZERO};
357
358 #[test]
359 fn test_insert() {
360 let mut store = ValueStore::default();
361
362 // insert the first key-value pair into the store
363 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
364 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
365 let value_a = [ONE; WORD_SIZE];
366
367 assert!(store.insert(key_a, value_a).is_none());
368 assert_eq!(store.values.len(), 1);
369
370 let entry = store.values.get(&raw_a).unwrap();
371 let expected_entry = StoreEntry::Single((key_a, value_a));
372 assert_eq!(entry, &expected_entry);
373
374 // insert a key-value pair with a different key into the store; since the keys are
375 // different, another entry is added to the values map
376 let raw_b = 0b_11111110_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
377 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
378 let value_b = [ONE, ZERO, ONE, ZERO];
379
380 assert!(store.insert(key_b, value_b).is_none());
381 assert_eq!(store.values.len(), 2);
382
383 let entry1 = store.values.get(&raw_a).unwrap();
384 let expected_entry1 = StoreEntry::Single((key_a, value_a));
385 assert_eq!(entry1, &expected_entry1);
386
387 let entry2 = store.values.get(&raw_b).unwrap();
388 let expected_entry2 = StoreEntry::Single((key_b, value_b));
389 assert_eq!(entry2, &expected_entry2);
390
391 // insert a key-value pair with the same 64-bit key prefix as the first key; this should
392 // transform the first entry into a List entry
393 let key_c = RpoDigest::from([ONE, ONE, ZERO, Felt::new(raw_a)]);
394 let value_c = [ONE, ONE, ZERO, ZERO];
395
396 assert!(store.insert(key_c, value_c).is_none());
397 assert_eq!(store.values.len(), 2);
398
399 let entry1 = store.values.get(&raw_a).unwrap();
400 let expected_entry1 = StoreEntry::List(vec![(key_c, value_c), (key_a, value_a)]);
401 assert_eq!(entry1, &expected_entry1);
402
403 let entry2 = store.values.get(&raw_b).unwrap();
404 let expected_entry2 = StoreEntry::Single((key_b, value_b));
405 assert_eq!(entry2, &expected_entry2);
406
407 // replace values for keys a and b
408 let value_a2 = [ONE, ONE, ONE, ZERO];
409 let value_b2 = [ZERO, ZERO, ZERO, ONE];
410
411 assert_eq!(store.insert(key_a, value_a2), Some(value_a));
412 assert_eq!(store.values.len(), 2);
413
414 assert_eq!(store.insert(key_b, value_b2), Some(value_b));
415 assert_eq!(store.values.len(), 2);
416
417 let entry1 = store.values.get(&raw_a).unwrap();
418 let expected_entry1 = StoreEntry::List(vec![(key_c, value_c), (key_a, value_a2)]);
419 assert_eq!(entry1, &expected_entry1);
420
421 let entry2 = store.values.get(&raw_b).unwrap();
422 let expected_entry2 = StoreEntry::Single((key_b, value_b2));
423 assert_eq!(entry2, &expected_entry2);
424
425 // insert one more key-value pair with the same 64-bit key-prefix as the first key
426 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
427 let value_d = [ZERO, ONE, ZERO, ZERO];
428
429 assert!(store.insert(key_d, value_d).is_none());
430 assert_eq!(store.values.len(), 2);
431
432 let entry1 = store.values.get(&raw_a).unwrap();
433 let expected_entry1 =
434 StoreEntry::List(vec![(key_c, value_c), (key_a, value_a2), (key_d, value_d)]);
435 assert_eq!(entry1, &expected_entry1);
436
437 let entry2 = store.values.get(&raw_b).unwrap();
438 let expected_entry2 = StoreEntry::Single((key_b, value_b2));
439 assert_eq!(entry2, &expected_entry2);
440 }
441
442 #[test]
443 fn test_remove() {
444 // populate the value store
445 let mut store = ValueStore::default();
446
447 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
448 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
449 let value_a = [ONE; WORD_SIZE];
450 store.insert(key_a, value_a);
451
452 let raw_b = 0b_11111110_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
453 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
454 let value_b = [ONE, ZERO, ONE, ZERO];
455 store.insert(key_b, value_b);
456
457 let key_c = RpoDigest::from([ONE, ONE, ZERO, Felt::new(raw_a)]);
458 let value_c = [ONE, ONE, ZERO, ZERO];
459 store.insert(key_c, value_c);
460
461 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
462 let value_d = [ZERO, ONE, ZERO, ZERO];
463 store.insert(key_d, value_d);
464
465 assert_eq!(store.values.len(), 2);
466
467 let entry1 = store.values.get(&raw_a).unwrap();
468 let expected_entry1 =
469 StoreEntry::List(vec![(key_c, value_c), (key_a, value_a), (key_d, value_d)]);
470 assert_eq!(entry1, &expected_entry1);
471
472 let entry2 = store.values.get(&raw_b).unwrap();
473 let expected_entry2 = StoreEntry::Single((key_b, value_b));
474 assert_eq!(entry2, &expected_entry2);
475
476 // remove non-existent keys
477 let key_e = RpoDigest::from([ZERO, ZERO, ONE, Felt::new(raw_a)]);
478 assert!(store.remove(&key_e).is_none());
479
480 let raw_f = 0b_11111110_11111111_00011111_11111111_10010110_10010011_11100000_00000000_u64;
481 let key_f = RpoDigest::from([ZERO, ZERO, ONE, Felt::new(raw_f)]);
482 assert!(store.remove(&key_f).is_none());
483
484 // remove keys from the list entry
485 assert_eq!(store.remove(&key_c).unwrap(), value_c);
486 let entry1 = store.values.get(&raw_a).unwrap();
487 let expected_entry1 = StoreEntry::List(vec![(key_a, value_a), (key_d, value_d)]);
488 assert_eq!(entry1, &expected_entry1);
489
490 assert_eq!(store.remove(&key_a).unwrap(), value_a);
491 let entry1 = store.values.get(&raw_a).unwrap();
492 let expected_entry1 = StoreEntry::Single((key_d, value_d));
493 assert_eq!(entry1, &expected_entry1);
494
495 assert_eq!(store.remove(&key_d).unwrap(), value_d);
496 assert!(store.values.get(&raw_a).is_none());
497 assert_eq!(store.values.len(), 1);
498
499 // remove a key from a single entry
500 assert_eq!(store.remove(&key_b).unwrap(), value_b);
501 assert!(store.values.get(&raw_b).is_none());
502 assert_eq!(store.values.len(), 0);
503 }
504
505 #[test]
506 fn test_range() {
507 // populate the value store
508 let mut store = ValueStore::default();
509
510 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
511 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
512 let value_a = [ONE; WORD_SIZE];
513 store.insert(key_a, value_a);
514
515 let raw_b = 0b_11111110_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
516 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
517 let value_b = [ONE, ZERO, ONE, ZERO];
518 store.insert(key_b, value_b);
519
520 let key_c = RpoDigest::from([ONE, ONE, ZERO, Felt::new(raw_a)]);
521 let value_c = [ONE, ONE, ZERO, ZERO];
522 store.insert(key_c, value_c);
523
524 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
525 let value_d = [ZERO, ONE, ZERO, ZERO];
526 store.insert(key_d, value_d);
527
528 let raw_e = 0b_10101000_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
529 let key_e = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_e)]);
530 let value_e = [ZERO, ZERO, ZERO, ONE];
531 store.insert(key_e, value_e);
532
533 // check the entire range
534 let mut iter = store.range(..u64::MAX);
535 assert_eq!(iter.next(), Some(&(key_e, value_e)));
536 assert_eq!(iter.next(), Some(&(key_c, value_c)));
537 assert_eq!(iter.next(), Some(&(key_a, value_a)));
538 assert_eq!(iter.next(), Some(&(key_d, value_d)));
539 assert_eq!(iter.next(), Some(&(key_b, value_b)));
540 assert_eq!(iter.next(), None);
541
542 // check all but e
543 let mut iter = store.range(raw_a..u64::MAX);
544 assert_eq!(iter.next(), Some(&(key_c, value_c)));
545 assert_eq!(iter.next(), Some(&(key_a, value_a)));
546 assert_eq!(iter.next(), Some(&(key_d, value_d)));
547 assert_eq!(iter.next(), Some(&(key_b, value_b)));
548 assert_eq!(iter.next(), None);
549
550 // check all but e and b
551 let mut iter = store.range(raw_a..raw_b);
552 assert_eq!(iter.next(), Some(&(key_c, value_c)));
553 assert_eq!(iter.next(), Some(&(key_a, value_a)));
554 assert_eq!(iter.next(), Some(&(key_d, value_d)));
555 assert_eq!(iter.next(), None);
556 }
557
558 #[test]
559 fn test_get_lone_sibling() {
560 // populate the value store
561 let mut store = ValueStore::default();
562
563 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
564 let key_a = RpoDigest::from([ZERO, ONE, ONE, Felt::new(raw_a)]);
565 let value_a = [ONE; WORD_SIZE];
566 store.insert(key_a, value_a);
567
568 let raw_b = 0b_11111111_11111111_00011111_11111111_10010110_10010011_11100000_00000000_u64;
569 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
570 let value_b = [ONE, ZERO, ONE, ZERO];
571 store.insert(key_b, value_b);
572
573 // check sibling node for `a`
574 let index = LeafNodeIndex::make(32, 0b_10101010_10101010_00011111_11111110);
575 let parent_index = LeafNodeIndex::make(16, 0b_10101010_10101010);
576 assert_eq!(store.get_lone_sibling(index), Some((&key_a, &value_a, parent_index)));
577
578 // check sibling node for `b`
579 let index = LeafNodeIndex::make(32, 0b_11111111_11111111_00011111_11111111);
580 let parent_index = LeafNodeIndex::make(16, 0b_11111111_11111111);
581 assert_eq!(store.get_lone_sibling(index), Some((&key_b, &value_b, parent_index)));
582
583 // check some other sibling for some other index
584 let index = LeafNodeIndex::make(32, 0b_11101010_10101010);
585 assert_eq!(store.get_lone_sibling(index), None);
586 }
587}