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