aboutsummaryrefslogtreecommitdiffstats
path: root/ethtrie
diff options
context:
space:
mode:
Diffstat (limited to 'ethtrie')
-rw-r--r--ethtrie/trie.go35
-rw-r--r--ethtrie/trie_test.go115
2 files changed, 129 insertions, 21 deletions
diff --git a/ethtrie/trie.go b/ethtrie/trie.go
index 38c78e7f4..f0f3fe5a8 100644
--- a/ethtrie/trie.go
+++ b/ethtrie/trie.go
@@ -5,10 +5,12 @@ import (
"fmt"
"github.com/ethereum/eth-go/ethcrypto"
"github.com/ethereum/eth-go/ethutil"
- "reflect"
+ _ "reflect"
"sync"
)
+func __ignore() { fmt.Println("") }
+
func ParanoiaCheck(t1 *Trie) (bool, *Trie) {
t2 := NewTrie(ethutil.Config.Db, "")
@@ -269,8 +271,7 @@ func (t *Trie) getState(node interface{}, key []int) interface{} {
}
// It shouldn't come this far
- fmt.Println("getState unexpected return")
- return ""
+ panic("unexpected return")
}
func (t *Trie) getNode(node interface{}) *ethutil.Value {
@@ -287,7 +288,9 @@ func (t *Trie) getNode(node interface{}) *ethutil.Value {
return ethutil.NewValueFromBytes([]byte(str))
}
- return t.cache.Get(n.Bytes())
+ data := t.cache.Get(n.Bytes())
+
+ return data
}
func (t *Trie) UpdateState(node interface{}, key []int, value string) interface{} {
@@ -323,7 +326,8 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter
// New node
n := ethutil.NewValue(node)
- if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 {
+ if node == nil || n.Len() == 0 {
+ //if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 {
newNode := []interface{}{CompactEncode(key), value}
return t.Put(newNode)
@@ -385,17 +389,22 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter
return t.Put(newNode)
}
- return ""
+ panic("unexpected end")
}
func (t *Trie) deleteState(node interface{}, key []int) interface{} {
if len(key) == 0 {
+ println("<empty ret>")
return ""
}
// New node
n := ethutil.NewValue(node)
- if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 {
+ //if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 {
+ if node == nil || n.Len() == 0 {
+ //return nil
+ //fmt.Printf("<empty ret> %x %d\n", n, len(n.Bytes()))
+
return ""
}
@@ -408,10 +417,17 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} {
// Matching key pair (ie. there's already an object with this key)
if CompareIntSlice(k, key) {
+ //fmt.Printf("<delete ret> %x\n", v)
+
return ""
} else if CompareIntSlice(key[:len(k)], k) {
hash := t.deleteState(v, key[len(k):])
child := t.getNode(hash)
+ /*
+ if child.IsNil() {
+ return node
+ }
+ */
var newNode []interface{}
if child.Len() == 2 {
@@ -421,6 +437,8 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} {
newNode = []interface{}{currentNode.Get(0).Str(), hash}
}
+ //fmt.Printf("%x\n", newNode)
+
return t.Put(newNode)
} else {
return node
@@ -463,10 +481,11 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} {
newNode = n
}
+ //fmt.Printf("%x\n", newNode)
return t.Put(newNode)
}
- return ""
+ panic("unexpected return")
}
type TrieIterator struct {
diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go
index a3d4547d7..3989a8f45 100644
--- a/ethtrie/trie_test.go
+++ b/ethtrie/trie_test.go
@@ -1,16 +1,17 @@
package ethtrie
import (
- "bytes"
- "encoding/hex"
- "encoding/json"
+ _ "bytes"
+ _ "encoding/hex"
+ _ "encoding/json"
"fmt"
- "io/ioutil"
- "math/rand"
- "net/http"
- "reflect"
+ "github.com/ethereum/eth-go/ethutil"
+ _ "io/ioutil"
+ _ "math/rand"
+ _ "net/http"
+ _ "reflect"
"testing"
- "time"
+ _ "time"
)
const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ"
@@ -42,6 +43,7 @@ func New() (*MemDatabase, *Trie) {
return db, NewTrie(db, "")
}
+/*
func TestTrieSync(t *testing.T) {
db, trie := New()
@@ -251,8 +253,8 @@ func TestRemote(t *testing.T) {
trie.Update(get(key), get(value))
}
- a := NewValue(h(test.Root)).Bytes()
- b := NewValue(trie.Root).Bytes()
+ a := ethutil.NewValue(h(test.Root)).Bytes()
+ b := ethutil.NewValue(trie.Root).Bytes()
if bytes.Compare(a, b) != 0 {
t.Errorf("%-10s: %x %x", test.Name, a, b)
}
@@ -267,12 +269,12 @@ func TestTrieReplay(t *testing.T) {
}
_, trie2 := New()
- trie.NewIterator().Each(func(key string, v *Value) {
+ trie.NewIterator().Each(func(key string, v *ethutil.Value) {
trie2.Update(key, v.Str())
})
- a := NewValue(trie.Root).Bytes()
- b := NewValue(trie2.Root).Bytes()
+ a := ethutil.NewValue(trie.Root).Bytes()
+ b := ethutil.NewValue(trie2.Root).Bytes()
if bytes.Compare(a, b) != 0 {
t.Errorf("%s %x %x\n", test.Name, trie.Root, trie2.Root)
}
@@ -329,3 +331,90 @@ func TestRegression(t *testing.T) {
}
}
}
+
+func TestDelete(t *testing.T) {
+ _, trie := New()
+
+ trie.Update("a", "jeffreytestlongstring")
+ trie.Update("aa", "otherstring")
+ trie.Update("aaa", "othermorestring")
+ trie.Update("aabbbbccc", "hithere")
+ trie.Update("abbcccdd", "hstanoehutnaheoustnh")
+ trie.Update("rnthaoeuabbcccdd", "hstanoehutnaheoustnh")
+ trie.Update("rneuabbcccdd", "hstanoehutnaheoustnh")
+ trie.Update("rneuabboeusntahoeucccdd", "hstanoehutnaheoustnh")
+ trie.Update("rnxabboeusntahoeucccdd", "hstanoehutnaheoustnh")
+ trie.Delete("aaboaestnuhbccc")
+ trie.Delete("a")
+ trie.Update("a", "nthaonethaosentuh")
+ trie.Update("c", "shtaosntehua")
+ trie.Delete("a")
+ trie.Update("aaaa", "testmegood")
+
+ fmt.Println("aa =>", trie.Get("aa"))
+ _, t2 := New()
+ trie.NewIterator().Each(func(key string, v *ethutil.Value) {
+ if key == "aaaa" {
+ t2.Update(key, v.Str())
+ } else {
+ t2.Update(key, v.Str())
+ }
+ })
+
+ a := ethutil.NewValue(trie.Root).Bytes()
+ b := ethutil.NewValue(t2.Root).Bytes()
+
+ fmt.Printf("o: %x\nc: %x\n", a, b)
+}
+*/
+
+func TestRndCase(t *testing.T) {
+ _, trie := New()
+
+ data := []struct{ k, v string }{
+ {"0000000000000000000000000000000000000000000000000000000000000001", "a07573657264617461000000000000000000000000000000000000000000000000"},
+ {"0000000000000000000000000000000000000000000000000000000000000003", "8453bb5b31"},
+ {"0000000000000000000000000000000000000000000000000000000000000004", "850218711a00"},
+ {"0000000000000000000000000000000000000000000000000000000000000005", "9462d7705bd0b3ecbc51a8026a25597cb28a650c79"},
+ {"0000000000000000000000000000000000000000000000000000000000000010", "947e70f9460402290a3e487dae01f610a1a8218fda"},
+ {"0000000000000000000000000000000000000000000000000000000000000111", "01"},
+ {"0000000000000000000000000000000000000000000000000000000000000112", "a053656e6174650000000000000000000000000000000000000000000000000000"},
+ {"0000000000000000000000000000000000000000000000000000000000000113", "a053656e6174650000000000000000000000000000000000000000000000000000"},
+ {"53656e6174650000000000000000000000000000000000000000000000000000", "94977e3f62f5e1ed7953697430303a3cfa2b5b736e"},
+ }
+ for _, e := range data {
+ trie.Update(string(ethutil.Hex2Bytes(e.k)), string(ethutil.Hex2Bytes(e.v)))
+ }
+
+ fmt.Printf("root after update %x\n", trie.Root)
+ trie.NewIterator().Each(func(k string, v *ethutil.Value) {
+ fmt.Printf("%x %x\n", k, v.Bytes())
+ })
+
+ data = []struct{ k, v string }{
+ {"0000000000000000000000000000000000000000000000000000000000000112", ""},
+ {"436974697a656e73000000000000000000000000000000000000000000000001", ""},
+ {"436f757274000000000000000000000000000000000000000000000000000002", ""},
+ {"53656e6174650000000000000000000000000000000000000000000000000000", ""},
+ {"436f757274000000000000000000000000000000000000000000000000000000", ""},
+ {"53656e6174650000000000000000000000000000000000000000000000000001", ""},
+ {"0000000000000000000000000000000000000000000000000000000000000113", ""},
+ {"436974697a656e73000000000000000000000000000000000000000000000000", ""},
+ {"436974697a656e73000000000000000000000000000000000000000000000002", ""},
+ {"436f757274000000000000000000000000000000000000000000000000000001", ""},
+ {"0000000000000000000000000000000000000000000000000000000000000111", ""},
+ {"53656e6174650000000000000000000000000000000000000000000000000002", ""},
+ }
+
+ for _, e := range data {
+ trie.Delete(string(ethutil.Hex2Bytes(e.k)))
+ }
+
+ fmt.Printf("root after delete %x\n", trie.Root)
+
+ trie.NewIterator().Each(func(k string, v *ethutil.Value) {
+ fmt.Printf("%x %x\n", k, v.Bytes())
+ })
+
+ fmt.Printf("%x\n", trie.Get(string(ethutil.Hex2Bytes("0000000000000000000000000000000000000000000000000000000000000001"))))
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-09 21:41:20 +0800