aboutsummaryrefslogtreecommitdiffstats
path: root/ethutil
diff options
context:
space:
mode:
Diffstat (limited to 'ethutil')
-rw-r--r--ethutil/encoding.go76
-rw-r--r--ethutil/encoding_test.go67
-rw-r--r--ethutil/slice.go26
-rw-r--r--ethutil/trie.go561
-rw-r--r--ethutil/trie_test.go193
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)
-}
generated by cgit (git 2.34.1) at 2024-11-12 14:41:32 +0800