C: Heap-sort (percolate) error: abort, where is the error? / How to get more details about the error?

Question

i tried to implement a simple heap sort algorithm, but it always terminates with the message [1] 25535 abort ./build/maps. I ran lldb ./build/maps core to inspect the error, this is what I got:

stop reason = signal SIGABRT
    frame #0: 0x00000001b65219b8 libsystem_kernel.dylib`__pthread_kill + 8
libsystem_kernel.dylib`__pthread_kill:
->  0x1b65219b8 <+8>:  b.lo   0x1b65219d8               ; <+40>
    0x1b65219bc <+12>: pacibsp
    0x1b65219c0 <+16>: stp    x29, x30, [sp, #-0x10]!
    0x1b65219c4 <+20>: mov    x29, sp
Target 0: (maps) stopped.

i don't know what to do with this. I suspect, that there is somewhere a overflow, because if I call the function with the length of the array - 1 it works. If i run lldb step by step I can't find the error, it just works til the end, what really confuses me However here is my Code:

#include <stdio.h>
#include <stdlib.h>
#include "./collections/heap.h"

int compare(const void *element_1, const void *element_2) {
    const int *a = element_1;
    const int *b = element_2;
    return *a - *b;
}

int main(int argc, char **argv) {
    int array[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    heap_sort(array, 9, sizeof(array[0]), compare);
    for(int i = 0; i < 9; i++) {
        printf("%d\n", array[i]);
    }
}

#include "heap.h"
#include "../assert.h"
#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

static void percolate(void *, int, size_t, size_t, int (*compare)(const void *, const void *));
static void swap(void * , int, int, size_t);


void heap_sort(void *array, size_t n_elements, size_t size_per_element, int (*compare)(const void *, const void *)) {
    int len = n_elements * size_per_element; // array has `len` bytes.
    unsigned char *src = array;
    for(int i = len/2; i >= 0; i -= size_per_element) {
        percolate(array, i, len - size_per_element, size_per_element, compare);
    }
    printf("successfully ran first for loop\n");
    for(int i = len; i > 0; i -= size_per_element) {
        swap(array, 0, i, size_per_element);
        percolate(array, 0, i - size_per_element, size_per_element, compare);
    }
    printf("successfully ran second for loop\n");
}

/**
 * Swaps the variables at index i and index j.
 */
static void swap(void *array, int i, int j, size_t element_size) {
    unsigned char *src = array;
    while(element_size-- > 0) {
        src[i] ^= src[j];
        src[j] ^= src[i];
        src[i] ^= src[j];
        ++i;
        ++j;
    }
}

static void percolate(void *array, int current, size_t last, size_t element_size, int (*compare)(const void *, const void *)) {
    unsigned char *src = array;
    int i = current;
    int j;
    while((2*i) + element_size <= last) {
        j = (2*i) + element_size;
        if(j+ element_size <= last) {
            if(compare(&src[j], &src[j+element_size]) > 0) {
                j += element_size;
            }
        }
        if(compare(&src[i], &src[j]) > 0) {
            swap(array, i, j, element_size);
            i = j;
        } else {
            break;
        }
    }
}

Thank you

Answer 1

You are exceeding the bounds of the array. This is UB (undefined behavior).

On your system, this produces a crash. On my system, it just produces bad results.

In addition to gdb/lldb debug, you can add range checks and debug printf

Here's a refactored version (compile with -DDEBUG). It checks all array indexes for being within range. You can add a debugger breakpoint on the _sysfault function to use both debug methods.

Anyway, here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

#ifdef DEBUG
#define dbgprt(_fmt...)     printf(_fmt)
#define CHKI(_idx)          chki(_idx,__LINE__)
#else
#define CHKI(_idx)          do { } while (0)
#define dbgprt(_fmt...)     do { } while (0)
#endif

#define CHKB(_off)          CHKI((_off) / sizeof(bigarray[0]))

#define ARRCNT(_arr) \
    (sizeof(_arr) / sizeof(_arr[0]))

#define RNGEM1(_val,_lo,_hi) \
    (((_val) >= (_lo)) && ((_val) < (_hi)))

int bigarray[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

#define sysfault(_fmt...) \
    do { \
        printf(_fmt); \
        _sysfault(); \
    } while (0)

void
_sysfault(void)
{

    printf("sysfault: aborting ...\n");
    exit(1);
}

void
chki(int idx,int lno)
{

    if (! RNGEM1(idx,0,ARRCNT(bigarray)))
        sysfault("chki: range error line %d -- idx=%d\n",lno,idx);
}

/**
 * Swaps the variables at index i and index j.
 */
static void
swap(void *array, int i, int j, size_t element_size)
{
    unsigned char *src = array;

    dbgprt("swap: ENTER i=%d j=%d element_size=%d\n",i,j,element_size);

    CHKB(i);
    CHKB(j);

    while (element_size-- > 0) {
        src[i] ^= src[j];
        src[j] ^= src[i];
        src[i] ^= src[j];
        ++i;
        ++j;
    }

    dbgprt("swap: EXIT\n");
}

static void
percolate(void *array, int current, size_t last, size_t element_size,
    int (*compare)(const void *,const void *))
{
    unsigned char *src = array;
    int i = current;
    int j;

    dbgprt("percolate: ENTER current=%d last=%zu element_size=%zu\n",
        current,last,element_size);

    while ((2 * i) + element_size <= last) {
        j = (2 * i) + element_size;

        dbgprt("percolate: LOOP i=%d j=%d\n",i,j);
        CHKB(i);
        CHKB(j);

        if (j + element_size <= last) {
            if (compare(&src[j], &src[j + element_size]) > 0) {
                dbgprt("percolate: BEF\n");
                j += element_size;
            }
        }
        if (compare(&src[i], &src[j]) > 0) {
            dbgprt("percolate: AFT\n");
            swap(array, i, j, element_size);
            i = j;
        }
        else {
            dbgprt("percolate: STOP\n");
            break;
        }
    }

    dbgprt("percolate: EXIT\n");
}

void
heap_sort(void *array, size_t n_elements, size_t size_per_element,
    int (*compare)(const void *, const void *))
{
    int len = n_elements * size_per_element;    // array has `len` bytes.
    unsigned char *src = array;
    int i;

    i = len / 2;
    for (; i >= 0; i -= size_per_element)
        percolate(array, i, len - size_per_element, size_per_element, compare);
    printf("successfully ran first for loop\n");

#if 1
    i = len;
#else
    i = len - 1;
#endif
    for (; i > 0; i -= size_per_element) {
        swap(array, 0, i, size_per_element);
        percolate(array, 0, i - size_per_element, size_per_element, compare);
    }
    printf("successfully ran second for loop\n");
}

int
compare(const void *element_1, const void *element_2)
{
    const int *a = element_1;
    const int *b = element_2;

    return *a - *b;
}

int
main(int argc, char **argv)
{

    setlinebuf(stdout);

    heap_sort(bigarray, ARRCNT(bigarray), sizeof(bigarray[0]), compare);

    for (int i = 0; i < ARRCNT(bigarray); i++) {
        printf("%d\n", bigarray[i]);
    }

    return 0;
}

---

Here is the program output:

percolate: ENTER current=18 last=32 element_size=4
percolate: EXIT
percolate: ENTER current=14 last=32 element_size=4
percolate: LOOP i=14 j=32
percolate: AFT
swap: ENTER i=14 j=32 element_size=4
swap: EXIT
percolate: EXIT
percolate: ENTER current=10 last=32 element_size=4
percolate: LOOP i=10 j=24
percolate: AFT
swap: ENTER i=10 j=24 element_size=4
swap: EXIT
percolate: EXIT
percolate: ENTER current=6 last=32 element_size=4
percolate: LOOP i=6 j=16
percolate: AFT
swap: ENTER i=6 j=16 element_size=4
swap: EXIT
percolate: EXIT
percolate: ENTER current=2 last=32 element_size=4
percolate: LOOP i=2 j=8
percolate: STOP
percolate: EXIT
successfully ran first for loop
swap: ENTER i=0 j=36 element_size=4
chki: range error line 59 -- idx=9
sysfault: aborting ...