root/src/utils/noit_str.c

Revision b0c153fce5b4700249d5d6183ffe833ea677780a, 2.5 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 6 years ago)

refs #29

  • Property mode set to 100644
Line 
1 /*
2  * Copyright (c) 2005-2007, OmniTI Computer Consulting, Inc.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  *
9  *    * Redistributions of source code must retain the above copyright
10  *      notice, this list of conditions and the following disclaimer.
11  *    * Redistributions in binary form must reproduce the above
12  *      copyright notice, this list of conditions and the following
13  *      disclaimer in the documentation and/or other materials provided
14  *      with the distribution.
15  *    * Neither the name OmniTI Computer Consulting, Inc. nor the names
16  *      of its contributors may be used to endorse or promote products
17  *      derived from this software without specific prior written
18  *      permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32
33 #include "noit_defines.h"
34
35 #ifndef HAVE_STRNSTRN
36
37 #define KMPPATSIZE 256
38 static void kmp_precompute(const char *pattern, int pattern_len,
39                            int *compile_buf) {
40   int i=0, j=-1;
41
42   compile_buf[0] = j;
43   while (i < pattern_len) {
44     while (j > -1 && pattern[i] != pattern[j])
45       j = compile_buf[j];
46     i++; j++;
47     if (pattern[i] == pattern[j])
48       compile_buf[i] = compile_buf[j];
49     else
50       compile_buf[i] = j;
51   }
52 }
53
54 const char *strnstrn(const char *needle, int needle_len,
55                      const char *haystack, int haystack_len) {
56   int i=0, j=0, compiled[KMPPATSIZE];
57
58   if(needle_len > KMPPATSIZE)
59     abort();
60   kmp_precompute(needle, needle_len, compiled);
61   while (j < haystack_len) {
62     while (i > -1 && needle[i] != haystack[j])
63       i = compiled[i];
64     i++; j++;
65     if (i >= needle_len) {
66       return haystack + j - i;
67     }
68   }
69   return NULL;
70 }
71 #endif
72
Note: See TracBrowser for help on using the browser.