1 /* 2 * nghttp2 - HTTP/2 C Library 3 * 4 * Copyright (c) 2015 Tatsuhiro Tsujikawa 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining 7 * a copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sublicense, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 */ 25 #ifndef SHRPX_ROUTER_H 26 #define SHRPX_ROUTER_H 27 28 #include "shrpx.h" 29 30 #include <vector> 31 #include <memory> 32 33 #include "allocator.h" 34 35 using namespace nghttp2; 36 37 namespace shrpx { 38 39 struct RNode { 40 RNode(); 41 RNode(const char *s, size_t len, ssize_t index, ssize_t wildcard_index); 42 RNode(RNode &&) = default; 43 RNode(const RNode &) = delete; 44 RNode &operator=(RNode &&) = default; 45 RNode &operator=(const RNode &) = delete; 46 47 // Next RNode, sorted by s[0]. 48 std::vector<std::unique_ptr<RNode>> next; 49 // Stores pointer to the string this node represents. Not 50 // NULL-terminated. 51 const char *s; 52 // Length of |s| 53 size_t len; 54 // Index of pattern if match ends in this node. Note that we don't 55 // store duplicated pattern. 56 ssize_t index; 57 // Index of wildcard pattern if query includes this node as prefix 58 // and it still has suffix to match. Note that we don't store 59 // duplicated pattern. 60 ssize_t wildcard_index; 61 }; 62 63 class Router { 64 public: 65 Router(); 66 ~Router(); 67 Router(Router &&) = default; 68 Router(const Router &) = delete; 69 Router &operator=(Router &&) = default; 70 Router &operator=(const Router &) = delete; 71 72 // Adds route |pattern| with its |index|. If same pattern has 73 // already been added, the existing index is returned. If 74 // |wildcard| is true, |pattern| is considered as wildcard pattern, 75 // and all paths which have the |pattern| as prefix and are strictly 76 // longer than |pattern| match. The wildcard pattern only works 77 // with match(const StringRef&, const StringRef&). 78 size_t add_route(const StringRef &pattern, size_t index, 79 bool wildcard = false); 80 // Returns the matched index of pattern. -1 if there is no match. 81 ssize_t match(const StringRef &host, const StringRef &path) const; 82 // Returns the matched index of pattern |s|. -1 if there is no 83 // match. 84 ssize_t match(const StringRef &s) const; 85 // Returns the matched index of pattern if a pattern is a suffix of 86 // |s|, otherwise -1. If |*last_node| is not nullptr, it specifies 87 // the first node to start matching. If it is nullptr, match will 88 // start from scratch. When the match was found (the return value 89 // is not -1), |*nread| has the number of bytes matched in |s|, and 90 // |*last_node| has the last matched node. One can continue to 91 // match the longer pattern using the returned |*last_node| to the 92 // another invocation of this function until it returns -1. 93 ssize_t match_prefix(size_t *nread, const RNode **last_node, 94 const StringRef &s) const; 95 96 void add_node(RNode *node, const char *pattern, size_t patlen, ssize_t index, 97 ssize_t wildcard_index); 98 99 void dump() const; 100 101 private: 102 BlockAllocator balloc_; 103 // The root node of Patricia tree. This is special node and its s 104 // field is nulptr, and len field is 0. 105 RNode root_; 106 }; 107 108 } // namespace shrpx 109 110 #endif // SHRPX_ROUTER_H 111