3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ By the way, when you're not coding for recreational/educational purposes, just use the POSIX fnmatch() function. \$\endgroup\$ – 200_success Sep 9 '13 at 10:12
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Sorry. Multichar is just *. I will have to restructure the logic due to the bug I found. I should be checking the string against the pattern and not the pattern against the string. \$\endgroup\$ – AntonioCS Aug 30 '13 at 8:48
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I was just trying to avoid multiple exit points, so in case of a clean up I know where the code will always go. \$\endgroup\$ – AntonioCS Aug 30 '13 at 8:46
  • \$\begingroup\$ A worthy aim. You do have two return points in the code BTW. \$\endgroup\$ – suspectus Aug 30 '13 at 20:01
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well I did find a bug but no, it doesn't return always true. If I do wildcard("Hello World","sdffdsdsfdsfadsfsdf?lo*"). This returns false. What is the problem with the headers? \$\endgroup\$ – AntonioCS Aug 30 '13 at 8:45
  • 1
    \$\begingroup\$ Yes you are right - I was looking at your examples, not all possibilities. I will add a note on headers. \$\endgroup\$ – William Morris Aug 30 '13 at 12:26
  • \$\begingroup\$ Thanks for the quick reply. I will update the code. So in my .h file I should just have the function prototype and any define I have, right? \$\endgroup\$ – AntonioCS Aug 30 '13 at 14:07
  • \$\begingroup\$ Yes, that is right. \$\endgroup\$ – William Morris Aug 30 '13 at 19:05
2
\$\begingroup\$

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';
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.