5
\$\begingroup\$

I'd like to know if there's any issues with this implementation of qsort_r (which is not available in all implementations, so I'm trying to provide one that allows to compare values in a dynamic environment) and whether it could be improved upon.

typedef int32_t compare_fn(void *data, const void *val1, const void *val2);

void memswap(void *mem1, void *mem2, size_t size)
{
    uint8_t buffer[size];

    memcpy(buffer, mem1, size);
    memcpy(mem1, mem2, size);
    memcpy(mem2, buffer, size);
}

void qsort_r(void *mem_low, void *mem_hi, size_t size, compare_fn compare, void *data)
{
    if (mem_low >= mem_hi || mem_hi < mem_low)
    {
        return;
    }

    uint8_t *mem_i = mem_low;
    uint8_t *mem_j = mem_low;

    while (mem_j < mem_hi)
    {
        if (compare(data, mem_j, mem_hi) < 0)
        {
            memswap(mem_i, mem_j, size);
            mem_i += size;
        }

        mem_j += size;
    }

    memswap(mem_i, mem_hi, size);

    qsort_r(mem_low, mem_i - size, size, compare, data);
    qsort_r(mem_i + size, mem_hi, size, compare, data);
}
\$\endgroup\$
6
\$\begingroup\$
  1. Pointer-arithmetic on void* is an error in standard c. Yes, gcc/clang have an extension assuming that sizeof(void) == 1. Ramp up your warning-level and specify the standard.

  2. That's an interesting method to swap two blocks of memory.

    Using a variable length array invites undefined behavior though, as the amount of stack requested is pretty much unbounded.

    Anyway, it would probably be a good idea to implement it directly, without such a buffer.

    void memswap(void* a, void* b, size_t n) {
        unsigned char *c = a, *d = b;
        while (n--) {
            unsigned char x = *c;
            *c++ = *d;
            *d++ = x;
        }
    }
    
  3. I somewhat expected all the elements to be between mem_low and mem_hi. You seem to have an element at mem_hi.
    At least if you sort a null terminated string, it just sorts the terminator too.

Did you try to run your code? See it break a basic test-case live on coliru.

\$\endgroup\$
  • \$\begingroup\$ I had tried it on an integer array of 10k elements, but it hid a nasty bug. My pivot cannot be mem_hi, it must be mem_hi - size. This change will solve (1). As for (2), it is very interesting, would there be a performance difference? I'll update the code with the changes. \$\endgroup\$ – sturcotte06 Aug 23 at 23:25
5
\$\begingroup\$

if (mem_low >= mem_hi || mem_hi < mem_low)

The second part of that if is completely redundant.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.