• 概述
  • Radix Tree数据结构
    • 定义
    • insertChild
    • addRoute
    • getValue

概述

HTTP router的核心数据结构之一就是Radix Tree了,也就是压缩Trie(字典树),比Trie更加节省空间。通过把单子节点和父节点合并,以此减少了树的节点数,也缩短了树的深度。HTTP router的Rarix Tree和普通的Radix Tree不同点就是需要支持通配符*和:并且支持不区分大小写查询

定义

Radix Tree的定义如下:

1
2
3
4
type methodTree struct {
	method string	//http请求方法
	root   *node
}

树节点的定义如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
type node struct {
	path      string	//当前节点路径
	indices   string	//各子节点路径首字母
	children  []*node	//子节点列表
	handlers  HandlersChain  //当前节点的handler集合
	priority  uint32	//节点的优先级,优先级高的在父节点children数组位置会更靠前
	nType     nodeType	//节点的类型
	maxParams uint8		//经过此节点的后续路径的最大参数数量
	wildChild bool		//儿子节点是否通配符类型
    fullPath  string	//完整路径
}

insertChild

这个函数的功能是设置好节点的path以及handers,但是path可能有带有通配符,需要对通配符进行相应的处理。在path中找到*或者:位置时,需要处理以下情形:

  1. 遇到/之前都不允许再出现通配符
  2. 当前节点在此之前不允许有child
  3. 通配符之后的参数长度大于1
  4. 如果通配符是*,那么*之后是不允许再出现/,也就是说numParams必须等于1,并且当前节点的path值最后一个字符不能为/,*前面一个字符必须为/

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    
    func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {
    	for numParams > 0 {
    		// 找到通配符为起始点的前缀字符串
    		wildcard, i, valid := findWildcard(path)
    		if i < 0 { // 没有查找到通配符
    			break
    		}
    
    		// 通配符字符串必须包含通配符:或者*
    		if !valid {
    			panic("only one wildcard per path segment is allowed, has: '" +
    				wildcard + "' in path '" + fullPath + "'")
    		}
    
    		// 通配符字符串必须有名字,所以只有单个通配字符是不正确的格式
    		if len(wildcard) < 2 {
    			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
    		}
    
    		// 如果当前节点已经存在儿子节点,那么插入通配字符串会和已存在的儿子节点冲突
    		// 导致之前的儿子节点无法查询到
    		if len(n.children) > 0 {
    			panic("wildcard segment '" + wildcard +
    				"' conflicts with existing children in path '" + fullPath + "'")
    		}
          
    		if wildcard[0] == ':' { // param
    			if i > 0 {
    				// Insert prefix before the current wildcard
    				n.path = path[:i]
    				path = path[i:]
    			}
            
    			n.wildChild = true
    			child := &node{
    				nType:     param,
    				path:      wildcard,
    				maxParams: numParams,
    				fullPath:  fullPath,
    			}
    			n.children = []*node{child}
    			n = child
    			n.priority++
    			numParams--
    
    			// 如果没有以通配字符串结束,那么会有以/字符为起点的其他非通配符子串,继续递归进行处理
    			if len(wildcard) < len(path) {
    				path = path[len(wildcard):]
    
    				child := &node{
    					maxParams: numParams,
    					priority:  1,
    					fullPath:  fullPath,
    				}
    				n.children = []*node{child}
    				n = child
    				continue
    			}
    
    			// 在新的叶子节点插入handle,结束处理
    			n.handlers = handlers
    			return
    		}
    
    		// catchAll
    		if i+len(wildcard) != len(path) || numParams > 1 {
    			panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
    		}
    
    		if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
    			panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
    		}
    
    		// currently fixed width 1 for '/'
    		i--
    		if path[i] != '/' {
    			panic("no / before catch-all in path '" + fullPath + "'")
    		}
    
    		n.path = path[:i]
    
    		// First node: catchAll node with empty path
    		child := &node{
    			wildChild: true,
    			nType:     catchAll,
    			maxParams: 1,
    			fullPath:  fullPath,
    		}
    		// update maxParams of the parent node
    		if n.maxParams < 1 {
    			n.maxParams = 1
    		}
    		n.children = []*node{child}
    		n.indices = string('/')
    		n = child
    		n.priority++
    
    		// second node: node holding the variable
    		child = &node{
    			path:      path[i:],
    			nType:     catchAll,
    			maxParams: 1,
    			handlers:  handlers,
    			priority:  1,
    			fullPath:  fullPath,
    		}
    		n.children = []*node{child}
    
    		return
    	}
    
    	// 插入剩余的path部分和handlers到叶子节点
    	n.path = path
    	n.handlers = handlers
    	n.fullPath = fullPath
    }

addRoute

此函数的的功能是添加路由,也就是把给定的URL路径插入到字典树中,并在叶子节点设置好handlers。 1.如果是空树,那么直接执行insertChild即可 2.如果是非空树,则需要在树中查找到适合位置进行插入。首先查找当前节点的path值和URL值的最长公共前缀,如果公共前缀长度小于URL的长度,那么需要对当前节点的进行分裂,并创建新的子节点。把当前节点的path值更新为最长公共前缀,并更新当前节点和新子节点的相关数据。如果公共前缀长度小于URL长度,并且查找不到匹配的子节点,那么需要为当前节点创建一个新的子节点,并对子节点执行insertChild,否则进入匹配的子节点,重复执行步骤2。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// addRoute adds a node with the given handle to the path.
// 非并发安全
func (n *node) addRoute(path string, handlers HandlersChain) {
	fullPath := path
	n.priority++
	numParams := countParams(path)

	// Empty tree
	if len(n.path) == 0 && len(n.children) == 0 {
		n.insertChild(numParams, path, fullPath, handlers)
		n.nType = root
		return
	}

	parentFullPathIndex := 0

walk:
	for {
		// Update maxParams of the current node
		if numParams > n.maxParams {
			n.maxParams = numParams
		}

		// 查找最长公共前缀
		// This also implies that the common prefix contains no ':' or '*'
		// since the existing key can't contain those chars.
		i := longestCommonPrefix(path, n.path)

		// 分裂节点
		if i < len(n.path) {
			child := node{
				path:      n.path[i:],
				wildChild: n.wildChild,
				indices:   n.indices,
				children:  n.children,
				handlers:  n.handlers,
				priority:  n.priority - 1,
				fullPath:  n.fullPath,
			}

			// Update maxParams (max of all children)
			for i := range child.children {
				if child.children[i].maxParams > child.maxParams {
					child.maxParams = child.children[i].maxParams
				}
			}

			n.children = []*node{&child}
			// []byte for proper unicode char conversion, see #65
			n.indices = string([]byte{n.path[i]})
			n.path = path[:i]
			n.handlers = nil
			n.wildChild = false
			n.fullPath = fullPath[:parentFullPathIndex+i]
		}

		// Make new node a child of this node
		if i < len(path) {
			path = path[i:]

			if n.wildChild {
				parentFullPathIndex += len(n.path)
				n = n.children[0]
				n.priority++

				// Update maxParams of the child node
				if numParams > n.maxParams {
					n.maxParams = numParams
				}
				numParams--

				// Check if the wildcard matches
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
					// check for longer wildcard, e.g. :name and :names
					if len(n.path) >= len(path) || path[len(n.path)] == '/' {
						continue walk
					}
				}

				pathSeg := path
				if n.nType != catchAll {
					pathSeg = strings.SplitN(path, "/", 2)[0]
				}
				prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
				panic("'" + pathSeg +
					"' in new path '" + fullPath +
					"' conflicts with existing wildcard '" + n.path +
					"' in existing prefix '" + prefix +
					"'")
			}

			c := path[0]

			// slash after param
			if n.nType == param && c == '/' && len(n.children) == 1 {
				parentFullPathIndex += len(n.path)
				n = n.children[0]
				n.priority++
				continue walk
			}

			// 找到子节点path值首字符与当前URL首字母相等的子节点并进入到此子节点并从循环最开始执行
			for i, max := 0, len(n.indices); i < max; i++ {
				if c == n.indices[i] {
					parentFullPathIndex += len(n.path)
					i = n.incrementChildPrio(i)
					n = n.children[i]
					continue walk
				}
			}

			// Otherwise insert it
			if c != ':' && c != '*' {
				// []byte for proper unicode char conversion, see #65
				n.indices += string([]byte{c})
				child := &node{
					maxParams: numParams,
					fullPath:  fullPath,
				}
				n.children = append(n.children, child)
				n.incrementChildPrio(len(n.indices) - 1)
				n = child
			}
			n.insertChild(numParams, path, fullPath, handlers)
			return
		}

		// Otherwise and handle to current node
		if n.handlers != nil {
			panic("handlers are already registered for path '" + fullPath + "'")
		}
		n.handlers = handlers
		return
	}
}

getValue

此函数的功能是根据给定的URL值查找到相应的树节点,并把此节点的handlers和树路径上经过的参数键值对返回,如果没查找到相应树节点,则根据情况判断URL是否缺少/字符并返回,具体代码实现其实和addRoute类似,都是在对树进行查找,此处不再赘述。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// getValue returns the handle registered with the given path (key). The values of
// wildcards are saved to a map.
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
// made if a handle exists with an extra (without the) trailing slash for the
// given path.
func (n *node) getValue(path string, po Params, unescape bool) (value nodeValue) {
	value.params = po
walk: // Outer loop for walking the tree
	for {
		prefix := n.path
		if len(path) > len(prefix) {
			if path[:len(prefix)] == prefix {
				path = path[len(prefix):]
				// If this node does not have a wildcard (param or catchAll)
				// child,  we can just look up the next child node and continue
				// to walk down the tree
				if !n.wildChild {
					c := path[0]
					indices := n.indices
					for i, max := 0, len(indices); i < max; i++ {
						if c == indices[i] {
							n = n.children[i]
							prefix = n.path
							continue walk
						}
					}

					// Nothing found.
					// We can recommend to redirect to the same URL without a
					// trailing slash if a leaf exists for that path.
					value.tsr = path == "/" && n.handlers != nil
					return
				}

				// handle wildcard child
				n = n.children[0]
				switch n.nType {
				case param:
					// find param end (either '/' or path end)
					end := 0
					for end < len(path) && path[end] != '/' {
						end++
					}

					// save param value
					if cap(value.params) < int(n.maxParams) {
						value.params = make(Params, 0, n.maxParams)
					}
					i := len(value.params)
					value.params = value.params[:i+1] // expand slice within preallocated capacity
					value.params[i].Key = n.path[1:]
					val := path[:end]
					if unescape {
						var err error
						if value.params[i].Value, err = url.QueryUnescape(val); err != nil {
							value.params[i].Value = val // fallback, in case of error
						}
					} else {
						value.params[i].Value = val
					}

					// we need to go deeper!
					if end < len(path) {
						if len(n.children) > 0 {
							path = path[end:]
							n = n.children[0]
							prefix = n.path
							continue walk
						}

						// ... but we can't
						value.tsr = len(path) == end+1
						return
					}

					if value.handlers = n.handlers; value.handlers != nil {
						value.fullPath = n.fullPath
						return
					}
					if len(n.children) == 1 {
						// No handle found. Check if a handle for this path + a
						// trailing slash exists for TSR recommendation
						n = n.children[0]
						value.tsr = n.path == "/" && n.handlers != nil
					}

					return

				case catchAll:
					// save param value
					if cap(value.params) < int(n.maxParams) {
						value.params = make(Params, 0, n.maxParams)
					}
					i := len(value.params)
					value.params = value.params[:i+1] // expand slice within preallocated capacity
					value.params[i].Key = n.path[2:]
					if unescape {
						var err error
						if value.params[i].Value, err = url.QueryUnescape(path); err != nil {
							value.params[i].Value = path // fallback, in case of error
						}
					} else {
						value.params[i].Value = path
					}

					value.handlers = n.handlers
					value.fullPath = n.fullPath
					return

				default:
					panic("invalid node type")
				}
			}
		} else if path == prefix {
			// We should have reached the node containing the handle.
			// Check if this node has a handle registered.
			if value.handlers = n.handlers; value.handlers != nil {
				value.fullPath = n.fullPath
				return
			}

			if path == "/" && n.wildChild && n.nType != root {
				value.tsr = true
				return
			}

			// No handle found. Check if a handle for this path + a
			// trailing slash exists for trailing slash recommendation
			indices := n.indices
			for i, max := 0, len(indices); i < max; i++ {
				if indices[i] == '/' {
					n = n.children[i]
					value.tsr = (len(n.path) == 1 && n.handlers != nil) ||
						(n.nType == catchAll && n.children[0].handlers != nil)
					return
				}
			}

			return
		}

		// Nothing found. We can recommend to redirect to the same URL with an
		// extra trailing slash if a leaf exists for that path
		value.tsr = (path == "/") ||
			(len(prefix) == len(path)+1 && prefix[len(path)] == '/' &&
				path == prefix[:len(prefix)-1] && n.handlers != nil)
		return
	}
}