You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
787 lines
17 KiB
787 lines
17 KiB
package capstan
|
|
|
|
import (
|
|
"bytes"
|
|
"fmt"
|
|
"math/rand"
|
|
"net/http"
|
|
"os"
|
|
"testing"
|
|
"time"
|
|
)
|
|
|
|
const (
|
|
MinLength = 5
|
|
GenerateRandomPrefixes = true
|
|
)
|
|
|
|
var rs = rand.NewSource(time.Now().Unix())
|
|
var rd = rand.New(rs)
|
|
|
|
type words []string
|
|
|
|
func (w words) RandomWord() string {
|
|
return w[rd.Intn(len(w)-1)]
|
|
}
|
|
|
|
var wordList words
|
|
var prefixList words
|
|
|
|
type offsetter interface {
|
|
Offset() int
|
|
}
|
|
|
|
type testHandler struct {
|
|
offset int
|
|
}
|
|
|
|
func (t *testHandler) Offset() int {
|
|
return t.offset
|
|
}
|
|
|
|
func (t *testHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
|
|
|
|
}
|
|
|
|
func initProxyTrie() error {
|
|
var err error
|
|
|
|
wordList, err = buildWordList(1000)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
|
|
prefixList, err = buildWordList(1000)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
prefixes, err := buildWordList(10)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
|
|
for i, word := range prefixList {
|
|
word = prefixes[rd.Intn(len(prefixes)-1)] + word
|
|
prefixList[i] = word
|
|
}
|
|
|
|
return nil
|
|
}
|
|
|
|
func Test_BTree(t *testing.T) {
|
|
root := &binaryTree{}
|
|
a_node := NewTrieNode('a', "", DefaultMappableNodeFunc)
|
|
b_node := NewTrieNode('b', "", DefaultMappableNodeFunc)
|
|
c_node := NewTrieNode('c', "", DefaultMappableNodeFunc)
|
|
d_node := NewTrieNode('d', "", DefaultMappableNodeFunc)
|
|
e_node := NewTrieNode('e', "", DefaultMappableNodeFunc)
|
|
|
|
root.Insert(a_node)
|
|
root.Insert(b_node)
|
|
root.Insert(c_node)
|
|
root.Insert(d_node)
|
|
root.Insert(e_node)
|
|
|
|
node, err := root.Lookup('a')
|
|
if err != nil {
|
|
t.Error("error looking up 'a':", err)
|
|
}
|
|
if node.label != 'a' {
|
|
t.Errorf("expected 'a' but got %c", node.label)
|
|
}
|
|
|
|
node, err = root.Lookup('b')
|
|
if err != nil {
|
|
t.Error("error looking up 'ab:", err)
|
|
}
|
|
if node.label != 'b' {
|
|
t.Errorf("expected 'b' but got %c", node.label)
|
|
}
|
|
|
|
node, err = root.Lookup('c')
|
|
if err != nil {
|
|
t.Error("error looking up 'c':", err)
|
|
}
|
|
if node.label != 'c' {
|
|
t.Errorf("expected 'c' but got %c", node.label)
|
|
}
|
|
|
|
node, err = root.Lookup('d')
|
|
if err != nil {
|
|
t.Error("error looking up 'd':", err)
|
|
}
|
|
if node.label != 'd' {
|
|
t.Errorf("expected 'd' but got %c", node.label)
|
|
}
|
|
|
|
node, err = root.Lookup('e')
|
|
if err != nil {
|
|
t.Error("error looking up 'e':", err)
|
|
}
|
|
if node.label != 'e' {
|
|
t.Errorf("expected 'e' but got %c", node.label)
|
|
}
|
|
}
|
|
|
|
func Test_BTreeOverwrite(t *testing.T) {
|
|
root := &binaryTree{}
|
|
a_node := NewTrieNode('a', "", DefaultMappableNodeFunc)
|
|
b_node := NewTrieNode('b', "", DefaultMappableNodeFunc)
|
|
c_node := NewTrieNode('c', "", DefaultMappableNodeFunc)
|
|
d_node := NewTrieNode('d', "", DefaultMappableNodeFunc)
|
|
e_node := NewTrieNode('e', "", DefaultMappableNodeFunc)
|
|
|
|
a_node.handler = &testHandler{1}
|
|
|
|
root.Insert(a_node)
|
|
root.Insert(b_node)
|
|
root.Insert(c_node)
|
|
root.Insert(d_node)
|
|
root.Insert(e_node)
|
|
|
|
a_overwrite := NewTrieNode('a', "", DefaultMappableNodeFunc)
|
|
a_overwrite.handler = &testHandler{2}
|
|
|
|
root.Insert(a_overwrite)
|
|
|
|
node, err := root.Lookup('a')
|
|
if err != nil {
|
|
t.Error("error looking up 'a':", err)
|
|
}
|
|
if node.label != 'a' {
|
|
t.Errorf("expected 'a' but got %c", node.label)
|
|
}
|
|
if node.handler != nil {
|
|
if h, ok := node.handler.(offsetter); ok {
|
|
if h.Offset() != 2 {
|
|
t.Errorf("expected offset of 2; received %d", h.Offset())
|
|
}
|
|
} else {
|
|
t.Error("node.handler not of type offsetter")
|
|
}
|
|
} else {
|
|
t.Error("node handler should not be nil")
|
|
}
|
|
}
|
|
|
|
func Test_LongestPrefix(t *testing.T) {
|
|
s := longestPrefix("test", "testing")
|
|
if s != "test" {
|
|
t.Error("expected longest prefix 'test' but got:", s)
|
|
}
|
|
|
|
s = longestPrefix("", "test")
|
|
if s != "" {
|
|
t.Error("expected empty string; got:", s)
|
|
}
|
|
}
|
|
|
|
func Test_TrieInsert(t *testing.T) {
|
|
node := NewProxyTrie()
|
|
node.Insert("testing", &testHandler{1})
|
|
node.Insert("test", &testHandler{2})
|
|
node.Insert("testings", &testHandler{3})
|
|
node.Insert("testify", &testHandler{4})
|
|
node.Insert("tester", &testHandler{5})
|
|
node.Insert("testee", &testHandler{6})
|
|
node.Insert("testament", &testHandler{7})
|
|
node.Insert("testable", &testHandler{8})
|
|
node.Insert("not a test at all", &testHandler{9})
|
|
|
|
if n := node.Lookup("testing"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 1 {
|
|
t.Errorf("'testing' expected 1 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("test"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 2 {
|
|
t.Errorf("'test' expected 2 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("testings"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 3 {
|
|
t.Errorf("'testings' expected 3 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("testify"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 4 {
|
|
t.Errorf("'testify' expected 4 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("tester"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 5 {
|
|
t.Errorf("'tester' expected 5 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("testee"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 6 {
|
|
t.Errorf("'testee' expected 6 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("testament"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 7 {
|
|
t.Errorf("'testament' expected 7 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("testable"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 8 {
|
|
t.Errorf("'testable' expected 8 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
|
|
if n := node.Lookup("not a test at all"); n != nil {
|
|
if no, ok := n.(offsetter); ok {
|
|
if no.Offset() != 9 {
|
|
t.Errorf("'not a test at all' expected 9 but received %d", no.Offset())
|
|
}
|
|
} else {
|
|
t.Error("handler not of type `offsetter`")
|
|
}
|
|
} else {
|
|
t.Error("unable to lookup node: nil returned")
|
|
}
|
|
}
|
|
|
|
func buildWordList(count int) ([]string, error) {
|
|
fp, err := os.Open("/usr/share/dict/words")
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
words := make([]string, 0)
|
|
|
|
i := 0
|
|
for {
|
|
buf := make([]byte, 4096)
|
|
n, err := fp.Read(buf)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
if n == 0 {
|
|
break
|
|
}
|
|
|
|
offset := 0
|
|
for {
|
|
offset = bytes.Index(buf, []byte{'\n'})
|
|
if offset < 0 {
|
|
break
|
|
}
|
|
|
|
word := string(buf[:offset])
|
|
if len(word) > MinLength {
|
|
words = append(words, word)
|
|
i++
|
|
}
|
|
|
|
if len(buf) >= offset+1 {
|
|
buf = buf[offset+1:]
|
|
} else {
|
|
break
|
|
}
|
|
|
|
// Double breaking doesn't require label.
|
|
if i >= count {
|
|
break
|
|
}
|
|
}
|
|
|
|
if i >= count {
|
|
break
|
|
}
|
|
}
|
|
|
|
return words, nil
|
|
}
|
|
|
|
func Test_RadixTrieLongestMatch(t *testing.T) {
|
|
node := NewProxyTrie()
|
|
node.Insert("subapp.example.com/testing", &testHandler{0})
|
|
node.Insert("subapp.example.com/testing/again", &testHandler{1})
|
|
|
|
// Validate handlers are present.
|
|
handler := node.Lookup("subapp.example.com/testing")
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != 0 {
|
|
t.Errorf("expected offset 0, got %d", h.Offset())
|
|
}
|
|
}
|
|
|
|
handler = node.Lookup("subapp.example.com/testing/again")
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != 1 {
|
|
t.Errorf("expected offset 1, got %d", h.Offset())
|
|
}
|
|
}
|
|
|
|
handler = node.LongestMatch("subapp.example.com/testing")
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != 0 {
|
|
t.Errorf("expected offset 0, got %d", h.Offset())
|
|
}
|
|
}
|
|
|
|
handler = node.LongestMatch("subapp.example.com/testing/again")
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != 1 {
|
|
t.Errorf("expected offset 1, got %d", h.Offset())
|
|
}
|
|
}
|
|
|
|
handler = node.LongestMatch("subapp.example.com/testing/")
|
|
if handler == nil {
|
|
t.Error("handler should not be nil")
|
|
}
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != 0 {
|
|
t.Errorf("expected offset 1, got %d", h.Offset())
|
|
}
|
|
}
|
|
}
|
|
|
|
// Test_RadixTrieLongestMatch2 is similar to Test_RadixTrieLongestMatch but
|
|
// tests multiple possible prefixes and duplicate characters. This test also
|
|
// uses the radix trie directly and doesn't bind to a server instance.
|
|
func Test_RadixTrieLongestMatch2(t *testing.T) {
|
|
node := NewProxyTrie()
|
|
|
|
patterns := []string{
|
|
"app.example.com/a",
|
|
"app.example.com/aa",
|
|
"app.example.com/aaa",
|
|
"app.example.com/ads",
|
|
"ape.example.com/bananas",
|
|
}
|
|
|
|
for i, v := range patterns {
|
|
node.Insert(v, &testHandler{i})
|
|
}
|
|
|
|
// Test additions work.
|
|
for i, v := range patterns {
|
|
handler := node.LongestMatch(v)
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != i {
|
|
t.Errorf("offset %d expected but received %d for pattern %s",
|
|
i, h.Offset(), v)
|
|
}
|
|
} else {
|
|
t.Errorf("pattern %s not bound to handler type `offsetter`", v)
|
|
}
|
|
}
|
|
|
|
// Path testing.
|
|
handler := node.LongestMatch("app.example.com/aaa/testing/a/aa/aaa")
|
|
if handler == nil {
|
|
t.Error("handler for `app.example.com/aaa/testing/a/aa/aaa` is nil")
|
|
}
|
|
if h, ok := handler.(offsetter); ok {
|
|
if h.Offset() != 2 {
|
|
t.Errorf("offset 2 expected but received 2 for `app.example.com/aaa/testing/a/aa/aaa`")
|
|
}
|
|
}
|
|
|
|
handler = node.LongestMatch("ope.example.com/bananas")
|
|
if handler != nil {
|
|
t.Error("handler should be nil")
|
|
}
|
|
|
|
// Counter-intuitive, but the LongestMatch algorithm is path agnostic. This
|
|
// WILL match the longest possible prefix, which is
|
|
// "ape.example.com/bananas".
|
|
handler = node.LongestMatch("ape.example.com/bananass")
|
|
if handler == nil {
|
|
t.Error("handler should not be nil")
|
|
}
|
|
|
|
handler = node.LongestMatch("ape.example.com/banana/testing")
|
|
if handler != nil {
|
|
t.Error("handler should be nil")
|
|
}
|
|
}
|
|
|
|
func Test_TrieTester(t *testing.T) {
|
|
return // skip
|
|
words := []string{
|
|
//"abc", // abc
|
|
//"ab", // ab -> c
|
|
//"a", // a -> b -> c
|
|
//"aardvark",
|
|
//"aardvark's",
|
|
//"aardvarks",
|
|
//"aa",
|
|
//"a",
|
|
//"aaa",
|
|
//"ah",
|
|
//"aah",
|
|
//"a", // ah => h <- a -> ah ah <- a <- a
|
|
//"aa",
|
|
//"aaah",
|
|
//"aaaah",
|
|
//"aaaaah",
|
|
//"aaaa",
|
|
//"ar",
|
|
//"art",
|
|
//"artys",
|
|
//"arts",
|
|
//"ar",
|
|
//"art",
|
|
//"ars",
|
|
//"aarts",
|
|
//"aartt",
|
|
//"aars",
|
|
//"aart",
|
|
//"a",
|
|
//"aa",
|
|
//"aaa",
|
|
//"example.com",
|
|
//"test.example.com",
|
|
//"example.com/app",
|
|
}
|
|
|
|
node := NewProxyTrie()
|
|
|
|
for i, word := range words {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
for i, word := range words {
|
|
fmt.Printf("offset %d; handler: %v\n", i, node.Lookup(word))
|
|
}
|
|
}
|
|
|
|
func Test_DictionaryInsertAndLookup(t *testing.T) {
|
|
node := NewProxyTrie()
|
|
|
|
for i, word := range wordList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
for i, word := range wordList {
|
|
handler := node.Lookup(word)
|
|
if no, ok := handler.(offsetter); ok {
|
|
if no.Offset() != i {
|
|
t.Errorf("expected %d but got %d", i, no.Offset())
|
|
}
|
|
} else {
|
|
if handler == nil {
|
|
t.Error("received nil for word:", word)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func Test_RadixTrieInsertOverwrite(t *testing.T) {
|
|
// Overwrite not currently supported.
|
|
return
|
|
node := NewProxyTrie()
|
|
handler := &testHandler{1}
|
|
|
|
node.Insert("testing", handler)
|
|
node.Insert("testing", handler)
|
|
|
|
if h := node.Lookup("testing"); h == nil {
|
|
t.Error("handler not added")
|
|
} else {
|
|
if ht, ok := h.(offsetter); !ok {
|
|
t.Error("handler not of type offsetter")
|
|
} else {
|
|
if ht.Offset() != 1 {
|
|
t.Errorf("expected offset 1 but got %d", ht.Offset())
|
|
}
|
|
}
|
|
}
|
|
|
|
node = NewProxyTrie()
|
|
|
|
node.Insert("testing", &testHandler{0})
|
|
node.Insert("testing", &testHandler{1})
|
|
|
|
fmt.Println(node)
|
|
|
|
if h := node.Lookup("testing"); h == nil {
|
|
t.Error("handler not added")
|
|
} else {
|
|
if ht, ok := h.(offsetter); !ok {
|
|
t.Error("handler not of type offsetter")
|
|
} else {
|
|
if ht.Offset() != 1 {
|
|
t.Errorf("expected offset 1 but got %d", ht.Offset())
|
|
}
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
func Benchmark_RadixTrieLookupMap(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
|
|
for i, word := range wordList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := wordList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTrieLookupBinaryTree(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
node.KeyFunc = BinaryTreeMapperFunc
|
|
|
|
for i, word := range wordList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := wordList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTrieLookupArray(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
node.KeyFunc = ArrayMapperFunc
|
|
|
|
for i, word := range wordList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := wordList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_MapLookup(b *testing.B) {
|
|
wordMap := make(map[string]*testHandler)
|
|
|
|
for i, word := range wordList {
|
|
wordMap[word] = &testHandler{i}
|
|
}
|
|
|
|
word := wordList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler, ok := wordMap[word]
|
|
if !ok {
|
|
b.Fatalf("handler for word %s not found", word)
|
|
}
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTrieHugeLookupMap(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
var list words
|
|
|
|
list, _ = buildWordList(100000)
|
|
|
|
for i, word := range list {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := list.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTrieHugeLookupBinaryTree(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
node.KeyFunc = BinaryTreeMapperFunc
|
|
var list words
|
|
|
|
list, _ = buildWordList(100000)
|
|
|
|
for i, word := range list {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := list.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTrieHugeLookupArray(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
node.KeyFunc = ArrayMapperFunc
|
|
var list words
|
|
|
|
list, _ = buildWordList(100000)
|
|
|
|
for i, word := range list {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
for i := 0; i < b.N; i++ {
|
|
word := list.RandomWord()
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_HugeMapLookup(b *testing.B) {
|
|
wordMap := make(map[string]*testHandler)
|
|
var list words
|
|
|
|
list, _ = buildWordList(100000)
|
|
|
|
for i, word := range list {
|
|
wordMap[word] = &testHandler{i}
|
|
}
|
|
|
|
word := list.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler, ok := wordMap[word]
|
|
if !ok {
|
|
b.Fatalf("handler for word %s not found", word)
|
|
}
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
func Benchmark_RadixTriePrefixLookupMap(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
|
|
for i, word := range prefixList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := prefixList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTriePrefixLookupBinaryTree(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
node.KeyFunc = BinaryTreeMapperFunc
|
|
|
|
for i, word := range prefixList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := prefixList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_RadixTriePrefixLookupArray(b *testing.B) {
|
|
node := NewProxyTrie()
|
|
node.KeyFunc = ArrayMapperFunc
|
|
|
|
for i, word := range prefixList {
|
|
node.Insert(word, &testHandler{i})
|
|
}
|
|
|
|
word := prefixList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler := node.Lookup(word)
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Benchmark_PrefixMapLookup(b *testing.B) {
|
|
wordMap := make(map[string]*testHandler)
|
|
|
|
for i, word := range prefixList {
|
|
wordMap[word] = &testHandler{i}
|
|
}
|
|
|
|
word := prefixList.RandomWord()
|
|
for i := 0; i < b.N; i++ {
|
|
handler, ok := wordMap[word]
|
|
if !ok {
|
|
b.Fatalf("handler for word %s not found", word)
|
|
}
|
|
if handler == nil {
|
|
b.Fatalf("handler for word %s should not be nil", word)
|
|
}
|
|
}
|
|
}
|