/
trie.go
673 lines (629 loc) · 22.8 KB
/
trie.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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
// Copyright 2014 The go-ethereum Authors
// This file is part of the go-ethereum library.
//
// The go-ethereum library is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// The go-ethereum library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
// Package trie implements Merkle Patricia Tries.
package trie
import (
"bytes"
"errors"
"fmt"
"sync"
"github.com/Evolution404/simcore/common"
"github.com/Evolution404/simcore/core/types"
"github.com/Evolution404/simcore/crypto"
"github.com/Evolution404/simcore/log"
"github.com/Evolution404/simcore/rlp"
)
var (
// emptyRoot is the known root hash of an empty trie.
// 对[128]进行keccak256计算
emptyRoot = common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")
// emptyState is the known hash of an empty state trie entry.
emptyState = crypto.Keccak256Hash(nil)
)
// LeafCallback is a callback type invoked when a trie operation reaches a leaf
// node.
//
// The paths is a path tuple identifying a particular trie node either in a single
// trie (account) or a layered trie (account -> storage). Each path in the tuple
// is in the raw format(32 bytes).
//
// The hexpath is a composite hexary path identifying the trie node. All the key
// bytes are converted to the hexary nibbles and composited with the parent path
// if the trie node is in a layered trie.
//
// It's used by state sync and commit to allow handling external references
// between account and storage tries. And also it's used in the state healing
// for extracting the raw states(leaf nodes) with corresponding paths.
// 当到达叶子节点的时候调用的函数
type LeafCallback func(paths [][]byte, hexpath []byte, leaf []byte, parent common.Hash) error
// Trie is a Merkle Patricia Trie.
// The zero value is an empty trie with no database.
// Use New to create a trie that sits on top of a database.
//
// Trie is not safe for concurrent use.
// 梅克尔帕特里夏树对象
type Trie struct {
// 保存数据库对象,用来读取节点内容
db *Database
// 保存根节点
root node
// Keep track of the number leafs which have been inserted since the last
// hashing operation. This number will not directly map to the number of
// actually unhashed nodes
// 记录当前树中有多少没计算哈希的节点
unhashed int
}
// newFlag returns the cache flag value for a newly created node.
// 默认的dirty是false,通过这个函数生成一个dirty是true的flag
func (t *Trie) newFlag() nodeFlag {
return nodeFlag{dirty: true}
}
// New creates a trie with an existing root node from db.
//
// If root is the zero hash or the sha3 hash of an empty string, the
// trie is initially empty and does not require a database. Otherwise,
// New will panic if db is nil and returns a MissingNodeError if root does
// not exist in the database. Accessing the trie loads nodes from db on demand.
// root为空,新建一个空树
// root不为空,根据root从数据库中重新加载整颗树
func New(root common.Hash, db *Database) (*Trie, error) {
if db == nil {
panic("trie.New called without a database")
}
trie := &Trie{
db: db,
}
// 如果root不为空,调用resolveHash加载整个树
if root != (common.Hash{}) && root != emptyRoot {
rootnode, err := trie.resolveHash(root[:], nil)
if err != nil {
return nil, err
}
trie.root = rootnode
}
return trie, nil
}
// NodeIterator returns an iterator that returns nodes of the trie. Iteration starts at
// the key after the given start key.
func (t *Trie) NodeIterator(start []byte) NodeIterator {
return newNodeIterator(t, start)
}
// Get returns the value for key stored in the trie.
// The value bytes must not be modified by the caller.
// 输入key是原始的格式
// Get函数不返回错误,有错误直接在日志打印
func (t *Trie) Get(key []byte) []byte {
res, err := t.TryGet(key)
if err != nil {
log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
}
return res
}
// TryGet returns the value for key stored in the trie.
// The value bytes must not be modified by the caller.
// If a node was not found in the database, a MissingNodeError is returned.
// 输入key是原始格式
// TyrGet有错误将会返回
func (t *Trie) TryGet(key []byte) ([]byte, error) {
value, newroot, didResolve, err := t.tryGet(t.root, keybytesToHex(key), 0)
// didResolve为true说明解析了某些hashNode
// 更改树根为新的解析了这些hashNode的树的树根
if err == nil && didResolve {
t.root = newroot
}
return value, err
}
// 输入key是hex格式,带有terminator
func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
switch n := (origNode).(type) {
case nil:
return nil, nil, false, nil
case valueNode:
return n, n, false, nil
case *shortNode:
// 查询的key长度在遇到这个shortNode后不足
// 或者这个shortNode保存的key片段不匹配
// 那么说明查询不到,直接返回
if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
// key not found in trie
return nil, n, false, nil
}
value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key))
if err == nil && didResolve {
n = n.copy()
n.Val = newnode
}
return value, n, didResolve, err
case *fullNode:
// terminator是16,所以遇到分支节点保存值key[pos]就取到了最后一项
value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
if err == nil && didResolve {
n = n.copy()
n.Children[key[pos]] = newnode
}
return value, n, didResolve, err
case hashNode:
// 将类型hashNode的n从数据库中解析为child
child, err := t.resolveHash(n, key[:pos])
if err != nil {
return nil, n, true, err
}
value, newnode, _, err := t.tryGet(child, key, pos)
return value, newnode, true, err
default:
panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
}
}
// TryGetNode attempts to retrieve a trie node by compact-encoded path. It is not
// possible to use keybyte-encoding as the path might contain odd nibbles.
// 输入compact格式的path查询树中节点
// 这个函数用来获取树中的任意节点,得到节点的rlp编码
func (t *Trie) TryGetNode(path []byte) ([]byte, int, error) {
item, newroot, resolved, err := t.tryGetNode(t.root, compactToHex(path), 0)
if err != nil {
return nil, resolved, err
}
if resolved > 0 {
t.root = newroot
}
if item == nil {
return nil, resolved, nil
}
return item, resolved, err
}
func (t *Trie) tryGetNode(origNode node, path []byte, pos int) (item []byte, newnode node, resolved int, err error) {
// If non-existent path requested, abort
if origNode == nil {
return nil, nil, 0, nil
}
// If we reached the requested path, return the current node
// 查询位置到达末尾了,返回当前的节点
if pos >= len(path) {
// Although we most probably have the original node expanded, encoding
// that into consensus form can be nasty (needs to cascade down) and
// time consuming. Instead, just pull the hash up from disk directly.
var hash hashNode
if node, ok := origNode.(hashNode); ok {
hash = node
} else {
hash, _ = origNode.cache()
}
if hash == nil {
return nil, origNode, 0, errors.New("non-consensus node")
}
blob, err := t.db.Node(common.BytesToHash(hash))
return blob, origNode, 1, err
}
// Path still needs to be traversed, descend into children
switch n := (origNode).(type) {
case valueNode:
// Path prematurely ended, abort
return nil, nil, 0, nil
case *shortNode:
if len(path)-pos < len(n.Key) || !bytes.Equal(n.Key, path[pos:pos+len(n.Key)]) {
// Path branches off from short node
return nil, n, 0, nil
}
item, newnode, resolved, err = t.tryGetNode(n.Val, path, pos+len(n.Key))
if err == nil && resolved > 0 {
n = n.copy()
n.Val = newnode
}
return item, n, resolved, err
case *fullNode:
item, newnode, resolved, err = t.tryGetNode(n.Children[path[pos]], path, pos+1)
if err == nil && resolved > 0 {
n = n.copy()
n.Children[path[pos]] = newnode
}
return item, n, resolved, err
case hashNode:
child, err := t.resolveHash(n, path[:pos])
if err != nil {
return nil, n, 1, err
}
item, newnode, resolved, err := t.tryGetNode(child, path, pos)
return item, newnode, resolved + 1, err
default:
panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
}
}
// Update associates key with value in the trie. Subsequent calls to
// Get will return value. If value has length zero, any existing value
// is deleted from the trie and calls to Get will return nil.
//
// The value bytes must not be modified by the caller while they are
// stored in the trie.
// 更新树中保存的键值
func (t *Trie) Update(key, value []byte) {
if err := t.TryUpdate(key, value); err != nil {
log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
}
}
func (t *Trie) TryUpdateAccount(key []byte, acc *types.StateAccount) error {
data, err := rlp.EncodeToBytes(acc)
if err != nil {
return fmt.Errorf("can't encode object at %x: %w", key[:], err)
}
return t.TryUpdate(key, data)
}
// TryUpdate associates key with value in the trie. Subsequent calls to
// Get will return value. If value has length zero, any existing value
// is deleted from the trie and calls to Get will return nil.
//
// The value bytes must not be modified by the caller while they are
// stored in the trie.
//
// If a node was not found in the database, a MissingNodeError is returned.
func (t *Trie) TryUpdate(key, value []byte) error {
t.unhashed++
k := keybytesToHex(key)
if len(value) != 0 {
_, n, err := t.insert(t.root, nil, k, valueNode(value))
if err != nil {
return err
}
t.root = n
} else {
_, n, err := t.delete(t.root, nil, k)
if err != nil {
return err
}
t.root = n
}
return nil
}
// prefix是已经处理完的部分key,key是还没有进行处理的key
// 存储元素完整的key是prefix+key
// 输入的n代表要插入的开始位置,可能是fullNode,shortNode,hashNode,valueNode,nil
// 输入的value一定是valueNode类型
func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
// 输入的key长度为0,只有可能是在更新某个节点递归到最后一步
if len(key) == 0 {
if v, ok := n.(valueNode); ok {
return !bytes.Equal(v, value.(valueNode)), value, nil
}
return true, value, nil
}
switch n := n.(type) {
// 这里n可能是叶子节点或者扩展节点
case *shortNode:
matchlen := prefixLen(key, n.Key)
// If the whole key matches, keep this short node as is
// and only update the value.
// 如果n是叶子节点,matchlen==len(n.Key)意味着n.Key和key完全一致,因为末尾的终止符也匹配到了
// 如果n是扩展节点,那么key一定比n.Key长
// 因为matchlen==len(n.Key),所以len(key)>=len(n.Key),这里总共就两种情况
// key和n.Key长度相等->n是叶子节点
// key比n.Key长->n是扩展节点
if matchlen == len(n.Key) {
// 如果n是叶子节点,由于n.Key和key完全一致,所以key[:matchlen]必然是空数组
dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
// dirty==false说明没修改,直接返回原来的
if !dirty || err != nil {
return false, n, err
}
// 被修改了,使用返回的内部节点重新构造一个shortNode
return true, &shortNode{n.Key, nn, t.newFlag()}, nil
}
// Otherwise branch out at the index where they differ.
// 到这里说明n.Key没有被完全匹配
branch := &fullNode{flags: t.newFlag()}
// 构建分支节点的两个分叉
var err error
_, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
if err != nil {
return false, nil, err
}
_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
if err != nil {
return false, nil, err
}
// Replace this shortNode with the branch if it occurs at index 0.
// 两者根本没有共同前缀,直接变成一个分支节点插入了两个shortNode
if matchlen == 0 {
return true, branch, nil
}
// Otherwise, replace it with a short node leading up to the branch.
// 使用两者的共同前缀,连接分支节点,分支节点连接两个分叉
return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
case *fullNode:
dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
return true, n, nil
// 向nil插入,直接生成一个叶子节点
case nil:
return true, &shortNode{key, value, t.newFlag()}, nil
// 先从数据库中加载出来再插入
case hashNode:
// We've hit a part of the trie that isn't loaded yet. Load
// the node and insert into it. This leaves all child nodes on
// the path to the value in the trie.
rn, err := t.resolveHash(n, prefix)
if err != nil {
return false, nil, err
}
dirty, nn, err := t.insert(rn, prefix, key, value)
// dirty=false也就是没修改所以返回rn(raw n)
if !dirty || err != nil {
return false, rn, err
}
// dirty=true 而且 err=nil,被修改了返回新的n也就是nn(new n)
return true, nn, nil
default:
panic(fmt.Sprintf("%T: invalid node: %v", n, n))
}
}
// Delete removes any existing value for key from the trie.
func (t *Trie) Delete(key []byte) {
if err := t.TryDelete(key); err != nil {
log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
}
}
// TryDelete removes any existing value for key from the trie.
// If a node was not found in the database, a MissingNodeError is returned.
func (t *Trie) TryDelete(key []byte) error {
t.unhashed++
k := keybytesToHex(key)
_, n, err := t.delete(t.root, nil, k)
if err != nil {
return err
}
t.root = n
return nil
}
// delete returns the new root of the trie with key deleted.
// It reduces the trie to minimal form by simplifying
// nodes on the way up after deleting recursively.
func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
switch n := n.(type) {
case *shortNode:
matchlen := prefixLen(key, n.Key)
// 不能完全匹配对于叶子结点还是扩展节点都说明接下去都搜索不到这个key了
// 不进行修改,直接返回原来的节点
if matchlen < len(n.Key) {
return false, n, nil // don't replace n on mismatch
}
// 这种情况key和n.Key完全一致,这个shortNode是一个叶子节点直接删除
if matchlen == len(key) {
return true, nil, nil // remove n entirely for whole matches
}
// The key is longer than n.Key. Remove the remaining suffix
// from the subtrie. Child can never be nil here since the
// subtrie must contain at least two other values with keys
// longer than n.Key.
// 这里的n是一个扩展节点,要向下搜索分支节点,进行删除
dirty, child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
// 没修改直接返回
if !dirty || err != nil {
return false, n, err
}
switch child := child.(type) {
// 将两个shortNode包含的前缀合并
case *shortNode:
// Deleting from the subtrie reduced it to another
// short node. Merge the nodes to avoid creating a
// shortNode{..., shortNode{...}}. Use concat (which
// always creates a new slice) instead of append to
// avoid modifying n.Key since it might be shared with
// other nodes.
return true, &shortNode{concat(n.Key, child.Key...), child.Val, t.newFlag()}, nil
// 其他类型直接设置n.Val为child即可
default:
return true, &shortNode{n.Key, child, t.newFlag()}, nil
}
case *fullNode:
dirty, nn, err := t.delete(n.Children[key[0]], append(prefix, key[0]), key[1:])
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
// Because n is a full node, it must've contained at least two children
// before the delete operation. If the new child value is non-nil, n still
// has at least two children after the deletion, and cannot be reduced to
// a short node.
if nn != nil {
return true, n, nil
}
// Reduction:
// Check how many non-nil entries are left after deleting and
// reduce the full node to a short node if only one entry is
// left. Since n must've contained at least two children
// before deletion (otherwise it would not be a full node) n
// can never be reduced to nil.
//
// When the loop is done, pos contains the index of the single
// value that is left in n or -2 if n contains at least two
// values.
// 检查分支节点里保存了几个分支,如果只有一个的话降级成shortNode
// pos为-2代表至少两个分支,否则保存了唯一一个分支的下标
pos := -1
for i, cld := range &n.Children {
if cld != nil {
if pos == -1 {
// 遇到第一个非nil,记录下标
pos = i
} else {
// 遇到了第二个非nil,设置为-2并且退出循环
pos = -2
break
}
}
}
if pos >= 0 {
if pos != 16 {
// If the remaining entry is a short node, it replaces
// n and its key gets the missing nibble tacked to the
// front. This avoids creating an invalid
// shortNode{..., shortNode{...}}. Since the entry
// might not be loaded yet, resolve it just for this
// check.
// pos不是16,剩的一个元素可能是shortNode也可能是fullNode
cnode, err := t.resolve(n.Children[pos], prefix)
if err != nil {
return false, nil, err
}
// 是shortNode就把分支的半字节和shortNode的前缀合并起来
if cnode, ok := cnode.(*shortNode); ok {
k := append([]byte{byte(pos)}, cnode.Key...)
return true, &shortNode{k, cnode.Val, t.newFlag()}, nil
}
}
// Otherwise, n is replaced by a one-nibble short node
// containing the child.
// 分支节点连接分支节点,将父分支节点修改为shortNode
return true, &shortNode{[]byte{byte(pos)}, n.Children[pos], t.newFlag()}, nil
}
// n still contains at least two values and cannot be reduced.
return true, n, nil
// 删除掉valueNode然后节点就变成了nil
case valueNode:
return true, nil, nil
// nil不能再删了
case nil:
return false, nil, nil
case hashNode:
// We've hit a part of the trie that isn't loaded yet. Load
// the node and delete from it. This leaves all child nodes on
// the path to the value in the trie.
rn, err := t.resolveHash(n, prefix)
if err != nil {
return false, nil, err
}
dirty, nn, err := t.delete(rn, prefix, key)
if !dirty || err != nil {
return false, rn, err
}
return true, nn, nil
default:
panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key))
}
}
// 先输入一个字节数组,后面可以根任意个字节变量作为参数
func concat(s1 []byte, s2 ...byte) []byte {
r := make([]byte, len(s1)+len(s2))
copy(r, s1)
copy(r[len(s1):], s2)
return r
}
// 用于解析hashNode,对resolveHash函数的封装->可以输入任意类型节点
// 其余类型的节点不进行处理
func (t *Trie) resolve(n node, prefix []byte) (node, error) {
if n, ok := n.(hashNode); ok {
return t.resolveHash(n, prefix)
}
return n, nil
}
// 输入hashNode,从数据库中读取原始节点信息
// 输入的prefix只是用来生成错误信息
func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
hash := common.BytesToHash(n)
if node := t.db.node(hash); node != nil {
return node, nil
}
return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
}
// Hash returns the root hash of the trie. It does not write to the
// database and can be used even if the trie doesn't have one.
// 计算整棵树的哈希,设置root为缓存树的根,并返回树根哈希
func (t *Trie) Hash() common.Hash {
hash, cached, _ := t.hashRoot()
t.root = cached
return common.BytesToHash(hash.(hashNode))
}
// Commit writes all nodes to the trie's memory database, tracking the internal
// and external (for account tries) references.
// 对树进行过插入删除等操作后调用Commit来提交到内存数据库中,也就是db.dirties中
// onleaf不为nil的话,树中的每个叶子节点都会调用一次onleaf
// t.root被修改为缓存树,返回树根的哈希
func (t *Trie) Commit(onleaf LeafCallback) (common.Hash, int, error) {
if t.db == nil {
panic("commit called on trie with nil database")
}
if t.root == nil {
return emptyRoot, 0, nil
}
// Derive the hash for all dirty nodes first. We hold the assumption
// in the following procedure that all nodes are hashed.
// Database的操作中都假设所有的节点都计算了哈希
// 所以这里首先计算整棵树的哈希
rootHash := t.Hash()
h := newCommitter()
defer returnCommitterToPool(h)
// Do a quick check if we really need to commit, before we spin
// up goroutines. This can happen e.g. if we load a trie for reading storage
// values, but don't write to it.
// dirty为false的时候没有必要提交
if _, dirty := t.root.cache(); !dirty {
return rootHash, 0, nil
}
var wg sync.WaitGroup
if onleaf != nil {
h.onleaf = onleaf
h.leafCh = make(chan *leaf, leafChanSize)
wg.Add(1)
go func() {
defer wg.Done()
// 监听leafCh
h.commitLoop(t.db)
}()
}
// 这里会不断向leafCh输入,由上面的commitLoop进行处理
newRoot, committed, err := h.Commit(t.root, t.db)
if onleaf != nil {
// The leafch is created in newCommitter if there was an onleaf callback
// provided. The commitLoop only _reads_ from it, and the commit
// operation was the sole writer. Therefore, it's safe to close this
// channel here.
// 到这里Commit执行完了,关闭leafCh,commitLoop可以继续读取
close(h.leafCh)
// 等待commitLoop执行完成
wg.Wait()
}
if err != nil {
return common.Hash{}, 0, err
}
// 让t.root变成hashNode
t.root = newRoot
return rootHash, committed, nil
}
// hashRoot calculates the root hash of the given trie
// 计算给定梅克尔树的根哈希,使用强制哈希,返回的树根一定是hashNode
// 分别返回树根的hashNode以及缓存树
func (t *Trie) hashRoot() (node, node, error) {
if t.root == nil {
return hashNode(emptyRoot.Bytes()), nil, nil
}
// If the number of changes is below 100, we let one thread handle it
h := newHasher(t.unhashed >= 100)
defer returnHasherToPool(h)
// 强制哈希,输入的树根不管编码是不是小于32都计算哈希
hashed, cached := h.hash(t.root, true)
t.unhashed = 0
return hashed, cached, nil
}
// Reset drops the referenced root node and cleans all internal state.
func (t *Trie) Reset() {
t.root = nil
t.unhashed = 0
}