Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Jun 13th, 2010, 6:13 PM   #1
Abhijit Bose
Newbie
 
Join Date: Jun 2010
Posts: 11
Rep Power: 0 Abhijit Bose is on a distinguished road
weird Allocation/Deallocation error in C code

A simple code to find a convex hull after reading a file storing the input points.

A.In ubuntu 10.04 using latest gcc...
the code runs fine with free() of pop() commented out
if not commented out
crashes at LOC B in code - gives error "*** glibc detected *** ./ConvexHull: free(): invalid next size (fast): 0x0000000001e52390 ***"

B.In windows 7 using Dev-cpp 5 running gcc mingw
crashes at LOC A in code -
windows says "program has stopped working : checking for solution" at malloc() at the first call to push().
I found the location of error using printf() debug codes and gdb backtrace.

Code follows
focus your attention to main(), upper_Hull(),lower_Hull() and Stack functions.
rest are all cool!

#include <stdio.h>
#include <stdlib.h>
#include "QuickSort.h"
#include "Stack.h"
 
struct data{
    double x;
    double y;
};
 
struct node{
    ElementS data;
    PtrToNode next;
};
 
typedef struct data Point2D;
typedef struct data Vector2D;
 
int compare(ElementA p1, ElementA p2);
int right_turn(Vector2D v1, Vector2D v2);
Array init_Points(FILE *input, int size);
void sort_Arr(Array arr, int size);
Stack upper_Hull(Array arr,int size);
Stack lower_Hull(Array arr,int size);
void read_out_Hull(Stack upperHull,Stack lowerHull,FILE *output);
void print_Stack_to_File(Stack s, FILE *output);
 
main(){
    int size;
    Array arr;
 
    FILE *input = fopen("hullMap.txt","r");
    if(!input){
        printf("Error while opening file.\n");
    exit(1);
    }
    fscanf(input,"%d",&size);
    arr = init_Points(input,size);
    fclose(input);
 
    printf("Initialization done!\n");
 
    FILE *output = fopen("hullPoints.txt","w");
    if(!output){
        printf("Error while creating file.\n");
        exit(1);
    }
 
    sort_Arr(arr,size);
    printf("Sorting done!\n");
 
    Stack s1 = upper_Hull(arr,size);
    printf("Upper hull calculated.\n");
 
    Stack s2 = lower_Hull(arr,size);
    printf("Lower hull calculated.\n");
 
    read_out_Hull(s1,s2,output);
    printf("Convex hull calculated.\n");
    fclose(output);
}
 
 
Stack upper_Hull(Array arr,int size){
    int i = 2;
    Vector2D v1, v2;
    Point2D p1, p2, p3;
    Stack upperHull = init_s();
    push(arr[0],&upperHull);
    p2 = arr[1];
    
    while(i<size){
        printf("Checking upper hull for point %d..\n",i - 1);
        p3 =arr[i++];
        while(!empty_s(upperHull)){
            p1 = pop(&upperHull);
            v1.x = p2.x - p1.x;    
            v1.y = p2.y - p1.y;
            v2.x = p3.x - p2.x;
            v2.y = p3.y - p2.y;
            if(right_turn(v1,v2)){
            push(p1,&upperHull);
                break;
            }
            p2 = p1;
        }
        push(p2,&upperHull);
        p2 = p3;
    }
    push(p3,&upperHull);
    return upperHull;    
}
 
Stack lower_Hull(Array arr,int size){
    int i = size-3;
    Vector2D v1, v2;
    Point2D p1, p2, p3;
    Stack lowerHull = init_s();
    push(arr[size-1],&lowerHull);
    p2 = arr[size-2];
 
    while(i>=0){
        p3 =arr[i--];
        printf("Checking lower hull for point %d..\n",i+1);
        while(!empty_s(lowerHull)){
            p1 = pop(&lowerHull);
            v1.x = p2.x - p1.x;    
            v1.y = p2.y - p1.y;
            v2.x = p3.x - p2.x;
            v2.y = p3.y - p2.y;
            if(right_turn(v1,v2)){
            push(p1,&lowerHull);
                break;
            }
            p2 = p1;
        }
        push(p2,&lowerHull);
        p2 = p3;
    }
    push(p3,&lowerHull);
    return lowerHull;    
}
 
 
Stack init_s(){
    return NULL;
}
    
int empty_s(Stack head){
    return head==NULL;
}
 
void push(ElementS data,Stack *head){
//LOC A
    PtrToNode target = (PtrToNode)malloc(sizeof(Node));
    if(!target){
        printf("Allocation error!\n");
        exit(1);
    }
    target->data = data;    
    target->next = *head;            
    *head = target;      
}
 
ElementS pop(Stack *head){
    PtrToNode cur = *head;
    ElementS data;
    if(!empty_s(*head)){
        *head = (*head)->next;
        data = cur->data;
//LOC B
        free(cur);
    }
    return data;        
}
        
 
Array init_Points(FILE *input,int size){
    Array arr = (ElementA *)malloc(sizeof(ElementA)*size);
    
    int i;
    
    for(i=0; i<size; i++)
        fscanf(input,"%lf %lf",&arr[i].x,&arr[i].y);
 
    return arr;    
}
    
int right_turn(Vector2D v1, Vector2D v2){
    return (v1.x*v2.y -v2.x*v1.y >= 0)?0:1;      
}
 
void sort_Arr(Array arr, int size){
    quick_sort(arr,0,size);
}
  
void quick_sort(Array arr,int left,int right){
    int i,j;
    ElementA pivot,temp;
    if(right-left<CUTOFF)
        insertion_sort(arr,left,right);
    else{    
        i=left,j=right-1;      
        pivot=set_Pivot_change(arr,left,right);
    
        while(1){
            while(compare(arr[++i],pivot)==-1);//checking from after left val...assured to be less than pivot
            while(compare(arr[--j],pivot)==1);//checking from before val left of pivot at right-1, right val
                              //                                     assured to be greater  
                              //"trail off" condition not possible, set_Pivot_change()
                              //eliminates possibility by ordering left,center and right ElementA
                              //and stopping loop at elements equal to pivot
            if(i<j)
                SWAP(temp,arr[i],arr[j]);
            else
                break;        
        }
        SWAP(temp,arr[i],arr[right-1]);
        quick_sort(arr,left,i-1);
        quick_sort(arr,i+1,right);      
    }
}
  
ElementA set_Pivot_change(Array arr,int left,int right){
    ElementA temp;
    int center=(left+right)/2;
 
    if(compare(arr[left],arr[center])==1)
        SWAP(temp,arr[left],arr[center]);
    if(compare(arr[center],arr[right])==1)
        SWAP(temp,arr[center],arr[right]);
    if(compare(arr[left],arr[center])==1)  
        SWAP(temp,arr[left],arr[center]);//arranging in order left val<=center val<=right val
 
    SWAP(temp,arr[center],arr[right-1]);  //taking pivot out of the way
    return arr[right-1];       //returning pivot
}
 
void insertion_sort(Array arr,int left,int right){
    int i=0,j=0;
    ElementA temp;
    for(i=left+1;i<=right;i++){
        temp=arr[i];
        for(j=i;j>left&&(compare(temp,arr[j-1])==-1);j--)
            arr[j]=arr[j-1];
        arr[j]=temp;
    }  
}      
 
int compare(ElementA p1,ElementA p2){
    if(p1.x<p2.x || (p1.x==p2.x && p1.y<p2.y))
        return -1;
    else if (p1.x>p2.x || (p1.x==p2.x && p1.y>p2.y))
        return 1;
    else return 0;
}

void read_out_Hull(Stack upperHull,Stack lowerHull,FILE *output){
    print_Stack_to_File(upperHull,output);
    pop(&lowerHull);
    Point2D top;
    while(1){
        top = pop(&lowerHull);
        if(empty_s(lowerHull))
            break;
        fprintf(output,"%lf %lf\n",top.x,top.y);        
    }
}
 
void print_Stack_to_File(Stack s, FILE *output){
    if(empty_s(s))
        return;    
    Point2D top = pop(&s);
    print_Stack_to_File(s,output);
    fprintf(output,"%lf %lf\n",top.x,top.y);
}
WEIRD : PROGRAM RUNS CORRECTLY IN UBUNTU WITH FREE() COMMENTED OUT!

googled it. found nothing!
i signed up in this forum for this. please help :\

ps. error at first occurrence of push and pop only. i checked with additional printf s which i have deleted for clarity.
Abhijit Bose is offline   Reply With Quote
Old Jun 13th, 2010, 6:40 PM   #2
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 18 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: weird Allocation/Deallocation error in C code

Quote:
Originally Posted by Abhijit Bose View Post
the code runs fine with free() of pop() commented out
if not commented out

...

B.In windows 7 using Dev-cpp 5 running gcc mingw
crashes at LOC A in code -
windows says "program has stopped working : checking for solution" at malloc() at the first call to push().
These symptoms indicate "undefined behaviour". Undefined behaviour is the result of using code for cases that have not been defined by the specification (e.g. accessing memory that isn't yours, operating on a null pointer, freeing memory that has already been freed, etc...).

When this happens, the result is implementation and environment dependent. The problem could hide itself, crash your program on an irrelevant line, or even create a mutant zombie and send it back in time to destroy you. Google "undefined behaviour".

Quote:
Originally Posted by Abhijit Bose View Post
I found the location of error using printf() debug codes and gdb backtrace.

Code follows
focus your attention to main(), upper_Hull(),lower_Hull() and Stack functions.
rest are all cool!
I don't fully trust that statement. Undefined behaviour may not manifest itself until later on. Consequently, the problem may be in places that you previously (and erroneously) assumed to be okay. To say that "the rest are all cool" could be completely wrong. But, in this case, I agree that the problem is probably your stack functions and/or the data that you are passing it.

My suggestion is to cook up some unit tests for your stack functions. Make a simple 'main' that will create a stack, push a couple things, pop a couple things, and prod the values at each point in the execution. Then add debug print statements to your program's push/pop to check the values that you're passing in.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Old Jun 13th, 2010, 6:50 PM   #3
Abhijit Bose
Newbie
 
Join Date: Jun 2010
Posts: 11
Rep Power: 0 Abhijit Bose is on a distinguished road
Re: weird Allocation/Deallocation error in C code

I say the rest is good cuz they have been tested in multiple environments. So i know for sure!
And I know those are the error location because that's the last instruction run before crashing everytime!
Abhijit Bose is offline   Reply With Quote
Old Jun 13th, 2010, 7:08 PM   #4
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 18 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: weird Allocation/Deallocation error in C code

Quote:
Originally Posted by Abhijit Bose View Post
And I know those are the error location because that's the last instruction run before crashing everytime!
Did you just ignore everything I said?
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Old Jun 13th, 2010, 7:30 PM   #5
Abhijit Bose
Newbie
 
Join Date: Jun 2010
Posts: 11
Rep Power: 0 Abhijit Bose is on a distinguished road
Re: weird Allocation/Deallocation error in C code

LOL dun get angry!
i should have mentioned that it's not undefined behavior...i have checked it vigorously using the same test case...it does not operate on unclaimed memory...proper memory tests are there in the code! you'll get it if you check the code. and the output was spot on with just a line commented out.
if you check the code you'll know why am being so sure.
Abhijit Bose is offline   Reply With Quote
Old Jun 13th, 2010, 8:16 PM   #6
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 8,368
Rep Power: 22 DaWei will become famous soon enoughDaWei will become famous soon enough
Re: weird Allocation/Deallocation error in C code

"Dun" get angry? Dun post here when you dun know the simplest of words. Bathe in the Ganges of certainty.
__________________
Contributor's Corner:
Politically Incorrect
DaWei on Pointers
DaWei is offline   Reply With Quote
Old Jun 14th, 2010, 12:05 AM   #7
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 18 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: weird Allocation/Deallocation error in C code

Quote:
Originally Posted by Abhijit Bose View Post
if you check the code you'll know why am being so sure.
If you follow my suggestions you might see why I am so sure.

Incidentally, me finding the source of the undefined behaviour for you requires a look into "Stack.h", to determine sizeof(Node) for 'push' (among other potential threats).
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.

Last edited by Sane; Jun 14th, 2010 at 12:18 AM.
Sane is offline   Reply With Quote
Old Jun 14th, 2010, 4:25 AM   #8
Abhijit Bose
Newbie
 
Join Date: Jun 2010
Posts: 11
Rep Power: 0 Abhijit Bose is on a distinguished road
Re: weird Allocation/Deallocation error in C code

Quote:
Originally Posted by Sane View Post
If you follow my suggestions you might see why I am so sure.

Incidentally, me finding the source of the undefined behaviour for you requires a look into "Stack.h", to determine sizeof(Node) for 'push' (among other potential threats).
Oh yes, I am so sorry! it was 4 am in the morning when i posted it and god knows what i was thinking!

here

stack.h

typedef struct data ElementS;

#ifndef _Stack_H

#define _Stack_H

        struct node;

        typedef struct node Node;

        typedef Node *PtrToNode;

        typedef PtrToNode Stack;



        Stack init_s();//initialize a stack

        int empty_s(Stack head);//check whether stack is empty

        void push(ElementS data,Stack *head);//insert on top of stack

        ElementS pop(Stack *head);//delete and return top of stack

#endif
Abhijit Bose is offline   Reply With Quote
Old Jun 14th, 2010, 4:29 AM   #9
Abhijit Bose
Newbie
 
Join Date: Jun 2010
Posts: 11
Rep Power: 0 Abhijit Bose is on a distinguished road
Re: weird Allocation/Deallocation error in C code

Forget that i ever mentioned that word "dun". I "did not" see a sign telling me shorthands are strictly prohibited.
Abhijit Bose is offline   Reply With Quote
Old Jun 14th, 2010, 7:33 AM   #10
Abhijit Bose
Newbie
 
Join Date: Jun 2010
Posts: 11
Rep Power: 0 Abhijit Bose is on a distinguished road
Re: weird Allocation/Deallocation error in C code

Quote:
Originally Posted by Sane View Post
If you follow my suggestions you might see why I am so sure.

Incidentally, me finding the source of the undefined behaviour for you requires a look into "Stack.h", to determine sizeof(Node) for 'push' (among other potential threats).
problem solved!
it was the lamest off by one error. thanks for your time

http://ubuntuforums.org/showthread.php?t=1509014
Abhijit Bose is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Incorporating javascript code into java application csrocker101 Java 1 Feb 11th, 2008 7:36 AM
S&K Trees, Differences In Code And Speed Sane C 6 Feb 7th, 2008 7:51 PM
How to post code Ancient Dragon C 3 Dec 5th, 2007 9:24 AM
How to post code Ancient Dragon C++ 0 Dec 4th, 2007 6:15 PM
What is wrong with this code? c0ldshadow Visual Basic .NET 5 Dec 5th, 2005 6:37 PM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 7:32 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC