hey_ram
March 8th, 2009, 02:04 PM
hi all,
i had been trying some examples from k&r. i am facing problems in ex 4-13. the problem statement is this:
Write a recursive version of the function reverse(s) , which reverses the string s in place.
i wrote the following code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char *reverse(char *src, int len);
int main(int argc, char *argv[])
{
char *src, *dest, ch;
int i = 0;
src = (char *)malloc(1*sizeof(char));
dest = (char *)malloc(1*sizeof(char));
fprintf(stdout, "\nEnter a string:");
while( (ch = getchar()) != '\n')
{
src = (char *)realloc(src, (i + 1)*sizeof(char));
*(src + i++) = ch;
}
*(src + i) = '\0';
dest = reverse(src, strlen(src));
fprintf(stdout, "\n%s, after reversing => %s\n", src, dest);
free(src);
free(dest);
return 0;
}
char *reverse(char *src, int len)
{
static char *dest;
static int i = 0, j = 0;
while(j >= 0)
{
if( i == 0 )
{
dest = (char *)malloc(1*sizeof(char));
j = len - 1;
}
dest = (char *)realloc(dest, (i + 1)*sizeof(char));
*(dest + i++) = *(src + j--);
dest = reverse(src, j);
}
*(dest + i + 1) = '\0';
return dest;
}
with the following valgrind report:
valgrind --tool=memcheck --leak-check=yes ./h
==10448== Memcheck, a memory error detector.
==10448== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==10448== Using LibVEX rev 1804, a library for dynamic binary translation.
==10448== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==10448== Using valgrind-3.3.0-Debian, a dynamic binary instrumentation framework.
==10448== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==10448== For more details, rerun with: -v
==10448==
Enter a string:google mail
==10448== Invalid write of size 1
==10448== at 0x804856F: main (reverse_recursive.c:23)
==10448== Address 0x418c2ab is 0 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048545: main (reverse_recursive.c:20)
==10448==
==10448== Invalid read of size 1
==10448== at 0x40239E3: strlen (mc_replace_strmem.c:242)
==10448== by 0x804857C: main (reverse_recursive.c:25)
==10448== Address 0x418c2ab is 0 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048545: main (reverse_recursive.c:20)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804858B: main (reverse_recursive.c:25)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804858B: main (reverse_recursive.c:25)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804858B: main (reverse_recursive.c:25)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid read of size 1
==10448== at 0x40239E3: strlen (mc_replace_strmem.c:242)
==10448== by 0x407D811: vfprintf (in /lib/tls/i686/cmov/libc-2.7.so)
==10448== by 0x4083321: fprintf (in /lib/tls/i686/cmov/libc-2.7.so)
==10448== by 0x80485B2: main (reverse_recursive.c:27)
==10448== Address 0x418c2ab is 0 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048545: main (reverse_recursive.c:20)
google mail, after reversing => liam elgoog
==10448==
==10448== ERROR SUMMARY: 16 errors from 7 contexts (suppressed: 11 from 1)
==10448== malloc/free: in use at exit: 1 bytes in 1 blocks.
==10448== malloc/free: 25 allocs, 24 frees, 135 bytes allocated.
==10448== For counts of detected errors, rerun with: -v
==10448== searching for pointers to 1 not-freed blocks.
==10448== checked 64,396 bytes.
==10448==
==10448==
==10448== 1 bytes in 1 blocks are definitely lost in loss record 1 of 1
==10448== at 0x4022AB8: malloc (vg_replace_malloc.c:207)
==10448== by 0x8048506: main (reverse_recursive.c:15)
==10448==
==10448== LEAK SUMMARY:
==10448== definitely lost: 1 bytes in 1 blocks.
==10448== possibly lost: 0 bytes in 0 blocks.
==10448== still reachable: 0 bytes in 0 blocks.
==10448== suppressed: 0 bytes in 0 blocks.
my questions are:
1. in the question, it says that the string needs to be replaced "in place". what does that mean exactly? does that mean i cannot return a char pointer (string) from the function, and that the original string needs to be altered?
2. is this program really a recursive function? i am struggling with recursive functions, and am not able to convince myself if this is one.
3. please help me find and plug the leak. i think it arises because i declare the destination string as static. but i have tried various combinations of free's and alloc's and the leak still seems to persist.
4. should i be bothered about the "invalid read" and "invalid write" operations?
thanks!
i had been trying some examples from k&r. i am facing problems in ex 4-13. the problem statement is this:
Write a recursive version of the function reverse(s) , which reverses the string s in place.
i wrote the following code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char *reverse(char *src, int len);
int main(int argc, char *argv[])
{
char *src, *dest, ch;
int i = 0;
src = (char *)malloc(1*sizeof(char));
dest = (char *)malloc(1*sizeof(char));
fprintf(stdout, "\nEnter a string:");
while( (ch = getchar()) != '\n')
{
src = (char *)realloc(src, (i + 1)*sizeof(char));
*(src + i++) = ch;
}
*(src + i) = '\0';
dest = reverse(src, strlen(src));
fprintf(stdout, "\n%s, after reversing => %s\n", src, dest);
free(src);
free(dest);
return 0;
}
char *reverse(char *src, int len)
{
static char *dest;
static int i = 0, j = 0;
while(j >= 0)
{
if( i == 0 )
{
dest = (char *)malloc(1*sizeof(char));
j = len - 1;
}
dest = (char *)realloc(dest, (i + 1)*sizeof(char));
*(dest + i++) = *(src + j--);
dest = reverse(src, j);
}
*(dest + i + 1) = '\0';
return dest;
}
with the following valgrind report:
valgrind --tool=memcheck --leak-check=yes ./h
==10448== Memcheck, a memory error detector.
==10448== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==10448== Using LibVEX rev 1804, a library for dynamic binary translation.
==10448== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==10448== Using valgrind-3.3.0-Debian, a dynamic binary instrumentation framework.
==10448== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==10448== For more details, rerun with: -v
==10448==
Enter a string:google mail
==10448== Invalid write of size 1
==10448== at 0x804856F: main (reverse_recursive.c:23)
==10448== Address 0x418c2ab is 0 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048545: main (reverse_recursive.c:20)
==10448==
==10448== Invalid read of size 1
==10448== at 0x40239E3: strlen (mc_replace_strmem.c:242)
==10448== by 0x804857C: main (reverse_recursive.c:25)
==10448== Address 0x418c2ab is 0 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048545: main (reverse_recursive.c:20)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804858B: main (reverse_recursive.c:25)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804858B: main (reverse_recursive.c:25)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid write of size 1
==10448== at 0x804868F: reverse (reverse_recursive.c:51)
==10448== by 0x804858B: main (reverse_recursive.c:25)
==10448== Address 0x418c52c is 1 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048621: reverse (reverse_recursive.c:47)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448== by 0x804866B: reverse (reverse_recursive.c:49)
==10448==
==10448== Invalid read of size 1
==10448== at 0x40239E3: strlen (mc_replace_strmem.c:242)
==10448== by 0x407D811: vfprintf (in /lib/tls/i686/cmov/libc-2.7.so)
==10448== by 0x4083321: fprintf (in /lib/tls/i686/cmov/libc-2.7.so)
==10448== by 0x80485B2: main (reverse_recursive.c:27)
==10448== Address 0x418c2ab is 0 bytes after a block of size 11 alloc'd
==10448== at 0x4022B8E: realloc (vg_replace_malloc.c:429)
==10448== by 0x8048545: main (reverse_recursive.c:20)
google mail, after reversing => liam elgoog
==10448==
==10448== ERROR SUMMARY: 16 errors from 7 contexts (suppressed: 11 from 1)
==10448== malloc/free: in use at exit: 1 bytes in 1 blocks.
==10448== malloc/free: 25 allocs, 24 frees, 135 bytes allocated.
==10448== For counts of detected errors, rerun with: -v
==10448== searching for pointers to 1 not-freed blocks.
==10448== checked 64,396 bytes.
==10448==
==10448==
==10448== 1 bytes in 1 blocks are definitely lost in loss record 1 of 1
==10448== at 0x4022AB8: malloc (vg_replace_malloc.c:207)
==10448== by 0x8048506: main (reverse_recursive.c:15)
==10448==
==10448== LEAK SUMMARY:
==10448== definitely lost: 1 bytes in 1 blocks.
==10448== possibly lost: 0 bytes in 0 blocks.
==10448== still reachable: 0 bytes in 0 blocks.
==10448== suppressed: 0 bytes in 0 blocks.
my questions are:
1. in the question, it says that the string needs to be replaced "in place". what does that mean exactly? does that mean i cannot return a char pointer (string) from the function, and that the original string needs to be altered?
2. is this program really a recursive function? i am struggling with recursive functions, and am not able to convince myself if this is one.
3. please help me find and plug the leak. i think it arises because i declare the destination string as static. but i have tried various combinations of free's and alloc's and the leak still seems to persist.
4. should i be bothered about the "invalid read" and "invalid write" operations?
thanks!