Weekday+day validation

Question

The string I'd like to check is something like "abcSun24def". If any valid "xxxyy" (xxx = weekday and yy = day) is found, return the position inside the string. If "xxxyy" is not found, return -1.

The code works as desired, but I think it can be optimized.

/* -------------------------------------------------------------
FUNC    : findxy (find pattern xxxyy)
          xxx = weekday (e.g. "Mon01")
          yy = day
          roster specific formatting
PARAMS  : c (char *), pointer to string
RETURNS : (int), if pattern found, pointer to found pattern in string c
          -1 if pattern not found
REMARKS : 
---------------------------------------------------------------- */
int findxy(char *c) {
    const char *days[] = { "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
    int i, j;
    char bufw[4];
    char bufd[3];

    /* check if c is at least 5 chars long */
    if (strlen(c) < 5)
        return -1;

    for (i = 0; i <= (int)strlen(c)-5; i++) {
        memcpy(bufw, c+i, 3);
        bufw[3]='\0';
        /* check all 7 weekdays */
        for (j = 0; j < 7; j++) {
            /* find weekday matches */
            if (!strcmp(bufw, days[j])) {
                /* check if both chars following weekday are numerical */
                if (isdigit(c[i+3]) && isdigit(c[i+4])) {
                    memcpy(bufd, c+i+3, 2);
                    bufd[2]='\0';
                    /* check if number after weekday is a valid day */
                    if (atoi(bufd) >= 1 && atoi(bufd) <= 31) {
                        return i;
                    }
                }
            }
        }
    }
    return -1;
}

Answer 1

I see some things that may help you improve your code.

Use the required #includes

The code uses strlen and memcpy which means that it should #include <string.h>. It was not difficult to infer, but it helps reviewers if the code is complete. It's also an important part of the interface. I believe these are the required includes:

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

Use const where practical

In your findxy routine, the passed string is never altered, which is just as it should be. You should indicate that fact by declaring it like this:

int findxy(const char *c)

Check for a null pointer

Things do not go well if the routine is passed a NULL pointer. On my machine, I get a segmentation fault and a crash. You can eliminate this hole by adding these lines near the top of the routine:

if (c == NULL) {
    return -1;
}

Use better naming

The days array is well named because it's easy to guess from the name what it contains. Likewise i and j are commonly used as index variables as you have done in this code. However, findxy is a rather cryptic name for what this does and c is a poor name for the passed string. I'd recommend something like this instead:

int findWeekdayDate(const char *str)

Avoid copying if practical

It's not strictly necessary to make copies of portions of the passed string. With a bit of careful planning, it can be done in place. Here's one way to do it, although it's not very efficient:

int isValidWeekdayDate(const char *str) {
    static const char *days[] = { "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
    if (str == NULL || strlen(str) < 5) {
        return 0;
    }
    for (const char **dayname = days; *dayname; ++dayname) {
        char *pos = strstr(str, *dayname);
        if (pos && pos == str) {
            if (isdigit(pos[3]) && isdigit(pos[4])) {
                int val = (pos[3]-'0') * 10 + (pos[4]-'0');
                if (val > 0 && val <= 31) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int findWeekdayDate(const char *str) {
    for (const char *curr = str ; *curr; ++curr) {
        if (isValidWeekdayDate(curr)) {
            return curr-str;
        }
    }
    return -1; 
}

Use a finite state machine

We can create a much more efficient routine by creating a finite state machine. For a particular candidate string, we note that the first character must be one of {'F', 'M', 'S', 'T', 'W'}. If it is not one of those, then the candidate string can be immediately rejected. Now let's say the first character is 'S'. In that case the second character must be one of {'a', 'u'}. We can proceed like this, one character at a time to create a finite state machine. Here's a visualization of such a state machine:

This is how compiler tools like flex and bison and lex and yacc work. The code is very efficient but might not be as easy to understand, so it's a tradeoff you should be aware of.

A very pedantic note

Strictly speaking, this line:

int val = (pos[3]-'0') * 10 + (pos[4]-'0');

is guaranteed to be portable. The C standard requires that encoding of digits is contiguous, so this will work with any character encoding, including EBCDIC, Unicode and ASCII.

Answer 2

Some other points to add in addition to @Edward fine answer.

1. (int) cast not needed in for (i = 0; i <= (int)strlen(c)-5; i++) as code could use i + 5 <= strlen(c).

2. strlen() returns type size_t. In general, int could be too narrow for array indexing and size_t is the right-size for array indexing. Simply enough to just use size_t. This does impact the return type though. What should code return if the date is found in the array past INT_MAX? (Yes, that is far-reaching, but to apply this to string processing in general is still valid.)

   size_t i;
   

3. Rather than potential cause code to repeatedly re-calculate string length (which takes length iterations each) with strlen(), call strlen() only once, if at all.

4. Use is...() functions to quickly filter out invalid candidates.

With some other ideas, a sample untested (todo) alternative.

#defined UC(ch) ((unsigned char) ch)
#define DOM_MIN 1
#define DOM_MAX 31

// return pointer to location with the date or NULL if not found
const char *find_DOW_Date2(const char *c) {
  while (*c) {
    if (isupper(UC(c[0])) && islower(UC(c[1])) && islower(UC(c[2])) && 
        isdigit(UC(c[3])) && isdigit(UC(c[4]))) {
      int dom = (c[3] - '0')*10 + (c[4] - '0');
      if (dom >= DOM_MIN && dom <= DOM_MAX) {
        static const char days[][3] = { "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
        for (size_t i = 0; i < sizeof days/sizeof days[0]; i++) {
          if (strncmp(c, days[i], 3) == 0) {
            return c;
          }
        }
      }
    }
    c++;
  }
  return NULL;
}

Answer 3

Check input characters

The input characters should be checked to not be outside ASCII values 32 to 126. The current implementation fails with input "öMon31" because strlen returns 2 for character 'ö'.