Lines Matching refs:node
44 RNode *find_next_node(const RNode *node, char c) {
45 auto itr = std::lower_bound(std::begin(node->next), std::end(node->next), c,
48 if (itr == std::end(node->next) || (*itr)->s[0] != c) {
57 void add_next_node(RNode *node, std::unique_ptr<RNode> new_node) {
58 auto itr = std::lower_bound(std::begin(node->next), std::end(node->next),
62 node->next.insert(itr, std::move(new_node));
66 void Router::add_node(RNode *node, const char *pattern, size_t patlen,
71 add_next_node(node, std::move(new_node));
82 auto node = &root_;
86 auto next_node = find_next_node(node, pattern[i]);
88 add_node(node, pattern.c_str() + i, pattern.size() - i, index,
93 node = next_node;
97 auto n = std::min(node->len, slen);
99 for (j = 0; j < n && node->s[j] == s[j]; ++j)
103 if (slen == node->len) {
106 if (node->index != -1) {
108 return node->index;
110 node->index = index;
116 if (node->wildcard_index != -1) {
117 return node->wildcard_index;
119 node->wildcard_index = wildcard_index;
123 if (slen > node->len) {
131 if (node->len > j) {
132 // node must be split into 2 nodes. new_node is now the child
133 // of node.
135 &node->s[j], node->len - j, node->index, node->wildcard_index);
136 std::swap(node->next, new_node->next);
138 node->len = j;
139 node->index = -1;
140 node->wildcard_index = -1;
142 add_next_node(node, std::move(new_node));
145 node->index = index;
146 node->wildcard_index = wildcard_index;
154 add_node(node, pattern.c_str() + i, pattern.size() - i, index,
162 const RNode *match_complete(size_t *offset, const RNode *node,
167 return node;
173 auto next_node = find_next_node(node, *p);
178 node = next_node;
180 auto n = std::min(node->len, static_cast<size_t>(last - p));
181 if (memcmp(node->s, p, n) != 0) {
187 return node;
194 const RNode *match_partial(bool *pattern_is_wildcard, const RNode *node,
199 if (node->len == offset) {
200 return node;
210 auto n = std::min(node->len - offset, static_cast<size_t>(last - first));
211 if (memcmp(node->s + offset, first, n) != 0) {
218 if (node->len == offset + n) {
219 if (node->index != -1) {
220 return node;
224 node = find_next_node(node, '/');
225 if (node != nullptr && node->index != -1 && node->len == 1) {
226 return node;
233 if (node->index != -1 && offset + n + 1 == node->len &&
234 node->s[node->len - 1] == '/') {
235 return node;
241 if (node->wildcard_index != -1) {
242 found_node = node;
244 } else if (node->index != -1 && node->s[node->len - 1] == '/') {
245 found_node = node;
249 assert(node->len == offset + n);
253 auto next_node = find_next_node(node, *p);
258 node = next_node;
260 auto n = std::min(node->len, static_cast<size_t>(last - p));
261 if (memcmp(node->s, p, n) != 0) {
268 if (node->len == n) {
269 // Complete match with this node
270 if (node->index != -1) {
272 return node;
276 node = find_next_node(node, '/');
277 if (node != nullptr && node->index != -1 && node->len == 1) {
279 return node;
291 if (node->index != -1 && n + 1 == node->len && node->s[n] == '/') {
293 return node;
299 if (node->wildcard_index != -1) {
300 found_node = node;
302 } else if (node->index != -1 && node->s[node->len - 1] == '/') {
305 found_node = node;
309 assert(node->len == n);
315 const RNode *node;
318 node = match_complete(&offset, &root_, std::begin(host), std::end(host));
319 if (node == nullptr) {
324 node = match_partial(&pattern_is_wildcard, node, offset, std::begin(path),
326 if (node == nullptr || node == &root_) {
330 return pattern_is_wildcard ? node->wildcard_index : node->index;
334 const RNode *node;
337 node = match_complete(&offset, &root_, std::begin(s), std::end(s));
338 if (node == nullptr) {
342 if (node->len != offset) {
346 return node->index;
350 const RNode *match_prefix(size_t *nread, const RNode *node, const char *first,
359 auto next_node = find_next_node(node, *p);
364 node = next_node;
366 auto n = std::min(node->len, static_cast<size_t>(last - p));
367 if (memcmp(node->s, p, n) != 0) {
374 if (node->index != -1) {
376 return node;
381 if (node->len == n) {
383 return node;
397 auto node =
399 if (node == nullptr) {
403 *last_node = node;
405 return node->index;
409 void dump_node(const RNode *node, int depth) {
411 (int)node->len, node->s, node->len, node->index);
412 for (auto &nd : node->next) {