# [−][src]Struct libra_jellyfish_merkle::node_type::InternalNode

Represents a 4-level subtree with 16 children at the bottom level. Theoretically, this reduces
IOPS to query a tree by 4x since we compress 4 levels in a standard Merkle tree into 1 node.
Though we choose the same internal node structure as that of Patricia Merkle tree, the root hash
computation logic is similar to a 4-level sparse Merkle tree except for some customizations. See
the `CryptoHash`

trait implementation below for details.

## Implementations

`impl InternalNode`

[src]

`pub fn new(children: HashMap<Nibble, Child>) -> Self`

[src]

Creates a new Internal node.

`pub fn hash(&self) -> HashValue`

[src]

`pub fn serialize(&self, binary: &mut Vec<u8>) -> Result<()>`

[src]

`pub fn deserialize(data: &[u8]) -> Result<Self>`

[src]

`pub fn child(&self, n: Nibble) -> Option<&Child>`

[src]

Gets the `n`

-th child.

`pub fn generate_bitmaps(&self) -> (u16, u16)`

[src]

Generates `existence_bitmap`

and `leaf_bitmap`

as a pair of `u16`

s: child at index `i`

exists if `existence_bitmap[i]`

is set; child at index `i`

is leaf node if
`leaf_bitmap[i]`

is set.

`pub fn get_child_with_siblings(`

&self,

node_key: &NodeKey,

n: Nibble

) -> (Option<NodeKey>, Vec<HashValue>)

[src]

&self,

node_key: &NodeKey,

n: Nibble

) -> (Option<NodeKey>, Vec<HashValue>)

Gets the child and its corresponding siblings that are necessary to generate the proof for
the `n`

-th child. If it is an existence proof, the returned child must be the `n`

-th
child; otherwise, the returned child may be another child. See inline explanation for
details. When calling this function with n = 11 (node `b`

in the following graph), the
range at each level is illustrated as a pair of square brackets:

```
4 [f e d c b a 9 8 7 6 5 4 3 2 1 0] -> root level
---------------------------------------------------------------
3 [f e d c b a 9 8] [7 6 5 4 3 2 1 0] width = 8
chs <--┘ shs <--┘
2 [f e d c] [b a 9 8] [7 6 5 4] [3 2 1 0] width = 4
shs <--┘ └--> chs
1 [f e] [d c] [b a] [9 8] [7 6] [5 4] [3 2] [1 0] width = 2
chs <--┘ └--> shs
0 [f] [e] [d] [c] [b] [a] [9] [8] [7] [6] [5] [4] [3] [2] [1] [0] width = 1
^ chs <--┘ └--> shs
| MSB|<---------------------- uint 16 ---------------------------->|LSB
height chs: `child_half_start` shs: `sibling_half_start`
```

## Trait Implementations

`impl Arbitrary for InternalNode`

[src]

Computes the hash of internal node according to `JellyfishTree`

data structure in the logical view. `start`

and `nibble_height`

determine a subtree whose
root hash we want to get. For an internal node with 16 children at the bottom level, we compute
the root hash of it as if a full binary Merkle tree with 16 leaves as below:

```
4 -> +------ root hash ------+
| |
3 -> +---- # ----+ +---- # ----+
| | | |
2 -> # # # #
/ \ / \ / \ / \
1 -> # # # # # # # #
/ \ / \ / \ / \ / \ / \ / \ / \
0 -> 0 1 2 3 4 5 6 7 8 9 A B C D E F
^
height
```

As illustrated above, at nibble height 0, `0..F`

in hex denote 16 chidren hashes. Each `#`

means the hash of its two direct children, which will be used to generate the hash of its
parent with the hash of its sibling. Finally, we can get the hash of this internal node.

However, if an internal node doesn't have all 16 chidren exist at height 0 but just a few of them, we have a modified hashing rule on top of what is stated above:

- From top to bottom, a node will be replaced by a leaf child if the subtree rooted at this node has only one child at height 0 and it is a leaf child.
- From top to bottom, a node will be replaced by the placeholder node if the subtree rooted at this node doesn't have any child at height 0. For example, if an internal node has 3 leaf children at index 0, 3, 8, respectively, and 1 internal node at index C, then the computation graph will be like:

```
4 -> +------ root hash ------+
| |
3 -> +---- # ----+ +---- # ----+
| | | |
2 -> # @ 8 #
/ \ / \
1 -> 0 3 # @
/ \
0 -> C @
^
height
Note: @ denotes placeholder hash.
```

`type Parameters = ()`

The type of parameters that `arbitrary_with`

accepts for configuration
of the generated `Strategy`

. Parameters must implement `Default`

. Read more

`type Strategy = BoxedStrategy<Self>`

`fn arbitrary_with(_args: ()) -> Self::Strategy`

[src]

`fn arbitrary() -> Self::Strategy`

`impl Clone for InternalNode`

[src]

`fn clone(&self) -> InternalNode`

[src]

`fn clone_from(&mut self, source: &Self)`

1.0.0[src]

`impl Debug for InternalNode`

[src]

`impl Eq for InternalNode`

[src]

`impl From<InternalNode> for Node`

[src]

`fn from(node: InternalNode) -> Self`

[src]

`impl From<InternalNode> for HashMap<Nibble, Child>`

[src]

`fn from(node: InternalNode) -> Self`

[src]

`impl PartialEq<InternalNode> for InternalNode`

[src]

`fn eq(&self, other: &InternalNode) -> bool`

[src]

`fn ne(&self, other: &InternalNode) -> bool`

[src]

`impl StructuralEq for InternalNode`

[src]

`impl StructuralPartialEq for InternalNode`

[src]

## Auto Trait Implementations

`impl RefUnwindSafe for InternalNode`

`impl Send for InternalNode`

`impl Sync for InternalNode`

`impl Unpin for InternalNode`

`impl UnwindSafe for InternalNode`

## Blanket Implementations

`impl<T> Any for T where`

T: 'static + ?Sized,

[src]

T: 'static + ?Sized,

`impl<T> Borrow<T> for T where`

T: ?Sized,

[src]

T: ?Sized,

`impl<T> BorrowMut<T> for T where`

T: ?Sized,

[src]

T: ?Sized,

`fn borrow_mut(&mut self) -> &mut T`

[src]

`impl<T> From<T> for T`

[src]

`impl<T, U> Into<U> for T where`

U: From<T>,

[src]

U: From<T>,

`impl<T> Pointable for T`

`const `**ALIGN**: usize

**ALIGN**: usize

`type Init = T`

The type for initializers.

`unsafe fn init(init: <T as Pointable>::Init) -> usize`

`unsafe fn deref<'a>(ptr: usize) -> &'a T`

`unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T`

`unsafe fn drop(ptr: usize)`

`impl<T> Same<T> for T`

`type Output = T`

Should always be `Self`

`impl<T> ToOwned for T where`

T: Clone,

[src]

T: Clone,

`type Owned = T`

The resulting type after obtaining ownership.

`fn to_owned(&self) -> T`

[src]

`fn clone_into(&self, target: &mut T)`

[src]

`impl<T, U> TryFrom<U> for T where`

U: Into<T>,

[src]

U: Into<T>,

`type Error = Infallible`

The type returned in the event of a conversion error.

`fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>`

[src]

`impl<T, U> TryInto<U> for T where`

U: TryFrom<T>,

[src]

U: TryFrom<T>,

`type Error = <U as TryFrom<T>>::Error`

The type returned in the event of a conversion error.

`fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>`

[src]

`impl<V, T> VZip<V> for T where`

V: MultiLane<T>,

V: MultiLane<T>,