/
helpers.go
97 lines (88 loc) · 2.25 KB
/
helpers.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package mpt
import "github.com/nspcc-dev/neo-go/pkg/util"
// lcp returns the longest common prefix of a and b.
// Note: it does no allocations.
func lcp(a, b []byte) []byte {
if len(a) < len(b) {
return lcp(b, a)
}
var i int
for i = 0; i < len(b); i++ {
if a[i] != b[i] {
break
}
}
return a[:i]
}
func lcpMany(kv []keyValue) []byte {
if len(kv) == 1 {
return kv[0].key
}
p := lcp(kv[0].key, kv[1].key)
if len(p) == 0 {
return p
}
for i := range kv[2:] {
p = lcp(p, kv[2+i].key)
}
return p
}
// toNibbles mangles the path by splitting every byte into 2 containing low- and high- 4-byte part.
func toNibbles(path []byte) []byte {
result := make([]byte, len(path)*2)
for i := range path {
result[i*2] = path[i] >> 4
result[i*2+1] = path[i] & 0x0F
}
return result
}
// strToNibbles mangles the path by splitting every byte into 2 containing low- and high- 4-byte part,
// ignoring the first byte (prefix).
func strToNibbles(path string) []byte {
result := make([]byte, (len(path)-1)*2)
for i := 0; i < len(path)-1; i++ {
result[i*2] = path[i+1] >> 4
result[i*2+1] = path[i+1] & 0x0F
}
return result
}
// fromNibbles performs an operation opposite to toNibbles and runs no path validity checks.
func fromNibbles(path []byte) []byte {
result := make([]byte, len(path)/2)
for i := range result {
result[i] = path[2*i]<<4 + path[2*i+1]
}
return result
}
// GetChildrenPaths returns a set of paths to the node's children who are non-empty HashNodes
// based on the node's path.
func GetChildrenPaths(path []byte, node Node) map[util.Uint256][][]byte {
res := make(map[util.Uint256][][]byte)
switch n := node.(type) {
case *LeafNode, *HashNode, EmptyNode:
return nil
case *BranchNode:
for i, child := range n.Children {
if child.Type() == HashT {
cPath := make([]byte, len(path), len(path)+1)
copy(cPath, path)
if i != lastChild {
cPath = append(cPath, byte(i))
}
paths := res[child.Hash()]
paths = append(paths, cPath)
res[child.Hash()] = paths
}
}
case *ExtensionNode:
if n.next.Type() == HashT {
cPath := make([]byte, len(path)+len(n.key))
copy(cPath, path)
copy(cPath[len(path):], n.key)
res[n.next.Hash()] = [][]byte{cPath}
}
default:
panic("unknown Node type")
}
return res
}