From 707d413761927f5ad95298e666e297b820ad0901 Mon Sep 17 00:00:00 2001 From: zelig Date: Sun, 29 Jun 2014 16:26:58 +0100 Subject: refactor ethutil/trie to ethtrie --- ethtrie/trie_test.go | 193 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 193 insertions(+) create mode 100644 ethtrie/trie_test.go (limited to 'ethtrie/trie_test.go') diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go new file mode 100644 index 000000000..284b189cb --- /dev/null +++ b/ethtrie/trie_test.go @@ -0,0 +1,193 @@ +package ethtrie + +import ( + "fmt" + "reflect" + "testing" +) + +const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" + +type MemDatabase struct { + db map[string][]byte +} + +func NewMemDatabase() (*MemDatabase, error) { + db := &MemDatabase{db: make(map[string][]byte)} + return db, nil +} +func (db *MemDatabase) Put(key []byte, value []byte) { + db.db[string(key)] = value +} +func (db *MemDatabase) Get(key []byte) ([]byte, error) { + return db.db[string(key)], nil +} +func (db *MemDatabase) Delete(key []byte) error { + delete(db.db, string(key)) + return nil +} +func (db *MemDatabase) Print() {} +func (db *MemDatabase) Close() {} +func (db *MemDatabase) LastKnownTD() []byte { return nil } + +func New() (*MemDatabase, *Trie) { + db, _ := NewMemDatabase() + return db, NewTrie(db, "") +} + +func TestTrieSync(t *testing.T) { + db, trie := New() + + trie.Update("dog", LONG_WORD) + if len(db.db) != 0 { + t.Error("Expected no data in database") + } + + trie.Sync() + if len(db.db) == 0 { + t.Error("Expected data to be persisted") + } +} + +func TestTrieDirtyTracking(t *testing.T) { + _, trie := New() + trie.Update("dog", LONG_WORD) + if !trie.cache.IsDirty { + t.Error("Expected trie to be dirty") + } + + trie.Sync() + if trie.cache.IsDirty { + t.Error("Expected trie not to be dirty") + } + + trie.Update("test", LONG_WORD) + trie.cache.Undo() + if trie.cache.IsDirty { + t.Error("Expected trie not to be dirty") + } + +} + +func TestTrieReset(t *testing.T) { + _, trie := New() + + trie.Update("cat", LONG_WORD) + if len(trie.cache.nodes) == 0 { + t.Error("Expected cached nodes") + } + + trie.cache.Undo() + + if len(trie.cache.nodes) != 0 { + t.Error("Expected no nodes after undo") + } +} + +func TestTrieGet(t *testing.T) { + _, trie := New() + + trie.Update("cat", LONG_WORD) + x := trie.Get("cat") + if x != LONG_WORD { + t.Error("expected %s, got %s", LONG_WORD, x) + } +} + +func TestTrieUpdating(t *testing.T) { + _, trie := New() + trie.Update("cat", LONG_WORD) + trie.Update("cat", LONG_WORD+"1") + x := trie.Get("cat") + if x != LONG_WORD+"1" { + t.Error("expected %S, got %s", LONG_WORD+"1", x) + } +} + +func TestTrieCmp(t *testing.T) { + _, trie1 := New() + _, trie2 := New() + + trie1.Update("doge", LONG_WORD) + trie2.Update("doge", LONG_WORD) + if !trie1.Cmp(trie2) { + t.Error("Expected tries to be equal") + } + + trie1.Update("dog", LONG_WORD) + trie2.Update("cat", LONG_WORD) + if trie1.Cmp(trie2) { + t.Errorf("Expected tries not to be equal %x %x", trie1.Root, trie2.Root) + } +} + +func TestTrieDelete(t *testing.T) { + _, trie := New() + trie.Update("cat", LONG_WORD) + exp := trie.Root + trie.Update("dog", LONG_WORD) + trie.Delete("dog") + if !reflect.DeepEqual(exp, trie.Root) { + t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) + } + + trie.Update("dog", LONG_WORD) + exp = trie.Root + trie.Update("dude", LONG_WORD) + trie.Delete("dude") + if !reflect.DeepEqual(exp, trie.Root) { + t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) + } +} + +func TestTrieDeleteWithValue(t *testing.T) { + _, trie := New() + trie.Update("c", LONG_WORD) + exp := trie.Root + trie.Update("ca", LONG_WORD) + trie.Update("cat", LONG_WORD) + trie.Delete("ca") + trie.Delete("cat") + if !reflect.DeepEqual(exp, trie.Root) { + t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) + } + +} + +func TestTriePurge(t *testing.T) { + _, trie := New() + trie.Update("c", LONG_WORD) + trie.Update("ca", LONG_WORD) + trie.Update("cat", LONG_WORD) + + lenBefore := len(trie.cache.nodes) + it := trie.NewIterator() + if num := it.Purge(); num != 3 { + t.Errorf("Expected purge to return 3, got %d", num) + } + + if lenBefore == len(trie.cache.nodes) { + t.Errorf("Expected cached nodes to be deleted") + } +} + +func TestTrieIt(t *testing.T) { + _, trie := New() + + data := [][]string{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + } + + for _, item := range data { + trie.Update(item[0], item[1]) + } + + fmt.Printf("root %x", trie.Root) +} -- cgit v1.2.3 From 09bade64666f82a2580e7d24a8bc7655e2113287 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 15 Jul 2014 15:29:54 +0200 Subject: Fixed an issue where the trie might crash on missmatching lengths --- ethtrie/trie_test.go | 46 +++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 41 insertions(+), 5 deletions(-) (limited to 'ethtrie/trie_test.go') diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go index a3d4547d7..f39477ff9 100644 --- a/ethtrie/trie_test.go +++ b/ethtrie/trie_test.go @@ -5,6 +5,7 @@ import ( "encoding/hex" "encoding/json" "fmt" + "github.com/ethereum/eth-go/ethutil" "io/ioutil" "math/rand" "net/http" @@ -251,8 +252,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 +268,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 +330,38 @@ 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) +} -- cgit v1.2.3 From ed3424ff75b396360990725afc124326dea4ab45 Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 17 Jul 2014 11:21:18 +0200 Subject: Trie fixes --- ethtrie/trie_test.go | 69 ++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 61 insertions(+), 8 deletions(-) (limited to 'ethtrie/trie_test.go') diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go index f39477ff9..3989a8f45 100644 --- a/ethtrie/trie_test.go +++ b/ethtrie/trie_test.go @@ -1,17 +1,17 @@ package ethtrie import ( - "bytes" - "encoding/hex" - "encoding/json" + _ "bytes" + _ "encoding/hex" + _ "encoding/json" "fmt" "github.com/ethereum/eth-go/ethutil" - "io/ioutil" - "math/rand" - "net/http" - "reflect" + _ "io/ioutil" + _ "math/rand" + _ "net/http" + _ "reflect" "testing" - "time" + _ "time" ) const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" @@ -43,6 +43,7 @@ func New() (*MemDatabase, *Trie) { return db, NewTrie(db, "") } +/* func TestTrieSync(t *testing.T) { db, trie := New() @@ -365,3 +366,55 @@ func TestDelete(t *testing.T) { 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")))) +} -- cgit v1.2.3 From 3debeb7236d2c8474fa9049cc91dc26bf1040b3f Mon Sep 17 00:00:00 2001 From: obscuren Date: Mon, 4 Aug 2014 10:38:18 +0200 Subject: ethtrie.NewTrie => ethtrie.New --- ethtrie/trie_test.go | 41 +++++++++++++++++++++-------------------- 1 file changed, 21 insertions(+), 20 deletions(-) (limited to 'ethtrie/trie_test.go') diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go index 3989a8f45..2661f8f25 100644 --- a/ethtrie/trie_test.go +++ b/ethtrie/trie_test.go @@ -5,13 +5,14 @@ import ( _ "encoding/hex" _ "encoding/json" "fmt" - "github.com/ethereum/eth-go/ethutil" _ "io/ioutil" _ "math/rand" _ "net/http" _ "reflect" "testing" _ "time" + + "github.com/ethereum/eth-go/ethutil" ) const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" @@ -38,14 +39,14 @@ func (db *MemDatabase) Print() {} func (db *MemDatabase) Close() {} func (db *MemDatabase) LastKnownTD() []byte { return nil } -func New() (*MemDatabase, *Trie) { +func NewTrie() (*MemDatabase, *Trie) { db, _ := NewMemDatabase() - return db, NewTrie(db, "") + return db, New(db, "") } /* func TestTrieSync(t *testing.T) { - db, trie := New() + db, trie := NewTrie() trie.Update("dog", LONG_WORD) if len(db.db) != 0 { @@ -59,7 +60,7 @@ func TestTrieSync(t *testing.T) { } func TestTrieDirtyTracking(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("dog", LONG_WORD) if !trie.cache.IsDirty { t.Error("Expected trie to be dirty") @@ -79,7 +80,7 @@ func TestTrieDirtyTracking(t *testing.T) { } func TestTrieReset(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("cat", LONG_WORD) if len(trie.cache.nodes) == 0 { @@ -94,7 +95,7 @@ func TestTrieReset(t *testing.T) { } func TestTrieGet(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("cat", LONG_WORD) x := trie.Get("cat") @@ -104,7 +105,7 @@ func TestTrieGet(t *testing.T) { } func TestTrieUpdating(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("cat", LONG_WORD) trie.Update("cat", LONG_WORD+"1") x := trie.Get("cat") @@ -114,8 +115,8 @@ func TestTrieUpdating(t *testing.T) { } func TestTrieCmp(t *testing.T) { - _, trie1 := New() - _, trie2 := New() + _, trie1 := NewTrie() + _, trie2 := NewTrie() trie1.Update("doge", LONG_WORD) trie2.Update("doge", LONG_WORD) @@ -131,7 +132,7 @@ func TestTrieCmp(t *testing.T) { } func TestTrieDelete(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("cat", LONG_WORD) exp := trie.Root trie.Update("dog", LONG_WORD) @@ -150,7 +151,7 @@ func TestTrieDelete(t *testing.T) { } func TestTrieDeleteWithValue(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("c", LONG_WORD) exp := trie.Root trie.Update("ca", LONG_WORD) @@ -164,7 +165,7 @@ func TestTrieDeleteWithValue(t *testing.T) { } func TestTriePurge(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("c", LONG_WORD) trie.Update("ca", LONG_WORD) trie.Update("cat", LONG_WORD) @@ -248,7 +249,7 @@ func CreateTests(uri string, cb func(Test)) map[string]Test { func TestRemote(t *testing.T) { CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) { - _, trie := New() + _, trie := NewTrie() for key, value := range test.In { trie.Update(get(key), get(value)) } @@ -263,12 +264,12 @@ func TestRemote(t *testing.T) { func TestTrieReplay(t *testing.T) { CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) { - _, trie := New() + _, trie := NewTrie() for key, value := range test.In { trie.Update(get(key), get(value)) } - _, trie2 := New() + _, trie2 := NewTrie() trie.NewIterator().Each(func(key string, v *ethutil.Value) { trie2.Update(key, v.Str()) }) @@ -314,7 +315,7 @@ func TestRegression(t *testing.T) { roots := make(map[string]int) for i := 0; i < MaxTest; i++ { - _, trie := New() + _, trie := NewTrie() data := RandomData() for _, test := range data { @@ -333,7 +334,7 @@ func TestRegression(t *testing.T) { } func TestDelete(t *testing.T) { - _, trie := New() + _, trie := NewTrie() trie.Update("a", "jeffreytestlongstring") trie.Update("aa", "otherstring") @@ -352,7 +353,7 @@ func TestDelete(t *testing.T) { trie.Update("aaaa", "testmegood") fmt.Println("aa =>", trie.Get("aa")) - _, t2 := New() + _, t2 := NewTrie() trie.NewIterator().Each(func(key string, v *ethutil.Value) { if key == "aaaa" { t2.Update(key, v.Str()) @@ -369,7 +370,7 @@ func TestDelete(t *testing.T) { */ func TestRndCase(t *testing.T) { - _, trie := New() + _, trie := NewTrie() data := []struct{ k, v string }{ {"0000000000000000000000000000000000000000000000000000000000000001", "a07573657264617461000000000000000000000000000000000000000000000000"}, -- cgit v1.2.3 From e02c0fa8088943bc995d290e58a7226f4a0ece91 Mon Sep 17 00:00:00 2001 From: obscuren Date: Fri, 10 Oct 2014 17:00:06 +0200 Subject: Added generic big to 256 method. Implemented new iterator --- ethtrie/trie_test.go | 107 +++++++++++++++++++++++++++++---------------------- 1 file changed, 60 insertions(+), 47 deletions(-) (limited to 'ethtrie/trie_test.go') diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go index 2661f8f25..11c20f8fb 100644 --- a/ethtrie/trie_test.go +++ b/ethtrie/trie_test.go @@ -1,16 +1,16 @@ package ethtrie import ( - _ "bytes" - _ "encoding/hex" - _ "encoding/json" + "bytes" + "encoding/hex" + "encoding/json" "fmt" - _ "io/ioutil" - _ "math/rand" - _ "net/http" - _ "reflect" + "io/ioutil" + "math/rand" + "net/http" + "reflect" "testing" - _ "time" + "time" "github.com/ethereum/eth-go/ethutil" ) @@ -44,7 +44,6 @@ func NewTrie() (*MemDatabase, *Trie) { return db, New(db, "") } -/* func TestTrieSync(t *testing.T) { db, trie := NewTrie() @@ -247,41 +246,6 @@ func CreateTests(uri string, cb func(Test)) map[string]Test { return tests } -func TestRemote(t *testing.T) { - CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) { - _, trie := NewTrie() - for key, value := range test.In { - trie.Update(get(key), get(value)) - } - - 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) - } - }) -} - -func TestTrieReplay(t *testing.T) { - CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) { - _, trie := NewTrie() - for key, value := range test.In { - trie.Update(get(key), get(value)) - } - - _, trie2 := NewTrie() - trie.NewIterator().Each(func(key string, v *ethutil.Value) { - trie2.Update(key, v.Str()) - }) - - 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) - } - }) -} - func RandomData() [][]string { data := [][]string{ {"0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1", "0x4e616d6552656700000000000000000000000000000000000000000000000000"}, @@ -352,7 +316,6 @@ func TestDelete(t *testing.T) { trie.Delete("a") trie.Update("aaaa", "testmegood") - fmt.Println("aa =>", trie.Get("aa")) _, t2 := NewTrie() trie.NewIterator().Each(func(key string, v *ethutil.Value) { if key == "aaaa" { @@ -365,10 +328,59 @@ func TestDelete(t *testing.T) { a := ethutil.NewValue(trie.Root).Bytes() b := ethutil.NewValue(t2.Root).Bytes() - fmt.Printf("o: %x\nc: %x\n", a, b) + if bytes.Compare(a, b) != 0 { + t.Errorf("Expected %x and %x to be equal", a, b) + } } -*/ +func TestTerminator(t *testing.T) { + key := CompactDecode("hello") + if !HasTerm(key) { + t.Errorf("Expected %v to have a terminator", key) + } +} + +func TestIt(t *testing.T) { + _, trie := NewTrie() + trie.Update("cat", "cat") + trie.Update("doge", "doge") + trie.Update("wallace", "wallace") + it := trie.Iterator() + + inputs := []struct { + In, Out string + }{ + {"", "cat"}, + {"bobo", "cat"}, + {"c", "cat"}, + {"car", "cat"}, + {"catering", "doge"}, + {"w", "wallace"}, + {"wallace123", ""}, + } + + for _, test := range inputs { + res := string(it.Next(test.In)) + if res != test.Out { + t.Errorf(test.In, "failed. Got", res, "Expected", test.Out) + } + } +} + +func TestBeginsWith(t *testing.T) { + a := CompactDecode("hello") + b := CompactDecode("hel") + + if BeginsWith(a, b) { + t.Errorf("Expected %x to begin with %x", a, b) + } + + if BeginsWith(b, a) { + t.Errorf("Expected %x not to begin with %x", b, a) + } +} + +/* func TestRndCase(t *testing.T) { _, trie := NewTrie() @@ -419,3 +431,4 @@ func TestRndCase(t *testing.T) { fmt.Printf("%x\n", trie.Get(string(ethutil.Hex2Bytes("0000000000000000000000000000000000000000000000000000000000000001")))) } +*/ -- cgit v1.2.3