aboutsummaryrefslogtreecommitdiffstats
path: root/trie/iterator.go
diff options
context:
space:
mode:
authorPéter Szilágyi <peterke@gmail.com>2015-12-28 21:20:37 +0800
committerPéter Szilágyi <peterke@gmail.com>2016-02-16 18:21:08 +0800
commit7e29b0b5b4e5cf7ded9a5a75789de6f8121caec9 (patch)
treeb1470ba733e04490fb797edce652a3cca802972e /trie/iterator.go
parent4f28c5b69d652e12adf8a88f526f459a492e159e (diff)
downloaddexon-7e29b0b5b4e5cf7ded9a5a75789de6f8121caec9.tar.gz
dexon-7e29b0b5b4e5cf7ded9a5a75789de6f8121caec9.tar.zst
dexon-7e29b0b5b4e5cf7ded9a5a75789de6f8121caec9.zip
core/state, trie: add node iterator, test state/trie sync consistency
Diffstat (limited to 'trie/iterator.go')
-rw-r--r--trie/iterator.go120
1 files changed, 117 insertions, 3 deletions
diff --git a/trie/iterator.go b/trie/iterator.go
index 5f205e081..e79de2e4e 100644
--- a/trie/iterator.go
+++ b/trie/iterator.go
@@ -18,22 +18,26 @@ package trie
import (
"bytes"
+ "fmt"
"github.com/ethereum/go-ethereum/logger"
"github.com/ethereum/go-ethereum/logger/glog"
)
+// Iterator is a key-value trie iterator to traverse the data contents.
type Iterator struct {
trie *Trie
- Key []byte
- Value []byte
+ Key []byte // Current data key on which the iterator is positioned on
+ Value []byte // Current data value on which the iterator is positioned on
}
+// NewIterator creates a new key-value iterator.
func NewIterator(trie *Trie) *Iterator {
return &Iterator{trie: trie, Key: nil}
}
+// Next moves the iterator forward with one key-value entry.
func (self *Iterator) Next() bool {
isIterStart := false
if self.Key == nil {
@@ -142,6 +146,116 @@ func (self *Iterator) key(node interface{}) []byte {
}
return self.key(rn)
}
-
return nil
}
+
+// 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
+}
+
+// NodeIterator is an iterator to traverse the trie post-order.
+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)
+}
+
+// NewNodeIterator creates an post-order trie iterator.
+func NewNodeIterator(trie *Trie) *NodeIterator {
+ if bytes.Compare(trie.Root(), emptyRoot.Bytes()) == 0 {
+ return new(NodeIterator)
+ }
+ return &NodeIterator{trie: trie}
+}
+
+// Next moves the iterator to the next node, returning whether there are any
+// further nodes.
+func (it *NodeIterator) Next() bool {
+ it.step()
+ return it.retrieve()
+}
+
+// step moves the iterator to the next node of the trie.
+func (it *NodeIterator) step() {
+ // Abort if we reached the end of the iteration
+ if it.trie == nil {
+ return
+ }
+ // Initialize the iterator if we've just started, or pop off the old node otherwise
+ if len(it.stack) == 0 {
+ it.stack = append(it.stack, &nodeIteratorState{node: it.trie.root, child: -1})
+ if it.stack[0].node == nil {
+ panic(fmt.Sprintf("root node missing: %x", it.trie.Root()))
+ }
+ } else {
+ it.stack = it.stack[:len(it.stack)-1]
+ if len(it.stack) == 0 {
+ it.trie = nil
+ return
+ }
+ }
+ // Continue iteration to the next child
+ for {
+ parent := it.stack[len(it.stack)-1]
+ if node, ok := parent.node.(fullNode); ok {
+ // Full node, traverse all children, then the node itself
+ if parent.child >= len(node) {
+ break
+ }
+ for parent.child++; parent.child < len(node); parent.child++ {
+ if current := node[parent.child]; current != nil {
+ it.stack = append(it.stack, &nodeIteratorState{node: current, child: -1})
+ break
+ }
+ }
+ } else if node, ok := parent.node.(shortNode); ok {
+ // Short node, traverse the pointer singleton child, then the node itself
+ if parent.child >= 0 {
+ break
+ }
+ parent.child++
+ it.stack = append(it.stack, &nodeIteratorState{node: node.Val, child: -1})
+ } else if node, 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)
+ if err != nil {
+ panic(err)
+ }
+ it.stack = append(it.stack, &nodeIteratorState{node: node, child: -1})
+ } else {
+ break
+ }
+ }
+}
+
+// retrieve pulls and caches the current trie node the iterator is traversing.
+// In case of a value node, the additional leaf blob is also populated with the
+// data contents for external interpretation.
+//
+// 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
+
+ // 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
+ if value, ok := it.Node.(valueNode); ok {
+ it.Leaf, it.LeafBlob = true, []byte(value)
+ }
+ return true
+}