建站软件,网站建设一定要公司吗,网站制作 语言选择怎么做,北京装修公司排名前十口碑推荐文章目录 首先回顾一下gin框架的路由如何使用的从源码分析一下gin框架gin的路由实现前缀树前缀树的实现压缩前缀树--Radix TrieTrie VS Map 首先回顾一下gin框架的路由如何使用的
package mainimport (fmtgithub.com/gin-gonic/ginnet/httpfmtgithub.com/gin-gonic/ginnet/http
)func main() {//创建一个gin Engine ,Engine实现了net/http包下Handler接口本质上是一个http Handlerr : gin.Default()//注册中间件r.Use(middleware1)r.Use(middleware2)//注册一个path为/hello的处理函数将/hello域名下的get请求路由到后面的handler函数来处理r.GET(/hello, handler)r.Run()}
func middleware1(c *gin.Context) {fmt.Println(Executing middleware1)c.Next() //将控制权传递给下一个中间件或者处理函数//c.Abort() //在请求处理过程中发现错误或异常情况时立即终止处理并返回错误信息后续的处理程序或者中间件不在执行//Executing middleware1//middle1 endfmt.Println(middle1 end)
}func middleware2(c *gin.Context) {fmt.Println(Executing middleware2)c.Next()fmt.Println(middle2 end)
}func handler(c *gin.Context) {fmt.Println(Executing handler)fmt.Println(handler end)c.JSON(http.StatusOK, gin.H{message: hello word})}/*
Executing middleware1
Executing middleware2
Executing handler
handler end
middle2 end
middle1 end*/
运行程序 在浏览器输入“http://127.0.0.1:8080/hello”可以看到 http的请求有9种GET\HEAD\POST\PUT\PATCH\DELETE\CONNECT\OPTIONS\TRACE
从源码分析一下gin框架
首先通过“gin.Default()”创建一个Engine实例并附带有“Logger\Recovery”中间件
// Default returns an Engine instance with the Logger and Recovery middleware already attached.
func Default() *Engine {debugPrintWARNINGDefault()engine : New()engine.Use(Logger(), Recovery())return engine
}Default()实际上是调用了New()并使用use注册“Logger\Recovery”两个中间件
func New() *Engine {debugPrintWARNINGNew()engine : Engine{RouterGroup: RouterGroup{Handlers: nil,basePath: /,root: true,},FuncMap: template.FuncMap{},RedirectTrailingSlash: true,RedirectFixedPath: false,HandleMethodNotAllowed: false,ForwardedByClientIP: true,RemoteIPHeaders: []string{X-Forwarded-For, X-Real-IP},TrustedPlatform: defaultPlatform,UseRawPath: false,RemoveExtraSlash: false,UnescapePathValues: true,MaxMultipartMemory: defaultMultipartMemory,trees: make(methodTrees, 0, 9),delims: render.Delims{Left: {{, Right: }}},secureJSONPrefix: while(1);,trustedProxies: []string{0.0.0.0/0, ::/0},trustedCIDRs: defaultTrustedCIDRs,}engine.RouterGroup.engine engineengine.pool.New func() any {return engine.allocateContext(engine.maxParams)}return engine
}New()函数初始化Engine实例并返回接下来看一下Engine struct都有些什么
type Engine struct {RouterGroup// RedirectTrailingSlash enables automatic redirection if the current route cant be matched but a// handler for the path with (without) the trailing slash exists.// For example if /foo/ is requested but a route only exists for /foo, the// client is redirected to /foo with http status code 301 for GET requests// and 307 for all other request methods.RedirectTrailingSlash bool// RedirectFixedPath if enabled, the router tries to fix the current request path, if no// handle is registered for it.// First superfluous path elements like ../ or // are removed.// Afterwards the router does a case-insensitive lookup of the cleaned path.// If a handle can be found for this route, the router makes a redirection// to the corrected path with status code 301 for GET requests and 307 for// all other request methods.// For example /FOO and /..//Foo could be redirected to /foo.// RedirectTrailingSlash is independent of this option.RedirectFixedPath bool// HandleMethodNotAllowed if enabled, the router checks if another method is allowed for the// current route, if the current request can not be routed.// If this is the case, the request is answered with Method Not Allowed// and HTTP status code 405.// If no other Method is allowed, the request is delegated to the NotFound// handler.HandleMethodNotAllowed bool// ForwardedByClientIP if enabled, client IP will be parsed from the requests headers that// match those stored at (*gin.Engine).RemoteIPHeaders. If no IP was// fetched, it falls back to the IP obtained from// (*gin.Context).Request.RemoteAddr.ForwardedByClientIP bool// AppEngine was deprecated.// Deprecated: USE TrustedPlatform WITH VALUE gin.PlatformGoogleAppEngine INSTEAD// #726 #755 If enabled, it will trust some headers starting with// X-AppEngine... for better integration with that PaaS.AppEngine bool// UseRawPath if enabled, the url.RawPath will be used to find parameters.UseRawPath bool// UnescapePathValues if true, the path value will be unescaped.// If UseRawPath is false (by default), the UnescapePathValues effectively is true,// as url.Path gonna be used, which is already unescaped.UnescapePathValues bool// RemoveExtraSlash a parameter can be parsed from the URL even with extra slashes.// See the PR #1817 and issue #1644RemoveExtraSlash bool// RemoteIPHeaders list of headers used to obtain the client IP when// (*gin.Engine).ForwardedByClientIP is true and// (*gin.Context).Request.RemoteAddr is matched by at least one of the// network origins of list defined by (*gin.Engine).SetTrustedProxies().RemoteIPHeaders []string// TrustedPlatform if set to a constant of value gin.Platform*, trusts the headers set by// that platform, for example to determine the client IPTrustedPlatform string// MaxMultipartMemory value of maxMemory param that is given to http.Requests ParseMultipartForm// method call.MaxMultipartMemory int64// UseH2C enable h2c support.UseH2C bool// ContextWithFallback enable fallback Context.Deadline(), Context.Done(), Context.Err() and Context.Value() when Context.Request.Context() is not nil.ContextWithFallback booldelims render.DelimssecureJSONPrefix stringHTMLRender render.HTMLRenderFuncMap template.FuncMapallNoRoute HandlersChainallNoMethod HandlersChainnoRoute HandlersChainnoMethod HandlersChainpool sync.Pooltrees methodTreesmaxParams uint16maxSections uint16trustedProxies []stringtrustedCIDRs []*net.IPNet
}从结构体中发现Engine有一个“sync.Pool”类型的pool变量 sync.Pool是sync包下的一个内存池组件用来实现对象的复用避免重复创建相同的对象造成频繁的内存分配和gc以达到提升程序性能的目的虽然池子中的对象可以被复用 但是sync.Pool并不会永久保存这个对象池子中的对象会在一定时间后被gc回收这个时间是随机的。所以用sync.Pool持久化存储对象不可取 sync.Pool本身是线程安全的支持多个goroutine并发的往sync.Pool存取数据
sync.Pool的使用例子
package main
import (fmtsync
)type Student struct {Name stringAge int
}func main() {pool : sync.Pool{New: func() interface{} {return Student{Name: zhangsan,Age: 23,}},}st : pool.Get().(*Student)fmt.Println(st.Age, st.Name)fmt.Printf(%p\n, st)pool.Put(st)st pool.Get().(*Student)fmt.Println(st.Age, st.Name)fmt.Printf(%p\n, st)}
//23 zhangsan
//0xc00000a028
//23 zhangsan
//0xc00000a028Engine结构RouterGroup结构体接下来看一下“RouterGroup”结构体
type RouterGroup struct {//HandlersChain defines a HandlerFunc slice//HandlerFunc defines the handler used by gin middleware as return valueHandlers HandlersChainbasePath stringengine *Engineroot bool
}Engine中还有一个“methodTrees”类型的变量trees
trees methodTrees
type methodTrees []methodTree
type methodTree struct{method stringroot *node
}
type node struct {path stringindices stringwildChild boolnType nodeTypepriority uint32children []*node // child nodes, at most 1 :param style node at the end of the arrayhandlers HandlersChainfullPath string
}node 中最重要的两个结构就是
type node struct{wildChild boolchildren []*node
}
//其实这个就是前缀树实现的比较重要的两个数据变量gin的路由实现
gin的每种请求都是一个域名对应着一个路由处理函数就是一种映射关系直观上可以使用map存储这种映射关系key存储域名value存储域名对应的处理函数 但实际上gin路由底层实现这个映射使用的是压缩前缀树首先介绍一下前缀树
前缀树
前缀树就是trie树是一种树形结构用于高效地存储和检索字符串集合。基本思想就是将字符串中的每个字符作为树的一个节点从根节点开始每个节点代表代表字符串中的一个前缀。在Trie树每个节点都包含一个指向子节点的指针数组数组的大小等于字符集的大小。如果某个节点代表的字符串是一个单词的结尾可以在该节点上做一个标记。 以下是前缀树的一些特性
前缀匹配。前缀树可以高效地实现前缀匹配。给定一个前缀可以在O(k)的时间复杂度内找到所有以该前缀开头的字符串k是前缀的长度高效存储和检索。前缀树可以高效地存储和检索字符串集合。在插入和查找字符串时时间复杂度为O(k)k是字符串的长度。相比于哈希表和二叉搜索树前缀树在字符串存储和检索方面具有更好的性能消耗较大的空间。空间复杂度较高每个节点都需要存储指向子节点的指针数组节点的数量可能会非常多。空间复杂度为O(n*m)其中n为字符串集合中字符串的平均长度m为字符串数量支持删除操作。删除操作相对比较复杂删除一个字符串需要同时删除相应的节点需要处理节点合并的情况。应用场景。单词查询自动补全模糊匹配
前缀树的实现
前缀树的实现可以参考力扣上的一道代码题 题目链接 大致的思路就是 go 语言实现
type Trie struct {trie [26]*Trieflag bool
}func Constructor() Trie {return Trie{}
}func (this *Trie) Insert(word string) {tr: thisfor i:0;ilen(word);i{if tr.trie[word[i]-a]nil{tr.trie[word[i]-a] Trie{}}trtr.trie[word[i]-a]}tr.flagtrue
}func (this *Trie) Search(word string) bool {tr:this.startpre(word)return tr!nil tr.flag
}func (this *Trie) StartsWith(prefix string) bool {return this.startpre(prefix)!nil
}
func (this *Trie)startpre(pre string)*Trie{tr:this for i:0;ilen(pre);i{if tr.trie[pre[i]-a]nil{return nil}trtr.trie[pre[i]-a]}return tr
}/*** Your Trie object will be instantiated and called as such:* obj : Constructor();* obj.Insert(word);* param_2 : obj.Search(word);* param_3 : obj.StartsWith(prefix);*/C实现版本由于C没有回收内存的机制所以需要手动释放内存
class Trie {
public:~Trie(){//析构函数释放内存del(this);}Trie():trie(26),flag(false){}void insert(string word) {Trie *tr this;for(const charc:word){if(!tr-trie[c-a]) tr-trie[c-a] new Trie();trtr-trie[c-a];}tr-flagtrue;}bool search(string word) {Trie *tr this;for(const charc:word){if(!tr-trie[c-a]) return false;trtr-trie[c-a];}return tr-flag;}bool startsWith(string prefix) {Trie *tr this;for(const charc:prefix){if(!tr-trie[c-a]) return false;trtr-trie[c-a];}return true;}
private:vectorTrie* trie;bool flag;
private:void del(Trie *tr){for(int i0;i26;i){delete(tr-trie[i]);tr-trie[i]nullptr;}}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj new Trie();* obj-insert(word);* bool param_2 obj-search(word);* bool param_3 obj-startsWith(prefix);*/解释一下其中的关键代码del void del(Trie *tr){//由于每个Trie节点都有一个长度为26的指向子节点的指针数组所以写了一个长度为26的for循环for(int i0;i26;i){//由于tr-trie[i]是一个Trie的数据类型变量所以在delete tr-trie[i]的时候会触发tr-trie[i]的析构函数往下递归的进行内存释放delete(tr-trie[i]);//释放完之后为了防止野指针将tr-trie[i]设置为nullptrtr-trie[i]nullptr;}}压缩前缀树–Radix Trie
从上述的分析和代码实现可以看出前缀树占用的空间特别大。那么为了优化空间的利用率gin的路由采用了“压缩前缀树”。
使用如下方法进行压缩
合并相邻的只有一个子节点的节点遍历前缀树当发现一个节点只有一个子节点时将该节点与其子节点合并。合并时将子节点的字符添加到父节点的字符中形成新的字符递归地压缩子树在合并节点后可能会出现新的节点也只有一个子节点的情况可以递归的对子树进行压缩直到无法压缩为止使用特殊字符表示合并为了在压缩前缀树中表示节点的合并可以使用一些特殊的字符进行标记。例如可以使用$表示节点的合并
接下来利用数据结构可视化工具查看两个结构的不同 依次插入[“apple”,“apricot”,“banana”,“bat”]
前缀树的结构如下 压缩前缀树的结构如下 从两图可以看出,Radix Trie对Trie进行了压缩遍历Trie发现某个节点只有一个子节点就与子节点进行合并减少指针数组的占用优化空间
Trie VS Map
接下来说一下为什么不用map实现路径和路由函数之间的映射。
map并不支持模糊匹配和参数提取前缀树可以根据前缀进行参数提取而使用map进行参数提取需要额外的步骤前缀树可以根据前缀进行分组管理而map不行
