I think you should write in ststr.3 that strnstr locates first occurrence
of null-terminated string 'little' in ___null-terminated___ string 'big'.
Andrew.
P.S. Because str(n)str functions deal with null-terminated strings
(i.e. we don't know sizes of strings), it is impossible to write
algorithm, that will work faster (in average) than current implementation.
P.P.S. In the case of binary strings it is possible to implement faster
search -- see attachment.
On Thu, 4 Oct 2001, Mike Barcroft wrote:
> [BCC'd to -hackers for additional comments.]
>
> Hello,
> I would appreciate comments/reviews of the following new addition to
> libc. It is largely based off the current strstr(3) implementation.
>
> Patch attached and also available at:
> http://people.FreeBSD.org/~mike/patches/strnstr.diff
>
>
> Best regards,
> Mike Barcroft
>
#include <sys/types.h>
#include <sys/time.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STRSZ (100*1024)
#define PATSZ 500
#define TRYS 100
void *
bstrstr(s, slen, p, plen)
register const void *s, *p;
size_t slen, plen;
{
register const u_char *str, *substr;
register size_t i, max_shift, curr_shift;
size_t shift[UCHAR_MAX + 1];
if (s == NULL || p == NULL || plen > slen || slen == 0 || plen == 0)
return (NULL);
str = (const u_char *)s;
substr = (const u_char *)p;
for (i = 0; i <= UCHAR_MAX; i++) shift[i] = plen + 1;
for (i = 0; i < plen; i++) shift[substr[i]] = plen - i;
i = 0;
max_shift = slen - plen;
while (i <= max_shift) {
if (*str == *substr && !memcmp(str + 1, substr + 1, plen -1))
return ((void *)str);
curr_shift = shift[str[plen]];
str += curr_shift;
i += curr_shift;
}
return (NULL);
}
int
main(void)
{
char *str;
struct timeval before, after;
size_t i;
srandomdev();
str = (char *)malloc(STRSZ + PATSZ + 1);
if (!str) {
printf("no mem\n");
exit(1);
}
for (i = 0; i < STRSZ + PATSZ; i++) {
str[i] = random() & 0xff;
if (!str[i]) str[i] = 1;
}
str[STRSZ + PATSZ] = 0;
printf("slen = %d, plen = %d\n", STRSZ + PATSZ, PATSZ);
gettimeofday(&before, NULL);
for (i = 0; i < TRYS; i++)
strstr(str, str + STRSZ);
gettimeofday(&after, NULL);
after.tv_sec -= before.tv_sec;
after.tv_usec -= before.tv_usec;
printf("Old: %f sec\n", (after.tv_sec + after.tv_usec/1000000.0)/TRYS);
gettimeofday(&before, NULL);
for (i = 0; i < TRYS; i++)
bstrstr(str, STRSZ + PATSZ, str + STRSZ, PATSZ);
gettimeofday(&after, NULL);
after.tv_sec -= before.tv_sec;
after.tv_usec -= before.tv_usec;
printf("New: %f sec\n", (after.tv_sec + after.tv_usec/1000000.0)/TRYS);
free(str);
return (0);
}
