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/encoding.go | 76 +++++++ ethtrie/encoding_test.go | 67 ++++++ ethtrie/slice.go | 26 +++ ethtrie/trie.go | 563 +++++++++++++++++++++++++++++++++++++++++++++++ ethtrie/trie_test.go | 193 ++++++++++++++++ 5 files changed, 925 insertions(+) create mode 100644 ethtrie/encoding.go create mode 100644 ethtrie/encoding_test.go create mode 100644 ethtrie/slice.go create mode 100644 ethtrie/trie.go create mode 100644 ethtrie/trie_test.go (limited to 'ethtrie') diff --git a/ethtrie/encoding.go b/ethtrie/encoding.go new file mode 100644 index 000000000..c9c391110 --- /dev/null +++ b/ethtrie/encoding.go @@ -0,0 +1,76 @@ +package ethtrie + +import ( + "bytes" + "encoding/hex" + "strings" +) + +func CompactEncode(hexSlice []int) string { + terminator := 0 + if hexSlice[len(hexSlice)-1] == 16 { + terminator = 1 + } + + if terminator == 1 { + hexSlice = hexSlice[:len(hexSlice)-1] + } + + oddlen := len(hexSlice) % 2 + flags := 2*terminator + oddlen + if oddlen != 0 { + hexSlice = append([]int{flags}, hexSlice...) + } else { + hexSlice = append([]int{flags, 0}, hexSlice...) + } + + var buff bytes.Buffer + for i := 0; i < len(hexSlice); i += 2 { + buff.WriteByte(byte(16*hexSlice[i] + hexSlice[i+1])) + } + + return buff.String() +} + +func CompactDecode(str string) []int { + base := CompactHexDecode(str) + base = base[:len(base)-1] + if base[0] >= 2 { + base = append(base, 16) + } + if base[0]%2 == 1 { + base = base[1:] + } else { + base = base[2:] + } + + return base +} + +func CompactHexDecode(str string) []int { + base := "0123456789abcdef" + hexSlice := make([]int, 0) + + enc := hex.EncodeToString([]byte(str)) + for _, v := range enc { + hexSlice = append(hexSlice, strings.IndexByte(base, byte(v))) + } + hexSlice = append(hexSlice, 16) + + return hexSlice +} + +func DecodeCompact(key []int) string { + base := "0123456789abcdef" + var str string + + for _, v := range key { + if v < 16 { + str += string(base[v]) + } + } + + res, _ := hex.DecodeString(str) + + return string(res) +} diff --git a/ethtrie/encoding_test.go b/ethtrie/encoding_test.go new file mode 100644 index 000000000..7a4849678 --- /dev/null +++ b/ethtrie/encoding_test.go @@ -0,0 +1,67 @@ +package ethtrie + +import ( + "fmt" + "testing" +) + +func TestCompactEncode(t *testing.T) { + test1 := []int{1, 2, 3, 4, 5} + if res := CompactEncode(test1); res != "\x11\x23\x45" { + t.Error(fmt.Sprintf("even compact encode failed. Got: %q", res)) + } + + test2 := []int{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)) + } + + test3 := []int{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)) + } + + test4 := []int{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)) + } +} + +func TestCompactHexDecode(t *testing.T) { + exp := []int{7, 6, 6, 5, 7, 2, 6, 2, 16} + res := CompactHexDecode("verb") + + if !CompareIntSlice(res, exp) { + t.Error("Error compact hex decode. Expected", exp, "got", res) + } +} + +func TestCompactDecode(t *testing.T) { + exp := []int{1, 2, 3, 4, 5} + res := CompactDecode("\x11\x23\x45") + + if !CompareIntSlice(res, exp) { + t.Error("odd compact decode. Expected", exp, "got", res) + } + + exp = []int{0, 1, 2, 3, 4, 5} + res = CompactDecode("\x00\x01\x23\x45") + + if !CompareIntSlice(res, exp) { + t.Error("even compact decode. Expected", exp, "got", res) + } + + exp = []int{0, 15, 1, 12, 11, 8 /*term*/, 16} + res = CompactDecode("\x20\x0f\x1c\xb8") + + if !CompareIntSlice(res, exp) { + t.Error("even terminated compact decode. Expected", exp, "got", res) + } + + exp = []int{15, 1, 12, 11, 8 /*term*/, 16} + res = CompactDecode("\x3f\x1c\xb8") + + if !CompareIntSlice(res, exp) { + t.Error("even terminated compact decode. Expected", exp, "got", res) + } +} diff --git a/ethtrie/slice.go b/ethtrie/slice.go new file mode 100644 index 000000000..b9d5d1285 --- /dev/null +++ b/ethtrie/slice.go @@ -0,0 +1,26 @@ +package ethtrie + +import () + +// Helper function for comparing slices +func CompareIntSlice(a, b []int) bool { + if len(a) != len(b) { + return false + } + for i, v := range a { + if v != b[i] { + return false + } + } + return true +} + +// Returns the amount of nibbles that match each other from 0 ... +func MatchingNibbleLength(a, b []int) int { + i := 0 + for CompareIntSlice(a[:i+1], b[:i+1]) && i < len(b) { + i += 1 + } + + return i +} diff --git a/ethtrie/trie.go b/ethtrie/trie.go new file mode 100644 index 000000000..c957e9b4c --- /dev/null +++ b/ethtrie/trie.go @@ -0,0 +1,563 @@ +package ethtrie + +import ( + "fmt" + "github.com/ethereum/eth-go/ethcrypto" + "github.com/ethereum/eth-go/ethutil" + "reflect" + "sync" +) + +func (s *Cache) Len() int { + return len(s.nodes) +} + +// TODO +// A StateObject is an object that has a state root +// This is goig to be the object for the second level caching (the caching of object which have a state such as contracts) +type StateObject interface { + State() *Trie + Sync() + Undo() +} + +type Node struct { + Key []byte + Value *ethutil.Value + Dirty bool +} + +func NewNode(key []byte, val *ethutil.Value, dirty bool) *Node { + return &Node{Key: key, Value: val, Dirty: dirty} +} + +func (n *Node) Copy() *Node { + return NewNode(n.Key, n.Value, n.Dirty) +} + +type Cache struct { + nodes map[string]*Node + db ethutil.Database + IsDirty bool +} + +func NewCache(db ethutil.Database) *Cache { + return &Cache{db: db, nodes: make(map[string]*Node)} +} + +func (cache *Cache) Put(v interface{}) interface{} { + value := ethutil.NewValue(v) + + enc := value.Encode() + if len(enc) >= 32 { + sha := ethcrypto.Sha3Bin(enc) + + cache.nodes[string(sha)] = NewNode(sha, value, true) + cache.IsDirty = true + + return sha + } + + return v +} + +func (cache *Cache) Get(key []byte) *ethutil.Value { + // First check if the key is the cache + if cache.nodes[string(key)] != nil { + return cache.nodes[string(key)].Value + } + + // Get the key of the database instead and cache it + data, _ := cache.db.Get(key) + // Create the cached value + value := ethutil.NewValueFromBytes(data) + // Create caching node + cache.nodes[string(key)] = NewNode(key, value, false) + + return value +} + +func (cache *Cache) Delete(key []byte) { + delete(cache.nodes, string(key)) + + cache.db.Delete(key) +} + +func (cache *Cache) Commit() { + // Don't try to commit if it isn't dirty + if !cache.IsDirty { + return + } + + for key, node := range cache.nodes { + if node.Dirty { + cache.db.Put([]byte(key), node.Value.Encode()) + node.Dirty = false + } + } + cache.IsDirty = false + + // If the nodes grows beyond the 200 entries we simple empty it + // FIXME come up with something better + if len(cache.nodes) > 200 { + cache.nodes = make(map[string]*Node) + } +} + +func (cache *Cache) Undo() { + for key, node := range cache.nodes { + if node.Dirty { + delete(cache.nodes, key) + } + } + cache.IsDirty = false +} + +// A (modified) Radix Trie implementation. The Trie implements +// a caching mechanism and will used cached values if they are +// present. If a node is not present in the cache it will try to +// fetch it from the database and store the cached value. +// Please note that the data isn't persisted unless `Sync` is +// explicitly called. +type Trie struct { + mut sync.RWMutex + prevRoot interface{} + Root interface{} + //db Database + cache *Cache +} + +func copyRoot(root interface{}) interface{} { + var prevRootCopy interface{} + if b, ok := root.([]byte); ok { + prevRootCopy = ethutil.CopyBytes(b) + } else { + prevRootCopy = root + } + + return prevRootCopy +} + +func NewTrie(db ethutil.Database, Root interface{}) *Trie { + // Make absolute sure the root is copied + r := copyRoot(Root) + p := copyRoot(Root) + + return &Trie{cache: NewCache(db), Root: r, prevRoot: p} +} + +// Save the cached value to the database. +func (t *Trie) Sync() { + t.cache.Commit() + t.prevRoot = copyRoot(t.Root) +} + +func (t *Trie) Undo() { + t.cache.Undo() + t.Root = t.prevRoot +} + +func (t *Trie) Cache() *Cache { + return t.cache +} + +/* + * Public (query) interface functions + */ +func (t *Trie) Update(key string, value string) { + t.mut.Lock() + defer t.mut.Unlock() + + k := CompactHexDecode(key) + + t.Root = t.UpdateState(t.Root, k, value) +} + +func (t *Trie) Get(key string) string { + t.mut.RLock() + defer t.mut.RUnlock() + + k := CompactHexDecode(key) + c := ethutil.NewValue(t.GetState(t.Root, k)) + + return c.Str() +} + +func (t *Trie) Delete(key string) { + t.Update(key, "") +} + +func (t *Trie) GetState(node interface{}, key []int) interface{} { + n := ethutil.NewValue(node) + // Return the node if key is empty (= found) + if len(key) == 0 || n.IsNil() || n.Len() == 0 { + return node + } + + currentNode := t.GetNode(node) + length := currentNode.Len() + + if length == 0 { + return "" + } else if length == 2 { + // Decode the key + k := CompactDecode(currentNode.Get(0).Str()) + v := currentNode.Get(1).Raw() + + if len(key) >= len(k) && CompareIntSlice(k, key[:len(k)]) { + return t.GetState(v, key[len(k):]) + } else { + return "" + } + } else if length == 17 { + return t.GetState(currentNode.Get(key[0]).Raw(), key[1:]) + } + + // It shouldn't come this far + fmt.Println("GetState unexpected return") + return "" +} + +func (t *Trie) GetNode(node interface{}) *ethutil.Value { + n := ethutil.NewValue(node) + + if !n.Get(0).IsNil() { + return n + } + + str := n.Str() + if len(str) == 0 { + return n + } else if len(str) < 32 { + return ethutil.NewValueFromBytes([]byte(str)) + } + + return t.cache.Get(n.Bytes()) +} + +func (t *Trie) UpdateState(node interface{}, key []int, value string) interface{} { + + if value != "" { + return t.InsertState(node, key, value) + } else { + // delete it + return t.DeleteState(node, key) + } + + return t.Root +} + +func (t *Trie) Put(node interface{}) interface{} { + /* + TODO? + c := Conv(t.Root) + fmt.Println(c.Type(), c.Length()) + if c.Type() == reflect.String && c.AsString() == "" { + return enc + } + */ + + return t.cache.Put(node) + +} + +func EmptyStringSlice(l int) []interface{} { + slice := make([]interface{}, l) + for i := 0; i < l; i++ { + slice[i] = "" + } + return slice +} + +func (t *Trie) InsertState(node interface{}, key []int, value interface{}) interface{} { + if len(key) == 0 { + return value + } + + // New node + n := ethutil.NewValue(node) + 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) + } + + currentNode := t.GetNode(node) + // Check for "special" 2 slice type node + if currentNode.Len() == 2 { + // Decode the key + + k := CompactDecode(currentNode.Get(0).Str()) + v := currentNode.Get(1).Raw() + + // Matching key pair (ie. there's already an object with this key) + if CompareIntSlice(k, key) { + newNode := []interface{}{CompactEncode(key), value} + return t.Put(newNode) + } + + var newHash interface{} + matchingLength := MatchingNibbleLength(key, k) + if matchingLength == len(k) { + // Insert the hash, creating a new node + newHash = t.InsertState(v, key[matchingLength:], value) + } else { + // Expand the 2 length slice to a 17 length slice + oldNode := t.InsertState("", k[matchingLength+1:], v) + newNode := t.InsertState("", key[matchingLength+1:], value) + // Create an expanded slice + scaledSlice := EmptyStringSlice(17) + // Set the copied and new node + scaledSlice[k[matchingLength]] = oldNode + scaledSlice[key[matchingLength]] = newNode + + newHash = t.Put(scaledSlice) + } + + if matchingLength == 0 { + // End of the chain, return + return newHash + } else { + newNode := []interface{}{CompactEncode(key[:matchingLength]), newHash} + return t.Put(newNode) + } + } else { + + // Copy the current node over to the new node and replace the first nibble in the key + newNode := EmptyStringSlice(17) + + for i := 0; i < 17; i++ { + cpy := currentNode.Get(i).Raw() + if cpy != nil { + newNode[i] = cpy + } + } + + newNode[key[0]] = t.InsertState(currentNode.Get(key[0]).Raw(), key[1:], value) + + return t.Put(newNode) + } + + return "" +} + +func (t *Trie) DeleteState(node interface{}, key []int) interface{} { + if len(key) == 0 { + return "" + } + + // New node + n := ethutil.NewValue(node) + if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { + return "" + } + + currentNode := t.GetNode(node) + // Check for "special" 2 slice type node + if currentNode.Len() == 2 { + // Decode the key + k := CompactDecode(currentNode.Get(0).Str()) + v := currentNode.Get(1).Raw() + + // Matching key pair (ie. there's already an object with this key) + if CompareIntSlice(k, key) { + return "" + } else if CompareIntSlice(key[:len(k)], k) { + hash := t.DeleteState(v, key[len(k):]) + child := t.GetNode(hash) + + var newNode []interface{} + if child.Len() == 2 { + newKey := append(k, CompactDecode(child.Get(0).Str())...) + newNode = []interface{}{CompactEncode(newKey), child.Get(1).Raw()} + } else { + newNode = []interface{}{currentNode.Get(0).Str(), hash} + } + + return t.Put(newNode) + } else { + return node + } + } else { + // Copy the current node over to the new node and replace the first nibble in the key + n := EmptyStringSlice(17) + var newNode []interface{} + + for i := 0; i < 17; i++ { + cpy := currentNode.Get(i).Raw() + if cpy != nil { + n[i] = cpy + } + } + + n[key[0]] = t.DeleteState(n[key[0]], key[1:]) + amount := -1 + for i := 0; i < 17; i++ { + if n[i] != "" { + if amount == -1 { + amount = i + } else { + amount = -2 + } + } + } + if amount == 16 { + newNode = []interface{}{CompactEncode([]int{16}), n[amount]} + } else if amount >= 0 { + child := t.GetNode(n[amount]) + if child.Len() == 17 { + newNode = []interface{}{CompactEncode([]int{amount}), n[amount]} + } else if child.Len() == 2 { + key := append([]int{amount}, CompactDecode(child.Get(0).Str())...) + newNode = []interface{}{CompactEncode(key), child.Get(1).Str()} + } + + } else { + newNode = n + } + + return t.Put(newNode) + } + + return "" +} + +// Simple compare function which creates a rlp value out of the evaluated objects +func (t *Trie) Cmp(trie *Trie) bool { + return ethutil.NewValue(t.Root).Cmp(ethutil.NewValue(trie.Root)) +} + +// Returns a copy of this trie +func (t *Trie) Copy() *Trie { + trie := NewTrie(t.cache.db, t.Root) + for key, node := range t.cache.nodes { + trie.cache.nodes[key] = node.Copy() + } + + return trie +} + +type TrieIterator struct { + trie *Trie + key string + value string + + shas [][]byte + values []string + + lastNode []byte +} + +func (t *Trie) NewIterator() *TrieIterator { + return &TrieIterator{trie: t} +} + +// Some time in the near future this will need refactoring :-) +// XXX Note to self, IsSlice == inline node. Str == sha3 to node +func (it *TrieIterator) workNode(currentNode *ethutil.Value) { + if currentNode.Len() == 2 { + k := CompactDecode(currentNode.Get(0).Str()) + + if currentNode.Get(1).Str() == "" { + it.workNode(currentNode.Get(1)) + } else { + if k[len(k)-1] == 16 { + it.values = append(it.values, currentNode.Get(1).Str()) + } else { + it.shas = append(it.shas, currentNode.Get(1).Bytes()) + it.getNode(currentNode.Get(1).Bytes()) + } + } + } else { + for i := 0; i < currentNode.Len(); i++ { + if i == 16 && currentNode.Get(i).Len() != 0 { + it.values = append(it.values, currentNode.Get(i).Str()) + } else { + if currentNode.Get(i).Str() == "" { + it.workNode(currentNode.Get(i)) + } else { + val := currentNode.Get(i).Str() + if val != "" { + it.shas = append(it.shas, currentNode.Get(1).Bytes()) + it.getNode([]byte(val)) + } + } + } + } + } +} + +func (it *TrieIterator) getNode(node []byte) { + currentNode := it.trie.cache.Get(node) + it.workNode(currentNode) +} + +func (it *TrieIterator) Collect() [][]byte { + if it.trie.Root == "" { + return nil + } + + it.getNode(ethutil.NewValue(it.trie.Root).Bytes()) + + return it.shas +} + +func (it *TrieIterator) Purge() int { + shas := it.Collect() + for _, sha := range shas { + it.trie.cache.Delete(sha) + } + return len(it.values) +} + +func (it *TrieIterator) Key() string { + return "" +} + +func (it *TrieIterator) Value() string { + return "" +} + +type EachCallback func(key string, node *ethutil.Value) + +func (it *TrieIterator) Each(cb EachCallback) { + it.fetchNode(nil, ethutil.NewValue(it.trie.Root).Bytes(), cb) +} + +func (it *TrieIterator) fetchNode(key []int, node []byte, cb EachCallback) { + it.iterateNode(key, it.trie.cache.Get(node), cb) +} + +func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb EachCallback) { + if currentNode.Len() == 2 { + k := CompactDecode(currentNode.Get(0).Str()) + + if currentNode.Get(1).Str() == "" { + it.iterateNode(key, currentNode.Get(1), cb) + } else { + pk := append(key, k...) + + if k[len(k)-1] == 16 { + cb(DecodeCompact(pk), currentNode.Get(1)) + } else { + it.fetchNode(pk, currentNode.Get(1).Bytes(), cb) + } + } + } else { + for i := 0; i < currentNode.Len(); i++ { + pk := append(key, i) + if i == 16 && currentNode.Get(i).Len() != 0 { + cb(DecodeCompact(pk), currentNode.Get(i)) + } else { + if currentNode.Get(i).Str() == "" { + it.iterateNode(pk, currentNode.Get(i), cb) + } else { + val := currentNode.Get(i).Str() + if val != "" { + it.fetchNode(pk, []byte(val), cb) + } + } + } + } + } +} 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 From 6748158ab4e437a983988f5477a2bea56a20e009 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 2 Jul 2014 13:40:02 +0200 Subject: Moved methods --- ethtrie/trie.go | 93 +++++++++++++++++++++++++++++---------------------------- 1 file changed, 47 insertions(+), 46 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 6a5d3807c..194c98006 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -150,25 +150,11 @@ func NewTrie(db ethutil.Database, Root interface{}) *Trie { return &Trie{cache: NewCache(db), Root: r, prevRoot: p} } -// Save the cached value to the database. -func (t *Trie) Sync() { - t.cache.Commit() - t.prevRoot = copyRoot(t.Root) -} - -func (t *Trie) Undo() { - t.cache.Undo() - t.Root = t.prevRoot -} - -func (t *Trie) Cache() *Cache { - return t.cache -} - /* * Public (query) interface functions */ -func (t *Trie) Update(key string, value string) { + +func (t *Trie) Update(key, value string) { t.mut.Lock() defer t.mut.Unlock() @@ -190,7 +176,7 @@ func (t *Trie) Get(key string) string { defer t.mut.RUnlock() k := CompactHexDecode(key) - c := ethutil.NewValue(t.GetState(t.Root, k)) + c := ethutil.NewValue(t.getState(t.Root, k)) return c.Str() } @@ -201,7 +187,7 @@ func (t *Trie) Delete(key string) { k := CompactHexDecode(key) - root := t.DeleteState(t.Root, k) + root := t.deleteState(t.Root, k) switch root.(type) { case string: t.Root = root @@ -212,14 +198,44 @@ func (t *Trie) Delete(key string) { } } -func (t *Trie) GetState(node interface{}, key []int) interface{} { +// Simple compare function which creates a rlp value out of the evaluated objects +func (t *Trie) Cmp(trie *Trie) bool { + return ethutil.NewValue(t.Root).Cmp(ethutil.NewValue(trie.Root)) +} + +// Returns a copy of this trie +func (t *Trie) Copy() *Trie { + trie := NewTrie(t.cache.db, t.Root) + for key, node := range t.cache.nodes { + trie.cache.nodes[key] = node.Copy() + } + + return trie +} + +// Save the cached value to the database. +func (t *Trie) Sync() { + t.cache.Commit() + t.prevRoot = copyRoot(t.Root) +} + +func (t *Trie) Undo() { + t.cache.Undo() + t.Root = t.prevRoot +} + +func (t *Trie) Cache() *Cache { + return t.cache +} + +func (t *Trie) getState(node interface{}, key []int) interface{} { n := ethutil.NewValue(node) // Return the node if key is empty (= found) if len(key) == 0 || n.IsNil() || n.Len() == 0 { return node } - currentNode := t.GetNode(node) + currentNode := t.getNode(node) length := currentNode.Len() if length == 0 { @@ -230,20 +246,20 @@ func (t *Trie) GetState(node interface{}, key []int) interface{} { v := currentNode.Get(1).Raw() if len(key) >= len(k) && CompareIntSlice(k, key[:len(k)]) { - return t.GetState(v, key[len(k):]) + return t.getState(v, key[len(k):]) } else { return "" } } else if length == 17 { - return t.GetState(currentNode.Get(key[0]).Raw(), key[1:]) + return t.getState(currentNode.Get(key[0]).Raw(), key[1:]) } // It shouldn't come this far - fmt.Println("GetState unexpected return") + fmt.Println("getState unexpected return") return "" } -func (t *Trie) GetNode(node interface{}) *ethutil.Value { +func (t *Trie) getNode(node interface{}) *ethutil.Value { n := ethutil.NewValue(node) if !n.Get(0).IsNil() { @@ -299,7 +315,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter return t.Put(newNode) } - currentNode := t.GetNode(node) + currentNode := t.getNode(node) // Check for "special" 2 slice type node if currentNode.Len() == 2 { // Decode the key @@ -358,7 +374,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter return "" } -func (t *Trie) DeleteState(node interface{}, key []int) interface{} { +func (t *Trie) deleteState(node interface{}, key []int) interface{} { if len(key) == 0 { return "" } @@ -369,7 +385,7 @@ func (t *Trie) DeleteState(node interface{}, key []int) interface{} { return "" } - currentNode := t.GetNode(node) + currentNode := t.getNode(node) // Check for "special" 2 slice type node if currentNode.Len() == 2 { // Decode the key @@ -380,8 +396,8 @@ func (t *Trie) DeleteState(node interface{}, key []int) interface{} { if CompareIntSlice(k, key) { return "" } else if CompareIntSlice(key[:len(k)], k) { - hash := t.DeleteState(v, key[len(k):]) - child := t.GetNode(hash) + hash := t.deleteState(v, key[len(k):]) + child := t.getNode(hash) var newNode []interface{} if child.Len() == 2 { @@ -407,7 +423,7 @@ func (t *Trie) DeleteState(node interface{}, key []int) interface{} { } } - n[key[0]] = t.DeleteState(n[key[0]], key[1:]) + n[key[0]] = t.deleteState(n[key[0]], key[1:]) amount := -1 for i := 0; i < 17; i++ { if n[i] != "" { @@ -421,7 +437,7 @@ func (t *Trie) DeleteState(node interface{}, key []int) interface{} { if amount == 16 { newNode = []interface{}{CompactEncode([]int{16}), n[amount]} } else if amount >= 0 { - child := t.GetNode(n[amount]) + child := t.getNode(n[amount]) if child.Len() == 17 { newNode = []interface{}{CompactEncode([]int{amount}), n[amount]} } else if child.Len() == 2 { @@ -439,21 +455,6 @@ func (t *Trie) DeleteState(node interface{}, key []int) interface{} { return "" } -// Simple compare function which creates a rlp value out of the evaluated objects -func (t *Trie) Cmp(trie *Trie) bool { - return ethutil.NewValue(t.Root).Cmp(ethutil.NewValue(trie.Root)) -} - -// Returns a copy of this trie -func (t *Trie) Copy() *Trie { - trie := NewTrie(t.cache.db, t.Root) - for key, node := range t.cache.nodes { - trie.cache.nodes[key] = node.Copy() - } - - return trie -} - type TrieIterator struct { trie *Trie key string -- cgit From 8de099ae753b2ea427a0f43abbd04019c5f76ddf Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 2 Jul 2014 17:47:18 +0200 Subject: Added paranoia check --- ethtrie/trie.go | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 194c98006..38c78e7f4 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -1,6 +1,7 @@ package ethtrie import ( + "bytes" "fmt" "github.com/ethereum/eth-go/ethcrypto" "github.com/ethereum/eth-go/ethutil" @@ -8,6 +9,19 @@ import ( "sync" ) +func ParanoiaCheck(t1 *Trie) (bool, *Trie) { + t2 := NewTrie(ethutil.Config.Db, "") + + t1.NewIterator().Each(func(key string, v *ethutil.Value) { + t2.Update(key, v.Str()) + }) + + a := ethutil.NewValue(t2.Root).Bytes() + b := ethutil.NewValue(t1.Root).Bytes() + + return bytes.Compare(a, b) == 0, t2 +} + func (s *Cache) Len() int { return len(s.nodes) } -- cgit 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.go | 19 ++++++++++++++----- ethtrie/trie_test.go | 46 +++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 55 insertions(+), 10 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 38c78e7f4..07720be54 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -9,6 +9,8 @@ import ( "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{} { @@ -385,7 +388,7 @@ 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{} { @@ -396,6 +399,7 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { // New node n := ethutil.NewValue(node) if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { + //return nil return "" } @@ -406,12 +410,17 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { k := CompactDecode(currentNode.Get(0).Str()) v := currentNode.Get(1).Raw() + matchingLength := MatchingNibbleLength(key, k) + // Matching key pair (ie. there's already an object with this key) if CompareIntSlice(k, key) { return "" - } else if CompareIntSlice(key[:len(k)], k) { + } else if CompareIntSlice(key[:matchingLength], k) { hash := t.deleteState(v, key[len(k):]) child := t.getNode(hash) + if child.IsNil() { + return node + } var newNode []interface{} if child.Len() == 2 { 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 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.go | 30 +++++++++++++++-------- ethtrie/trie_test.go | 69 ++++++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 81 insertions(+), 18 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 07720be54..f0f3fe5a8 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -5,7 +5,7 @@ import ( "fmt" "github.com/ethereum/eth-go/ethcrypto" "github.com/ethereum/eth-go/ethutil" - "reflect" + _ "reflect" "sync" ) @@ -326,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) @@ -393,13 +394,17 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter func (t *Trie) deleteState(node interface{}, key []int) interface{} { if len(key) == 0 { + println("") 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(" %x %d\n", n, len(n.Bytes())) + return "" } @@ -410,17 +415,19 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { k := CompactDecode(currentNode.Get(0).Str()) v := currentNode.Get(1).Raw() - matchingLength := MatchingNibbleLength(key, k) - // Matching key pair (ie. there's already an object with this key) if CompareIntSlice(k, key) { + //fmt.Printf(" %x\n", v) + return "" - } else if CompareIntSlice(key[:matchingLength], k) { + } else if CompareIntSlice(key[:len(k)], k) { hash := t.deleteState(v, key[len(k):]) child := t.getNode(hash) - if child.IsNil() { - return node - } + /* + if child.IsNil() { + return node + } + */ var newNode []interface{} if child.Len() == 2 { @@ -430,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 @@ -472,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 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 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/slice.go | 12 ++++++++---- ethtrie/trie.go | 11 ++++++----- ethtrie/trie_test.go | 41 +++++++++++++++++++++-------------------- 3 files changed, 35 insertions(+), 29 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/slice.go b/ethtrie/slice.go index b9d5d1285..cf4e8df7a 100644 --- a/ethtrie/slice.go +++ b/ethtrie/slice.go @@ -1,6 +1,6 @@ package ethtrie -import () +import "math" // Helper function for comparing slices func CompareIntSlice(a, b []int) bool { @@ -17,9 +17,13 @@ func CompareIntSlice(a, b []int) bool { // Returns the amount of nibbles that match each other from 0 ... func MatchingNibbleLength(a, b []int) int { - i := 0 - for CompareIntSlice(a[:i+1], b[:i+1]) && i < len(b) { - i += 1 + var i, length = 0, int(math.Min(float64(len(a)), float64(len(b)))) + + for i < length { + if a[i] != b[i] { + break + } + i++ } return i diff --git a/ethtrie/trie.go b/ethtrie/trie.go index f0f3fe5a8..38ae0754d 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -3,16 +3,17 @@ package ethtrie import ( "bytes" "fmt" - "github.com/ethereum/eth-go/ethcrypto" - "github.com/ethereum/eth-go/ethutil" _ "reflect" "sync" + + "github.com/ethereum/eth-go/ethcrypto" + "github.com/ethereum/eth-go/ethutil" ) func __ignore() { fmt.Println("") } func ParanoiaCheck(t1 *Trie) (bool, *Trie) { - t2 := NewTrie(ethutil.Config.Db, "") + t2 := New(ethutil.Config.Db, "") t1.NewIterator().Each(func(key string, v *ethutil.Value) { t2.Update(key, v.Str()) @@ -158,7 +159,7 @@ func copyRoot(root interface{}) interface{} { return prevRootCopy } -func NewTrie(db ethutil.Database, Root interface{}) *Trie { +func New(db ethutil.Database, Root interface{}) *Trie { // Make absolute sure the root is copied r := copyRoot(Root) p := copyRoot(Root) @@ -221,7 +222,7 @@ func (t *Trie) Cmp(trie *Trie) bool { // Returns a copy of this trie func (t *Trie) Copy() *Trie { - trie := NewTrie(t.cache.db, t.Root) + trie := New(t.cache.db, t.Root) for key, node := range t.cache.nodes { trie.cache.nodes[key] = node.Copy() } 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 From f3a93b046e45a293b673a955959666ec5389c4eb Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 18 Sep 2014 01:02:15 +0200 Subject: Upped protocol version for VM change --- ethtrie/trie.go | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 38ae0754d..e6e09dd0d 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -92,6 +92,13 @@ func (cache *Cache) Get(key []byte) *ethutil.Value { data, _ := cache.db.Get(key) // Create the cached value value := ethutil.NewValueFromBytes(data) + + defer func() { + if r := recover(); r != nil { + fmt.Println("RECOVER GET", cache, cache.nodes) + panic("bye") + } + }() // Create caching node cache.nodes[string(key)] = NewNode(key, value, false) -- cgit From ad13b402d715e120009b3efb6a08d2c90139f31d Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 24 Sep 2014 17:47:01 +0200 Subject: Fixed race condition --- ethtrie/trie.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index e6e09dd0d..695ff436a 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -196,8 +196,8 @@ func (t *Trie) Update(key, value string) { } func (t *Trie) Get(key string) string { - t.mut.RLock() - defer t.mut.RUnlock() + t.mut.Lock() + defer t.mut.Unlock() k := CompactHexDecode(key) c := ethutil.NewValue(t.getState(t.Root, k)) -- cgit From 9d86a49a7327199c01977f3372c8adf748252c32 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 8 Oct 2014 12:06:39 +0200 Subject: Renamed Sha3Bin to Sha3 --- ethtrie/trie.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 695ff436a..24f6a1f08 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -67,7 +67,7 @@ func (cache *Cache) PutValue(v interface{}, force bool) interface{} { enc := value.Encode() if len(enc) >= 32 || force { - sha := ethcrypto.Sha3Bin(enc) + sha := ethcrypto.Sha3(enc) cache.nodes[string(sha)] = NewNode(sha, value, true) cache.IsDirty = true -- cgit From 6877660fe247f758d06fe95d020a29ac3f0357cc Mon Sep 17 00:00:00 2001 From: obscuren Date: Fri, 10 Oct 2014 16:56:28 +0200 Subject: Implemented new iterator --- ethtrie/iterator.go | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 143 insertions(+) create mode 100644 ethtrie/iterator.go (limited to 'ethtrie') diff --git a/ethtrie/iterator.go b/ethtrie/iterator.go new file mode 100644 index 000000000..e16816229 --- /dev/null +++ b/ethtrie/iterator.go @@ -0,0 +1,143 @@ +package ethtrie + +import ( + "bytes" + + "github.com/ethereum/eth-go/ethutil" +) + +type NodeType byte + +const ( + EmptyNode NodeType = iota + BranchNode + LeafNode + ExtNode +) + +func getType(node *ethutil.Value) NodeType { + if node.Len() == 0 { + return EmptyNode + } + + if node.Len() == 2 { + k := CompactDecode(node.Get(0).Str()) + if HasTerm(k) { + return LeafNode + } + + return ExtNode + } + + return BranchNode +} + +type Iterator struct { + Path [][]byte + trie *Trie + + Key []byte + Value *ethutil.Value +} + +func NewIterator(trie *Trie) *Iterator { + return &Iterator{trie: trie} +} + +func (self *Iterator) key(node *ethutil.Value, path [][]byte) []byte { + switch getType(node) { + case LeafNode: + k := RemTerm(CompactDecode(node.Get(0).Str())) + + self.Path = append(path, k) + self.Value = node.Get(1) + + return k + case BranchNode: + if node.Get(16).Len() > 0 { + return []byte{16} + } + + for i := byte(0); i < 16; i++ { + o := self.key(self.trie.getNode(node.Get(int(i)).Raw()), append(path, []byte{i})) + if o != nil { + return append([]byte{i}, o...) + } + } + case ExtNode: + currKey := node.Get(0).Bytes() + + return self.key(self.trie.getNode(node.Get(1).Raw()), append(path, currKey)) + } + + return nil +} + +func (self *Iterator) next(node *ethutil.Value, key []byte, path [][]byte) []byte { + switch typ := getType(node); typ { + case EmptyNode: + return nil + case BranchNode: + if len(key) > 0 { + subNode := self.trie.getNode(node.Get(int(key[0])).Raw()) + + o := self.next(subNode, key[1:], append(path, key[:1])) + if o != nil { + return append([]byte{key[0]}, o...) + } + } + + var r byte = 0 + if len(key) > 0 { + r = key[0] + 1 + } + + for i := r; i < 16; i++ { + subNode := self.trie.getNode(node.Get(int(i)).Raw()) + o := self.key(subNode, append(path, []byte{i})) + if o != nil { + return append([]byte{i}, o...) + } + } + case LeafNode, ExtNode: + k := RemTerm(CompactDecode(node.Get(0).Str())) + if typ == LeafNode { + if bytes.Compare([]byte(k), []byte(key)) > 0 { + self.Value = node.Get(1) + self.Path = append(path, k) + + return k + } + } else { + subNode := self.trie.getNode(node.Get(1).Raw()) + subKey := key[len(k):] + var ret []byte + if BeginsWith(key, k) { + ret = self.next(subNode, subKey, append(path, k)) + } else if bytes.Compare(k, key[:len(k)]) > 0 { + ret = self.key(node, append(path, k)) + } else { + ret = nil + } + + if ret != nil { + return append(k, ret...) + } + } + } + + return nil +} + +// Get the next in keys +func (self *Iterator) Next(key string) []byte { + self.trie.mut.Lock() + defer self.trie.mut.Unlock() + + k := RemTerm(CompactHexDecode(key)) + n := self.next(self.trie.getNode(self.trie.Root), k, nil) + + self.Key = []byte(DecodeCompact(n)) + + return self.Key +} -- cgit 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/encoding.go | 18 ++++---- ethtrie/encoding_test.go | 29 ++++++------- ethtrie/slice.go | 27 +++++++++++- ethtrie/trie.go | 53 +++++++++-------------- ethtrie/trie_test.go | 107 ++++++++++++++++++++++++++--------------------- 5 files changed, 129 insertions(+), 105 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/encoding.go b/ethtrie/encoding.go index c9c391110..bcf2c5669 100644 --- a/ethtrie/encoding.go +++ b/ethtrie/encoding.go @@ -6,7 +6,7 @@ import ( "strings" ) -func CompactEncode(hexSlice []int) string { +func CompactEncode(hexSlice []byte) string { terminator := 0 if hexSlice[len(hexSlice)-1] == 16 { terminator = 1 @@ -17,11 +17,11 @@ func CompactEncode(hexSlice []int) string { } oddlen := len(hexSlice) % 2 - flags := 2*terminator + oddlen + flags := byte(2*terminator + oddlen) if oddlen != 0 { - hexSlice = append([]int{flags}, hexSlice...) + hexSlice = append([]byte{flags}, hexSlice...) } else { - hexSlice = append([]int{flags, 0}, hexSlice...) + hexSlice = append([]byte{flags, 0}, hexSlice...) } var buff bytes.Buffer @@ -32,7 +32,7 @@ func CompactEncode(hexSlice []int) string { return buff.String() } -func CompactDecode(str string) []int { +func CompactDecode(str string) []byte { base := CompactHexDecode(str) base = base[:len(base)-1] if base[0] >= 2 { @@ -47,20 +47,20 @@ func CompactDecode(str string) []int { return base } -func CompactHexDecode(str string) []int { +func CompactHexDecode(str string) []byte { base := "0123456789abcdef" - hexSlice := make([]int, 0) + hexSlice := make([]byte, 0) enc := hex.EncodeToString([]byte(str)) for _, v := range enc { - hexSlice = append(hexSlice, strings.IndexByte(base, byte(v))) + hexSlice = append(hexSlice, byte(strings.IndexByte(base, byte(v)))) } hexSlice = append(hexSlice, 16) return hexSlice } -func DecodeCompact(key []int) string { +func DecodeCompact(key []byte) string { base := "0123456789abcdef" var str string diff --git a/ethtrie/encoding_test.go b/ethtrie/encoding_test.go index 7a4849678..0cceef792 100644 --- a/ethtrie/encoding_test.go +++ b/ethtrie/encoding_test.go @@ -1,67 +1,68 @@ package ethtrie import ( + "bytes" "fmt" "testing" ) func TestCompactEncode(t *testing.T) { - test1 := []int{1, 2, 3, 4, 5} + 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)) } - test2 := []int{0, 1, 2, 3, 4, 5} + 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)) } - test3 := []int{0, 15, 1, 12, 11, 8 /*term*/, 16} + 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)) } - test4 := []int{15, 1, 12, 11, 8 /*term*/, 16} + 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)) } } func TestCompactHexDecode(t *testing.T) { - exp := []int{7, 6, 6, 5, 7, 2, 6, 2, 16} + exp := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16} res := CompactHexDecode("verb") - if !CompareIntSlice(res, exp) { + if !bytes.Equal(res, exp) { t.Error("Error compact hex decode. Expected", exp, "got", res) } } func TestCompactDecode(t *testing.T) { - exp := []int{1, 2, 3, 4, 5} + exp := []byte{1, 2, 3, 4, 5} res := CompactDecode("\x11\x23\x45") - if !CompareIntSlice(res, exp) { + if !bytes.Equal(res, exp) { t.Error("odd compact decode. Expected", exp, "got", res) } - exp = []int{0, 1, 2, 3, 4, 5} + exp = []byte{0, 1, 2, 3, 4, 5} res = CompactDecode("\x00\x01\x23\x45") - if !CompareIntSlice(res, exp) { + if !bytes.Equal(res, exp) { t.Error("even compact decode. Expected", exp, "got", res) } - exp = []int{0, 15, 1, 12, 11, 8 /*term*/, 16} + exp = []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} res = CompactDecode("\x20\x0f\x1c\xb8") - if !CompareIntSlice(res, exp) { + if !bytes.Equal(res, exp) { t.Error("even terminated compact decode. Expected", exp, "got", res) } - exp = []int{15, 1, 12, 11, 8 /*term*/, 16} + exp = []byte{15, 1, 12, 11, 8 /*term*/, 16} res = CompactDecode("\x3f\x1c\xb8") - if !CompareIntSlice(res, exp) { + if !bytes.Equal(res, exp) { t.Error("even terminated compact decode. Expected", exp, "got", res) } } diff --git a/ethtrie/slice.go b/ethtrie/slice.go index cf4e8df7a..f0edc9532 100644 --- a/ethtrie/slice.go +++ b/ethtrie/slice.go @@ -1,6 +1,9 @@ package ethtrie -import "math" +import ( + "bytes" + "math" +) // Helper function for comparing slices func CompareIntSlice(a, b []int) bool { @@ -16,7 +19,7 @@ func CompareIntSlice(a, b []int) bool { } // Returns the amount of nibbles that match each other from 0 ... -func MatchingNibbleLength(a, b []int) int { +func MatchingNibbleLength(a, b []byte) int { var i, length = 0, int(math.Min(float64(len(a)), float64(len(b)))) for i < length { @@ -28,3 +31,23 @@ func MatchingNibbleLength(a, b []int) int { return i } + +func HasTerm(s []byte) bool { + return s[len(s)-1] == 16 +} + +func RemTerm(s []byte) []byte { + if HasTerm(s) { + return s[:len(s)-1] + } + + return s +} + +func BeginsWith(a, b []byte) bool { + if len(b) > len(a) { + return false + } + + return bytes.Equal(a[:len(b)], b) +} diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 24f6a1f08..0d0c13456 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -252,7 +252,7 @@ func (t *Trie) Cache() *Cache { return t.cache } -func (t *Trie) getState(node interface{}, key []int) interface{} { +func (t *Trie) getState(node interface{}, key []byte) interface{} { n := ethutil.NewValue(node) // Return the node if key is empty (= found) if len(key) == 0 || n.IsNil() || n.Len() == 0 { @@ -269,13 +269,13 @@ func (t *Trie) getState(node interface{}, key []int) interface{} { k := CompactDecode(currentNode.Get(0).Str()) v := currentNode.Get(1).Raw() - if len(key) >= len(k) && CompareIntSlice(k, key[:len(k)]) { + if len(key) >= len(k) && bytes.Equal(k, key[:len(k)]) { //CompareIntSlice(k, key[:len(k)]) { return t.getState(v, key[len(k):]) } else { return "" } } else if length == 17 { - return t.getState(currentNode.Get(key[0]).Raw(), key[1:]) + return t.getState(currentNode.Get(int(key[0])).Raw(), key[1:]) } // It shouldn't come this far @@ -301,20 +301,11 @@ func (t *Trie) getNode(node interface{}) *ethutil.Value { return data } -func (t *Trie) UpdateState(node interface{}, key []int, value string) interface{} { +func (t *Trie) UpdateState(node interface{}, key []byte, value string) interface{} { return t.InsertState(node, key, value) } func (t *Trie) Put(node interface{}) interface{} { - /* - TODO? - c := Conv(t.Root) - fmt.Println(c.Type(), c.Length()) - if c.Type() == reflect.String && c.AsString() == "" { - return enc - } - */ - return t.cache.Put(node) } @@ -327,7 +318,7 @@ func EmptyStringSlice(l int) []interface{} { return slice } -func (t *Trie) InsertState(node interface{}, key []int, value interface{}) interface{} { +func (t *Trie) InsertState(node interface{}, key []byte, value interface{}) interface{} { if len(key) == 0 { return value } @@ -335,7 +326,6 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter // New node n := ethutil.NewValue(node) 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) @@ -350,7 +340,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter v := currentNode.Get(1).Raw() // Matching key pair (ie. there's already an object with this key) - if CompareIntSlice(k, key) { + if bytes.Equal(k, key) { //CompareIntSlice(k, key) { newNode := []interface{}{CompactEncode(key), value} return t.Put(newNode) } @@ -392,7 +382,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter } } - newNode[key[0]] = t.InsertState(currentNode.Get(key[0]).Raw(), key[1:], value) + newNode[key[0]] = t.InsertState(currentNode.Get(int(key[0])).Raw(), key[1:], value) return t.Put(newNode) } @@ -400,9 +390,8 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter panic("unexpected end") } -func (t *Trie) deleteState(node interface{}, key []int) interface{} { +func (t *Trie) deleteState(node interface{}, key []byte) interface{} { if len(key) == 0 { - println("") return "" } @@ -424,18 +413,13 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { v := currentNode.Get(1).Raw() // Matching key pair (ie. there's already an object with this key) - if CompareIntSlice(k, key) { + if bytes.Equal(k, key) { //CompareIntSlice(k, key) { //fmt.Printf(" %x\n", v) return "" - } else if CompareIntSlice(key[:len(k)], k) { + } else if bytes.Equal(key[:len(k)], k) { //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 { @@ -475,13 +459,13 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { } } if amount == 16 { - newNode = []interface{}{CompactEncode([]int{16}), n[amount]} + newNode = []interface{}{CompactEncode([]byte{16}), n[amount]} } else if amount >= 0 { child := t.getNode(n[amount]) if child.Len() == 17 { - newNode = []interface{}{CompactEncode([]int{amount}), n[amount]} + newNode = []interface{}{CompactEncode([]byte{byte(amount)}), n[amount]} } else if child.Len() == 2 { - key := append([]int{amount}, CompactDecode(child.Get(0).Str())...) + key := append([]byte{byte(amount)}, CompactDecode(child.Get(0).Str())...) newNode = []interface{}{CompactEncode(key), child.Get(1).Str()} } @@ -511,6 +495,10 @@ func (t *Trie) NewIterator() *TrieIterator { return &TrieIterator{trie: t} } +func (self *Trie) Iterator() *Iterator { + return NewIterator(self) +} + // Some time in the near future this will need refactoring :-) // XXX Note to self, IsSlice == inline node. Str == sha3 to node func (it *TrieIterator) workNode(currentNode *ethutil.Value) { @@ -583,11 +571,11 @@ func (it *TrieIterator) Each(cb EachCallback) { it.fetchNode(nil, ethutil.NewValue(it.trie.Root).Bytes(), cb) } -func (it *TrieIterator) fetchNode(key []int, node []byte, cb EachCallback) { +func (it *TrieIterator) fetchNode(key []byte, node []byte, cb EachCallback) { it.iterateNode(key, it.trie.cache.Get(node), cb) } -func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb EachCallback) { +func (it *TrieIterator) iterateNode(key []byte, currentNode *ethutil.Value, cb EachCallback) { if currentNode.Len() == 2 { k := CompactDecode(currentNode.Get(0).Str()) @@ -595,7 +583,6 @@ func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb Ea if currentNode.Get(1).Len() != 0 && currentNode.Get(1).Str() == "" { it.iterateNode(pk, currentNode.Get(1), cb) } else { - if k[len(k)-1] == 16 { cb(DecodeCompact(pk), currentNode.Get(1)) } else { @@ -604,7 +591,7 @@ func (it *TrieIterator) iterateNode(key []int, currentNode *ethutil.Value, cb Ea } } else { for i := 0; i < currentNode.Len(); i++ { - pk := append(key, i) + pk := append(key, byte(i)) if i == 16 && currentNode.Get(i).Len() != 0 { cb(DecodeCompact(pk), currentNode.Get(i)) } else { 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