6
\$\begingroup\$

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

3 Answers 3

6
\$\begingroup\$

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:

weekday validation 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.

\$\endgroup\$
7
  • \$\begingroup\$ FSM appears to accept "Tun" and "Sue" as valid. \$\endgroup\$ Commented Dec 22, 2016 at 16:31
  • \$\begingroup\$ @chux While it might be handy to have 9 days in a week, you're right and the FSM is not. Thanks! \$\endgroup\$
    – Edward
    Commented Dec 22, 2016 at 16:34
  • \$\begingroup\$ What is pos == str for in if (pos && pos == str)? I do not see its need yet. \$\endgroup\$ Commented Dec 22, 2016 at 16:39
  • \$\begingroup\$ It checks that the string was found and that it's in the first position. Otherwise, the calling loop would not have the correct pointer. it's a major source of the inefficiency of that code. \$\endgroup\$
    – Edward
    Commented Dec 22, 2016 at 16:43
  • 1
    \$\begingroup\$ I used the fabulously useful tool graphviz to create the FSM diagram. \$\endgroup\$
    – Edward
    Commented Dec 22, 2016 at 18:57
2
\$\begingroup\$

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

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 'ö'.

\$\endgroup\$
9
  • \$\begingroup\$ Are you saying findxy("öMon31") fails to return a non-negative result on your system? \$\endgroup\$ Commented Dec 23, 2016 at 13:46
  • \$\begingroup\$ oops no it works, hmmm....I could swear it didn't work on my work computer. It didn't return a negative number but the wrong number. \$\endgroup\$ Commented Dec 23, 2016 at 13:55
  • \$\begingroup\$ I'll run another test and delete the answer if it's not showing up again \$\endgroup\$ Commented Dec 23, 2016 at 13:58
  • 1
    \$\begingroup\$ Do not agree - OP's code is correct on that matter. It is not that findxy("öMon31") produces 1 or 2 consistently. It is for code to produce an offset into the string that begins "Mon31" - something OP's code does correct on both platforms. Did that not happen in your testing? Your 2 compilations are not using the same character sets/encoding and so not the same string - even though they print alike. Look at their byte values. That accounts for the 1 or 2. \$\endgroup\$ Commented Dec 23, 2016 at 15:55
  • 1
    \$\begingroup\$ Ok, you are right. Linux obviously encodes in UTF-8 and windows doesn't. I gonna leave the answer here since the answer with our discussion has still some value (unless people vote it down). \$\endgroup\$ Commented Dec 23, 2016 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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