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:
Here is my code (quite long, but not really complicated):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.
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; }
Originally Posted by anon
