Thread: Some help please ? :)

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    5

    Some help please ? :)

    Hi all,

    My code will only run on arrays that are 4, 8, 16... in size, and i can't understand why. it crashes at runtime when running on arrays whose size is 5 or 6 for example.

    Any help is welcomed.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    /*
    pointerSort:
    -----------
    Description:    Sorts an array of pointers based on the values of the integers
                    they are pointing to.
    Input:            int* arr - The array that will be used to sort the pointers by.
                    int size - The size of the above array.
    Output:            int** - Returns a sorted pointer array. 
    */
    int** pointerSort(int* arr, int size);
    
    /*
    mergeSort:
    ----------
    Description:    Sort an pointer array recursively.
    Input:            int** pointArr - The array of pointers that will be sorted.
                    int size - The size of the above array.
    Output:            int** pointArr - A sorted pointer array.
    */
    void mergeSort(int** pointArr, int size);
    
    /*
    mergeArrays:
    ------------
    Description:    Merges 2 given pointer arrays into a third array, while sorting them.
    Input:            int** arr1 - The first pointer array to merge.
                    int size1 - The size of the above array.
                    int** arr2 - The second pointer array to merge with the first.
                    int size2 - The size of the above array.
                    int** resultArr - The resulting array, a sorted merge of arr1 and arr2.
    Output:            int** resultArr - A sorted pointer array. 
    */
    void mergeArrays(int** arr1, int size1, int** arr2, int size2, int** resultArr);
    
    /*
    copyArr:
    --------
    Description:    Copies the values of one array to another.
    Input:            int** destArr - The array who's data will be overwritten.
                    int** srcPArr - The array to copy from.
                    int size - The size of both of the above arrays.
    Output:            int** destArr - Will now have new values.
    */
    void copyArr(int** destArr, int** srcPArr, int size);
    
    
    void main(){
        int nums[8] = { 7, 2, 5, 9, 6, 13, 1, 19 };
        int** resultArr;
        int size, i;
        size = 8;
        resultArr = pointerSort(nums, size);
        for ( i = 0 ; i<size ; i++ )
            printf("%d, ", *resultArr[i]);
    }
    
    
    int** pointerSort(int* arr, int size){
        int i;
        int **pArr;
        pArr = (int**)malloc(size * sizeof(int));
        if (pArr != NULL){
            for ( i = 0 ; i < size ; i++ )
                pArr[i] = &arr[i];
            mergeSort(pArr, size);    
        }
        return pArr;
    }
    
    
    void mergeSort(int** pointArr, int size){
        int** tempPArr;
        if (size == 1)
            return;
        else{
            mergeSort(pointArr, size/2);
            mergeSort(pointArr + size/2, size/2);
            tempPArr = (int**)malloc(size*sizeof(int));
            if (tempPArr != NULL){
                mergeArrays(pointArr, size/2, pointArr+size/2, size/2, tempPArr);
                copyArr(pointArr, tempPArr, size);
                free(tempPArr);
            }
        }
    }
    
    
    void mergeArrays(int** arr1, int size1, int** arr2, int size2, int** resultArr){
        int ind1, ind2, write;
        ind1 = ind2 = write = 0;
        while (ind1 < size1 && ind2 < size2){
            if ( *arr1[ind1] <  *arr2[ind2] ){
                resultArr[write] = arr1[ind1];
                write++;
                ind1++;
            }
            else{ // (*arr1[ind1] >=  *arr2[ind2])
                resultArr[write] = arr2[ind2];
                write++;
                ind2++;
            }
        }
        while ( ind1 < size1 ){
            resultArr[write] = arr1[ind1];
            write++;
            ind1++;
        }
        while ( ind2 < size2 ){
            resultArr[write] = arr2[ind2];
            write++;
            ind2++;
        }
    }
    
    
    void copyArr(int** destArr, int** srcPArr, int size){
        int i;
        for ( i = 0 ; i < size ; i++ )
            destArr[i] = srcPArr[i];
    }

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    First of all don't cast malloc in C. Make sure you handle malloc failures with some error message.

    As for your program I would start by debugging the program when your array has a size that makes the program crash. Step through the code and watch the array and indices to see what is happening. If you still can't figure it out, come back here and post any additional observations. This way you will also learn something useful while solving your problem because ultimately that's what you get from all of this.

    EDIT: also void main() is not the correct signature for main. It should be int main(void), having a return 0 when it finishes normally.
    Last edited by claudiu; 03-14-2012 at 06:28 AM. Reason: forgot something
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Why are you copying an array and sorting it? Why don't you just sort the original array?
    Also: the return type of main is int, not void.

    Quote Originally Posted by Roncho View Post
    it crashes at runtime when running on arrays whose size is 5 or 6 for example.
    When I first ran it, it crashed on an array of any size, due to "free(): invalid next size" at line 87.

    The issue starts here.

    Code:
        int **pArr;
        pArr = (int**)malloc(size * sizeof(int));
    But then you act as if you had malloc'd size * sizeof(int*), not sizeof(int). You have allocated an array of ints to an array of int pointers.

    Code:
            for ( i = 0 ; i < size ; i++ )
                pArr[i] = &arr[i];
    An int pointer on a 64-bit system is likely twice as big as an int -- perhaps this is why you had to use the (int**) cast? Anyway, that is what leads to the "invalid next size" issue with free. I'm guessing you are not on a 64-bit system however (keep reading).

    IMO, the mistake is having used an array of pointers at all; all you need to do is swap int values. You are lucky tho: I took all the ** and changed them to *, plus removed the (int**) casts and every instance of the address of operator, &. Guess what? Runs without a hitch on odd or even sized arrays -- except the last number for odd sorted arrays was 0, and one value was missing. Ie, there is still a mistake in it (keep reading).

    Of course, if this were strings, you'd want to be able to swap pointers, so I tried to fix that version too, by changing the mallocs to sizeof(int*). That's when I got a seg fault for odd sized arrays. Here's why:

    Code:
                mergeArrays(pointArr, size/2, pointArr+size/2, size/2, tempPArr);
    You are splitting the array into two even sized chunks. So, eg, a 9 element array would end up as two 4 element arrays, leaving the last element out. With a normal int array, this results in one unsorted, uninitialized value at the end (0, because modern OS's zero out malloc'd memory). With a pointer array, when you try to dereference back in main:

    Code:
        for ( i = 0 ; i<size ; i++ )
            printf("%d, ", *resultArr[i]);
    You get a seg fault for the last iteration of this loop on odd arrays, because the last address value was uninitialized.
    Last edited by MK27; 03-14-2012 at 07:40 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    5
    Thanks for the help.

    I haven't got it right yet, some I'm going to do some more reading on pointers and memory allocation.

    By the way, I've seen a few discussions on the forum about the pros and cons of casting malloc, but if i don't cast malloc - the compiler gives me an error.

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    2,673
    but if i don't cast malloc - the compiler gives me an error.
    Then, because you actually are including stdlib.h (the other cause of such an error), you're compiling this C program as C++ rather than C.

  6. #6
    Registered User
    Join Date
    Mar 2012
    Posts
    5
    I see.

    Iv'e tried to only include <stdio.h> but then i get an "identifier "malloc" is undefined" error.

    What am i doing wrong?

    I'm using visual c++ express, and i've saved the file as FILENAME.c.

  7. #7
    Registered User
    Join Date
    Dec 2007
    Posts
    2,673
    No, you should absolutely include <stdlib.h> for the malloc/calloc/realloc functions.

    I don't use Windows (or haven't in a while), but I was under the impression that if you named the file with a .c extension, it was smart enough to compile it as C. There is another option (a setting somewhere) to force it to compile the code as C, but I can't seem to Google it up. Perhaps someone more versed in VS will come along and help with that.

  8. #8
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Yes, there is an option in VS to compile as C. However, I recommend keeping VS for .NET development and using a more C friendly IDE for good old C development. Pelles or Codeblocks are very good choices, and the level you are programming you don't need 90% of the pork that VS comes with. You will find that you are spending more time on programming, debugging and testing and less time messing around in the labyrinth of IDE options VS provides.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  9. #9
    Registered User
    Join Date
    Mar 2012
    Posts
    5
    Thanks, i'm downloading Codeblocks now. I'll try it.

  10. #10
    Registered User
    Join Date
    Mar 2012
    Posts
    5
    I got it working, thanks for all the help.

Popular pages Recent additions subscribe to a feed