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.hpp b/http/routing.hpp
index 7d1432a..eef1d2c 100644
--- a/http/routing.hpp
+++ b/http/routing.hpp
@@ -10,12 +10,11 @@
#include "routing/baserule.hpp"
#include "routing/dynamicrule.hpp"
#include "routing/taggedrule.hpp"
+#include "routing/trie.hpp"
#include "verb.hpp"
#include <boost/beast/http/field.hpp>
#include <boost/beast/http/status.hpp>
-#include <boost/container/flat_map.hpp>
-#include <boost/container/small_vector.hpp>
#include <algorithm>
#include <array>
@@ -36,311 +35,6 @@
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;
-};
-
class Router
{
public:
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