type node struct

在router.go中可以看到对node的使用

  1. type Router struct {
  2.     trees map[string]*node
  3. }

map中的key是不同的method，*node就是不同method的树的根节点

直接看结构体定义

  1. type node struct {
  2.     path      string        // 路径，比如`s`、`earch`、`up`
  3.     wildChild bool            // 标明当前节点的子是否为参数节点
  4.     nType     nodeType        // 
  5.     maxParams uint8            // 自己以及所有子孙节点，path中的最大参数数量
  6.     priority  uint32        // 优先级，是当前节点的子孙节点数量+1，在介绍中有提到过
  7.     indices   string        // 存放所有子节点的首字母，比如`eu`
  8.     children  []*node        // 
  9.     handle    Handle        // 处理程序
  10. }

nodetype包含四种类型

  1. type nodeType uint8
  3. const (
  4.     static nodeType = iota // default，譬如search与sup中的s节点
  5.     root            // 每个方法的根节点
  6.     param            // 其他的节点
  7.     catchAll        // 存在*name的节点
  8. )

建树过程

建树主要涉及node.addRoute()以及node.insertChild()两个函数

node.addRoute()

回顾一下，注册路由的函数是Router.Handle()，该函数调用node.addRoute()，其接收者是某个method的root节点。

  1. // addRoute 向tree中增加节点
  2. // Not concurrency-safe!
  3. func (n *node) addRoute(path string, handle Handle) {
  4.     fullPath := path
  5.     n.priority++        // 根节点的权重+1
  6.     numParams := countParams(path)        // 计算路径中的参数个数
  8.     // non-empty tree
  9.     if len(n.path) > 0 || len(n.children) > 0 {
  10.     walk:        // 循环的标记
  11.         for {
  12.             // Update maxParams of the current node
  13.             if numParams > n.maxParams {
  14.                 n.maxParams = numParams
  15.             }
  17.             // 查找最长公共前缀
  18.             // This also implies that the common prefix contains no ':' or '*'
  19.             // since the existing key can't contain those chars.
  20.             i := 0
  21.             max := min(len(path), len(n.path))        // 最长不会超过最短path的长度
  22.             for i < max && path[i] == n.path[i] {
  23.                 i++
  24.             }
  26.             // Split edge
  27.             // 如果公共部分比当前节点的path要短，如sup与search
  28.             // 需要将原来的node切分成公共前缀node和后续的node两个部分
  29.             if i < len(n.path) {
  30.                 child := node{
  31.                     path:      n.path[i:],
  32.                     wildChild: n.wildChild,
  33.                     nType:     static,
  34.                     indices:   n.indices,
  35.                     children:  n.children,
  36.                     handle:    n.handle,
  37.                     priority:  n.priority - 1,    // 存疑，不知道为什么要-1
  38.                 }
  40.                 // Update maxParams (max of all children)
  41.                 for i := range child.children {
  42.                     if child.children[i].maxParams > child.maxParams {
  43.                         child.maxParams = child.children[i].maxParams
  44.                     }
  45.                 }
  47.                 n.children = []*node{&child}
  48.                 // []byte for proper unicode char conversion, see #65
  49.                 n.indices = string([]byte{n.path[i]})    
  50.                 n.path = path[:i]
  51.                 n.handle = nil        // 由于已经将handle给了子节点，当前路径中不含通配符
  53.                 // 很明显的，如果有正常的子节点，就不可能再有`:`或者`*`，
  54.                 n.wildChild = false        
  55.             }
  57.             // Make new node a child of this node
  58.             // 如果公共部分比新的path要短
  59.             // 由于是先处理的n节点，所以当前节点中存放的就是公共前缀
  60.             // 所以只需要将path的非公共部分存放到一个新的节点中
  61.             if i < len(path) {
  62.                 path = path[i:]
  64.                 // 这个条件判断，当前路径是否有名字参数
  65.                 // 也可以直接理解为，没有经过上一个if的处理
  66.                 // 因为上一个if将n.wildChild设为了false
  67.                 // 所以也意味着，公共前缀的长度>=len(n.path)
  68.                 if n.wildChild {
  69.                     n = n.children[0]
  70.                     n.priority++
  72.                     // Update maxParams of the child node
  73.                     if numParams > n.maxParams {
  74.                         n.maxParams = numParams
  75.                     }
  76.                     numParams--
  78.                     // Check if the wildcard matches
  79.                     if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
  80.                         // Adding a child to a catchAll is not possible
  81.                         n.nType != catchAll &&
  82.                         // Check for longer wildcard, e.g. :name and :names
  83.                         (len(n.path) >= len(path) || path[len(n.path)] == '/') {
  84.                         continue walk
  85.                     } else {
  86.                         // Wildcard conflict
  87.                         var pathSeg string
  88.                         if n.nType == catchAll {
  89.                             pathSeg = path
  90.                         } else {
  91.                             pathSeg = strings.SplitN(path, "/", 2)[0]
  92.                         }
  93.                         prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
  94.                         panic("'" + pathSeg +
  95.                             "' in new path '" + fullPath +
  96.                             "' conflicts with existing wildcard '" + n.path +
  97.                             "' in existing prefix '" + prefix +
  98.                             "'")
  99.                     }
  100.                 }
  102.                 c := path[0]
  104.                 // slash after param
  105.                 if n.nType == param && c == '/' && len(n.children) == 1 {
  106.                     n = n.children[0]
  107.                     n.priority++
  108.                     continue walk
  109.                 }
  111.                 // Check if a child with the next path byte exists
  112.                 for i := 0; i < len(n.indices); i++ {
  113.                     if c == n.indices[i] {
  114.                         i = n.incrementChildPrio(i)
  115.                         n = n.children[i]
  116.                         continue walk
  117.                     }
  118.                 }
  120.                 // Otherwise insert it
  121.                 if c != ':' && c != '*' {
  122.                     // []byte for proper unicode char conversion, see #65
  123.                     n.indices += string([]byte{c})
  124.                     child := &node{
  125.                         maxParams: numParams,
  126.                     }
  127.                     n.children = append(n.children, child)
  128.                     n.incrementChildPrio(len(n.indices) - 1)
  129.                     n = child
  130.                 }
  131.                 n.insertChild(numParams, path, fullPath, handle)
  132.                 return
  134.             } else if i == len(path) { // Make node a (in-path) leaf
  135.                 // 新注册的路由路径与当前节点路径相同
  137.                 // 想要注册的路由是否已有handler
  138.                 if n.handle != nil {
  139.                     panic("a handle is already registered for path '" + fullPath + "'")
  140.                 }
  141.                 n.handle = handle
  142.             }
  143.             return
  144.         }
  145.     } else { // Empty tree
  146.         n.insertChild(numParams, path, fullPath, handle)    //空树则给该树插入子节点
  147.         n.nType = root                        // 标明当前节点类型
  148.     }
  149. }

node.insertChild()

  1. func (n *node) insertChild(numParams uint8, path, fullPath string, handle Handle) {
  2.     var offset int // 用于记录目前已经处理了path中的长度
  4.     // find prefix until first wildcard (beginning with ':'' or '*'')
  5.     // 如果存在`:`或者`*`，需要对节点进行特殊处理
  6.     for i, max := 0, len(path); numParams > 0; i++ {
  7.         c := path[i]
  8.         if c != ':' && c != '*' {
  9.             continue
  10.         }
  12.         // find wildcard end (either '/' or path end)
  13.         // 找到`:`或`*`以后，找到其结尾
  14.         end := i + 1
  15.         for end < max && path[end] != '/' {
  16.             switch path[end] {
  17.             // the wildcard name must not contain ':' and '*'
  18.             case ':', '*':
  19.                 panic("only one wildcard per path segment is allowed, has: '" +
  20.                     path[i:] + "' in path '" + fullPath + "'")
  21.             default:
  22.                 end++
  23.             }
  24.         }
  26.         // 如果存在子节点，则在此插入通配符将导致子节点无法访问
  27.         // 比如存在`/path1/path2`，则无法插入`/path1/:post`
  28.         if len(n.children) > 0 {
  29.             panic("wildcard route '" + path[i:end] +
  30.                 "' conflicts with existing children in path '" + fullPath + "'")
  31.         }
  33.         // check if the wildcard has a name
  34.         // `:`和`*`是需要有名字的
  35.         if end-i < 2 {
  36.             panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
  37.         }
  39.         if c == ':' { // param
  40.             // 将`:`之前的分割出来
  41.             if i > 0 {
  42.                 n.path = path[offset:i]
  43.                 offset = i
  44.             }
  46.             child := &node{
  47.                 nType:     param,
  48.                 maxParams: numParams,
  49.             }
  50.             n.children = []*node{child}
  51.             n.wildChild = true
  52.             n = child        // 移动到child节点，准备处理剩下的path
  53.             n.priority++
  54.             numParams--        // 处理掉一个通配符，剩下的路径中的参数个数--
  56.             // if the path doesn't end with the wildcard, then there
  57.             // will be another non-wildcard subpath starting with '/'
  58.             // 如果通配符项不是剩余path的全部路径，则需要将通配符这一节
  59.             // 单独做成一个节点
  60.             if end < max {
  61.                 n.path = path[offset:end]
  62.                 offset = end
  64.                 child := &node{
  65.                     maxParams: numParams,
  66.                     priority:  1,
  67.                 }
  68.                 n.children = []*node{child}
  69.                 n = child
  70.             }
  72.         } else { // catchAll
  73.             if end != max || numParams > 1 {
  74.                 panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
  75.             }
  77.             if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
  78.                 panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
  79.             }
  81.             // currently fixed width 1 for '/'
  82.             i--
  83.             if path[i] != '/' {
  84.                 panic("no / before catch-all in path '" + fullPath + "'")
  85.             }
  87.             n.path = path[offset:i]
  89.             // first node: catchAll node with empty path
  90.             child := &node{
  91.                 wildChild: true,
  92.                 nType:     catchAll,
  93.                 maxParams: 1,
  94.             }
  95.             // update maxParams of the parent node
  96.             if n.maxParams < 1 {
  97.                 n.maxParams = 1
  98.             }
  99.             n.children = []*node{child}
  100.             n.indices = string(path[i])
  101.             n = child
  102.             n.priority++
  104.             // second node: node holding the variable
  105.             child = &node{
  106.                 path:      path[i:],
  107.                 nType:     catchAll,
  108.                 maxParams: 1,
  109.                 handle:    handle,
  110.                 priority:  1,
  111.             }
  112.             n.children = []*node{child}
  114.             return
  115.         }
  116.     }
  118.     // insert remaining path part and handle to the leaf
  119.     n.path = path[offset:]        // 节点中的path只保留非公共部分
  120.     n.handle = handle
  121. }

其他函数

func countParams()

用于计算一个路径中有多少占位参数（:name和*name）

  1. func countParams(path string) uint8 {
  2.     var n uint
  3.     for i := 0; i < len(path); i++ {
  4.         if path[i] != ':' && path[i] != '*' {
  5.             continue
  6.         }
  7.         n++
  8.     }
  9.     if n >= uint(maxParamCount) {
  10.         return maxParamCount
  11.     }
  13.     return uint8(n)
  14. }
  16. // var maxParamCount uint8 = ^uint8(0) 也就是255

相关内容

  • #65，关于string的类型转换问题