1

I am trying to write a generic quicksort:

void _qsort(void *ptr, 
        size_t lrange, 
        size_t rrange,
        size_t size,
        int (*cmp)(const void *, const void *))
{
    if (lrange < rrange) {
        size_t i, j;
        void *key;

        key = malloc(size);
        i = lrange;
        j = rrange;
        memcpy(key, ptr + i * size, size);
        while (i < j) {
            while (i < j && (*cmp)(ptr + j * size, key) > 0)
                j--;
            if (i < j) {
                memcpy(ptr + i * size, ptr + j * size, size);
                i++;
            }
            while (i < j && (*cmp)(key, ptr + i * size) > 0)
                i++;
            if (i < j) {
                memcpy(ptr + j * size, ptr + i * size, size);
                j--;
            }
        }
        memcpy(ptr + i * size, key, size);
        _qsort(ptr, lrange, i - 1, size, cmp);
        _qsort(ptr, i + 1, rrange, size, cmp);
    }
}

I write a simple test on a int array, this is the cmp funciton:

int cmp(const void *x, const void *y)
{
    return *(int *)x - *(int *)y;
}

It cause a core dump, but when I change the type of lrange, rrange, i, j from size_t to int, it run right, I can't understand, why?

protream
  • 29
  • 1
  • 4
  • 1
    Look at [this question](http://stackoverflow.com/questions/2550774/what-is-size-t-in-c) to better understand what is `size_t` and why it causes a crash. HINT: it's probably due to memcpy operating with it. but you're close. – Shark Mar 30 '16 at 13:50
  • Why don't you debug the core dump? – kamikaze Mar 30 '16 at 13:51
  • There is a problem when i debug this core dump, "malloc.c: No such file or directory." – protream Mar 30 '16 at 13:59
  • @protream What compiler, what debugger? Did you include `` where malloc is located? – Lundin Mar 30 '16 at 14:00
  • gdb. Seems same to this: http://stackoverflow.com/questions/9220853/call-to-malloc-failing-in-gdb-session – protream Mar 30 '16 at 14:07

2 Answers2

3
memcpy(key, ptr + i * size, size);

ptr is a void *, you can't use pointer arithmetic with void *, switch to char * (as qsort in the standard library).

David Ranieri
  • 39,972
  • 7
  • 52
  • 94
  • 2
    Nicely spotted. To avoid goof-up like this, use a standard compliant compiler. For example `gcc -std=c11 -pedantic-errors // gives excellent C compiler` rather than `gcc // gives non-standard crapiler` – Lundin Mar 30 '16 at 13:55
3
size_t i, j;

are unsigned types. If a value of an unsigned variable is 0, and 1 is subtracted, the value will wrap-around to the largest possible value for that unsigned type.

This can happen on lines:

j--;

and:

_qsort(ptr, lrange, i - 1, size, cmp);

When that invalid value used as an index for an array, it will cause a seg-fault as the program cannot read an address that is out-of-bounds.

Do not use names with the prefix _, _qsort, as those are reserved for the implementation.

2501
  • 25,460
  • 4
  • 47
  • 87