Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
char **L;
char **R;
int *left;
int *right;
int mergelen;
int overlap_last(char *st)
{
int k,j,length;
char last;
int overlap_at;
overlap_at=0;
length=strlen(st);
last=st[length-1];
for(k=0;k<=((length-3)/2);k++)
{
if(st[length-1-k-1]==last && st[length-1-k-1-k-1]==last)
{
overlap_at=length-1-k-1;
for(j=0;j<k;j++)
{
if(st[length-1-k-1-k+j]!=st[length-1-k+j])
{
overlap_at=0;
break;
}
}
if(overlap_at!=0)
break;
}
}
return overlap_at;
}
void muk(char *u, int k)
{
int i,j,p2m,length;
char *h1;
p2m=pow(2,k);
h1=(char *)malloc(sizeof(char)*(p2m+1)*strlen(u));
strcpy(h1,u);
u[0]='\0';
length=strlen(h1);
for(i=1;i<=k;i++)
{
for(j=0;j<length;j++)
{
if(h1[j]=='a') strcat(u,"ab");
if(h1[j]=='b') strcat(u,"ba");
}
strcpy(h1,u);
u[0]='\0';
if(i==k) strcpy(u,h1);
}
free(h1);
}
int ov_free_concat(char *u, char *v)
{
int k,i,ov_free=1,length;
char *l;
char *t;
char *m;
k=strlen(u);
l=(char *)malloc(sizeof(char)*((strlen(u)+strlen(v))+1));
t=(char *)malloc(sizeof(char)*((strlen(u)+strlen(v))+1));
m=(char *)malloc(sizeof(char)*2);
strcpy(l,u);
strcpy(t,u);
strcat(l,v);
length=strlen(l);
for(i=k;i<length;i++)
{
m[0]=l[i];
m[1]='\0';
strcat(t,m);
if(overlap_last(t)!=0)
{
ov_free=0;break;
}
}
free(l);
free(t);
free(m);
return ov_free;
}
int unique(char **M, char *u)
{
int i,k=1;
for(i=0;i<mergelen;i++)
{
if((strcmp(M[i],u))==0)
{
k=0;
break;
}
}
return k;
}
void addL(char *u)
{
if((unique(L,u)==1))
{
L[mergelen]=(char *)malloc(sizeof(char)*(strlen(u)+1));
strcpy(L[mergelen],u);
mergelen++;
}
}
void addR(char *u)
{
if((unique(R,u)==1))
{
R[mergelen]=(char *)malloc(sizeof(char)*(strlen(u)+1));
strcpy(R[mergelen],u);
mergelen++;
}
}
void Lmuk(int k)
{
int i,j,m;
char **s;
char **u;
char *s1;
int lmergelen;
s=(char **)malloc(sizeof(char *)*4);
s[0]="a";
s[1]="b";
s[2]="aa";
s[3]="bb";
L[0]="";
L[1]="a";
L[2]="aa";
L[3]="b";
L[4]="bb";
mergelen=5;
u=(char **)malloc(sizeof(char *)*4);
lmergelen=mergelen;
for(m=1;m<=k;m++)
{
for(i=0;i<4;i++)
{
u[i]=(char *)malloc(sizeof(char)*(pow(2,m)+1)*strlen(s[i]));
strcpy(u[i],s[i]);
}
///overlap free concatenation add in L//
for(i=0;i<4;i++)
{
muk(u[i],m);
for(j=0;j<lmergelen;j++)
{
if(ov_free_concat(L[j],u[i])!=0)
{
s1=(char *)malloc(sizeof(char)*(strlen(L[j])+strlen(u[i])+1));
strcpy(s1,L[j]);
strcat(s1,u[i]);
addL(s1);
free(s1);
}
}
}
/// finished overlap free concatenation add in L//
for(i=0;i<4;i++)
{
free(u[i]);
}
lmergelen=mergelen;
} //m loop
free(u);
left=(int *)malloc(sizeof(int)*mergelen);
for(i=0;i<mergelen;i++)
{
left[i]=strlen(L[i]);
}
}
void mukR(int k)
{
int i,j,m,rmergelen;
char **s;
char **u;
char *s1;
s=(char **)malloc(sizeof(char *)*4);
s[0]="a";
s[1]="b";
s[2]="aa";
s[3]="bb";
u=(char **)malloc(sizeof(char *)*4);
rmergelen=mergelen;
R[0]="";
for(i=0;i<4;i++)
{
u[i]=(char *)malloc(sizeof(char)*(pow(2,k)+1)*strlen(s[i]));
strcpy(u[i],s[i]);
muk(u[i],k);
R[i+1]=(char *)malloc(sizeof(char)*(pow(2,k)+1)*strlen(s[i]));
strcpy(R[i+1],u[i]);
}
mergelen=5;
for(i=0;i<4;i++)
{
free(u[i]);
}
rmergelen=mergelen;
for(m=k-1;m>0;m--)
{
for(i=0;i<4;i++)
{
u[i]=(char *)malloc(sizeof(char)*(pow(2,k)+1)*strlen(s[i]));
strcpy(u[i],s[i]);
}
///overlap free concatenatioan and addition in R///
for(i=0;i<4;i++)
{
muk(u[i],m);
for(j=0;j<rmergelen;j++)
{
if(ov_free_concat(R[j],u[i])!=0)
{
s1=(char *)malloc(sizeof(char)*(strlen(R[j])+strlen(u[i])+1));
strcpy(s1,R[j]);
strcat(s1,u[i]);
addR(s1);
free(s1);
}
}
} //addition in R finished
rmergelen=mergelen;
for(i=0;i<4;i++)
{
free(u[i]);
}
}//m loop finished
free(u);
//concatenation with s[]
for(i=0;i<4;i++)
{
for(j=0;j<rmergelen;j++)
{
if(ov_free_concat(R[j],s[i])!=0)
{
s1=(char *)malloc(sizeof(char)*(strlen(R[j])+strlen(s[i])+1));
strcpy(s1,R[j]);
strcat(s1,s[i]);
addR(s1);
free(s1);
}
}
}
right=(int *)malloc(sizeof(int)*mergelen);
for(i=0;i<mergelen;i++)
{
right[i]=strlen(R[i]);
}
}
int main()
{
int m=5,k=5,i;
//higher bound of L size estimation
for(i=0;i<k;i++)
{
m=4*m+4;
}
L=(char **)malloc(sizeof(char *)*(m+1));
Lmuk(k);
printf("\nLmergelen=%d",mergelen);
/* for(i=0;i<mergelen;i++)
{
printf("\n%s",L[i]);
}*/
mergelen=0;
R=(char **)malloc(sizeof(char *)*(m+1));
mukR(k);
printf("\nRmergelen=%d",mergelen);
/*for(i=0;i<mergelen;i++)
{
printf("\n%s",R[i]);
}*/
printf("\n");
return 0;
}
I have removed memory write errors and wall warning from programme. But still 3 or 4 read errors are present in the programme. Now my programme is giving out put. Thank You. But can you help me to remove theses read errors i am not getting how to remove these read errors show in this code snippet. Give some tips about leakage reduction. Thank You
Code:
valgrind --db-attach=yes --leak-check=full --show-reachable=yes ./a.out
==2503== Memcheck, a memory error detector
==2503== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==2503== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==2503== Command: ./a.out
==2503==
==2503== Invalid read of size 1
==2503== at 0x80485FB: overlap_last (restivo_salemi.c:20)
==2503== by 0x804899B: ov_free_concat (restivo_salemi.c:80)
==2503== by 0x8048D20: Lmuk (restivo_salemi.c:160)
==2503== by 0x80494FD: main (restivo_salemi.c:275)
==2503== Address 0x4224897 is 1 bytes before a block of size 4 alloc'd
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x80488F5: ov_free_concat (restivo_salemi.c:69)
==2503== by 0x8048D20: Lmuk (restivo_salemi.c:160)
==2503== by 0x80494FD: main (restivo_salemi.c:275)
==2503==
==2503==
==2503== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ---- n
==2503== Invalid read of size 1
==2503== at 0x80485FB: overlap_last (restivo_salemi.c:20)
==2503== by 0x804899B: ov_free_concat (restivo_salemi.c:80)
==2503== by 0x8049356: mukR (restivo_salemi.c:248)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503== Address 0x42b09a7 is 1 bytes before a block of size 3 alloc'd
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x80488F5: ov_free_concat (restivo_salemi.c:69)
==2503== by 0x8049356: mukR (restivo_salemi.c:248)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503==
==2503==
==2503== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ---- n
Lmergelen=329
Rmergelen=329
==2503==
==2503== HEAP SUMMARY:
==2503== in use at exit: 64,004 bytes in 658 blocks
==2503== total heap usage: 9,622 allocs, 8,964 frees, 154,390 bytes allocated
==2503==
==2503== 16 bytes in 1 blocks are definitely lost in loss record 1 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8048B69: Lmuk (restivo_salemi.c:134)
==2503== by 0x80494FD: main (restivo_salemi.c:275)
==2503==
==2503== 16 bytes in 1 blocks are definitely lost in loss record 2 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8048EC1: mukR (restivo_salemi.c:191)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503==
==2503== 198 bytes in 4 blocks are still reachable in loss record 3 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8049063: mukR (restivo_salemi.c:204)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503==
==2503== 1,316 bytes in 1 blocks are still reachable in loss record 4 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8048E4F: Lmuk (restivo_salemi.c:178)
==2503== by 0x80494FD: main (restivo_salemi.c:275)
==2503==
==2503== 1,316 bytes in 1 blocks are still reachable in loss record 5 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x804943C: mukR (restivo_salemi.c:259)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503==
==2503== 1,818 bytes in 126 blocks are still reachable in loss record 6 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8048B1E: addR (restivo_salemi.c:121)
==2503== by 0x80492A8: mukR (restivo_salemi.c:231)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503==
==2503== 2,810 bytes in 198 blocks are still reachable in loss record 7 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8048B1E: addR (restivo_salemi.c:121)
==2503== by 0x8049403: mukR (restivo_salemi.c:253)
==2503== by 0x8049541: main (restivo_salemi.c:284)
==2503==
==2503== 4,634 bytes in 324 blocks are still reachable in loss record 8 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8048A8B: addL (restivo_salemi.c:110)
==2503== by 0x8048DCD: Lmuk (restivo_salemi.c:165)
==2503== by 0x80494FD: main (restivo_salemi.c:275)
==2503==
==2503== 25,940 bytes in 1 blocks are still reachable in loss record 9 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x80494EC: main (restivo_salemi.c:274)
==2503==
==2503== 25,940 bytes in 1 blocks are still reachable in loss record 10 of 10
==2503== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==2503== by 0x8049530: main (restivo_salemi.c:283)
==2503==
==2503== LEAK SUMMARY:
==2503== definitely lost: 32 bytes in 2 blocks
==2503== indirectly lost: 0 bytes in 0 blocks
==2503== possibly lost: 0 bytes in 0 blocks
==2503== still reachable: 63,972 bytes in 656 blocks
==2503== suppressed: 0 bytes in 0 blocks
==2503==
==2503== For counts of detected and suppressed errors, rerun with: -v
==2503== ERROR SUMMARY: 24 errors from 4 contexts (suppressed: 0 from 0)