From d0141b26136ddccbb2185b17b2b3822cf13d422a Mon Sep 17 00:00:00 2001 From: ipknHama Date: Wed, 16 Apr 2014 02:57:18 +0900 Subject: fix routing bugs, some optimization on trie --- .gitignore | 7 +--- Makefile | 3 +- common.h | 17 +++++++++ flask.h | 6 +++ routing.h | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----- unittest.cpp | 95 ++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 232 insertions(+), 16 deletions(-) diff --git a/.gitignore b/.gitignore index e86bfe6..2837b7f 100644 --- a/.gitignore +++ b/.gitignore @@ -27,8 +27,5 @@ unittest *.gcov covtest -unittest.gcda -unittest.gcno - -http_parser.gcda -http_parser.gcno +*.gcda +*.gcno diff --git a/Makefile b/Makefile index 5e34a02..ff23cb6 100644 --- a/Makefile +++ b/Makefile @@ -15,7 +15,8 @@ unittest: unittest.cpp routing.h ./unittest covtest: unittest.cpp routing.h utility.h flask.h http_server.h http_connection.h parser.h http_response.h common.h - g++ -Wall -g -std=c++11 -fno-default-inline -fno-inline-small-functions --coverage -o covtest unittest.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/ + g++ -O2 -Wall -g -std=c++11 -fno-default-inline -fno-inline-small-functions --coverage -o covtest unittest.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/ + #clang++ -O2 -Wall -g -std=c++11 -o covtest unittest.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/ ./covtest gcov -r unittest.cpp diff --git a/common.h b/common.h index ff63e9f..c028ee4 100644 --- a/common.h +++ b/common.h @@ -22,6 +22,23 @@ namespace flask std::vector double_params; std::vector string_params; + void debug_print() const + { + std::cerr << "routing_params" << std::endl; + for(auto i:int_params) + std::cerr< T get(unsigned) const; diff --git a/flask.h b/flask.h index ec14f9a..ddc91e8 100644 --- a/flask.h +++ b/flask.h @@ -59,6 +59,12 @@ namespace flask Server server(this, port_); server.run(); } + void debug_print() + { + std::cerr << "Routing:" << std::endl; + router_.debug_print(); + } + private: uint16_t port_ = 80; diff --git a/routing.h b/routing.h index fd8c475..4b3c812 100644 --- a/routing.h +++ b/routing.h @@ -122,7 +122,7 @@ namespace flask { response operator()(F& handler, const routing_params& params) { - using pushed = typename black_magic::S::template push_back>; + using pushed = typename black_magic::S::template push_back>; return call, pushed>()(handler, params); } @@ -133,7 +133,7 @@ namespace flask { response operator()(F& handler, const routing_params& params) { - using pushed = typename black_magic::S::template push_back>; + using pushed = typename black_magic::S::template push_back>; return call, pushed>()(handler, params); } @@ -144,7 +144,7 @@ namespace flask { response operator()(F& handler, const routing_params& params) { - using pushed = typename black_magic::S::template push_back>; + using pushed = typename black_magic::S::template push_back>; return call, pushed>()(handler, params); } @@ -158,7 +158,6 @@ namespace flask return handler( params.get(Args1::pos)... ); - //return response(500); } }; public: @@ -182,6 +181,8 @@ namespace flask { static_assert(black_magic::CallHelper>::value, "Handler type is mismatched with URL paramters"); + static_assert(!std::is_same()...))>::value, + "Handler function cannot have void return type; valid return types: string, int, flask::resposne"); handler_ = [f = std::move(f)](Args ... args){ return response(f(args...)); }; @@ -192,6 +193,8 @@ namespace flask { static_assert(black_magic::CallHelper>::value, "Handler type is mismatched with URL paramters"); + static_assert(!std::is_same()...))>::value, + "Handler function cannot have void return type; valid return types: string, int, flask::resposne"); name_ = std::move(name); handler_ = [f = std::move(f)](Args ... args){ return response(f(args...)); @@ -222,9 +225,10 @@ namespace flask public: struct Node { - std::unordered_map children; unsigned rule_index{}; std::array param_childrens{}; + std::unordered_map children; + bool IsSimpleNode() const { return @@ -243,10 +247,46 @@ namespace flask 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]; - optimizeNode(child); + 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); + } } } @@ -383,7 +423,7 @@ public: } } - return {found, std::move(match_params)}; + return {found, match_params}; } void add(const std::string& url, unsigned rule_index) @@ -416,7 +456,12 @@ public: { if (url.compare(i, it->name.size(), it->name) == 0) { - idx = nodes_[idx].param_childrens[(int)it->type] = new_node(); + if (!nodes_[idx].param_childrens[(int)it->type]) + { + auto new_node_idx = new_node(); + nodes_[idx].param_childrens[(int)it->type] = new_node_idx; + } + idx = nodes_[idx].param_childrens[(int)it->type]; i += it->name.size(); found = true; break; @@ -425,7 +470,8 @@ public: if (!found) { - throw std::runtime_error("Invalid parameter type: " + url + " (" + boost::lexical_cast(i) + ")"); + throw std::runtime_error("Invalid parameter type: " + url + + " (" + boost::lexical_cast(i) + ")"); } i --; } @@ -434,7 +480,8 @@ public: std::string piece(&c, 1); if (!nodes_[idx].children.count(piece)) { - nodes_[idx].children.emplace(piece, new_node()); + auto new_node_idx = new_node(); + nodes_[idx].children.emplace(piece, new_node_idx); } idx = nodes_[idx].children[piece]; } @@ -443,6 +490,52 @@ public: 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]) + { + std::cerr << std::string(2*level, ' ') /*<< "("<param_childrens[i]<<") "*/; + switch((ParamType)i) + { + case ParamType::INT: + std::cerr << ""; + break; + case ParamType::UINT: + std::cerr << ""; + break; + case ParamType::DOUBLE: + std::cerr << ""; + break; + case ParamType::STRING: + std::cerr << ""; + break; + case ParamType::PATH: + std::cerr << ""; + break; + default: + std::cerr << ""; + break; + } + std::cerr << std::endl; + debug_node_print(&nodes_[n->param_childrens[i]], level+1); + } + } + for(auto& kv : n->children) + { + std::cerr << std::string(2*level, ' ') /*<< "(" << kv.second << ") "*/ << kv.first << std::endl; + debug_node_print(&nodes_[kv.second], level+1); + } + } + + public: + void debug_print() + { + debug_node_print(head(), 0); + } + private: const Node* head() const { @@ -498,6 +591,7 @@ public: response handle(const request& req) { auto found = trie_.find(req); + unsigned rule_index = found.first; if (!rule_index) @@ -508,6 +602,12 @@ public: return rules_[rule_index]->handle(req, found.second); } + + void debug_print() + { + trie_.debug_print(); + } + private: std::vector> rules_; Trie trie_; diff --git a/unittest.cpp b/unittest.cpp index b573b13..c0a45b7 100644 --- a/unittest.cpp +++ b/unittest.cpp @@ -30,6 +30,8 @@ void fail(Args...args) { error_print(args...);failed__ = true; } #define ASSERT_NOTEQUAL(a, b) if (a != b) fail("Assert fail: not expected ", (a), ", " #a " != " #b ", at " __FILE__ ":",__LINE__) #define TEST(x) struct test##x:public Test{void test();}x##_; \ void test##x::test() +#define DISABLE_TEST(x) struct test##x{void test();}x##_; \ + void test##x::test() TEST(Rule) { @@ -79,6 +81,99 @@ TEST(ParameterTagging) static_assert(std::is_same, black_magic::arguments<6*6+6*3+2>::type>::value, "tag to type container"); } +TEST(RoutingTest) +{ + Flask app; + int A{}; + uint32_t B{}; + double C{}; + string D{}; + string E{}; + + FLASK_ROUTE(app, "/0/") + ([&](uint32_t b){ + B = b; + return "OK"; + }); + + FLASK_ROUTE(app, "/1//") + ([&](int a, uint32_t b){ + A = a; B = b; + return "OK"; + }); + + FLASK_ROUTE(app, "/4////") + ([&](int a, uint32_t b, double c, string d){ + A = a; B = b; C = c; D = d; + return "OK"; + }); + + FLASK_ROUTE(app, "/5/////") + ([&](int a, uint32_t b, double c, string d, string e){ + A = a; B = b; C = c; D = d; E = e; + return "OK"; + }); + + app.validate(); + app.debug_print(); + + { + request req; + + req.url = "/0/1001999"; + + auto res = app.handle(req); + + ASSERT_EQUAL(200, res.code); + + ASSERT_EQUAL(1001999, B); + } + + { + request req; + + req.url = "/1/-100/1999"; + + auto res = app.handle(req); + + ASSERT_EQUAL(200, res.code); + + ASSERT_EQUAL(-100, A); + ASSERT_EQUAL(1999, B); + } + { + request req; + + req.url = "/4/5000/3/-2.71828/hellhere"; + req.headers["TestHeader"] = "Value"; + + auto res = app.handle(req); + + ASSERT_EQUAL(200, res.code); + + ASSERT_EQUAL(5000, A); + ASSERT_EQUAL(3, B); + ASSERT_EQUAL(-2.71828, C); + ASSERT_EQUAL("hellhere", D); + } + { + request req; + + req.url = "/5/-5/999/3.141592/hello_there/a/b/c/d"; + req.headers["TestHeader"] = "Value"; + + auto res = app.handle(req); + + ASSERT_EQUAL(200, res.code); + + ASSERT_EQUAL(-5, A); + ASSERT_EQUAL(999, B); + ASSERT_EQUAL(3.141592, C); + ASSERT_EQUAL("hello_there", D); + ASSERT_EQUAL("a/b/c/d", E); + } +} + TEST(simple_response_routing_params) { ASSERT_EQUAL(100, response(100).code); -- cgit v1.2.3-54-g00ecf