OLD | NEW |
1 #include <wchar.h> | 1 #include <wchar.h> |
2 | 2 |
3 #define MAX(a,b) ((a)>(b)?(a):(b)) | 3 #define MAX(a, b) ((a) > (b) ? (a) : (b)) |
4 #define MIN(a,b) ((a)<(b)?(a):(b)) | 4 #define MIN(a, b) ((a) < (b) ? (a) : (b)) |
5 | 5 |
6 static wchar_t *twoway_wcsstr(const wchar_t *h, const wchar_t *n) | 6 static wchar_t* twoway_wcsstr(const wchar_t* h, const wchar_t* n) { |
7 { | 7 const wchar_t* z; |
8 » const wchar_t *z; | 8 size_t l, ip, jp, k, p, ms, p0, mem, mem0; |
9 » size_t l, ip, jp, k, p, ms, p0, mem, mem0; | |
10 | 9 |
11 » /* Computing length of needle */ | 10 /* Computing length of needle */ |
12 » for (l=0; n[l] && h[l]; l++); | 11 for (l = 0; n[l] && h[l]; l++) |
13 » if (n[l]) return 0; /* hit the end of h */ | 12 ; |
| 13 if (n[l]) |
| 14 return 0; /* hit the end of h */ |
14 | 15 |
15 » /* Compute maximal suffix */ | 16 /* Compute maximal suffix */ |
16 » ip = -1; jp = 0; k = p = 1; | 17 ip = -1; |
17 » while (jp+k<l) { | 18 jp = 0; |
18 » » if (n[ip+k] == n[jp+k]) { | 19 k = p = 1; |
19 » » » if (k == p) { | 20 while (jp + k < l) { |
20 » » » » jp += p; | 21 if (n[ip + k] == n[jp + k]) { |
21 » » » » k = 1; | 22 if (k == p) { |
22 » » » } else k++; | 23 jp += p; |
23 » » } else if (n[ip+k] > n[jp+k]) { | 24 k = 1; |
24 » » » jp += k; | 25 } else |
25 » » » k = 1; | 26 k++; |
26 » » » p = jp - ip; | 27 } else if (n[ip + k] > n[jp + k]) { |
27 » » } else { | 28 jp += k; |
28 » » » ip = jp++; | 29 k = 1; |
29 » » » k = p = 1; | 30 p = jp - ip; |
30 » » } | 31 } else { |
31 » } | 32 ip = jp++; |
32 » ms = ip; | 33 k = p = 1; |
33 » p0 = p; | 34 } |
| 35 } |
| 36 ms = ip; |
| 37 p0 = p; |
34 | 38 |
35 » /* And with the opposite comparison */ | 39 /* And with the opposite comparison */ |
36 » ip = -1; jp = 0; k = p = 1; | 40 ip = -1; |
37 » while (jp+k<l) { | 41 jp = 0; |
38 » » if (n[ip+k] == n[jp+k]) { | 42 k = p = 1; |
39 » » » if (k == p) { | 43 while (jp + k < l) { |
40 » » » » jp += p; | 44 if (n[ip + k] == n[jp + k]) { |
41 » » » » k = 1; | 45 if (k == p) { |
42 » » » } else k++; | 46 jp += p; |
43 » » } else if (n[ip+k] < n[jp+k]) { | 47 k = 1; |
44 » » » jp += k; | 48 } else |
45 » » » k = 1; | 49 k++; |
46 » » » p = jp - ip; | 50 } else if (n[ip + k] < n[jp + k]) { |
47 » » } else { | 51 jp += k; |
48 » » » ip = jp++; | 52 k = 1; |
49 » » » k = p = 1; | 53 p = jp - ip; |
50 » » } | 54 } else { |
51 » } | 55 ip = jp++; |
52 » if (ip+1 > ms+1) ms = ip; | 56 k = p = 1; |
53 » else p = p0; | 57 } |
| 58 } |
| 59 if (ip + 1 > ms + 1) |
| 60 ms = ip; |
| 61 else |
| 62 p = p0; |
54 | 63 |
55 » /* Periodic needle? */ | 64 /* Periodic needle? */ |
56 » if (wmemcmp(n, n+p, ms+1)) { | 65 if (wmemcmp(n, n + p, ms + 1)) { |
57 » » mem0 = 0; | 66 mem0 = 0; |
58 » » p = MAX(ms, l-ms-1) + 1; | 67 p = MAX(ms, l - ms - 1) + 1; |
59 » } else mem0 = l-p; | 68 } else |
60 » mem = 0; | 69 mem0 = l - p; |
| 70 mem = 0; |
61 | 71 |
62 » /* Initialize incremental end-of-haystack pointer */ | 72 /* Initialize incremental end-of-haystack pointer */ |
63 » z = h; | 73 z = h; |
64 | 74 |
65 » /* Search loop */ | 75 /* Search loop */ |
66 » for (;;) { | 76 for (;;) { |
67 » » /* Update incremental end-of-haystack pointer */ | 77 /* Update incremental end-of-haystack pointer */ |
68 » » if (z-h < l) { | 78 if (z - h < l) { |
69 » » » /* Fast estimate for MIN(l,63) */ | 79 /* Fast estimate for MIN(l,63) */ |
70 » » » size_t grow = l | 63; | 80 size_t grow = l | 63; |
71 » » » const wchar_t *z2 = wmemchr(z, 0, grow); | 81 const wchar_t* z2 = wmemchr(z, 0, grow); |
72 » » » if (z2) { | 82 if (z2) { |
73 » » » » z = z2; | 83 z = z2; |
74 » » » » if (z-h < l) return 0; | 84 if (z - h < l) |
75 » » » } else z += grow; | 85 return 0; |
76 » » } | 86 } else |
| 87 z += grow; |
| 88 } |
77 | 89 |
78 » » /* Compare right half */ | 90 /* Compare right half */ |
79 » » for (k=MAX(ms+1,mem); n[k] && n[k] == h[k]; k++); | 91 for (k = MAX(ms + 1, mem); n[k] && n[k] == h[k]; k++) |
80 » » if (n[k]) { | 92 ; |
81 » » » h += k-ms; | 93 if (n[k]) { |
82 » » » mem = 0; | 94 h += k - ms; |
83 » » » continue; | 95 mem = 0; |
84 » » } | 96 continue; |
85 » » /* Compare left half */ | 97 } |
86 » » for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); | 98 /* Compare left half */ |
87 » » if (k <= mem) return (wchar_t *)h; | 99 for (k = ms + 1; k > mem && n[k - 1] == h[k - 1]; k--) |
88 » » h += p; | 100 ; |
89 » » mem = mem0; | 101 if (k <= mem) |
90 » } | 102 return (wchar_t*)h; |
| 103 h += p; |
| 104 mem = mem0; |
| 105 } |
91 } | 106 } |
92 | 107 |
93 wchar_t *wcsstr(const wchar_t *restrict h, const wchar_t *restrict n) | 108 wchar_t* wcsstr(const wchar_t* restrict h, const wchar_t* restrict n) { |
94 { | 109 /* Return immediately on empty needle or haystack */ |
95 » /* Return immediately on empty needle or haystack */ | 110 if (!n[0]) |
96 » if (!n[0]) return (wchar_t *)h; | 111 return (wchar_t*)h; |
97 » if (!h[0]) return 0; | 112 if (!h[0]) |
| 113 return 0; |
98 | 114 |
99 » /* Use faster algorithms for short needles */ | 115 /* Use faster algorithms for short needles */ |
100 » h = wcschr(h, *n); | 116 h = wcschr(h, *n); |
101 » if (!h || !n[1]) return (wchar_t *)h; | 117 if (!h || !n[1]) |
102 » if (!h[1]) return 0; | 118 return (wchar_t*)h; |
| 119 if (!h[1]) |
| 120 return 0; |
103 | 121 |
104 » return twoway_wcsstr(h, n); | 122 return twoway_wcsstr(h, n); |
105 } | 123 } |
OLD | NEW |