3
\$\begingroup\$

I wrote a function (get_last_word_of) that takes a C string and a destination buffer, and then copies the last word into the buffer. The code was originally C++, and was changed into C later.

#include <assert.h>
#include <stdio.h>
#include <string.h>

// Check whether the two values are equal, and print an error if they are not.
void AssertEq(int lhs, int rhs, int line) {
    if (lhs != rhs)
        printf("Fail: %d != %d (line %d)", lhs, rhs, line);
}

#define ASSERT_EQ(lhs, rhs) do { AssertEq(lhs, rhs, __LINE__); } while (0);

// Given a valid C string pointer, find the index of the last character that
// is not whitespace.  If str points to an empty string, return -1.
int find_index_of_last_nonwhitespace(char const* str) {
    assert(str && "str must point to a valid C string");

    int const length = strlen(str);

    // We subtract 1 to skip the null terminator.  Seeing as we check p >= str
    // before we do anything else, this should be okay even for a str that is empty.
    char const* p = str + length - 1;
    while (p >= str && *p == ' ')
        --p;

    return p - str;
}

// Return the index of the beginning last word in the given C string.  If the string
// is empty, return 0.
int find_index_of_beginning_of_last_word(char const* str) {
    assert(str && "str must point to a valid C string");

    int end_of_last_word = find_index_of_last_nonwhitespace(str);

    // Subtract 1 so that we have the index of the first letter
    char const* p = str + end_of_last_word;
    while (p >= str && *p != ' ')
        --p;

    return p - str + 1; // To compensate for this being the index prior to the word.
}

// Given a destination buffer and a source C string pointer, copy the source
// into the destination until a space or the end of the string is hit.
// The buffer must be large enough to store the word and a \0 character after it.
// If dest == src, simply truncate after the first word.
void wordcpy(char* dest, char const* src) {
    assert(src && "src must point to a valid C string");
    assert(dest && "dest must point to a valid buffer");

    char* d = dest;
    char const* s = src;

    for ( ; *s != '\0' && *s != ' '; ++s, ++d)
        *d = *s;

    *d = '\0';
}

// Given a pointer to a C string, and a pointer to an output buffer that is at least
// as large as the last word in the input plus one, copy the last word of the input
// into the output buffer.
void get_last_word_of(char const* input, char* output) {
    assert(input && "input must be a valid C string");
    assert(output && "output must be a valid buffer");

    int index_of_last_word = find_index_of_beginning_of_last_word(input);
    wordcpy(output, input + index_of_last_word);
}

int main() {
    ASSERT_EQ(find_index_of_last_nonwhitespace("Test  "), 3);
    ASSERT_EQ(find_index_of_last_nonwhitespace("Test"), 3);
    ASSERT_EQ(find_index_of_last_nonwhitespace("Te st "), 4);
    ASSERT_EQ(find_index_of_last_nonwhitespace("Te st"), 4);
    ASSERT_EQ(find_index_of_last_nonwhitespace(""), -1);
    ASSERT_EQ(find_index_of_last_nonwhitespace("  "), -1);

    ASSERT_EQ(find_index_of_beginning_of_last_word("Test"), 0);
    ASSERT_EQ(find_index_of_beginning_of_last_word("Test  "), 0);
    ASSERT_EQ(find_index_of_beginning_of_last_word("Test test"), 5);
    ASSERT_EQ(find_index_of_beginning_of_last_word("Test test  "), 5);
    ASSERT_EQ(find_index_of_beginning_of_last_word(""), 0);
    ASSERT_EQ(find_index_of_beginning_of_last_word("   "), 0);

    char buf[100];
    wordcpy(buf, "Hello");
    ASSERT_EQ(strcmp(buf, "Hello"), 0);
    wordcpy(buf, "Hello  ");
    ASSERT_EQ(strcmp(buf, "Hello"), 0);
    wordcpy(buf, "    ");
    ASSERT_EQ(strcmp(buf, ""), 0);
    return 0;
}

I'm primarily interested in:

  1. What inputs (if any) could cause these functions to perform undefined behaviour?
  2. Are there enough comments?
  3. Is the ASSERT_EQ macro safe to use, and is there any way to let it be used with types other than int? (I used templates in C++, but am at a loss in C.)
  4. Would there be a significant advantage to using size_t instead of int here?
  5. Are the tests sufficient? Are there any cases I missed? Are some unnecessary?

Any further nitpicking is of course welcome.

\$\endgroup\$
13
  • \$\begingroup\$ assert(input && "input must be a valid C string"); will never fail. If input is false, the string will evaluate to true, no? \$\endgroup\$ – Joey Adams Jan 13 '12 at 0:32
  • \$\begingroup\$ That's why it's &&, not ||. If input is false, the string will never evaluate at all (and even if it does, false && true is still false). \$\endgroup\$ – Anton Golov Jan 13 '12 at 0:39
  • \$\begingroup\$ Oops, you're right. \$\endgroup\$ – Joey Adams Jan 13 '12 at 0:49
  • \$\begingroup\$ OK. Asked and answered. \$\endgroup\$ – Paul Martel Jan 13 '12 at 1:00
  • 1
    \$\begingroup\$ Been awhile for me and C, but we used to always wrap macro arguments in the replacement part of the macro in parentheses. Why? I think maybe it was in case the argument involved a comma operator, or some such ugliness. \$\endgroup\$ – President James K. Polk Jan 13 '12 at 2:30
4
\$\begingroup\$

Found some inputs that could cause wordcpy to perform undefined behaviour. See below.

Enough comments? Pretty close, though some needed tweaking. What IS lacking is some definition of what is meant by "word", "space", "whitespace" especially as they relate to the presence of punctuation, tabs, newlines, etc.

As for ASSERT_EQ, I'm pretty sure you need separate per-type macros, functions, and format strings in C.

size_t would probably be cleaner for all lengths and offsets, but I don't know of any specific environments where int would be an actual issue.

Are the tests sufficient? Cases missed? I added a few and suggested the shape of a few more.

Are some unnecessary? You never know when you'll break an edge case.

I didn't compile anything, so consider all mods to be c-like pseudo code.

#include <assert.h>
#include <stdio.h>
#include <string.h>

// Check whether the two values are equal, and print an error if they are not.
void AssertEq(int lhs, int rhs, int line) {
    if (lhs != rhs)

OP had printf(...

        fprintf(stderr, "Fail: %d != %d (line %d)", lhs, rhs, line);
}

#define ASSERT_EQ(lhs, rhs) do { AssertEq(lhs, rhs, __LINE__); } while (0);


// Given a valid C string pointer, find the index of the last character that

OP had ...If str points to an empty string, return -1.

// is not whitespace.  If str points to an empty or all-whitespace string, return -1.
int find_index_of_last_nonwhitespace(char const* str) {
    assert(str && "str must point to a valid C string");

    int const length = strlen(str);

    // We subtract 1 to skip the null terminator.  Seeing as we check p >= str
    // before we do anything else, this should be okay even for a str that is empty.
    char const* p = str + length - 1;

OP had while (p >= str && *p == ' ')

    while (p >= str && isspace(*p))
        --p;

    return p - str;
}

OP had ...index of the beginning last word ... is empty, return 0.

// Return the index of the beginning of the last word in the given C string.  If the string
// is empty or all whitespace, return 0.

Design Note: It seems a little strange that you get the same 0 result for inputs "abc" and " "

int find_index_of_beginning_of_last_word(char const* str) {
    assert(str && "str must point to a valid C string");

    int end_of_last_word = find_index_of_last_nonwhitespace(str);

OP had // Subtract 1 so that we have the index of the first letter

(Comment removed -- no subtraction in sight)

Suggestion: add a reassuring comment around here about what happens for an empty/blank input.

    char const* p = str + end_of_last_word;

OP had while (p >= str && *p != ' ')

    while (p >= str && ! isspace(*p))
        --p;

    return p - str + 1; // To compensate for this being the index prior to the word.
}

Needs buffer overlap validation -- passed a dest pointer between src+1 and the last character in the first word of src, this will loop forever trashing memory.

// Given a destination buffer and a source C string pointer, copy the source
// into the destination until a space or the end of the string is hit.
// The buffer must be large enough to store the word and a \0 character after it.
// If dest == src, simply truncate after the first word.
void wordcpy(char* dest, char const* src) {
    assert(src && "src must point to a valid C string");
    assert(dest && "dest must point to a valid buffer");

    char* d = dest;
    char const* s = src;

Do we really mean "space" or general "white space" including \n \t, etc.? Up until now, I had been assuming "white space" as defined by isspace, so I'm following through, here.

OP had for ( ; *s != '\0' && *s != ' '; ++s, ++d)

    for ( ; *s != '\0' && ! isspace(*s); ++s, ++d)
        *d = *s;

    *d = '\0';
}

Consistency in argument ordering (and argument naming? dest/output src/input) between wrdcpy and this function might reduce caller confusion and might improve readability.

// Given a pointer to a C string, and a pointer to an output buffer that is at least
// as large as the last word in the input plus one, copy the last word of the input
// into the output buffer.
void get_last_word_of(char const* input, char* output) {
    assert(input && "input must be a valid C string");
    assert(output && "output must be a valid buffer");

    int index_of_last_word = find_index_of_beginning_of_last_word(input);
    wordcpy(output, input + index_of_last_word);
}

int main() {
    ASSERT_EQ(find_index_of_last_nonwhitespace("Test  "), 3);
    ASSERT_EQ(find_index_of_last_nonwhitespace("Test"), 3);
    ASSERT_EQ(find_index_of_last_nonwhitespace("Te st "), 4);
    ASSERT_EQ(find_index_of_last_nonwhitespace("Te st"), 4);
    ASSERT_EQ(find_index_of_last_nonwhitespace(""), -1);
    ASSERT_EQ(find_index_of_last_nonwhitespace("  "), -1);

    ASSERT_EQ(find_index_of_beginning_of_last_word("Test"), 0);
    ASSERT_EQ(find_index_of_beginning_of_last_word("Test  "), 0);
    ASSERT_EQ(find_index_of_beginning_of_last_word("Test test"), 5);
    ASSERT_EQ(find_index_of_beginning_of_last_word("Test test  "), 5);
    ASSERT_EQ(find_index_of_beginning_of_last_word(""), 0);
    ASSERT_EQ(find_index_of_beginning_of_last_word("   "), 0);

Add:

    ASSERT_EQ(find_index_of_beginning_of_last_word(" Test "), 1);
    ASSERT_EQ(find_index_of_beginning_of_last_word(" Test"), 1);
    ASSERT_EQ(find_index_of_beginning_of_last_word("  Test "), 2);
    ASSERT_EQ(find_index_of_beginning_of_last_word("  Test"), 2);

Suggestion: (Re)initialize buf before each test to a distinctive pattern like 'XXXXXX...' and validate that buf[strlen(buf)+1] is still 'X'.

    char buf[100];
    wordcpy(buf, "Hello");
    ASSERT_EQ(strcmp(buf, "Hello"), 0);
    wordcpy(buf, "Hello  ");
    ASSERT_EQ(strcmp(buf, "Hello"), 0);
    wordcpy(buf, "    ");
    ASSERT_EQ(strcmp(buf, ""), 0);

Test the claim made in the wordcpy comment that it will just null out the first space when dest == src.

    strcpy(buf, "");
    strcpy(buf+strlen(buf)+1, "XYZ");
    wordcpy(buf, buf);
    ASSERT_EQ(strcmp(buf, ""), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, "XYZ"), 0);

    strcpy(buf, " ");
    strcpy(buf+strlen(buf)+1, "XYZ");
    wordcpy(buf, buf);
    ASSERT_EQ(strcmp(buf, ""), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, ""), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+2, "XYZ"), 0);

    strcpy(buf, "  ");
    strcpy(buf+strlen(buf)+1, "XYZ");
    wordcpy(buf, buf);
    ASSERT_EQ(strcmp(buf, ""), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, " "), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+3, "XYZ"), 0);

    strcpy(buf, "ABC");
    strcpy(buf+strlen(buf)+1, "XYZ");
    wordcpy(buf, buf);
    ASSERT_EQ(strcmp(buf, "ABC"), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, "XYZ"), 0);

    strcpy(buf, "ABC XYZ");
    wordcpy(buf, buf);
    ASSERT_EQ(strcmp(buf, "ABC"), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, "XYZ"), 0);

    strcpy(buf, "ABC  XYZ");
    wordcpy(buf, buf);
    ASSERT_EQ(strcmp(buf, "ABC"), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, " XYZ"), 0);

Try strange offsets.

    strcpy(buf, "ABC  XYZ");
    wordcpy(buf, buf+2);
    ASSERT_EQ(strcmp(buf, "C"), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, "C XYZ"), 0);

    strcpy(buf, "ABC  XYZ");
    wordcpy(buf, buf+2);
    ASSERT_EQ(strcmp(buf, "C"), 0);
    ASSERT_EQ(strcmp(buf+strlen(buf)+1, "C XYZ"), 0);

Fix the forever loop before trying these strange offsets.

    strcpy(buf, "ABC XYZ");
    // Until fixed, this will trash memory with "ABABAB...
    // wordcpy(buf+2, buf); 
    // Assuming this will be caught and do nothing.
    ASSERT_EQ(strcmp(buf, "ABC XYZ"), 0);

Also, both to show that it works as intended AND to give examples of what you intend, add tests for handling of non-alphabetics, especially common cases like punctuation, tabs, and newlines.

Suggestion: test get_last_word_of

    return 0;


}
\$\endgroup\$
1
  • \$\begingroup\$ Wow, I hadn't realised just how much I was promising with "simply truncate"! I think I'll simply leave that part out; it wasn't my intention to guarantee that much. Thank you for the feedback. \$\endgroup\$ – Anton Golov Jan 13 '12 at 9:27
2
\$\begingroup\$

Leaving aside philosophical issues like why do you bother with a language which today is only used for programming micro-controllers the size of a contact lens, and why would you ruin a something written in C++ by converting it to C, I must say that it is a well written piece of code, authored by someone who has a good understanding of what he is doing. (Then again, of course, you really cannot accomplish anything in C unless you have a good understanding of what you are doing.) Notwithstanding that, there are a few issues.

  1. As GregS pointed out, macro arguments need parentheses.
  2. find_index_of_last_nonwhitespace() does not really do what its name says, nor what the comment above it says, because when we say "whitespace" we don't only mean the space character. You need to use isspace() from ctype.h to tell if a character is whitespace or not, and this applies to all places in the code that compare against the space character.
  3. The If dest == src, simply truncate after the first word comment looks like it has been added after the fact, in order to describe what the code will actually do, rather than to specify a requirement for the code. I would suggest that you replace it with a comment saying If dest == src, the behavior is undefined, because if you ever decide to implement that function differently in the future, you don't want to have to do tricks in order to precisely emulate the bizarre functionality of the old version, do you?
  4. Obviously, get_last_word_of will fail if it is ever given to parse some text containing a word larger than some buffer, and the way it is written precludes the possibility of ever having any control over this so as to prevent it from happening, because the size of the output buffer is not passed as a parameter. In the test code, you would have a failure if you used a word longer than 100 characters. You might say, "you gotta be kidding, who would ever write a word longer than 100 characters?" One answer is, my son did, when he was 1.5 years old, and got a hold of my computer while I was in the kitchen, and he typed his first word document by holding the z key down for a couple of minutes and watching the 'z's fly by on the screen. If Microsoft Word was using your code, it would have crashed. Another answer is that this is precisely the kind of stuff that buffer overrun exploits are made of: the hacker will intentionally give the kind of input that the programmer did not expect.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Some people just enjoy coding in C. \$\endgroup\$ – seand Jan 13 '12 at 16:52
  • \$\begingroup\$ Well, of course, everyone is entitled to have their own little perversions. \$\endgroup\$ – Mike Nakis Jan 13 '12 at 17:02

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.