Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(323)

Side by Side Diff: fusl/src/string/wcsstr.c

Issue 1714623002: [fusl] clang-format fusl (Closed) Base URL: git@github.com:domokit/mojo.git@master
Patch Set: headers too Created 4 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698