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对比很容易发现,同样添加dogdogesdoll,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


下面是规则:

举例

/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