src/string/wcsstr.c

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