aboutsummaryrefslogtreecommitdiffstats
path: root/trie/iterator.go
diff options
context:
space:
mode:
Diffstat (limited to 'trie/iterator.go')
-rw-r--r--trie/iterator.go243
1 files changed, 136 insertions, 107 deletions
diff --git a/trie/iterator.go b/trie/iterator.go
index 26ae1d5ad..76146c0d6 100644
--- a/trie/iterator.go
+++ b/trie/iterator.go
@@ -24,14 +24,13 @@ import (
"github.com/ethereum/go-ethereum/common"
)
-var iteratorEnd = errors.New("end of iteration")
-
// Iterator is a key-value trie iterator that traverses a Trie.
type Iterator struct {
nodeIt NodeIterator
Key []byte // Current data key on which the iterator is positioned on
Value []byte // Current data value on which the iterator is positioned on
+ Err error
}
// NewIterator creates a new key-value iterator from a node iterator
@@ -45,35 +44,42 @@ func NewIterator(it NodeIterator) *Iterator {
func (it *Iterator) Next() bool {
for it.nodeIt.Next(true) {
if it.nodeIt.Leaf() {
- it.Key = hexToKeybytes(it.nodeIt.Path())
+ it.Key = it.nodeIt.LeafKey()
it.Value = it.nodeIt.LeafBlob()
return true
}
}
it.Key = nil
it.Value = nil
+ it.Err = it.nodeIt.Error()
return false
}
// NodeIterator is an iterator to traverse the trie pre-order.
type NodeIterator interface {
- // Hash returns the hash of the current node
- Hash() common.Hash
- // Parent returns the hash of the parent of the current node
- Parent() common.Hash
- // Leaf returns true iff the current node is a leaf node.
- Leaf() bool
- // LeafBlob returns the contents of the node, if it is a leaf.
- // Callers must not retain references to the return value after calling Next()
- LeafBlob() []byte
- // Path returns the hex-encoded path to the current node.
- // Callers must not retain references to the return value after calling Next()
- Path() []byte
// Next moves the iterator to the next node. If the parameter is false, any child
// nodes will be skipped.
Next(bool) bool
// Error returns the error status of the iterator.
Error() error
+
+ // Hash returns the hash of the current node.
+ Hash() common.Hash
+ // Parent returns the hash of the parent of the current node. The hash may be the one
+ // grandparent if the immediate parent is an internal node with no hash.
+ Parent() common.Hash
+ // Path returns the hex-encoded path to the current node.
+ // Callers must not retain references to the return value after calling Next.
+ // For leaf nodes, the last element of the path is the 'terminator symbol' 0x10.
+ Path() []byte
+
+ // Leaf returns true iff the current node is a leaf node.
+ // LeafBlob, LeafKey return the contents and key of the leaf node. These
+ // method panic if the iterator is not positioned at a leaf.
+ // Callers must not retain references to their return value after calling Next
+ Leaf() bool
+ LeafBlob() []byte
+ LeafKey() []byte
}
// nodeIteratorState represents the iteration state at one particular node of the
@@ -89,8 +95,21 @@ type nodeIteratorState struct {
type nodeIterator struct {
trie *Trie // Trie being iterated
stack []*nodeIteratorState // Hierarchy of trie nodes persisting the iteration state
- err error // Failure set in case of an internal error in the iterator
path []byte // Path to the current node
+ err error // Failure set in case of an internal error in the iterator
+}
+
+// iteratorEnd is stored in nodeIterator.err when iteration is done.
+var iteratorEnd = errors.New("end of iteration")
+
+// seekError is stored in nodeIterator.err if the initial seek has failed.
+type seekError struct {
+ key []byte
+ err error
+}
+
+func (e seekError) Error() string {
+ return "seek error: " + e.err.Error()
}
func newNodeIterator(trie *Trie, start []byte) NodeIterator {
@@ -98,60 +117,57 @@ func newNodeIterator(trie *Trie, start []byte) NodeIterator {
return new(nodeIterator)
}
it := &nodeIterator{trie: trie}
- it.seek(start)
+ it.err = it.seek(start)
return it
}
-// Hash returns the hash of the current node
func (it *nodeIterator) Hash() common.Hash {
if len(it.stack) == 0 {
return common.Hash{}
}
-
return it.stack[len(it.stack)-1].hash
}
-// Parent returns the hash of the parent node
func (it *nodeIterator) Parent() common.Hash {
if len(it.stack) == 0 {
return common.Hash{}
}
-
return it.stack[len(it.stack)-1].parent
}
-// Leaf returns true if the current node is a leaf
func (it *nodeIterator) Leaf() bool {
- if len(it.stack) == 0 {
- return false
- }
-
- _, ok := it.stack[len(it.stack)-1].node.(valueNode)
- return ok
+ return hasTerm(it.path)
}
-// LeafBlob returns the data for the current node, if it is a leaf
func (it *nodeIterator) LeafBlob() []byte {
- if len(it.stack) == 0 {
- return nil
+ if len(it.stack) > 0 {
+ if node, ok := it.stack[len(it.stack)-1].node.(valueNode); ok {
+ return []byte(node)
+ }
}
+ panic("not at leaf")
+}
- if node, ok := it.stack[len(it.stack)-1].node.(valueNode); ok {
- return []byte(node)
+func (it *nodeIterator) LeafKey() []byte {
+ if len(it.stack) > 0 {
+ if _, ok := it.stack[len(it.stack)-1].node.(valueNode); ok {
+ return hexToKeybytes(it.path)
+ }
}
- return nil
+ panic("not at leaf")
}
-// Path returns the hex-encoded path to the current node
func (it *nodeIterator) Path() []byte {
return it.path
}
-// Error returns the error set in case of an internal error in the iterator
func (it *nodeIterator) Error() error {
if it.err == iteratorEnd {
return nil
}
+ if seek, ok := it.err.(seekError); ok {
+ return seek.err
+ }
return it.err
}
@@ -160,29 +176,37 @@ func (it *nodeIterator) Error() error {
// sets the Error field to the encountered failure. If `descend` is false,
// skips iterating over any subnodes of the current node.
func (it *nodeIterator) Next(descend bool) bool {
- if it.err != nil {
+ if it.err == iteratorEnd {
return false
}
- // Otherwise step forward with the iterator and report any errors
+ if seek, ok := it.err.(seekError); ok {
+ if it.err = it.seek(seek.key); it.err != nil {
+ return false
+ }
+ }
+ // Otherwise step forward with the iterator and report any errors.
state, parentIndex, path, err := it.peek(descend)
- if err != nil {
- it.err = err
+ it.err = err
+ if it.err != nil {
return false
}
it.push(state, parentIndex, path)
return true
}
-func (it *nodeIterator) seek(prefix []byte) {
+func (it *nodeIterator) seek(prefix []byte) error {
// The path we're looking for is the hex encoded key without terminator.
key := keybytesToHex(prefix)
key = key[:len(key)-1]
// Move forward until we're just before the closest match to key.
for {
state, parentIndex, path, err := it.peek(bytes.HasPrefix(key, it.path))
- if err != nil || bytes.Compare(path, key) >= 0 {
- it.err = err
- return
+ if err == iteratorEnd {
+ return iteratorEnd
+ } else if err != nil {
+ return seekError{prefix, err}
+ } else if bytes.Compare(path, key) >= 0 {
+ return nil
}
it.push(state, parentIndex, path)
}
@@ -197,7 +221,8 @@ func (it *nodeIterator) peek(descend bool) (*nodeIteratorState, *int, []byte, er
if root != emptyRoot {
state.hash = root
}
- return state, nil, nil, nil
+ err := state.resolve(it.trie, nil)
+ return state, nil, nil, err
}
if !descend {
// If we're skipping children, pop the current node first
@@ -205,72 +230,73 @@ func (it *nodeIterator) peek(descend bool) (*nodeIteratorState, *int, []byte, er
}
// Continue iteration to the next child
- for {
- if len(it.stack) == 0 {
- return nil, nil, nil, iteratorEnd
- }
+ for len(it.stack) > 0 {
parent := it.stack[len(it.stack)-1]
ancestor := parent.hash
if (ancestor == common.Hash{}) {
ancestor = parent.parent
}
- if node, ok := parent.node.(*fullNode); ok {
- // Full node, move to the first non-nil child.
- for i := parent.index + 1; i < len(node.Children); i++ {
- child := node.Children[i]
- if child != nil {
- hash, _ := child.cache()
- state := &nodeIteratorState{
- hash: common.BytesToHash(hash),
- node: child,
- parent: ancestor,
- index: -1,
- pathlen: len(it.path),
- }
- path := append(it.path, byte(i))
- parent.index = i - 1
- return state, &parent.index, path, nil
- }
+ state, path, ok := it.nextChild(parent, ancestor)
+ if ok {
+ if err := state.resolve(it.trie, path); err != nil {
+ return parent, &parent.index, path, err
}
- } else if node, ok := parent.node.(*shortNode); ok {
- // Short node, return the pointer singleton child
- if parent.index < 0 {
- hash, _ := node.Val.cache()
+ return state, &parent.index, path, nil
+ }
+ // No more child nodes, move back up.
+ it.pop()
+ }
+ return nil, nil, nil, iteratorEnd
+}
+
+func (st *nodeIteratorState) resolve(tr *Trie, path []byte) error {
+ if hash, ok := st.node.(hashNode); ok {
+ resolved, err := tr.resolveHash(hash, path)
+ if err != nil {
+ return err
+ }
+ st.node = resolved
+ st.hash = common.BytesToHash(hash)
+ }
+ return nil
+}
+
+func (it *nodeIterator) nextChild(parent *nodeIteratorState, ancestor common.Hash) (*nodeIteratorState, []byte, bool) {
+ switch node := parent.node.(type) {
+ case *fullNode:
+ // Full node, move to the first non-nil child.
+ for i := parent.index + 1; i < len(node.Children); i++ {
+ child := node.Children[i]
+ if child != nil {
+ hash, _ := child.cache()
state := &nodeIteratorState{
hash: common.BytesToHash(hash),
- node: node.Val,
+ node: child,
parent: ancestor,
index: -1,
pathlen: len(it.path),
}
- var path []byte
- if hasTerm(node.Key) {
- path = append(it.path, node.Key[:len(node.Key)-1]...)
- } else {
- path = append(it.path, node.Key...)
- }
- return state, &parent.index, path, nil
+ path := append(it.path, byte(i))
+ parent.index = i - 1
+ return state, path, true
}
- } else if hash, ok := parent.node.(hashNode); ok {
- // Hash node, resolve the hash child from the database
- if parent.index < 0 {
- node, err := it.trie.resolveHash(hash, nil, nil)
- if err != nil {
- return it.stack[len(it.stack)-1], &parent.index, it.path, err
- }
- state := &nodeIteratorState{
- hash: common.BytesToHash(hash),
- node: node,
- parent: ancestor,
- index: -1,
- pathlen: len(it.path),
- }
- return state, &parent.index, it.path, nil
+ }
+ case *shortNode:
+ // Short node, return the pointer singleton child
+ if parent.index < 0 {
+ hash, _ := node.Val.cache()
+ state := &nodeIteratorState{
+ hash: common.BytesToHash(hash),
+ node: node.Val,
+ parent: ancestor,
+ index: -1,
+ pathlen: len(it.path),
}
+ path := append(it.path, node.Key...)
+ return state, path, true
}
- // No more child nodes, move back up.
- it.pop()
}
+ return parent, it.path, false
}
func (it *nodeIterator) push(state *nodeIteratorState, parentIndex *int, path []byte) {
@@ -288,23 +314,21 @@ func (it *nodeIterator) pop() {
}
func compareNodes(a, b NodeIterator) int {
- cmp := bytes.Compare(a.Path(), b.Path())
- if cmp != 0 {
+ if cmp := bytes.Compare(a.Path(), b.Path()); cmp != 0 {
return cmp
}
-
if a.Leaf() && !b.Leaf() {
return -1
} else if b.Leaf() && !a.Leaf() {
return 1
}
-
- cmp = bytes.Compare(a.Hash().Bytes(), b.Hash().Bytes())
- if cmp != 0 {
+ if cmp := bytes.Compare(a.Hash().Bytes(), b.Hash().Bytes()); cmp != 0 {
return cmp
}
-
- return bytes.Compare(a.LeafBlob(), b.LeafBlob())
+ if a.Leaf() && b.Leaf() {
+ return bytes.Compare(a.LeafBlob(), b.LeafBlob())
+ }
+ return 0
}
type differenceIterator struct {
@@ -341,6 +365,10 @@ func (it *differenceIterator) LeafBlob() []byte {
return it.b.LeafBlob()
}
+func (it *differenceIterator) LeafKey() []byte {
+ return it.b.LeafKey()
+}
+
func (it *differenceIterator) Path() []byte {
return it.b.Path()
}
@@ -410,7 +438,6 @@ func (h *nodeIteratorHeap) Pop() interface{} {
type unionIterator struct {
items *nodeIteratorHeap // Nodes returned are the union of the ones in these iterators
count int // Number of nodes scanned across all tries
- err error // The error, if one has been encountered
}
// NewUnionIterator constructs a NodeIterator that iterates over elements in the union
@@ -421,9 +448,7 @@ func NewUnionIterator(iters []NodeIterator) (NodeIterator, *int) {
copy(h, iters)
heap.Init(&h)
- ui := &unionIterator{
- items: &h,
- }
+ ui := &unionIterator{items: &h}
return ui, &ui.count
}
@@ -443,6 +468,10 @@ func (it *unionIterator) LeafBlob() []byte {
return (*it.items)[0].LeafBlob()
}
+func (it *unionIterator) LeafKey() []byte {
+ return (*it.items)[0].LeafKey()
+}
+
func (it *unionIterator) Path() []byte {
return (*it.items)[0].Path()
}
generated by cgit (git 2.34.1) at 2024-11-13 00:36:39 +0800