From f7417d3552de86f5acf969b6eb882502fd104a11 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 18 Nov 2014 12:02:13 +0100 Subject: New modified patricia trie --- ptrie/fullnode.go | 59 +++++++++++ ptrie/hashnode.go | 22 +++++ ptrie/node.go | 40 ++++++++ ptrie/shortnode.go | 31 ++++++ ptrie/trie.go | 286 +++++++++++++++++++++++++++++++++++++++++++++++++++++ ptrie/trie_test.go | 138 ++++++++++++++++++++++++++ ptrie/valuenode.go | 13 +++ 7 files changed, 589 insertions(+) create mode 100644 ptrie/fullnode.go create mode 100644 ptrie/hashnode.go create mode 100644 ptrie/node.go create mode 100644 ptrie/shortnode.go create mode 100644 ptrie/trie.go create mode 100644 ptrie/trie_test.go create mode 100644 ptrie/valuenode.go (limited to 'ptrie') diff --git a/ptrie/fullnode.go b/ptrie/fullnode.go new file mode 100644 index 000000000..2b1a62789 --- /dev/null +++ b/ptrie/fullnode.go @@ -0,0 +1,59 @@ +package ptrie + +type FullNode struct { + trie *Trie + nodes [17]Node +} + +func NewFullNode(t *Trie) *FullNode { + return &FullNode{trie: t} +} + +func (self *FullNode) Dirty() bool { return true } +func (self *FullNode) Value() Node { + self.nodes[16] = self.trie.trans(self.nodes[16]) + return self.nodes[16] +} + +func (self *FullNode) Copy() Node { return self } + +// Returns the length of non-nil nodes +func (self *FullNode) Len() (amount int) { + for _, node := range self.nodes { + if node != nil { + amount++ + } + } + + return +} + +func (self *FullNode) Hash() interface{} { + return self.trie.store(self) +} + +func (self *FullNode) RlpData() interface{} { + t := make([]interface{}, 17) + for i, node := range self.nodes { + if node != nil { + t[i] = node.Hash() + } else { + t[i] = "" + } + } + + return t +} + +func (self *FullNode) set(k byte, value Node) { + self.nodes[int(k)] = value +} + +func (self *FullNode) get(i byte) Node { + if self.nodes[int(i)] != nil { + self.nodes[int(i)] = self.trie.trans(self.nodes[int(i)]) + + return self.nodes[int(i)] + } + return nil +} diff --git a/ptrie/hashnode.go b/ptrie/hashnode.go new file mode 100644 index 000000000..4c17569d7 --- /dev/null +++ b/ptrie/hashnode.go @@ -0,0 +1,22 @@ +package ptrie + +type HashNode struct { + key []byte +} + +func NewHash(key []byte) *HashNode { + return &HashNode{key} +} + +func (self *HashNode) RlpData() interface{} { + return self.key +} + +func (self *HashNode) Hash() interface{} { + return self.key +} + +// These methods will never be called but we have to satisfy Node interface +func (self *HashNode) Value() Node { return nil } +func (self *HashNode) Dirty() bool { return true } +func (self *HashNode) Copy() Node { return self } diff --git a/ptrie/node.go b/ptrie/node.go new file mode 100644 index 000000000..2c85dbce7 --- /dev/null +++ b/ptrie/node.go @@ -0,0 +1,40 @@ +package ptrie + +import "fmt" + +var indices = []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "[17]"} + +type Node interface { + Value() Node + Copy() Node // All nodes, for now, return them self + Dirty() bool + fstring(string) string + Hash() interface{} + RlpData() interface{} +} + +// Value node +func (self *ValueNode) String() string { return self.fstring("") } +func (self *FullNode) String() string { return self.fstring("") } +func (self *ShortNode) String() string { return self.fstring("") } +func (self *ValueNode) fstring(ind string) string { return fmt.Sprintf("%s ", self.data) } +func (self *HashNode) fstring(ind string) string { return fmt.Sprintf("%x ", self.key) } + +// Full node +func (self *FullNode) fstring(ind string) string { + resp := fmt.Sprintf("[\n%s ", ind) + for i, node := range self.nodes { + if node == nil { + resp += fmt.Sprintf("%s: ", indices[i]) + } else { + resp += fmt.Sprintf("%s: %v", indices[i], node.fstring(ind+" ")) + } + } + + return resp + fmt.Sprintf("\n%s] ", ind) +} + +// Short node +func (self *ShortNode) fstring(ind string) string { + return fmt.Sprintf("[ %s: %v ] ", self.key, self.value.fstring(ind+" ")) +} diff --git a/ptrie/shortnode.go b/ptrie/shortnode.go new file mode 100644 index 000000000..49319c555 --- /dev/null +++ b/ptrie/shortnode.go @@ -0,0 +1,31 @@ +package ptrie + +import "github.com/ethereum/go-ethereum/trie" + +type ShortNode struct { + trie *Trie + key []byte + value Node +} + +func NewShortNode(t *Trie, key []byte, value Node) *ShortNode { + return &ShortNode{t, []byte(trie.CompactEncode(key)), value} +} +func (self *ShortNode) Value() Node { + self.value = self.trie.trans(self.value) + + return self.value +} +func (self *ShortNode) Dirty() bool { return true } +func (self *ShortNode) Copy() Node { return self } + +func (self *ShortNode) RlpData() interface{} { + return []interface{}{self.key, self.value.Hash()} +} +func (self *ShortNode) Hash() interface{} { + return self.trie.store(self) +} + +func (self *ShortNode) Key() []byte { + return trie.CompactDecode(string(self.key)) +} diff --git a/ptrie/trie.go b/ptrie/trie.go new file mode 100644 index 000000000..3e642b334 --- /dev/null +++ b/ptrie/trie.go @@ -0,0 +1,286 @@ +package ptrie + +import ( + "bytes" + "sync" + + "github.com/ethereum/go-ethereum/crypto" + "github.com/ethereum/go-ethereum/ethutil" + "github.com/ethereum/go-ethereum/trie" +) + +type Backend interface { + Get([]byte) []byte + Set([]byte, []byte) +} + +type Cache map[string][]byte + +func (self Cache) Get(key []byte) []byte { + return self[string(key)] +} +func (self Cache) Set(key []byte, data []byte) { + self[string(key)] = data +} + +type Trie struct { + mu sync.Mutex + root Node + roothash []byte + backend Backend +} + +func NewEmpty() *Trie { + return &Trie{sync.Mutex{}, nil, nil, make(Cache)} +} + +func New(root []byte, backend Backend) *Trie { + trie := &Trie{} + trie.roothash = root + trie.backend = backend + + value := ethutil.NewValueFromBytes(trie.backend.Get(root)) + trie.root = trie.mknode(value) + + return trie +} + +func (self *Trie) Hash() []byte { + var hash []byte + if self.root != nil { + t := self.root.Hash() + if byts, ok := t.([]byte); ok { + hash = byts + } else { + hash = crypto.Sha3(ethutil.Encode(self.root.RlpData())) + } + } else { + hash = crypto.Sha3(ethutil.Encode(self.root)) + } + + self.roothash = hash + + return hash +} + +func (self *Trie) UpdateString(key, value string) Node { return self.Update([]byte(key), []byte(value)) } +func (self *Trie) Update(key, value []byte) Node { + self.mu.Lock() + defer self.mu.Unlock() + + k := trie.CompactHexDecode(string(key)) + + if len(value) != 0 { + self.root = self.insert(self.root, k, &ValueNode{self, value}) + } else { + self.root = self.delete(self.root, k) + } + + return self.root +} + +func (self *Trie) GetString(key string) []byte { return self.Get([]byte(key)) } +func (self *Trie) Get(key []byte) []byte { + self.mu.Lock() + defer self.mu.Unlock() + + k := trie.CompactHexDecode(string(key)) + + n := self.get(self.root, k) + if n != nil { + return n.(*ValueNode).Val() + } + + return nil +} + +func (self *Trie) DeleteString(key string) Node { return self.Delete([]byte(key)) } +func (self *Trie) Delete(key []byte) Node { + self.mu.Lock() + defer self.mu.Unlock() + + k := trie.CompactHexDecode(string(key)) + self.root = self.delete(self.root, k) + + return self.root +} + +func (self *Trie) insert(node Node, key []byte, value Node) Node { + if len(key) == 0 { + return value + } + + if node == nil { + return NewShortNode(self, key, value) + } + + switch node := node.(type) { + case *ShortNode: + k := node.Key() + cnode := node.Value() + if bytes.Equal(k, key) { + return NewShortNode(self, key, value) + } + + var n Node + matchlength := trie.MatchingNibbleLength(key, k) + if matchlength == len(k) { + n = self.insert(cnode, key[matchlength:], value) + } else { + pnode := self.insert(nil, k[matchlength+1:], cnode) + nnode := self.insert(nil, key[matchlength+1:], value) + fulln := NewFullNode(self) + fulln.set(k[matchlength], pnode) + fulln.set(key[matchlength], nnode) + n = fulln + } + if matchlength == 0 { + return n + } + + return NewShortNode(self, key[:matchlength], n) + + case *FullNode: + cpy := node.Copy().(*FullNode) + cpy.set(key[0], self.insert(node.get(key[0]), key[1:], value)) + + return cpy + + default: + panic("Invalid node") + } +} + +func (self *Trie) get(node Node, key []byte) Node { + if len(key) == 0 { + return node + } + + if node == nil { + return nil + } + + switch node := node.(type) { + case *ShortNode: + k := node.Key() + cnode := node.Value() + + if len(key) >= len(k) && bytes.Equal(k, key[:len(k)]) { + return self.get(cnode, key[len(k):]) + } + + return nil + case *FullNode: + return self.get(node.get(key[0]), key[1:]) + default: + panic("Invalid node") + } +} + +func (self *Trie) delete(node Node, key []byte) Node { + if len(key) == 0 { + return nil + } + + switch node := node.(type) { + case *ShortNode: + k := node.Key() + cnode := node.Value() + if bytes.Equal(key, k) { + return nil + } else if bytes.Equal(key[:len(k)], k) { + child := self.delete(cnode, key[len(k):]) + + var n Node + switch child := child.(type) { + case *ShortNode: + nkey := append(k, child.Key()...) + n = NewShortNode(self, nkey, child.Value()) + case *FullNode: + n = NewShortNode(self, node.key, child) + } + + return n + } else { + return node + } + + case *FullNode: + n := node.Copy().(*FullNode) + n.set(key[0], self.delete(n.get(key[0]), key[1:])) + + pos := -1 + for i := 0; i < 17; i++ { + if n.get(byte(i)) != nil { + if pos == -1 { + pos = i + } else { + pos = -2 + } + } + } + + var nnode Node + if pos == 16 { + nnode = NewShortNode(self, []byte{16}, n.get(byte(pos))) + } else if pos >= 0 { + cnode := n.get(byte(pos)) + switch cnode := cnode.(type) { + case *ShortNode: + // Stitch keys + k := append([]byte{byte(pos)}, cnode.Key()...) + nnode = NewShortNode(self, k, cnode.Value()) + case *FullNode: + nnode = NewShortNode(self, []byte{byte(pos)}, n.get(byte(pos))) + } + } else { + nnode = n + } + + return nnode + + default: + panic("Invalid node") + } +} + +// casting functions and cache storing +func (self *Trie) mknode(value *ethutil.Value) Node { + l := value.Len() + switch l { + case 2: + return NewShortNode(self, trie.CompactDecode(string(value.Get(0).Bytes())), self.mknode(value.Get(1))) + case 17: + fnode := NewFullNode(self) + for i := 0; i < l; i++ { + fnode.set(byte(i), self.mknode(value.Get(i))) + } + return fnode + case 32: + return &HashNode{value.Bytes()} + default: + return &ValueNode{self, value.Bytes()} + } +} + +func (self *Trie) trans(node Node) Node { + switch node := node.(type) { + case *HashNode: + value := ethutil.NewValueFromBytes(self.backend.Get(node.key)) + return self.mknode(value) + default: + return node + } +} + +func (self *Trie) store(node Node) interface{} { + data := ethutil.Encode(node) + if len(data) >= 32 { + key := crypto.Sha3(data) + self.backend.Set(key, data) + + return key + } + + return node.RlpData() +} diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go new file mode 100644 index 000000000..29380d3f0 --- /dev/null +++ b/ptrie/trie_test.go @@ -0,0 +1,138 @@ +package ptrie + +import ( + "bytes" + "fmt" + "testing" + + "github.com/ethereum/go-ethereum/ethutil" +) + +func TestInsert(t *testing.T) { + trie := NewEmpty() + + trie.UpdateString("doe", "reindeer") + trie.UpdateString("dog", "puppy") + trie.UpdateString("dogglesworth", "cat") + + exp := ethutil.Hex2Bytes("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3") + root := trie.Hash() + if !bytes.Equal(root, exp) { + t.Errorf("exp %x got %x", exp, root) + } + + trie = NewEmpty() + trie.UpdateString("A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") + + exp = ethutil.Hex2Bytes("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab") + root = trie.Hash() + if !bytes.Equal(root, exp) { + t.Errorf("exp %x got %x", exp, root) + } +} + +func TestGet(t *testing.T) { + trie := NewEmpty() + + trie.UpdateString("doe", "reindeer") + trie.UpdateString("dog", "puppy") + trie.UpdateString("dogglesworth", "cat") + + res := trie.GetString("dog") + if !bytes.Equal(res, []byte("puppy")) { + t.Errorf("expected puppy got %x", res) + } + + unknown := trie.GetString("unknown") + if unknown != nil { + t.Errorf("expected nil got %x", unknown) + } +} + +func TestDelete(t *testing.T) { + trie := NewEmpty() + + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + } + for _, val := range vals { + trie.UpdateString(val.k, val.v) + } + + hash := trie.Hash() + exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84") + if !bytes.Equal(hash, exp) { + t.Errorf("expected %x got %x", exp, hash) + } +} + +func TestReplication(t *testing.T) { + trie := NewEmpty() + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + {"somethingveryoddindeedthis is", "myothernodedata"}, + } + for _, val := range vals { + trie.UpdateString(val.k, val.v) + } + trie.Hash() + + trie2 := New(trie.roothash, trie.backend) + if string(trie2.GetString("horse")) != "stallion" { + t.Error("expected to have harse => stallion") + } + + hash := trie2.Hash() + exp := trie.Hash() + if !bytes.Equal(hash, exp) { + t.Errorf("root failure. expected %x got %x", exp, hash) + } + +} + +func BenchmarkGets(b *testing.B) { + trie := NewEmpty() + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + {"somethingveryoddindeedthis is", "myothernodedata"}, + } + for _, val := range vals { + trie.UpdateString(val.k, val.v) + } + + b.ResetTimer() + for i := 0; i < b.N; i++ { + trie.Get([]byte("horse")) + } +} + +func BenchmarkUpdate(b *testing.B) { + trie := NewEmpty() + + b.ResetTimer() + for i := 0; i < b.N; i++ { + trie.UpdateString(fmt.Sprintf("aaaaaaaaaaaaaaa%d", j), "value") + } + trie.Hash() +} diff --git a/ptrie/valuenode.go b/ptrie/valuenode.go new file mode 100644 index 000000000..c226621a7 --- /dev/null +++ b/ptrie/valuenode.go @@ -0,0 +1,13 @@ +package ptrie + +type ValueNode struct { + trie *Trie + data []byte +} + +func (self *ValueNode) Value() Node { return self } // Best not to call :-) +func (self *ValueNode) Val() []byte { return self.data } +func (self *ValueNode) Dirty() bool { return true } +func (self *ValueNode) Copy() Node { return self } +func (self *ValueNode) RlpData() interface{} { return self.data } +func (self *ValueNode) Hash() interface{} { return self.data } -- cgit v1.2.3 From e08aba5dd9f1e481aab18c6c062c97e0e400f75b Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 18 Nov 2014 12:18:27 +0100 Subject: added output test --- ptrie/trie.go | 2 ++ ptrie/trie_test.go | 19 ++++++++++++++++++- 2 files changed, 20 insertions(+), 1 deletion(-) (limited to 'ptrie') diff --git a/ptrie/trie.go b/ptrie/trie.go index 3e642b334..207aad91e 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -45,6 +45,8 @@ func New(root []byte, backend Backend) *Trie { return trie } +// Legacy support +func (self *Trie) Root() []byte { return self.Hash() } func (self *Trie) Hash() []byte { var hash []byte if self.root != nil { diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index 29380d3f0..8b98f4408 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -132,7 +132,24 @@ func BenchmarkUpdate(b *testing.B) { b.ResetTimer() for i := 0; i < b.N; i++ { - trie.UpdateString(fmt.Sprintf("aaaaaaaaaaaaaaa%d", j), "value") + trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", base, i), "value") } trie.Hash() } + +// Not actual test +func TestOutput(t *testing.T) { + base := "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + trie := NewEmpty() + for i := 0; i < 50; i++ { + trie.UpdateString(fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee") + } + trie.Hash() + fmt.Println("############################## FULL ################################") + fmt.Println(trie.root) + + trie2 := New(trie.roothash, trie.backend) + trie2.GetString(base + "20") + fmt.Println("############################## SMALL ################################") + fmt.Println(trie2.root) +} -- cgit v1.2.3 From 93e693be72e1a7734e826016316434c1e2320de9 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 18 Nov 2014 19:52:45 +0100 Subject: Fixed tests for 'types' --- ptrie/trie_test.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'ptrie') diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index 8b98f4408..6cdd2bde4 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -132,7 +132,7 @@ func BenchmarkUpdate(b *testing.B) { b.ResetTimer() for i := 0; i < b.N; i++ { - trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", base, i), "value") + trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", i), "value") } trie.Hash() } -- cgit v1.2.3 From e70529a97785012368e7e0d5b272cccab705e551 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 19 Nov 2014 15:05:08 +0100 Subject: Added new iterator and tests --- ptrie/fullnode.go | 5 ++- ptrie/iterator.go | 114 +++++++++++++++++++++++++++++++++++++++++++++++++ ptrie/iterator_test.go | 28 ++++++++++++ ptrie/trie.go | 18 +++++--- ptrie/trie_test.go | 2 + 5 files changed, 159 insertions(+), 8 deletions(-) create mode 100644 ptrie/iterator.go create mode 100644 ptrie/iterator_test.go (limited to 'ptrie') diff --git a/ptrie/fullnode.go b/ptrie/fullnode.go index 2b1a62789..eaa4611b6 100644 --- a/ptrie/fullnode.go +++ b/ptrie/fullnode.go @@ -14,6 +14,9 @@ func (self *FullNode) Value() Node { self.nodes[16] = self.trie.trans(self.nodes[16]) return self.nodes[16] } +func (self *FullNode) Branches() []Node { + return self.nodes[:16] +} func (self *FullNode) Copy() Node { return self } @@ -49,7 +52,7 @@ func (self *FullNode) set(k byte, value Node) { self.nodes[int(k)] = value } -func (self *FullNode) get(i byte) Node { +func (self *FullNode) branch(i byte) Node { if self.nodes[int(i)] != nil { self.nodes[int(i)] = self.trie.trans(self.nodes[int(i)]) diff --git a/ptrie/iterator.go b/ptrie/iterator.go new file mode 100644 index 000000000..c6d4f64a0 --- /dev/null +++ b/ptrie/iterator.go @@ -0,0 +1,114 @@ +package ptrie + +import ( + "bytes" + + "github.com/ethereum/go-ethereum/trie" +) + +type Iterator struct { + trie *Trie + + Key []byte + Value []byte +} + +func NewIterator(trie *Trie) *Iterator { + return &Iterator{trie: trie, Key: []byte{0}} +} + +func (self *Iterator) Next() bool { + self.trie.mu.Lock() + defer self.trie.mu.Unlock() + + key := trie.RemTerm(trie.CompactHexDecode(string(self.Key))) + k := self.next(self.trie.root, key) + + self.Key = []byte(trie.DecodeCompact(k)) + + return len(k) > 0 + +} + +func (self *Iterator) next(node Node, key []byte) []byte { + if node == nil { + return nil + } + + switch node := node.(type) { + case *FullNode: + if len(key) > 0 { + k := self.next(node.branch(key[0]), key[1:]) + if k != nil { + return append([]byte{key[0]}, k...) + } + } + + var r byte + if len(key) > 0 { + r = key[0] + 1 + } + + for i := r; i < 16; i++ { + k := self.key(node.branch(byte(i))) + if k != nil { + return append([]byte{i}, k...) + } + } + + case *ShortNode: + k := trie.RemTerm(node.Key()) + if vnode, ok := node.Value().(*ValueNode); ok { + if bytes.Compare([]byte(k), key) > 0 { + self.Value = vnode.Val() + return k + } + } else { + cnode := node.Value() + skey := key[len(k):] + + var ret []byte + if trie.BeginsWith(key, k) { + ret = self.next(cnode, skey) + } else if bytes.Compare(k, key[:len(k)]) > 0 { + ret = self.key(node) + } + + if ret != nil { + return append(k, ret...) + } + } + } + + return nil +} + +func (self *Iterator) key(node Node) []byte { + switch node := node.(type) { + case *ShortNode: + // Leaf node + if vnode, ok := node.Value().(*ValueNode); ok { + k := trie.RemTerm(node.Key()) + self.Value = vnode.Val() + + return k + } else { + return self.key(node.Value()) + } + case *FullNode: + if node.Value() != nil { + self.Value = node.Value().(*ValueNode).Val() + + return []byte{16} + } + + for i := 0; i < 16; i++ { + k := self.key(node.branch(byte(i))) + if k != nil { + return append([]byte{byte(i)}, k...) + } + } + } + + return nil +} diff --git a/ptrie/iterator_test.go b/ptrie/iterator_test.go new file mode 100644 index 000000000..8921bb670 --- /dev/null +++ b/ptrie/iterator_test.go @@ -0,0 +1,28 @@ +package ptrie + +import "testing" + +func TestIterator(t *testing.T) { + trie := NewEmpty() + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + } + v := make(map[string]bool) + for _, val := range vals { + v[val.k] = false + trie.UpdateString(val.k, val.v) + } + + it := trie.Iterator() + for it.Next() { + v[string(it.Key)] = true + } + + for k, found := range v { + if !found { + t.Error("iterator didn't find", k) + } + } +} diff --git a/ptrie/trie.go b/ptrie/trie.go index 207aad91e..bb2b3845a 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -45,6 +45,10 @@ func New(root []byte, backend Backend) *Trie { return trie } +func (self *Trie) Iterator() *Iterator { + return NewIterator(self) +} + // Legacy support func (self *Trie) Root() []byte { return self.Hash() } func (self *Trie) Hash() []byte { @@ -144,7 +148,7 @@ func (self *Trie) insert(node Node, key []byte, value Node) Node { case *FullNode: cpy := node.Copy().(*FullNode) - cpy.set(key[0], self.insert(node.get(key[0]), key[1:], value)) + cpy.set(key[0], self.insert(node.branch(key[0]), key[1:], value)) return cpy @@ -173,7 +177,7 @@ func (self *Trie) get(node Node, key []byte) Node { return nil case *FullNode: - return self.get(node.get(key[0]), key[1:]) + return self.get(node.branch(key[0]), key[1:]) default: panic("Invalid node") } @@ -209,11 +213,11 @@ func (self *Trie) delete(node Node, key []byte) Node { case *FullNode: n := node.Copy().(*FullNode) - n.set(key[0], self.delete(n.get(key[0]), key[1:])) + n.set(key[0], self.delete(n.branch(key[0]), key[1:])) pos := -1 for i := 0; i < 17; i++ { - if n.get(byte(i)) != nil { + if n.branch(byte(i)) != nil { if pos == -1 { pos = i } else { @@ -224,16 +228,16 @@ func (self *Trie) delete(node Node, key []byte) Node { var nnode Node if pos == 16 { - nnode = NewShortNode(self, []byte{16}, n.get(byte(pos))) + nnode = NewShortNode(self, []byte{16}, n.branch(byte(pos))) } else if pos >= 0 { - cnode := n.get(byte(pos)) + cnode := n.branch(byte(pos)) switch cnode := cnode.(type) { case *ShortNode: // Stitch keys k := append([]byte{byte(pos)}, cnode.Key()...) nnode = NewShortNode(self, k, cnode.Value()) case *FullNode: - nnode = NewShortNode(self, []byte{byte(pos)}, n.get(byte(pos))) + nnode = NewShortNode(self, []byte{byte(pos)}, n.branch(byte(pos))) } } else { nnode = n diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index 6cdd2bde4..6af6e1b40 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -139,6 +139,8 @@ func BenchmarkUpdate(b *testing.B) { // Not actual test func TestOutput(t *testing.T) { + t.Skip() + base := "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" trie := NewEmpty() for i := 0; i < 50; i++ { -- cgit v1.2.3 From 0f460ad26e864ae8b4c4cf99147c5b57a10f3be9 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 19 Nov 2014 16:21:28 +0100 Subject: Added caching and database interface to trie * Reimplemented caching for trie * Reimplemented resetting and persisting trie --- ptrie/fullnode.go | 9 ++++++- ptrie/shortnode.go | 2 +- ptrie/trie.go | 77 ++++++++++++++++++++++++++++++++++++++++++----------- ptrie/trie_test.go | 78 ++++++++++++++++++++++++++++++++++++++++-------------- ptrie/valuenode.go | 2 +- 5 files changed, 130 insertions(+), 38 deletions(-) (limited to 'ptrie') diff --git a/ptrie/fullnode.go b/ptrie/fullnode.go index eaa4611b6..7a7f7d22d 100644 --- a/ptrie/fullnode.go +++ b/ptrie/fullnode.go @@ -18,7 +18,14 @@ func (self *FullNode) Branches() []Node { return self.nodes[:16] } -func (self *FullNode) Copy() Node { return self } +func (self *FullNode) Copy() Node { + nnode := NewFullNode(self.trie) + for i, node := range self.nodes { + nnode.nodes[i] = node + } + + return nnode +} // Returns the length of non-nil nodes func (self *FullNode) Len() (amount int) { diff --git a/ptrie/shortnode.go b/ptrie/shortnode.go index 49319c555..73ff2914b 100644 --- a/ptrie/shortnode.go +++ b/ptrie/shortnode.go @@ -17,7 +17,7 @@ func (self *ShortNode) Value() Node { return self.value } func (self *ShortNode) Dirty() bool { return true } -func (self *ShortNode) Copy() Node { return self } +func (self *ShortNode) Copy() Node { return NewShortNode(self.trie, self.key, self.value) } func (self *ShortNode) RlpData() interface{} { return []interface{}{self.key, self.value.Hash()} diff --git a/ptrie/trie.go b/ptrie/trie.go index bb2b3845a..687126aef 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -2,6 +2,7 @@ package ptrie import ( "bytes" + "container/list" "sync" "github.com/ethereum/go-ethereum/crypto" @@ -14,33 +15,61 @@ type Backend interface { Set([]byte, []byte) } -type Cache map[string][]byte +type Cache struct { + store map[string][]byte + backend Backend +} + +func NewCache(backend Backend) *Cache { + return &Cache{make(map[string][]byte), backend} +} + +func (self *Cache) Get(key []byte) []byte { + data := self.store[string(key)] + if data == nil { + data = self.backend.Get(key) + } + + return data +} + +func (self *Cache) Set(key []byte, data []byte) { + self.store[string(key)] = data +} + +func (self *Cache) Flush() { + for k, v := range self.store { + self.backend.Set([]byte(k), v) + } -func (self Cache) Get(key []byte) []byte { - return self[string(key)] + // This will eventually grow too large. We'd could + // do a make limit on storage and push out not-so-popular nodes. + //self.Reset() } -func (self Cache) Set(key []byte, data []byte) { - self[string(key)] = data + +func (self *Cache) Reset() { + self.store = make(map[string][]byte) } type Trie struct { mu sync.Mutex root Node roothash []byte - backend Backend -} + cache *Cache -func NewEmpty() *Trie { - return &Trie{sync.Mutex{}, nil, nil, make(Cache)} + revisions *list.List } func New(root []byte, backend Backend) *Trie { trie := &Trie{} + trie.revisions = list.New() trie.roothash = root - trie.backend = backend + trie.cache = NewCache(backend) - value := ethutil.NewValueFromBytes(trie.backend.Get(root)) - trie.root = trie.mknode(value) + if root != nil { + value := ethutil.NewValueFromBytes(trie.cache.Get(root)) + trie.root = trie.mknode(value) + } return trie } @@ -64,10 +93,28 @@ func (self *Trie) Hash() []byte { hash = crypto.Sha3(ethutil.Encode(self.root)) } - self.roothash = hash + if !bytes.Equal(hash, self.roothash) { + self.revisions.PushBack(self.roothash) + self.roothash = hash + } return hash } +func (self *Trie) Commit() { + // Hash first + self.Hash() + + self.cache.Flush() +} + +func (self *Trie) Reset() { + self.cache.Reset() + + revision := self.revisions.Remove(self.revisions.Back()).([]byte) + self.roothash = revision + value := ethutil.NewValueFromBytes(self.cache.Get(self.roothash)) + self.root = self.mknode(value) +} func (self *Trie) UpdateString(key, value string) Node { return self.Update([]byte(key), []byte(value)) } func (self *Trie) Update(key, value []byte) Node { @@ -272,7 +319,7 @@ func (self *Trie) mknode(value *ethutil.Value) Node { func (self *Trie) trans(node Node) Node { switch node := node.(type) { case *HashNode: - value := ethutil.NewValueFromBytes(self.backend.Get(node.key)) + value := ethutil.NewValueFromBytes(self.cache.Get(node.key)) return self.mknode(value) default: return node @@ -283,7 +330,7 @@ func (self *Trie) store(node Node) interface{} { data := ethutil.Encode(node) if len(data) >= 32 { key := crypto.Sha3(data) - self.backend.Set(key, data) + self.cache.Set(key, data) return key } diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index 6af6e1b40..478f59c60 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -8,6 +8,16 @@ import ( "github.com/ethereum/go-ethereum/ethutil" ) +type Db map[string][]byte + +func (self Db) Get(k []byte) []byte { return self[string(k)] } +func (self Db) Set(k, v []byte) { self[string(k)] = v } + +// Used for testing +func NewEmpty() *Trie { + return New(nil, make(Db)) +} + func TestInsert(t *testing.T) { trie := NewEmpty() @@ -91,7 +101,7 @@ func TestReplication(t *testing.T) { } trie.Hash() - trie2 := New(trie.roothash, trie.backend) + trie2 := New(trie.roothash, trie.cache) if string(trie2.GetString("horse")) != "stallion" { t.Error("expected to have harse => stallion") } @@ -104,37 +114,32 @@ func TestReplication(t *testing.T) { } -func BenchmarkGets(b *testing.B) { +func TestReset(t *testing.T) { trie := NewEmpty() vals := []struct{ k, v string }{ {"do", "verb"}, {"ether", "wookiedoo"}, {"horse", "stallion"}, - {"shaman", "horse"}, - {"doge", "coin"}, - {"ether", ""}, - {"dog", "puppy"}, - {"shaman", ""}, - {"somethingveryoddindeedthis is", "myothernodedata"}, } for _, val := range vals { trie.UpdateString(val.k, val.v) } + trie.Commit() - b.ResetTimer() - for i := 0; i < b.N; i++ { - trie.Get([]byte("horse")) - } -} + before := ethutil.CopyBytes(trie.roothash) + trie.UpdateString("should", "revert") + trie.Hash() + // Should have no effect + trie.Hash() + trie.Hash() + // ### -func BenchmarkUpdate(b *testing.B) { - trie := NewEmpty() + trie.Reset() + after := ethutil.CopyBytes(trie.roothash) - b.ResetTimer() - for i := 0; i < b.N; i++ { - trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", i), "value") + if !bytes.Equal(before, after) { + t.Errorf("expected roots to be equal. %x - %x", before, after) } - trie.Hash() } // Not actual test @@ -150,8 +155,41 @@ func TestOutput(t *testing.T) { fmt.Println("############################## FULL ################################") fmt.Println(trie.root) - trie2 := New(trie.roothash, trie.backend) + trie2 := New(trie.roothash, trie.cache) trie2.GetString(base + "20") fmt.Println("############################## SMALL ################################") fmt.Println(trie2.root) } + +func BenchmarkGets(b *testing.B) { + trie := NewEmpty() + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + {"somethingveryoddindeedthis is", "myothernodedata"}, + } + for _, val := range vals { + trie.UpdateString(val.k, val.v) + } + + b.ResetTimer() + for i := 0; i < b.N; i++ { + trie.Get([]byte("horse")) + } +} + +func BenchmarkUpdate(b *testing.B) { + trie := NewEmpty() + + b.ResetTimer() + for i := 0; i < b.N; i++ { + trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", i), "value") + } + trie.Hash() +} diff --git a/ptrie/valuenode.go b/ptrie/valuenode.go index c226621a7..c593eb6c6 100644 --- a/ptrie/valuenode.go +++ b/ptrie/valuenode.go @@ -8,6 +8,6 @@ type ValueNode struct { func (self *ValueNode) Value() Node { return self } // Best not to call :-) func (self *ValueNode) Val() []byte { return self.data } func (self *ValueNode) Dirty() bool { return true } -func (self *ValueNode) Copy() Node { return self } +func (self *ValueNode) Copy() Node { return &ValueNode{self.trie, self.data} } func (self *ValueNode) RlpData() interface{} { return self.data } func (self *ValueNode) Hash() interface{} { return self.data } -- cgit v1.2.3 From cab7e6000e20413d697d07a1a6b2abcc85dfc2e1 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 19 Nov 2014 16:35:57 +0100 Subject: Increased coverage --- ptrie/cache.go | 42 ++++++++++++++++++++++++++++++++++++++ ptrie/trie.go | 59 ++++++++++-------------------------------------------- ptrie/trie_test.go | 40 +++++++++++++++++++++++++++++++++++- 3 files changed, 92 insertions(+), 49 deletions(-) create mode 100644 ptrie/cache.go (limited to 'ptrie') diff --git a/ptrie/cache.go b/ptrie/cache.go new file mode 100644 index 000000000..8efdb047b --- /dev/null +++ b/ptrie/cache.go @@ -0,0 +1,42 @@ +package ptrie + +type Backend interface { + Get([]byte) []byte + Set([]byte, []byte) +} + +type Cache struct { + store map[string][]byte + backend Backend +} + +func NewCache(backend Backend) *Cache { + return &Cache{make(map[string][]byte), backend} +} + +func (self *Cache) Get(key []byte) []byte { + data := self.store[string(key)] + if data == nil { + data = self.backend.Get(key) + } + + return data +} + +func (self *Cache) Set(key []byte, data []byte) { + self.store[string(key)] = data +} + +func (self *Cache) Flush() { + for k, v := range self.store { + self.backend.Set([]byte(k), v) + } + + // This will eventually grow too large. We'd could + // do a make limit on storage and push out not-so-popular nodes. + //self.Reset() +} + +func (self *Cache) Reset() { + self.store = make(map[string][]byte) +} diff --git a/ptrie/trie.go b/ptrie/trie.go index 687126aef..0ef498b10 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -10,47 +10,6 @@ import ( "github.com/ethereum/go-ethereum/trie" ) -type Backend interface { - Get([]byte) []byte - Set([]byte, []byte) -} - -type Cache struct { - store map[string][]byte - backend Backend -} - -func NewCache(backend Backend) *Cache { - return &Cache{make(map[string][]byte), backend} -} - -func (self *Cache) Get(key []byte) []byte { - data := self.store[string(key)] - if data == nil { - data = self.backend.Get(key) - } - - return data -} - -func (self *Cache) Set(key []byte, data []byte) { - self.store[string(key)] = data -} - -func (self *Cache) Flush() { - for k, v := range self.store { - self.backend.Set([]byte(k), v) - } - - // This will eventually grow too large. We'd could - // do a make limit on storage and push out not-so-popular nodes. - //self.Reset() -} - -func (self *Cache) Reset() { - self.store = make(map[string][]byte) -} - type Trie struct { mu sync.Mutex root Node @@ -83,14 +42,17 @@ func (self *Trie) Root() []byte { return self.Hash() } func (self *Trie) Hash() []byte { var hash []byte if self.root != nil { - t := self.root.Hash() - if byts, ok := t.([]byte); ok { - hash = byts - } else { - hash = crypto.Sha3(ethutil.Encode(self.root.RlpData())) - } + hash = self.root.Hash().([]byte) + /* + t := self.root.Hash() + if byts, ok := t.([]byte); ok { + hash = byts + } else { + hash = crypto.Sha3(ethutil.Encode(self.root.RlpData())) + } + */ } else { - hash = crypto.Sha3(ethutil.Encode(self.root)) + hash = crypto.Sha3(ethutil.Encode("")) } if !bytes.Equal(hash, self.roothash) { @@ -107,6 +69,7 @@ func (self *Trie) Commit() { self.cache.Flush() } +// Reset should only be called if the trie has been hashed func (self *Trie) Reset() { self.cache.Reset() diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index 478f59c60..aed16a2ff 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -5,6 +5,7 @@ import ( "fmt" "testing" + "github.com/ethereum/go-ethereum/crypto" "github.com/ethereum/go-ethereum/ethutil" ) @@ -18,6 +19,15 @@ func NewEmpty() *Trie { return New(nil, make(Db)) } +func TestEmptyTrie(t *testing.T) { + trie := NewEmpty() + res := trie.Hash() + exp := crypto.Sha3(ethutil.Encode("")) + if !bytes.Equal(res, exp) { + t.Errorf("expected %x got %x", exp, res) + } +} + func TestInsert(t *testing.T) { trie := NewEmpty() @@ -62,6 +72,34 @@ func TestGet(t *testing.T) { func TestDelete(t *testing.T) { trie := NewEmpty() + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + } + for _, val := range vals { + if val.v != "" { + trie.UpdateString(val.k, val.v) + } else { + trie.DeleteString(val.k) + } + } + + hash := trie.Hash() + exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84") + if !bytes.Equal(hash, exp) { + t.Errorf("expected %x got %x", exp, hash) + } +} + +func TestEmptyValues(t *testing.T) { + trie := NewEmpty() + vals := []struct{ k, v string }{ {"do", "verb"}, {"ether", "wookiedoo"}, @@ -142,7 +180,7 @@ func TestReset(t *testing.T) { } } -// Not actual test +// Not an actual test func TestOutput(t *testing.T) { t.Skip() -- cgit v1.2.3 From b05e63c34d335e65c8c76ed9a9401b74170db617 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 19 Nov 2014 16:56:01 +0100 Subject: Added paranoia check for tries --- ptrie/cache.go | 10 +++++----- ptrie/trie.go | 13 ++++++++++++- ptrie/trie_test.go | 35 +++++++++++++++++++++++++++++++---- 3 files changed, 48 insertions(+), 10 deletions(-) (limited to 'ptrie') diff --git a/ptrie/cache.go b/ptrie/cache.go index 8efdb047b..721dc4cf6 100644 --- a/ptrie/cache.go +++ b/ptrie/cache.go @@ -1,8 +1,8 @@ package ptrie type Backend interface { - Get([]byte) []byte - Set([]byte, []byte) + Get([]byte) ([]byte, error) + Put([]byte, []byte) } type Cache struct { @@ -17,19 +17,19 @@ func NewCache(backend Backend) *Cache { func (self *Cache) Get(key []byte) []byte { data := self.store[string(key)] if data == nil { - data = self.backend.Get(key) + data, _ = self.backend.Get(key) } return data } -func (self *Cache) Set(key []byte, data []byte) { +func (self *Cache) Put(key []byte, data []byte) { self.store[string(key)] = data } func (self *Cache) Flush() { for k, v := range self.store { - self.backend.Set([]byte(k), v) + self.backend.Put([]byte(k), v) } // This will eventually grow too large. We'd could diff --git a/ptrie/trie.go b/ptrie/trie.go index 0ef498b10..4b0f20d8c 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -10,6 +10,17 @@ import ( "github.com/ethereum/go-ethereum/trie" ) +func ParanoiaCheck(t1 *Trie, backend Backend) (bool, *Trie) { + t2 := New(nil, backend) + + it := t1.Iterator() + for it.Next() { + t2.Update(it.Key, it.Value) + } + + return bytes.Compare(t2.Hash(), t1.Hash()) == 0, t2 +} + type Trie struct { mu sync.Mutex root Node @@ -293,7 +304,7 @@ func (self *Trie) store(node Node) interface{} { data := ethutil.Encode(node) if len(data) >= 32 { key := crypto.Sha3(data) - self.cache.Set(key, data) + self.cache.Put(key, data) return key } diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index aed16a2ff..dfc89709d 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -11,8 +11,8 @@ import ( type Db map[string][]byte -func (self Db) Get(k []byte) []byte { return self[string(k)] } -func (self Db) Set(k, v []byte) { self[string(k)] = v } +func (self Db) Get(k []byte) ([]byte, error) { return self[string(k)], nil } +func (self Db) Put(k, v []byte) { self[string(k)] = v } // Used for testing func NewEmpty() *Trie { @@ -122,6 +122,7 @@ func TestEmptyValues(t *testing.T) { } func TestReplication(t *testing.T) { + t.Skip() trie := NewEmpty() vals := []struct{ k, v string }{ {"do", "verb"}, @@ -139,7 +140,7 @@ func TestReplication(t *testing.T) { } trie.Hash() - trie2 := New(trie.roothash, trie.cache) + trie2 := New(trie.roothash, trie.cache.backend) if string(trie2.GetString("horse")) != "stallion" { t.Error("expected to have harse => stallion") } @@ -180,6 +181,32 @@ func TestReset(t *testing.T) { } } +func TestParanoia(t *testing.T) { + t.Skip() + trie := NewEmpty() + + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + {"somethingveryoddindeedthis is", "myothernodedata"}, + } + for _, val := range vals { + trie.UpdateString(val.k, val.v) + } + trie.Commit() + + ok, t2 := ParanoiaCheck(trie, trie.cache.backend) + if !ok { + t.Errorf("trie paranoia check failed %x %x", trie.roothash, t2.roothash) + } +} + // Not an actual test func TestOutput(t *testing.T) { t.Skip() @@ -193,7 +220,7 @@ func TestOutput(t *testing.T) { fmt.Println("############################## FULL ################################") fmt.Println(trie.root) - trie2 := New(trie.roothash, trie.cache) + trie2 := New(trie.roothash, trie.cache.backend) trie2.GetString(base + "20") fmt.Println("############################## SMALL ################################") fmt.Println(trie2.root) -- cgit v1.2.3 From 12f1aea38d6f9dd9748a95b2d9ea813ae16277a7 Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 20 Nov 2014 18:11:31 +0100 Subject: Fixed iterator for short nodes. In some cases the iterator didn't properly return the correct key because it didn't append fields to the reverse lookup. --- ptrie/iterator.go | 5 +++-- ptrie/iterator_test.go | 5 +++++ ptrie/trie_test.go | 3 +-- 3 files changed, 9 insertions(+), 4 deletions(-) (limited to 'ptrie') diff --git a/ptrie/iterator.go b/ptrie/iterator.go index c6d4f64a0..5714bdbc8 100644 --- a/ptrie/iterator.go +++ b/ptrie/iterator.go @@ -65,9 +65,9 @@ func (self *Iterator) next(node Node, key []byte) []byte { } } else { cnode := node.Value() - skey := key[len(k):] var ret []byte + skey := key[len(k):] if trie.BeginsWith(key, k) { ret = self.next(cnode, skey) } else if bytes.Compare(k, key[:len(k)]) > 0 { @@ -93,7 +93,8 @@ func (self *Iterator) key(node Node) []byte { return k } else { - return self.key(node.Value()) + k := trie.RemTerm(node.Key()) + return append(k, self.key(node.Value())...) } case *FullNode: if node.Value() != nil { diff --git a/ptrie/iterator_test.go b/ptrie/iterator_test.go index 8921bb670..acfc03d63 100644 --- a/ptrie/iterator_test.go +++ b/ptrie/iterator_test.go @@ -8,12 +8,17 @@ func TestIterator(t *testing.T) { {"do", "verb"}, {"ether", "wookiedoo"}, {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"dog", "puppy"}, + {"somethingveryoddindeedthis is", "myothernodedata"}, } v := make(map[string]bool) for _, val := range vals { v[val.k] = false trie.UpdateString(val.k, val.v) } + trie.Commit() it := trie.Iterator() for it.Next() { diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index dfc89709d..ba50f50a5 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -122,7 +122,6 @@ func TestEmptyValues(t *testing.T) { } func TestReplication(t *testing.T) { - t.Skip() trie := NewEmpty() vals := []struct{ k, v string }{ {"do", "verb"}, @@ -138,7 +137,7 @@ func TestReplication(t *testing.T) { for _, val := range vals { trie.UpdateString(val.k, val.v) } - trie.Hash() + trie.Commit() trie2 := New(trie.roothash, trie.cache.backend) if string(trie2.GetString("horse")) != "stallion" { -- cgit v1.2.3 From 9b8a12b4b53f319f6422a43e43b2274a337d7fec Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 20 Nov 2014 18:20:04 +0100 Subject: Removed naively casting to bytes --- ptrie/trie.go | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) (limited to 'ptrie') diff --git a/ptrie/trie.go b/ptrie/trie.go index 4b0f20d8c..7701966e5 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -53,15 +53,13 @@ func (self *Trie) Root() []byte { return self.Hash() } func (self *Trie) Hash() []byte { var hash []byte if self.root != nil { - hash = self.root.Hash().([]byte) - /* - t := self.root.Hash() - if byts, ok := t.([]byte); ok { - hash = byts - } else { - hash = crypto.Sha3(ethutil.Encode(self.root.RlpData())) - } - */ + //hash = self.root.Hash().([]byte) + t := self.root.Hash() + if byts, ok := t.([]byte); ok { + hash = byts + } else { + hash = crypto.Sha3(ethutil.Encode(self.root.RlpData())) + } } else { hash = crypto.Sha3(ethutil.Encode("")) } -- cgit v1.2.3 From 8cf9ed0ea588e97f2baf0f834248727e8fbca18f Mon Sep 17 00:00:00 2001 From: obscuren Date: Fri, 21 Nov 2014 10:48:07 -0500 Subject: Fixed test --- ptrie/trie.go | 3 ++- ptrie/trie_test.go | 4 ++-- 2 files changed, 4 insertions(+), 3 deletions(-) (limited to 'ptrie') diff --git a/ptrie/trie.go b/ptrie/trie.go index 7701966e5..9fe9ea52a 100644 --- a/ptrie/trie.go +++ b/ptrie/trie.go @@ -3,6 +3,7 @@ package ptrie import ( "bytes" "container/list" + "fmt" "sync" "github.com/ethereum/go-ethereum/crypto" @@ -198,7 +199,7 @@ func (self *Trie) get(node Node, key []byte) Node { case *FullNode: return self.get(node.branch(key[0]), key[1:]) default: - panic("Invalid node") + panic(fmt.Sprintf("%T: invalid node: %v", node, node)) } } diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go index ba50f50a5..5b1c64140 100644 --- a/ptrie/trie_test.go +++ b/ptrie/trie_test.go @@ -215,13 +215,13 @@ func TestOutput(t *testing.T) { for i := 0; i < 50; i++ { trie.UpdateString(fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee") } - trie.Hash() fmt.Println("############################## FULL ################################") fmt.Println(trie.root) + trie.Commit() + fmt.Println("############################## SMALL ################################") trie2 := New(trie.roothash, trie.cache.backend) trie2.GetString(base + "20") - fmt.Println("############################## SMALL ################################") fmt.Println(trie2.root) } -- cgit v1.2.3