ethtrie => trie

6 files changed, 0 insertions, 1394 deletions

diff --git a/ethtrie/encoding.go b/ethtrie/encoding.go
deleted file mode 100644
index bcf2c5669..000000000
--- a/ethtrie/encoding.go
+++ /dev/null
@@ -1,76 +0,0 @@
-package ethtrie
-
-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/ethtrie/encoding_test.go b/ethtrie/encoding_test.go
deleted file mode 100644
index 0cceef792..000000000
--- a/ethtrie/encoding_test.go
+++ /dev/null
@@ -1,68 +0,0 @@
-package ethtrie
-
-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/ethtrie/iterator.go b/ethtrie/iterator.go
deleted file mode 100644
index 43f497416..000000000
--- a/ethtrie/iterator.go
+++ /dev/null
@@ -1,143 +0,0 @@
-package ethtrie
-
-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/ethtrie/slice.go b/ethtrie/slice.go
deleted file mode 100644
index f0edc9532..000000000
--- a/ethtrie/slice.go
+++ /dev/null
@@ -1,53 +0,0 @@
-package ethtrie
-
-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/ethtrie/trie.go b/ethtrie/trie.go
deleted file mode 100644
index 4a6613b9d..000000000
--- a/ethtrie/trie.go
+++ /dev/null
@@ -1,620 +0,0 @@
-package ethtrie
-
-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/ethtrie/trie_test.go b/ethtrie/trie_test.go
deleted file mode 100644
index a70916483..000000000
--- a/ethtrie/trie_test.go
+++ /dev/null
@@ -1,434 +0,0 @@
-package ethtrie
-
-import (
-	"bytes"
-	"encoding/hex"
-	"encoding/json"
-	"fmt"
-	"io/ioutil"
-	"math/rand"
-	"net/http"
-	"reflect"
-	"testing"
-	"time"
-
-	"github.com/ethereum/go-ethereum/ethutil"
-)
-
-const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ"
-
-type MemDatabase struct {
-	db map[string][]byte
-}
-
-func NewMemDatabase() (*MemDatabase, error) {
-	db := &MemDatabase{db: make(map[string][]byte)}
-	return db, nil
-}
-func (db *MemDatabase) Put(key []byte, value []byte) {
-	db.db[string(key)] = value
-}
-func (db *MemDatabase) Get(key []byte) ([]byte, error) {
-	return db.db[string(key)], nil
-}
-func (db *MemDatabase) Delete(key []byte) error {
-	delete(db.db, string(key))
-	return nil
-}
-func (db *MemDatabase) Print()              {}
-func (db *MemDatabase) Close()              {}
-func (db *MemDatabase) LastKnownTD() []byte { return nil }
-
-func NewTrie() (*MemDatabase, *Trie) {
-	db, _ := NewMemDatabase()
-	return db, New(db, "")
-}
-
-func TestTrieSync(t *testing.T) {
-	db, trie := NewTrie()
-
-	trie.Update("dog", LONG_WORD)
-	if len(db.db) != 0 {
-		t.Error("Expected no data in database")
-	}
-
-	trie.Sync()
-	if len(db.db) == 0 {
-		t.Error("Expected data to be persisted")
-	}
-}
-
-func TestTrieDirtyTracking(t *testing.T) {
-	_, trie := NewTrie()
-	trie.Update("dog", LONG_WORD)
-	if !trie.cache.IsDirty {
-		t.Error("Expected trie to be dirty")
-	}
-
-	trie.Sync()
-	if trie.cache.IsDirty {
-		t.Error("Expected trie not to be dirty")
-	}
-
-	trie.Update("test", LONG_WORD)
-	trie.cache.Undo()
-	if trie.cache.IsDirty {
-		t.Error("Expected trie not to be dirty")
-	}
-
-}
-
-func TestTrieReset(t *testing.T) {
-	_, trie := NewTrie()
-
-	trie.Update("cat", LONG_WORD)
-	if len(trie.cache.nodes) == 0 {
-		t.Error("Expected cached nodes")
-	}
-
-	trie.cache.Undo()
-
-	if len(trie.cache.nodes) != 0 {
-		t.Error("Expected no nodes after undo")
-	}
-}
-
-func TestTrieGet(t *testing.T) {
-	_, trie := NewTrie()
-
-	trie.Update("cat", LONG_WORD)
-	x := trie.Get("cat")
-	if x != LONG_WORD {
-		t.Error("expected %s, got %s", LONG_WORD, x)
-	}
-}
-
-func TestTrieUpdating(t *testing.T) {
-	_, trie := NewTrie()
-	trie.Update("cat", LONG_WORD)
-	trie.Update("cat", LONG_WORD+"1")
-	x := trie.Get("cat")
-	if x != LONG_WORD+"1" {
-		t.Error("expected %S, got %s", LONG_WORD+"1", x)
-	}
-}
-
-func TestTrieCmp(t *testing.T) {
-	_, trie1 := NewTrie()
-	_, trie2 := NewTrie()
-
-	trie1.Update("doge", LONG_WORD)
-	trie2.Update("doge", LONG_WORD)
-	if !trie1.Cmp(trie2) {
-		t.Error("Expected tries to be equal")
-	}
-
-	trie1.Update("dog", LONG_WORD)
-	trie2.Update("cat", LONG_WORD)
-	if trie1.Cmp(trie2) {
-		t.Errorf("Expected tries not to be equal %x %x", trie1.Root, trie2.Root)
-	}
-}
-
-func TestTrieDelete(t *testing.T) {
-	_, trie := NewTrie()
-	trie.Update("cat", LONG_WORD)
-	exp := trie.Root
-	trie.Update("dog", LONG_WORD)
-	trie.Delete("dog")
-	if !reflect.DeepEqual(exp, trie.Root) {
-		t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root)
-	}
-
-	trie.Update("dog", LONG_WORD)
-	exp = trie.Root
-	trie.Update("dude", LONG_WORD)
-	trie.Delete("dude")
-	if !reflect.DeepEqual(exp, trie.Root) {
-		t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root)
-	}
-}
-
-func TestTrieDeleteWithValue(t *testing.T) {
-	_, trie := NewTrie()
-	trie.Update("c", LONG_WORD)
-	exp := trie.Root
-	trie.Update("ca", LONG_WORD)
-	trie.Update("cat", LONG_WORD)
-	trie.Delete("ca")
-	trie.Delete("cat")
-	if !reflect.DeepEqual(exp, trie.Root) {
-		t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root)
-	}
-
-}
-
-func TestTriePurge(t *testing.T) {
-	_, trie := NewTrie()
-	trie.Update("c", LONG_WORD)
-	trie.Update("ca", LONG_WORD)
-	trie.Update("cat", LONG_WORD)
-
-	lenBefore := len(trie.cache.nodes)
-	it := trie.NewIterator()
-	if num := it.Purge(); num != 3 {
-		t.Errorf("Expected purge to return 3, got %d", num)
-	}
-
-	if lenBefore == len(trie.cache.nodes) {
-		t.Errorf("Expected cached nodes to be deleted")
-	}
-}
-
-func h(str string) string {
-	d, err := hex.DecodeString(str)
-	if err != nil {
-		panic(err)
-	}
-
-	return string(d)
-}
-
-func get(in string) (out string) {
-	if len(in) > 2 && in[:2] == "0x" {
-		out = h(in[2:])
-	} else {
-		out = in
-	}
-
-	return
-}
-
-type Test struct {
-	Name string
-	In   map[string]string
-	Root string
-}
-
-func CreateTest(name string, data []byte) (Test, error) {
-	t := Test{Name: name}
-	err := json.Unmarshal(data, &t)
-	if err != nil {
-		return Test{}, fmt.Errorf("%v", err)
-	}
-
-	return t, nil
-}
-
-func CreateTests(uri string, cb func(Test)) map[string]Test {
-	resp, err := http.Get(uri)
-	if err != nil {
-		panic(err)
-	}
-	defer resp.Body.Close()
-
-	data, err := ioutil.ReadAll(resp.Body)
-
-	var objmap map[string]*json.RawMessage
-	err = json.Unmarshal(data, &objmap)
-	if err != nil {
-		panic(err)
-	}
-
-	tests := make(map[string]Test)
-	for name, testData := range objmap {
-		test, err := CreateTest(name, *testData)
-		if err != nil {
-			panic(err)
-		}
-
-		if cb != nil {
-			cb(test)
-		}
-		tests[name] = test
-	}
-
-	return tests
-}
-
-func RandomData() [][]string {
-	data := [][]string{
-		{"0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1", "0x4e616d6552656700000000000000000000000000000000000000000000000000"},
-		{"0x0000000000000000000000000000000000000000000000000000000000000045", "0x22b224a1420a802ab51d326e29fa98e34c4f24ea"},
-		{"0x0000000000000000000000000000000000000000000000000000000000000046", "0x67706c2076330000000000000000000000000000000000000000000000000000"},
-		{"0x000000000000000000000000697c7b8c961b56f675d570498424ac8de1a918f6", "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000"},
-		{"0x0000000000000000000000007ef9e639e2733cb34e4dfc576d4b23f72db776b2", "0x4655474156000000000000000000000000000000000000000000000000000000"},
-		{"0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000", "0x697c7b8c961b56f675d570498424ac8de1a918f6"},
-		{"0x4655474156000000000000000000000000000000000000000000000000000000", "0x7ef9e639e2733cb34e4dfc576d4b23f72db776b2"},
-		{"0x4e616d6552656700000000000000000000000000000000000000000000000000", "0xec4f34c97e43fbb2816cfd95e388353c7181dab1"},
-	}
-
-	var c [][]string
-	for len(data) != 0 {
-		e := rand.Intn(len(data))
-		c = append(c, data[e])
-
-		copy(data[e:], data[e+1:])
-		data[len(data)-1] = nil
-		data = data[:len(data)-1]
-	}
-
-	return c
-}
-
-const MaxTest = 1000
-
-// This test insert data in random order and seeks to find indifferences between the different tries
-func TestRegression(t *testing.T) {
-	rand.Seed(time.Now().Unix())
-
-	roots := make(map[string]int)
-	for i := 0; i < MaxTest; i++ {
-		_, trie := NewTrie()
-		data := RandomData()
-
-		for _, test := range data {
-			trie.Update(test[0], test[1])
-		}
-		trie.Delete("0x4e616d6552656700000000000000000000000000000000000000000000000000")
-
-		roots[string(trie.Root.([]byte))] += 1
-	}
-
-	if len(roots) > 1 {
-		for root, num := range roots {
-			t.Errorf("%x => %d\n", root, num)
-		}
-	}
-}
-
-func TestDelete(t *testing.T) {
-	_, trie := NewTrie()
-
-	trie.Update("a", "jeffreytestlongstring")
-	trie.Update("aa", "otherstring")
-	trie.Update("aaa", "othermorestring")
-	trie.Update("aabbbbccc", "hithere")
-	trie.Update("abbcccdd", "hstanoehutnaheoustnh")
-	trie.Update("rnthaoeuabbcccdd", "hstanoehutnaheoustnh")
-	trie.Update("rneuabbcccdd", "hstanoehutnaheoustnh")
-	trie.Update("rneuabboeusntahoeucccdd", "hstanoehutnaheoustnh")
-	trie.Update("rnxabboeusntahoeucccdd", "hstanoehutnaheoustnh")
-	trie.Delete("aaboaestnuhbccc")
-	trie.Delete("a")
-	trie.Update("a", "nthaonethaosentuh")
-	trie.Update("c", "shtaosntehua")
-	trie.Delete("a")
-	trie.Update("aaaa", "testmegood")
-
-	_, t2 := NewTrie()
-	trie.NewIterator().Each(func(key string, v *ethutil.Value) {
-		if key == "aaaa" {
-			t2.Update(key, v.Str())
-		} else {
-			t2.Update(key, v.Str())
-		}
-	})
-
-	a := ethutil.NewValue(trie.Root).Bytes()
-	b := ethutil.NewValue(t2.Root).Bytes()
-
-	if bytes.Compare(a, b) != 0 {
-		t.Errorf("Expected %x and %x to be equal", a, b)
-	}
-}
-
-func TestTerminator(t *testing.T) {
-	key := CompactDecode("hello")
-	if !HasTerm(key) {
-		t.Errorf("Expected %v to have a terminator", key)
-	}
-}
-
-func TestIt(t *testing.T) {
-	_, trie := NewTrie()
-	trie.Update("cat", "cat")
-	trie.Update("doge", "doge")
-	trie.Update("wallace", "wallace")
-	it := trie.Iterator()
-
-	inputs := []struct {
-		In, Out string
-	}{
-		{"", "cat"},
-		{"bobo", "cat"},
-		{"c", "cat"},
-		{"car", "cat"},
-		{"catering", "doge"},
-		{"w", "wallace"},
-		{"wallace123", ""},
-	}
-
-	for _, test := range inputs {
-		res := string(it.Next(test.In))
-		if res != test.Out {
-			t.Errorf(test.In, "failed. Got", res, "Expected", test.Out)
-		}
-	}
-}
-
-func TestBeginsWith(t *testing.T) {
-	a := CompactDecode("hello")
-	b := CompactDecode("hel")
-
-	if BeginsWith(a, b) {
-		t.Errorf("Expected %x to begin with %x", a, b)
-	}
-
-	if BeginsWith(b, a) {
-		t.Errorf("Expected %x not to begin with %x", b, a)
-	}
-}
-
-/*
-func TestRndCase(t *testing.T) {
-	_, trie := NewTrie()
-
-	data := []struct{ k, v string }{
-		{"0000000000000000000000000000000000000000000000000000000000000001", "a07573657264617461000000000000000000000000000000000000000000000000"},
-		{"0000000000000000000000000000000000000000000000000000000000000003", "8453bb5b31"},
-		{"0000000000000000000000000000000000000000000000000000000000000004", "850218711a00"},
-		{"0000000000000000000000000000000000000000000000000000000000000005", "9462d7705bd0b3ecbc51a8026a25597cb28a650c79"},
-		{"0000000000000000000000000000000000000000000000000000000000000010", "947e70f9460402290a3e487dae01f610a1a8218fda"},
-		{"0000000000000000000000000000000000000000000000000000000000000111", "01"},
-		{"0000000000000000000000000000000000000000000000000000000000000112", "a053656e6174650000000000000000000000000000000000000000000000000000"},
-		{"0000000000000000000000000000000000000000000000000000000000000113", "a053656e6174650000000000000000000000000000000000000000000000000000"},
-		{"53656e6174650000000000000000000000000000000000000000000000000000", "94977e3f62f5e1ed7953697430303a3cfa2b5b736e"},
-	}
-	for _, e := range data {
-		trie.Update(string(ethutil.Hex2Bytes(e.k)), string(ethutil.Hex2Bytes(e.v)))
-	}
-
-	fmt.Printf("root after update %x\n", trie.Root)
-	trie.NewIterator().Each(func(k string, v *ethutil.Value) {
-		fmt.Printf("%x %x\n", k, v.Bytes())
-	})
-
-	data = []struct{ k, v string }{
-		{"0000000000000000000000000000000000000000000000000000000000000112", ""},
-		{"436974697a656e73000000000000000000000000000000000000000000000001", ""},
-		{"436f757274000000000000000000000000000000000000000000000000000002", ""},
-		{"53656e6174650000000000000000000000000000000000000000000000000000", ""},
-		{"436f757274000000000000000000000000000000000000000000000000000000", ""},
-		{"53656e6174650000000000000000000000000000000000000000000000000001", ""},
-		{"0000000000000000000000000000000000000000000000000000000000000113", ""},
-		{"436974697a656e73000000000000000000000000000000000000000000000000", ""},
-		{"436974697a656e73000000000000000000000000000000000000000000000002", ""},
-		{"436f757274000000000000000000000000000000000000000000000000000001", ""},
-		{"0000000000000000000000000000000000000000000000000000000000000111", ""},
-		{"53656e6174650000000000000000000000000000000000000000000000000002", ""},
-	}
-
-	for _, e := range data {
-		trie.Delete(string(ethutil.Hex2Bytes(e.k)))
-	}
-
-	fmt.Printf("root after delete %x\n", trie.Root)
-
-	trie.NewIterator().Each(func(k string, v *ethutil.Value) {
-		fmt.Printf("%x %x\n", k, v.Bytes())
-	})
-
-	fmt.Printf("%x\n", trie.Get(string(ethutil.Hex2Bytes("0000000000000000000000000000000000000000000000000000000000000001"))))
-}
-*/