nsz Git - musl/blob - src/string/wcsstr.c

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