Implementing strnstr

Jimmay picture Jimmay · Jun 2, 2014 · Viewed 18k times · Source

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

Jonathan Ben-Avraham picture Jonathan Ben-Avraham · Sep 7, 2014

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