Searched hist:"827 c4902835d3175a36d90808a51304f744203ce" (Results 1 – 2 of 2) sorted by relevance
| /openbmc/bmcweb/redfish-core/include/ |
| H A D | query.hpp | diff 827c4902835d3175a36d90808a51304f744203ce Tue Aug 02 23:57:55 CDT 2022 Nan Zhou <nanzhoumails@gmail.com> 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
|
| /openbmc/bmcweb/redfish-core/include/utils/ |
| H A D | query_param.hpp | diff 827c4902835d3175a36d90808a51304f744203ce Tue Aug 02 23:57:55 CDT 2022 Nan Zhou <nanzhoumails@gmail.com> 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
|