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/trie.go | 286 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 286 insertions(+) create mode 100644 ptrie/trie.go (limited to 'ptrie/trie.go') 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() +} -- 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 ++ 1 file changed, 2 insertions(+) (limited to 'ptrie/trie.go') 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 { -- 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/trie.go | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) (limited to 'ptrie/trie.go') 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 -- 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/trie.go | 77 +++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 62 insertions(+), 15 deletions(-) (limited to 'ptrie/trie.go') 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 } -- 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/trie.go | 59 +++++++++++------------------------------------------------ 1 file changed, 11 insertions(+), 48 deletions(-) (limited to 'ptrie/trie.go') 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() -- 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/trie.go | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) (limited to 'ptrie/trie.go') 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 } -- 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/trie.go') 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 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'ptrie/trie.go') 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)) } } -- cgit v1.2.3