Segmentation fault (core dumped) error, in a C search function

Question

I'm trying to write a C program to take an array of discrete positive integers and find the length of the longest increasing subsequence.

'int* a' is the array of randomly generated integers, which is of length 'int b'

call: lis_n = answer(seq, seq_size);

function:

int answer(int* a, int b) {
    if (a == NULL) {return -1;}
    int i = 0;
    int j = 0;
    int k = 0;
    //instantiate max and set it to 0
    int max = 0;
    //make an array storing all included numbers
    int included[b];
    memset(included, 0, b*sizeof(int));
    //create a pointer to the index in included[] with the largest value
    int indexMax = 0;
    //create a pointer to the index in a[]
    int indexArray = 0;
    //index of a[] for max included
    int maxToA = 0;
    //set the first included number to the first element in a[]
    included[indexMax] = a[indexArray];
    //loop until break
    while (1) {
        if (a[indexArray] > included[indexMax]/*digit greater than last included*/) {
            //include the digit
            included[indexMax+1] = a[indexArray];
            //increment current max pointer
            indexMax++;
        }
        j = b - 1;
        while (indexArray >= j/*pointer is at end"*/) {
            if (j == (b - 1)) {
                if ((indexMax+1) > max/*total is greater than current max*/) {
                    max = indexMax + 1;
                }
            }
            if (a[b-1] == included[0]/*last element is in included[0], stop*/) {
                return max;
            } else {
                //max included is set to zero
                included[indexMax] = 0;
                //max included pointer decreased
                indexMax--;
                //set array pointer to new max included
                for (k=0;k<(b-1);k++) {
                    if (a[k] == included[indexMax]) {
                        indexArray = k;
                    }
                }
                //increment array pointer
                indexArray++;
                j--;
            }
        }
        indexArray++;

        printf("(");
        for (i=0;i<b;i++) {
            printf("%d,",included[i]);
        }
        printf(")");
    }
}

I'm receiving 'Segmentation fault (core dumped)' in the terminal upon running.

Any help would be awesome.

I haven't read your program, but just from glancing at it I can see it uses quite a few arrays. A segfault could possibly occur from trying to read outside the bounds of an array (sometimes this is the classic "off by one" error). I would check to make sure your program isn't trying to read outside the max length of an array somewhere. Also, look into debugging. Google "debug a seg fault with gdb". — nanny
Program received signal SIGSEGV, Segmentation fault. 0x0000000000400add in answer (a=0x602010, b=4) at prog3A.c:129 warning: Source file is more recent than executable. 129 indexMax--; Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.80.el6.x86_64 — Tom

Weather Vane Weather Vane · Accepted Answer · 2014-11-06T16:53:55

You have declared

int indexMax = 0;

And here you use it as an array index

incuded[indexMax] = 0;

You increment and decrement it

indexMax++;
...
indexMax--;

You check its range but you don't limit it, you alter the value you compare it with

if ((indexMax+1) > max/*total is greater than current max*/) {
                max = indexMax + 1;
}

You never check indexMax against b or with 0

int included[b];

So you are almost guaranteed to exceed the bounds of included[].

Some general points of advice. Make your function and variable names meaningful. Avoid making a premature exit from a function wherever possible. Avoid while(1) wherever possible. And never make assumptions about array sizes (including C "strings"). It might seem hard work putting in the overhead, but there is a payoff. The payoff is not just about catching unexpected errors, it makes you think about the code you are writing as you do it.

Segmentation fault (core dumped) error, in a C search function

2 Answers