idok
asked on
help with implementation of strcpy and strcat
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
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
Is this question related to homework?
"Yo" yourself ;-)
Sounds like homework?
Sounds like homework?
>> 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.
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;
}
^^^ 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 :)
ASKER
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 ;-)
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 ;-)
ASKER
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
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
>> 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/
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/
ASKER
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
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
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.
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.
>> 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..
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..
ASKER
ok then, what would be the solution now?
ASKER
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.
>> 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.
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;
}
ASKER
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
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;
}
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.
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.
ASKER
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?
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;
}
ASKER
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?
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;
}
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 :)
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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);
}
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)
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);
}
>> 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!
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!