乐趣区

关于golang:七天实现web框架动态路由

jiezi

之前看学长他们用过这个动静路由，然而以前也没有太留神，最近在学习框架的建设。第一次让我感触到了算法在写我的项目时候的利用，之前都感觉算法这个货色，就是刷题用的，在实战的时候很少用。明天学习这一块略微有一点吃力，然而还是看懂了，很 nice。
<!– more –>

什么是动静路由呢

动静路由在开发的时候，就是说不是像原来写我的项目的时候，这个固定路由绑定固定的函数，而是变动的路由进行固定函数的绑定，这样就能够实现很多的性能。
动静路由的实例：/api/v1/:name
这里咱们要晓得的是，下面这个路由能够匹配很多的路由比方：
/api/v1/lzz /api/v1/ceshi …. 等
这里第三个分隔开的字段，就是对 name 的赋值。这就是动静路由

实现动静路由须要筹备什么

首先咱们要用到的就是前缀树，这里咱们看一下怎么实现前缀树。咱们还是阐明一下，比如说，在咱们路由中咱们能够通过 / 来宰割节点，而后前面通过这些节点进行寻找正确的路由。
、
下面的这个图就是展现了前缀树。而后上面咱们就来实现一下这个前缀树。
首先定义前缀树的节点：

type node struct {
  pattern  string  // 待匹配的路由
  part     string  // 路由中的一部分
  children []*node // 子节点
  isWild   bool // 这里如果是 * 或者：结尾的就是 true
}

而后咱们建设一个注册函数，一个查找函数 

func (n *node) insert(pattern string, parts []string, height int) {
    // 查看是不是最初一个，是的话就返回
    if len(parts) == height {
        n.pattern = pattern
        return
    }
    // 取出门路中的一部分
    part := parts[height]
    // 查看当初的树中是不是有这个节点，没有的话就进行创立
    child := n.matchChild(part)
    // 上面是创立的流程。也就是创立
    if child == nil {
        // 如果是动静的就会设置为 true
        child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
        n.children = append(n.children, child)
    }
    child.insert(pattern, parts, height+1)
}

查找函数：

func (n *node) search(parts []string, height int) *node {if len(parts) == height || strings.HasPrefix(n.part, "*") {
        if n.pattern == "" {return nil}
        return n
    }

    part := parts[height]
    children := n.matchChildren(part)

    for _, child := range children {result := child.search(parts, height+1)
        if result != nil {return result}
    }

    return nil
}

下面两个函数中有两个要害的函数，就是对路由的匹配，这两个函数我还是看了很久才了解，也是在学习的时候呈现的问题。

// 创立节点插入的时候的判断函数
func (n *node) matchChild(part string) *node {
    for _, child := range n.children {
        if child.part == part || child.isWild {return child}
    }
    return nil
}

// 查找门路
func (n *node) matchChildren(part string) []*node {nodes := make([]*node, 0)
    for _, child := range n.children {
        if child.part == part || child.isWild {nodes = append(nodes, child)
        }
    }
    return nodes
}

两个函数的原理都是差不多的，传入须要判断的门路一部分，而后在节点外面去寻找是否有这个节点，而后找到了就返回，没有找到就返回 nil，我认为的这两个函数，第一个就是判断有没有这个节点，如果没有就返回，而后建设新的节点进行存储，如果找到了就不做操作。
第二个函数，就是对没有局部的判断，而后进行一个增加。
前缀树残缺的代码：

package gee

import (
    "fmt"
    "strings"
)

type node struct {
    pattern  string
    part     string
    children []*node
    isWild   bool
}

func (n *node) String() string {return fmt.Sprintf("node{pattern=%s, part=%s, isWild=%t}", n.pattern, n.part, n.isWild)
}

func (n *node) insert(pattern string, parts []string, height int) {
    // 查看是不是最初一个，是的话就返回
    if len(parts) == height {
        n.pattern = pattern
        return
    }
    // 取出门路中的一部分
    part := parts[height]
    // 查看当初的树中是不是有这个节点，没有的话就进行创立
    child := n.matchChild(part)
    // 上面是创立的流程。也就是创立
    if child == nil {
        // 如果是动静的就会设置为 true
        child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
        n.children = append(n.children, child)
    }
    child.insert(pattern, parts, height+1)
}

// 路由的查找
func (n *node) search(parts []string, height int) *node {if len(parts) == height || strings.HasPrefix(n.part, "*") {
        if n.pattern == "" {return nil}
        return n
    }

    part := parts[height]
    children := n.matchChildren(part)

    for _, child := range children {result := child.search(parts, height+1)
        if result != nil {return result}
    }

    return nil
}

func (n *node) travel(list *([]*node)) {
    if n.pattern != "" {*list = append(*list, n)
    }
    for _, child := range n.children {child.travel(list)
    }
}

// 创立节点插入的时候的判断函数
func (n *node) matchChild(part string) *node {
    for _, child := range n.children {
        if child.part == part || child.isWild {return child}
    }
    return nil
}

// 查找门路
func (n *node) matchChildren(part string) []*node {nodes := make([]*node, 0)
    for _, child := range n.children {
        if child.part == part || child.isWild {nodes = append(nodes, child)
        }
    }
    return nodes
}
退出移动版