Thread: EXC_BAD_ACCESS error help

Theres a lot of code here sorry but idt you need to look at it all.

Code:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct BigInt{
    int digits;
    struct BigInt *next;
}BigInt;

struct integer{
    int *digits;
    int size;
};

    //needed prototypes
//turns character array into a BigInt
BigInt* makeBigInt(char *stringInt);
//prints BigInt
void printBigInt(BigInt *p);
//multiply two BigInts
BigInt *multiply(BigInt *p, BigInt *q);

struct integer *destroy_integer(struct integer *p){
    free(p->digits);
    free(p);
    return NULL;
}

//frees a linked list (still need to test)
void freeLinkedList(BigInt *p){
    if(p->next)                               //error is occurring in this line
        freeLinkedList(p->next);
    free(p);
}

//Assumes linked list has one element
//and converts to a struct integer array
//still needs testing!
struct integer *convertLLtoArray(BigInt *head){
    BigInt *tmp1, *tmp2;
    tmp1 = tmp2 = head;
    int n = 1, i;
    for ( ; tmp1->next != NULL; tmp1 = tmp1->next)
        n++;
    struct integer *array = malloc(sizeof(struct integer));
    array->digits = malloc(sizeof(int) * n);
    array->size = n;
    for (i = 0; i < n; i++) {
        array->digits[i] = tmp2->next->digits;
        tmp2 = tmp2->next;
    }
    tmp1 = head;
    freeLinkedList(tmp1);
    tmp2 = head;
    freeLinkedList(tmp2);
    return array;
}

//convert struct integer array to LL
//returns the head of the ll
//still needs testing!
BigInt *convertArraytoLL(struct integer *p){
    BigInt *head, *tmp, *dubTmp;
    int i;
    head = malloc(sizeof(BigInt));
    dubTmp = malloc(sizeof(BigInt));
    head->next = dubTmp;
    for (i = 0; i <= p->size; i++) {
        //find a way to test this along
        //with the other convert function
        tmp = malloc(sizeof(BigInt));
        tmp->digits = p->digits[i];
        tmp->next = dubTmp;
        dubTmp = tmp;
    }
    freeLinkedList(tmp);
    return head;
}

/**************************************/
void printBigInt(BigInt *p){
    struct integer *q;
    q = malloc(sizeof(struct integer));
    q = convertLLtoArray(p);
    int i;
    for (i = q->size - 1; i >= 0; i--)
        printf("%d", q->digits[i]);
    destroy_integer(q);
}

void print(struct integer *p){
    int i;
    for (i = p->size - 1; i >= 0; i--)
        printf("%d", p->digits[i]);
}

/**************************************/
BigInt* makeBigInt(char *stringInt){
    int i;
    
    struct integer *p = malloc(sizeof(struct integer));
    
    p->size = strlen(stringInt);
    p->digits = malloc(sizeof(int) * p->size);
    
    for (i = 0; i < p->size; i++)
        p->digits[i] = stringInt[p->size - 1 - i] - '0';
    //convert array to ll
    BigInt *head;
    head = convertArraytoLL(p);
    
    return head;
}

struct integer *convert_integer(char *stringInt){
    int i;

    struct integer *p = malloc(sizeof(struct integer));

    p->size = strlen(stringInt);
    p->digits = malloc(sizeof(int) * p->size);

    for (i = 0; i < p->size; i++)
        p->digits[i] = stringInt[p->size - 1 - i] - '0';

    return p;
}

int isZero(struct integer *p){
    return (p->size == 1 && p->digits[0] == 0);
}

/*************************************/
BigInt *multiply(BigInt *p, BigInt *q){
    struct integer *pArray, *qArray;
    pArray = convertLLtoArray(p);
    qArray = convertLLtoArray(q);
    int i, j, carry;
    
    struct integer *m;
    
    // Terminate early in special case of multiplication by zero
    if (isZero(pArray) || isZero(qArray))
        return makeBigInt("0");
    
    // Create struct to hold product
    m = malloc(sizeof(struct integer));
    m->size = pArray->size + qArray->size;
    m->digits = calloc(m->size, sizeof(int));
    
    // Perform multiplication; don't worry about addition overflows yet
    for (i = 0; i < qArray->size; i++)
        for (j = 0; j < pArray->size; j++)
            m->digits[i + j] += qArray->digits[i] * pArray->digits[j];
    
    // Compensate for addition overflows
    for (i = carry = 0; i < m->size; i++){
        m->digits[i] += carry;
        carry        = m->digits[i] / 10;
        m->digits[i] = m->digits[i] % 10;
    }
    
    // Strip leading zero if it exists
    if (m->digits[m->size - 1] == 0)
        m->size--;
    
    //convert m to a ll
    BigInt *head;
    head = convertArraytoLL(m);
    //memory management
    destroy_integer(pArray);
    destroy_integer(qArray);
    destroy_integer(m);
    return head;
}

struct integer *multiply1(struct integer *p, struct integer *q){
    int i, j, carry;
    
    struct integer *m;
    
    // Terminate early in special case of multiplication by zero
    if (isZero(p) || isZero(q))
        return convert_integer("0");

    // Create struct to hold product
    m = malloc(sizeof(struct integer));
    m->size = p->size + q->size;
    m->digits = calloc(m->size, sizeof(int));

    // Perform multiplication; don't worry about addition overflows yet
    for (i = 0; i < q->size; i++)
        for (j = 0; j < p->size; j++)
            m->digits[i + j] += q->digits[i] * p->digits[j];

    // Compensate for addition overflows
    for (i = carry = 0; i < m->size; i++){
        m->digits[i] += carry;
        carry        = m->digits[i] / 10;
        m->digits[i] = m->digits[i] % 10;
    }

    // Strip leading zero if it exists
    if (m->digits[m->size - 1] == 0)
        m->size--;

    return m;
}

int main(void){
    int N, i;
    char buffer[10001];
    //struct integer *p, *q, *m;
    BigInt *p, *q, *m;
    
    FILE *ifp = fopen("bigint.txt", "r");

    fscanf(ifp, "%d", &N);
    for (i = 1; i <= N; i++){
        fscanf(ifp, "%s", buffer);
        //p = convert_integer(buffer);
        p = makeBigInt(buffer);
        fscanf(ifp, "%s", buffer);
        //q = convert_integer(buffer);
        q = makeBigInt(buffer);
        //m = multiply1(p, q);
        m = multiply(p, q);
        // Problem Output
        printf("Problem #%d: ", i);
        //print(p);
        printBigInt(p);
        printf(" * ");
        //print(q);
        printBigInt(q);
        printf(" = ");
        //print(m);
        printBigInt(m);
        printf("\n");

        // Memory Management
        freeLinkedList(p);
        freeLinkedList(q);
        freeLinkedList(m);
        //p = destroy_integer(p);
        //q = destroy_integer(q);
        //m = destroy_integer(m);
    }

    fclose(ifp);
    return 0;
    
}

lines 53 - 56

Code:

    tmp1 = head;
    freeLinkedList(tmp1);
    tmp2 = head;
    freeLinkedList(tmp2);

tmp1 and tmp2 both point to same place as head. This results in trying to free head twice.

cant believe i over looked that...THANK YOU!

changed those 4 lines to

Code:

freeLinkedList(head);

still getting the same error

Code:

//frees a linked list (still need to test)
void freeLinkedList(BigInt *p){
    if(p->next)                               //error is occurring in this line
        freeLinkedList(p->next);
    free(p);
}
...
//convert struct integer array to LL
//returns the head of the ll
//still needs testing!
BigInt *convertArraytoLL(struct integer *p){
    BigInt *head, *tmp, *dubTmp;
    int i;
    head = malloc(sizeof(BigInt));
    dubTmp = malloc(sizeof(BigInt));
    head->next = dubTmp;
    for (i = 0; i <= p->size; i++) {
        //find a way to test this along
        //with the other convert function
        tmp = malloc(sizeof(BigInt));
        tmp->digits = p->digits[i];
        tmp->next = dubTmp;
        dubTmp = tmp;
    }
    freeLinkedList(tmp);

Your program crashes because you create an infinite loop in convertArraytoLL() ("tmp->next" points to "dubTmp" which points back to "tmp") and then freeLinkedList() desperately tries to find the end of the list but fails because p->next will always be true.

Code:

$ gdb -q ./foo
Reading symbols from ./foo...done.
(gdb) r
Starting program: ./foo 

Program received signal SIGSEGV, Segmentation fault.
0x080485ff in freeLinkedList (p=0x804c228) at foo.c:33
33              freeLinkedList(p->next);
(gdb) bt
#0  0x080485ff in freeLinkedList (p=0x804c228) at foo.c:33
#1  0x08048607 in freeLinkedList (p=0x804c238) at foo.c:33
#2  0x08048607 in freeLinkedList (p=0x804c228) at foo.c:33
#3  0x08048607 in freeLinkedList (p=0x804c238) at foo.c:33
#4  0x08048607 in freeLinkedList (p=0x804c228) at foo.c:33
...

Bye, Andreas

ya i caught that problem today, however, its now giving me the same problem with a different line

Code:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct BigInt{
    int digits;
    struct BigInt *next;
}BigInt;

struct integer{
    int *digits;
    int size;
};

    //needed prototypes
//turns character array into a BigInt
BigInt* makeBigInt(char *stringInt);
//prints BigInt
void printBigInt(BigInt *p);
//multiply two BigInts
BigInt *multiply(BigInt *p, BigInt *q);



struct integer *destroy_integer(struct integer *p){
    free(p->digits);
    free(p);
    return NULL;
}

//frees a linked list (still need to test)
void freeLinkedList(BigInt *p){
    if(p == NULL)
        freeLinkedList(p->next);
    free(p);
}

//Assumes linked list has one element
//and converts to a struct integer array
//still needs testing!
struct integer *convertLLtoArray(BigInt *head){
    BigInt *tmp, *tmp2;
    tmp = tmp2 = head;
    int n = 1, i;
    while(tmp != NULL){
        n++;
        tmp = tmp->next;        /*ERROR IN THIS LINE HERE*/
    }
    struct integer *array = malloc(sizeof(struct integer));
    array->digits = malloc(sizeof(int) * n);
    array->size = n;
    for (i = 0; i < n; i++) {
        array->digits[i] = tmp2->digits;
        tmp2 = tmp2->next;
    }
    freeLinkedList(head);
    return array;
}

//convert struct integer array to LL
//returns the head of the ll
//still needs testing!
BigInt *convertArraytoLL(struct integer *p){
    BigInt *tmp, *dubTmp;
    int i;
    dubTmp = malloc(sizeof(BigInt));
    for (i = 0; i <= p->size; i++) {
        //find a way to test this along
        //with the other convert function
        tmp = malloc(sizeof(BigInt));
        tmp->digits = p->digits[i];
        tmp->next = dubTmp->next;
        dubTmp = tmp;
        tmp->next = NULL;
        freeLinkedList(tmp);
    }
    dubTmp->next = NULL;
    return dubTmp; //or return head;
}

/**************************************/
void printBigInt(BigInt *p){
    if (p == NULL)
        return;
    printBigInt(p->next);
    printf("%d", p->digits);
}

void print(struct integer *p){
    int i;
    for (i = p->size - 1; i >= 0; i--)
        printf("%d", p->digits[i]);
}

/**************************************/
BigInt* makeBigInt(char *stringInt){
    int i;
    
    struct integer *p = malloc(sizeof(struct integer));
    
    p->size = strlen(stringInt);
    p->digits = malloc(sizeof(int) * p->size);
    
    for (i = 0; i < p->size; i++)
        p->digits[i] = stringInt[p->size - 1 - i] - '0';
    //convert array to ll
    BigInt *head;
    head = convertArraytoLL(p);
    destroy_integer(p);
    return head;
}

struct integer *convert_integer(char *stringInt){
    int i;

    struct integer *p = malloc(sizeof(struct integer));

    p->size = strlen(stringInt);
    p->digits = malloc(sizeof(int) * p->size);

    for (i = 0; i < p->size; i++)
        p->digits[i] = stringInt[p->size - 1 - i] - '0';

    return p;
}

int isZero(struct integer *p){
    return (p->size == 1 && p->digits[0] == 0);
}

/************************************/
BigInt *multiply(BigInt *p, BigInt *q){
    struct integer *pArray, *qArray;
    pArray = convertLLtoArray(p);
    qArray = convertLLtoArray(q);
    int i, j, carry;
    
    struct integer *m;
    
    // Terminate early in special case of multiplication by zero
    if (isZero(pArray) || isZero(qArray))
        return makeBigInt("0");
    
    // Create struct to hold product
    m = malloc(sizeof(struct integer));
    m->size = pArray->size + qArray->size;
    m->digits = calloc(m->size, sizeof(int));
    
    // Perform multiplication; don't worry about addition overflows yet
    for (i = 0; i < qArray->size; i++)
        for (j = 0; j < pArray->size; j++)
            m->digits[i + j] += qArray->digits[i] * pArray->digits[j];
    
    // Compensate for addition overflows
    for (i = carry = 0; i < m->size; i++){
        m->digits[i] += carry;
        carry        = m->digits[i] / 10;
        m->digits[i] = m->digits[i] % 10;
    }
    
    // Strip leading zero if it exists
    if (m->digits[m->size - 1] == 0)
        m->size--;
    
    //convert m to a ll
    BigInt *head;
    head = convertArraytoLL(m);
    //memory management
    destroy_integer(pArray);
    destroy_integer(qArray);
    destroy_integer(m);
    return head;
}

struct integer *multiply1(struct integer *p, struct integer *q){
    int i, j, carry;
    
    struct integer *m;
    
    // Terminate early in special case of multiplication by zero
    if (isZero(p) || isZero(q))
        return convert_integer("0");

    // Create struct to hold product
    m = malloc(sizeof(struct integer));
    m->size = p->size + q->size;
    m->digits = calloc(m->size, sizeof(int));

    // Perform multiplication; don't worry about addition overflows yet
    for (i = 0; i < q->size; i++)
        for (j = 0; j < p->size; j++)
            m->digits[i + j] += q->digits[i] * p->digits[j];

    // Compensate for addition overflows
    for (i = carry = 0; i < m->size; i++){
        m->digits[i] += carry;
        carry        = m->digits[i] / 10;
        m->digits[i] = m->digits[i] % 10;
    }

    // Strip leading zero if it exists
    if (m->digits[m->size - 1] == 0)
        m->size--;

    return m;
}

int main(void){
    int N, i;
    char buffer[10001];
    //struct integer *p, *q, *m;
    BigInt *p, *q, *m;
    
    FILE *ifp = fopen("bigint.txt", "r");
    
    fscanf(ifp, "%d", &N);
    
    for (i = 1; i <= N; i++){
        fscanf(ifp, "%s", buffer);
        //p = convert_integer(buffer);
        p = makeBigInt(buffer);
        //printBigInt(p);
        fscanf(ifp, "%s", buffer);
        //q = convert_integer(buffer);
        q = makeBigInt(buffer);
        //m = multiply1(p, q);
        m = multiply(p, q);
        // Problem Output
        printf("Problem #%d: ", i);
        //print(p);
        printf(" * ");
        //print(q);
        printBigInt(q);
        printf(" = ");
        //print(m);
        printBigInt(m);
        printf("\n");

        // Memory Management
        freeLinkedList(p);
        freeLinkedList(q);
        freeLinkedList(m);
        //p = destroy_integer(p);
        //q = destroy_integer(q);
        //m = destroy_integer(m);
    }

    fclose(ifp);
    return 0;
    
}

Your problem starts here:

Code:

BigInt *convertArraytoLL(struct integer *p){
    BigInt *tmp, *dubTmp;
    int i;
    dubTmp = malloc(sizeof(BigInt));
    for (i = 0; i <= p->size; i++) {
        //find a way to test this along
        //with the other convert function
        tmp = malloc(sizeof(BigInt));
        tmp->digits = p->digits[i];
        tmp->next = dubTmp->next;
        dubTmp = tmp;
        tmp->next = NULL;
        freeLinkedList(tmp);
    }

It helps to go through these lines step by step:
1) You allocate memory for "dubTmp"
First Iteration:
2) You allocate memory for "tmp"
3) "tmp->next" should point to "dubTmp->next" and Crash Boom Bang!
Where does "dubTmp->next" points to? To garbage.

But suppose "dubTmp->next" was ok and continue:
4) "dubTmp" points to "tmp", i.e. you throw away the memory you have allocated earlier -> you leak memory
5) "tmp->next" points to NULL, i.e. the assignment from 3) is thrown away too.
6) freeLinkedList(tmp) doesn't just free "tmp" but since in 4) you assigned "tmp" to "dubTmp" both pointers would point to invalid memory if freeLinkedList() would succeed (which is unlikely)

All in all it seems you do not really know where your pointers should point to.

I also don't understand why you convert arrays to linked lists and back to arrays.

Bye, Andreas