summaryrefslogtreecommitdiffstats
path: root/strmatch/apr_strmatch.c
diff options
context:
space:
mode:
Diffstat (limited to 'strmatch/apr_strmatch.c')
-rw-r--r--strmatch/apr_strmatch.c118
1 files changed, 118 insertions, 0 deletions
diff --git a/strmatch/apr_strmatch.c b/strmatch/apr_strmatch.c
new file mode 100644
index 0000000..6a4bf6f
--- /dev/null
+++ b/strmatch/apr_strmatch.c
@@ -0,0 +1,118 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+
+#include "apr_strmatch.h"
+#include "apr_lib.h"
+#define APR_WANT_STRFUNC
+#include "apr_want.h"
+
+
+#define NUM_CHARS 256
+
+/*
+ * String searching functions
+ */
+static const char *match_no_op(const apr_strmatch_pattern *this_pattern,
+ const char *s, apr_size_t slen)
+{
+ return s;
+}
+
+static const char *match_boyer_moore_horspool(
+ const apr_strmatch_pattern *this_pattern,
+ const char *s, apr_size_t slen)
+{
+ const char *s_end = s + slen;
+ apr_size_t *shift = (apr_size_t *)(this_pattern->context);
+ const char *s_next = s + this_pattern->length - 1;
+ const char *p_start = this_pattern->pattern;
+ const char *p_end = p_start + this_pattern->length - 1;
+ while (s_next < s_end) {
+ const char *s_tmp = s_next;
+ const char *p_tmp = p_end;
+ while (*s_tmp == *p_tmp) {
+ p_tmp--;
+ if (p_tmp < p_start) {
+ return s_tmp;
+ }
+ s_tmp--;
+ }
+ s_next += shift[(int)*((const unsigned char *)s_next)];
+ }
+ return NULL;
+}
+
+static const char *match_boyer_moore_horspool_nocase(
+ const apr_strmatch_pattern *this_pattern,
+ const char *s, apr_size_t slen)
+{
+ const char *s_end = s + slen;
+ apr_size_t *shift = (apr_size_t *)(this_pattern->context);
+ const char *s_next = s + this_pattern->length - 1;
+ const char *p_start = this_pattern->pattern;
+ const char *p_end = p_start + this_pattern->length - 1;
+ while (s_next < s_end) {
+ const char *s_tmp = s_next;
+ const char *p_tmp = p_end;
+ while (apr_tolower(*s_tmp) == apr_tolower(*p_tmp)) {
+ p_tmp--;
+ if (p_tmp < p_start) {
+ return s_tmp;
+ }
+ s_tmp--;
+ }
+ s_next += shift[(unsigned char)apr_tolower(*s_next)];
+ }
+ return NULL;
+}
+
+APU_DECLARE(const apr_strmatch_pattern *) apr_strmatch_precompile(
+ apr_pool_t *p, const char *s,
+ int case_sensitive)
+{
+ apr_strmatch_pattern *pattern;
+ apr_size_t i;
+ apr_size_t *shift;
+
+ pattern = apr_palloc(p, sizeof(*pattern));
+ pattern->pattern = s;
+ pattern->length = strlen(s);
+ if (pattern->length == 0) {
+ pattern->compare = match_no_op;
+ pattern->context = NULL;
+ return pattern;
+ }
+
+ shift = (apr_size_t *)apr_palloc(p, sizeof(apr_size_t) * NUM_CHARS);
+ for (i = 0; i < NUM_CHARS; i++) {
+ shift[i] = pattern->length;
+ }
+ if (case_sensitive) {
+ pattern->compare = match_boyer_moore_horspool;
+ for (i = 0; i < pattern->length - 1; i++) {
+ shift[(unsigned char)s[i]] = pattern->length - i - 1;
+ }
+ }
+ else {
+ pattern->compare = match_boyer_moore_horspool_nocase;
+ for (i = 0; i < pattern->length - 1; i++) {
+ shift[(unsigned char)apr_tolower(s[i])] = pattern->length - i - 1;
+ }
+ }
+ pattern->context = shift;
+
+ return pattern;
+}