create an api router

一般来讲，很多API的前缀都是相同的， 如:

/api/v1/:who/moha
/api/v2/:who/+1s

包括现在看到的这篇，它的API是

/article/:id

所有的帖子都有共同的前缀 /article，那么怎样快速的从众多API里面找到某一篇帖子呢？

trie (prefix tree)

顾名思义，就是根据前缀来快速查找文本的 一种典型的空间换时间的数据结构。实现也是非常简单。

class Trie
{
public:
  struct Node
  {
    bool ok;
    Node* children[26];

    Node() : ok{false}, children{} {}
  };

  Trie() = default;

  ~Trie()
  {
    std::list<Node*> tmp;
    for(auto c: root_.children)
    {
      if(c)
      {
        tmp.push_back(c);
      }
    }

    while(!tmp.empty())
    {
      Node* c = tmp.front();
      tmp.pop_front();
      for(auto cc: c->children)
      {
        if(cc)
        {
          tmp.push_back(cc);
        }
      }
      delete c;
    }
  }

  void put(const std::string_view& s)
  {
    Node* p = &root_;
    for(auto c: s)
    {
      if(!p->children[c - 'a'])
      {
        p->children[c - 'a'] = new Node{};
      }
      p = p->children[c - 'a'];
    }
    p->ok = true;
  }

  bool get(const std::string_view& s)
  {
    Node* p = find(s);
    return p != &root_ && p->ok;
  }

private:
  Node root_;

  Node* find(const std::string_view& s)
  {
    Node* p = & root_;
    for(auto c: s)
    {
      if(p->children[c-'a'])
      {
        p = p->children[c-'a'];
      }
    }
    return p;
  }
};

看了上面的实现，我们很容易发现， 字母表children[26]会占用大量的空间。那么，如何在不牺牲太多时间效率的情况下减少空间占用呢？

3way trie

我们可以在每个节点保存输入的第n个字符，然后判断n+1个字符与n个字符的大小关系。这样每个节点只需要保存3个下一级节点的指针就行了。如：

struct Node
{
    bool word = false;
    Node* left;
    Node* mid;
    Node* right;
    char c;
};

这样实现起来类似binary search tree：

Node* put_impl(Node* n, std::string_view s, size_t d)
{
    char c = s[d];
    if(n == nullptr)
    {
        n = new Node{};
        n->c = c;
    }
    if(c < n->c)
    {
        n->left = put_impl(n->left, s, d);
    }
    else if(c > n->c)
    {
        n->right = put_impl(n->right, s, d);
    }
    else if(d < s.size()-1)
    {
        n->mid = put_impl(n->mid, s, d+1);
    }
    else
    {
        n->word = true;
    }
    return n;
}

查找的时候也是同样的思路，代码就不贴了。

看了上面的实现，我们很容易发现，虽然children从26减少到了3但是这个树的深度还是太大了，这样并不会节约多少个有用的节点。那么还有其他办法吗？

space-optimized trie (radix tree)

前面提到，优化空间的方法就是减小字符表的大小，前面的3way trie效果有限是因为仅在节点中保留1一个字符，如果我们先保留全部的字符，等到有相同前缀的字符串添加时在分到新的节点，这样不就减少树的深度了吗，沿着这个思路实现我们就可以得到一个radix tree了。

举个例子： 当添加 dog时，这棵树长这样。

            [dog]

接着添加 doges，这时和已添加的dog有共同的前缀dog，但第一个词刚好就是这个前缀，直接把分割后的es放到下一级即可。

          [dog]
          /
        [es]

接着添加doll，这时共同前缀变成了do，那么需要将当前的节点拆分成两部分，一部分时共同的前缀do，另一部分是剩下的g放在下一级，同时把当前的下一级作为下下集，将要添加字符的剩余部分放到下一级即可。

        [do]
        /    \
      [g]   [ll]
      /
    [es]

以此类推 … …

和前面的3way trie对比很容易发现，同样添加dog、doges、doll，3way trie长这样:

                  [d]
                   |
                  [o]
                /
             [g]
           /     \
        [e]        [l]
           \        |
           [s]     [l]

很明显radix tree比3way trie节约了近一半的节点。

下面贴一下节点类型与添加的实现

struct Node
{
    bool word;
    std::string path;
    std::vector<Node*> children;
    std::vector<char> indices;

    Node(const std::string_view& s) : word{false}, path{s.data(), s.size()}, children{}, indices{} {}
};

void put_impl(Node* n, std::string_view path)
{
    if(n->path.empty() && n->indices.empty())
    {
        n->word = true;
        n->path = path;
        return;
    }
    size_t i = common_prefix(n->path, path);
    if(i < n->path.size())
    {
        Node* c = new Node{n->path.substr(i)};
        c->children = n->children;
        c->indices = n->indices;
        c->word = true;

        n->children.clear();
        n->children.push_back(c);
        n->indices.clear();
        n->indices.push_back(n->path[i]);
        n->path = n->path.substr(0, i);
        n->word = false;
    }

    if(i < path.size())
    {
        path = path.substr(i);
        for(size_t idx = 0; idx < n->indices.size(); ++idx)
        {
            if(n->indices[idx] == path[0])
            {
                n = n->children[idx];
                put_impl(n, path);
                return;
            }
        }
        Node* c = new Node{path};
        c->word = true;
        n->children.push_back(c);
        n->indices.push_back(path[0]);
    }
}

当然，任何算法和数据结构都有一定的局限性。如果空间足够的话，单纯的判断前缀是否存在，当然还是trie最强了。

实现API路由

什么，你想用正则表达式？那可以不用看了。

拿这个blog的实现来说，它只支持3种类型：全匹配，全替换，k-v替换。比如：

# 登录
/api/login

# 静态资源
/static/*file

# 某个帖子
/article/:id

全替换的规则很简单，就是把*file后面所有的字符都替换为实际的字符，如:

/static/css/article.css

这时*file替换为css/article.css。

k-v替换的规则稍微复杂一些，k-v可以有多个，直到遇到/或末尾为止，如规则/api/:user/:id，有url为

/user/elder/+1s

那么会得到键值对

{
  "user": "elder",
  "id": "+1s"
}

规则

为了方便下文解释，这里给一个对照表

name	value
全匹配	static
全替换	wild
k-v替换	param

下面是规则：

• static 必须完全匹配，优先级最高
  
• param 可以与static重合 （/foo/与/foo/:bar可共存）
• wild 不能与static重合 （/foo/与/foo/*bar不可共存）
• param 与 wild 不可共存 （/foo/:bar与/foo/*bar）

举例

/foo
/foo/

=> ok

/foo
/foo/
/foo/:bar

=> ok

/foo
/foo/*bar

=> ok

/foo
/foo/
/foo/*bar

=> conflict with static

/foo
/foo/*bar
/foo/

=> conflict with wild

/foo/:bar
/foo/*bar

=> conflict with param

/foo/*bar
/foo/:bar

=> conflict with wild

/foo/*bar/baz

=> invalid, wild must in the end

/foo/bar*baz

=> invalid, * must after /

/foo/*bar
/foo/bar/*baz

=> invalid, wild will match to the end

/foo
/foo/
/foo/:name
/foo/:name/:age

=> ok

/foo
/foo/
/foo/:name
/foo/:name/*age

=> ok

/foo
/foo
/foo/:name
/foo/bar
/foo/bar/

=> /foo/bar and /foo/bar conflict with param

完整代码

router