对于后面学习内容的一个规划吧，其实中途变化的可能很大，但是先制定再实行吧



1. 对gin的url前缀树进行学习
2. 使用自己的代码对url前缀树进行实现
3. 看完gin的源代码
4. 实现https://github.com/RezaSi/go-interview-practice中的题目

未来学习规划

# 前缀树静态实现
在学习gin的前缀树的过程中，很难理解其中的逻辑，后来看了部分源代码之后，突然领悟，还得从简单添加功能到复杂，所以，先写一个静态的前缀树，后面再添加功能到复杂



```go
package urltree

import (
	"fmt"
	"log"
	"strings"

	"gitee.com/duzy2023/urltree/internel"
)

// 首先创建一个静态匹配前缀树
type nodeType uint8 // 节点类型
const (
	static nodeType = iota // 静态类型
)

type node struct {
	fullpath string // 全路径，只有最后一个节点才有
	path     string // 当前节点在整个路径中的字段
	children []*node
	nType    nodeType // 节点类型
	indices  string   //子节点path的第一个字符
}

// 获取新节点
func NewRoot() *node {
	n := &node{
		fullpath: "/",
		children: make([]*node, 0),
	}
	return n
}

// 找到两个路径段最长相同前缀的下标
func longestCommonPrefix(apath, bpath string) int {
	i := 0
	max_ := min(len(apath), len(bpath))
	for i < max_ && apath[i] == bpath[i] {
		i++
	}
	return i
}

// 添加静态路由
func (n *node) AddRoute(fullpath string) error {
	if !strings.HasPrefix(fullpath, "/") {
		return fmt.Errorf("path must start with '/' but get '%s'", fullpath)
	}

	// 由于后面会对fullpath进行处理，所以这里对fullpath进行备份
	_fullpath := fullpath

	// 1.
	// 先判断是否是空节点
	// 没有子节点并且path为空，那么就是空节点
	if len(n.children) == 0 && len(n.path) == 0 {
		log.Printf("Empty Node")
		n.path = fullpath
		n.fullpath = _fullpath
		return nil
	}

	// 对于非空节点进行处理
	parentFullPathIndex := 0
walk:
	for {
		// 2.计算最长公共前缀(LCP)
		i := longestCommonPrefix(fullpath, n.path)

		// 3.节点分裂
		// 如果LCP小于当前节点的path长度，就需要分裂
		if i < len(n.path) {
			child := node{
				path:     n.path[i:],
				nType:    n.nType,
				indices:  n.indices,
				children: n.children,
				fullpath: n.fullpath,
			}
			n.children = []*node{&child}
			n.indices = internel.BytesToString([]byte{n.path[i]})
			n.path = fullpath[:i]
			n.fullpath = ""
		}

		// 4.处理剩余路径
		if i < len(fullpath) {
			fullpath = fullpath[i:]
			nextChar := fullpath[0]

			// 5. 查找匹配的子节点
			for j, idxChar := range n.indices {
				if byte(idxChar) == nextChar {
					parentFullPathIndex += len(n.path)
					n = n.children[j]
					continue walk
				}
			}

			// 6.没有匹配的子节点，创建新的节点
			n.indices += internel.BytesToString([]byte{nextChar})
			newChild := &node{
				path:     fullpath,
				fullpath: _fullpath,
				nType:    static,
			}

			n.addChild(newChild)
			return nil

		}
		// 7.完全匹配
		// 说明已经注册了一个完整路径，报错
		if n.fullpath != "" {
			return fmt.Errorf("path '%s' is already registered", _fullpath)
		}
		// 如果n.fullpath == ""，那么，就表明这个路由还没被注册
		n.fullpath = _fullpath
		return nil
	}
}

func (n *node) addChild(child *node) {
	n.children = append(n.children, child)
}

// FindRoute 查找路由 (可选功能)
// path: 待查找的路径
// returns: 找到的节点的 fullpath，如果没找到则返回空字符串
func (n *node) FindRoute(path string) string {
	parentPathIndex := 0

	currentNode := n
	for {
		// 计算当前节点 path 与查找路径的 LCP
		i := longestCommonPrefix(path, currentNode.path)

		// 如果 LCP 不等于当前节点的 path，说明匹配失败
		if i != len(currentNode.path) {
			return "" // 路径不存在
		}

		// 如果 path 已经完全匹配（LCP 等于 path 长度）
		if i == len(path) {
			// 检查当前节点是否有 fullpath（代表它是一个注册的终点）
			return currentNode.fullpath // 返回注册时的完整路径
		}

		// path 还有剩余，继续向下查找
		path = path[i:]
		nextChar := path[0]

		// 在 indices 中查找下一个字符
		foundIndex := -1
		for j, idxChar := range currentNode.indices {
			if byte(idxChar) == nextChar {
				foundIndex = j
				break
			}
		}

		if foundIndex == -1 {
			return "" // 没有找到匹配的子节点，路径不存在
		}

		// 更新 parentPathIndex 并跳转到子节点
		parentPathIndex += len(currentNode.path)
		currentNode = currentNode.children[foundIndex]
	}
}

// PrintTree 用于调试：打印树结构 (辅助函数)
func (n *node) PrintTree(prefix string, isLast bool) {
	if n == nil {
		return
	}
	connector := "├── "
	if isLast {
		connector = "└── "
	}
	fmt.Printf("%s%s path: '%s', fullpath: '%s'\n", prefix, connector, n.path, n.fullpath)

	childCount := len(n.children)
	for i, child := range n.children {
		isLastChild := i == childCount-1
		newPrefix := prefix
		if !isLast {
			newPrefix += "│   " // 如果当前节点不是父节点的最后一个孩子，则竖线继续
		} else {
			newPrefix += "    " // 如果是最后一个孩子，则用空格填充
		}
		child.PrintTree(newPrefix, isLastChild)
	}
}

```
其中的FindTree和PrintTree是使用AI生成的，AI真好用

前缀树静态实现

# 对gin的addRoute代码进行的一个注释
在学习gin代码的过程中，对源码的进行的注释，相当于对自己学习过程的一个笔记

```go
package gin

import (
	"net/url"
	"strings"
	"unicode"
	"unicode/utf8"

	"github.com/gin-gonic/gin/internal/bytesconv"
)

// Param是一个url参数，比如路径是/user/delete/:id
// 请求的url是/user/delete/133
// 那么url参数就是Key:id value:133
type Param struct {
	Key   string
	Value string
}

// 参数切片是有序的，第一个参数也是切片的第一个的值
// 因此，通过下标访问是安全滴
type Params []Param

// 返沪给定的key值的参数值，返回的布尔值表示是否找到对应的值
func (ps Params) Get(name string) (string, bool) {
	for _, entry := range ps {
		if entry.Key == name {
			return entry.Value, true
		}
	}
	return "", false
}

// ByName函数是找到给定key值的参数值，如果没找到返回空
func (ps Params) ByName(name string) (va string) {
	va, _ = ps.Get(name)
	return
}

// 方法树，保存各个方法的root节点
type methodTree struct {
	method string
	root   *node
}

type methodTrees []methodTree

// 返回给定请求方法的root节点，比如get("POST")，那么就返回POST请求的trie树的root节点
func (trees methodTrees) get(method string) *node {
	for _, tree := range trees {
		if tree.method == method {
			return tree.root
		}
	}
	return nil
}

// 比较a,b两个字符串的最长相同前缀的长度
func longestCommonPrefix(a, b string) int {
	i := 0
	max_ := min(len(a), len(b))
	for i < max_ && a[i] == b[i] {
		i++
	}
	return i
}

// addChild will add a child node, keeping wildcardChild at the end
// 添加子节点
func (n *node) addChild(child *node) {
	// 如果是子节点包含通配符节点，那么通配符节点一定在最后
	// 所以在最后一个节点的前面插入新节点
	if n.wildChild && len(n.children) > 0 {
		wildcardChild := n.children[len(n.children)-1]
		n.children = append(n.children[:len(n.children)-1], child, wildcardChild)
	} else {
		// 如果子节点不包含通配符节点，那么直接在最后插入
		n.children = append(n.children, child)
	}
}

func countParams(path string) uint16 {
	colons := strings.Count(path, ":")
	stars := strings.Count(path, "*")
	return safeUint16(colons + stars)
}

func countSections(path string) uint16 {
	return safeUint16(strings.Count(path, "/"))
}

// 节点类型
type nodeType uint8

// 定义节点类型
const (
	static   nodeType = iota // 静态节点
	root                     // 根节点
	param                    // 参数节点 :id之类
	catchAll                 // *匹配节点
)

// 定义节点结构
type node struct {
	path      string        // 子节点路径
	indices   string        // 子节点索引，存储子节点path的第一个字符，比如当前节点有三个子节点user,vip,admin，那么indices就是uva
	wildChild bool          // 是否有通配符子节点
	nType     nodeType      // 子节点类型
	priority  uint32        // 优先级，根据访问频率来计算
	children  []*node       // child nodes, 静态节点在前，通配符子节点在后
	handlers  HandlersChain // 处理函数链
	fullPath  string        // 存储从根节点到当前节点的完整路径
}

// Increments priority of the given child and reorders if necessary
// 提升给定子节点的优先级并在必须的情况下记录
func (n *node) incrementChildPrio(pos int) int {
	// 提升给定位置pos的子节点的优先级
	cs := n.children
	cs[pos].priority++
	prio := cs[pos].priority

	// Adjust position (move to front)
	newPos := pos
	// 当下标pos不在头部（若在头部pos-1就过界了）并且前一个的优先级小于当前pos的优先级，就交换两个位置的子节点
	for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
		// Swap node positions
		cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
	}

	// Build new index char string
	// newPos不等于pos表示更换了位置，需要重新建立索引
	// 上面是子节点切片排序，下面是索引重新排序
	if newPos != pos {
		n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
			n.indices[pos:pos+1] + // The index char we move
			n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
	}

	return newPos
}

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
// 添加路由函数，非线程安全
func (n *node) addRoute(path string, handlers HandlersChain) {
	// path 就是全路径
	fullPath := path
	n.priority++

	// Empty tree
	// 初始化根节点后，根节点内容：path="" fullpath="/"
	// 所以当path为空且无子节点，就可以判断为根节点
	if len(n.path) == 0 && len(n.children) == 0 {
		// 根节点插入子节点
		n.insertChild(path, fullPath, handlers)
		n.nType = root
		return
	}

	// 全路径下标
	parentFullPathIndex := 0

walk:
	for {
		// Find the longest common prefix.
		// This also implies that the common prefix contains no ':' or '*'
		// since the existing key can't contain those chars.
		// 找到最长的普通前缀，并且不包含冒号和引号
		// 因为现存的key不能包含这两种符号
		// i 是最长相同前缀的下标
		i := longestCommonPrefix(path, n.path)

		// Split edge
		// 根据最长相同前缀的下标分割path
		// 注意：这里是小于n.path，也就是节点的path，说明当前节点的path和参数path有相同前缀
		// 所以需要将相同部分的提取出来，作为父节点，将n.path后面不同的部分作为子节点
		// 将当前节点n的所有参数，除了path参数，都由child继承，这样就由node n --> node n children 变为new node --> node child --> node n children
		if i < len(n.path) {
			child := node{
				// 新建子节点，并将path从i分为前后两个path
				path:      n.path[i:],
				wildChild: n.wildChild,
				nType:     static,
				indices:   n.indices,
				children:  n.children,
				handlers:  n.handlers,
				priority:  n.priority - 1,
				fullPath:  n.fullPath,
			}

			n.children = []*node{&child}
			// []byte for proper unicode char conversion, see #65
			n.indices = bytesconv.BytesToString([]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
		// 这里是小于参数path，也就是说处理完相同前缀部分，仍有不同的部分
		// 如果是等于len(path)，那么就是说匹配上了
		if i < len(path) {
			path = path[i:]
			c := path[0]

			// 所以下面要对后面不同部分进行处理
			// 当前节点是参数节点，未处理完的参数path是以 / 开始，并且参数节点只有一个子节点，此时就跳转到子节点进行处理
			// '/' after param
			if n.nType == param && c == '/' && len(n.children) == 1 {
				// 全路径下标新增加当前节点长度，比如：/usr/local/:id/statis，之前是下标在0，当前节点路径是/usr/local/:id，那么下标就跑到/statis的/这里了
				parentFullPathIndex += len(n.path)
				n = n.children[0]
				n.priority++
				continue walk
			}

			// Check if a child with the next path byte exists
			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 != '*' && n.nType != catchAll {
				// []byte for proper unicode char conversion, see #65
				n.indices += bytesconv.BytesToString([]byte{c})
				child := &node{
					fullPath: fullPath,
				}
				n.addChild(child)
				n.incrementChildPrio(len(n.indices) - 1)
				n = child
			} else if n.wildChild {
				// inserting a wildcard node, need to check if it conflicts with the existing wildcard
				n = n.children[len(n.children)-1]
				n.priority++

				// Check if the wildcard matches
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
					// Adding a child to a catchAll is not possible
					n.nType != catchAll &&
					// Check for longer wildcard, e.g. :name and :names
					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
					continue walk
				}

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

			n.insertChild(path, fullPath, handlers)
			return
		}

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

// Search for a wildcard segment and check the name for invalid characters.
// Returns -1 as index, if no wildcard was found.
// 搜索通配符字段，并检查名字中是否有非法字段，比如：/usr/add/:id 就看:id这个通配符字段是否合规
// 如果没有通配符字段，那么就返回-1索引
// 返回通配符段，通配符段的起始下标，是否是合规字段
func findWildcard(path string) (wildcard string, i int, valid bool) {
	// Find start
	escapeColon := false
	for start, c := range []byte(path) {
		// 如果转义字符//后面不是冒号，那么就报错
		if escapeColon {
			escapeColon = false
			if c == ':' {
				continue
			}
			panic("invalid escape string in path '" + path + "'")
		}
		// 如果是\\，就表明，即使后面是:，那么是不转义的冒号，忽略
		if c == '\\' {
			escapeColon = true
			continue
		}
		// A wildcard starts with ':' (param) or '*' (catch-all)
		// 如果不是冒号和星号就重新循环，如果是就是找到了通配符匹配字段的开始点
		if c != ':' && c != '*' {
			continue
		}
		// 上面都是为了找到通配符匹配字段的起始点
		// 下面是为了找到终点

		// Find end and check for invalid characters
		valid = true
		for end, c := range []byte(path[start+1:]) {
			switch c {
			case '/': // 找到通配符：或者*后面的/，表示通配符字段合规，返回
				return path[start : start+1+end], start, valid
			case ':', '*': // 通配符：或者*后面还有：或者*，那么就是不合规
				valid = false
			}
		}
		return path[start:], start, valid
	}
	return "", -1, false
}

// 空根节点（刚初始化，没有子节点）插入子节点函数
// path 路径段
// fullpath 全路径
func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) {
	for {
		// Find prefix until first wildcard
		// 对全路径进行通配符查找
		wildcard, i, valid := findWildcard(path)
		// 没找到通配符就说明全路径是静态匹配，跳出循环
		if i < 0 { // No wildcard found
			break
		}

		// The wildcard name must only contain one ':' or '*' character
		// 如果通配符不合规，就报错退出
		if !valid {
			panic("only one wildcard per path segment is allowed, has: '" +
				wildcard + "' in path '" + fullPath + "'")
		}

		// check if the wildcard has a name
		// 如果通配符匹配段长度小于2，那么表示通配符匹配没有名字，错误的表达，退出
		if len(wildcard) < 2 {
			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
		}

		// 对通配符进行分割处理，分割为一个父节点和一个子节点
		// 对冒号匹配进行处理
		if wildcard[0] == ':' { // param
			// 从通配符字段开始位置将path分为两段，前面的作为父节点的path，后面的是子节点的path
			if i > 0 {
				// Insert prefix before the current wildcard
				n.path = path[:i] // 前面的段给当前的节点，因为分割，会出先一个子节点
				path = path[i:]
			}

			child := &node{
				nType:    param,
				path:     wildcard, // 由此可以看出path就是当前所属的url字段，比如/usr/seller/show/:id，path就是seller或者/seller/这个字段一样
				fullPath: fullPath,
			}
			n.addChild(child)
			n.wildChild = true
			n = child
			n.priority++

			// if the path doesn't end with the wildcard, then there
			// will be another subpath starting with '/'
			// 如果通配符字段不是路径段的全部，那么说明还有部分路径在后面
			// 注意：此时n在上面已经是子节点了
			if len(wildcard) < len(path) {
				path = path[len(wildcard):]

				child := &node{
					priority: 1,
					fullPath: fullPath,
				}
				n.addChild(child)
				n = child
				continue
			}

			// Otherwise we're done. Insert the handle in the new leaf
			n.handlers = handlers
			return
		}

		// catchAll
		// 对于*name 的通配符字段进行处理
		// 如果通配符段的起始下标+通配符段长度不等于路径段的全部长度，那么也就是说*通配符段不是最后一部分，报错
		if i+len(wildcard) != len(path) {
			panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
		}
		// 当path长度大于0，并且最后一个字符是 / ；也就是/usr/seller/show/*id/ 这种
		// 此段代码的逻辑：
		// 因为最后一个字符是 / ；那么也就说这是一个目录，也就是说 / 后面还有其他的内容，那么在这种情况下，*通配符不是唯一一个子节点，就会报错
		// 因为*通配符应该是某个路径下的唯一子节点，因为*号会匹配所有的路径
		if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
			pathSeg := ""
			if len(n.children) != 0 { // 有子节点
				pathSeg, _, _ = strings.Cut(n.children[0].path, "/")
			}
			panic("catch-all wildcard '" + path +
				"' in new path '" + fullPath +
				"' conflicts with existing path segment '" + pathSeg +
				"' in existing prefix '" + n.path + pathSeg +
				"'")
		}

		// currently fixed width 1 for '/'
		// 现在处理只有一个 / 的情况
		// i-- + i<0 就是说，*符号在第一位，但是通配符不能在一个路径段的首位
		// i-- + path[i] != '/'，也就是说*符号前面没有 /
		i--
		if i < 0 || path[i] != '/' {
			panic("no / before catch-all in path '" + fullPath + "'")
		}
		// 因为之前的i-- ，i目前是*通配符下标的前一位，这里是将前面的通用路径赋予当前的节点
		n.path = path[:i]

		// First node: catchAll node with empty path
		child := &node{
			wildChild: true,
			nType:     catchAll,
			fullPath:  fullPath,
		}

		n.addChild(child)
		n.indices = "/"
		n = child
		n.priority++

		// second node: node holding the variable
		child = &node{
			path:     path[i:],
			nType:    catchAll,
			handlers: handlers,
			priority: 1,
			fullPath: fullPath,
		}
		n.children = []*node{child}

		return
	}

	// If no wildcard was found, simply insert the path and handle
	// 因为是静态匹配，就跳出循环
	// 但是注意，这里不会对全路径进行拆分，比如path=/book/20260101/package/details
	// 那么path不会根据"/"符号拆分，而是将子节点的path和fullpath都等于这个path
	// 那么匹配的时候直接全路径匹配，这样节省时间和空间
	// 当插入新路径，比如：path=/book/20260101/mod/details和这个重叠的时候，再进行拆分
	n.path = path
	n.handlers = handlers
	n.fullPath = fullPath
}
```

gin添加路由代码注释

# rhce考试题目错题集

## 查看考题

打开小帽子查看，是web界面

### 考试注意事项

1. 重启之后才会评分，所以所有的操作必须在重启之后仍然有效



### node1的题目

1. 配置网络设置

   1. 先配置网络，然后远程配置更方便，可以复制信息进去

      nmcli connection show

2. 配置yum源
3. 调试selinux
4. 创建用户账户


前缀树静态实现

对gin的addRoute代码进行的一个注释

rhce考试题目错题集

查看考题

小项目初步了解go