Moved ptrie => trie. Removed old trie

1 files changed, 161 insertions, 298 deletions

diff --git a/trie/trie_test.go b/trie/trie_test.go
index 3abe56040..ffb78d4f2 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -1,345 +1,188 @@
 package trie
 
-/*
 import (
 	"bytes"
-	"encoding/hex"
-	"encoding/json"
 	"fmt"
-	"io/ioutil"
-	"math/rand"
-	"net/http"
 	"testing"
-	"time"
-
-	checker "gopkg.in/check.v1"
 
+	"github.com/ethereum/go-ethereum/crypto"
 	"github.com/ethereum/go-ethereum/ethutil"
 )
 
-const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ"
-
-type TrieSuite struct {
-	db   *MemDatabase
-	trie *Trie
-}
-
-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 NewTrie() (*MemDatabase, *Trie) {
-	db, _ := NewMemDatabase()
-	return db, New(db, "")
-}
-
-func (s *TrieSuite) SetUpTest(c *checker.C) {
-	s.db, s.trie = NewTrie()
-}
-
-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)
-}
-
-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"))
-
-	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 (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"))
+type Db map[string][]byte
 
-	s.trie.cache.Undo()
-	c.Assert(s.trie.cache.nodes, checker.HasLen, 0, checker.Commentf("Expected no nodes after undo"))
-}
+func (self Db) Get(k []byte) ([]byte, error) { return self[string(k)], nil }
+func (self Db) Put(k, v []byte)              { self[string(k)] = v }
 
-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)
+// Used for testing
+func NewEmpty() *Trie {
+	return New(nil, make(Db))
 }
 
-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 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 (s *TrieSuite) TestTrieCmp(c *checker.C) {
-	_, trie1 := NewTrie()
-	_, trie2 := NewTrie()
+func TestInsert(t *testing.T) {
+	trie := NewEmpty()
 
-	trie1.Update("doge", LONG_WORD)
-	trie2.Update("doge", LONG_WORD)
-	c.Assert(trie1, checker.DeepEquals, trie2)
+	trie.UpdateString("doe", "reindeer")
+	trie.UpdateString("dog", "puppy")
+	trie.UpdateString("dogglesworth", "cat")
 
-	trie1.Update("dog", LONG_WORD)
-	trie2.Update("cat", LONG_WORD)
-	c.Assert(trie1, checker.Not(checker.DeepEquals), trie2)
-}
+	exp := ethutil.Hex2Bytes("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
+	root := trie.Hash()
+	if !bytes.Equal(root, exp) {
+		t.Errorf("exp %x got %x", exp, 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)
-}
+	trie = NewEmpty()
+	trie.UpdateString("A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
 
-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)
+	exp = ethutil.Hex2Bytes("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab")
+	root = trie.Hash()
+	if !bytes.Equal(root, exp) {
+		t.Errorf("exp %x got %x", exp, root)
+	}
 }
 
-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)
+func TestGet(t *testing.T) {
+	trie := NewEmpty()
 
-	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)
-}
+	trie.UpdateString("doe", "reindeer")
+	trie.UpdateString("dog", "puppy")
+	trie.UpdateString("dogglesworth", "cat")
 
-func h(str string) string {
-	d, err := hex.DecodeString(str)
-	if err != nil {
-		panic(err)
+	res := trie.GetString("dog")
+	if !bytes.Equal(res, []byte("puppy")) {
+		t.Errorf("expected puppy got %x", res)
 	}
 
-	return string(d)
-}
-
-func get(in string) (out string) {
-	if len(in) > 2 && in[:2] == "0x" {
-		out = h(in[2:])
-	} else {
-		out = in
+	unknown := trie.GetString("unknown")
+	if unknown != nil {
+		t.Errorf("expected nil got %x", unknown)
 	}
-
-	return
 }
 
-type TrieTest struct {
-	Name string
-	In   map[string]string
-	Root string
-}
+func TestDelete(t *testing.T) {
+	trie := NewEmpty()
 
-func CreateTest(name string, data []byte) (TrieTest, error) {
-	t := TrieTest{Name: name}
-	err := json.Unmarshal(data, &t)
-	if err != nil {
-		return TrieTest{}, fmt.Errorf("%v", err)
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"ether", ""},
+		{"dog", "puppy"},
+		{"shaman", ""},
 	}
-
-	return t, nil
-}
-
-func CreateTests(uri string, cb func(TrieTest)) map[string]TrieTest {
-	resp, err := http.Get(uri)
-	if err != nil {
-		panic(err)
+	for _, val := range vals {
+		if val.v != "" {
+			trie.UpdateString(val.k, val.v)
+		} else {
+			trie.DeleteString(val.k)
+		}
 	}
-	defer resp.Body.Close()
 
-	data, err := ioutil.ReadAll(resp.Body)
-
-	var objmap map[string]*json.RawMessage
-	err = json.Unmarshal(data, &objmap)
-	if err != nil {
-		panic(err)
+	hash := trie.Hash()
+	exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
+	if !bytes.Equal(hash, exp) {
+		t.Errorf("expected %x got %x", exp, hash)
 	}
+}
 
-	tests := make(map[string]TrieTest)
-	for name, testData := range objmap {
-		test, err := CreateTest(name, *testData)
-		if err != nil {
-			panic(err)
-		}
+func TestEmptyValues(t *testing.T) {
+	trie := NewEmpty()
 
-		if cb != nil {
-			cb(test)
-		}
-		tests[name] = test
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"ether", ""},
+		{"dog", "puppy"},
+		{"shaman", ""},
 	}
-
-	return tests
-}
-
-func RandomData() [][]string {
-	data := [][]string{
-		{"0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1", "0x4e616d6552656700000000000000000000000000000000000000000000000000"},
-		{"0x0000000000000000000000000000000000000000000000000000000000000045", "0x22b224a1420a802ab51d326e29fa98e34c4f24ea"},
-		{"0x0000000000000000000000000000000000000000000000000000000000000046", "0x67706c2076330000000000000000000000000000000000000000000000000000"},
-		{"0x000000000000000000000000697c7b8c961b56f675d570498424ac8de1a918f6", "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000"},
-		{"0x0000000000000000000000007ef9e639e2733cb34e4dfc576d4b23f72db776b2", "0x4655474156000000000000000000000000000000000000000000000000000000"},
-		{"0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000", "0x697c7b8c961b56f675d570498424ac8de1a918f6"},
-		{"0x4655474156000000000000000000000000000000000000000000000000000000", "0x7ef9e639e2733cb34e4dfc576d4b23f72db776b2"},
-		{"0x4e616d6552656700000000000000000000000000000000000000000000000000", "0xec4f34c97e43fbb2816cfd95e388353c7181dab1"},
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
 	}
 
-	var c [][]string
-	for len(data) != 0 {
-		e := rand.Intn(len(data))
-		c = append(c, data[e])
-
-		copy(data[e:], data[e+1:])
-		data[len(data)-1] = nil
-		data = data[:len(data)-1]
+	hash := trie.Hash()
+	exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
+	if !bytes.Equal(hash, exp) {
+		t.Errorf("expected %x got %x", exp, hash)
 	}
-
-	return c
 }
 
-const MaxTest = 1000
-
-// This test insert data in random order and seeks to find indifferences between the different tries
-func (s *TrieSuite) TestRegression(c *checker.C) {
-	rand.Seed(time.Now().Unix())
-
-	roots := make(map[string]int)
-	for i := 0; i < MaxTest; i++ {
-		_, trie := NewTrie()
-		data := RandomData()
-
-		for _, test := range data {
-			trie.Update(test[0], test[1])
-		}
-		trie.Delete("0x4e616d6552656700000000000000000000000000000000000000000000000000")
-
-		roots[string(trie.Root.([]byte))] += 1
+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()
 
-	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 (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()
-	s.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(s.trie.Root).Bytes()
-	b := ethutil.NewValue(t2.Root).Bytes()
+	trie2 := New(trie.roothash, trie.cache.backend)
+	if string(trie2.GetString("horse")) != "stallion" {
+		t.Error("expected to have horse => stallion")
+	}
 
-	c.Assert(a, checker.DeepEquals, b)
-}
+	hash := trie2.Hash()
+	exp := trie.Hash()
+	if !bytes.Equal(hash, exp) {
+		t.Errorf("root failure. expected %x got %x", exp, hash)
+	}
 
-func (s *TrieSuite) TestTerminator(c *checker.C) {
-	key := CompactDecode("hello")
-	c.Assert(HasTerm(key), checker.Equals, true, checker.Commentf("Expected %v to have a terminator", key))
 }
 
-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
-	}{
-		{"", "cat"},
-		{"bobo", "cat"},
-		{"c", "cat"},
-		{"car", "cat"},
-		{"catering", "doge"},
-		{"w", "wallace"},
-		{"wallace123", ""},
+func TestReset(t *testing.T) {
+	trie := NewEmpty()
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
 	}
-
-	for _, test := range inputs {
-		res := string(it.Next(test.In))
-		c.Assert(res, checker.Equals, test.Out)
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
 	}
-}
+	trie.Commit()
 
-func (s *TrieSuite) TestBeginsWith(c *checker.C) {
-	a := CompactDecode("hello")
-	b := CompactDecode("hel")
-
-	c.Assert(BeginsWith(a, b), checker.Equals, false)
-	c.Assert(BeginsWith(b, a), checker.Equals, true)
-}
+	before := ethutil.CopyBytes(trie.roothash)
+	trie.UpdateString("should", "revert")
+	trie.Hash()
+	// Should have no effect
+	trie.Hash()
+	trie.Hash()
+	// ###
 
-func (s *TrieSuite) TestItems(c *checker.C) {
-	s.trie.Update("A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
-	exp := "d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab"
+	trie.Reset()
+	after := ethutil.CopyBytes(trie.roothash)
 
-	c.Assert(s.trie.GetRoot(), checker.DeepEquals, ethutil.Hex2Bytes(exp))
+	if !bytes.Equal(before, after) {
+		t.Errorf("expected roots to be equal. %x - %x", before, after)
+	}
 }
 
-func TestOtherSomething(t *testing.T) {
-	_, trie := NewTrie()
+func TestParanoia(t *testing.T) {
+	t.Skip()
+	trie := NewEmpty()
 
 	vals := []struct{ k, v string }{
 		{"do", "verb"},
@@ -350,20 +193,40 @@ func TestOtherSomething(t *testing.T) {
 		{"ether", ""},
 		{"dog", "puppy"},
 		{"shaman", ""},
+		{"somethingveryoddindeedthis is", "myothernodedata"},
 	}
 	for _, val := range vals {
-		trie.Update(val.k, val.v)
+		trie.UpdateString(val.k, val.v)
 	}
+	trie.Commit()
 
-	exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
-	hash := trie.Root.([]byte)
-	if !bytes.Equal(hash, exp) {
-		t.Errorf("expected %x got %x", exp, hash)
+	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 := NewTrie()
+	trie := NewEmpty()
 	vals := []struct{ k, v string }{
 		{"do", "verb"},
 		{"ether", "wookiedoo"},
@@ -376,21 +239,21 @@ func BenchmarkGets(b *testing.B) {
 		{"somethingveryoddindeedthis is", "myothernodedata"},
 	}
 	for _, val := range vals {
-		trie.Update(val.k, val.v)
+		trie.UpdateString(val.k, val.v)
 	}
 
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
-		trie.Get("horse")
+		trie.Get([]byte("horse"))
 	}
 }
 
 func BenchmarkUpdate(b *testing.B) {
-	_, trie := NewTrie()
+	trie := NewEmpty()
 
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
-		trie.Update(fmt.Sprintf("aaaaaaaaaaaaaaa%d", i), "value")
+		trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", i), "value")
 	}
+	trie.Hash()
 }
-*/