117965080

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/neo-project/neo/commit/<a class=hub.com/neo-project/neo/commit/63db9f39190687c90d7dce15ad730e068f63b302">63db9f391<a href="https://github.com/neo-project/neo/commit/63db9f39190687c90d7dce15ad730e068f63b302">">Merge </a><a class="double-link" href="https://github.com/neo-project/neo/commit/<a class="double-link" href="https://github.com/neo-project/neo/commit/528283b4887635d6971bc54a6c89544747b426a0">528283b48</a>">528283b48</a><a href="https://github.com/neo-project/neo/commit/63db9f39190687c90d7dce15ad730e068f63b302"> into ce0234d7f">ce0234d7f</a>

Pull Request Pull Request #1442: Add MPT

Run Details

2887 of 4342 branches covered (66.49%)

Branch coverage included in aggregate %.

484 of 484 new or added lines in 12 files covered. (100.0%)

10291 of 12970 relevant lines covered (79.34%)

511212.81 hits per line

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

83.63

/src/neo/Cryptography/MPT/MPTTrie.Put.cs

using Neo.IO;
using System;

namespace Neo.Cryptography.MPT
{
    partial class MPTTrie<TKey, TValue>
    {
        private static ReadOnlySpan<byte> CommonPrefix(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b)
        {
            var minLen = a.Length <= b.Length ? a.Length : b.Length;
            int i = 0;
            if (a.Length != 0 && b.Length != 0)
            {
                for (i = 0; i < minLen; i++)
                {
                    if (a[i] != b[i]) break;
                }
            }
            return a[..i];
        }

        public bool Put(TKey key, TValue value)
        {
            var path = ToNibbles(key.ToArray());
            var val = value.ToArray();
            if (path.Length == 0 || path.Length > ExtensionNode.MaxKeyLength)
                return false;
            if (val.Length > LeafNode.MaxValueLength)
                return false;
            if (val.Length == 0)
                return TryDelete(ref root, path);
            var n = new LeafNode(val);
            return Put(ref root, path, n);
        }

        private bool Put(ref MPTNode node, ReadOnlySpan<byte> path, MPTNode val)
        {
            switch (node)
            {
                case LeafNode leafNode:
                    {
                        if (val is LeafNode v)
                        {
                            if (path.IsEmpty)
                            {
                                node = v;
                                PutToStore(node);
                                return true;
                            }
                            var branch = new BranchNode();
                            branch.Children[BranchNode.ChildCount - 1] = leafNode;
                            Put(ref branch.Children[path[0]], path[1..], v);
                            PutToStore(branch);
                            node = branch;
                            return true;
                        }
                        return false;
                    }
                case ExtensionNode extensionNode:
                    {
                        if (path.StartsWith(extensionNode.Key))
                        {
                            var result = Put(ref extensionNode.Next, path[extensionNode.Key.Length..], val);
                            if (result)
                            {
                                extensionNode.SetDirty();
                                PutToStore(extensionNode);
                            }
                            return result;
                        }
                        var prefix = CommonPrefix(extensionNode.Key, path);
                        var pathRemain = path[prefix.Length..];
                        var keyRemain = extensionNode.Key.AsSpan(prefix.Length);
                        var son = new BranchNode();
                        MPTNode grandSon1 = HashNode.EmptyNode;
                        MPTNode grandSon2 = HashNode.EmptyNode;

                        Put(ref grandSon1, keyRemain[1..], extensionNode.Next);
                        son.Children[keyRemain[0]] = grandSon1;

                        if (pathRemain.IsEmpty)
                        {
                            Put(ref grandSon2, pathRemain, val);
                            son.Children[BranchNode.ChildCount - 1] = grandSon2;
                        }
                        else
                        {
                            Put(ref grandSon2, pathRemain[1..], val);
                            son.Children[pathRemain[0]] = grandSon2;
                        }
                        PutToStore(son);
                        if (prefix.Length > 0)
                        {
                            var exNode = new ExtensionNode()
                            {
                                Key = prefix.ToArray(),
                                Next = son,
                            };
                            PutToStore(exNode);
                            node = exNode;
                        }
                        else
                        {
                            node = son;
                        }
                        return true;
                    }
                case BranchNode branchNode:
                    {
                        bool result;
                        if (path.IsEmpty)
                        {
                            result = Put(ref branchNode.Children[BranchNode.ChildCount - 1], path, val);
                        }
                        else
                        {
                            result = Put(ref branchNode.Children[path[0]], path[1..], val);
                        }
                        if (result)
                        {
                            branchNode.SetDirty();
                            PutToStore(branchNode);
                        }
                        return result;
                    }
                case HashNode hashNode:
                    {
                        MPTNode newNode;
                        if (hashNode.IsEmpty)
                        {
                            if (path.IsEmpty)
                            {
                                newNode = val;
                            }
                            else
                            {
                                newNode = new ExtensionNode()
                                {
                                    Key = path.ToArray(),
                                    Next = val,
                                };
                                PutToStore(newNode);
                            }
                            node = newNode;
                            if (val is LeafNode) PutToStore(val);
                            return true;
                        }
                        newNode = Resolve(hashNode);
                        if (newNode is null) return false;
                        node = newNode;
                        return Put(ref node, path, val);
                    }
                default:
                    return false;
            }
        }
    }
}

1	using Neo.IO;
2	using System;
3
4	namespace Neo.Cryptography.MPT
5	{
6	partial class MPTTrie<TKey, TValue>
7	{
8	private static ReadOnlySpan<byte> CommonPrefix(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b)
9	{	6✔
10	var minLen = a.Length <= b.Length ? a.Length : b.Length;	6✔
11	int i = 0;	6✔
12	if (a.Length != 0 && b.Length != 0)	6!
13	{	6✔
14	for (i = 0; i < minLen; i++)	44✔
15	{	20✔
16	if (a[i] != b[i]) break;	24✔
17	}	16✔
18	}	6✔
19	return a[..i];	6✔
20	}	6✔
21
22	public bool Put(TKey key, TValue value)
23	{	17✔
24	var path = ToNibbles(key.ToArray());	17✔
25	var val = value.ToArray();	17✔
26	if (path.Length == 0 \|\| path.Length > ExtensionNode.MaxKeyLength)	17!
27	return false;	×
28	if (val.Length > LeafNode.MaxValueLength)	17!
29	return false;	×
30	if (val.Length == 0)	17!
31	return TryDelete(ref root, path);	×
32	var n = new LeafNode(val);	17✔
33	return Put(ref root, path, n);	17✔
34	}	17✔
35
36	private bool Put(ref MPTNode node, ReadOnlySpan<byte> path, MPTNode val)
37	{	37✔
38	switch (node)	37!
39	{
40	case LeafNode leafNode:
41	{	2✔
42	if (val is LeafNode v)	2!
43	{	2✔
44	if (path.IsEmpty)	2!
45	{	×
46	node = v;	×
47	PutToStore(node);	×
48	return true;	×
49	}
50	var branch = new BranchNode();	2✔
51	branch.Children[BranchNode.ChildCount - 1] = leafNode;	2✔
52	Put(ref branch.Children[path[0]], path[1..], v);	2✔
53	PutToStore(branch);	2✔
54	node = branch;	2✔
55	return true;	2✔
56	}
57	return false;	×
58	}
59	case ExtensionNode extensionNode:
60	{	10✔
61	if (path.StartsWith(extensionNode.Key))	10✔
62	{	4✔
63	var result = Put(ref extensionNode.Next, path[extensionNode.Key.Length..], val);	4✔
64	if (result)	4✔
65	{	4✔
66	extensionNode.SetDirty();	4✔
67	PutToStore(extensionNode);	4✔
68	}	4✔
69	return result;	4✔
70	}
71	var prefix = CommonPrefix(extensionNode.Key, path);	6✔
72	var pathRemain = path[prefix.Length..];	6✔
73	var keyRemain = extensionNode.Key.AsSpan(prefix.Length);	6✔
74	var son = new BranchNode();	6✔
75	MPTNode grandSon1 = HashNode.EmptyNode;	6✔
76	MPTNode grandSon2 = HashNode.EmptyNode;	6✔
77
78	Put(ref grandSon1, keyRemain[1..], extensionNode.Next);	6✔
79	son.Children[keyRemain[0]] = grandSon1;	6✔
80
81	if (pathRemain.IsEmpty)	6✔
82	{	2✔
83	Put(ref grandSon2, pathRemain, val);	2✔
84	son.Children[BranchNode.ChildCount - 1] = grandSon2;	2✔
85	}	2✔
86	else
87	{	4✔
88	Put(ref grandSon2, pathRemain[1..], val);	4✔
89	son.Children[pathRemain[0]] = grandSon2;	4✔
90	}	4✔
91	PutToStore(son);	6✔
92	if (prefix.Length > 0)	6!
93	{	6✔
94	var exNode = new ExtensionNode()	6✔
95	{	6✔
96	Key = prefix.ToArray(),	6✔
97	Next = son,	6✔
98	};	6✔
99	PutToStore(exNode);	6✔
100	node = exNode;	6✔
101	}	6✔
102	else
103	{	×
104	node = son;	×
105	}	×
106	return true;	6✔
107	}
108	case BranchNode branchNode:
109	{	2✔
110	bool result;
111	if (path.IsEmpty)	2✔
112	{	1✔
113	result = Put(ref branchNode.Children[BranchNode.ChildCount - 1], path, val);	1✔
114	}	1✔
115	else
116	{	1✔
117	result = Put(ref branchNode.Children[path[0]], path[1..], val);	1✔
118	}	1✔
119	if (result)	2✔
120	{	2✔
121	branchNode.SetDirty();	2✔
122	PutToStore(branchNode);	2✔
123	}	2✔
124	return result;	2✔
125	}
126	case HashNode hashNode:
127	{	23✔
128	MPTNode newNode;
129	if (hashNode.IsEmpty)	23!
130	{	23✔
131	if (path.IsEmpty)	23✔
132	{	7✔
133	newNode = val;	7✔
134	}	7✔
135	else
136	{	16✔
137	newNode = new ExtensionNode()	16✔
138	{	16✔
139	Key = path.ToArray(),	16✔
140	Next = val,	16✔
141	};	16✔
142	PutToStore(newNode);	16✔
143	}	16✔
144	node = newNode;	23✔
145	if (val is LeafNode) PutToStore(val);	45✔
146	return true;	23✔
147	}
148	newNode = Resolve(hashNode);	×
149	if (newNode is null) return false;	×
150	node = newNode;	×
151	return Put(ref node, path, val);	×
152	}
153	default:
154	return false;	×
155	}
156	}	37✔
157	}
158	}

neo-project / neo / 117965080

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