Move router trie to its own file
Just as the title says. Trie is useful outside of just the router (for
making other routers.)
Change-Id: I961927f2cea44ee78f32337e64741edad9dc542f
Signed-off-by: Ed Tanous <etanous@nvidia.com>
diff --git a/http/routing/trie.hpp b/http/routing/trie.hpp
new file mode 100644
index 0000000..6e60714
--- /dev/null
+++ b/http/routing/trie.hpp
@@ -0,0 +1,327 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: Copyright OpenBMC Authors
+
+#pragma once
+
+#include "logging.hpp"
+
+#include <boost/container/flat_map.hpp>
+#include <boost/container/small_vector.hpp>
+
+#include <cstddef>
+#include <format>
+#include <functional>
+#include <stdexcept>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace crow
+{
+
+template <typename ContainedType>
+class Trie
+{
+ public:
+ struct Node
+ {
+ unsigned ruleIndex = 0U;
+
+ size_t stringParamChild = 0U;
+ size_t pathParamChild = 0U;
+
+ using ChildMap = boost::container::flat_map<
+ std::string, unsigned, std::less<>,
+ boost::container::small_vector<std::pair<std::string, unsigned>,
+ 1>>;
+ ChildMap children;
+
+ bool isSimpleNode() const
+ {
+ return ruleIndex == 0 && stringParamChild == 0 &&
+ pathParamChild == 0;
+ }
+ };
+
+ Trie() : nodes(1) {}
+
+ private:
+ void optimizeNode(Node& node)
+ {
+ if (node.stringParamChild != 0U)
+ {
+ optimizeNode(nodes[node.stringParamChild]);
+ }
+ if (node.pathParamChild != 0U)
+ {
+ optimizeNode(nodes[node.pathParamChild]);
+ }
+
+ if (node.children.empty())
+ {
+ return;
+ }
+ while (true)
+ {
+ bool didMerge = false;
+ typename Node::ChildMap merged;
+ for (const typename Node::ChildMap::value_type& kv : node.children)
+ {
+ Node& child = nodes[kv.second];
+ if (child.isSimpleNode())
+ {
+ for (const typename Node::ChildMap::value_type& childKv :
+ child.children)
+ {
+ merged[kv.first + childKv.first] = childKv.second;
+ didMerge = true;
+ }
+ }
+ else
+ {
+ merged[kv.first] = kv.second;
+ }
+ }
+ node.children = std::move(merged);
+ if (!didMerge)
+ {
+ break;
+ }
+ }
+
+ for (const typename Node::ChildMap::value_type& kv : node.children)
+ {
+ optimizeNode(nodes[kv.second]);
+ }
+ }
+
+ void optimize()
+ {
+ optimizeNode(head());
+ }
+
+ public:
+ void validate()
+ {
+ optimize();
+ }
+
+ void findRouteIndexesHelper(std::string_view reqUrl,
+ std::vector<unsigned>& routeIndexes,
+ const Node& node) const
+ {
+ for (const typename Node::ChildMap::value_type& kv : node.children)
+ {
+ const std::string& fragment = kv.first;
+ const Node& child = nodes[kv.second];
+ if (reqUrl.empty())
+ {
+ if (child.ruleIndex != 0 && fragment != "/")
+ {
+ routeIndexes.push_back(child.ruleIndex);
+ }
+ findRouteIndexesHelper(reqUrl, routeIndexes, child);
+ }
+ else
+ {
+ if (reqUrl.starts_with(fragment))
+ {
+ findRouteIndexesHelper(reqUrl.substr(fragment.size()),
+ routeIndexes, child);
+ }
+ }
+ }
+ }
+
+ void findRouteIndexes(const std::string& reqUrl,
+ std::vector<unsigned>& routeIndexes) const
+ {
+ findRouteIndexesHelper(reqUrl, routeIndexes, head());
+ }
+
+ struct FindResult
+ {
+ unsigned ruleIndex = 0;
+ std::vector<std::string> params;
+ };
+
+ private:
+ FindResult findHelper(const std::string_view reqUrl, const Node& node,
+ std::vector<std::string>& params) const
+ {
+ if (reqUrl.empty())
+ {
+ return {node.ruleIndex, params};
+ }
+
+ if (node.stringParamChild != 0U)
+ {
+ size_t epos = 0;
+ for (; epos < reqUrl.size(); epos++)
+ {
+ if (reqUrl[epos] == '/')
+ {
+ break;
+ }
+ }
+
+ if (epos != 0)
+ {
+ params.emplace_back(reqUrl.substr(0, epos));
+ FindResult ret = findHelper(
+ reqUrl.substr(epos), nodes[node.stringParamChild], params);
+ if (ret.ruleIndex != 0U)
+ {
+ return {ret.ruleIndex, std::move(ret.params)};
+ }
+ params.pop_back();
+ }
+ }
+
+ if (node.pathParamChild != 0U)
+ {
+ params.emplace_back(reqUrl);
+ FindResult ret = findHelper("", nodes[node.pathParamChild], params);
+ if (ret.ruleIndex != 0U)
+ {
+ return {ret.ruleIndex, std::move(ret.params)};
+ }
+ params.pop_back();
+ }
+
+ for (const typename Node::ChildMap::value_type& kv : node.children)
+ {
+ const std::string& fragment = kv.first;
+ const Node& child = nodes[kv.second];
+
+ if (reqUrl.starts_with(fragment))
+ {
+ FindResult ret =
+ findHelper(reqUrl.substr(fragment.size()), child, params);
+ if (ret.ruleIndex != 0U)
+ {
+ return {ret.ruleIndex, std::move(ret.params)};
+ }
+ }
+ }
+
+ return {0U, std::vector<std::string>()};
+ }
+
+ public:
+ FindResult find(const std::string_view reqUrl) const
+ {
+ std::vector<std::string> start;
+ return findHelper(reqUrl, head(), start);
+ }
+
+ void add(std::string_view urlIn, unsigned ruleIndex)
+ {
+ size_t idx = 0;
+
+ std::string_view url = urlIn;
+
+ while (!url.empty())
+ {
+ char c = url[0];
+ if (c == '<')
+ {
+ bool found = false;
+ for (const std::string_view str1 :
+ {"<str>", "<string>", "<path>"})
+ {
+ if (!url.starts_with(str1))
+ {
+ continue;
+ }
+ found = true;
+ Node& node = nodes[idx];
+ size_t* param = &node.stringParamChild;
+ if (str1 == "<path>")
+ {
+ param = &node.pathParamChild;
+ }
+ if (*param == 0U)
+ {
+ *param = newNode();
+ }
+ idx = *param;
+
+ url.remove_prefix(str1.size());
+ break;
+ }
+ if (found)
+ {
+ continue;
+ }
+
+ BMCWEB_LOG_CRITICAL("Can't find tag for {}", urlIn);
+ return;
+ }
+ std::string piece(&c, 1);
+ if (!nodes[idx].children.contains(piece))
+ {
+ unsigned newNodeIdx = newNode();
+ nodes[idx].children.emplace(piece, newNodeIdx);
+ }
+ idx = nodes[idx].children[piece];
+ url.remove_prefix(1);
+ }
+ Node& node = nodes[idx];
+ if (node.ruleIndex != 0U)
+ {
+ BMCWEB_LOG_CRITICAL("handler already exists for \"{}\"", urlIn);
+ throw std::runtime_error(
+ std::format("handler already exists for \"{}\"", urlIn));
+ }
+ node.ruleIndex = ruleIndex;
+ }
+
+ private:
+ void debugNodePrint(Node& n, size_t level)
+ {
+ std::string spaces(level, ' ');
+ if (n.stringParamChild != 0U)
+ {
+ BMCWEB_LOG_DEBUG("{}<str>", spaces);
+ debugNodePrint(nodes[n.stringParamChild], level + 5);
+ }
+ if (n.pathParamChild != 0U)
+ {
+ BMCWEB_LOG_DEBUG("{} <path>", spaces);
+ debugNodePrint(nodes[n.pathParamChild], level + 6);
+ }
+ for (const typename Node::ChildMap::value_type& kv : n.children)
+ {
+ BMCWEB_LOG_DEBUG("{}{}", spaces, kv.first);
+ debugNodePrint(nodes[kv.second], level + kv.first.size());
+ }
+ }
+
+ public:
+ void debugPrint()
+ {
+ debugNodePrint(head(), 0U);
+ }
+
+ private:
+ const Node& head() const
+ {
+ return nodes.front();
+ }
+
+ Node& head()
+ {
+ return nodes.front();
+ }
+
+ unsigned newNode()
+ {
+ nodes.resize(nodes.size() + 1);
+ return static_cast<unsigned>(nodes.size() - 1);
+ }
+
+ std::vector<Node> nodes{};
+};
+} // namespace crow