From af34749a6b47ff8f9b4cb55d9ea65e1235d63b68 Mon Sep 17 00:00:00 2001 From: obscuren Date: Fri, 31 Oct 2014 14:45:03 +0100 Subject: ethtrie => trie --- ethtrie/trie_test.go | 434 --------------------------------------------------- 1 file changed, 434 deletions(-) delete mode 100644 ethtrie/trie_test.go (limited to 'ethtrie/trie_test.go') diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go deleted file mode 100644 index a70916483..000000000 --- a/ethtrie/trie_test.go +++ /dev/null @@ -1,434 +0,0 @@ -package ethtrie - -import ( - "bytes" - "encoding/hex" - "encoding/json" - "fmt" - "io/ioutil" - "math/rand" - "net/http" - "reflect" - "testing" - "time" - - "github.com/ethereum/go-ethereum/ethutil" -) - -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 NewTrie() (*MemDatabase, *Trie) { - db, _ := NewMemDatabase() - 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 TestTrieDirtyTracking(t *testing.T) { - _, trie := NewTrie() - 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 := NewTrie() - - 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 := NewTrie() - - 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 := 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 TestTrieCmp(t *testing.T) { - _, 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") - } - - 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 := 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 TestTrieDeleteWithValue(t *testing.T) { - _, 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 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) - } - - if lenBefore == len(trie.cache.nodes) { - t.Errorf("Expected cached nodes to be deleted") - } -} - -func h(str string) string { - d, err := hex.DecodeString(str) - if err != nil { - panic(err) - } - - return string(d) -} - -func get(in string) (out string) { - if len(in) > 2 && in[:2] == "0x" { - out = h(in[2:]) - } else { - out = in - } - - return -} - -type Test struct { - Name string - In map[string]string - Root string -} - -func CreateTest(name string, data []byte) (Test, error) { - t := Test{Name: name} - err := json.Unmarshal(data, &t) - if err != nil { - return Test{}, fmt.Errorf("%v", err) - } - - return t, nil -} - -func CreateTests(uri string, cb func(Test)) map[string]Test { - resp, err := http.Get(uri) - if err != nil { - panic(err) - } - 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) - } - - tests := make(map[string]Test) - for name, testData := range objmap { - test, err := CreateTest(name, *testData) - if err != nil { - panic(err) - } - - if cb != nil { - cb(test) - } - tests[name] = test - } - - return tests -} - -func RandomData() [][]string { - data := [][]string{ - {"0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1", "0x4e616d6552656700000000000000000000000000000000000000000000000000"}, - {"0x0000000000000000000000000000000000000000000000000000000000000045", "0x22b224a1420a802ab51d326e29fa98e34c4f24ea"}, - {"0x0000000000000000000000000000000000000000000000000000000000000046", "0x67706c2076330000000000000000000000000000000000000000000000000000"}, - {"0x000000000000000000000000697c7b8c961b56f675d570498424ac8de1a918f6", "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000"}, - {"0x0000000000000000000000007ef9e639e2733cb34e4dfc576d4b23f72db776b2", "0x4655474156000000000000000000000000000000000000000000000000000000"}, - {"0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000", "0x697c7b8c961b56f675d570498424ac8de1a918f6"}, - {"0x4655474156000000000000000000000000000000000000000000000000000000", "0x7ef9e639e2733cb34e4dfc576d4b23f72db776b2"}, - {"0x4e616d6552656700000000000000000000000000000000000000000000000000", "0xec4f34c97e43fbb2816cfd95e388353c7181dab1"}, - } - - 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] - } - - return c -} - -const MaxTest = 1000 - -// This test insert data in random order and seeks to find indifferences between the different tries -func TestRegression(t *testing.T) { - 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 - } - - 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") - - _, t2 := NewTrie() - 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() - - 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() - - 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