aboutsummaryrefslogtreecommitdiffstats
path: root/trie
diff options
context:
space:
mode:
Diffstat (limited to 'trie')
-rw-r--r--trie/encoding.go76
-rw-r--r--trie/encoding_test.go68
-rw-r--r--trie/iterator.go143
-rw-r--r--trie/slice.go53
-rw-r--r--trie/trie.go620
-rw-r--r--trie/trie_test.go434
6 files changed, 1394 insertions, 0 deletions
diff --git a/trie/encoding.go b/trie/encoding.go
new file mode 100644
index 000000000..4906bc90b
--- /dev/null
+++ b/trie/encoding.go
@@ -0,0 +1,76 @@
+package trie
+
+import (
+ "bytes"
+ "encoding/hex"
+ "strings"
+)
+
+func CompactEncode(hexSlice []byte) string {
+ terminator := 0
+ if hexSlice[len(hexSlice)-1] == 16 {
+ terminator = 1
+ }
+
+ if terminator == 1 {
+ hexSlice = hexSlice[:len(hexSlice)-1]
+ }
+
+ oddlen := len(hexSlice) % 2
+ flags := byte(2*terminator + oddlen)
+ if oddlen != 0 {
+ hexSlice = append([]byte{flags}, hexSlice...)
+ } else {
+ hexSlice = append([]byte{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) []byte {
+ 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) []byte {
+ base := "0123456789abcdef"
+ hexSlice := make([]byte, 0)
+
+ enc := hex.EncodeToString([]byte(str))
+ for _, v := range enc {
+ hexSlice = append(hexSlice, byte(strings.IndexByte(base, byte(v))))
+ }
+ hexSlice = append(hexSlice, 16)
+
+ return hexSlice
+}
+
+func DecodeCompact(key []byte) 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/trie/encoding_test.go b/trie/encoding_test.go
new file mode 100644
index 000000000..c9bc113c9
--- /dev/null
+++ b/trie/encoding_test.go
@@ -0,0 +1,68 @@
+package trie
+
+import (
+ "bytes"
+ "fmt"
+ "testing"
+)
+
+func TestCompactEncode(t *testing.T) {
+ 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 := []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 := []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 := []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 := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16}
+ res := CompactHexDecode("verb")
+
+ if !bytes.Equal(res, exp) {
+ t.Error("Error compact hex decode. Expected", exp, "got", res)
+ }
+}
+
+func TestCompactDecode(t *testing.T) {
+ exp := []byte{1, 2, 3, 4, 5}
+ res := CompactDecode("\x11\x23\x45")
+
+ if !bytes.Equal(res, exp) {
+ t.Error("odd compact decode. Expected", exp, "got", res)
+ }
+
+ exp = []byte{0, 1, 2, 3, 4, 5}
+ res = CompactDecode("\x00\x01\x23\x45")
+
+ if !bytes.Equal(res, exp) {
+ t.Error("even compact decode. Expected", exp, "got", res)
+ }
+
+ exp = []byte{0, 15, 1, 12, 11, 8 /*term*/, 16}
+ res = CompactDecode("\x20\x0f\x1c\xb8")
+
+ if !bytes.Equal(res, exp) {
+ t.Error("even terminated compact decode. Expected", exp, "got", res)
+ }
+
+ exp = []byte{15, 1, 12, 11, 8 /*term*/, 16}
+ res = CompactDecode("\x3f\x1c\xb8")
+
+ if !bytes.Equal(res, exp) {
+ t.Error("even terminated compact decode. Expected", exp, "got", res)
+ }
+}
diff --git a/trie/iterator.go b/trie/iterator.go
new file mode 100644
index 000000000..53d099a0c
--- /dev/null
+++ b/trie/iterator.go
@@ -0,0 +1,143 @@
+package trie
+
+import (
+ "bytes"
+
+ "github.com/ethereum/go-ethereum/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
+}
diff --git a/trie/slice.go b/trie/slice.go
new file mode 100644
index 000000000..f53b6c749
--- /dev/null
+++ b/trie/slice.go
@@ -0,0 +1,53 @@
+package trie
+
+import (
+ "bytes"
+ "math"
+)
+
+// 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 []byte) int {
+ 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
+}
+
+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/trie/trie.go b/trie/trie.go
new file mode 100644
index 000000000..b442abfe3
--- /dev/null
+++ b/trie/trie.go
@@ -0,0 +1,620 @@
+package trie
+
+import (
+ "bytes"
+ "fmt"
+ "sync"
+
+ "github.com/ethereum/go-ethereum/crypto"
+ "github.com/ethereum/go-ethereum/ethutil"
+)
+
+func ParanoiaCheck(t1 *Trie) (bool, *Trie) {
+ t2 := New(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)
+}
+
+// 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) PutValue(v interface{}, force bool) interface{} {
+ value := ethutil.NewValue(v)
+
+ enc := value.Encode()
+ if len(enc) >= 32 || force {
+ sha := crypto.Sha3(enc)
+
+ cache.nodes[string(sha)] = NewNode(sha, value, true)
+ cache.IsDirty = true
+
+ return sha
+ }
+
+ return v
+}
+
+func (cache *Cache) Put(v interface{}) interface{} {
+ return cache.PutValue(v, false)
+}
+
+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)
+
+ 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)
+
+ 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 New(db ethutil.Database, Root interface{}) *Trie {
+ // Make absolute sure the root is copied
+ r := copyRoot(Root)
+ p := copyRoot(Root)
+
+ trie := &Trie{cache: NewCache(db), Root: r, prevRoot: p}
+ trie.setRoot(Root)
+
+ return trie
+}
+
+func (self *Trie) setRoot(root interface{}) {
+ switch t := root.(type) {
+ case string:
+ if t == "" {
+ root = crypto.Sha3([]byte(""))
+ }
+ self.Root = root
+ case []byte:
+ self.Root = root
+ default:
+ self.Root = self.cache.PutValue(root, true)
+ }
+}
+
+/*
+ * Public (query) interface functions
+ */
+
+func (t *Trie) Update(key, value string) {
+ t.mut.Lock()
+ defer t.mut.Unlock()
+
+ k := CompactHexDecode(key)
+
+ root := t.UpdateState(t.Root, k, value)
+ t.setRoot(root)
+}
+
+func (t *Trie) Get(key string) string {
+ t.mut.Lock()
+ defer t.mut.Unlock()
+
+ k := CompactHexDecode(key)
+ c := ethutil.NewValue(t.getState(t.Root, k))
+
+ return c.Str()
+}
+
+func (t *Trie) Delete(key string) {
+ t.mut.Lock()
+ defer t.mut.Unlock()
+
+ k := CompactHexDecode(key)
+
+ root := t.deleteState(t.Root, k)
+ t.setRoot(root)
+}
+
+func (self *Trie) GetRoot() []byte {
+ switch self.Root.(type) {
+ case string:
+ return []byte(self.Root.(string))
+ case []byte:
+ return self.Root.([]byte)
+ default:
+ panic(fmt.Sprintf("invalid root type %T", self.Root))
+ }
+}
+
+// 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 := New(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 []byte) 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) && 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(int(key[0])).Raw(), key[1:])
+ }
+
+ // It shouldn't come this far
+ panic("unexpected 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))
+ }
+
+ data := t.cache.Get(n.Bytes())
+
+ return data
+}
+
+func (t *Trie) UpdateState(node interface{}, key []byte, value string) interface{} {
+ return t.InsertState(node, key, value)
+}
+
+func (t *Trie) Put(node interface{}) interface{} {
+ 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 []byte, value interface{}) interface{} {
+ if len(key) == 0 {
+ return value
+ }
+
+ // New node
+ n := ethutil.NewValue(node)
+ if node == nil || 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 bytes.Equal(k, key) { //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(int(key[0])).Raw(), key[1:], value)
+
+ return t.Put(newNode)
+ }
+
+ panic("unexpected end")
+}
+
+func (t *Trie) deleteState(node interface{}, key []byte) 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 {
+ if node == nil || n.Len() == 0 {
+ //return nil
+ //fmt.Printf("<empty ret> %x %d\n", n, len(n.Bytes()))
+
+ 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 bytes.Equal(k, key) { //CompareIntSlice(k, key) {
+ //fmt.Printf("<delete ret> %x\n", v)
+
+ return ""
+ } else if bytes.Equal(key[:len(k)], k) { //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}
+ }
+
+ //fmt.Printf("%x\n", newNode)
+
+ 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([]byte{16}), n[amount]}
+ } else if amount >= 0 {
+ child := t.getNode(n[amount])
+ if child.Len() == 17 {
+ newNode = []interface{}{CompactEncode([]byte{byte(amount)}), n[amount]}
+ } else if child.Len() == 2 {
+ key := append([]byte{byte(amount)}, CompactDecode(child.Get(0).Str())...)
+ newNode = []interface{}{CompactEncode(key), child.Get(1).Str()}
+ }
+
+ } else {
+ newNode = n
+ }
+
+ //fmt.Printf("%x\n", newNode)
+ return t.Put(newNode)
+ }
+
+ panic("unexpected return")
+}
+
+type TrieIterator struct {
+ trie *Trie
+ key string
+ value string
+
+ shas [][]byte
+ values []string
+
+ lastNode []byte
+}
+
+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) {
+ 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 []byte, node []byte, cb EachCallback) {
+ it.iterateNode(key, it.trie.cache.Get(node), cb)
+}
+
+func (it *TrieIterator) iterateNode(key []byte, currentNode *ethutil.Value, cb EachCallback) {
+ if currentNode.Len() == 2 {
+ k := CompactDecode(currentNode.Get(0).Str())
+
+ pk := append(key, k...)
+ 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 {
+ it.fetchNode(pk, currentNode.Get(1).Bytes(), cb)
+ }
+ }
+ } else {
+ for i := 0; i < currentNode.Len(); i++ {
+ pk := append(key, byte(i))
+ if i == 16 && currentNode.Get(i).Len() != 0 {
+ cb(DecodeCompact(pk), currentNode.Get(i))
+ } else {
+ if currentNode.Get(i).Len() != 0 && 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/trie/trie_test.go b/trie/trie_test.go
new file mode 100644
index 000000000..5f3975915
--- /dev/null
+++ b/trie/trie_test.go
@@ -0,0 +1,434 @@
+package trie
+
+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"))))
+}
+*/
generated by cgit (git 2.34.1) at 2024-11-16 10:18:02 +0800