Segmentation Fault :: Insertionsort Pointers

This is a discussion on Segmentation Fault :: Insertionsort Pointers within the C Programming forums, part of the General Programming Boards category; Im pulling my hair out ,, can someone give me feedback on what errors i am making ??? Code: #include ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    2

    Segmentation Fault :: Insertionsort Pointers


    Im pulling my hair out ,, can someone give me feedback on what errors i am making ???

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    using namespace std;
    
    void inssrt(void *akeys, int n, int size, int (*compare) (const void * , const void *))
    {
        register int i,j;
        char *keys;
        char *tmp;
    
        keys= (char *) akeys;
        tmp = (char *) malloc(size*sizeof(char));
        
        for(j=1;j<n;j++) {
        memcpy(tmp,&keys[(j)*size],size);
        i = j - 1;
        while(i >= 0 && (compare(&keys[(i) * size],&keys[(i+1)* size]) < 0)) {
            memcpy(&keys[(i+1) * size], &keys[(i) * size],size);
            i = i - 1;
        }
        memcpy(&keys[(i + 1) * size],tmp,size);
        }
        free ((char *)tmp);
    }
    Last edited by bgreen7887; 02-06-2013 at 03:46 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    It's going to be hard for us to pinpoint your seg fault with just this function. A seg fault is tricky, because it presents itself when an invalid memory access happens, but the cause of that invalid access might be elsewhere (e.g. some other function that corrupts the value in a pointer, a buffer overrun in malloc'ed memory, etc). It would help us if you provided the smallest, compilable program that produces the error, along with the input you gave the program that causes the problem. That would mean, in this case, an input file (or input to type in), a small main function that reads that input and stores it in an array of sorts, and your compare function. Then a quick compile, and we can throw it into a debugger, and find the problem very quickly. Note, you should learn to use a debugger if you haven't yet. You have reached the point in programming where it will be almost necessary, and it's about the most useful tool for a programmer.

    In the mean time, a few smaller problems I see:

    Code:
    using namespace std;
    For one, you're using/posting C++ in a C forum. Pick a language and stick to it. If you want to use C, get rid of this line. If you want to use C++, then there are better ways to implement a generic insertion sort in C++.

    Second, the register keyword is no longer recommended. The compiler has a much better idea of what will produce the fastest code, so just remove that word, and enable optimizations in your compiler, and let it do the work.

    Third, don't cast malloc. Read this: FAQ > Casting malloc - Cprogramming.com.

    Your algorithm appears to be fine at first glance, but it's hard to tell without being able to run it. Again, give us a quick framework for inputting data and testing this, and I can say with more certainty whether your algorithm is good.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    2
    Hey Anduril,
    Thank you for the suggestions im having a little bit of problem setting up the main to run and compile the code. This is an assignment and that parameter list is fixed. So i have to use the "compare" function. This code isn't suppose to be ran alone , its compiled along with 2 other files , which gets turned into an executable using a makefile. Anywho here's updated and corrected so far.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    void inssrt(void *akeys, int n, int size, int (*compare) (const void * , const void *));
    int compare(const void  *x,const void  *y);
    
    int main() 
    {
        int a[] = {2,56,87,1,4};
        int size = 4; //size of int 32bit
        int n = 5;
        inssrt(&a,n,size,/* PROBLEM HERE */);
    }
    
    int compare(const void  *x,const void  *y)
    {
        return(* ((int*)x)-*((int *)y));
    }
    
    void inssrt(void *akeys, int n, int size, int (*compare) (const void * , const void *)) 
    {
        int i,j;
        char *keys;
        char *tmp;
        
        keys= (char *) akeys;
        tmp = (char *) malloc(size*sizeof(char));
        
        for(j=1;j<n;j++) {
        memcpy(tmp,&keys[(j)*size],size);
        i = j - 1;
        while(i >= 0 && (compare(&keys[(i) * size],&keys[(i+1)* size]) < 0)) {
            memcpy(&keys[(i+1) * size], &keys[(i) * size],size);
            i = i - 1;
        }
        memcpy(&keys[(i + 1) * size],tmp,size);
        free ((char *)tmp);
        }
    }

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    My program produces a bit more output than just a seg fault:
    Code:
    $ ./sort
    a is at 0xbfb5ab8c, &a is 0xbfb5ab8c
    *** glibc detected *** ./sort: double free or corruption (fasttop): 0x09632008 ***
    ...
    It looks like you call free multiple times, without re-allocating tmp.

    This is hard to see due to crappy indentation. Good indentation makes it hard to screw up, and easy to find/fix when you do. Get an editor with auto-indent if need be, and let it do it's thing. Most editors have this feature (syntax highlighting is also part of nearly every editor, and equally useful). Both of those will help you spot simple errors like this one. Here is your code with better indentation.
    Code:
    void inssrt(void *akeys, int n, int size, int (*compare) (const void * , const void *))
    {
        int i,j;
        char *keys;
        char *tmp;
    
    
        keys= (char *) akeys;
        tmp = (char *) malloc(size*sizeof(char));
    
    
        for(j=1;j<n;j++) {
            memcpy(tmp,&keys[(j)*size],size);
            i = j - 1;
            while(i >= 0 && (compare(&keys[(i) * size],&keys[(i+1)* size]) < 0)) {
                memcpy(&keys[(i+1) * size], &keys[(i) * size],size);
                i = i - 1;
            }
            memcpy(&keys[(i + 1) * size],tmp,size);
            free ((char *)tmp);
        }
    }
    Note, due to the indentation, it is easy to see that the free is inside the loop, and the malloc outside it. Thus, you are getting multiple frees with one malloc. Move the free to after the for loop.

    EDIT: I just saw that your original post has the free outside the loop, as it should be. That seems to have fixed it.
    Last edited by anduril462; 02-06-2013 at 05:15 PM.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Gah! totally forgot about your /* PROBLEM HERE */ part. Just pass the name of the compare function you wish to use:
    Code:
    inssrt(a, n, size, compare);
    Also, notice that I dropped the & from a. The name of an array, without any [ ], serves as a pointer to the first element, which is what you want to pass. &a is technically a pointer to array of int, which is not the right type. Technically that results in undefined behavior, which means anything could happen, or nothing at all. Best to avoid it, and use the right parameter.

    Lastly, in your test program, you assume size of an int is 4. It's only guaranteed to be at least 4. It may be larger, say 8 on a 64-bit system. Try doing
    Code:
    int size = sizeof(a[0]);
    int n = sizeof(a) / sizeof(a[0]);
    That way, if you change your code to use long, short, float, double, etc, or you change how many elements in a, you wont need to change your size, n, or inssrt call.

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,630
    Quote Originally Posted by anduril462 View Post
    Lastly, in your test program, you assume size of an int is 4. It's only guaranteed to be at least 4.
    Not true. There is no guarantee on the size of an int (except that it must be at least one).

    The standard only articulates constraints on the range of values an int can support. The minimum range is [-32767, 32767], but larger ranges are permitted. Practically, that can equate to a 16-bit int type and - on a machine with 8 bit char types (which is also not actually required) - means sizeof(int) can be 2. There are plenty of implementations (admittedly mostly ageing) that still have sizeof(int) as 2.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Quote Originally Posted by grumpy View Post
    Not true. There is no guarantee on the size of an int (except that it must be at least one).

    The standard only articulates constraints on the range of values an int can support. The minimum range is [-32767, 32767], but larger ranges are permitted. Practically, that can equate to a 16-bit int type and - on a machine with 8 bit char types (which is also not actually required) - means sizeof(int) can be 2. There are plenty of implementations (admittedly mostly ageing) that still have sizeof(int) as 2.
    Duh...I knew all that too, guess I just got sloppy. Thanks for the correction.

  8. #8
    Registered User
    Join Date
    Jun 2011
    Posts
    2,692
    ...on a machine with 8 bit char types (which is also not actually required)
    I've heard this before, but admittedly don't understand how that is. Perhaps my understanding of the standard is wrong, but it seems the number of bits for a byte is at least eight, and the min/max value of a signed char are [-127/127] (or [255] for an unsigned char). (*5.2.4.2.1)

    Your wording in response to anduril462, regarding int sizes, implies that there's no guarantee (i.e. in practice) of meeting the standard, but is constrained (i.e. technically required) by the standard. However, your wording regarding the char types would imply (using the phrase "not required") that there's no constraint for an 8-bit char in the standard.

    Just to be clear, I'm not trying to challenge you, only get a better understanding of this concept. Perhaps I'm misunderstanding the standard, or misunderstanding your post. There's no question in my mind that your knowledge of 'C' hugely trumps my own. That is why I'm seeking clarification. Please correct me if I'm wrong (which I likely am!).

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,630
    Quote Originally Posted by Matticus View Post
    I've heard this before, but admittedly don't understand how that is. Perhaps my understanding of the standard is wrong, but it seems the number of bits for a byte is at least eight, and the min/max value of a signed char are [-127/127] (or [255] for an unsigned char). (*5.2.4.2.1)
    Your understanding of the standard is somewhat flawed. That section states (in effect - I'm paraphrasing) that -127 is an upper bound for SCHAR_MIN (the minimum value for a signed char) and 127 is a lower bound for SCHAR_MAX (the maximum value of a signed char). That requires that a char must be able to support a range of [-127,127] (i.e. all distinct values between -127 and 127 inclusive can be represented). It does not prevent (in fact, it specifically allows for) a char type that supports a larger range of values.

    Similarly, the lower bound for UCHAR_MAX (maximum value for a unsigned char) is 255.

    Quote Originally Posted by Matticus View Post
    Your wording in response to anduril462, regarding int sizes, implies that there's no guarantee (i.e. in practice) of meeting the standard, but is constrained (i.e. technically required) by the standard. However, your wording regarding the char types would imply (using the phrase "not required") that there's no constraint for an 8-bit char in the standard.
    Well, no. A standard would be rather pointless if it was impossible for any implementation (compiler, library, host platform) to comply with it.

    What happens (at least, in this regard) is that the standard explicitly allows implementations certain freedoms, but then imposes constraints on those freedoms.

    There is a requirement in the standard that CHAR_BIT (number of bits for the smallest object that is not a bit field) has a lower bound of 8. That allows an implementation to support an 8-bit char. It does not, however, prevent another implementation from supporting a 9-bit char, or a 16-bit char. It does prevent any implementation from supporting a 4-bit char.

    Formally, the standard states that the value of CHAR_BIT (like INT_MIN, INT_MAX, etc) is implementation defined. The term "implementation defined" is also defined (in another section of the standard) to mean that the standard describes constraints on what an implementation can do (in this case, that CHAR_BIT has a value of at least 8). As long as a implementation honours the constraints, it is compliant with the standard. So, a compiler/library that supports CHAR_BIT with a value of 9 would be compliant with the standard. A compiler/library for which CHAR_BIT was 4 would not comply with the standard.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  10. #10
    Registered User
    Join Date
    Jun 2011
    Posts
    2,692
    @ Grumpy - It turns out I was mistaken in interpreting your message. I thought I've heard people say that a char, on some systems, can be less than eight bits (though perhaps I'm remembering wrongly), and for some reason read your response that way. But I was clearly wrong. My apologies, and thanks for the clarification!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Strcat with pointers and Segmentation Fault
    By thames in forum C Programming
    Replies: 6
    Last Post: 12-02-2012, 06:48 AM
  2. Segmentation fault (strings, pointers, Linux)
    By ankushwrites in forum C Programming
    Replies: 2
    Last Post: 03-25-2012, 01:00 PM
  3. Replies: 8
    Last Post: 04-28-2008, 03:46 AM
  4. Segmentation fault with structs and char pointers
    By Keybone in forum C++ Programming
    Replies: 20
    Last Post: 01-17-2004, 01:36 PM
  5. segmentation fault - pointers/functions
    By p1c1078 in forum C Programming
    Replies: 15
    Last Post: 04-22-2003, 06:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21