string functions

Question

I'm solving this K&R exercise:

Write versions of the library functions strncpy , strncat , and strncmp , which operate on at most the first n characters of their argument strings. For example, strncpy(s,t,n) copies at most n characters of t to s . Full descriptions are in Appendix B.

So i was wandering if there's a site that contains source code for these string functions so i could check to see if i did something wrong.

These are the versions i wrote: i would appreciate if you would tell me if i have some bugs in the functions or something i should add/correct/improve!

int strncmp(char *s, char *t, int n)
{

     if(strlen(s) == strlen(t)) {

         while(*s == *t && *s && n) 
            n--, s++, t++;

         if(!n) 
             return 0; /* same length and same characters */
         else 
             return 1; /* same length, doesnt has the same characters */         
     }
     else
        return strlen(s) - strlen(t);
}

char *strncpy(char *s, char *t, int n)
{
     while(n-- && *s) {
        *s = *t;
        s++, t++;
     }

     if(strlen(t) < n)
        *s = '\0';

     return s;
}

char *strncat2(char *s, char *t, int n)
{
     while(*s)
       s++;

     while(n-- && *t) 
       *s = *t, s++, t++;

     *s = '\0';
     return s;
}

Answer 1

Sure, there are plenty of open source implementations of strncmp and friends (e.g., strncmp here), but they won't necessarily help you that much.

Your strncmp for example just implements the wrong algorithm: it's not the case that a shorter string is always "less than" a longer one, e.g., "z" is not less than "aa" -- so you can't start by comparing the lengths only.

Your strncpy is checking *s where it should be checking *t instead, among other issues.

Seeing alternate open source implementations will not help much in diagnosing your bugs: peer review of your code, as you get by posting it to SO, probably helps more;-)

Answer 2

A quick look seems to reveal at least a couple of problems:

• In strncmp: The strlen() call on the input is not valid. They do not have to be null terminated. Also, the return value should be <0, =0, >0 depending on the equality.
• strncpy: I believe the library version pads the string with \0 to the end.

Answer 3

For solutions, see CLC Wiki page.

Now some comments about your code:

For strncmp:

if(strlen(s) == strlen(t)) {

You don't need this check. strlen() traverses the string, so you are going to process the strings twice if the lengths are equal. This can get expensive. In general, low-level functions like these, which can be called a lot in any program should be efficient (although premature optimization is the root of all evil!). Also, you're calling strlen() again for both the strings if the lengths aren't equal. In addition to being expensive, it is wrong too, but we will come to that later. About your while loop:

while(*s == *t && *s && n) 
    n--, s++, t++;

Why abuse the comma operator? I would simplify and write the above as (untested, after all, this is an exercise you are solving!):

while (*s && *t && *s == *t && n--) {
    s++;
    t++;
}
if (!n) return 0;
else return *s - *t;

Your return values are wrong. strncmp() should return 0, less-than 0, or greater-than 0 depending upon whether the first n characters of the first string compare equal to, less than, or greater than (lexicographically) the second string.

Similarly, you should change your strncpy() and strncat2() functions. I haven't looked at those two in detail, but since this is an exercise, you probably want to make the changes yourself anyway.

Answer 4

Google code search is great for looking up implementations of standard functions :) e.g. strncpy:

http://www.google.com/codesearch/p?hl=en#XAzRy8oK4zA/libc/string/strncpy.c&amp;q=strncpy&amp;sa=N&amp;cd=1&amp;ct=rc

Answer 5

Ok, well i was looking at the library and i saw that arguments are declared constant pointers. Why is that? Would it make any diffrence if they werent?

int strncmp(const char *s, const char *t, size_t n)
{

    while(n-- && *s) {
        if(*s != *t)
          return (*(unsigned char *)s - *(unsigned char *)--t);

        s++, t++;
    }
    return 0;

}

And whats with the cast (unsigned char)s and decrementation of t string? Why is that decrementation neccesary?

*s - *t represents the ascii value of after subtraction of the first characters that do not match?

Answer 6

For reference:

char* strncpy(char* s, const char* t, size_t n)
{
    char* ret = s; // need to return this
    while (n-- && *s++ = *t++)
         ;
    if (n) *s = 0;
    return ret;
}

// be lazy, there's no reason to write the copy part of strncpy and strncat twice.
char* strncat(char* s, const char* t, size_t n)
{
     char *ret = s;
     strncpy(s+strlen(s), t, n);
//
//   // if you don't want to call strlen, you can do this
//   while (*s++) ;
//   strncpy(s, t, n);
//
     return ret;
}

int strncmp(const char* s, const char* t, size_t n)
{
    while (n-- && *s == *t) {
          ++s;
          ++t;
    }
    if (n) return *s - *t;
    return 0;
}