文章目录
- 一.概念辨析
- 二.编写思路
- 三.代码实践
一.概念辨析
- 这个模块是干啥的？
用户给服务器发送一条消息，消息中只指定了交换机，没有指定具体要发布到哪些队列。这个时候服务器模块就需要使用我们的路由交换模块，选择与之匹配的队列了- 怎么匹配？
一个交换机和一个绑定的队列是否匹配，取决于两个要素：
具体如下：
- DIRECT——直接交换：routinng_key 和 binding_key 相等则匹配成功
- FANOUT——广播交换：不用做任何比较，直接匹配成功(注意前提是这个队列和交换机有绑定关系)
- TOPIC——主题交换：只有 routing_key 和 binding_key“匹配”，交换机和队列才匹配成功
- routing_key 和 binding_key 构成
routing_key：由若干个单词构成，单词之间用".“分开，单词由字母，数字和下划线构成
binding_key：在 routing_key 的基础上多了两个通配符”*"和“#”，可以匹配一个单词，#可以匹配 0 个或多个单词
规定和#只能单独存在，不能和其它字符一起组成一个单词，并且#附近不能再有通配符了，因为#已经可以匹配任意多个单词了，再加通配符是没有意义的
二.编写思路
本模块是一个纯算法模块，不管理数据，指向外提供一些静态方法，供服务器模块使用。
方法：
- 判断 binding_key 是否合法：当要新建一个 binding 时，服务器模块会先检查用户给的 binding_key 是否合法
先遍历判断是否有不合法的字符，然后检查每个单词合法性，即不能通配符和普通字符混搭，最后检查#附近是否有通配符- 判断 routing_key 是否合法：服务器模块检查用户发来的消息中的 routing_key 是否合法，如果这都不合法，那根本无法路由交换，选择与之匹配的队列了
只需遍历判断是否有不合法字符即可- 判断 routing_key 是否能和 binding_key 匹配
- 直接交换：判断 routing_key 和 binding_key 是否相等
- 广播交换：直接返回 true
- 主题交换：两个数组的动态规划问题
首先把 binding_key，routing_key 分割成一个个单词构成的单词的数组
建一个 dp 表，dp[i][j]的含义是 binding 单词表的[0,i]部分，和 routing 单词表的[0, j]部分是否匹配
dp[i][j]怎么填？考虑两个单词表的第 i 个单词和第 j 个单词
分类讨论：
- 如果 binding 表和 routing 表最后一个单词相同，或者 binding 表最后是"*"，那么最后一个单词就匹配上了，整体能否匹配取决于他们前面部分能否匹配，取决于 dp[i-1][j-1]的状态
[i, j]这个格子的左上方如果为真，它就为真- 如果 binding 表最后一个单词是#，接下来有三种做法：
- #与和 routing 表最后一个单词匹配，并且#消去，整体能否匹配取决于 dp[i-1][j-1]
- #和 routing 表最后一个单词匹配，但是#不消去，继续向前匹配，整体能否匹配取决于 dp[i][j-1]
- #不和最后一个单词匹配，但是#消去，相当于#匹配了 0 个单词，整体能否匹配去取决于 dp[i-1][j]
所以[i,j]这个格子左上方，左方，上方，任何一个为真即为真
三.代码实践
Route.hpp:
#pragma once
#include "../common/Util.hpp"
#include "../common/Type.hpp"
namespace ns_route
{class Router{public:static bool isLegalRoutingKey(const std::string &routingKey){// 只能有字母，数字和下划线for (auto ch : routingKey){if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_' ||(ch >= '0' && ch <= '9') || ch == '.'){continue;}else{return false;}}return true;}static bool isLegalBindingKey(const std::string &bindingKey){// 先判断是否有非法字符for (auto ch : bindingKey){if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_' || (ch >= '0' && ch <= '9') ||ch == '*' || ch == '#' || ch == '.'){continue;}else{return false;}}// 检查每个单词是否合法:通配符只能单独存在std::vector<std::string> words;int wordNum = ns_util::StringUtil::split(bindingKey, ".", &words, ns_util::SepType::SPLITEASCHAR);for (const auto &word : words){if (word.size() > 1 &&(word.find('*', 0) != std::string::npos || word.find('#', 0) != std::string::npos)){//LOG(INFO) << "单词不合法, bindingKey:" << bindingKey << ", word: " << word << endl;return false;}}// 检查‘#’附近是否有通配符for (int i = 1; i < wordNum; i++){if (words[i] == "#"){if (words[i - 1] == "*" || words[i - 1] == "#"){//LOG(INFO) << "#附近有通配符, bindingKey: " << bindingKey << endl;return false;}}}return true;}static bool isMatched(const std::string &routingKey, const std::string &bindingKey, ns_data::ExchangeType type){if (type == ns_data::ExchangeType::DIRECT){return routingKey == bindingKey;}else if (type == ns_data::ExchangeType::FANOUT){return true;}//主题交换std::vector<std::string> routingWords;std::vector<std::string> bindingWords;int m = ns_util::StringUtil::split(bindingKey, ".", &bindingWords, ns_util::SepType::SPLITEASCHAR);int n = ns_util::StringUtil::split(routingKey, ".", &routingWords, ns_util::SepType::SPLITEASCHAR);// dp[i]对[j]表示对于bindingKey和routingKey分割出来的单词表，前者[0,i]和后者[0,j]是否匹配std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));dp[0][0] = true; // 当两者都为空时匹配成功// 如果bindingWords的第一个单词是“#”,要特殊处理if (bindingWords[0] == "#"){dp[1][0] = true;}// #后面不可能继续跟#,无需往后判断了for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){int x = i - 1;int y = j - 1;if (bindingWords[x] == "#"){// 考虑二者的最后一个单词：// 1.#和routingWords[y]匹配，并且#消去了// 2.#和routingWords[y]匹配,但#留下继续向前匹配// 3.#不和routingWords[y]匹配,但#消去了dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j];}else // 普通单词或者“*”{if (bindingWords[x] == "*" || bindingWords[x] == routingWords[y]){dp[i][j] = dp[i - 1][j - 1];}}}} // end of for(int i)return dp[m][n];}};
}
