From db4aaedcbdb409e17ea3de161e7b24a80ba0a58c Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 8 Jan 2015 11:47:04 +0100 Subject: Moved ptrie => trie. Removed old trie --- ptrie/cache.go | 42 ------- ptrie/fullnode.go | 77 ------------ ptrie/hashnode.go | 22 ---- ptrie/iterator.go | 115 ----------------- ptrie/iterator_test.go | 33 ----- ptrie/node.go | 40 ------ ptrie/shortnode.go | 31 ----- ptrie/trie.go | 335 ------------------------------------------------- ptrie/trie_test.go | 259 -------------------------------------- ptrie/valuenode.go | 13 -- 10 files changed, 967 deletions(-) delete mode 100644 ptrie/cache.go delete mode 100644 ptrie/fullnode.go delete mode 100644 ptrie/hashnode.go delete mode 100644 ptrie/iterator.go delete mode 100644 ptrie/iterator_test.go delete mode 100644 ptrie/node.go delete mode 100644 ptrie/shortnode.go delete mode 100644 ptrie/trie.go delete mode 100644 ptrie/trie_test.go delete mode 100644 ptrie/valuenode.go (limited to 'ptrie') diff --git a/ptrie/cache.go b/ptrie/cache.go deleted file mode 100644 index 721dc4cf6..000000000 --- a/ptrie/cache.go +++ /dev/null @@ -1,42 +0,0 @@ -package ptrie - -type Backend interface { - Get([]byte) ([]byte, error) - Put([]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) Put(key []byte, data []byte) { - self.store[string(key)] = data -} - -func (self *Cache) Flush() { - for k, v := range self.store { - self.backend.Put([]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/fullnode.go b/ptrie/fullnode.go deleted file mode 100644 index 4dd98049d..000000000 --- a/ptrie/fullnode.go +++ /dev/null @@ -1,77 +0,0 @@ -package ptrie - -import "fmt" - -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) Branches() []Node { - return self.nodes[:16] -} - -func (self *FullNode) Copy() Node { - nnode := NewFullNode(self.trie) - for i, node := range self.nodes { - if node != nil { - nnode.nodes[i] = node - } - } - - return nnode -} - -// 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) { - if _, ok := value.(*ValueNode); ok && k != 16 { - fmt.Println(value, k) - } - - self.nodes[int(k)] = value -} - -func (self *FullNode) branch(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 deleted file mode 100644 index 4c17569d7..000000000 --- a/ptrie/hashnode.go +++ /dev/null @@ -1,22 +0,0 @@ -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/iterator.go b/ptrie/iterator.go deleted file mode 100644 index 787ba09c0..000000000 --- a/ptrie/iterator.go +++ /dev/null @@ -1,115 +0,0 @@ -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: make([]byte, 32)} -} - -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() - - 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 { - 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 { - k := trie.RemTerm(node.Key()) - return append(k, 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 deleted file mode 100644 index acfc03d63..000000000 --- a/ptrie/iterator_test.go +++ /dev/null @@ -1,33 +0,0 @@ -package ptrie - -import "testing" - -func TestIterator(t *testing.T) { - trie := NewEmpty() - vals := []struct{ k, v string }{ - {"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() { - v[string(it.Key)] = true - } - - for k, found := range v { - if !found { - t.Error("iterator didn't find", k) - } - } -} diff --git a/ptrie/node.go b/ptrie/node.go deleted file mode 100644 index ab90a1a02..000000000 --- a/ptrie/node.go +++ /dev/null @@ -1,40 +0,0 @@ -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("%x ", 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("[ %x: %v ] ", self.key, self.value.fstring(ind+" ")) -} diff --git a/ptrie/shortnode.go b/ptrie/shortnode.go deleted file mode 100644 index 73ff2914b..000000000 --- a/ptrie/shortnode.go +++ /dev/null @@ -1,31 +0,0 @@ -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 NewShortNode(self.trie, self.key, self.value) } - -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 deleted file mode 100644 index 5c83b57d0..000000000 --- a/ptrie/trie.go +++ /dev/null @@ -1,335 +0,0 @@ -package ptrie - -import ( - "bytes" - "container/list" - "fmt" - "sync" - - "github.com/ethereum/go-ethereum/crypto" - "github.com/ethereum/go-ethereum/ethutil" - "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.Equal(t2.Hash(), t1.Hash()), t2 -} - -type Trie struct { - mu sync.Mutex - root Node - roothash []byte - cache *Cache - - revisions *list.List -} - -func New(root []byte, backend Backend) *Trie { - trie := &Trie{} - trie.revisions = list.New() - trie.roothash = root - trie.cache = NewCache(backend) - - if root != nil { - value := ethutil.NewValueFromBytes(trie.cache.Get(root)) - trie.root = trie.mknode(value) - } - - return trie -} - -func (self *Trie) Iterator() *Iterator { - return NewIterator(self) -} - -func (self *Trie) Copy() *Trie { - return New(self.roothash, self.cache.backend) -} - -// Legacy support -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 && len(byts) > 0 { - hash = byts - } else { - hash = crypto.Sha3(ethutil.Encode(self.root.RlpData())) - } - } else { - hash = crypto.Sha3(ethutil.Encode("")) - } - - if !bytes.Equal(hash, self.roothash) { - self.revisions.PushBack(self.roothash) - self.roothash = hash - } - - return hash -} -func (self *Trie) Commit() { - self.mu.Lock() - defer self.mu.Unlock() - - // Hash first - self.Hash() - - self.cache.Flush() -} - -// Reset should only be called if the trie has been hashed -func (self *Trie) Reset() { - self.mu.Lock() - defer self.mu.Unlock() - - self.cache.Reset() - - if self.revisions.Len() > 0 { - 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 { - 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.branch(key[0]), key[1:], value)) - - return cpy - - default: - panic(fmt.Sprintf("%T: invalid node: %v", node, 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.branch(key[0]), key[1:]) - default: - panic(fmt.Sprintf("%T: invalid node: %v", node, node)) - } -} - -func (self *Trie) delete(node Node, key []byte) Node { - if len(key) == 0 && node == nil { - 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: - sn := NewShortNode(self, node.Key(), child) - sn.key = node.key - n = sn - } - - return n - } else { - return node - } - - case *FullNode: - n := node.Copy().(*FullNode) - n.set(key[0], self.delete(n.branch(key[0]), key[1:])) - - pos := -1 - for i := 0; i < 17; i++ { - if n.branch(byte(i)) != nil { - if pos == -1 { - pos = i - } else { - pos = -2 - } - } - } - - var nnode Node - if pos == 16 { - nnode = NewShortNode(self, []byte{16}, n.branch(byte(pos))) - } else if pos >= 0 { - 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.branch(byte(pos))) - } - } else { - nnode = n - } - - return nnode - case nil: - return nil - default: - panic(fmt.Sprintf("%T: invalid node: %v (%v)", node, node, key)) - } -} - -// casting functions and cache storing -func (self *Trie) mknode(value *ethutil.Value) Node { - l := value.Len() - switch l { - case 0: - return nil - case 2: - // A value node may consists of 2 bytes. - if value.Get(0).Len() != 0 { - 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()} - } - - return &ValueNode{self, value.Bytes()} -} - -func (self *Trie) trans(node Node) Node { - switch node := node.(type) { - case *HashNode: - value := ethutil.NewValueFromBytes(self.cache.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.cache.Put(key, data) - - return key - } - - return node.RlpData() -} - -func (self *Trie) PrintRoot() { - fmt.Println(self.root) -} diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go deleted file mode 100644 index 63a8ed36e..000000000 --- a/ptrie/trie_test.go +++ /dev/null @@ -1,259 +0,0 @@ -package ptrie - -import ( - "bytes" - "fmt" - "testing" - - "github.com/ethereum/go-ethereum/crypto" - "github.com/ethereum/go-ethereum/ethutil" -) - -type Db map[string][]byte - -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 { - 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() - - 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 { - 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"}, - {"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.Commit() - - trie2 := New(trie.roothash, trie.cache.backend) - if string(trie2.GetString("horse")) != "stallion" { - t.Error("expected to have horse => stallion") - } - - hash := trie2.Hash() - exp := trie.Hash() - if !bytes.Equal(hash, exp) { - t.Errorf("root failure. expected %x got %x", exp, hash) - } - -} - -func TestReset(t *testing.T) { - trie := NewEmpty() - vals := []struct{ k, v string }{ - {"do", "verb"}, - {"ether", "wookiedoo"}, - {"horse", "stallion"}, - } - for _, val := range vals { - trie.UpdateString(val.k, val.v) - } - trie.Commit() - - before := ethutil.CopyBytes(trie.roothash) - trie.UpdateString("should", "revert") - trie.Hash() - // Should have no effect - trie.Hash() - trie.Hash() - // ### - - trie.Reset() - after := ethutil.CopyBytes(trie.roothash) - - if !bytes.Equal(before, after) { - t.Errorf("expected roots to be equal. %x - %x", before, after) - } -} - -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() - - base := "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - trie := NewEmpty() - for i := 0; i < 50; i++ { - trie.UpdateString(fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee") - } - 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(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 deleted file mode 100644 index c593eb6c6..000000000 --- a/ptrie/valuenode.go +++ /dev/null @@ -1,13 +0,0 @@ -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 &ValueNode{self.trie, self.data} } -func (self *ValueNode) RlpData() interface{} { return self.data } -func (self *ValueNode) Hash() interface{} { return self.data } -- cgit