Update get_routes to use trie for efficiency
This commit updates the behavior of request_routes to actually use the
trie data structure to find the appropriate routes. This function was
originaly intended for debugging, but now with redfish, it is being
used to look up routes.
Also, update the prototype so it returns a string pointer to the main
route in the trie instead of copying the whole list of stings.
A future optimization should also give the ability to pick a "stop at"
character, or a depth so that users can decide how deep into the tree
they want to iterate, instead of getting the whole subtree and
filtering after the fact.
Change-Id: I8b98fb3f19f59a043ae6aa583ed62ab89be10eb8
diff --git a/crow/include/crow/app.h b/crow/include/crow/app.h
index 3635b78..e00cf9d 100644
--- a/crow/include/crow/app.h
+++ b/crow/include/crow/app.h
@@ -117,8 +117,12 @@
router_.debug_print();
}
- std::vector<std::string> get_routes() { return router_.get_routes(); }
- std::vector<std::string> get_routes(const std::string& parent) {
+ std::vector<const std::string*> get_routes() {
+ // TODO(ed) Should this be /?
+ const std::string root("");
+ return router_.get_routes(root);
+ }
+ std::vector<const std::string*> get_routes(const std::string& parent) {
return router_.get_routes(parent);
}
diff --git a/crow/include/crow/routing.h b/crow/include/crow/routing.h
index 9a83970..32a580d 100644
--- a/crow/include/crow/routing.h
+++ b/crow/include/crow/routing.h
@@ -552,6 +552,30 @@
optimize();
}
+ void find_route_indexes(const std::string& req_url,
+ std::vector<unsigned>& route_indexes,
+ const Node* node = nullptr, unsigned pos = 0) {
+ if (node == nullptr) {
+ node = head();
+ }
+ for (auto& kv : node->children) {
+ const std::string& fragment = kv.first;
+ const Node* child = &nodes_[kv.second];
+ if (pos >= req_url.size()) {
+ if (child->rule_index != 0 && fragment != "/") {
+ route_indexes.push_back(child->rule_index);
+ }
+ find_route_indexes(req_url, route_indexes, child,
+ pos + fragment.size());
+ } else {
+ if (req_url.compare(pos, fragment.size(), fragment) == 0) {
+ find_route_indexes(req_url, route_indexes, child,
+ pos + fragment.size());
+ }
+ }
+ }
+ }
+
std::pair<unsigned, routing_params> find(
const std::string& req_url, const Node* node = nullptr, unsigned pos = 0,
routing_params* params = nullptr) const {
@@ -798,7 +822,7 @@
rule_without_trailing_slash.pop_back();
rules_.emplace_back(ruleObject);
trie_.add(rule_without_trailing_slash, rules_.size() - 1);
- //trie_.add(rule_without_trailing_slash, RULE_SPECIAL_REDIRECT_SLASH);
+ // trie_.add(rule_without_trailing_slash, RULE_SPECIAL_REDIRECT_SLASH);
}
}
@@ -900,9 +924,9 @@
if (req.get_header_value("Host").empty()) {
res.add_header("Location", req.url + "/");
} else {
- res.add_header("Location", (req.is_secure ? "https://" : "http://") +
- req.get_header_value("Host") + req.url +
- "/");
+ res.add_header("Location",
+ (req.is_secure ? "https://" : "http://") +
+ req.get_header_value("Host") + req.url + "/");
}
res.end();
return;
@@ -942,27 +966,13 @@
void debug_print() { trie_.debug_print(); }
- std::vector<std::string> get_routes() {
- // TODO(ed) Shoudl this be /?
- std::string root("");
- return get_routes(root);
- }
-
- std::vector<std::string> get_routes(const std::string& parent) {
- std::vector<std::string> ret;
- // TODO(ed) this is so lazy, slow and unconcious of performance, but it
- // works
- // this should be replaced with something more performant that actually uses
- // the trie
- // that's available for doing matching.
- for (auto& rule : rules_) {
- if (rule != nullptr) {
- if (rule->rule_.compare(0, parent.size(), parent) == 0) {
- ret.push_back(rule->rule_);
- }
- }
+ std::vector<const std::string*> get_routes(const std::string& parent) {
+ std::vector<unsigned> x;
+ std::vector<const std::string*> ret;
+ trie_.find_route_indexes(parent, x);
+ for (unsigned index : x) {
+ ret.push_back(&rules_[index]->rule_);
}
-
return ret;
}
diff --git a/include/redfish_v1.hpp b/include/redfish_v1.hpp
index 4de009e..243ddfb 100644
--- a/include/redfish_v1.hpp
+++ b/include/redfish_v1.hpp
@@ -18,15 +18,15 @@
template <typename... Middlewares>
void get_redfish_sub_routes(Crow<Middlewares...>& app, const std::string& url,
nlohmann::json& j) {
- auto routes = app.get_routes(url);
- for (auto& route : routes) {
+ std::vector<const std::string*> routes = app.get_routes(url);
+ for (auto route : routes) {
auto redfish_sub_route =
- route.substr(url.size(), route.size() - url.size() - 1);
+ route->substr(url.size(), route->size() - url.size() - 1);
// check if the route is at this level, and we didn't find and exact match
// also, filter out resources that start with $ to remove $metadata
if (!redfish_sub_route.empty() && redfish_sub_route[0] != '$' &&
redfish_sub_route.find('/') == std::string::npos) {
- j[redfish_sub_route] = nlohmann::json{{"@odata.id", route}};
+ j[redfish_sub_route] = nlohmann::json{{"@odata.id", *route}};
}
}
}
@@ -87,6 +87,7 @@
}
}
*/
+
res.json_value = {
{"@odata.context",
"/redfish/v1/$metadata#ChassisCollection.ChassisCollection"},
diff --git a/src/crow_getroutes_test.cpp b/src/crow_getroutes_test.cpp
index 6a9f538..d89c7c1 100644
--- a/src/crow_getroutes_test.cpp
+++ b/src/crow_getroutes_test.cpp
@@ -18,7 +18,8 @@
decltype(app)::server_t server(&app, "127.0.0.1", 45451);
CROW_ROUTE(app, "/")([]() { return 200; });
- EXPECT_THAT(app.get_routes(), testing::ElementsAre("/"));
+ EXPECT_THAT(app.get_routes(),
+ testing::ElementsAre(testing::Pointee(std::string("/"))));
}
// Tests that static urls are correctly passed
@@ -32,7 +33,11 @@
CROW_ROUTE(app, "/boo")([]() { return 200; });
CROW_ROUTE(app, "/moo")([]() { return 200; });
- EXPECT_THAT(app.get_routes(),
- testing::UnorderedElementsAre("/", "/foo", "/bar", "/baz", "/boo",
- "/moo"));
+ EXPECT_THAT(app.get_routes(), testing::UnorderedElementsAre(
+ testing::Pointee(std::string("/")),
+ testing::Pointee(std::string("/foo")),
+ testing::Pointee(std::string("/bar")),
+ testing::Pointee(std::string("/baz")),
+ testing::Pointee(std::string("/boo")),
+ testing::Pointee(std::string("/moo"))));
}
\ No newline at end of file