Trie based routing

5 files changed, 124 insertions, 22 deletions

diff --git a/Makefile b/Makefile
index d69a960..012b488 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 all: example
 # unittest
 example: example.cpp flask.h http_server.h http_connection.h parser.h http_response.h routing.h
-	g++ -g -std=c++1y -o example example.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/
+	g++ -Wall -g -std=c++1y -o example example.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/
 test: example
 	pkill example || exit 0
 	./example &
diff --git a/http_connection.h b/http_connection.h
index d5ee1c9..2f245ba 100644
--- a/http_connection.h
+++ b/http_connection.h
@@ -69,11 +69,22 @@ namespace flask
                     if (!ec)
                     {
                         bool ret = parser_.feed(buffer_.data(), bytes_transferred);
-                        do_read();
+						if (ret)
+							do_read();
+						else
+						{
+							socket_.close();
+
+							life_--;
+							if ((int)life_ == 0)
+							{
+								delete this;
+							}
+						}
                     }
                     else
                     {
-                        bool ret = parser_.done();
+                        parser_.done();
                         socket_.close();
 
                         life_--;
diff --git a/http_response.h b/http_response.h
index 4f19848..eb7926f 100644
--- a/http_response.h
+++ b/http_response.h
@@ -28,11 +28,11 @@ namespace flask
 
     struct response
     {
-        int status = 200;
         std::string body;
+        int status = 200;
         std::unordered_map<std::string, std::string> headers;
         response() {}
-        response(int status) : status(status) {}
+        explicit response(int status) : status(status) {}
         response(std::string body) : body(std::move(body)) {}
         response(std::string body, int status) : body(std::move(body)), status(status) {}
     };
diff --git a/parser.h b/parser.h
index af1d6c3..642e735 100644
--- a/parser.h
+++ b/parser.h
@@ -83,7 +83,6 @@ namespace flask
             return 0;
         }
         HTTPParser(Handler* handler) :
-            handler_(handler),
             settings_ {
                 on_message_begin,
                 on_url,
@@ -93,7 +92,8 @@ namespace flask
                 on_headers_complete,
                 on_body,
                 on_message_complete,
-            }
+            },
+            handler_(handler)
         {
             http_parser_init(this, HTTP_REQUEST);
         }
diff --git a/routing.h b/routing.h
index fe16288..79e35fd 100644
--- a/routing.h
+++ b/routing.h
@@ -4,15 +4,19 @@
 #include <utility>
 #include <string>
 #include <tuple>
+#include <unordered_map>
 
 #include "http_response.h"
 
+//TEST
+#include <iostream>
+
 namespace flask
 {
     class Rule
     {
     public:
-        explicit Rule(std::string&& rule)
+        explicit Rule(std::string rule)
             : rule_(std::move(rule))
         {
         }
@@ -26,7 +30,7 @@ namespace flask
         }
 
         template <typename Func>
-        void operator()(std::string&& name, Func&& f)
+        void operator()(std::string name, Func&& f)
         {
             name_ = std::move(name);
             handler_ = [f = std::move(f)]{
@@ -40,16 +44,17 @@ namespace flask
             return req.url == rule_;
         }
 
-        Rule& name(const std::string& name)
+        Rule& name(std::string name)
         {
-            name_ = name;
+            name_ = std::move(name);
             return *this;
         }
+
         void validate()
         {
             if (!handler_)
             {
-                throw std::runtime_error("no handler for url " + rule_);
+                throw std::runtime_error(name_ + (!name_.empty() ? ": " : "") + "no handler for url " + rule_);
             }
         }
 
@@ -64,17 +69,101 @@ namespace flask
         std::function<response()> handler_;
     };
 
+    constexpr const size_t INVALID_RULE_INDEX{static_cast<size_t>(-1)};
+    class Trie
+    {
+    public:
+        struct Node
+        {
+            std::unordered_map<std::string, size_t> children;
+            size_t rule_index{INVALID_RULE_INDEX};
+        };
+
+        Trie() : nodes_(1)
+        {
+        }
+
+        void optimize()
+        {
+        }
+
+        size_t find(const request& req, const Node* node = nullptr, size_t pos = 0) const
+        {
+            size_t found = INVALID_RULE_INDEX;
+
+            if (node == nullptr)
+                node = head();
+            if (pos == req.url.size())
+                return node->rule_index;
+
+            for(auto& kv : node->children)
+            {
+                const std::string& fragment = kv.first;
+                const Node* child = &nodes_[kv.second];
+
+                if (req.url.compare(pos, fragment.size(), fragment) == 0)
+                {
+                    size_t ret = find(req, child, pos + fragment.size());
+                    if (ret != INVALID_RULE_INDEX && (found == INVALID_RULE_INDEX || found > ret))
+                    {
+                        found = ret;
+                    }
+                }
+            }
+
+            return found;
+        }
+
+        void add(const std::string& url, size_t rule_index)
+        {
+            size_t idx = 0;
+            for(char c:url)
+            {
+                std::string piece(&c, 1);
+                //std::string piece("/");
+                if (!nodes_[idx].children.count(piece))
+                {
+                    nodes_[idx].children.emplace(piece, new_node());
+                }
+                idx = nodes_[idx].children[piece];
+            }
+            if (nodes_[idx].rule_index != INVALID_RULE_INDEX)
+                throw std::runtime_error("handler already exists for " + url);
+            nodes_[idx].rule_index = rule_index;
+        }
+    private:
+        const Node* head() const
+        {
+            return &nodes_.front();
+        }
+
+        Node* head()
+        {
+            return &nodes_.front();
+        }
+
+        size_t new_node()
+        {
+            nodes_.resize(nodes_.size()+1);
+            return nodes_.size() - 1;
+        }
+
+        std::vector<Node> nodes_;
+    };
+
     class Router
     {
     public:
-        Rule& new_rule(std::string&& rule)
+        Rule& new_rule(const std::string& rule)
         {
-            rules_.emplace_back(std::move(rule));
+            rules_.emplace_back(rule);
+            trie_.add(rule, rules_.size() - 1);
             return rules_.back();
         }
 
         void validate()
         {
+            trie_.optimize();
             for(auto& rule:rules_)
             {
                 rule.validate();
@@ -83,16 +172,18 @@ namespace flask
 
         response handle(const request& req)
         {
-            for(auto& rule : rules_)
-            {
-                if (rule.match(req))
-                {
-                    return rule.handle(req);
-                }
-            }
-            return response(404);
+            size_t rule_index = trie_.find(req);
+
+            if (rule_index == INVALID_RULE_INDEX)
+                return response(404);
+
+            if (rule_index >= rules_.size())
+                throw std::runtime_error("Trie internal structure corrupted!");
+
+            return rules_[rule_index].handle(req);
         }
     private:
         std::vector<Rule> rules_;
+        Trie trie_;
     };
 }