[c++/HTTP] 路由的 前缀树和哈希表 实现

/ 1,236评论 / 3797阅读 / 3点赞

路由

基础功能

思考|数据结构设计

前缀树|字典树

哈希表

结合前缀树和哈希表

实现思路

c++实现

#ifndef HTTPMETHOD_H
#define HTTPMETHOD_H
#include <string>

//http请求类型枚举
class MyHttpMethod_e {
public:
	static constexpr int 
		HttpMethod_size = 8,	//http请求类型的数量
		Get		= 1,
		Post	= 2,
		Put		= 4,
		Delete	= 8,
		Head	= 16,
		Options	= 32,
		Trace	= 64,
		Connect	= 128,
		Min		= MyHttpMethod_e::Get,
		Max		= MyHttpMethod_e::Connect;
};

class MyHttpMethodArrItem_s {
public:
	int				mNum;	//在数组中的下标
	int				mInt;	//method的枚举数值
	std::string		mStr;	//类型字符串名称
	MyHttpMethodArrItem_s(int in_mNum, int in_mInt, const std::string& in_mStr) {
		mNum = in_mNum;
		mInt = in_mInt;
		mStr = in_mStr;
	}
};
//HTTP请求类型数组,便于循环判断
static const MyHttpMethodArrItem_s myHttpMethodArr[MyHttpMethod_e::HttpMethod_size] = {
	MyHttpMethodArrItem_s(0, MyHttpMethod_e::Get,		"GET"),
	MyHttpMethodArrItem_s(1, MyHttpMethod_e::Post,		"POST"),
	MyHttpMethodArrItem_s(2, MyHttpMethod_e::Put,		"PUT"),
	MyHttpMethodArrItem_s(3, MyHttpMethod_e::Delete,	"DELETE"),
	MyHttpMethodArrItem_s(4, MyHttpMethod_e::Head,		"HEAD"),
	MyHttpMethodArrItem_s(5, MyHttpMethod_e::Options,	"OPTIONS"),
	MyHttpMethodArrItem_s(6, MyHttpMethod_e::Trace,		"TRACE"),
	MyHttpMethodArrItem_s(7, MyHttpMethod_e::Connect,	"CONNECT")
};
//HTTP请求类型的相关操作方法
class MyHttpMethod_c {
public:
	//判断in_m1与in_m2包含的请求类型是否有交集
	static bool isAllow(int in_m1, int in_m2);
	static bool isAllow(const std::string& in_m1, int in_m2);
	static bool isAllow_strOne(const std::string& in_m1, int in_m2);
	static bool isAllow(const std::string& in_m1, const std::string& in_m2);

	//将包含请求类型的in_str转为int值表示
	static int strToInt(const std::string& in_str);
	/*将包含请求类型的in_str转为int值表示
		*	但要求in_str只包含了一个请求类型
		*	否则只返回按HttpMethod_e枚举顺序第一个找到的类型对应的int值
	*/
	static int strToInt_one(const std::string& in_str);
	//将使用int值表示的请求类型转为string表示
	static std::string intToStr(int in_int);
	/*将使用int值表示的请求类型转为string表示
		*	但要求in_int只表示一个请求类型
		*	否则只返回按HttpMethod_e枚举顺序第一个找到的类型对应的string
	*/
	static std::string intToStr_one(int in_int);
	static int toIndex_one(int in_method);
	static int toIndex_one(const std::string& in_method);
};

#endif
#ifndef MYROUTER_H
#define	MYROUTER_H

#include <map>
#include <string>

#include "MyHttpTask.h"
#include "MyHttpMethod.h"

//路由
class MyRouter_c {
protected:
	//路由 树节点
	struct RouterTreePort_s {
	protected:
	public:
		/// <summary>
		///  路径
		/// </summary>
		std::string			path;
		/// <summary>
		/// 对应Http方法的处理函数
		/// </summary>
		MyHttpProcess_t		fun[MyHttpMethod_e::HttpMethod_size];
		/// <summary>
		/// 子节点
		/// </summary>
		std::map<std::string, RouterTreePort_s*> child;
		
		RouterTreePort_s(const std::string& in_path = "") noexcept :path(in_path) {
			for (int i = MyHttpMethod_e::HttpMethod_size; i-- > 0;)
				fun[i] = nullptr;
		}
		// 返回对应路径节点,不存在则返回nullptr
		RouterTreePort_s* get_child(const std::string& in_path, std::string& re_path, bool do_add = false) {
			return this->get_child(in_path.c_str(), re_path, do_add);
		}
		/// <summary>
		/// 获取对应路径[in_path]的节点,并返回路由路径到[re_path]
		/// </summary>
		/// <param name="in_path">待查找路径</param>
		/// <param name="re_path">节点真实路由路径;无对应节点时返回空</param>
		/// <param name="do_add">当路径对应节点不存在时,是否添加节点</param>
		/// <returns>对应路径节点,不存在则返回nullptr</returns>
		RouterTreePort_s* get_child(const char* in_path, std::string& re_path, bool do_add = false) {
			const char* strptr = in_path, *nextptr = in_path;
			for (;;) {
				if (*nextptr == '/') {
					if (*(nextptr + 1) == '/') {
						++nextptr;
					}
					else
						break;
				}
				else if (*nextptr != '\0') {
					++strptr;
					++nextptr;
				}
				else {	//strp = '\0',是最后一个子节点
					auto it = child.find(in_path);
					if (it != child.end()) {	//存在子节点
						re_path = in_path;
						return it->second;
					}
					else {
						if (do_add) {
							auto treeptr = new RouterTreePort_s(in_path);
							child[in_path] = treeptr;
							re_path = in_path;
							return treeptr;
						}
						else {
							it = child.find("*");
							if (it != child.end()) {
								re_path = "*";
								return it->second;
							}
							else {
								re_path.clear();
								return nullptr;
							}
						}
					}
				}
			}
			// *strp = '/',不是最后一个子节点
			std::string str{ in_path, strptr };
			++nextptr;
			auto it = child.find(str);
			if (it != child.end()) {	//如果存在子节点
				auto re_ptr = it->second->get_child(nextptr, re_path, do_add);
				if (re_ptr != nullptr) {	//有找到匹配的路径
					re_path = str + "/" + re_path;
				}
				return re_ptr;
			}
			else {
				if (do_add) {		//如果需要新建子节点
					auto treeptr = new RouterTreePort_s(str);
					child[str] = treeptr;
					auto re_ptr = treeptr->get_child(nextptr, re_path, do_add);
					if (re_ptr != nullptr) {
						re_path = str + "/" + re_path;
					}
					return re_ptr;
				}
				else {		//查找是否有通配符
					it = child.find("*");
					if (it != child.end()) {
						re_path = "*";
						return it->second;
					}
					else {	// 无查找结果,清空re_path并返回nullptr
						re_path.clear();
						return nullptr;
					}
				}
			}
		}
		/* 使用类型枚举设置处理函数
		* 支持同时设置多个类型
		*/
		bool set_fun_byMethod(const MyHttpProcess_t& in_fun, int in_method) {
			size_t donum = 0;	//记录设置函数的次数
			for (int i = 0; i < MyHttpMethod_e::HttpMethod_size; ++i) {
				if (MyHttpMethod_c::isAllow(in_method, myHttpMethodArr[i].mInt)) {
					fun[myHttpMethodArr[i].mNum] = in_fun;
					++donum;
				}
			}
			if (donum > 0)
				return true;
			else
				return false;
		}
		/* 使用类型下标设置处理函数
		* 仅支持一个类型下标
		*/
		bool set_fun_byIndex(const MyHttpProcess_t& in_fun, int in_index) {
			if (in_index >= 0 && in_index < MyHttpMethod_e::HttpMethod_size) {
				fun[in_index] = in_fun;
				return true;
			}
			else
				return false;
		}
		/* 用数组下标获取函数
		* 下表越界时返回nullptr
		* 指定下标的函数未定义时返回nullptr
		*/
		const MyHttpProcess_t& get_fun_byIndex(int in_index) const {
			if (in_index >= 0 && in_index < MyHttpMethod_e::HttpMethod_size) {
				return fun[in_index];
			}
			else
				return Nullptr_MyHttpProcess;
		}
		/* 用请求类型获取函数
		* 指定请求类型对应的函数未定义时返回nullptr
		*/
		const MyHttpProcess_t& get_fun_byMethod(int in_method) const {
			return this->get_fun_byIndex(MyHttpMethod_c::toIndex_one(in_method));
		}
		/* 清空子节点
		*/
		void clear_child() {
			for (auto it = child.begin(); it != child.end(); ) {
				it->second->clear_child();		//调用子节点的清理
				delete (it->second);			//释放子节点
				child.erase(it);
				it = child.begin();				//重置it的指向
			}
		}
		~RouterTreePort_s() {
			this->clear_child();
		}
	};
	struct RouterCacheValue_s {
		/// <summary>
		/// 路由路径
		/// </summary>
		std::string router_path;
		/// <summary>
		/// 对应节点
		/// </summary>
		RouterTreePort_s* treeptr = nullptr;
	};

	//路由字典树
	RouterTreePort_s routerTree;
	/* 哈希缓存
	* 如果使用缓存接口获取路由位置,获取成功将留下缓存
	* 下次使用相同的path获取时直接提取缓存
	* 添加或删除路由位置将清空缓存重新生成
	*/
	std::unordered_map<std::string, RouterCacheValue_s> cacheMap;
	/// <summary>
	/// 不经过缓存,直接搜索对应路径[in_path]、对应Http方法[in_method]的节点
	/// </summary>
	/// <param name="in_path">待查找路径</param>
	/// <param name="re_path">返回该节点的真实路由路径;节点不存在时返回空</param>
	/// <returns>返回查找结果节点</returns>
	RouterTreePort_s* get_treep_nocache(const std::string& in_path, std::string& re_path);

public:
	MyRouter_c() noexcept :routerTree("/") {}

	/* 添加路由
	* 允许使用通配符 *
	* 允许同时设置多个类型枚举
	* 路径中连续的 / 将被视为仅一个 /
		* 即 /a//b///c 等同于 /a/b/c
	*/
	bool add(const std::string& in_path, int in_method, const MyHttpProcess_t& in_fun);
	/* 判断是否存在路由位置,使用缓存
		* 有,且对应方法有处理函数:返回其处理函数指针,并赋值re_path
		* 有,但对应方法没有处理函数:返回nullptr,并赋值re_path
		* 没有:	返回nullptr,re_path置空
	*/
	const MyHttpProcess_t& get(const std::string& in_path, int in_method, std::string& re_path);
	/* 判断是否存在路由位置,不使用缓存
	* 有,且对应方法有处理函数:返回其处理函数指针,并赋值re_path
	* 有,但对应方法没有处理函数:返回nullptr,并赋值re_path
	* 没有:	返回nullptr,re_path置空
	*/
	const MyHttpProcess_t& get_nocache(const std::string& in_path, int in_method, std::string& re_path);
	/*移除指定的路由位置,并返回其处理函数
	* \param in_method_one 一次调用仅支持移除单一请求类型对应的处理函数
	*/
	MyHttpProcess_t remove(const std::string& in_path, int in_method_one);
	/* 清理缓存
	*/
	void clear_cache();
	//清空路由
	void clear();

};

#endif // ! MYROUTER_H
#include "MyRouter.h"

using std::string;
using std::map;

bool MyRouter_c::add(const string& in_path, int in_method, const MyHttpProcess_t& in_fun)
{
	string&& method = MyHttpMethod_c::intToStr(in_method);
	if (method.empty() == false){		//检查method
		this->cacheMap.clear();
		const char* strp = in_path.c_str();
		while (*strp == '/')
			++strp;
		string re_path{};
		auto treep = this->routerTree.get_child(strp, re_path ,true);
		return treep->set_fun_byMethod(in_fun, in_method);
	}
	else
		return false;
}
MyRouter_c::RouterTreePort_s* MyRouter_c::get_treep_nocache(const std::string& in_path, std::string& re_path) {
	const char* strp = in_path.c_str();
	while (*strp == '/')
		++strp;
	auto treep = this->routerTree.get_child(strp, re_path);
	if (false == re_path.empty()) {
		re_path = "/" + re_path;
	}
	return treep;
}
const MyHttpProcess_t& MyRouter_c::get_nocache(const std::string& in_path, int in_method, std::string& re_path) {
	auto treep = this->get_treep_nocache(in_path, re_path);
	if (treep != nullptr) {		//判断是否存在路由位置
		const auto& fun = treep->get_fun_byMethod(in_method);
		return fun;
	}
	return Nullptr_MyHttpProcess;
}
const MyHttpProcess_t& MyRouter_c::get(const std::string& in_path, int in_method, string& re_path)
{
	auto refind = this->cacheMap.find(in_path);
	MyRouter_c::RouterTreePort_s* treeptr = nullptr;
	if (refind != this->cacheMap.end()) {
		treeptr = refind->second.treeptr;
		re_path = refind->second.router_path;
	}
	else
		treeptr = this->get_treep_nocache(in_path, re_path);
	if (treeptr != nullptr) {		//判断是否存在路由位置
		const auto& fun = treeptr->get_fun_byMethod(in_method);
		if (fun) {
			this->cacheMap.insert(
				{
					in_path,
					{
						re_path,
						treeptr
					}
				});
		}
		return fun;
	}
	return Nullptr_MyHttpProcess;
}
MyHttpProcess_t MyRouter_c::remove(const std::string& in_path, int in_method) {
	string&& method = MyHttpMethod_c::intToStr(in_method);
	if (method.empty() == false) {		//检查method
		const char* strp = in_path.c_str();
		while (*strp == '/')
			++strp;
		string re_path{};
		auto treep = this->routerTree.get_child(strp, re_path, false);
		if (treep) {
			this->cacheMap.clear();
			int index = MyHttpMethod_c::toIndex_one(in_method);
			const auto& fun = treep->get_fun_byIndex(index);
			treep->set_fun_byIndex(nullptr, index);
			return fun;
		}
	}
	return nullptr;
}
void MyRouter_c::clear_cache() {
	this->cacheMap.clear();
}
void MyRouter_c::clear()
{
	this->routerTree.clear_child();
}
  1. Michaelsew说道:

    https://indiaph24.store/# п»їlegitimate online pharmacies india

  2. StevenSen说道:

    mexican border pharmacies shipping to usa: Online Pharmacies in Mexico – mexican rx online

  3. RickyAlage说道:

    best online pharmacy india buy medicines from India top online pharmacy india

  4. Michaelsew说道:

    https://canadaph24.pro/# canada pharmacy reviews

  5. StevenSen说道:

    best online pharmacies in mexico: Mexican Pharmacy Online – mexican drugstore online

  6. RickyAlage说道:

    pharmacy website india indian pharmacy best online pharmacy india

  7. RickyAlage说道:

    reputable mexican pharmacies online Mexican Pharmacy Online medication from mexico pharmacy

  8. Michaelsew说道:

    https://canadaph24.pro/# canadian pharmacy phone number

  9. RickyAlage说道:

    online canadian drugstore Certified Canadian Pharmacies canadian pharmacy review

  10. RickyAlage说道:

    canada pharmacy online Large Selection of Medications from Canada best canadian online pharmacy

  11. StevenSen说道:

    canada pharmacy online legit: canadian pharmacy checker – safe canadian pharmacy

  12. RickyAlage说道:

    best india pharmacy Generic Medicine India to USA indian pharmacy

  13. Michaelsew说道:

    https://mexicoph24.life/# mexican border pharmacies shipping to usa

  14. RickyAlage说道:

    Online medicine order indian pharmacy top online pharmacy india

  15. StevenSen说道:

    mail order pharmacy india: Generic Medicine India to USA – indian pharmacies safe

  16. Michaelsew说道:

    http://indiaph24.store/# mail order pharmacy india

  17. RickyAlage说道:

    mexican border pharmacies shipping to usa buying from online mexican pharmacy mexico drug stores pharmacies

  18. Michaelsew说道:

    http://canadaph24.pro/# canadian drug pharmacy

  19. RickyAlage说道:

    canada drugs online reviews Certified Canadian Pharmacies canadian online drugs

  20. RickyAlage说道:

    buying prescription drugs in mexico online mexican pharmacy medicine in mexico pharmacies

  21. Michaelsew说道:

    http://indiaph24.store/# top 10 online pharmacy in india

  22. RickyAlage说道:

    online shopping pharmacy india online pharmacy india world pharmacy india

  23. RickyAlage说道:

    medicine in mexico pharmacies mexico pharmacy medicine in mexico pharmacies

  24. Michaelsew说道:

    http://canadaph24.pro/# best rated canadian pharmacy

  25. RickyAlage说道:

    mexican border pharmacies shipping to usa cheapest mexico drugs mexico pharmacies prescription drugs

  26. Michaelsew说道:

    http://mexicoph24.life/# purple pharmacy mexico price list

  27. StevenSen说道:

    buying prescription drugs in mexico online: mexico pharmacy – mexico drug stores pharmacies

  28. RickyAlage说道:

    mexican pharmacy cheapest mexico drugs п»їbest mexican online pharmacies

  29. RickyAlage说道:

    purple pharmacy mexico price list Online Pharmacies in Mexico mexican border pharmacies shipping to usa

  30. Michaelsew说道:

    https://canadaph24.pro/# canadian online pharmacy

  31. RickyAlage说道:

    top online pharmacy india buy medicines from India pharmacy website india

  32. Walteronerb说道:

    https://casinvietnam.shop/# casino tr?c tuy?n vi?t nam

  33. JamesAnirm说道:

    https://casinvietnam.com/# web c? b?c online uy tin

  34. MichaelFah说道:

    casino tr?c tuy?n uy tin choi casino tr?c tuy?n tren di?n tho?i game c? b?c online uy tin

  35. Chrisror说道:

    danh bai tr?c tuy?n casino tr?c tuy?n vi?t nam choi casino tr?c tuy?n tren di?n tho?i

  36. Walteronerb说道:

    https://casinvietnam.com/# web c? b?c online uy tin

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注