Case insensitive sub-string search

Question

I found myself in a need of a function that checks whether a string is a sub-string of another string, in a case-insensitive manner. I found that there's no standard function to do this, so I wrote my own.

Please review for bugs / improvements:

char *istrstr(char *str, const char *substr)
{
    size_t n = 0;
    while (*str) {
        while (str[n] && substr[n]) {
            if (tolower(str[n]) != tolower(substr[n])) {
                break;
            }
            n++;
        }
        if (!substr[n]) {
            return str;
        }
        else if (!str[n]) {
            return substr[n] ? str : NULL;
        }
        n = 0;
        str++;
    }
    return NULL;
}

Answer 1

Obscure bug when CHAR_MIN < 0.

islower(int ch) is only valid when ch has a value in the unsigned char range or EOF. As char may have various negative values, tolower(str[n]) can be undefined behavior (UB).

... In all cases the argument is an int, the value of which shall be representable as an unsigned char or shall equal the value of the macro EOF. If the argument has any other value, the behavior is undefined. C11dr §7.4 1

tolower(str[n]) != tolower(substr[n]) // UB
// replace with
tolower((unsigned char) str[n]) != tolower((unsigned char) substr[n])

---

Small simplification.

Use the property that when ch != 0, then tolower(ch) != 0. Then code need not check str[n] and substr[n]

while (str[n] /* && substr[n] */) {
  if (tolower((unsigned char) str[n]) != tolower((unsigned char) substr[n])) {
    break;
  }
...

---

Use const for str too. Wider application and some optimizations may be had.

// char *istrstr(char *str, const char *substr)
char *istrstr(const char *str, const char *substr)

---

Rarely are micro optimizations worth the effort, yet this may be one of those exceptions.

Functions like istrstr() or my_strcmp_caseless() may be used a lot and so warrant "tricks" (AKA micro-optimizations) not meant for normal code as they are higher maintenance yet may provide meaningful improved performance in select cases.

Use with caution.

One is to take advantage that the usually 256 different char values are mapped to a smaller than 256 set. So by using two tolower() functions: perhaps 256 byte look-up tables that differ only in my_tolower[0] != my_tolower0[0], then the compare for a null character is not needed, simplifying the crucial inner loop. Further, I found many compilers perform pre-increment faster than post increment.

 unsigned char my_tolower[256] = { '\0', 1, ... , 'a', 'b', ... 'a', 'b', ... };
 unsigned char my_tolower0[256] = { 'A', 1, ... , 'a', 'b', ... 'a', 'b', ... };

int my_strcmp_caseless(const unsigned char *a, const unsigned char *b) {
  // different lookup tables
  if (my_tolower[*a] == my_tolower0[*b]) {
    while (my_tolower[*(++a)] == my_tolower0[*(++b)]) {
    }
  }
  // same lookup table
  return my_tolower[(unsigned char) *a] - my_tolower[(unsigned char) *b];
}

char *istrstr2(const char *str, const char *substr) {
  while (*str) {
    if (my_strcmp_caseless((const unsigned char *) str), 
        (const unsigned char *) substr) == 0) {
      return str;
    }
    str++;
  }
  return NULL;
}

Of course, locale issues need attention to proper populate and maintain my_tolower[], my_tolower0[].

Answer 2

Both arguments should be const char*. It's a search, it shouldn't be able to change str by accident.

Let's have a look at its use, though. Does it really work like strstr?

puts(istrstr("example", "please")); // prints "ple"

istrstr's behaviour completely differs from strstr. The latter will return NULL when the second string isn't completely in the first one. istrstr's name is therefore misleading and should be called istringoverlap or similar.

Unless you're going for performance, I suggest you to go for simplicity and write an additional helper:

/** @brief checks whether @a prefix is a prefix of @a str.
 *
 * @param str    a null-terminated string
 * @param prefix a null-terminated string
 * @returns 1 if @a prefix is a prefix of @a str
 * @returns 0 otherwise
 *
 * The check is case-insensitive.
 *
 * This function yields undefined behavior if tolower() yields undefined 
 * behavior for any character in either str or prefix. If @a str
 * or @a prefix is not a null-terminated string, the behavior will be
 * undefined.
*/
int is_iprefix(const char * str, const char * prefix) {
    while(*str && *prefix) {
        if(tolower(*str) != tolower(*prefix)) {
            return 0;
        }
        prefix++;
        str++;
    }
    return (*prefix == '\0');
}

Why would I recommend to write another function? With only seven lines it's easy to check whether we got that right. We can re-use this function if we want to, and we can use it as a building block for our now istrstr variant:

const char * istrstr(const char * str, const char * substr) {
    while(*str) {
        if(is_iprefix(str,substr)) {
            return str;
        } else {            /* not really necessary, since return exits */
            str++;
        }    
    }
    return NULL;
}

However, that's not going for maximum performance. If we're really interested in more performance, we have to stop as soon as str is shorter than substr. We can either use strlen and count down, e.g.

const char * istrstr(const char * str, const char * substr) {
    int diff = strlen(str) - strlen(substr);
    while(*str && diff-- >= 0) {
        if(is_iprefix(str,substr)) {
            return str;
        } else {
            str++;
        }    
    }
    return NULL;
}

or we can inline is_iprefix and check whether str runs out of characters, but that's left as an exercise. Your code is almost there, by the way, you just need to fix the aforementioned bug.

Answer 3

Algorithm

There are more efficient string searching algorithms than this; if performance is important, you should research them.

Also, consider whether tolower() is really what you want for a case-insensitive comparison - it's fine for the C locale, but in some locales, both e and é are equivalent to E, in which case, comparing the results of tolower() will miss matches and comparing toupper() will produce false positives.

Includes

The code is missing definitions for size_t, NULL and tolower(). It needs

#include <ctype.h>
#include <stddef.h>

Interface

All names beginning with is are reserved for future use by the standard library; so declaring istrstr() is Undefined Behaviour. Similarly, we can't call it stristr() or similar; we could safely call it i_strstr if you want.

The standard library strstr() accepts str as a const char*. Even though it returns a pointer to non-const and thus creates a hole in the type system, it's probably better to be consistent with that implementation, to avoid surprising users.

Logic

There's a redundant test here:

    if (!substr[n]) {
        return str;
    }
    else if (!str[n]) {
        return substr[n] ? str : NULL;
    }

We only reach the else branch if substr[n] is true, so we don't need to re-test it:

    if (!substr[n]) {
        return str;
    }
    else if (!str[n]) {
        return str;
    }

However, this still looks incorrect - if we ran out of str while there's still some substr remaining to check, then we didn't find a match; this fails the abcdefg and efg tests in my test program (below). We want to return NULL in that case:

    if (!substr[n]) {
        return str;
    }
    else if (!str[n]) {
        return NULL;
    }

Alternatively, just omit the else - we'll fall through to returning NULL before long anyway.

We can stop the loop when str is too short to contain substr:

const size_t substr_len = strlen(substr);
if (strlen(str) < substr_len)
    return NULL;

while (str[substr_len]) {
    /* ... */
}

To further reduce unnecessary work when str is very long, we don't need to measure its full length - we can define a shorter_than() function which iterates until either string ends. I wanted to call it is_shorter(), but as we've seen above, that's reserved for future Standard Library extension.

---

Improved version

#include <ctype.h>
#include <stddef.h>
#include <string.h>

static int shorter_than(const char *a, const char *b)
{
    while (*a++ && *b)
        ++b;
    return *b;
}

char *i_strstr(const char *str, const char *substr)
{
    const size_t substr_len = strlen(substr);

    if (shorter_than(str, substr))
        return NULL;

    do {
        for (const char *p = str, *q = substr;  ;  ++p, ++q) {
            /* Have we matched all of substr */
            if (!*q)
                return (char*)str;
            /* Test the next char */
            if (tolower(*p) != tolower(*q))
                break;
        }
    } while (str++[substr_len]);

    return NULL;
}

Test program

Note carefully that many of these tests are designed to exercise the edge cases, such as matching (or not) at the extreme ends of the string, or using empty strings as arguments.

I've purposefully not tested passing null pointers to the functions; I consider that a programming error and should document that it would be undefined behaviour. Alternatively, we could add some appropriate tests, and adjust the code to pass them.

#include <stdarg.h>
#include <stdio.h>
int expect(int val, const char *file, int line, const char *message, ...)
{
    if (!val) {
        va_list args;
        va_start(args, message);
        fprintf(stderr, "%s:%d:fail: ", file, line);
        vfprintf(stderr, message, args);
        fprintf(stderr, "\n");
        va_end(args);
    }
    return !val;
}

#define expect_true(a) expect((a), __FILE__, __LINE__, #a " should be true")
#define expect_false(a) expect(!(a), __FILE__, __LINE__, #a " should be false")
#define expect_equal(actual, expected) \
    expect((actual)==(expected), __FILE__, __LINE__, #actual " should be " #expected)

int main()
{
    static char p[] = "ABcdEF";
    static char z[] = "";
    /* Return the number of test failures */
    return 0
        + expect_false(shorter_than("a", "a"))
        + expect_false(shorter_than("ab", "a"))
        + expect_true(shorter_than("a", "ab"))
        + expect_false(shorter_than("", ""))
        + expect_false(shorter_than("a", ""))
        + expect_true(shorter_than("", "a"))
        + expect_equal(i_strstr(p, ""), p)
        + expect_equal(i_strstr(p, "ABC"), p)
        + expect_equal(i_strstr(p, "abcdef"), p)
        + expect_equal(i_strstr(p, "bc"), p+1)
        + expect_equal(i_strstr(p, "cd"), p+2)
        + expect_equal(i_strstr(p, "ef"), p+4)
        + expect_equal(i_strstr(p, "BA"), NULL)
        + expect_equal(i_strstr(p, "abcdefg"), NULL)
        + expect_equal(i_strstr(p, "efg"), NULL)
        + expect_equal(i_strstr("", p), NULL)
        + expect_equal(i_strstr(z, z), z)
        ;
}