A simple and safe implementation for strnstr (search for a substring in the first n characters of char array)

Question

I'd like to suggest the following implementation:

// Find an instance of substr in an array of characters
// the array of characters does not have to be null terminated
// the search is limited to the first n characters in the array.
char *strnstr(char *str, const char *substr, size_t n)
{
    char *p = str, *pEnd = str+n;
    size_t substr_len = strlen(substr);

    if(0 == substr_len)
        return str; // the empty string is contained everywhere.

    pEnd -= (substr_len - 1);
    for(;p < pEnd; ++p)
    {
        if(0 == strncmp(p, substr, substr_len))
            return p;
    }
    return NULL;
}

The rationale for the first parameter is not to be const is that you may want to use the return value pointer to modify the array in that location.

for completeness, in C++, it's possible to add an overloaded variant that's const:

const char *strnstr(const char *str, const char *substr, size_t n)
{
    return strnstr((char *)str, substr, n);
}

Any comments?

---

As suggested, here's a test program:

#include <iostream>
#include <cstring>
#include <string>

int main()
{
    char s[] = "1234567890abcdefgh";
    size_t n = sizeof(s) - 1;

    const char *patterns[] = { "efgh", "0ab", "0b", NULL };
    const char *result = NULL;
    const char *pPattern = patterns[0];

    std::cout << "array of length " << n << " is: " << s << std::endl;

    for (int i = 0; pPattern; pPattern = patterns[++i])
    {
        result = strnstr(s, pPattern, n);
        std::cout << "finding " << pPattern << " n=" << n << ": "
            << (result ? result : "(null)") << std::endl;
    }

    pPattern = patterns[0];
    result = strnstr(s, pPattern, n-1);
    std::cout << "finding " << pPattern << " n=" << n-1 << ": "
        << (result ? result : "(null)") << std::endl;
    return 0;
}

Output:

array of length 18 is: 1234567890abcdefgh
finding efgh n=18: efgh
finding 0ab n=18: 0abcdefgh
finding 0b n=18: (null)
finding efgh n=17: (null)

Answer 1

1. Design: The str as an array and searched up to n is inconsistent with string like functions and strstr(). Rather than "the search is limited to the first n characters in the array", I'd also expect characters in str that follow a null character are not searched. IMO, a design flaw.

   Following review assumes str[i] == 0 has no special meaning.

2. Weak argument name str. str is the address of an array and maybe not a string. Calling a potential non-string str conveys the wrong idea. Suggest src, etc. When looking for sub-strings, I like needle and haystack.

3. As the C version does not change str contents, recommend making that const. "The rationale for the first parameter is not to be const is that you may want to use the return value pointer to modify the array in that location." does not apply. Just cast char * the return value. Follow strstr()s tyle.

   // From C library.
         char *strstr( const char *s1, const char *s2); 
   
   // Expected signatures: (spaced for clarity)
   // C
         char *strnstr(const char *src, const char *substr, size_t n);
   // C++
         char *strnstr(      char *src, const char *substr, size_t n);
   const char *strnstr(const char *src, const char *substr, size_t n);
   

4. Using a name that is close to standard names is tricky. C reserves name with certain prefixes, etc and so does *nix, etc. Maybe use CP_strnstr() and an optional #define strnstr CP_strnstr.

5. Corner case: Returning str with if(0 == substr_len) return str; does not make sense when size == 0. I'd expect NULL.

6. Underflow possible. The length of the needle may be longer or shorter than the haystack

   // add check
   if (n + 1 < substr_len) {
     return NULL;
   }
   pEnd -= (substr_len - 1);
   

Minor

8. In debug mode, consider testing against NULL

   char *strnstr(char *str, const char *substr, size_t n) {
     assert(str || n == 0);
     assert(substr);
   

Answer 2

A few points here.

1. The name strnstr is reserved for the implementation¹, so your code has undefined behavior.

2. Unless you're fairly sure that the strings you're dealing with are fairly short (or have a lot of repetition) I'd at least consider a different algorithm such as Knuth-Morris-Pratt or one of the Boyer-Moore variants.

3. Use of this should almost always be restricted to C, not C++ (in C++ you'd normally want to use std::string, not nul-terminated byte sequences).

4. The code can have undefined behavior. If n is greater than the size of buffer that str is pointing at, then *pEnd = str+n; can attempt to produce an invalid pointer. In particular, you're allowed to create a pointer to any position in the array, or you can create a pointer to a position one past the end of the array--but any more than one past the end is not allowed--even attempting to create that pointer (without ever attempting to dereference it) gives undefined behavior--and this isn't purely a technicality either--there have been real systems relatively recently that could throw a hardware exception for such a case (e.g., OS/2 1.x).

---

1 c draft N1570 (but the same requirements have existed since C89): "Reserved Identifiers":

All identifiers with external linkage in any of the following subclauses (including the future library directions) are always reserved for use as identifiers with external linkage.

and "Future library directions":

Function names that begin with str, mem, or wcs and a lowercase letter may be added to the declarations in the header.

Answer 3

I'll suggest the following based on your code. Other than style is does have two optimizations: if needle is empty no point calculating end and as I've seen elsewhere checking first char before calling strncmp seems like a good optimization.

char *strnstr(const char *haystack, const char *needle, size_t haystackLength) {
    size_t needleLength = strlen(needle);
    if (needleLength == 0) {
        // empty string is in any string
        return haystack;
    }

    char *end = haystack + haystackLength - (needleLength - 1);
    for (char *start = haystack; start < end; ++start) {
        // checking first char before the whole needle is an optimization
        if ((*start == *needle) && strncmp(start, needle, needleLength) == 0) {
            return start;
        }
    }
    return NULL;
}

As for whether haystack should be as non-const, that's how it's defined in FreeBSD which I assume is what you're shooting for. It is odd that it returns non-const and the result is a pointer to or inside of haystack. Thing is, if you are searching a variable that is const, then passing it in as non-const is weird (wrong-ish). Maybe better to make both haystack and the result const. And if the caller knows it's not actually const to typecast to non-const. ... FWIW I'm thinking in C right now. Might be different considerations in the C++ world.

Answer 4

The test program doesn't seem to have been reviewed yet.

A few minor problems are easily fixed:

• There's no declaration of size_t - it's probably better to use std::size_t instead.
• Prefer nullptr to NULL, as the former is strongly-typed.
• Don't use std::endl when there's no need to flush the stream.
• i seems redundant in the loop - we could simply for (const char *pPattern = patterns[0]; pPattern; ++pPattern). Or even clearer, omit the final null pointer, and just use range-based loop: for (const char *pPattern: patterns).
• There's no confirmation that the returned pointer (when not null) points within the argument string (as opposed, say, to returning the search pattern argument in some cases).
• It's lacking tests of some important cases (zero-length array and/or empty search string; inputs containing null characters).

The main problem with it, though, is that it doesn't actually test the function. It exercises it with a few values, but requires the user to determine whether the behaviour was correct or not. That's the kind of tedious activity that's best shifted to the machine, so make it return EXIT_SUCCESS if the tests all return the expected results, and EXIT_FAILURE otherwise.