7
\$\begingroup\$

This is exercise 5-4 from K&R. I spent hours tweaking it but now it seems to work. I'm new to pointers and I'd welcome any comments about how to do it better.

/* Function strend(s, t), which returns 1 if the string t 
 * occurs at the end of string s and zero otherwise */
int strend(const char *s, const char *t)
{   
    const char *s0, *t0;

    if (s == 0) {
        printf("s is NULL pointer\n");
        return (-1);
    }
    if (t == 0) {
        printf("t is NULL pointer\n");
        return (-1);
    }
    s0 = s;
    t0 = t;

    while (*s++)
        ;
    s -= 2;         /* *s points to last real char in s */

    while (*t++)
        ;
    t -= 2;         /* *t points to last real char in t */

    if ((t-t0) > (s-s0))
            return (0);  /* t is longer than s */

    while (t>=t0) {
        if (*s-- != *t--) 
            return (0);  /* Mismatch */
    }

    return (1); /* Match */
}

Here is main():

/* Test the function strend(s, t), which returns 1 if the string t 
 * occurs at the end of string s and zero otherwise */
#include "jim.h"
#include "subs.c"

char a[MAXLINE], b[MAXLINE];

int main (void)

{
    printf("Return = %1d, Expect = 1\n", strend("12345", "45"));
    printf("Return = %1d, Expect = 0\n", strend("12345", "35"));
    printf("Return = %1d, Expect = 0\n", strend("45", "345"));
    printf("Return = %1d, Expect = 1\n", strend("12345", "12345"));
    printf("Return = %1d, Expect = 1\n", strend("12345", "5"));
    printf("Return = %1d, Expect = 0\n", strend("12345", "4"));
    printf("Return = %1d, Expect = 1\n", strend("12345", ""));
    printf("Return = %1d, Expect = 0\n", strend("12345", "+"));
    printf("Return = %1d, Expect = 0\n", strend("12345", "a2345"));
    printf("Return = %1d, Expect = 1\n", strend("", ""));
    printf("Return = %1d, Expect = 0\n", strend("", "Z"));
    printf("Return = %1d, Expect = 1\n", strend("1", "1"));
    printf("Return = %1d, Expect = 0\n", strend("1", "1A"));
    printf("Return = %1d, Expect = -1\n", strend(0, "1A"));
    printf("Return = %1d, Expect = -1\n", strend("1", 0));
}

Here is the output:

Return = 1, Expect = 1
Return = 0, Expect = 0
Return = 0, Expect = 0
Return = 1, Expect = 1
Return = 1, Expect = 1
Return = 0, Expect = 0
Return = 1, Expect = 1
Return = 0, Expect = 0
Return = 0, Expect = 0
Return = 1, Expect = 1
Return = 0, Expect = 0
Return = 1, Expect = 1
Return = 0, Expect = 0
s is NULL pointer
Return = -1, Expect = -1
t is NULL pointer
Return = -1, Expect = -1
\$\endgroup\$
6
\$\begingroup\$

Const correct the pointers. The function is not changing anything in memory, no reason they shouldn't be const. Same with variables you declare in the function; Make them const

int strend(const char* s, const char* t)

Check for NULL in the input pointers.

Use library string functions wherever possible. Instead of doing:

while(*s++) ;
s-=2;

call strlen(s); and then substract 1 as needed in your algo. Since you are iterating over the string anyway replacing this with a function call has the same efficiency and makes it more readable.

Add { around the while loop. It is future-proof.

Unit-test to confirm correctness.

\$\endgroup\$
  • \$\begingroup\$ Thx, Chintan. What do you mean by unit-test? \$\endgroup\$ – grok12 May 19 '11 at 21:44
  • \$\begingroup\$ @grok unit-testing is an agile concept where you write the test code first before implementing the actual function. This is usually done with the support of a unit-testing framework to make this process easy. Just google or search on SO if you need more details. \$\endgroup\$ – greatwolf May 19 '11 at 22:39
  • \$\begingroup\$ @Chintan: After I looked it up I realized that it is what we did 30 years ago in microprocessor design. Create an environment where you can test your part of the chip design (we actually called them units!) thoroughly without using anything outside your unit. It made integration go much easier. \$\endgroup\$ – grok12 May 19 '11 at 23:56
  • \$\begingroup\$ I've edited my question to include all of Chintan's input and showed my main used for unit-testing and the output from the test. \$\endgroup\$ – grok12 May 19 '11 at 23:58
  • \$\begingroup\$ Don't know why I can't vote your answer up. It wants me to login or register but I'm already logged in. \$\endgroup\$ – grok12 May 20 '11 at 0:00
3
\$\begingroup\$

Seems like this could be a lot shorter....

/* Function strend(s, t), which returns 1 if the string t 
 * occurs at the end of string s and zero otherwise */
int strend(const char *s, const char *t)
{
   size_t slen, tlen;

   if (!s || !t)
      return -1;

   slen = strlen(s);
   tlen = strlen(t);

   /* Is t longer than s? */
   if (tlen > slen)
      return 0;

   /* Compare the strings... */
   return !strcmp(s + slen - tlen, t);
}

While I'm all in favor of the crazy C style pointer arithmetic loops when they make sense, I don't think it really gains you much to reinvert strlen. And doing the compare backwards is kind of weird, especially where strcmp is perfectly reasonable. I mean, you can deduce the lengths from the previous pass... No need to be all macho.

Also, this is subjective, but I don't think it makes sense to return -1 if NULL is passed. Especially since the function lends itself towards use in a boolean expression; if (strend(NULL, "foo")) will be true, which is weird. Maybe you should let the program crash in that point. (Since dereferencing NULL is a bug.) Or if that scares you, you could return 0. (A NULL pointer can't be said to have a suffix or be a suffix, right?)

I might also consider changing the name. Something like str_contains_suffix maybe?

\$\endgroup\$
  • \$\begingroup\$ Thx, asveikau, good points. I guess that !s will be true is s is null because a null pointer points to address 0, right? \$\endgroup\$ – grok12 May 20 '11 at 21:33
  • \$\begingroup\$ @grok12 correct. \$\endgroup\$ – asveikau May 21 '11 at 1:28
  • \$\begingroup\$ Writing strlen yourself has the potential of fusing the loops, i.e. you could calculate the length of both strings in a single loop and bail out immediately if you notice that s is shorter than t instead of computing the exact length of t in all cases. \$\endgroup\$ – Frerich Raabe Sep 9 '13 at 21:30
  • \$\begingroup\$ @FrerichRaabe - I agree that there could be performance benefits to a single-pass rather than doing both strlen and strcmp. OTOH it might be that your libc's string functions have crazy platform-specific optimizations that you won't be able to beat. Or, for most common data sizes, maybe there'd be no difference at all. And in big-O terms a cost of N and 2N is still O(N). \$\endgroup\$ – asveikau Sep 9 '13 at 22:34
  • \$\begingroup\$ @asveikau: Yeah, the point is: if you fuse the loops, you can pull the tlen > slen check into the loop. In your code, imagine if t is 1048576 bytes and s is just two bytes. As it is, the strlen(t) call will walk the entire t string. If you fuse the loops and pull in the tlen > slen check you wouldn't need to compute the exact length of t if you can tell that it's longer than s. The if is quite simple too, so the branch predictor of the processor should have an easy time with it. \$\endgroup\$ – Frerich Raabe Sep 10 '13 at 8:30
0
\$\begingroup\$

I'd change it more like...

char* start_of_s = s;
char* start_of_t = t;
if(s == NULL || t==NULL) return 0;
while(*s) s++;
while(*t) t++;
while(*s == *t && s > start_of_s && t> start_of_t)
{
    s--; t--;
}
return (t == start_of_t) && (*s == *t);

also unit tested with your tests (and mine), except I caled it "string_is_at_end". I use http://code.google.com/p/seatest/ for unit testing. ( mainly coz I wrote it, though I have a much later version which I haven't released yet)

    assert_true(string_is_at_end("12345",""));
    assert_true(string_is_at_end("123","23"));
    assert_true(string_is_at_end("123","3"));
    assert_false(string_is_at_end("","123"));
    assert_false(string_is_at_end("123","1"));
    assert_false(string_is_at_end("123","2"));
    assert_true(string_is_at_end("12345", "45"));
    assert_false(string_is_at_end("12345", "35"));
    assert_false(string_is_at_end("45", "345"));
    assert_true(string_is_at_end("12345", "12345"));
    assert_true(string_is_at_end("12345", "5"));
    assert_false(string_is_at_end("12345", "4"));
    assert_true(string_is_at_end("12345", ""));
    assert_false(string_is_at_end("12345", "+"));
    assert_false(string_is_at_end("12345", "a2345"));
    assert_true(string_is_at_end("", ""));
    assert_false(string_is_at_end("", "Z"));
    assert_true(string_is_at_end("1", "1"));
    assert_false(string_is_at_end("1", "1A"));
    assert_false(string_is_at_end(0, "1A"));
    assert_false(string_is_at_end("1", 0));
\$\endgroup\$
  • \$\begingroup\$ I DLd your stuff and it looks pretty cool. It looks like it could be a match for my project which is: \$\endgroup\$ – grok12 May 20 '11 at 1:05
  • \$\begingroup\$ I hate how the return key pops you out of a comment. My project is: "To design the microprocessor that I wish I had designed in 1975." \$\endgroup\$ – grok12 May 20 '11 at 1:06
  • \$\begingroup\$ By the way, I like your version better than mine. \$\endgroup\$ – grok12 May 20 '11 at 1:09

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.