Savan
Reputation: 171
Delete all nodes in null terminated doubly linked list
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
).
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.
Upvotes: 0
Views: 593
Answers (1)
aghast
Reputation: 15310
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.
Upvotes: 3
Related Questions
- Doubly linked list - Delete the list from memory
- How to delete node in double-linked-list by C programming?
- Delete all nodes linked list
- How to delete nodes in a doubly linked list
- C - Deleting any node from a doubly linked list
- Doubly linked list in C- delete node function
- C : Deleting only one node from a doubly linked list
- Deleting a node from a doubly linked list
- C - deleting node in doubly linked list
- Removing a Node from a Doubly Linked List in C