Thread: Segmentation Fault :: Insertionsort Pointers

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.

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);
    }
}

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.

Originally Posted by grumpy

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.

...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!).

@ 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!