0

I'm facing a problem while destroying all the nodes in null-terminated doubly linked list (It is a list where 2 pointers head and tail points at the nodes and the first node's prev and last node's next is null).The null-terminated doubly list looks like this
Null terminated doubly linked list).

The code works fine for small input ,but for very large input it gives corrupted size vs prefix size error

>>Input1 : 12312312312123123123123123123123
>>Input2 : 1
>>Addition : 12312312312123123123123123123124
>>Inside Destroy
*** Error in `./savan': corrupted size vs. prev_size: 0x0000000002066c40 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f88ba43a7e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x83781)[0x7f88ba446781]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x179)[0x7f88ba447839]
./savan[0x401073]
./savan[0x401369]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f88ba3e3830]
./savan[0x400749]

This is my code for destroying all the nodes, and the structure defination.

Structure Defination

typedef struct node{
        char ch;
        struct node *next,*prev;
}node;

typedef struct Integer{
        node *p, *q;
}Integer;

Code for destroyInteger

 void destroyInteger(Integer *a){
    node *tmp = NULL;
    printf("Inside Destroy");
        if(a->p == NULL) //if the Integer is empty then do nothing
            return;
        while(a->p->next != NULL){ //while integer's next not null loop
            tmp = a->p;        //assign to temp and free it
            a->p = a->p->next; // move the pointer ahead
            free(tmp);
        }
        tmp = a->p; //for last node or if only one node as it is double null terminated list
        free(tmp);  
        a->p = NULL; //make the integer null as in initInteger
        a->q = NULL;
    }

Integer.c ADT whole code

#include<stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <limits.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include<unistd.h>
#include<string.h>
#include<ctype.h>
#include "integer.h"
void initInteger(Integer *a){
    a->p = NULL;
    a->q = NULL;
}

void addDigit(Integer *a, char c){
    node *temp;
    if(isdigit(c)){
        temp = (node*)malloc(sizeof(node));
        temp->ch = c;
        temp->next = NULL;
        if(a->p == NULL){
            temp->prev = NULL;
            a->p = temp;
            a->q = temp;
        }
        else{
            a->q->next = temp;
            temp->prev = a->q;  
            a->q = temp;
        }
    }
    else
        return;
}
void printInteger(Integer a){
    char c;
    if(a.p == NULL){
        printf("0\n");
        return;
    }
    while(a.p->next != NULL){
        c = a.p->ch;
        putchar(c);
        a.p = a.p->next;
    }
    c = a.p->ch;
    putchar(c);
    putchar('\n');
}
Integer createIntegerFromString(char *str){
    int i = 0, flag = 0;
    char ch;
    Integer res;
    initInteger(&res);
    while(*(str + i) != '\0'){
        if(isdigit(*(str + i))){
            ch = *(str + i);
            addDigit(&res, ch);
            flag = 1;
            i++;
        }
        else
            break;          
    }   
    if(flag == 0){
        addDigit(&res, '0');
    }
    return res;
}
Integer addIntegers(Integer a, Integer b){
    Integer c;
    char num1, num2, *revString = (char*)malloc(sizeof(char));
    int n1, n2, carry = 0, counter = 0, sum = 0, flag1 = 0, flag2 = 0, mainflag = 0, i;
    initInteger(&c);
    if(a.p == NULL && b.p == NULL){
        addDigit(&c, '0');
        return c;
    }
    else if(a.p == NULL && b.p != NULL)
        return b;       
    else if(a.p != NULL && b.p == NULL)
        return a;

    else{
        do{     n1 = n2 = 0;
            num1 = num2 = '\0';
            if(a.q->prev == NULL && b.q->prev == NULL)
                mainflag = 1;
            //for a
            if(a.q->prev == NULL && flag1 == 0){
                num1 = a.q->ch;
                n1 = num1 - '0';
                flag1 = 1;
            }
            else if(a.q->prev != NULL){
                num1 = a.q->ch;
                n1 = num1 - '0';
                a.q = a.q->prev;
            }
            else
                n1 = 0;
            //for b
            if(b.q->prev == NULL && flag2 == 0){
                num2 = b.q->ch;
                n2 = num2 - '0';
                flag2 = 1;      
            }
            else if(b.q->prev != NULL){
                num2 = b.q->ch;
                n2 = num2 - '0';
                b.q = b.q->prev;
            }
            else
                n2 = 0; 
            sum = n1 + n2 + carry;
            if(sum >=  10){
                revString[counter++] = (sum % 10) + '0';
                carry = 1;
                sum = 0;
            }
            else{
                revString[counter++] = sum + '0';
                carry = 0;
            }
        revString = (char*)realloc(revString, counter + 1);
        }while(mainflag != 1);
        if(carry == 1){
            revString[counter++] = '1';
        }
        for(i = counter; i > 0; i--){
            addDigit(&c, revString[i-1]);
        }
    }
    free(revString);
    return c;
}
Integer substractIntegers(Integer a, Integer b){
    Integer c;
    char num1, num2, *revString = (char*)malloc(sizeof(char));
    int n1, n2, carry = 0, counter = 0, sum = 0, flag1 = 0, flag2 = 0, mainflag = 0, i, len1, len2;
    len1 = length(a);
    len2 = length(b);
    initInteger(&c);
    if(len1 < len2){
        addDigit(&c, '0');
        return c;
    }
    if(a.p == NULL && b.p == NULL){
        addDigit(&c, '0');
        return c;
    }
    else if(a.p == NULL && b.p != NULL)
        return b;       
    else if(a.p != NULL && b.p == NULL)
        return a;

    else{
        do{     n1 = n2 = 0;
            num1 = num2 = '\0';
            if(a.q->prev == NULL && b.q->prev == NULL)
                mainflag = 1;
            //for a
            if(a.q->prev == NULL && flag1 == 0){
                num1 = a.q->ch;
                n1 = num1 - '0';
                flag1 = 1;
            }
            else if(a.q->prev != NULL){
                num1 = a.q->ch;
                n1 = num1 - '0';
                a.q = a.q->prev;
            }
            else
                n1 = 0;
            //for b
            if(b.q->prev == NULL && flag2 == 0){
                num2 = b.q->ch;
                n2 = num2 - '0';
                flag2 = 1;      
            }
            else if(b.q->prev != NULL){
                num2 = b.q->ch;
                n2 = num2 - '0';
                b.q = b.q->prev;
            }
            else
                n2 = 0; 
            sum = n1 - n2 - carry;
            if(sum <  0){
                sum += 10;
                revString[counter++] = sum  + '0';
                carry = 1;
                sum = 0;
            }
            else{
                revString[counter++] = sum + '0';
                carry = 0;
            }
        revString = (char*)realloc(revString, counter);
        }while(mainflag != 1);

        if(carry == 1){
            revString[counter++] = '1';
        }
        for(i = counter; i > 0; i--){
            addDigit(&c, revString[i-1]);
        }
    }
    free(revString);
    return c;
}
int length(Integer l) {
    int len = 0;
    node *tmp;
    tmp = l.p;
    if(!tmp)
        return 0;
    while(tmp->next != NULL){
        tmp = tmp->next;
        len++;
    }
    return len+1;
}
void destroyInteger(Integer *a){
    node *tmp = NULL;
    if(a->p == NULL)
        return;
    while(a->p->next != NULL){
        tmp = a->p;
        a->p = a->p->next;
        free(tmp);
    }
    tmp = a->p;
    a->p = NULL;
    a->q = NULL;
    free(tmp);
}

Main.c for calling and also i have integer.h which is in other file

Integer a, b, c;
    char ch;
    char str[64]; /* This size may change */

    initInteger(&a);
    initInteger(&b);

    while((ch = getchar()) != '\n')
        addDigit(&a, ch);
    scanf("%s", str);
    b = createIntegerFromString(str);
    c = addIntegers(a, b); 
    printInteger(c);
    destroyInteger(&c);

Integer.h file

typedef struct node{
    char ch;
    struct node *next,*prev;
}node;

typedef struct Integer{
    node *p, *q;
}Integer;

/*Functions*/
void initInteger(Integer *a);
void addDigit(Integer *a, char c);
void printInteger(Integer a);
Integer createIntegerFromString(char *str);
Integer addIntegers(Integer a, Integer b);
Integer substractIntegers(Integer a, Integer b);
void destroyInteger(Integer *a);
int length(Integer a);

Any help would be appreciated.Thank you.

Improve this question
22
  • You probably have memory corruption elsewhere. Commented Sep 17, 2017 at 3:10
  • My code works fine without destroyInteger @BLUEPIXY . Commented Sep 17, 2017 at 3:11
  • Where are you detecting the corruption? Your code doesn't match the output you show. Can you provide the rest of the code? Commented Sep 17, 2017 at 3:16
  • 1
    My code works fine : I think it is doubtful. Commented Sep 17, 2017 at 3:18
  • @AustinHastings the corruption is in destroyInteger,i have updated the code ,removed the printf Commented Sep 17, 2017 at 3:20

1 Answer 1

Reset to default
3

One thing I did notice is this code in addIntegers:

else if(a.p == NULL && b.p != NULL)
    return b;

If you set 

c = addIntegers(a, b)

This code will make c a copy of b, but both c and b will point to the same nodes. If you then destroy c (or b), the other one will have pointers to released memory, which is a recipe for failure.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Also, I'd suggest that once you have this fixed, you submit it to codereview for further cleanup.
Yes you are right ,about that i din't noticed it.Anyways the part is only executed if my first input i.e a is null.My problem is im providing both the input's the calculations are correct but when i free the Integer c with destroyInteger im getting that error of corrupt memory
It's also true the other way, since there's a clause for the reverse case. But still it doesn't seem to affect the example you showed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.