strmatch/apr_strmatch.c

   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 #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 {
  31     return s;
  32 }
  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 {
  38     const char *s_end = s + slen;
  39     int *shift = (int *)(this_pattern->context);
  40     const char *s_next = s + this_pattern->length - 1;
  41     const char *p_start = this_pattern->pattern;
  42     const char *p_end = p_start + this_pattern->length - 1;
  43     while (s_next < s_end) {
  44         const char *s_tmp = s_next;
  45         const char *p_tmp = p_end;
  46         while (*s_tmp == *p_tmp) {
  47             p_tmp--;
  48             if (p_tmp < p_start) {
  49                 return s_tmp;
  50             }
  51             s_tmp--;
  52         }
  53         s_next += shift[(int)*((const unsigned char *)s_next)];
  54     }
  55     return NULL;
  56 }
  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 {
  62     const char *s_end = s + slen;
  63     int *shift = (int *)(this_pattern->context);
  64     const char *s_next = s + this_pattern->length - 1;
  65     const char *p_start = this_pattern->pattern;
  66     const char *p_end = p_start + this_pattern->length - 1;
  67     while (s_next < s_end) {
  68         const char *s_tmp = s_next;
  69         const char *p_tmp = p_end;
  70         while (apr_tolower(*s_tmp) == apr_tolower(*p_tmp)) {
  71             p_tmp--;
  72             if (p_tmp < p_start) {
  73                 return s_tmp;
  74             }
  75             s_tmp--;
  76         }
  77         s_next += shift[apr_tolower(*s_next)];
  78     }
  79     return NULL;
  80 }
  81
  82 APU_DECLARE(const apr_strmatch_pattern *) apr_strmatch_precompile(
  83                                               apr_pool_t *p, const char *s,
  84                                               int case_sensitive)
  85 {
  86     apr_strmatch_pattern *pattern;
  87     apr_size_t i;
  88     int *shift;
  89
  90     pattern = apr_palloc(p, sizeof(*pattern));
  91     pattern->pattern = s;
  92     pattern->length = strlen(s);
  93     if (pattern->length == 0) {
  94         pattern->compare = match_no_op;
  95         pattern->context = NULL;
  96         return pattern;
  97     }
  98
  99     shift = (int *)apr_palloc(p, sizeof(int) * NUM_CHARS);
 100     for (i = 0; i < NUM_CHARS; i++) {
 101         shift[i] = pattern->length;
 102     }
 103     if (case_sensitive) {
 104         pattern->compare = match_boyer_moore_horspool;
 105         for (i = 0; i < pattern->length - 1; i++) {
 106             shift[(int)s[i]] = pattern->length - i - 1;
 107         }
 108     }
 109     else {
 110         pattern->compare = match_boyer_moore_horspool_nocase;
 111         for (i = 0; i < pattern->length - 1; i++) {
 112             shift[apr_tolower(s[i])] = pattern->length - i - 1;
 113         }
 114     }
 115     pattern->context = shift;
 116
 117     return pattern;
 118 }