aboutsummaryrefslogtreecommitdiffstats
path: root/trie
diff options
context:
space:
mode:
authorTaylor Gerring <taylor.gerring@gmail.com>2014-11-15 05:01:52 +0800
committerTaylor Gerring <taylor.gerring@gmail.com>2014-11-15 05:01:52 +0800
commit2a9fc7baa908d64ff1ddae44641024114d3ec88d (patch)
tree7b94082bd16765984046fa3c04c2ed57812d8c89 /trie
parent56aa24002de357c24a9644a49d5702c8d4663909 (diff)
downloaddexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.tar
dexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.tar.gz
dexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.tar.bz2
dexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.tar.lz
dexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.tar.xz
dexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.tar.zst
dexon-2a9fc7baa908d64ff1ddae44641024114d3ec88d.zip
Merge branch 'develop' of https://github.com/tgerring/go-ethereum
Diffstat (limited to 'trie')
-rw-r--r--trie/encoding_test.go67
-rw-r--r--trie/main_test.go8
-rw-r--r--trie/trie_test.go277
3 files changed, 148 insertions, 204 deletions
diff --git a/trie/encoding_test.go b/trie/encoding_test.go
index c9bc113c9..193c898f3 100644
--- a/trie/encoding_test.go
+++ b/trie/encoding_test.go
@@ -1,68 +1,59 @@
package trie
import (
- "bytes"
- "fmt"
- "testing"
+ checker "gopkg.in/check.v1"
)
-func TestCompactEncode(t *testing.T) {
+type TrieEncodingSuite struct{}
+
+var _ = checker.Suite(&TrieEncodingSuite{})
+
+func (s *TrieEncodingSuite) TestCompactEncode(c *checker.C) {
+ // even compact encode
test1 := []byte{1, 2, 3, 4, 5}
- if res := CompactEncode(test1); res != "\x11\x23\x45" {
- t.Error(fmt.Sprintf("even compact encode failed. Got: %q", res))
- }
+ res1 := CompactEncode(test1)
+ c.Assert(res1, checker.Equals, "\x11\x23\x45")
+ // odd compact encode
test2 := []byte{0, 1, 2, 3, 4, 5}
- if res := CompactEncode(test2); res != "\x00\x01\x23\x45" {
- t.Error(fmt.Sprintf("odd compact encode failed. Got: %q", res))
- }
+ res2 := CompactEncode(test2)
+ c.Assert(res2, checker.Equals, "\x00\x01\x23\x45")
+ //odd terminated compact encode
test3 := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
- if res := CompactEncode(test3); res != "\x20\x0f\x1c\xb8" {
- t.Error(fmt.Sprintf("odd terminated compact encode failed. Got: %q", res))
- }
+ res3 := CompactEncode(test3)
+ c.Assert(res3, checker.Equals, "\x20\x0f\x1c\xb8")
+ // even terminated compact encode
test4 := []byte{15, 1, 12, 11, 8 /*term*/, 16}
- if res := CompactEncode(test4); res != "\x3f\x1c\xb8" {
- t.Error(fmt.Sprintf("even terminated compact encode failed. Got: %q", res))
- }
+ res4 := CompactEncode(test4)
+ c.Assert(res4, checker.Equals, "\x3f\x1c\xb8")
}
-func TestCompactHexDecode(t *testing.T) {
+func (s *TrieEncodingSuite) TestCompactHexDecode(c *checker.C) {
exp := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16}
res := CompactHexDecode("verb")
-
- if !bytes.Equal(res, exp) {
- t.Error("Error compact hex decode. Expected", exp, "got", res)
- }
+ c.Assert(res, checker.DeepEquals, exp)
}
-func TestCompactDecode(t *testing.T) {
+func (s *TrieEncodingSuite) TestCompactDecode(c *checker.C) {
+ // odd compact decode
exp := []byte{1, 2, 3, 4, 5}
res := CompactDecode("\x11\x23\x45")
+ c.Assert(res, checker.DeepEquals, exp)
- if !bytes.Equal(res, exp) {
- t.Error("odd compact decode. Expected", exp, "got", res)
- }
-
+ // even compact decode
exp = []byte{0, 1, 2, 3, 4, 5}
res = CompactDecode("\x00\x01\x23\x45")
+ c.Assert(res, checker.DeepEquals, exp)
- if !bytes.Equal(res, exp) {
- t.Error("even compact decode. Expected", exp, "got", res)
- }
-
+ // even terminated compact decode
exp = []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
res = CompactDecode("\x20\x0f\x1c\xb8")
+ c.Assert(res, checker.DeepEquals, exp)
- if !bytes.Equal(res, exp) {
- t.Error("even terminated compact decode. Expected", exp, "got", res)
- }
-
+ // even terminated compact decode
exp = []byte{15, 1, 12, 11, 8 /*term*/, 16}
res = CompactDecode("\x3f\x1c\xb8")
-
- if !bytes.Equal(res, exp) {
- t.Error("even terminated compact decode. Expected", exp, "got", res)
- }
+ c.Assert(res, checker.DeepEquals, exp)
}
diff --git a/trie/main_test.go b/trie/main_test.go
new file mode 100644
index 000000000..f131b83de
--- /dev/null
+++ b/trie/main_test.go
@@ -0,0 +1,8 @@
+package trie
+
+import (
+ checker "gopkg.in/check.v1"
+ "testing"
+)
+
+func Test(t *testing.T) { checker.TestingT(t) }
diff --git a/trie/trie_test.go b/trie/trie_test.go
index 4c7e621dc..98d02c83e 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -1,15 +1,13 @@
package trie
import (
- "bytes"
"encoding/hex"
"encoding/json"
"fmt"
+ checker "gopkg.in/check.v1"
"io/ioutil"
"math/rand"
"net/http"
- "reflect"
- "testing"
"time"
"github.com/ethereum/go-ethereum/ethutil"
@@ -17,6 +15,11 @@ import (
const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ"
+type TrieSuite struct {
+ db *MemDatabase
+ trie *Trie
+}
+
type MemDatabase struct {
db map[string][]byte
}
@@ -44,142 +47,97 @@ func NewTrie() (*MemDatabase, *Trie) {
return db, New(db, "")
}
-func TestTrieSync(t *testing.T) {
- db, trie := NewTrie()
-
- 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 (s *TrieSuite) SetUpTest(c *checker.C) {
+ s.db, s.trie = NewTrie()
}
-func TestTrieDirtyTracking(t *testing.T) {
- _, trie := NewTrie()
- trie.Update("dog", LONG_WORD)
- if !trie.cache.IsDirty {
- t.Error("Expected trie to be dirty")
- }
+func (s *TrieSuite) TestTrieSync(c *checker.C) {
+ s.trie.Update("dog", LONG_WORD)
+ c.Assert(s.db.db, checker.HasLen, 0, checker.Commentf("Expected no data in database"))
+ s.trie.Sync()
+ c.Assert(s.db.db, checker.HasLen, 3)
+}
- trie.Sync()
- if trie.cache.IsDirty {
- t.Error("Expected trie not to be dirty")
- }
+func (s *TrieSuite) TestTrieDirtyTracking(c *checker.C) {
+ s.trie.Update("dog", LONG_WORD)
+ c.Assert(s.trie.cache.IsDirty, checker.Equals, true, checker.Commentf("Expected no data in database"))
- trie.Update("test", LONG_WORD)
- trie.cache.Undo()
- if trie.cache.IsDirty {
- t.Error("Expected trie not to be dirty")
- }
+ s.trie.Sync()
+ c.Assert(s.trie.cache.IsDirty, checker.Equals, false, checker.Commentf("Expected trie to be dirty"))
+ s.trie.Update("test", LONG_WORD)
+ s.trie.cache.Undo()
+ c.Assert(s.trie.cache.IsDirty, checker.Equals, false)
}
-func TestTrieReset(t *testing.T) {
- _, trie := NewTrie()
-
- trie.Update("cat", LONG_WORD)
- if len(trie.cache.nodes) == 0 {
- t.Error("Expected cached nodes")
- }
+func (s *TrieSuite) TestTrieReset(c *checker.C) {
+ s.trie.Update("cat", LONG_WORD)
+ c.Assert(s.trie.cache.nodes, checker.HasLen, 1, checker.Commentf("Expected cached nodes"))
- trie.cache.Undo()
-
- if len(trie.cache.nodes) != 0 {
- t.Error("Expected no nodes after undo", len(trie.cache.nodes))
- }
+ s.trie.cache.Undo()
+ c.Assert(s.trie.cache.nodes, checker.HasLen, 0, checker.Commentf("Expected no nodes after undo"))
}
-func TestTrieGet(t *testing.T) {
- _, trie := NewTrie()
-
- trie.Update("cat", LONG_WORD)
- x := trie.Get("cat")
- if x != LONG_WORD {
- t.Error("expected %s, got %s", LONG_WORD, x)
- }
+func (s *TrieSuite) TestTrieGet(c *checker.C) {
+ s.trie.Update("cat", LONG_WORD)
+ x := s.trie.Get("cat")
+ c.Assert(x, checker.DeepEquals, LONG_WORD)
}
-func TestTrieUpdating(t *testing.T) {
- _, trie := NewTrie()
- 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 (s *TrieSuite) TestTrieUpdating(c *checker.C) {
+ s.trie.Update("cat", LONG_WORD)
+ s.trie.Update("cat", LONG_WORD+"1")
+ x := s.trie.Get("cat")
+ c.Assert(x, checker.DeepEquals, LONG_WORD+"1")
}
-func TestTrieCmp(t *testing.T) {
+func (s *TrieSuite) TestTrieCmp(c *checker.C) {
_, trie1 := NewTrie()
_, trie2 := NewTrie()
trie1.Update("doge", LONG_WORD)
trie2.Update("doge", LONG_WORD)
- if !trie1.Cmp(trie2) {
- t.Error("Expected tries to be equal")
- }
+ c.Assert(trie1, checker.DeepEquals, trie2)
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)
- }
+ c.Assert(trie1, checker.Not(checker.DeepEquals), trie2)
}
-func TestTrieDelete(t *testing.T) {
- t.Skip()
- _, trie := NewTrie()
- 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 (s *TrieSuite) TestTrieDelete(c *checker.C) {
+ s.trie.Update("cat", LONG_WORD)
+ exp := s.trie.Root
+ s.trie.Update("dog", LONG_WORD)
+ s.trie.Delete("dog")
+ c.Assert(s.trie.Root, checker.DeepEquals, exp)
+
+ s.trie.Update("dog", LONG_WORD)
+ exp = s.trie.Root
+ s.trie.Update("dude", LONG_WORD)
+ s.trie.Delete("dude")
+ c.Assert(s.trie.Root, checker.DeepEquals, exp)
}
-func TestTrieDeleteWithValue(t *testing.T) {
- t.Skip()
- _, trie := NewTrie()
- 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 (s *TrieSuite) TestTrieDeleteWithValue(c *checker.C) {
+ s.trie.Update("c", LONG_WORD)
+ exp := s.trie.Root
+ s.trie.Update("ca", LONG_WORD)
+ s.trie.Update("cat", LONG_WORD)
+ s.trie.Delete("ca")
+ s.trie.Delete("cat")
+ c.Assert(s.trie.Root, checker.DeepEquals, exp)
}
-func TestTriePurge(t *testing.T) {
- _, trie := NewTrie()
- 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)
- }
+func (s *TrieSuite) TestTriePurge(c *checker.C) {
+ s.trie.Update("c", LONG_WORD)
+ s.trie.Update("ca", LONG_WORD)
+ s.trie.Update("cat", LONG_WORD)
- if lenBefore == len(trie.cache.nodes) {
- t.Errorf("Expected cached nodes to be deleted")
- }
+ lenBefore := len(s.trie.cache.nodes)
+ it := s.trie.NewIterator()
+ num := it.Purge()
+ c.Assert(num, checker.Equals, 3)
+ c.Assert(len(s.trie.cache.nodes), checker.Equals, lenBefore)
}
func h(str string) string {
@@ -201,23 +159,23 @@ func get(in string) (out string) {
return
}
-type Test struct {
+type TrieTest struct {
Name string
In map[string]string
Root string
}
-func CreateTest(name string, data []byte) (Test, error) {
- t := Test{Name: name}
+func CreateTest(name string, data []byte) (TrieTest, error) {
+ t := TrieTest{Name: name}
err := json.Unmarshal(data, &t)
if err != nil {
- return Test{}, fmt.Errorf("%v", err)
+ return TrieTest{}, fmt.Errorf("%v", err)
}
return t, nil
}
-func CreateTests(uri string, cb func(Test)) map[string]Test {
+func CreateTests(uri string, cb func(TrieTest)) map[string]TrieTest {
resp, err := http.Get(uri)
if err != nil {
panic(err)
@@ -232,7 +190,7 @@ func CreateTests(uri string, cb func(Test)) map[string]Test {
panic(err)
}
- tests := make(map[string]Test)
+ tests := make(map[string]TrieTest)
for name, testData := range objmap {
test, err := CreateTest(name, *testData)
if err != nil {
@@ -276,7 +234,7 @@ func RandomData() [][]string {
const MaxTest = 1000
// This test insert data in random order and seeks to find indifferences between the different tries
-func TestRegression(t *testing.T) {
+func (s *TrieSuite) TestRegression(c *checker.C) {
rand.Seed(time.Now().Unix())
roots := make(map[string]int)
@@ -292,34 +250,33 @@ func TestRegression(t *testing.T) {
roots[string(trie.Root.([]byte))] += 1
}
- if len(roots) > 1 {
- for root, num := range roots {
- t.Errorf("%x => %d\n", root, num)
- }
- }
+ c.Assert(len(roots) <= 1, checker.Equals, true)
+ // if len(roots) > 1 {
+ // for root, num := range roots {
+ // t.Errorf("%x => %d\n", root, num)
+ // }
+ // }
}
-func TestDelete(t *testing.T) {
- _, trie := NewTrie()
-
- 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")
+func (s *TrieSuite) TestDelete(c *checker.C) {
+ s.trie.Update("a", "jeffreytestlongstring")
+ s.trie.Update("aa", "otherstring")
+ s.trie.Update("aaa", "othermorestring")
+ s.trie.Update("aabbbbccc", "hithere")
+ s.trie.Update("abbcccdd", "hstanoehutnaheoustnh")
+ s.trie.Update("rnthaoeuabbcccdd", "hstanoehutnaheoustnh")
+ s.trie.Update("rneuabbcccdd", "hstanoehutnaheoustnh")
+ s.trie.Update("rneuabboeusntahoeucccdd", "hstanoehutnaheoustnh")
+ s.trie.Update("rnxabboeusntahoeucccdd", "hstanoehutnaheoustnh")
+ s.trie.Delete("aaboaestnuhbccc")
+ s.trie.Delete("a")
+ s.trie.Update("a", "nthaonethaosentuh")
+ s.trie.Update("c", "shtaosntehua")
+ s.trie.Delete("a")
+ s.trie.Update("aaaa", "testmegood")
_, t2 := NewTrie()
- trie.NewIterator().Each(func(key string, v *ethutil.Value) {
+ s.trie.NewIterator().Each(func(key string, v *ethutil.Value) {
if key == "aaaa" {
t2.Update(key, v.Str())
} else {
@@ -327,27 +284,22 @@ func TestDelete(t *testing.T) {
}
})
- a := ethutil.NewValue(trie.Root).Bytes()
+ a := ethutil.NewValue(s.trie.Root).Bytes()
b := ethutil.NewValue(t2.Root).Bytes()
- if bytes.Compare(a, b) != 0 {
- t.Errorf("Expected %x and %x to be equal", a, b)
- }
+ c.Assert(a, checker.DeepEquals, b)
}
-func TestTerminator(t *testing.T) {
+func (s *TrieSuite) TestTerminator(c *checker.C) {
key := CompactDecode("hello")
- if !HasTerm(key) {
- t.Errorf("Expected %v to have a terminator", key)
- }
+ c.Assert(HasTerm(key), checker.Equals, true, checker.Commentf("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()
+func (s *TrieSuite) TestIt(c *checker.C) {
+ s.trie.Update("cat", "cat")
+ s.trie.Update("doge", "doge")
+ s.trie.Update("wallace", "wallace")
+ it := s.trie.Iterator()
inputs := []struct {
In, Out string
@@ -363,23 +315,16 @@ func TestIt(t *testing.T) {
for _, test := range inputs {
res := string(it.Next(test.In))
- if res != test.Out {
- t.Errorf(test.In, "failed. Got", res, "Expected", test.Out)
- }
+ c.Assert(res, checker.Equals, test.Out)
}
}
-func TestBeginsWith(t *testing.T) {
+func (s *TrieSuite) TestBeginsWith(c *checker.C) {
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)
- }
+ c.Assert(BeginsWith(a, b), checker.Equals, false)
+ c.Assert(BeginsWith(b, a), checker.Equals, true)
}
func TestItems(t *testing.T) {