query: $select : use trie
The previous implementation has a downside: it stores all intermediate
paths in a hashset. This increases the space complexity. This commit
implements a more efficient (both time and space) algorithm: Trie.
The commit contructs a trie from the values of $select. Upon delegation,
it delegates the whole trie for now. When doing recursive select, now we
only need to keep the current JSON node and corresponding TrieNode.
Given the following assumption:
1. size of the JSON tree (#nodes) is N
2. length of the $select properties is M
3. average length of a single $select property is K
The previous implementation has the following complexity:
1. time: worst case O(N + M * K), when a property is like /a/a/a/a/a
2. space: O(N + M * K^2), when a property is like /a/a/a/a/a
The current implementation improves complexity to:
1. time: O(N + M * K)
2. space: O(N + M * K)
The total image (squashfs) decreases 4096 bytes. The binaray size
also decreases 4096 bytes.
Tested:
1. $select works on real hardware
2. No new service validator failures
3. Added more unit tests
Signed-off-by: Nan Zhou <nanzhoumails@gmail.com>
Change-Id: If9f09db8c76e4e1abb6fa9b760be3816d9eb9f96
diff --git a/redfish-core/include/query.hpp b/redfish-core/include/query.hpp
index d9401bc..fd5d189 100644
--- a/redfish-core/include/query.hpp
+++ b/redfish-core/include/query.hpp
@@ -71,11 +71,13 @@
delegated = query_param::delegate(queryCapabilities, *queryOpt);
std::function<void(crow::Response&)> handler =
asyncResp->res.releaseCompleteRequestHandler();
+
asyncResp->res.setCompleteRequestHandler(
[&app, handler(std::move(handler)),
- query{*queryOpt}](crow::Response& resIn) mutable {
+ query{std::move(*queryOpt)}](crow::Response& resIn) mutable {
processAllParams(app, query, handler, resIn);
});
+
return true;
}