| 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 |