Memory leaks problem in C -- Help please
Hi !
I'm quite new to C-programming. I am working on a program to make operations on polynoms. My problem is that I have memory leaks (I checked with valgrind) but I don't know where and how to get rid of these! (I don't really understand the valgrind output...)
I would be pleased that someone can help me, I'm sure it is not really complicated but I'm really stuck on this...
Thank you very much in advance
Here is the Valgrind output:
Code:
==16436== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 15 from 1)
==16436== malloc/free: in use at exit: 45,134 bytes in 1,301 blocks.
==16436== malloc/free: 5,015 allocs, 3,714 frees, 177,109 bytes allocated.
==16436== For counts of detected errors, rerun with: -v
==16436== searching for pointers to 1,301 not-freed blocks.
==16436== checked 130,212 bytes.
==16436==
==16436== 12 bytes in 1 blocks are still reachable in loss record 1 of 5
==16436== at 0x4022862: realloc (vg_replace_malloc.c:306)
==16436== by 0x80594E1: (within /usr/bin/make)
==16436== by 0x804B04A: (within /usr/bin/make)
==16436== by 0x805FE7A: (within /usr/bin/make)
==16436== by 0x8060DDA: (within /usr/bin/make)
==16436== by 0x8058B0F: (within /usr/bin/make)
==16436== by 0x405004F: (below main) (in /lib/tls/i686/cmov/libc-2.6.1.so)
==16436==
==16436==
==16436== 46 bytes in 3 blocks are still reachable in loss record 2 of 5
==16436== at 0x4022765: malloc (vg_replace_malloc.c:149)
==16436== by 0x80594F4: (within /usr/bin/make)
==16436== by 0x804B71A: (within /usr/bin/make)
==16436== by 0x804B97D: (within /usr/bin/make)
==16436== by 0x8060110: (within /usr/bin/make)
==16436== by 0x8060DDA: (within /usr/bin/make)
==16436== by 0x8058B0F: (within /usr/bin/make)
==16436== by 0x405004F: (below main) (in /lib/tls/i686/cmov/libc-2.6.1.so)
==16436==
==16436==
==16436== 4,234 bytes in 212 blocks are still reachable in loss record 3 of 5
==16436== at 0x4022765: malloc (vg_replace_malloc.c:149)
==16436== by 0x40AA2CF: strdup (in /lib/tls/i686/cmov/libc-2.6.1.so)
==16436== by 0x8059480: (within /usr/bin/make)
==16436== by 0x805762A: (within /usr/bin/make)
==16436== by 0x405004F: (below main) (in /lib/tls/i686/cmov/libc-2.6.1.so)
==16436==
==16436==
==16436== 16,384 bytes in 15 blocks are still reachable in loss record 4 of 5
==16436== at 0x4021AA4: calloc (vg_replace_malloc.c:279)
==16436== by 0x80653B7: (within /usr/bin/make)
==16436== by 0x8062C11: (within /usr/bin/make)
==16436== by 0x80575E8: (within /usr/bin/make)
==16436== by 0x405004F: (below main) (in /lib/tls/i686/cmov/libc-2.6.1.so)
==16436==
==16436==
==16436== 24,458 bytes in 1,070 blocks are still reachable in loss record 5 of 5
==16436== at 0x4022765: malloc (vg_replace_malloc.c:149)
==16436== by 0x8059546: (within /usr/bin/make)
==16436== by 0x80636BB: (within /usr/bin/make)
==16436== by 0x805766F: (within /usr/bin/make)
==16436== by 0x405004F: (below main) (in /lib/tls/i686/cmov/libc-2.6.1.so)
==16436==
==16436== LEAK SUMMARY:
==16436== definitely lost: 0 bytes in 0 blocks.
==16436== possibly lost: 0 bytes in 0 blocks.
==16436== still reachable: 45,134 bytes in 1,301 blocks.
==16436== suppressed: 0 bytes in 0 blocks.
Here is my code (quite long, but not really complicated):
Code:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include "error.h"
#include "poly.h"
/*MACROS*/
#define PAUSE { {printf("\nPress 'Enter' to quit...\n"); while(getchar() != '\n'){;}} }
#define EMALLOC(type,v,N) { if( (v = (type*) malloc(N*sizeof(type))) == NULL){\
error("ERROR: malloc failed, out of memory");}; }
#define EREALLOC(type,v,N) { type* temp = NULL; \
if ((temp = (type*) realloc(v, N*sizeof(type))) == NULL){\
error("ERROR: realloc failed, out of memory");}; v = temp; free(&temp); }
#define PASS_NEXT(tmp,var,copy)\
{ tmp = var; var = poly_copy(copy); tmp->prev = var; var->next = tmp; }
/*STRUCTURE DECLARATION*/
typedef struct poly_t *pointer;
typedef struct poly_t{
pointer prev; //Points the prev element of the list
long coeff;
long exponent;
pointer next; //Points the next element of the list (Double-linked list)
}poly;
/*PROTOTYPE FUNCTIONS*/
poly_t* string_to_struct(const char*); //takes a part of the string and save it as a poly structure
char* short_string(const char*,int); //makes the string shorter (ignoring spaces before and after)
char* next_element(const char* string); //returns the next element of the string
poly_t* poly_copy(poly_t*); //copies one element of the list of polynoms
poly_t* poly_copy_all(poly_t*); //copies all the element of the list of polynoms
poly_t* max_deg (poly_t*); //returns the element with the higher exponent
/*FUNCTION NEW POLY*/
poly_t* new_poly_from_string(const char* string)
{
poly_t *new = NULL;
poly_t *tmp = NULL;
char* s;
EMALLOC(char,s,strlen(string)+1);
s = strcpy(s,string);
char* poly_el;
while(strlen(s) > 0)
{
poly_el = next_element(s);
if(new == NULL)
new = string_to_struct(poly_el);
else
{
tmp = new;
new = string_to_struct(poly_el);
tmp->next = new;
new->prev = tmp;
}
s = short_string(s,strlen(poly_el));
}
free(poly_el);
free(s);
free_poly(tmp);
return new;
}
/*FUNCTION ADD*/
poly_t* add(poly_t* poly1, poly_t* poly2)
{
poly_t *add_poly = NULL;
poly_t *tmp = NULL;
poly_t *poly1_copy = poly_copy_all(poly1);
poly_t *poly2_copy = poly_copy_all(poly2);
//Handle extrem cases
if(poly1==NULL)
return poly2_copy;
else if(poly2==NULL)
return poly1_copy;
else if( (poly1 == NULL)&&(poly2 == NULL) )
return NULL;
//Algorithm
poly_t *max1 = max_deg(poly1_copy);
poly_t *max2 = max_deg(poly2_copy);
while( (max1->exponent != -1)||(max2->exponent != -1) )
{
if(max1->exponent > max2->exponent)
{
if(add_poly == NULL)
add_poly = poly_copy(max1);
else
PASS_NEXT(tmp,add_poly,max1)
max1->exponent = -1;
}
else if(max2->exponent > max1->exponent)
{
if(add_poly == NULL)
add_poly = poly_copy(max2);
else
PASS_NEXT(tmp,add_poly,max2)
max2->exponent = -1;
}
else
{
if(add_poly == NULL)
add_poly = poly_copy(max2);
else
PASS_NEXT(tmp,add_poly,max2)
add_poly->coeff += max1->coeff;
max1->exponent = -1;
max2->exponent = -1;
}
max1 = max_deg(poly1_copy);
max2 = max_deg(poly2_copy);
}
free_poly(poly1_copy);
free_poly(poly2_copy);
while(add_poly->next!=NULL)
add_poly = add_poly->next;
return add_poly;
}
/*FUNCTION MUL*/
poly_t* mul(poly_t* poly1, poly_t* poly2){
poly_t* mul_poly = NULL;
poly_t *poly1_copy = poly_copy_all(poly1);
while(poly1_copy != NULL)
{
poly_t *poly2_copy = poly_copy_all(poly2);
while(poly2_copy != NULL)
{
poly_t *tmp = poly_copy(poly1_copy);
tmp->exponent += poly2_copy->exponent;
tmp->coeff *= poly2_copy->coeff;
mul_poly = add(mul_poly,tmp);
free(tmp);
if(poly2_copy->prev == NULL)
{
poly_t *trash;
trash = poly2_copy;
poly2_copy = NULL;
free_poly(trash);
}
else
poly2_copy = poly2_copy->prev;
}
if(poly1_copy->prev == NULL)
{
poly_t *trash;
trash = poly1_copy;
poly1_copy = NULL;
free_poly(trash);
}
else
poly1_copy = poly1_copy->prev;
free_poly(poly2_copy);
}
free_poly(poly1_copy);
return mul_poly;
}
/*FUNCTION FREE_POLY*/
void free_poly(poly_t* poly){
poly_t* p = poly;
poly_t* q;
if(p->next == NULL){
while(p !=NULL){
q = p->prev;
free(p);
p = q;
}
}
else{
while(p !=NULL){
q = p->next;
free(p);
p = q;
}
}
free(q);
}
/*FUNCTION PRINT_POLY*/
void print_poly(poly_t* poly)
{
poly_t *temp = poly;
if(temp == NULL)
{
printf("Null polynomial\n");
return;
}
while (temp != NULL)
{
if(temp->coeff == 0)
continue;
if(temp->coeff < 0)
printf("- ");
if( ((temp->next!=NULL)&&(temp->coeff > 0))||(temp->prev==NULL) )
printf("+ ");
if( (abs(temp->coeff) > 1)||((abs(temp->coeff)==1)&&(temp->exponent == 0)))
printf("%d ",abs(temp->coeff));
if(temp->exponent == 1)
printf("x ");
else if(temp->exponent > 1)
printf("x^%ld ",temp->exponent);
else
printf(" ");
temp = temp->prev;
}
printf("\n");
free_poly(temp);
}
/*OTHER FUNCTIONS*/
poly_t* string_to_struct(const char *poly_el_string)
{
poly_t * poly_el_struct = NULL;
if(strlen(poly_el_string) <= 1)
return poly_el_struct;
EMALLOC(poly_t,poly_el_struct,1);
poly_el_struct->prev = NULL;
poly_el_struct->next = NULL;
char c;
int i = 0;
int rank = 0;
if(isdigit(c = poly_el_string[i]))
{
double buff = 0;
while((i < strlen(poly_el_string))&&(isdigit(c = poly_el_string[i++])))
buff += (c-'0')*pow(10,rank++);
if( (i < strlen(poly_el_string))&&(c == '^') )
{
poly_el_struct->exponent = buff;
i++;
rank = 0;
if(!isdigit(c = poly_el_string[i]))
poly_el_struct->coeff = 1;
else
poly_el_struct->coeff = 0;
while((i < strlen(poly_el_string))&&(isdigit(c = poly_el_string[i++])))
poly_el_struct->coeff += (long)(c-'0')*pow(10,rank++);
if((i < strlen(poly_el_string))&&(c == '-'))
poly_el_struct->coeff = - poly_el_struct->coeff;
}
else
{
poly_el_struct->coeff = buff;
poly_el_struct->exponent = 0;
}
free(&buff);
}
else
{
i++;
poly_el_struct->coeff = 0;
while((i < strlen(poly_el_string))&&(isdigit(c = poly_el_string[i++])))
poly_el_struct->coeff += (long) (c-'0')*pow(10,rank++);
if(c == '-')
poly_el_struct->coeff *= -1;
poly_el_struct->exponent = 1;
}
free(&c);
free(&i);
free(&rank);
return poly_el_struct;
}
char* next_element(const char* string){
int i = strlen(string)-1;
char c;
char *el;
//EMALLOC(char,el,1);
el = malloc(sizeof(char)+1);
if(el==NULL)
printf("ERROR : out of memory. \nmalloc failed");
int j = 0;
while(i > -1)
{
c = string[i--];
if(isspace(c))
continue;
el[j] = c;
EREALLOC(char,el,++j);
if( (c == '+')||(c == '-') )
break;
}
*(el+j) = '\0';
free(&c);
free(&i);
return el;
}
char* short_string(const char *s_old, int l){
char *s_new = NULL;
int spaces = 0;
if( (strlen(s_old) != l) )
{
if(strlen(s_old) != l+1)
spaces = 2;
else
spaces = 1;
}
int new_l = strlen(s_old)-l-spaces ;
//EMALLOC(char,s_new,new_l)
s_new = malloc(new_l*sizeof(char));
if(s_new==NULL)
printf("ERROR : out of memory. \nmalloc failed");
strncpy(s_new,s_old,new_l);
s_new[new_l] = '\0';
free(&spaces);
free(&new_l);
return s_new;
}
poly_t* max_deg(poly_t *poly){
poly_t *max = poly;
while( (poly != NULL)&&(poly->prev != NULL) )
{
if(poly->exponent < (poly->prev)->exponent)
max = poly->prev;
poly = poly->prev;
}
return max;
}
poly_t* poly_copy_all(poly_t *poly){
poly_t *copy = NULL;
poly_t *tmp = NULL;
if(poly == NULL)
return NULL;
if(poly->next == NULL)
{
while(poly != NULL)
{
if(copy == NULL)
copy = poly_copy(poly);
else
{
tmp = copy;
copy = poly_copy(poly);
tmp->prev = copy;
copy->next = tmp;
}
poly = poly->prev;
}
while(copy->next != NULL)
copy = copy->next;
}
else
{
while(poly != NULL)
{
if(copy == NULL)
copy = poly_copy(poly);
else
{
tmp = copy;
copy = poly_copy(poly);
tmp->next = copy;
copy->prev = tmp;
}
poly = poly->prev;
}
while(copy->prev != NULL)
copy = copy->prev;
}
free_poly(tmp);
return copy;
}
poly_t* poly_copy(poly_t *poly){
poly_t *cpy;
//EMALLOC(poly_t,cpy,1);
cpy = malloc(sizeof(poly_t));
if(cpy==NULL)
printf("ERROR : out of memory. \nmalloc failed");
else{
cpy->coeff = poly->coeff;
cpy->exponent = poly->exponent;
cpy->next = NULL;
cpy->prev = NULL;
}
return cpy;
}
