上班无聊用 Go 简易的实现了 trie tree, 然后又基于它实现了一下 HTTP 路由
vakaka · 2016-09-12 16:38:06 +08:00 · 1590 次点击这是一个创建于 2994 天前的主题，其中的信息可能已经有所发展或是发生改变。
Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
type Trie
func New() *Trie
func (trie *Trie) GetNode(v string) (ok bool, node *Node)
func (trie *Trie) Has(pattern string) bool
func (trie *Trie) Match(v string) (bool, *Result)
func (trie *Trie) Put(pattern string, value interface{}) error
func (trie *Trie) SetDelimeter(delimeter string)
基于该 Trie 数实现的 HTTP router
type Context
func NewContent(rw http.ResponseWriter, r *http.Request) *Context
func (context *Context) ParamInt(key string, d ...int) (int, error)
func (context *Context) ParamString(key string, d ...string) string
func (context *Context) WriteString(v string)
type Handler
func NewHanlder() *Handler
func (handler *Handler) Delete(handleFunc func(*Context))
func (handler *Handler) DoDelete(context *Context)
func (handler *Handler) DoGet(context *Context)
func (handler *Handler) DoPatch(context *Context)
func (handler *Handler) DoPost(context *Context)
func (handler *Handler) DoPut(context *Context)
func (handler *Handler) Get(handleFunc func(*Context))
func (handler *Handler) Patch(handleFunc func(*Context))
func (handler *Handler) Post(handleFunc func(*Context))
func (handler *Handler) Put(handleFunc func(*Context))
type HandlerInterface
type Router
func New() *Router
func (router *Router) After(pattern string, midwares ...func(context *Context))
func (router *Router) Before(pattern string, midwares ...func(*Context))
func (router *Router) Delete(pattern string, handlefunc func(*Context))
func (router *Router) Get(pattern string, handlefunc func(*Context))
func (router *Router) Patch(pattern string, handlefunc func(*Context))
func (router *Router) Post(pattern string, handlefunc func(*Context))
func (router *Router) Put(pattern string, handlefunc func(*Context))
func (router *Router) Router(pattern string, handler HandlerInterface)
func (router *Router) ServeHTTP(rw http.ResponseWriter, r *http.Request)
示例
package main
import (
"fmt"
"net/http"
"os"
"github.com/importcjj/trie.go/router"
)
func Helloworld(ctx *router.Context) {
ctx.WriteString("hello, world!")
}
func ParamHandler(ctx *router.Context) {
username := ctx.ParamString("username")
text := fmt.Sprintf("hi, %s", username)
ctx.WriteString(text)
}
var PageResource = &router.Handler{
OnGet: func(ctx *router.Context) {
filepath := ctx.ParamString("filepath")
text := fmt.Sprintf("Get page %s", filepath)
ctx.WriteString(text)
},
OnPost: func(ctx *router.Context) {
filepath := ctx.ParamString("filepath")
text := fmt.Sprintf("Post page %s", filepath)
ctx.WriteString(text)
},
}
// BasicAuth is a Midwares
func BasicAuth(ctx *router.Context) {
fmt.Fprintln(os.Stderr, ctx.Request.URL, "Call Basic Auth.")
}
// BeforeMetric mark a time point when the request start.
func BeforeMetric(ctx *router.Context) {
// just a example, so use the params map to
// record the time.
ctx.Params["time"] = time.Now().Format("Mon Jan 2 15:04:05 -0700 MST 2006")
}
// AfterMetric log the time spent to handle the requeset.
func AfterMetric(ctx *router.Context) {
start, _ := time.Parse("Mon Jan 2 15:04:05 -0700 MST 2006", ctx.Params["time"])
dur := time.Since(start)
fmt.Fprintf(os.Stderr, "%s spent", dur.String())
}
var r = router.New()
func init() {
r.Get("/hello/world", Helloworld)
r.Get("/hi/<username:str>", ParamHandler)
// restful api style, this pattern can match such as
// "/page/hi.html" "/page/static/inde.html" eta.
r.Router("/page/<filepath:*>", PageResource)
r.Before("/", BasicAuth, BeforeMetric)
r.After("/", AfterMetric)
}
func main() {
server := &http.Server{
Addr: ":8080",
Handler: r,
}
server.ListenAndServe()
}
项目地址: https://github.com/importcjj/trie.go
没有花很多时间，没有进行彻底测试。不过简单测试了一下，没有发现什么问题，性能也还过的去。如果可以的话，希望大家去试试，提一点意见。如果觉得写得可以的话，欢迎 star 和 fork 哦！然后，基于该 HTTP router 可以实现一个简单的 web 框架（懒得搞了）。有兴趣的同学可以试试。
Select Language