diff options
author | zelig <viktor.tron@gmail.com> | 2014-06-29 23:26:58 +0800 |
---|---|---|
committer | zelig <viktor.tron@gmail.com> | 2014-06-29 23:26:58 +0800 |
commit | 707d413761927f5ad95298e666e297b820ad0901 (patch) | |
tree | 347ffb4f9e1c6694cf1d2b1d5892e297c98d2e94 /ethutil | |
parent | 4be3521727698141512eb6454121302bd3b9cc6d (diff) | |
download | dexon-707d413761927f5ad95298e666e297b820ad0901.tar dexon-707d413761927f5ad95298e666e297b820ad0901.tar.gz dexon-707d413761927f5ad95298e666e297b820ad0901.tar.bz2 dexon-707d413761927f5ad95298e666e297b820ad0901.tar.lz dexon-707d413761927f5ad95298e666e297b820ad0901.tar.xz dexon-707d413761927f5ad95298e666e297b820ad0901.tar.zst dexon-707d413761927f5ad95298e666e297b820ad0901.zip |
refactor ethutil/trie to ethtrie
Diffstat (limited to 'ethutil')
-rw-r--r-- | ethutil/encoding.go | 76 | ||||
-rw-r--r-- | ethutil/encoding_test.go | 67 | ||||
-rw-r--r-- | ethutil/slice.go | 26 | ||||
-rw-r--r-- | ethutil/trie.go | 561 | ||||
-rw-r--r-- | ethutil/trie_test.go | 193 |
5 files changed, 0 insertions, 923 deletions
diff --git a/ethutil/encoding.go b/ethutil/encoding.go deleted file mode 100644 index 9fcdf3edf..000000000 --- a/ethutil/encoding.go +++ /dev/null @@ -1,76 +0,0 @@ -package ethutil - -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/ethutil/encoding_test.go b/ethutil/encoding_test.go deleted file mode 100644 index 10e1995c0..000000000 --- a/ethutil/encoding_test.go +++ /dev/null @@ -1,67 +0,0 @@ -package ethutil - -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/ethutil/slice.go b/ethutil/slice.go deleted file mode 100644 index 3cedcb189..000000000 --- a/ethutil/slice.go +++ /dev/null @@ -1,26 +0,0 @@ -package ethutil - -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/ethutil/trie.go b/ethutil/trie.go deleted file mode 100644 index 18d0a5f0a..000000000 --- a/ethutil/trie.go +++ /dev/null @@ -1,561 +0,0 @@ -package ethutil - -import ( - "fmt" - "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 *Value - Dirty bool -} - -func NewNode(key []byte, val *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 Database - IsDirty bool -} - -func NewCache(db Database) *Cache { - return &Cache{db: db, nodes: make(map[string]*Node)} -} - -func (cache *Cache) Put(v interface{}) interface{} { - value := NewValue(v) - - enc := value.Encode() - if len(enc) >= 32 { - sha := Sha3Bin(enc) - - cache.nodes[string(sha)] = NewNode(sha, value, true) - cache.IsDirty = true - - return sha - } - - return v -} - -func (cache *Cache) Get(key []byte) *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 := 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 = CopyBytes(b) - } else { - prevRootCopy = root - } - - return prevRootCopy -} - -func NewTrie(db 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 := 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 := 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{}) *Value { - n := NewValue(node) - - if !n.Get(0).IsNil() { - return n - } - - str := n.Str() - if len(str) == 0 { - return n - } else if len(str) < 32 { - return 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 := 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 := 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 NewValue(t.Root).Cmp(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 *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(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 *Value) - -func (it *TrieIterator) Each(cb EachCallback) { - it.fetchNode(nil, 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 *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/ethutil/trie_test.go b/ethutil/trie_test.go deleted file mode 100644 index 2937b1525..000000000 --- a/ethutil/trie_test.go +++ /dev/null @@ -1,193 +0,0 @@ -package ethutil - -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) -} |