diff options
author | obscuren <geffobscura@gmail.com> | 2015-03-06 00:46:11 +0800 |
---|---|---|
committer | obscuren <geffobscura@gmail.com> | 2015-03-06 00:46:11 +0800 |
commit | 72bf02bf15d01fad45bbdf586f294d939c9d7fd6 (patch) | |
tree | 2a7bd70f0268c8641f463d67ff59c18f3bdf2cf8 /trie | |
parent | 201b09f99af11ea23e9cb5170a65867d026aedc9 (diff) | |
parent | 357d17ae58e6570278a3ed78a754a4ac1c346d74 (diff) | |
download | dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.tar dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.tar.gz dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.tar.bz2 dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.tar.lz dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.tar.xz dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.tar.zst dexon-72bf02bf15d01fad45bbdf586f294d939c9d7fd6.zip |
Merge branch 'tendermint-develop_pull_request' into develop
Diffstat (limited to 'trie')
-rw-r--r-- | trie/iterator.go | 28 | ||||
-rw-r--r-- | trie/trie_test.go | 3 |
2 files changed, 22 insertions, 9 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 4b185f355..21a1eb11f 100644 --- a/trie/trie_test.go +++ b/trie/trie_test.go @@ -267,14 +267,13 @@ 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) trie.Update(value2.k, value2.v) vals[string(value.k)] = value vals[string(value2.k)] = value2 - fmt.Println(value, "\n", value2) } it := trie.Iterator() |