aboutsummaryrefslogtreecommitdiffstats
path: root/trie
diff options
context:
space:
mode:
Diffstat (limited to 'trie')
-rw-r--r--trie/iterator.go25
-rw-r--r--trie/iterator_test.go32
-rw-r--r--trie/sync_test.go3
3 files changed, 47 insertions, 13 deletions
diff --git a/trie/iterator.go b/trie/iterator.go
index e79de2e4e..12ca96bd1 100644
--- a/trie/iterator.go
+++ b/trie/iterator.go
@@ -20,6 +20,7 @@ import (
"bytes"
"fmt"
+ "github.com/ethereum/go-ethereum/common"
"github.com/ethereum/go-ethereum/logger"
"github.com/ethereum/go-ethereum/logger/glog"
)
@@ -152,8 +153,9 @@ func (self *Iterator) key(node interface{}) []byte {
// nodeIteratorState represents the iteration state at one particular node of the
// trie, which can be resumed at a later invocation.
type nodeIteratorState struct {
- node node // Trie node being iterated
- child int // Child to be processed next
+ hash common.Hash // Hash of the node being iterated (nil if not standalone)
+ node node // Trie node being iterated
+ child int // Child to be processed next
}
// NodeIterator is an iterator to traverse the trie post-order.
@@ -161,9 +163,10 @@ type NodeIterator struct {
trie *Trie // Trie being iterated
stack []*nodeIteratorState // Hierarchy of trie nodes persisting the iteration state
- Node node // Current node being iterated (internal representation)
- Leaf bool // Flag whether the current node is a value (data) node
- LeafBlob []byte // Data blob contained within a leaf (otherwise nil)
+ Hash common.Hash // Hash of the current node being iterated (nil if not standalone)
+ Node node // Current node being iterated (internal representation)
+ Leaf bool // Flag whether the current node is a value (data) node
+ LeafBlob []byte // Data blob contained within a leaf (otherwise nil)
}
// NewNodeIterator creates an post-order trie iterator.
@@ -221,18 +224,18 @@ func (it *NodeIterator) step() {
}
parent.child++
it.stack = append(it.stack, &nodeIteratorState{node: node.Val, child: -1})
- } else if node, ok := parent.node.(hashNode); ok {
+ } else if hash, ok := parent.node.(hashNode); ok {
// Hash node, resolve the hash child from the database, then the node itself
if parent.child >= 0 {
break
}
parent.child++
- node, err := it.trie.resolveHash(node, nil, nil)
+ node, err := it.trie.resolveHash(hash, nil, nil)
if err != nil {
panic(err)
}
- it.stack = append(it.stack, &nodeIteratorState{node: node, child: -1})
+ it.stack = append(it.stack, &nodeIteratorState{hash: common.BytesToHash(hash), node: node, child: -1})
} else {
break
}
@@ -246,14 +249,16 @@ func (it *NodeIterator) step() {
// The method returns whether there are any more data left for inspection.
func (it *NodeIterator) retrieve() bool {
// Clear out any previously set values
- it.Node, it.Leaf, it.LeafBlob = nil, false, nil
+ it.Hash, it.Node, it.Leaf, it.LeafBlob = common.Hash{}, nil, false, nil
// If the iteration's done, return no available data
if it.trie == nil {
return false
}
// Otherwise retrieve the current node and resolve leaf accessors
- it.Node = it.stack[len(it.stack)-1].node
+ state := it.stack[len(it.stack)-1]
+
+ it.Hash, it.Node = state.hash, state.node
if value, ok := it.Node.(valueNode); ok {
it.Leaf, it.LeafBlob = true, []byte(value)
}
diff --git a/trie/iterator_test.go b/trie/iterator_test.go
index fdc60b412..dc8276116 100644
--- a/trie/iterator_test.go
+++ b/trie/iterator_test.go
@@ -16,7 +16,12 @@
package trie
-import "testing"
+import (
+ "testing"
+
+ "github.com/ethereum/go-ethereum/common"
+ "github.com/ethereum/go-ethereum/ethdb"
+)
func TestIterator(t *testing.T) {
trie := newEmpty()
@@ -47,3 +52,28 @@ func TestIterator(t *testing.T) {
}
}
}
+
+// Tests that the node iterator indeed walks over the entire database contents.
+func TestNodeIteratorCoverage(t *testing.T) {
+ // Create some arbitrary test trie to iterate
+ db, trie, _ := makeTestTrie()
+
+ // Gather all the node hashes found by the iterator
+ hashes := make(map[common.Hash]struct{})
+ for it := NewNodeIterator(trie); it.Next(); {
+ if it.Hash != (common.Hash{}) {
+ hashes[it.Hash] = struct{}{}
+ }
+ }
+ // Cross check the hashes and the database itself
+ for hash, _ := range hashes {
+ if _, err := db.Get(hash.Bytes()); err != nil {
+ t.Errorf("failed to retrieve reported node %x: %v", hash, err)
+ }
+ }
+ for _, key := range db.(*ethdb.MemDatabase).Keys() {
+ if _, ok := hashes[common.BytesToHash(key)]; !ok {
+ t.Errorf("state entry not reported %x", key)
+ }
+ }
+}
diff --git a/trie/sync_test.go b/trie/sync_test.go
index 94d6edd68..ce098d5a0 100644
--- a/trie/sync_test.go
+++ b/trie/sync_test.go
@@ -96,8 +96,7 @@ func checkTrieConsistency(db Database, root common.Hash) (failure error) {
if err != nil {
return
}
- it := NewNodeIterator(trie)
- for it.Next() {
+ for it := NewNodeIterator(trie); it.Next(); {
}
return nil
}