Thursday, November 19, 2009

help with implementation of strcpy and strcat

help with implementation of strcpy and strcat
Asked by idok in C Programming Language, Design Patterns, Open Source Programming
Tags: strcpy strcat implementation
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

=======================
evilrix:
>> 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.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:



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;
}
=============================
evilrix:
>> 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...

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:



#include
#include

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);
}

No comments: