/src/httpd/srclib/apr/strmatch/apr_strmatch.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* Licensed to the Apache Software Foundation (ASF) under one or more |
2 | | * contributor license agreements. See the NOTICE file distributed with |
3 | | * this work for additional information regarding copyright ownership. |
4 | | * The ASF licenses this file to You under the Apache License, Version 2.0 |
5 | | * (the "License"); you may not use this file except in compliance with |
6 | | * the License. You may obtain a copy of the License at |
7 | | * |
8 | | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | | * |
10 | | * Unless required by applicable law or agreed to in writing, software |
11 | | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | | * See the License for the specific language governing permissions and |
14 | | * limitations under the License. |
15 | | */ |
16 | | |
17 | | #include "apr_strmatch.h" |
18 | | #include "apr_lib.h" |
19 | | #define APR_WANT_STRFUNC |
20 | | #include "apr_want.h" |
21 | | |
22 | | |
23 | 224k | #define NUM_CHARS 256 |
24 | | |
25 | | /* |
26 | | * String searching functions |
27 | | */ |
28 | | static const char *match_no_op(const apr_strmatch_pattern *this_pattern, |
29 | | const char *s, apr_size_t slen) |
30 | 0 | { |
31 | 0 | return s; |
32 | 0 | } |
33 | | |
34 | | static const char *match_boyer_moore_horspool( |
35 | | const apr_strmatch_pattern *this_pattern, |
36 | | const char *s, apr_size_t slen) |
37 | 453 | { |
38 | 453 | const char *s_end = s + slen; |
39 | 453 | apr_size_t *shift = (apr_size_t *)(this_pattern->context); |
40 | 453 | const char *s_next = s + this_pattern->length - 1; |
41 | 453 | const char *p_start = this_pattern->pattern; |
42 | 453 | const char *p_end = p_start + this_pattern->length - 1; |
43 | 2.59k | while (s_next < s_end) { |
44 | 2.30k | const char *s_tmp = s_next; |
45 | 2.30k | const char *p_tmp = p_end; |
46 | 5.68k | while (*s_tmp == *p_tmp) { |
47 | 3.54k | p_tmp--; |
48 | 3.54k | if (p_tmp < p_start) { |
49 | 170 | return s_tmp; |
50 | 170 | } |
51 | 3.37k | s_tmp--; |
52 | 3.37k | } |
53 | 2.13k | s_next += shift[(int)*((const unsigned char *)s_next)]; |
54 | 2.13k | } |
55 | 283 | return NULL; |
56 | 453 | } |
57 | | |
58 | | static const char *match_boyer_moore_horspool_nocase( |
59 | | const apr_strmatch_pattern *this_pattern, |
60 | | const char *s, apr_size_t slen) |
61 | 0 | { |
62 | 0 | const char *s_end = s + slen; |
63 | 0 | apr_size_t *shift = (apr_size_t *)(this_pattern->context); |
64 | 0 | const char *s_next = s + this_pattern->length - 1; |
65 | 0 | const char *p_start = this_pattern->pattern; |
66 | 0 | const char *p_end = p_start + this_pattern->length - 1; |
67 | 0 | while (s_next < s_end) { |
68 | 0 | const char *s_tmp = s_next; |
69 | 0 | const char *p_tmp = p_end; |
70 | 0 | while (apr_tolower(*s_tmp) == apr_tolower(*p_tmp)) { |
71 | 0 | p_tmp--; |
72 | 0 | if (p_tmp < p_start) { |
73 | 0 | return s_tmp; |
74 | 0 | } |
75 | 0 | s_tmp--; |
76 | 0 | } |
77 | 0 | s_next += shift[(unsigned char)apr_tolower(*s_next)]; |
78 | 0 | } |
79 | 0 | return NULL; |
80 | 0 | } |
81 | | |
82 | | APR_DECLARE(const apr_strmatch_pattern *) apr_strmatch_precompile( |
83 | | apr_pool_t *p, const char *s, |
84 | | int case_sensitive) |
85 | 874 | { |
86 | 874 | apr_strmatch_pattern *pattern; |
87 | 874 | apr_size_t i; |
88 | 874 | apr_size_t *shift; |
89 | | |
90 | 874 | pattern = apr_palloc(p, sizeof(*pattern)); |
91 | 874 | pattern->pattern = s; |
92 | 874 | pattern->length = strlen(s); |
93 | 874 | if (pattern->length == 0) { |
94 | 0 | pattern->compare = match_no_op; |
95 | 0 | pattern->context = NULL; |
96 | 0 | return pattern; |
97 | 0 | } |
98 | | |
99 | 874 | shift = (apr_size_t *)apr_palloc(p, sizeof(apr_size_t) * NUM_CHARS); |
100 | 224k | for (i = 0; i < NUM_CHARS; i++) { |
101 | 223k | shift[i] = pattern->length; |
102 | 223k | } |
103 | 874 | if (case_sensitive) { |
104 | 874 | pattern->compare = match_boyer_moore_horspool; |
105 | 8.28k | for (i = 0; i < pattern->length - 1; i++) { |
106 | 7.41k | shift[(unsigned char)s[i]] = pattern->length - i - 1; |
107 | 7.41k | } |
108 | 874 | } |
109 | 0 | else { |
110 | 0 | pattern->compare = match_boyer_moore_horspool_nocase; |
111 | 0 | for (i = 0; i < pattern->length - 1; i++) { |
112 | 0 | shift[(unsigned char)apr_tolower(s[i])] = pattern->length - i - 1; |
113 | 0 | } |
114 | 0 | } |
115 | 874 | pattern->context = shift; |
116 | | |
117 | 874 | return pattern; |
118 | 874 | } |