Wildcard search in C

Question

In the effort to improve my C knowledge, I tried creating a wildcard search function:

bool wildcard(char *value, char *wcard) {
    size_t vsize = strlen(value);
    size_t wsize = strlen(wcard);

    bool no_match = false;

    if (wsize > vsize) {
        return false;
    }

    for (int w = 0, v = 0; w < wsize; w++, v++) {     
        switch (wcard[w]) {
            case MULTICHAR:          
                if (w == wsize) {
                    goto match;
                } else {                    
                    w++;
                    while (v < vsize) {
                        if (wcard[w] == value[v++]) {
                            v--;
                            break;
                        }
                    }
                    if (no_match) {
                        goto no_match;
                    }
                }
                break;
            case ONECHAR:
                break;
            default:
                if (wcard[w] != value[v]) {
                    goto no_match;
                }
        }
    }

    match:
    return true;

    no_match:
    return false;
}

I have tested this by doing:

printf("Result: %d <- Should be true\n",wildcard("Hello World","Hello*"));
printf("Result: %d <- Should be true\n",wildcard("Hello World","*Hello*"));
printf("Result: %d <- Should be true\n",wildcard("Hello World","He?lo*"));

All return 1.

You can see the project here.

Any tips or improvements are welcome.

Note

I've already found a bug. If the wcard in present in the string, it will return true even if there is more data there.

Example:

wildcard("Hello World","Hello")

This will return true when it shouldn't.

Answer 1

You should the parameters for null values. strlen() does not tolerate nulls passed to it as parameters.

I'm not a complete zealot when it comes to the use of goto, but I'm not sure what benefit it gives in this code. Replacing the gotos with return true or return false would make the code a little simpler and more readable.

  if (no_match) {
       goto no_match;
  }

compared to this for example:

  if (no_match)
     return false;

For the bug you mentioned you will need to compare the lengths of the first and second wildcard parameters IF there is no special character in the second parameter.

Answer 2

There's no need for the gotos whatsoever. Just use the appropriate bools. You also complicate the logic by giving a variable and a goto the same name.

I'd put MULTICHAR's work in a function for clarity.

Personally, I prefer isMatch over no_match. It's up to you.

Since the function returns a bool, just have the switch update isMatch and return it at the end.

bool wildcard(char *value, char *wcard) {
    size_t vsize = strlen(value);
    size_t wsize = strlen(wcard);

    bool isMatch = false;

    if (wsize > vsize) {
        return isMatch;
    }

    for (int w = 0, v = 0; w < wsize; w++, v++) {     
        switch (wcard[w]) {
            case MULTICHAR:          
                isMatch = doSomethingWithBool();
                break;
            case ONECHAR:
                break;
            default:
                isMatch = (wcard[w] == value[v]);
                break;
        }
    }

    return isMatch;
}

Answer 3

Your program returns 1 all the time (for your examples) because you never set no_match apart from at initialisation. Note also that the if (w == wsize) condition is never true because the loop condition is w < size.

I'm also not entirely sure what the function should do in all conditions, but maybe I'm being slow.

Note also that you include four standard library headers in your public header. These includes belong in the C file, not the H file.

Note further that your loop variables should be size_t not int to avoid sign conversion warnings.

EDIT: Exporting unnecessary headers like this is bad practice as they become part of the public interface and any program using your header becomes dependent upon those headers; the compiler must read them in each time it compiles their code. Most of the time this doesn't matter. But I have worked on embedded systems where this sort of thing is a real nuisance. As you are achieving nothing extra by placing the headers in the H file here - they are not providing any declarations needed by the header - put them in the C file. Some projects outlaw nested includes completely, but in general people put them in where the user of the header (not the implementation of what the header exports) needs them to compile correctly.

Answer 4

First, let's clear up some terminology. To me, a wildcard is a special character such as * and ? in shell, or % and _ in SQL. Your wcard parameter is a wildcard expression. Unix users might call it a glob, though Windows users rarely do. I think that pattern would be the most appropriate term, so let's go with that.

(I would also prefer the term subject to value. Also, strictly speaking, this is a wildcard matching function, not a searching function. But those aren't really much of an issue in your code.)

Also on the subject of naming, the inverted logic of bool no_match is unnecessarily confusing. Fortunately, that turns out to be irrelevant since you never actually use the no_match variable!

It's not valid to say that wsize > vsize means the match fails. A long subject (e.g. abc) can match a short pattern (a*). A short subject (a) can match a long pattern (a*). Therefore, if (wsize > vsize) return false is a bug.

The goto feature should be used judiciously, and here its use is inappropriate. This function has no side effects, and you haven't allocated anything other than some local stack variables. There is nothing to clean up, and therefore no reason to restrict your function's exit points. Just return true or false as soon as you know the answer — the code will be more readable.

I think incrementing v in the for loop is a bad idea. Since a MULTICHAR wildcard can match zero characters, it's not certain that v will advance by one character every loop iteration. We do know that w will advance by one character each loop iteration, so the for loop should only be about w.

Instead of counting v and w, then calculating value[v] and wcard[w] all the time, I would just use pointers that crawl along the subject and pattern. Using crawling pointers has the additional advantage of avoiding strlen() — you just look for the null terminator as you go.

Your ONECHAR and default cases need to verify that you have not run past the end of the value string.

In your MULTICHAR case, if (w == wsize) goto match is unreachable code that indicates a logic bug. That condition can never be met since you just checked for w < wsize as a condition in the for loop.

The biggest problem with your MULTICHAR handling is that it only does the non-greediest match possible, which is not expected behaviour. I would expect wildcard("Hello world", "H*orld") to be true, but the o following * would only match the o of Hello, ignoring the other possibility. The simplest way to test all possibilities for the MULTICHAR wildcard is to use recursion.

In summary, here's how I would do it…

bool wildcard(char *subject, char *pattern) {
    for (; *pattern; pattern++) {
        switch (*pattern) {
          case MULTICHAR:
            if (*(pattern + 1) == '\0') {
                /* This wildcard appears at the end of the pattern.
                   If we made it this far already, the match succeeds
                   regardless of what the rest of the subject looks like. */
                return true;
            }
            for (char *s = subject; *s; s++) {
                if (wildcard(s, pattern + 1)) {
                    return true;
                }
            }
            return false;

          case ONECHAR:
            if (*(subject++) == '\0') {
                return false;
            }
            break;

          default:
            if (*subject == '\0' || *pattern != *(subject++)) {
                return false;
            }
        }
    }

    /* End of pattern reached.  If this also the end of the subject, then
       match succeeds. */
    return *subject == '\0';
}