From 81fcf4af0127d93e817877d0ce1223b606d30fd6 Mon Sep 17 00:00:00 2001 From: ipknHama Date: Thu, 7 Aug 2014 06:18:21 +0900 Subject: decide to be header only --- include/routing.h | 362 ++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 340 insertions(+), 22 deletions(-) (limited to 'include/routing.h') diff --git a/include/routing.h b/include/routing.h index 2483bb9..28700c1 100644 --- a/include/routing.h +++ b/include/routing.h @@ -279,42 +279,329 @@ namespace crow std::array param_childrens{}; std::unordered_map children; - bool IsSimpleNode() const; + bool IsSimpleNode() const + { + return + !rule_index && + std::all_of( + std::begin(param_childrens), + std::end(param_childrens), + [](unsigned x){ return !x; }); + } }; - Trie(); + Trie() : nodes_(1) + { + } - void validate(); +private: + void optimizeNode(Node* node) + { + for(auto x : node->param_childrens) + { + if (!x) + continue; + Node* child = &nodes_[x]; + optimizeNode(child); + } + if (node->children.empty()) + return; + bool mergeWithChild = true; + for(auto& kv : node->children) + { + Node* child = &nodes_[kv.second]; + if (!child->IsSimpleNode()) + { + mergeWithChild = false; + break; + } + } + if (mergeWithChild) + { + decltype(node->children) merged; + for(auto& kv : node->children) + { + Node* child = &nodes_[kv.second]; + for(auto& child_kv : child->children) + { + merged[kv.first + child_kv.first] = child_kv.second; + } + } + node->children = std::move(merged); + optimizeNode(node); + } + else + { + for(auto& kv : node->children) + { + Node* child = &nodes_[kv.second]; + optimizeNode(child); + } + } + } + + void optimize() + { + optimizeNode(head()); + } - void add(const std::string& url, unsigned rule_index); +public: + void validate() + { + if (!head()->IsSimpleNode()) + throw std::runtime_error("Internal error: Trie header should be simple!"); + optimize(); + } - std::pair find( - const request& req, - const Node* node = nullptr, - unsigned pos = 0, - routing_params* params = nullptr) const; + std::pair find(const request& req, const Node* node = nullptr, unsigned pos = 0, routing_params* params = nullptr) const + { + routing_params empty; + if (params == nullptr) + params = ∅ - void debug_print(); + unsigned found{}; + routing_params match_params; - private: - void debug_node_print(Node* n, int level); + if (node == nullptr) + node = head(); + if (pos == req.url.size()) + return {node->rule_index, *params}; + + auto update_found = [&found, &match_params](std::pair& ret) + { + if (ret.first && (!found || found > ret.first)) + { + found = ret.first; + match_params = std::move(ret.second); + } + }; + + if (node->param_childrens[(int)ParamType::INT]) + { + char c = req.url[pos]; + if ((c >= '0' && c <= '9') || c == '+' || c == '-') + { + char* eptr; + errno = 0; + long long int value = strtoll(req.url.data()+pos, &eptr, 10); + if (errno != ERANGE && eptr != req.url.data()+pos) + { + params->int_params.push_back(value); + auto ret = find(req, &nodes_[node->param_childrens[(int)ParamType::INT]], eptr - req.url.data(), params); + update_found(ret); + params->int_params.pop_back(); + } + } + } + + if (node->param_childrens[(int)ParamType::UINT]) + { + char c = req.url[pos]; + if ((c >= '0' && c <= '9') || c == '+') + { + char* eptr; + errno = 0; + unsigned long long int value = strtoull(req.url.data()+pos, &eptr, 10); + if (errno != ERANGE && eptr != req.url.data()+pos) + { + params->uint_params.push_back(value); + auto ret = find(req, &nodes_[node->param_childrens[(int)ParamType::UINT]], eptr - req.url.data(), params); + update_found(ret); + params->uint_params.pop_back(); + } + } + } + + if (node->param_childrens[(int)ParamType::DOUBLE]) + { + char c = req.url[pos]; + if ((c >= '0' && c <= '9') || c == '+' || c == '-' || c == '.') + { + char* eptr; + errno = 0; + double value = strtod(req.url.data()+pos, &eptr); + if (errno != ERANGE && eptr != req.url.data()+pos) + { + params->double_params.push_back(value); + auto ret = find(req, &nodes_[node->param_childrens[(int)ParamType::DOUBLE]], eptr - req.url.data(), params); + update_found(ret); + params->double_params.pop_back(); + } + } + } + + if (node->param_childrens[(int)ParamType::STRING]) + { + size_t epos = pos; + for(; epos < req.url.size(); epos ++) + { + if (req.url[epos] == '/') + break; + } + + if (epos != pos) + { + params->string_params.push_back(req.url.substr(pos, epos-pos)); + auto ret = find(req, &nodes_[node->param_childrens[(int)ParamType::STRING]], epos, params); + update_found(ret); + params->string_params.pop_back(); + } + } + + if (node->param_childrens[(int)ParamType::PATH]) + { + size_t epos = req.url.size(); + + if (epos != pos) + { + params->string_params.push_back(req.url.substr(pos, epos-pos)); + auto ret = find(req, &nodes_[node->param_childrens[(int)ParamType::PATH]], epos, params); + update_found(ret); + params->string_params.pop_back(); + } + } - void optimizeNode(Node* node); - void optimize(); + for(auto& kv : node->children) + { + const std::string& fragment = kv.first; + const Node* child = &nodes_[kv.second]; - const Node* head() const; - Node* head(); + if (req.url.compare(pos, fragment.size(), fragment) == 0) + { + auto ret = find(req, child, pos + fragment.size(), params); + update_found(ret); + } + } - unsigned new_node(); + return {found, match_params}; + } + + void add(const std::string& url, unsigned rule_index) + { + unsigned idx{0}; + + for(unsigned i = 0; i < url.size(); i ++) + { + char c = url[i]; + if (c == '<') + { + static struct ParamTraits + { + ParamType type; + std::string name; + } paramTraits[] = + { + { ParamType::INT, "" }, + { ParamType::UINT, "" }, + { ParamType::DOUBLE, "" }, + { ParamType::DOUBLE, "" }, + { ParamType::STRING, "" }, + { ParamType::STRING, "" }, + { ParamType::PATH, "" }, + }; + + for(auto& x:paramTraits) + { + if (url.compare(i, x.name.size(), x.name) == 0) + { + if (!nodes_[idx].param_childrens[(int)x.type]) + { + auto new_node_idx = new_node(); + nodes_[idx].param_childrens[(int)x.type] = new_node_idx; + } + idx = nodes_[idx].param_childrens[(int)x.type]; + i += x.name.size(); + break; + } + } + + i --; + } + else + { + std::string piece(&c, 1); + if (!nodes_[idx].children.count(piece)) + { + auto new_node_idx = new_node(); + nodes_[idx].children.emplace(piece, new_node_idx); + } + idx = nodes_[idx].children[piece]; + } + } + if (nodes_[idx].rule_index) + throw std::runtime_error("handler already exists for " + url); + nodes_[idx].rule_index = rule_index; + } + private: + void debug_node_print(Node* n, int level) + { + for(int i = 0; i < (int)ParamType::MAX; i ++) + { + if (n->param_childrens[i]) + { + CROW_LOG_DEBUG << std::string(2*level, ' ') /*<< "("<param_childrens[i]<<") "*/; + switch((ParamType)i) + { + case ParamType::INT: + CROW_LOG_DEBUG << ""; + break; + case ParamType::UINT: + CROW_LOG_DEBUG << ""; + break; + case ParamType::DOUBLE: + CROW_LOG_DEBUG << ""; + break; + case ParamType::STRING: + CROW_LOG_DEBUG << ""; + break; + case ParamType::PATH: + CROW_LOG_DEBUG << ""; + break; + default: + CROW_LOG_DEBUG << ""; + break; + } + + debug_node_print(&nodes_[n->param_childrens[i]], level+1); + } + } + for(auto& kv : n->children) + { + CROW_LOG_DEBUG << std::string(2*level, ' ') /*<< "(" << kv.second << ") "*/ << kv.first; + debug_node_print(&nodes_[kv.second], level+1); + } + } + + public: + void debug_print() + { + debug_node_print(head(), 0); + } private: + const Node* head() const + { + return &nodes_.front(); + } + + Node* head() + { + return &nodes_.front(); + } + + unsigned new_node() + { + nodes_.resize(nodes_.size()+1); + return nodes_.size() - 1; + } + std::vector nodes_; }; class Router { public: - Router(); + Router() : rules_(1) {} template typename black_magic::arguments::type::template rebind& new_rule_tagged(const std::string& rule) { @@ -325,11 +612,42 @@ namespace crow return *ruleObject; } - void validate(); + void validate() + { + trie_.validate(); + for(auto& rule:rules_) + { + if (rule) + rule->validate(); + } + } - void handle(const request& req, response& res); - - void debug_print(); + void handle(const request& req, response& res) + { + auto found = trie_.find(req); + + unsigned rule_index = found.first; + + if (!rule_index) + { + CROW_LOG_DEBUG << "Cannot match rules " << req.url; + res = response(404); + res.end(); + return; + } + + if (rule_index >= rules_.size()) + throw std::runtime_error("Trie internal structure corrupted!"); + + CROW_LOG_DEBUG << "Matched rule '" << ((TaggedRule<>*)rules_[rule_index].get())->rule_ << "'"; + + rules_[rule_index]->handle(req, res, found.second); + } + + void debug_print() + { + trie_.debug_print(); + } private: std::vector> rules_; -- cgit v1.2.3-54-g00ecf