cfx_storage/impls/merkle_patricia_trie/
children_table.rs

1// Copyright 2019 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5pub trait NodeRefTrait:
6    Copy + Clone + Encodable + Decodable + PartialEq + Debug
7{
8}
9
10impl NodeRefTrait for MerkleHash {}
11
12#[derive(Clone, Debug, PartialEq, MallocSizeOfDerive)]
13pub struct VanillaChildrenTable<NodeRefT: NodeRefTrait> {
14    table: [NodeRefT; CHILDREN_COUNT],
15    // TODO(yz): Use bitmap to save space for rlp format.
16    // TODO(yz): the proof format may differ.
17    children_count: u8,
18}
19
20impl From<ChildrenMerkleTable> for VanillaChildrenTable<MerkleHash> {
21    fn from(x: ChildrenMerkleTable) -> Self {
22        let mut children_count = 0;
23        for merkle in &x {
24            if !merkle.eq(ChildrenTableItem::<MerkleHash>::no_child()) {
25                children_count += 1;
26            }
27        }
28        Self {
29            table: x,
30            children_count,
31        }
32    }
33}
34
35impl From<MaybeMerkleTable> for VanillaChildrenTable<MerkleHash> {
36    fn from(x: MaybeMerkleTable) -> Self {
37        match x {
38            None => Self::default(),
39            Some(t) => t.into(),
40        }
41    }
42}
43
44pub trait DefaultChildrenItem<NodeRefT: NodeRefTrait> {
45    fn no_child() -> &'static NodeRefT;
46}
47
48pub struct ChildrenTableItem<NodeRefT: NodeRefTrait> {
49    _marker: PhantomData<NodeRefT>,
50}
51
52impl DefaultChildrenItem<MerkleHash> for ChildrenTableItem<MerkleHash> {
53    fn no_child() -> &'static MerkleHash { &MERKLE_NULL_NODE }
54}
55
56impl<NodeRefT: NodeRefTrait> WrappedCreateFrom<NodeRefT, NodeRefT>
57    for ChildrenTableItem<NodeRefT>
58{
59    fn take(x: NodeRefT) -> NodeRefT { x }
60}
61
62impl<'x, NodeRefT: NodeRefTrait> WrappedCreateFrom<&'x NodeRefT, NodeRefT>
63    for ChildrenTableItem<NodeRefT>
64{
65    fn take(x: &'x NodeRefT) -> NodeRefT { x.clone() }
66
67    fn take_from(dest: &mut NodeRefT, x: &'x NodeRefT) { dest.clone_from(x); }
68}
69
70impl<NodeRefT: 'static + NodeRefTrait> Default
71    for VanillaChildrenTable<NodeRefT>
72where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT>
73{
74    fn default() -> Self {
75        Self {
76            children_count: 0,
77            table: [ChildrenTableItem::<NodeRefT>::no_child().clone();
78                CHILDREN_COUNT],
79        }
80    }
81}
82
83impl<NodeRefT: 'static + NodeRefTrait> VanillaChildrenTable<NodeRefT> {
84    // FIXME: put most method in a trait.
85
86    pub fn new_from_one_child(child_index: u8, child: &NodeRefT) -> Self
87    where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT> {
88        let mut table = VanillaChildrenTable::default();
89        table.children_count = 1;
90        table.table[child_index as usize] = child.clone();
91        table
92    }
93
94    pub fn get_children_table(&self) -> &[NodeRefT; CHILDREN_COUNT] {
95        &self.table
96    }
97
98    pub fn get_children_count(&self) -> u8 { self.children_count }
99
100    pub unsafe fn get_children_count_mut(&mut self) -> &mut u8 {
101        &mut self.children_count
102    }
103
104    pub fn get_child(&self, child_index: u8) -> Option<&NodeRefT>
105    where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT> {
106        let child_ref =
107            unsafe { self.table.get_unchecked(child_index as usize) };
108        if child_ref.eq(ChildrenTableItem::<NodeRefT>::no_child()) {
109            None
110        } else {
111            Some(child_ref)
112        }
113    }
114
115    pub unsafe fn get_child_mut_unchecked(
116        &mut self, child_index: u8,
117    ) -> &mut NodeRefT {
118        self.table.get_unchecked_mut(child_index as usize)
119    }
120
121    pub fn iter(&self) -> VanillaChildrenTableIterator<'_, NodeRefT> {
122        VanillaChildrenTableIterator {
123            next_child_index: 0,
124            table: &self.table,
125        }
126    }
127}
128
129// TODO(yz): Use bitmap to save space for rlp format.
130// TODO(yz): the proof format may differ.
131impl<NodeRefT: 'static + NodeRefTrait> Encodable
132    for VanillaChildrenTable<NodeRefT>
133where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT>
134{
135    fn rlp_append(&self, s: &mut RlpStream) {
136        if self.children_count == 0 {
137            s.begin_list(0);
138        } else {
139            s.append_list(&self.table[..]);
140        };
141    }
142}
143
144impl<NodeRefT: 'static + NodeRefTrait> Decodable
145    for VanillaChildrenTable<NodeRefT>
146where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT>
147{
148    fn decode(rlp: &Rlp) -> std::result::Result<Self, DecoderError> {
149        if rlp.is_empty() {
150            Ok(Default::default())
151        } else {
152            let mut table_uninit: MaybeUninit<[NodeRefT; CHILDREN_COUNT]> =
153                MaybeUninit::uninit();
154            let table = unsafe { &mut *table_uninit.as_mut_ptr() };
155            let mut children_count = 0;
156            for i in 0..16 {
157                (*table)[i] = rlp.val_at::<NodeRefT>(i)?;
158                if !(*table)[i].eq(ChildrenTableItem::<NodeRefT>::no_child()) {
159                    children_count += 1;
160                }
161            }
162
163            Ok(VanillaChildrenTable {
164                table: unsafe { table_uninit.assume_init() },
165                children_count,
166            })
167        }
168    }
169}
170
171impl<NodeRefT: NodeRefTrait + Serialize> Serialize
172    for VanillaChildrenTable<NodeRefT>
173{
174    fn serialize<S>(
175        &self, serializer: S,
176    ) -> std::result::Result<S::Ok, S::Error>
177    where S: Serializer {
178        let seq = if self.children_count == 0 {
179            serializer.serialize_seq(Some(0))?
180        } else {
181            let mut seq = serializer.serialize_seq(Some(self.table.len()))?;
182            for element in self.table.iter() {
183                seq.serialize_element(element)?;
184            }
185            seq
186        };
187
188        seq.end()
189    }
190}
191
192impl<'a, NodeRefT: 'static + NodeRefTrait + Deserialize<'a>> Deserialize<'a>
193    for VanillaChildrenTable<NodeRefT>
194where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT>
195{
196    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
197    where D: Deserializer<'a> {
198        let nodes: Vec<NodeRefT> = Deserialize::deserialize(deserializer)?;
199
200        if nodes.len() == 0 {
201            Ok(Default::default())
202        } else {
203            let mut table_uninit: MaybeUninit<[NodeRefT; CHILDREN_COUNT]> =
204                MaybeUninit::uninit();
205            let table = unsafe { &mut *table_uninit.as_mut_ptr() };
206            let mut children_count = 0;
207            for i in 0..16 {
208                (*table)[i] = nodes[i];
209                if !(*table)[i].eq(ChildrenTableItem::<NodeRefT>::no_child()) {
210                    children_count += 1;
211                }
212            }
213
214            Ok(VanillaChildrenTable {
215                table: unsafe { table_uninit.assume_init() },
216                children_count,
217            })
218        }
219    }
220}
221
222pub struct VanillaChildrenTableIterator<'a, NodeRefT: NodeRefTrait> {
223    next_child_index: u8,
224    table: &'a [NodeRefT; CHILDREN_COUNT],
225}
226
227impl<'a, NodeRefT: 'static + NodeRefTrait> Iterator
228    for VanillaChildrenTableIterator<'a, NodeRefT>
229where ChildrenTableItem<NodeRefT>: DefaultChildrenItem<NodeRefT>
230{
231    type Item = (u8, &'a NodeRefT);
232
233    fn next(&mut self) -> Option<Self::Item> {
234        while (self.next_child_index as usize) < CHILDREN_COUNT {
235            let child_index = self.next_child_index;
236            let child_ref = unsafe {
237                self.table.get_unchecked(self.next_child_index as usize)
238            };
239            self.next_child_index = child_index + 1;
240            if !child_ref.eq(ChildrenTableItem::<NodeRefT>::no_child()) {
241                return Some((child_index, child_ref));
242            }
243        }
244        None
245    }
246}
247
248impl<'a, NodeRefT: NodeRefTrait> ChildrenTableIteratorStartIndex
249    for VanillaChildrenTableIterator<'a, NodeRefT>
250{
251    fn set_start_index(mut self, index: u8) -> Self {
252        self.next_child_index = index;
253        self
254    }
255}
256
257/// NodeRefT for delta MPT and persistent MPT can be different.
258pub struct CompactedChildrenTable<NodeRefT: NodeRefTrait> {
259    /// Stores whether each child exists.
260    bitmap: u16,
261    /// Stores the number of children in children table.
262    children_count: u8,
263    /// Stores the existing children ordered.
264    table_ptr: *mut NodeRefT,
265}
266
267impl<NodeRefT: NodeRefTrait> MallocSizeOf for CompactedChildrenTable<NodeRefT> {
268    fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
269        // `table_ptr` is either null or from Vec
270        unsafe { ops.malloc_size_of(self.table_ptr) }
271    }
272}
273
274pub const CHILDREN_COUNT: usize = 16;
275
276impl<NodeRefT: NodeRefTrait> Default for CompactedChildrenTable<NodeRefT> {
277    fn default() -> Self {
278        Self {
279            bitmap: 0,
280            children_count: 0,
281            table_ptr: null_mut(),
282        }
283    }
284}
285
286impl<NodeRefT: NodeRefTrait> Clone for CompactedChildrenTable<NodeRefT> {
287    fn clone(&self) -> Self { self.to_ref().into() }
288}
289
290impl<NodeRefT: NodeRefTrait> Debug for CompactedChildrenTable<NodeRefT> {
291    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
292        write!(f, "ChildrenTable{{ {:?} }}", self.to_ref())
293    }
294}
295
296impl<NodeRefT: NodeRefTrait> CompactedChildrenTable<NodeRefT> {
297    pub fn get_children_count(&self) -> u8 { self.children_count }
298
299    pub fn get_child(&self, index: u8) -> Option<NodeRefT> {
300        if Self::has_index(self.bitmap, index) {
301            Some(unsafe {
302                (*self.table_ptr.add(Self::lower_bound(self.bitmap, index)))
303                    .clone()
304            })
305        } else {
306            None
307        }
308    }
309
310    pub unsafe fn get_child_mut_unchecked(
311        &mut self, index: u8,
312    ) -> &mut NodeRefT {
313        &mut *self.table_ptr.add(Self::lower_bound(self.bitmap, index))
314    }
315
316    /// Unsafe because child must already exist at the index.
317    pub unsafe fn set_child_unchecked(&mut self, index: u8, value: NodeRefT) {
318        *self.table_ptr.add(Self::lower_bound(self.bitmap, index)) =
319            value.clone();
320    }
321
322    pub fn new_from_one_child(index: u8, value: NodeRefT) -> Self {
323        Self {
324            bitmap: Self::bit(index.into()),
325            children_count: 1,
326            table_ptr: unsafe {
327                Self::managed_slice_into_raw(vec![value].into_boxed_slice())
328            },
329        }
330    }
331
332    pub unsafe fn insert_child_unchecked(
333        old_table: ChildrenTableRef<NodeRefT>, index: u8, value: NodeRefT,
334    ) -> Self {
335        let insertion_pos = Self::lower_bound(old_table.bitmap, index);
336        Self {
337            bitmap: old_table.bitmap | Self::bit(index.into()),
338            children_count: old_table.table.len() as u8 + 1,
339            table_ptr: Self::managed_slice_into_raw(
340                [
341                    &old_table.table[0..insertion_pos],
342                    &[value],
343                    &old_table.table[insertion_pos..],
344                ]
345                .concat()
346                .into_boxed_slice(),
347            ),
348        }
349    }
350
351    pub unsafe fn delete_child_unchecked(
352        old_table: ChildrenTableRef<NodeRefT>, index: u8,
353    ) -> Self {
354        let deletion_pos = Self::lower_bound(old_table.bitmap, index);
355        Self {
356            bitmap: old_table.bitmap & (!Self::bit(index.into())),
357            children_count: old_table.table.len() as u8 - 1,
358            table_ptr: Self::managed_slice_into_raw(
359                [
360                    &old_table.table[0..deletion_pos],
361                    &old_table.table[deletion_pos + 1..],
362                ]
363                .concat()
364                .into_boxed_slice(),
365            ),
366        }
367    }
368}
369
370#[cfg(test)]
371impl<NodeRefT: NodeRefTrait> CompactedChildrenTable<NodeRefT> {
372    pub fn assert_no_alloc_in_empty_children_table(&self) {
373        assert_eq!(
374            true,
375            self.children_count != 0
376                || self.table_ptr == null_mut()
377                || self.table_ptr as usize == mem::align_of::<NodeRefT>()
378        )
379    }
380}
381
382impl<NodeRefT: NodeRefTrait> Drop for CompactedChildrenTable<NodeRefT> {
383    fn drop(&mut self) {
384        if self.children_count != 0 {
385            drop(unsafe { self.into_managed_slice() });
386        } else {
387            // When children_count is 0, the table_ptr must be null.
388            // If the table_ptr is an "empty array" there could be memory leak.
389            //
390            // The assertion is commented out here because it's checked in unit
391            // test.
392            /*
393            assert_eq!(
394                true,
395                self.table_ptr == null_mut()
396                    || self.table_ptr as usize == mem::align_of::<NodeRefT>()
397            );
398            */
399        }
400    }
401}
402
403impl<NodeRefT: NodeRefTrait> CompactedChildrenTable<NodeRefT> {
404    unsafe fn into_managed_slice(&self) -> Option<Vec<NodeRefT>> {
405        if self.children_count != 0 {
406            assert_ne!(self.table_ptr, null_mut());
407            Some(Vec::from_raw_parts(
408                self.table_ptr,
409                self.children_count.into(),
410                self.children_count.into(),
411            ))
412        } else {
413            None
414        }
415    }
416
417    unsafe fn managed_slice_into_raw(
418        mut managed: Box<[NodeRefT]>,
419    ) -> *mut NodeRefT {
420        // If the slice has length 0, the pointer returned from as_mut_ptr
421        // isn't NULL, but alignment of the type in rust's stdlib
422        // implementation. This is OK because we always check (unless
423        // otherwise specified) before using the pointer.
424        let ret = managed.as_mut_ptr();
425
426        mem::forget(managed);
427        ret
428    }
429
430    pub fn from_managed(managed: ChildrenTable<NodeRefT>) -> Self {
431        let children_count = managed.table.len() as u8;
432        Self {
433            bitmap: managed.bitmap,
434            table_ptr: unsafe { Self::managed_slice_into_raw(managed.table) },
435            children_count,
436        }
437    }
438
439    pub fn to_ref(&self) -> ChildrenTableRef<'_, NodeRefT> {
440        debug_assert!(!self.table_ptr.is_null() || self.children_count == 0);
441        ChildrenTableRef {
442            table: unsafe {
443                slice::from_raw_parts(
444                    if self.table_ptr.is_null() {
445                        NonNull::dangling().as_ptr()
446                    } else {
447                        self.table_ptr
448                    },
449                    self.children_count.into(),
450                )
451            },
452            bitmap: self.bitmap,
453        }
454    }
455
456    pub fn from_ref<'a>(r: ChildrenTableRef<'a, NodeRefT>) -> Self {
457        Self {
458            bitmap: r.bitmap,
459            table_ptr: unsafe {
460                Self::managed_slice_into_raw(r.table.to_vec().into())
461            },
462            children_count: r.table.len() as u8,
463        }
464    }
465}
466
467impl<NodeRefT: NodeRefTrait> CompactedChildrenTable<NodeRefT> {
468    fn bit(index: u16) -> u16 { 1 << index }
469
470    fn has_index(bitmap: u16, index: u8) -> bool {
471        Self::bit(index.into()) & bitmap != 0
472    }
473
474    fn lower_bits(index: u16) -> u16 { (1 << index) - 1 }
475
476    fn all_bits() -> u16 { !0 }
477
478    fn count_bits(bitmap: u16) -> u16 {
479        let mut count = (bitmap & 0b0101010101010101)
480            + ((bitmap >> 1) & 0b0101010101010101);
481        count =
482            (count & 0b0011001100110011) + ((count >> 2) & 0b0011001100110011);
483        count =
484            (count & 0b0000111100001111) + ((count >> 4) & 0b0000111100001111);
485        (count & 0b0000000011111111) + (count >> 8)
486    }
487
488    fn lowest_bit_at(bitmap: u16) -> u8 {
489        Self::count_bits(1 ^ bitmap ^ (bitmap - 1)) as u8
490    }
491
492    fn remove_lowest_bit(bitmap: u16) -> u16 { bitmap & (bitmap - 1) }
493
494    fn lower_bound(bitmap: u16, index: u8) -> usize {
495        Self::count_bits(bitmap & Self::lower_bits(index.into())).into()
496    }
497}
498
499impl<NodeRefT: NodeRefTrait> CompactedChildrenTable<NodeRefT> {
500    pub fn iter(&self) -> CompactedChildrenTableIterator<'_, NodeRefT> {
501        CompactedChildrenTableIterator {
502            elements: self.table_ptr,
503            bitmap: self.bitmap,
504            __marker: PhantomData,
505        }
506    }
507
508    pub fn iter_mut(
509        &mut self,
510    ) -> CompactedChildrenTableIteratorMut<'_, NodeRefT> {
511        CompactedChildrenTableIteratorMut {
512            elements: self.table_ptr,
513            bitmap: self.bitmap,
514            __marker: PhantomData,
515        }
516    }
517
518    pub fn iter_non_skip(
519        &self,
520    ) -> CompactedChildrenTableIteratorNonSkip<'_, NodeRefT> {
521        CompactedChildrenTableIteratorNonSkip {
522            next_child_index: 0,
523            elements: self.table_ptr,
524            bitmap: self.bitmap,
525            __marker: PhantomData,
526        }
527    }
528
529    pub fn iter_non_skip_mut(
530        &mut self,
531    ) -> CompactedChildrenTableIteratorNonSkipMut<'_, NodeRefT> {
532        CompactedChildrenTableIteratorNonSkipMut {
533            next_child_index: 0,
534            elements: self.table_ptr,
535            bitmap: self.bitmap,
536            __marker: PhantomData,
537        }
538    }
539}
540
541impl<NodeRefT: NodeRefTrait> PartialEq for CompactedChildrenTable<NodeRefT> {
542    fn eq(&self, other: &Self) -> bool { self.to_ref() == other.to_ref() }
543}
544
545pub trait ChildrenTableIteratorStartIndex {
546    fn set_start_index(self, index: u8) -> Self;
547}
548
549trait CompactedChildrenTableIteratorTrait: ChildrenTableIteratorStartIndex {
550    type NodeRefT: NodeRefTrait;
551    type RefType;
552
553    fn get_bitmap(&self) -> u16;
554
555    /// Only for CompactedChildrenTableIteratorNextTrait
556    fn set_bitmap(&mut self, bitmap: u16);
557
558    /// Only for CompactedChildrenTableIteratorNonSkipNextTrait
559    fn set_next_child_index(&mut self, child_index: u8);
560
561    fn get_current_element(&self) -> Self::RefType;
562
563    fn advance_elements(&mut self);
564}
565
566trait CompactedChildrenTableIteratorNonSkipImplTrait:
567    CompactedChildrenTableIteratorTrait
568{
569    fn set_start_index_impl(&mut self, index: u8) {
570        self.set_next_child_index(index);
571    }
572
573    fn next_impl(
574        &mut self, child_index: u8,
575    ) -> Option<(u8, Option<Self::RefType>)> {
576        if child_index as usize == CHILDREN_COUNT {
577            return None;
578        }
579
580        let ret;
581        if CompactedChildrenTable::<Self::NodeRefT>::has_index(
582            self.get_bitmap(),
583            child_index,
584        ) {
585            ret = Some((child_index, Some(self.get_current_element())));
586            self.advance_elements();
587        } else {
588            ret = Some((child_index, None));
589        }
590        self.set_next_child_index(child_index + 1);
591
592        ret
593    }
594}
595
596trait CompactedChildrenTableIteratorImplTrait:
597    CompactedChildrenTableIteratorTrait
598{
599    fn set_start_index_impl(&mut self, index: u8) {
600        self.set_bitmap(
601            self.get_bitmap()
602                & !CompactedChildrenTable::<Self::NodeRefT>::lower_bits(
603                    index.into(),
604                ),
605        );
606    }
607
608    fn next_impl(&mut self) -> Option<(u8, Self::RefType)> {
609        let ret;
610        if self.get_bitmap() != 0 {
611            ret = Some((
612                CompactedChildrenTable::<Self::NodeRefT>::lowest_bit_at(
613                    self.get_bitmap(),
614                ),
615                self.get_current_element(),
616            ));
617        } else {
618            return None;
619        }
620
621        self.advance_elements();
622        self.set_bitmap(
623            CompactedChildrenTable::<Self::NodeRefT>::remove_lowest_bit(
624                self.get_bitmap(),
625            ),
626        );
627
628        ret
629    }
630}
631
632pub struct CompactedChildrenTableIteratorNonSkip<'a, NodeRefT> {
633    next_child_index: u8,
634    elements: *const NodeRefT,
635    bitmap: u16,
636    __marker: PhantomData<&'a NodeRefT>,
637}
638
639impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorTrait
640    for CompactedChildrenTableIteratorNonSkip<'a, NodeRefT>
641{
642    type NodeRefT = NodeRefT;
643    type RefType = &'a NodeRefT;
644
645    fn get_bitmap(&self) -> u16 { self.bitmap }
646
647    /// This method is unnecessary.
648    fn set_bitmap(&mut self, _bitmap: u16) { unreachable!() }
649
650    fn set_next_child_index(&mut self, child_index: u8) {
651        self.next_child_index = child_index;
652    }
653
654    fn get_current_element(&self) -> &'a NodeRefT { unsafe { &*self.elements } }
655
656    fn advance_elements(&mut self) {
657        unsafe {
658            self.elements = self.elements.offset(1);
659        }
660    }
661}
662
663impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorNonSkipImplTrait
664    for CompactedChildrenTableIteratorNonSkip<'a, NodeRefT>
665{
666}
667
668impl<'a, NodeRefT: NodeRefTrait> Iterator
669    for CompactedChildrenTableIteratorNonSkip<'a, NodeRefT>
670{
671    type Item = (u8, Option<&'a NodeRefT>);
672
673    fn next(&mut self) -> Option<Self::Item> {
674        self.next_impl(self.next_child_index)
675    }
676}
677
678impl<'a, NodeRefT: NodeRefTrait> ChildrenTableIteratorStartIndex
679    for CompactedChildrenTableIteratorNonSkip<'a, NodeRefT>
680{
681    fn set_start_index(mut self, index: u8) -> Self {
682        self.set_start_index_impl(index);
683        self
684    }
685}
686
687pub struct CompactedChildrenTableIteratorNonSkipMut<'a, NodeRefT> {
688    next_child_index: u8,
689    elements: *mut NodeRefT,
690    bitmap: u16,
691    __marker: PhantomData<&'a mut NodeRefT>,
692}
693
694impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorTrait
695    for CompactedChildrenTableIteratorNonSkipMut<'a, NodeRefT>
696{
697    type NodeRefT = NodeRefT;
698    type RefType = &'a mut NodeRefT;
699
700    fn get_bitmap(&self) -> u16 { self.bitmap }
701
702    /// This method is unnecessary.
703    fn set_bitmap(&mut self, _bitmap: u16) { unreachable!() }
704
705    fn set_next_child_index(&mut self, child_index: u8) {
706        self.next_child_index = child_index;
707    }
708
709    fn get_current_element(&self) -> &'a mut NodeRefT {
710        unsafe { &mut *self.elements }
711    }
712
713    fn advance_elements(&mut self) {
714        unsafe {
715            self.elements = self.elements.offset(1);
716        }
717    }
718}
719
720impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorNonSkipImplTrait
721    for CompactedChildrenTableIteratorNonSkipMut<'a, NodeRefT>
722{
723}
724
725impl<'a, NodeRefT: NodeRefTrait> Iterator
726    for CompactedChildrenTableIteratorNonSkipMut<'a, NodeRefT>
727{
728    type Item = (u8, Option<&'a mut NodeRefT>);
729
730    fn next(&mut self) -> Option<Self::Item> {
731        self.next_impl(self.next_child_index)
732    }
733}
734
735impl<'a, NodeRefT: NodeRefTrait> ChildrenTableIteratorStartIndex
736    for CompactedChildrenTableIteratorNonSkipMut<'a, NodeRefT>
737{
738    fn set_start_index(mut self, index: u8) -> Self {
739        self.set_start_index_impl(index);
740        self
741    }
742}
743
744pub struct CompactedChildrenTableIterator<'a, NodeRefT> {
745    elements: *const NodeRefT,
746    bitmap: u16,
747    __marker: PhantomData<&'a NodeRefT>,
748}
749
750impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorTrait
751    for CompactedChildrenTableIterator<'a, NodeRefT>
752{
753    type NodeRefT = NodeRefT;
754    type RefType = &'a NodeRefT;
755
756    fn get_bitmap(&self) -> u16 { self.bitmap }
757
758    fn set_bitmap(&mut self, bitmap: u16) { self.bitmap = bitmap }
759
760    /// This method is unnecessary.
761    fn set_next_child_index(&mut self, _child_index: u8) { unreachable!() }
762
763    fn get_current_element(&self) -> &'a NodeRefT { unsafe { &*self.elements } }
764
765    fn advance_elements(&mut self) {
766        unsafe {
767            self.elements = self.elements.offset(1);
768        }
769    }
770}
771
772impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorImplTrait
773    for CompactedChildrenTableIterator<'a, NodeRefT>
774{
775}
776
777impl<'a, NodeRefT: NodeRefTrait> Iterator
778    for CompactedChildrenTableIterator<'a, NodeRefT>
779{
780    type Item = (u8, &'a NodeRefT);
781
782    fn next(&mut self) -> Option<Self::Item> { self.next_impl() }
783}
784
785impl<'a, NodeRefT: NodeRefTrait> ChildrenTableIteratorStartIndex
786    for CompactedChildrenTableIterator<'a, NodeRefT>
787{
788    fn set_start_index(mut self, index: u8) -> Self {
789        self.set_start_index_impl(index);
790        self
791    }
792}
793
794pub struct CompactedChildrenTableIteratorMut<'a, NodeRefT> {
795    elements: *mut NodeRefT,
796    bitmap: u16,
797    __marker: PhantomData<&'a mut NodeRefT>,
798}
799
800impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorTrait
801    for CompactedChildrenTableIteratorMut<'a, NodeRefT>
802{
803    type NodeRefT = NodeRefT;
804    type RefType = &'a mut NodeRefT;
805
806    fn get_bitmap(&self) -> u16 { self.bitmap }
807
808    fn set_bitmap(&mut self, bitmap: u16) { self.bitmap = bitmap }
809
810    /// This method is unnecessary.
811    fn set_next_child_index(&mut self, _child_index: u8) { unreachable!() }
812
813    fn get_current_element(&self) -> &'a mut NodeRefT {
814        unsafe { &mut *self.elements }
815    }
816
817    fn advance_elements(&mut self) {
818        unsafe {
819            self.elements = self.elements.offset(1);
820        }
821    }
822}
823
824impl<'a, NodeRefT: NodeRefTrait> CompactedChildrenTableIteratorImplTrait
825    for CompactedChildrenTableIteratorMut<'a, NodeRefT>
826{
827}
828
829impl<'a, NodeRefT: NodeRefTrait> Iterator
830    for CompactedChildrenTableIteratorMut<'a, NodeRefT>
831{
832    type Item = (u8, &'a mut NodeRefT);
833
834    fn next(&mut self) -> Option<Self::Item> { self.next_impl() }
835}
836
837impl<'a, NodeRefT: NodeRefTrait> ChildrenTableIteratorStartIndex
838    for CompactedChildrenTableIteratorMut<'a, NodeRefT>
839{
840    fn set_start_index(mut self, index: u8) -> Self {
841        self.set_start_index_impl(index);
842        self
843    }
844}
845
846#[derive(MallocSizeOfDerive)]
847pub struct ChildrenTable<NodeRefT: NodeRefTrait> {
848    /// Stores the existing children ordered.
849    table: Box<[NodeRefT]>,
850    /// Stores whether each child exists.
851    bitmap: u16,
852}
853
854impl<NodeRefT: NodeRefTrait> Default for ChildrenTable<NodeRefT> {
855    fn default() -> Self {
856        Self {
857            table: vec![].into_boxed_slice(),
858            bitmap: 0,
859        }
860    }
861}
862
863#[derive(Clone, Debug, PartialEq)]
864pub struct ChildrenTableRef<'a, NodeRefT: NodeRefTrait> {
865    table: &'a [NodeRefT],
866    bitmap: u16,
867}
868
869impl<'a, NodeRefT: NodeRefTrait> From<ChildrenTableRef<'a, NodeRefT>>
870    for CompactedChildrenTable<NodeRefT>
871{
872    fn from(x: ChildrenTableRef<'a, NodeRefT>) -> Self { Self::from_ref(x) }
873}
874
875impl<NodeRefT: NodeRefTrait> From<ChildrenTable<NodeRefT>>
876    for CompactedChildrenTable<NodeRefT>
877{
878    fn from(x: ChildrenTable<NodeRefT>) -> Self { Self::from_managed(x) }
879}
880
881impl<'a, NodeRefT: NodeRefTrait> Encodable for ChildrenTableRef<'a, NodeRefT> {
882    fn rlp_append(&self, s: &mut RlpStream) {
883        match self.table.len() {
884            0 => s.begin_list(0),
885            // Skip bitmap if list has length of 16.
886            16 => s.append_list(self.table),
887            // TODO(yz): Instead, use [bitmap, child_0, ... , child_n] for N @
888            // 1..14; when N == 15: [bitmap, 0, child_0, ... ,
889            // child_15] to save 2 bytes.
890            _ => s.begin_list(2).append(&self.bitmap).append_list(self.table),
891        };
892    }
893}
894
895impl<NodeRefT: NodeRefTrait> Decodable for ChildrenTable<NodeRefT> {
896    fn decode(rlp: &Rlp) -> ::std::result::Result<Self, DecoderError> {
897        let item_count = rlp.item_count()?;
898        Ok(match item_count {
899            0..=1 => Self::default(),
900            16 => Self {
901                bitmap: CompactedChildrenTable::<NodeRefT>::all_bits(),
902                table: rlp.as_list::<NodeRefT>()?.into_boxed_slice(),
903            },
904            _ => Self {
905                bitmap: rlp.val_at::<u16>(0)?,
906                table: rlp.list_at::<NodeRefT>(1)?.into_boxed_slice(),
907            },
908        })
909    }
910}
911
912use super::{
913    super::super::utils::WrappedCreateFrom,
914    merkle::{ChildrenMerkleTable, MaybeMerkleTable},
915};
916use malloc_size_of::{MallocSizeOf, MallocSizeOfOps};
917use malloc_size_of_derive::MallocSizeOf as MallocSizeOfDerive;
918use primitives::{MerkleHash, MERKLE_NULL_NODE};
919use rlp::*;
920use serde::{
921    ser::SerializeSeq, Deserialize, Deserializer, Serialize, Serializer,
922};
923use std::{
924    fmt::*,
925    marker::PhantomData,
926    mem::{self, MaybeUninit},
927    ptr::{null_mut, NonNull},
928    slice,
929};
cfx_storage/impls/merkle_patricia_trie/children_table.rs

cfx_storage/impls/merkle_patricia_trie/
children_table.rs
