/src/uWebSockets/src/HttpRouter.h

Source (jump to first uncovered line)
/*
 * Authored by Alex Hultman, 2018-2020.
 * Intellectual property of third-party.

 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at

 *     http://www.apache.org/licenses/LICENSE-2.0

 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef UWS_HTTPROUTER_HPP
#define UWS_HTTPROUTER_HPP

#include <map>
#include <vector>
#include <cstring>
#include <string_view>
#include <string>
#include <algorithm>
#include <memory>
#include <utility>

#include <iostream>

#include "MoveOnlyFunction.h"

namespace uWS {

template <class USERDATA>
struct HttpRouter {
    static constexpr std::string_view ANY_METHOD_TOKEN = "*";
    static const uint32_t HIGH_PRIORITY = 0xd0000000, MEDIUM_PRIORITY = 0xe0000000, LOW_PRIORITY = 0xf0000000;

private:
    USERDATA userData;
    static const unsigned int MAX_URL_SEGMENTS = 100;

    /* Handler ids are 32-bit */
    static const uint32_t HANDLER_MASK = 0x0fffffff;

    /* List of handlers */
    std::vector<MoveOnlyFunction<bool(HttpRouter *)>> handlers;

    /* Current URL cache */
    std::string_view currentUrl;
    std::string_view urlSegmentVector[MAX_URL_SEGMENTS];
    int urlSegmentTop;

    /* The matching tree */
    struct Node {
        std::string name;
        std::vector<std::unique_ptr<Node>> children;
        std::vector<uint32_t> handlers;
        bool isHighPriority;

        Node(std::string name) : name(name) {}
    } root = {"rootNode"};

    /* Sort wildcards after alphanum */
    int lexicalOrder(std::string &name) {
        if (!name.length()) {
            return 2;
        }
        if (name[0] == ':') {
            return 1;
        }
        if (name[0] == '*') {
            return 0;
        }
        return 2;
    }

    /* Advance from parent to child, adding child if necessary */
    Node *getNode(Node *parent, std::string child, bool isHighPriority) {
        for (std::unique_ptr<Node> &node : parent->children) {
            if (node->name == child && node->isHighPriority == isHighPriority) {
                return node.get();
            }
        }

        /* Insert sorted, but keep order if parent is root (we sort methods by priority elsewhere) */
        std::unique_ptr<Node> newNode(new Node(child));
        newNode->isHighPriority = isHighPriority;
        return parent->children.emplace(std::upper_bound(parent->children.begin(), parent->children.end(), newNode, [parent, this](auto &a, auto &b) {

            if (a->isHighPriority != b->isHighPriority) {
                return a->isHighPriority;
            }

            return b->name.length() && (parent != &root) && (lexicalOrder(b->name) < lexicalOrder(a->name));
        }), std::move(newNode))->get();
    }

    /* Basically a pre-allocated stack */
    struct RouteParameters {
        friend struct HttpRouter;
    private:
        std::string_view params[MAX_URL_SEGMENTS];
        int paramsTop;

        void reset() {
            paramsTop = -1;
        }

        void push(std::string_view param) {
            /* We check these bounds indirectly via the urlSegments limit */
            params[++paramsTop] = param;
        }

        void pop() {
            /* Same here, we cannot pop outside */
            paramsTop--;
        }
    } routeParameters;

    /* Set URL for router. Will reset any URL cache */
    inline void setUrl(std::string_view url) {

        /* Todo: URL may also start with "http://domain/" or "*", not only "/" */

        /* We expect to stand on a slash */
        currentUrl = url;
        urlSegmentTop = -1;
    }

    /* Lazily parse or read from cache */
    inline std::pair<std::string_view, bool> getUrlSegment(int urlSegment) {
        if (urlSegment > urlSegmentTop) {
            /* Signal as STOP when we have no more URL or stack space */
            if (!currentUrl.length() || urlSegment > int(MAX_URL_SEGMENTS - 1)) {
                return {{}, true};
            }

            /* We always stand on a slash here, so step over it */
            currentUrl.remove_prefix(1);

            auto segmentLength = currentUrl.find('/');
            if (segmentLength == std::string::npos) {
                segmentLength = currentUrl.length();

                /* Push to url segment vector */
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
                urlSegmentTop++;

                /* Update currentUrl */
                currentUrl = currentUrl.substr(segmentLength);
            } else {
                /* Push to url segment vector */
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
                urlSegmentTop++;

                /* Update currentUrl */
                currentUrl = currentUrl.substr(segmentLength);
            }
        }
        /* In any case we return it */
        return {urlSegmentVector[urlSegment], false};
    }

    /* Executes as many handlers it can */
    bool executeHandlers(Node *parent, int urlSegment, USERDATA &userData) {

        auto [segment, isStop] = getUrlSegment(urlSegment);

        /* If we are on STOP, return where we may stand */
        if (isStop) {
            /* We have reached accross the entire URL with no stoppage, execute */
            for (uint32_t handler : parent->handlers) {
                if (handlers[handler & HANDLER_MASK](this)) {
                    return true;
                }
            }
            /* We reached the end, so go back */
            return false;
        }

        for (auto &p : parent->children) {
            if (p->name.length() && p->name[0] == '*') {
                /* Wildcard match (can be seen as a shortcut) */
                for (uint32_t handler : p->handlers) {
                    if (handlers[handler & HANDLER_MASK](this)) {
                        return true;
                    }
                }
            } else if (p->name.length() && p->name[0] == ':' && segment.length()) {
                /* Parameter match */
                routeParameters.push(segment);
                if (executeHandlers(p.get(), urlSegment + 1, userData)) {
                    return true;
                }
                routeParameters.pop();
            } else if (p->name == segment) {
                /* Static match */
                if (executeHandlers(p.get(), urlSegment + 1, userData)) {
                    return true;
                }
            }
        }
        return false;
    }

    /* Scans for one matching handler, returning the handler and its priority or UINT32_MAX for not found */
    uint32_t findHandler(std::string method, std::string pattern, uint32_t priority) {
        for (std::unique_ptr<Node> &node : root.children) {
            if (method == node->name) {
                setUrl(pattern);
                Node *n = node.get();
                for (int i = 0; !getUrlSegment(i).second; i++) {
                    /* Go to next segment or quit */
                    std::string segment = std::string(getUrlSegment(i).first);
                    Node *next = nullptr;
                    for (std::unique_ptr<Node> &child : n->children) {
                        if (((segment.length() && child->name.length() && segment[0] == ':' && child->name[0] == ':') || child->name == segment) && child->isHighPriority == (priority == HIGH_PRIORITY)) {
                            next = child.get();
                            break;
                        }
                    }
                    if (!next) {
                        return UINT32_MAX;
                    }
                    n = next;
                }
                /* Seek for a priority match in the found node */
                for (unsigned int i = 0; i < n->handlers.size(); i++) {
                    if ((n->handlers[i] & ~HANDLER_MASK) == priority) {
                        return n->handlers[i];
                    }
                }
                return UINT32_MAX;
            }
        }
        return UINT32_MAX;
    }

public:
    HttpRouter() {
        /* Always have ANY route */
        getNode(&root, std::string(ANY_METHOD_TOKEN.data(), ANY_METHOD_TOKEN.length()), false);
    }

    std::pair<int, std::string_view *> getParameters() {
        return {routeParameters.paramsTop, routeParameters.params};
    }

    USERDATA &getUserData() {
        return userData;
    }

    /* Fast path */
    bool route(std::string_view method, std::string_view url) {
        /* Reset url parsing cache */
        setUrl(url);
        routeParameters.reset();

        /* Begin by finding the method node */
        for (auto &p : root.children) {
            if (p->name == method) {
                /* Then route the url */
                if (executeHandlers(p.get(), 0, userData)) {
                    return true;
                } else {
                    break;
                }
            }
        }

        /* Always test any route last (this check should not be necessary if we always have at least one handler) */
        if (root.children.empty()) [[unlikely]] {
            return false;
        }
        return executeHandlers(root.children.back().get(), 0, userData);
    }

    /* Adds the corresponding entires in matching tree and handler list */
    void add(std::vector<std::string> methods, std::string pattern, MoveOnlyFunction<bool(HttpRouter *)> &&handler, uint32_t priority = MEDIUM_PRIORITY) {
        /* First remove existing handler */
        remove(methods[0], pattern, priority);
        
        for (std::string method : methods) {
            /* Lookup method */
            Node *node = getNode(&root, method, false);
            /* Iterate over all segments */
            setUrl(pattern);
            for (int i = 0; !getUrlSegment(i).second; i++) {
                std::string strippedSegment(getUrlSegment(i).first);
                if (strippedSegment.length() && strippedSegment[0] == ':') {
                    /* Parameter routes must be named only : */
                    strippedSegment = ":";
                }
                node = getNode(node, strippedSegment, priority == HIGH_PRIORITY);
            }
            /* Insert handler in order sorted by priority (most significant 1 byte) */
            node->handlers.insert(std::upper_bound(node->handlers.begin(), node->handlers.end(), (uint32_t) (priority | handlers.size())), (uint32_t) (priority | handlers.size()));
        }

        /* Alloate this handler */
        handlers.emplace_back(std::move(handler));

        /* ANY method must be last, GET must be first */
        std::sort(root.children.begin(), root.children.end(), [](const auto &a, const auto &b) {
            if (a->name == "GET" && b->name != "GET") {
                return true;
            } else if (b->name == "GET" && a->name != "GET") {
                return false;
            } else if (a->name == ANY_METHOD_TOKEN && b->name != ANY_METHOD_TOKEN) {
                return false;
            } else if (b->name == ANY_METHOD_TOKEN && a->name != ANY_METHOD_TOKEN) {
                return true;
            } else {
                return a->name < b->name;
            }
        });
    }

    bool cullNode(Node *parent, Node *node, uint32_t handler) {
        /* For all children */
        for (unsigned int i = 0; i < node->children.size(); ) {
            /* Optimization todo: only enter those with same isHighPrioirty */
            /* Enter child so we get depth first */
            if (!cullNode(node, node->children[i].get(), handler)) {
                /* Only increase if this node was not removed */
                i++;
            }
        }

        /* Cull this node (but skip the root node) */
        if (parent /*&& parent != &root*/) {
            /* Scan for equal (remove), greater (lower by 1) */
            for (auto it = node->handlers.begin(); it != node->handlers.end(); ) {
                if ((*it & HANDLER_MASK) > (handler & HANDLER_MASK)) {
                    *it = ((*it & HANDLER_MASK) - 1) | (*it & ~HANDLER_MASK);
                } else if (*it == handler) {
                    it = node->handlers.erase(it);
                    continue;
                }
                it++;
            }

            /* If we have no children and no handlers, remove us from the parent->children list */
            if (!node->handlers.size() && !node->children.size()) {
                parent->children.erase(std::find_if(parent->children.begin(), parent->children.end(), [node](const std::unique_ptr<Node> &a) {
                    return a.get() == node;
                }));
                /* Returning true means we removed node from parent */
                return true;
            }
        }

        return false;
    }

    /* Removes ALL routes with the same handler as can be found with the given parameters.
     * Removing a wildcard is done by removing ONE OF the methods the wildcard would match with.
     * Example: If wildcard includes POST, GET, PUT, you can remove ALL THREE by removing GET. */
    bool remove(std::string method, std::string pattern, uint32_t priority) {
        uint32_t handler = findHandler(method, pattern, priority);
        if (handler == UINT32_MAX) {
            /* Not found or already removed, do nothing */
            return false;
        }

        /* Cull the entire tree */
        /* For all nodes in depth first tree traveral;
         * if node contains handler - remove the handler -
         * if node holds no handlers after removal, remove the node and return */
        cullNode(nullptr, &root, handler);

        /* Now remove the actual handler */
        handlers.erase(handlers.begin() + (handler & HANDLER_MASK));

        return true;
    }
};

}

#endif // UWS_HTTPROUTER_HPP

Coverage Report

Created: 2025-06-13 06:09

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Authored by Alex Hultman, 2018-2020.
3		* Intellectual property of third-party.
4
5		* Licensed under the Apache License, Version 2.0 (the "License");
6		* you may not use this file except in compliance with the License.
7		* You may obtain a copy of the License at
8
9		* http://www.apache.org/licenses/LICENSE-2.0
10
11		* Unless required by applicable law or agreed to in writing, software
12		* distributed under the License is distributed on an "AS IS" BASIS,
13		* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14		* See the License for the specific language governing permissions and
15		* limitations under the License.
16		*/
17
18		#ifndef UWS_HTTPROUTER_HPP
19		#define UWS_HTTPROUTER_HPP
20
21		#include <map>
22		#include <vector>
23		#include <cstring>
24		#include <string_view>
25		#include <string>
26		#include <algorithm>
27		#include <memory>
28		#include <utility>
29
30		#include <iostream>
31
32		#include "MoveOnlyFunction.h"
33
34		namespace uWS {
35
36		template <class USERDATA>
37		struct HttpRouter {
38		static constexpr std::string_view ANY_METHOD_TOKEN = "*";
39		static const uint32_t HIGH_PRIORITY = 0xd0000000, MEDIUM_PRIORITY = 0xe0000000, LOW_PRIORITY = 0xf0000000;
40
41		private:
42		USERDATA userData;
43		static const unsigned int MAX_URL_SEGMENTS = 100;
44
45		/* Handler ids are 32-bit */
46		static const uint32_t HANDLER_MASK = 0x0fffffff;
47
48		/* List of handlers */
49		std::vector<MoveOnlyFunction<bool(HttpRouter *)>> handlers;
50
51		/* Current URL cache */
52		std::string_view currentUrl;
53		std::string_view urlSegmentVector[MAX_URL_SEGMENTS];
54		int urlSegmentTop;
55
56		/* The matching tree */
57		struct Node {
58		std::string name;
59		std::vector<std::unique_ptr<Node>> children;
60		std::vector<uint32_t> handlers;
61		bool isHighPriority;
62
63	22	Node(std::string name) : name(name) {}
64		} root = {"rootNode"};
65
66		/* Sort wildcards after alphanum */
67	12	int lexicalOrder(std::string &name) {
68	12	if (!name.length()) {
69	0	return 2;
70	0	}
71	12	if (name[0] == ':') {
72	4	return 1;
73	4	}
74	8	if (name[0] == '*') {
75	4	return 0;
76	4	}
77	4	return 2;
78	8	}
79
80		/* Advance from parent to child, adding child if necessary */
81	24	Node getNode(Node parent, std::string child, bool isHighPriority) {
82	24	for (std::unique_ptr<Node> &node : parent->children) {
83	16	if (node->name == child && node->isHighPriority == isHighPriority) {
84	4	return node.get();
85	4	}
86	16	}
87
88		/* Insert sorted, but keep order if parent is root (we sort methods by priority elsewhere) */
89	20	std::unique_ptr<Node> newNode(new Node(child));
90	20	newNode->isHighPriority = isHighPriority;
91	20	return parent->children.emplace(std::upper_bound(parent->children.begin(), parent->children.end(), newNode, [parent, this](auto &a, auto &b) {
92
93	10	if (a->isHighPriority != b->isHighPriority) {
94	0	return a->isHighPriority;
95	0	}
96
97	10	return b->name.length() && (parent != &root) && (lexicalOrder(b->name) < lexicalOrder(a->name));
98	10	}), std::move(newNode))->get();
99	24	}
100
101		/* Basically a pre-allocated stack */
102		struct RouteParameters {
103		friend struct HttpRouter;
104		private:
105		std::string_view params[MAX_URL_SEGMENTS];
106		int paramsTop;
107
108	11.8k	void reset() {
109	11.8k	paramsTop = -1;
110	11.8k	}
111
112	8.32k	void push(std::string_view param) {
113		/* We check these bounds indirectly via the urlSegments limit */
114	8.32k	params[++paramsTop] = param;
115	8.32k	}
116
117	106	void pop() {
118		/* Same here, we cannot pop outside */
119	106	paramsTop--;
120	106	}
121		} routeParameters;
122
123		/* Set URL for router. Will reset any URL cache */
124	11.8k	inline void setUrl(std::string_view url) {
125
126		/* Todo: URL may also start with "http://domain/" or "", not only "/" /
127
128		/* We expect to stand on a slash */
129	11.8k	currentUrl = url;
130	11.8k	urlSegmentTop = -1;
131	11.8k	}
132
133		/* Lazily parse or read from cache */
134	28.0k	inline std::pair<std::string_view, bool> getUrlSegment(int urlSegment) {
135	28.0k	if (urlSegment > urlSegmentTop) {
136		/* Signal as STOP when we have no more URL or stack space */
137	27.1k	if (!currentUrl.length() \|\| urlSegment > int(MAX_URL_SEGMENTS - 1)) {
138	9.92k	return {{}, true};
139	9.92k	}
140
141		/* We always stand on a slash here, so step over it */
142	17.2k	currentUrl.remove_prefix(1);
143
144	17.2k	auto segmentLength = currentUrl.find('/');
145	17.2k	if (segmentLength == std::string::npos) {
146	11.7k	segmentLength = currentUrl.length();
147
148		/* Push to url segment vector */
149	11.7k	urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
150	11.7k	urlSegmentTop++;
151
152		/* Update currentUrl */
153	11.7k	currentUrl = currentUrl.substr(segmentLength);
154	11.7k	} else {
155		/* Push to url segment vector */
156	5.50k	urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
157	5.50k	urlSegmentTop++;
158
159		/* Update currentUrl */
160	5.50k	currentUrl = currentUrl.substr(segmentLength);
161	5.50k	}
162	17.2k	}
163		/* In any case we return it */
164	18.1k	return {urlSegmentVector[urlSegment], false};
165	28.0k	}
166
167		/* Executes as many handlers it can */
168	28.0k	bool executeHandlers(Node *parent, int urlSegment, USERDATA &userData) {
169
170	28.0k	auto [segment, isStop] = getUrlSegment(urlSegment);
171
172		/* If we are on STOP, return where we may stand */
173	28.0k	if (isStop) {
174		/* We have reached accross the entire URL with no stoppage, execute */
175	9.91k	for (uint32_t handler : parent->handlers) {
176	9.84k	if (handlers[handler & HANDLER_MASK](this)) {
177	9.84k	return true;
178	9.84k	}
179	9.84k	}
180		/* We reached the end, so go back */
181	72	return false;
182	9.91k	}
183
184	19.6k	for (auto &p : parent->children) {
185	19.6k	if (p->name.length() && p->name[0] == '*') {
186		/* Wildcard match (can be seen as a shortcut) */
187	1.35k	for (uint32_t handler : p->handlers) {
188	1.35k	if (handlers[handler & HANDLER_MASK](this)) {
189	1.23k	return true;
190	1.23k	}
191	1.35k	}
192	18.3k	} else if (p->name.length() && p->name[0] == ':' && segment.length()) {
193		/* Parameter match */
194	8.32k	routeParameters.push(segment);
195	8.32k	if (executeHandlers(p.get(), urlSegment + 1, userData)) {
196	8.21k	return true;
197	8.21k	}
198	106	routeParameters.pop();
199	10.0k	} else if (p->name == segment) {
200		/* Static match */
201	7.74k	if (executeHandlers(p.get(), urlSegment + 1, userData)) {
202	6.97k	return true;
203	6.97k	}
204	7.74k	}
205	19.6k	}
206	1.69k	return false;
207	18.1k	}
208
209		/* Scans for one matching handler, returning the handler and its priority or UINT32_MAX for not found */
210	8	uint32_t findHandler(std::string method, std::string pattern, uint32_t priority) {
211	10	for (std::unique_ptr<Node> &node : root.children) {
212	10	if (method == node->name) {
213	4	setUrl(pattern);
214	4	Node *n = node.get();
215	4	for (int i = 0; !getUrlSegment(i).second; i++) {
216		/* Go to next segment or quit */
217	4	std::string segment = std::string(getUrlSegment(i).first);
218	4	Node *next = nullptr;
219	6	for (std::unique_ptr<Node> &child : n->children) {
220	6	if (((segment.length() && child->name.length() && segment[0] == ':' && child->name[0] == ':') \|\| child->name == segment) && child->isHighPriority == (priority == HIGH_PRIORITY)) {
221	0	next = child.get();
222	0	break;
223	0	}
224	6	}
225	4	if (!next) {
226	4	return UINT32_MAX;
227	4	}
228	0	n = next;
229	0	}
230		/* Seek for a priority match in the found node */
231	0	for (unsigned int i = 0; i < n->handlers.size(); i++) {
232	0	if ((n->handlers[i] & ~HANDLER_MASK) == priority) {
233	0	return n->handlers[i];
234	0	}
235	0	}
236	0	return UINT32_MAX;
237	0	}
238	10	}
239	4	return UINT32_MAX;
240	8	}
241
242		public:
243	2	HttpRouter() {
244		/* Always have ANY route */
245	2	getNode(&root, std::string(ANY_METHOD_TOKEN.data(), ANY_METHOD_TOKEN.length()), false);
246	2	}
247
248	11.2k	std::pair<int, std::string_view *> getParameters() {
249	11.2k	return {routeParameters.paramsTop, routeParameters.params};
250	11.2k	}
251
252	11.8k	USERDATA &getUserData() {
253	11.8k	return userData;
254	11.8k	}
255
256		/* Fast path */
257	11.8k	bool route(std::string_view method, std::string_view url) {
258		/* Reset url parsing cache */
259	11.8k	setUrl(url);
260	11.8k	routeParameters.reset();
261
262		/* Begin by finding the method node */
263	14.3k	for (auto &p : root.children) {
264	14.3k	if (p->name == method) {
265		/* Then route the url */
266	11.2k	if (executeHandlers(p.get(), 0, userData)) {
267	11.0k	return true;
268	11.0k	} else {
269	127	break;
270	127	}
271	11.2k	}
272	14.3k	}
273
274		/* Always test any route last (this check should not be necessary if we always have at least one handler) */
275	764	if (root.children.empty()) [[unlikely]] {
276	0	return false;
277	0	}
278	764	return executeHandlers(root.children.back().get(), 0, userData);
279	764	}
280
281		/* Adds the corresponding entires in matching tree and handler list */
282	8	void add(std::vector<std::string> methods, std::string pattern, MoveOnlyFunction<bool(HttpRouter *)> &&handler, uint32_t priority = MEDIUM_PRIORITY) {
283		/* First remove existing handler */
284	8	remove(methods[0], pattern, priority);
285
286	8	for (std::string method : methods) {
287		/* Lookup method */
288	8	Node *node = getNode(&root, method, false);
289		/* Iterate over all segments */
290	8	setUrl(pattern);
291	22	for (int i = 0; !getUrlSegment(i).second; i++) {
292	14	std::string strippedSegment(getUrlSegment(i).first);
293	14	if (strippedSegment.length() && strippedSegment[0] == ':') {
294		/* Parameter routes must be named only : */
295	8	strippedSegment = ":";
296	8	}
297	14	node = getNode(node, strippedSegment, priority == HIGH_PRIORITY);
298	14	}
299		/* Insert handler in order sorted by priority (most significant 1 byte) */
300	8	node->handlers.insert(std::upper_bound(node->handlers.begin(), node->handlers.end(), (uint32_t) (priority \| handlers.size())), (uint32_t) (priority \| handlers.size()));
301	8	}
302
303		/* Alloate this handler */
304	8	handlers.emplace_back(std::move(handler));
305
306		/* ANY method must be last, GET must be first */
307	16	std::sort(root.children.begin(), root.children.end(), [](const auto &a, const auto &b) {
308	16	if (a->name == "GET" && b->name != "GET") {
309	0	return true;
310	16	} else if (b->name == "GET" && a->name != "GET") {
311	0	return false;
312	16	} else if (a->name == ANY_METHOD_TOKEN && b->name != ANY_METHOD_TOKEN) {
313	6	return false;
314	10	} else if (b->name == ANY_METHOD_TOKEN && a->name != ANY_METHOD_TOKEN) {
315	4	return true;
316	6	} else {
317	6	return a->name < b->name;
318	6	}
319	16	});
320	8	}
321
322	0	bool cullNode(Node parent, Node node, uint32_t handler) {
323		/* For all children */
324	0	for (unsigned int i = 0; i < node->children.size(); ) {
325		/* Optimization todo: only enter those with same isHighPrioirty */
326		/* Enter child so we get depth first */
327	0	if (!cullNode(node, node->children[i].get(), handler)) {
328		/* Only increase if this node was not removed */
329	0	i++;
330	0	}
331	0	}
332
333		/* Cull this node (but skip the root node) */
334	0	if (parent /&& parent != &root/) {
335		/* Scan for equal (remove), greater (lower by 1) */
336	0	for (auto it = node->handlers.begin(); it != node->handlers.end(); ) {
337	0	if ((*it & HANDLER_MASK) > (handler & HANDLER_MASK)) {
338	0	it = ((it & HANDLER_MASK) - 1) \| (*it & ~HANDLER_MASK);
339	0	} else if (*it == handler) {
340	0	it = node->handlers.erase(it);
341	0	continue;
342	0	}
343	0	it++;
344	0	}
345
346		/* If we have no children and no handlers, remove us from the parent->children list */
347	0	if (!node->handlers.size() && !node->children.size()) {
348	0	parent->children.erase(std::find_if(parent->children.begin(), parent->children.end(), [node](const std::unique_ptr<Node> &a) {
349	0	return a.get() == node;
350	0	}));
351		/* Returning true means we removed node from parent */
352	0	return true;
353	0	}
354	0	}
355
356	0	return false;
357	0	}
358
359		/* Removes ALL routes with the same handler as can be found with the given parameters.
360		* Removing a wildcard is done by removing ONE OF the methods the wildcard would match with.
361		* Example: If wildcard includes POST, GET, PUT, you can remove ALL THREE by removing GET. */
362	8	bool remove(std::string method, std::string pattern, uint32_t priority) {
363	8	uint32_t handler = findHandler(method, pattern, priority);
364	8	if (handler == UINT32_MAX) {
365		/* Not found or already removed, do nothing */
366	8	return false;
367	8	}
368
369		/* Cull the entire tree */
370		/* For all nodes in depth first tree traveral;
371		* if node contains handler - remove the handler -
372		* if node holds no handlers after removal, remove the node and return */
373	0	cullNode(nullptr, &root, handler);
374
375		/* Now remove the actual handler */
376	0	handlers.erase(handlers.begin() + (handler & HANDLER_MASK));
377
378	0	return true;
379	8	}
380		};
381
382		}
383
384		#endif // UWS_HTTPROUTER_HPP