forked from cosmos/iavl
-
Notifications
You must be signed in to change notification settings - Fork 0
/
serialize.go
200 lines (176 loc) · 5.08 KB
/
serialize.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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
package iavl
// NodeData groups together a key, value and depth.
type NodeData struct {
Key []byte
Value []byte
Depth uint8
}
// SerializeFunc is any implementation that can serialize
// an iavl Node and its descendants.
type SerializeFunc func(*Tree, *Node) []NodeData
// RestoreFunc is an implementation that can restore an iavl tree from
// NodeData.
type RestoreFunc func(*Tree, []NodeData)
// Restore will take an (empty) tree restore it
// from the keys returned from a SerializeFunc.
func Restore(empty *Tree, kvs []NodeData) {
for _, kv := range kvs {
empty.Set(kv.Key, kv.Value)
}
empty.Hash()
}
func RestoreUsingDepth(empty *Tree, kvs []NodeData) {
// Create an array of arrays of nodes. We're going to store each depth in
// here, forming a kind of pyramid.
depths := [][]*Node{}
// Go through all the leaf nodes, grouping them in pairs and creating their
// parents recursively.
for _, kv := range kvs {
var (
// Left and right nodes.
l *Node = nil
r *Node = NewNode(kv.Key, kv.Value, 1)
depth uint8 = kv.Depth
)
// Create depths as needed.
for len(depths) < int(depth)+1 {
depths = append(depths, []*Node{})
}
depths[depth] = append(depths[depth], r) // Add the leaf node to this depth.
// If the nodes at this level are uneven after adding a node to it, it
// means we have to wait for another node to be appended before we have
// a pair. If we do have a pair, go up the tree until we don't.
for d := depth; len(depths[d])%2 == 0; d-- {
nodes := depths[d] // List of nodes at this depth.
l = nodes[len(nodes)-1-1]
r = nodes[len(nodes)-1]
depths[d-1] = append(depths[d-1], &Node{
key: leftmost(r).Key,
height: maxInt8(l.height, r.height) + 1,
size: l.size + r.size,
leftNode: l,
rightNode: r,
version: 1,
})
}
}
empty.root = depths[0][0]
empty.Hash()
}
// InOrderSerialize returns all key-values in the
// key order (as stored). May be nice to read, but
// when recovering, it will create a different.
func InOrderSerialize(t *Tree, root *Node) []NodeData {
res := make([]NodeData, 0, root.size)
root.traverseWithDepth(t, true, func(node *Node, depth uint8) bool {
if node.height == 0 {
kv := NodeData{Key: node.key, Value: node.value, Depth: depth}
res = append(res, kv)
}
return false
})
return res
}
// StableSerializeBFS serializes the tree in a breadth-first manner.
func StableSerializeBFS(t *Tree, root *Node) []NodeData {
if root == nil {
return nil
}
size := root.size
visited := map[string][]byte{}
keys := make([][]byte, 0, size)
numKeys := -1
// Breadth-first search. At every depth, add keys in search order. Keep
// going as long as we find keys at that depth. When we reach a leaf, set
// its value in the visited map.
// Since we have an AVL+ tree, the inner nodes contain only keys and not
// values, while the leaves contain both. Note also that there are N-1 inner
// nodes for N keys, so one of the leaf keys is only set once we reach the leaves
// of the tree.
for depth := uint(0); len(keys) > numKeys; depth++ {
numKeys = len(keys)
root.traverseDepth(t, depth, func(node *Node) {
if _, ok := visited[string(node.key)]; !ok {
keys = append(keys, node.key)
visited[string(node.key)] = nil
}
if node.isLeaf() {
visited[string(node.key)] = node.value
}
})
}
nds := make([]NodeData, size)
for i, k := range keys {
nds[i] = NodeData{k, visited[string(k)], 0}
}
return nds
}
// StableSerializeFrey exports the key value pairs of the tree
// in an order, such that when Restored from those keys, the
// new tree would have the same structure (and thus same
// shape) as the original tree.
//
// the algorithm is basically this: take the leftmost node
// of the left half and the leftmost node of the righthalf.
// Then go down a level...
// each time adding leftmost node of the right side.
// (bredth first search)
//
// Imagine 8 nodes in a balanced tree, split in half each time
// 1
// 1, 5
// 1, 5, 3, 7
// 1, 5, 3, 7, 2, 4, 6, 8
func StableSerializeFrey(t *Tree, top *Node) []NodeData {
if top == nil {
return nil
}
size := top.size
// store all pending nodes for depth-first search
queue := make([]*Node, 0, size)
queue = append(queue, top)
// to store all results - started with
res := make([]NodeData, 0, size)
left := leftmost(top)
if left != nil {
res = append(res, *left)
}
var n *Node
for len(queue) > 0 {
// pop
n, queue = queue[0], queue[1:]
// l := n.getLeftNode(tree)
l := n.leftNode
if isInner(l) {
queue = append(queue, l)
}
// r := n.getRightNode(tree)
r := n.rightNode
if isInner(r) {
queue = append(queue, r)
left = leftmost(r)
if left != nil {
res = append(res, *left)
}
} else if isLeaf(r) {
kv := NodeData{Key: r.key, Value: r.value}
res = append(res, kv)
}
}
return res
}
func isInner(n *Node) bool {
return n != nil && !n.isLeaf()
}
func isLeaf(n *Node) bool {
return n != nil && n.isLeaf()
}
func leftmost(node *Node) *NodeData {
for isInner(node) {
node = node.leftNode
}
if node == nil {
return nil
}
return &NodeData{Key: node.key, Value: node.value}
}