[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

help with implementation of strcpy and strcat

Posted on 2009-04-23
21
Medium Priority
?
1,930 Views
Last Modified: 2013-11-13
Yo experts,

I need help / referal / link / source of:
correct, _efficient_ C-only (not C++) implmentation of strcpy and strcat - and it needs to be implmented as if you are actually writing library "string.h" - meaning you need to do all the memory allocation/deallocation perfectly...

thanks
0
Comment
Question by:idok
21 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 24217048
Is this question related to homework?
0
 
LVL 10

Expert Comment

by:peetm
ID: 24217058
"Yo" yourself ;-)

Sounds like homework?
0
 
LVL 40

Expert Comment

by:evilrix
ID: 24217122
>> C-only (not C++) implmentation of strcpy and strcat
It's not unknown for the actual implementation of these functions to be in assembly for performance reasons. There is no standard implementation for any of the standard functions, the standard just defines the interface, the semantics and the behavior but it is up to the compiler vendor to figure out the best way to implement the solution... some being better than others :)

An implementation of these functions can be found here
http://www.jbox.dk/sanos/source/lib/string.c.html

They seem about as optimal as you'd get writing them in native C.
char *strcpy(char *dst, const char *src)
{
  char *cp = dst;
  while (*cp++ = *src++);
  return dst;
}
 
char *strcat(char *dst, const char *src)
{
  char *cp = dst;
  while (*cp) cp++;
  while (*cp++ = *src++);
  return dst;
}

Open in new window

0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 40

Expert Comment

by:evilrix
ID: 24217151
^^^ BTW if this is a homework Q please be honest, we'll still help you... we just want to make sure you understand the answers :)
0
 

Author Comment

by:idok
ID: 24218102
ok, want the truth? it's worse than you think...
it's not homework, it's interview question!

the issue is that I am an electrical engineer and haven't touched hardcore programming for quite few years now...
now please help ;-)
0
 

Author Comment

by:idok
ID: 24218136
evilrix:
thanks for your post.. but what about memory allocation/deallocation?
where's the "\0" (null terminated string) treatment?

i mean:

char *s1;
char *s2;

strcpy(s1,"this is one");
strcat(s2," and this is two")

will surely get me a runtime error
I am assuming the user is not resposible for the memory allocation, but the library itself
0
 
LVL 40

Expert Comment

by:evilrix
ID: 24218266
>> but what about memory allocation/deallocation?
What about it? Why do you think there would be any? both functions just work with user provided buffers, there is no alloc or dealloc for them to do.

>> where's the "\0" (null terminated string) treatment?
What treatment? Neither of these functions explicitly appends a null (look at strncat and strncpy for that type fo behavior), they just manipulate what's provided. In the cast of strcat it will cat the source to the dest and include the null, in the case of strycpy it'll copy the source to the dest and include the null.

The magic sauce is this line..

while (*cp++ = *src++);

...it will copy up to and including the null.

Have you looked at the source? Do you understand it? If not then you are going to struggle with interview questions since both of these functions as about as basic as you can get.

>> will surely get me a runtime error
Of course because your usage of strcat or strcpy don't meet the precondition, which is the destination must be a buffer large enough to hold the result

>> I am assuming the user is not resposible for the memory allocation, but the library itself
You assume correct

http://www.cplusplus.com/reference/clibrary/cstring/strcat/
http://www.cplusplus.com/reference/clibrary/cstring/strcpy/
0
 

Author Comment

by:idok
ID: 24220425
evilrix:
I stand corrected, thanks alot.  yes, I do understand the code. I am not new to progamming at all, just not in shape ...

one final issue:
I remember they asked me to write strcpy/strcat
and provided the function headers forcing the source paramter to be a pointer to pointer, i.e.:

char *strcpy(char** src, char *dest);

any idea why and how?

thanks again
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 24220828
The alloc stuff makes sense in that context.  
With that prototype, one would expect that the function allocated the storage for the result and populated the pointer-to-pointer with the address of the allocated data.
However, I would never in a million years name the function strcpy or strcat... I'd use a name like strAllocAndCopy ...  But I'm the kind of programmer who doesn't want the maintence people to wonder what's going on, even for one minute.  A function name should describe what the function does.  And a function shouldn't have the same name as one that does something else.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 24222406
>> The alloc stuff makes sense in that context.  
Agreed, in that context it looks like they expect strcpy to alloc memory.

>> I would never in a million years name the function strcpy or strcat
Also agreed..
0
 

Author Comment

by:idok
ID: 24222911
ok then, what would be the solution now?

0
 

Author Comment

by:idok
ID: 24222966
also - what's the logic behind assuming that the pointer to pointer prototype should allocate the memory and the single pointer should not? I am a bit unclear on that.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 24223003
>> ok then, what would be the solution now?
Something like below. Note that these are untested, they are for example only. Note, the caller is responsible for calling free on the returned pointer otherwise memory will leak.

>> what's the logic behind assuming that the pointer to pointer prototype should allocate the memory and the single pointer should not?
Just that the semantics of passing something by pointer means it's going to be modified (since you are passing by reference and not value). When we pass char * we expect that chars pointer too to be modified. If we pass char ** we expect the pointer being pointed too to be modified. That doesn't mean it will, but these semantics imply that is the case.
char *strcpyAlloc(char **lhs, const char *rhs)
{
	char *ret = malloc(strlen(*dst) + strlen(rhs) + 1)
	char *cp = ret;
	while (*cp++ = *rhs++);
	*lhs = ret;
	return *lhs;
}
 
char *strcatAlloc(char **lhs, const char *rhs)
{
	char *ret = malloc(strlen(*dst) + strlen(rhs) + 1)
	char *cp = ret;
	while (*cp++ = *lhs++);
	while (*cp++ = *rhs++);
	*lhs = ret;
	return *lhs;
}

Open in new window

0
 

Author Comment

by:idok
ID: 24232573
evilrix:
Thanks again for your help, it is appreciated.

I found two issues in your code:
1. on strcpyAlloc - the malloc should be done only for strlen(rhs), if I'm not wrong
2.  on strcatAlloc - the while loop for lhs should dereference the pointer of the pointer as **

also, I added a "free" deallocation support for the functions you provided...
tell please me if it looks right to you and we'll wrap this up

Thanks again

char *strcpyAlloc(char **lhs, const char *rhs)
{
	if (*lhs != NULL)
		free(*lhs);
	char *ret = malloc(strlen(rhs) + 1) // changed this from strlen(*dst) + strlen(rhs) 
	char *cp = ret;
	while (*cp++ = *rhs++);
	*lhs = ret;
	return *lhs;
}
 
char *strcatAlloc(char **lhs, const char *rhs)
{
	if (*lhs != NULL)
		free(*lhs);
	char *ret = malloc(strlen(*dst) + strlen(rhs) + 1)
	char *cp = ret;
	while (*cp++ = **lhs++); // changed from * to **
	while (*cp++ = *rhs++);
	*lhs = ret;
	return *lhs;
}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
ID: 24232741
1 not need space for both lhs and rhs so you need to allocate memory enough for both.

2 possible. I did say it was untested. :)

Regarding free. How do you know that just cos it's not null it's hear allocated memory? It could just be am uninitialized pointer. This is a dangerous assumption.
0
 

Author Comment

by:idok
ID: 24233012
1. why do you need memory for both? you copy lhs<=rhs so you need to allocate memory for rhs characters only, no?
2. actually the correct line is:
while (*cp++ = *(*lhs)++);

3. regarding free - you are right. how can I check for uninitialized pointer?
also -- look at my strcatAlloc function now. I moved the deallocation for lhs only after it's use, but I get runtime error on that (even though *lhs is initialized and allocated)... any idea why?


char *strcatAlloc(char **lhs, const char *rhs)
{
	char *ret = (char *)malloc(strlen(*lhs) + strlen(rhs) + 1);
	char *cp = ret;
	while (*cp++ = *(*lhs)++);
	while (*cp++ = *rhs++);
	if (*lhs != NULL)
		free(*lhs);
	*lhs = ret;
	return *lhs;
}

Open in new window

0
 

Author Comment

by:idok
ID: 24233108
ok, regarding the free - ofcourse advancing *lhs caused the free(*lhs) to fail... (yeah, visual studio is open, we couldn't avoid that...)

attached is the full solution for reference, but without handling uninitalized pointer allocation.
How do I do that, evilrix?

when I was asked this question - they strictly asked for a function taking care of all the possible cases.
anything else I am missing here?
// string_training.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <string.h>
#include <malloc.h>
 
char *strcpyAlloc(char **lhs, const char *rhs)
{
	if (*lhs != NULL)
		free(*lhs);
	char *ret = (char *)malloc(strlen(rhs) + 1);
	char *cp = ret;
	while (*cp++ = *rhs++);
	*lhs = ret;
	return *lhs;
}
 
char *strcatAlloc(char **lhs, const char *rhs)
{
	char *ret = (char *)malloc(strlen(*lhs) + strlen(rhs) + 1);
	char *cp = ret;
	char *cp_lhs = *lhs;
	while (*cp++ = *cp_lhs++);
	while (*cp++ = *rhs++);
	if (*lhs != NULL)
		free(*lhs);
	*lhs = ret;
	return *lhs;
}
 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
	char str1[80] = "this is the first string, ";
	char str2[80] = "this is the second string";
 
	char *s1 = NULL;
	//char *s2 = NULL;
	
	strcpyAlloc(&s1, str1);
	strcatAlloc(&s1, str2);
 
	printf("%s",s1);
 
	return 0;
}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
ID: 24233437
sorry yes for the copy you don't need to allocate both. That's a copy and paste typo and I'm answering on my phone right now so I missed that when I replied before. I thought you ment the strcat. when I get home I'll repost a tested version and deal with you other comments :)
0
 
LVL 40

Accepted Solution

by:
evilrix earned 400 total points
ID: 24233670
>> k, regarding the free - ofcourse advancing *lhs caused the free(*lhs) to fail... (yeah, visual studio is open, we couldn't avoid that...)

You cannot safely implement free in these functions... you have no way to know if the pointer is pointing to memory allocated using malloc and you are likely to just cause the application to crash (or at least introduce undefined and unexpected behaviour)


>> attached is the full solution for reference,
Did you test the code? It doen't work when you perform the strcat -- you need to --cp after the first while to lose the null terminator from the rhs string. Also, it seemed to cause heap corruption for me when I tested it.

>> but without handling uninitalized pointer allocation. How do I do that, evilrix?
You can't there is no way to know if the pointer contains garbage or points to heap that needs to be freed. Put simply there is no way to safely do this so therefore you cannot free in these functions.

>> when I was asked this question - they strictly asked for a function taking care of all the possible cases.
Frankly, who ever asked these questions was an idiot (and you can tell them I said do)! Not only are they asking you to write functions that are pointless they are also asking to the implement unsafe functionality.
---
Right, try my original example below, which I've now had time to test...
#include <malloc.h>
#include <string.h>
 
char *strcpyAlloc(char **lhs, const char *rhs)
{
        char *ret = malloc(strlen(rhs) + 1);
        char *cp = ret;
        while (*cp++ = *rhs++);
        *lhs = ret;
        return *lhs;
}
 
char *strcatAlloc(char **lhs, const char *rhs)
{
        char *ret = malloc(strlen(*lhs) + strlen(rhs) + 1);
        char *cp = ret;
        while (*cp++ = *(*lhs)++);
		--cp;
        while (*cp++ = *rhs++);
        *lhs = ret;
        return *lhs;
}
 
 
int main()
{
	char * p1 = 0;
	char * p2 = 0;
 
	strcpyAlloc(&p1, "hello");
 
	p2 = p1;
	strcatAlloc(&p2, " world");
 
	free(p1);
	free(p2);
}

Open in new window

0
 
LVL 9

Expert Comment

by:Subrat (C++ windows/Linux)
ID: 24942032
Hi evilx,
I thik it'd be more better if we'll check for NULL pointer before entering into each functions as follows.
if (rhs == NULL)
  return NULL;

Again malloc() needs type casting.
So Evilx's modified code will look as below.

#include <malloc.h>
#include <string.h>
 
char *strcpyAlloc(char **lhs, const char *rhs)
{
        if (rhs == NULL)
          return NULL;
        char *ret = (char*)malloc(strlen(rhs) + 1);
        char *cp = ret;
        while (*cp++ = *rhs++);
        *lhs = ret;
        return *lhs;
}
 
char *strcatAlloc(char **lhs, const char *rhs)
{
        if (rhs == NULL)
          return NULL;
        char *ret = (char*)malloc(strlen(*lhs) + strlen(rhs) + 1);
        char *cp = ret;
        while (*cp++ = *(*lhs)++);
            --cp;
        while (*cp++ = *rhs++);
        *lhs = ret;
        return *lhs;
}
 
 
int main()
{
      char * p1 = 0;
      char * p2 = 0;
 
      strcpyAlloc(&p1, "hello");
                printf("%s\n", p1); // For verification
      p2 = p1;
      strcatAlloc(&p2, " world");
                 free(p1);
                 printf("%s\n", p2); // For verification
       free(p2);
}
0
 
LVL 40

Expert Comment

by:evilrix
ID: 25066869
>> I thik it'd be more better if we'll check for NULL pointer before entering into each functions as follows.

The standard functions do not do this. It is a precondition of the function and it is up to the caller to ensure this precondition is met. The reason it is like this is for performance... it adds an extra overhead that isn't necessary. If you want to use an assert to check the code is sane in a debug build but in release it is up to the caller to do the correct checks.

>> Again malloc() needs type casting.
Not in C it doesn't... ever! In fact, in C tt is bad practice to cast the return from malloc since void * will implicitly convert to any pointer type in C (unnecessary explicit casts hide problems).

I guess you are trying this using a C++ compiler, where this implicit cast is not allowed!
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
When you discover the power of the R programming language, you are going to wonder how you ever lived without it! Learn why the language merits a place in your programming arsenal.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question