refactor ethutil/trie to ethtrie

5 files changed, 925 insertions, 0 deletions

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)
+}