wcsstr.c raw

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