Implementing strnstr

Question

I am trying to implement a strnstr function into C (strstr but it checks the length), for some reason it doesn't work (output is always no):

#include <stdio.h>

char *searchingFor = "stackdummy";
char *in = "la da\ndoo a da\nnow here comes the stack\nok there it was.\n";

char *strnstr(char *s1, char *s2, int length) {
    if(s1 == NULL || s2 == NULL) return NULL;
    printf("searching \n\n\"%s\"\n for %.*s\n", s1, length, s2);
    char *ss1 = malloc(strlen(s1) + 1);
    strcpy(ss1, s1);
    char *ss2 = malloc(length + 1);
    strncpy(ss2, s2, length);
    char *result = strstr(ss1, ss2);
    free(ss1);
    free(ss2);
    return result;
}

int main(void) {
    printf("found: %s\n", strnstr(in, searchingFor, 5) ? "yes" : "no");
    printf("found: %s\n", strnstr(in, searchingFor, 5) ? "yes" : "no");
    printf("found: %s\n", strnstr(in, searchingFor, 5) ? "yes" : "no");
    return 0;
}

Answer 1

The implementation provided by Chris Dodd has the following disadvantages:

1. It defeats the purpose of strnstr in that the while condition uses the unbounded string function strchr
2. It depends on haystack being NULL terminated, which is a deviation from the usual implementation of strnstr, for example as provided by GNU-Darwin
3. The call to strchr is an unnecessary function call when strchar is not inlined
4. Returns haystack instead of NULL when len is zero, a deviation from the accepted strstr semantics
5. Returns an empty string instead of haystack when needle has length of zero

The following implementation remedies the above problems without becoming as difficult to read as the GNU-Darwin implementation, and is Creative Commons licensed:

#include <string.h>

char *strnstr(const char *haystack, const char *needle, size_t len)
{
        int i;
        size_t needle_len;

        if (0 == (needle_len = strnlen(needle, len)))
                return (char *)haystack;

        for (i=0; i<=(int)(len-needle_len); i++)
        {
                if ((haystack[0] == needle[0]) &&
                        (0 == strncmp(haystack, needle, needle_len)))
                        return (char *)haystack;

                haystack++;
        }
        return NULL;
}

Answer 2

How about:

char *strnstr(char *haystack, char *needle, size_t len) {
    if (len == 0) return haystack; /* degenerate edge case */
    while (haystack = strchr(haystack, needle[0])) {
        if (!strncmp(haystack, needle, len)) return haystack;
        haystack++; }
    return 0;
}

If you want haystack to not be null terminated, you'll need two length args:

char *memmem(char *haystack, size_t hlen, char *needle, size_t nlen) {
    if (nlen == 0) return haystack; /* degenerate edge case */
    if (hlen < nlen) return 0; /* another degenerate edge case */
    char *hlimit = haystack + hlen - nlen + 1;
    while (haystack = memchr(haystack, needle[0], hlimit-haystack)) {
        if (!memcmp(haystack, needle, nlen)) return haystack;
        haystack++; }
    return 0;
}

which is available in GNU libc, though older versions are broken.

Answer 3

The strnstr function is not defined in the C Standard, it is available on BSD and some other systems as an extension.

Here is the man page on OS/X:

NAME

strstr, strcasestr, strnstr -- locate a substring in a string

LIBRARY

Standard C Library (libc, -lc)

SYNOPSIS

    #include <string.h>

[...]

    char *strnstr(const char *haystack, const char *needle, size_t len);

[...]

DESCRIPTION

[...]

The strnstr() function locates the first occurrence of the null-terminated string needle in the string haystack, where not more than len characters are searched. Characters that appear after a '\0' character are not searched. Since the strnstr() function is a FreeBSD specific API, it should only be used when portability is not a concern.

RETURN VALUES

If needle is an empty string, haystack is returned; if needle occurs nowhere in haystack, NULL is returned; otherwise a pointer to the first character of the first occurrence of needle is returned.

EXAMPLES

The following sets the pointer ptr to the "Bar Baz" portion of largestring:

       const char *largestring = "Foo Bar Baz";
       const char *smallstring = "Bar";
       char *ptr;

       ptr = strstr(largestring, smallstring);

The following sets the pointer ptr to NULL, because only the first 4 characters of largestring are searched:

       const char *largestring = "Foo Bar Baz";
       const char *smallstring = "Bar";
       char *ptr;

       ptr = strnstr(largestring, smallstring, 4);

This specification is not concise enough, (the man page for the linux kernel version is even more imprecise), yet the example on BSD systems (notably above here) is clear: len is the maximum number of bytes to consider in haystack, not needle, which is just a regular null terminated C string.

Your function does not work for multiple reasons:

• the semantics are incorrect as you consider length to limit s2 instead of s1
• in your approach, duplicating s1 is useless and counter-productive: result, if non NULL, will point into the allocated copy that is freed before returning from the function, hence accessing the string pointed to by the return value will have undefined behavior.
• strncpy does not null terminate the destination array if the source string has at least length characters before its own null terminator. You must set ss2[length] = '\0'; for your approach to work, but again, the real strnstr() function operates differently.
• using malloc() and free() is probably not what you are expected to do, and failing to test for potential allocation failure is a mistake.

Here is a corrected version:

char *strnstr(const char *s1, const char *s2, size_t n) {
    // simplistic algorithm with O(n2) worst case
    size_t i, len;
    char c = *s2;

    if (c == '\0')
        return (char *)s1;

    for (len = strlen(s2); len <= n; n--, s1++) {
        if (*s1 == c) {
            for (i = 1;; i++) {
                if (i == len)
                    return (char *)s1;
                if (s1[i] != s2[i])
                    break;
            }
        }
    }
    return NULL;
}