aboutsummaryrefslogtreecommitdiffstats
path: root/trie
diff options
context:
space:
mode:
authorobscuren <geffobscura@gmail.com>2015-03-06 00:46:40 +0800
committerobscuren <geffobscura@gmail.com>2015-03-06 00:46:40 +0800
commitd44fe4ec627f0aecdb891b5ae415b8c89315d131 (patch)
tree4e7795792711da0b545129b0f18ad0930886e9a5 /trie
parent377c8a13de3405424f16a67c2f3ae3485290a0ca (diff)
parent72bf02bf15d01fad45bbdf586f294d939c9d7fd6 (diff)
downloadgo-tangerine-d44fe4ec627f0aecdb891b5ae415b8c89315d131.tar.gz
go-tangerine-d44fe4ec627f0aecdb891b5ae415b8c89315d131.tar.zst
go-tangerine-d44fe4ec627f0aecdb891b5ae415b8c89315d131.zip
Merge branch 'develop' into poc-9
Diffstat (limited to 'trie')
-rw-r--r--trie/iterator.go28
-rw-r--r--trie/trie_test.go2
2 files changed, 22 insertions, 8 deletions
diff --git a/trie/iterator.go b/trie/iterator.go
index 3b3ddd751..fda7c6cbe 100644
--- a/trie/iterator.go
+++ b/trie/iterator.go
@@ -1,6 +1,8 @@
package trie
-import "bytes"
+import (
+ "bytes"
+)
type Iterator struct {
trie *Trie
@@ -10,22 +12,28 @@ type Iterator struct {
}
func NewIterator(trie *Trie) *Iterator {
- return &Iterator{trie: trie, Key: make([]byte, 32)}
+ return &Iterator{trie: trie, Key: nil}
}
func (self *Iterator) Next() bool {
self.trie.mu.Lock()
defer self.trie.mu.Unlock()
+ isIterStart := false
+ if self.Key == nil {
+ isIterStart = true
+ self.Key = make([]byte, 32)
+ }
+
key := RemTerm(CompactHexDecode(string(self.Key)))
- k := self.next(self.trie.root, key)
+ k := self.next(self.trie.root, key, isIterStart)
self.Key = []byte(DecodeCompact(k))
return len(k) > 0
}
-func (self *Iterator) next(node Node, key []byte) []byte {
+func (self *Iterator) next(node Node, key []byte, isIterStart bool) []byte {
if node == nil {
return nil
}
@@ -33,7 +41,7 @@ func (self *Iterator) next(node Node, key []byte) []byte {
switch node := node.(type) {
case *FullNode:
if len(key) > 0 {
- k := self.next(node.branch(key[0]), key[1:])
+ k := self.next(node.branch(key[0]), key[1:], isIterStart)
if k != nil {
return append([]byte{key[0]}, k...)
}
@@ -54,7 +62,13 @@ func (self *Iterator) next(node Node, key []byte) []byte {
case *ShortNode:
k := RemTerm(node.Key())
if vnode, ok := node.Value().(*ValueNode); ok {
- if bytes.Compare([]byte(k), key) > 0 {
+ switch bytes.Compare([]byte(k), key) {
+ case 0:
+ if isIterStart {
+ self.Value = vnode.Val()
+ return k
+ }
+ case 1:
self.Value = vnode.Val()
return k
}
@@ -64,7 +78,7 @@ func (self *Iterator) next(node Node, key []byte) []byte {
var ret []byte
skey := key[len(k):]
if BeginsWith(key, k) {
- ret = self.next(cnode, skey)
+ ret = self.next(cnode, skey, isIterStart)
} else if bytes.Compare(k, key[:len(k)]) > 0 {
return self.key(node)
}
diff --git a/trie/trie_test.go b/trie/trie_test.go
index 92e0df8e2..b6a260483 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -271,7 +271,7 @@ func TestLargeData(t *testing.T) {
trie := NewEmpty()
vals := make(map[string]*kv)
- for i := byte(1); i < 255; i++ {
+ for i := byte(0); i < 255; i++ {
value := &kv{ethutil.LeftPadBytes([]byte{i}, 32), []byte{i}, false}
value2 := &kv{ethutil.LeftPadBytes([]byte{10, i}, 32), []byte{i}, false}
trie.Update(value.k, value.v)