V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
vakaka
V2EX  ›  Go 编程语言

上班无聊用 Go 简易的实现了 trie tree, 然后又基于它实现了一下 HTTP 路由

  •  1
     
  •   vakaka · 2016-09-12 16:38:06 +08:00 · 1620 次点击
    这是一个创建于 3027 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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 框架(懒得搞了)。有兴趣的同学可以试试。

    3 条回复    2016-11-16 09:52:28 +08:00
    JamesRuan
        1
    JamesRuan  
       2016-09-12 20:47:47 +08:00
    上班时写得东西适合开源吗?

    我这个库虽然是为公司使用写的,但是却是 100%的下班时间+个人设备的产物。

    https://github.com/jamesruan/sodium
    vakaka
        2
    vakaka  
    OP
       2016-09-12 23:17:48 +08:00
    @JamesRuan 不是为公司写的,主要是没事干。
    zijing07
        3
    zijing07  
       2016-11-16 09:52:28 +08:00
    公司不管你做别的事情么
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3280 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 12:16 · PVG 20:16 · LAX 04:16 · JFK 07:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.