-
Notifications
You must be signed in to change notification settings - Fork 319
/
node.go
65 lines (54 loc) · 1.48 KB
/
node.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
// Copyright (c) 2020 IoTeX
// This is an alpha (internal) release and is not suitable for production. This source code is provided 'as is' and no
// warranties are given as to title or non-infringement, merchantability or fitness for purpose and, to the extent
// permitted by law, all liability for your use of the code is disclaimed. This source code is governed by Apache
// License 2.0 that can be found in the LICENSE file.
package mptrie
import (
"github.com/golang/protobuf/proto"
"github.com/pkg/errors"
)
// ErrNoData is an error when a hash node has no corresponding data
var ErrNoData = errors.New("no data in hash node")
type (
keyType []byte
node interface {
Search(keyType, uint8) (node, error)
Delete(keyType, uint8) (node, error)
Upsert(keyType, uint8, []byte) (node, error)
Hash() ([]byte, error)
Flush() error
}
serializable interface {
node
hash(flush bool) ([]byte, error)
proto(flush bool) (proto.Message, error)
delete() error
store() (node, error)
}
leaf interface {
node
// Key returns the key of a node, only leaf has key
Key() []byte
// Value returns the value of a node, only leaf has value
Value() []byte
}
extension interface {
node
Child() node
}
branch interface {
node
Children() []node
MarkAsRoot()
}
)
// key1 should not be longer than key2
func commonPrefixLength(key1, key2 []byte) uint8 {
match := uint8(0)
len1 := uint8(len(key1))
for match < len1 && key1[match] == key2[match] {
match++
}
return match
}