Method buildTree

router.go:829–884

buildTree build the prefix tree from the previously registered routes

()

// buildTree build the prefix tree from the previously registered routes
func (app *App) buildTree() *App {
	// If routes haven't been refreshed, nothing to do
	if !app.hasRoutesRefreshed {
		return app
	}

	// 1) First loop: determine all possible 3-char prefixes ("treePaths") for each method
	for method := range app.config.RequestMethods {
		routes := app.stack[method]
		treePaths := make([]int, len(routes))

		globalCount := 0
		prefixCounts := make(map[int]int, len(routes))

		for i, route := range routes {
			if len(route.routeParser.segs) > 0 && len(route.routeParser.segs[0].Const) >= maxDetectionPaths {
				treePaths[i] = int(route.routeParser.segs[0].Const[0])<<16 |
					int(route.routeParser.segs[0].Const[1])<<8 |
					int(route.routeParser.segs[0].Const[2])
			}

			if treePaths[i] == 0 {
				globalCount++
				continue
			}

			prefixCounts[treePaths[i]]++
		}

		prevBuckets := app.treeStack[method]
		tsMap := make(map[int][]*Route, len(prefixCounts)+1)
		tsMap[0] = reuseRouteBucket(prevBuckets, 0, globalCount)
		for treePath, count := range prefixCounts {
			tsMap[treePath] = reuseRouteBucket(prevBuckets, treePath, count+globalCount)
		}

		for i, route := range routes {
			treePath := treePaths[i]

			if treePath == 0 {
				for bucket := range tsMap {
					tsMap[bucket] = append(tsMap[bucket], route)
				}
				continue
			}

			tsMap[treePath] = append(tsMap[treePath], route)
		}

		app.treeStack[method] = tsMap
	}

	// reset the flag and return
	app.hasRoutesRefreshed = false
	return app
}

func reuseRouteBucket(prev map[int][]*Route, key, capHint int) []*Route {