3
\$\begingroup\$

I have taken a look at these review questions: one, two, three and four and would still like to ask you to review my implementation of mergesort that follows the man 3 qsort prototype.

void *malloc_or_exit(size_t size) {
    void *tmp = malloc(size);

    if (tmp == NULL) {

        if (size == 0) {
            return tmp;
        }

        fprintf(
            stderr, "Failed to malloc %zu bytes: %s",
            size, strerror(errno)
        );

        exit(EXIT_FAILURE);
    }

    return tmp;
}

void mergesort0(
    void *xs, size_t n, size_t s,
    int (*cmp) (const void *, const void *)
) {
    if (n == 0 || n == 1) return;

    const size_t nlft = n / 2;
    const size_t nrgt = n - nlft;

    void *ys = (char *)xs + nlft * s;

    mergesort0(xs, nlft, s, cmp);
    mergesort0(ys, nrgt, s, cmp);

    void *const as = malloc_or_exit(n * s);
    void *const bs = (char *)as + nlft * s;
    void *const cs = (char *)as + n * s;

    memcpy(as, xs, n * s);

    void const *i = as;
    void const *j = bs;
    while (i != bs && j != cs) {
        if (cmp(i, j) <= 0) {
            memcpy(xs, i, s);
            i = (char *)i + s;
        } else {
            memcpy(xs, j, s);
            j = (char *)j + s;
        }

        xs = (char *)xs + s;
    }

    for (; i != bs; i = (char *)i + s, xs = (char *)xs + s) {
        memcpy(xs, i, s);
    }

    for (; j != cs; j = (char *)j + s, xs = (char *)xs + s) {
        memcpy(xs, j, s);
    }

    free(as);
}

#include <stdio.h>
int main() {
    int xs[] = {1, 2, 3, 4, 5};
    int ys[] = {5, 4, 3, 2, 1};
    int zs[] = {3, 1, 2, 4, 5};
    int as[] = {1, 1, 1};
    int bs[] = {3, 2, 2};

    int len = 5;

    qsort(zs, len, sizeof(int), compare_int);

    for (int i = 0; i < len; ++i) {
        printf("%d ", *(zs + i));
    } printf("\n");
}
\$\endgroup\$
5
\$\begingroup\$
  1. Better show your includes too, that makes evaluating your code easier and more meaningful.
    Anyway, it's <stdlib.h>, <stdio.h> and <string.h>.

  2. You know you can combine multiple conditions into a single expression with &&?

  3. You can avoid all those casts if you use char* instead of void* internally.

  4. Why don't you reuse a single allocation instead of doing n*log(n) ones, each local?

  5. You know doing a single combined memcpy is far more efficient than multiple consecutive smaller ones?

  6. If you only move the first nlft elements out of the way, you only need half the extra-space and save on copying.

Your test-program:

  1. Your test-program doesn't seem to exercise your code...

  2. You lost a newline at the end of your test-program.

Modified code:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void* malloc_or_exit(size_t size) {
    void* result = malloc(size);

    if (!result && size) {
        fprintf(
            stderr, "Failed to malloc %zu bytes: %s",
            size, strerror(errno)
        );
        exit(EXIT_FAILURE);
    }

    return result;
}

static void mergesort0_impl(
    char* as, char* xs, size_t n, size_t s,
    int (*cmp) (const void*, const void*)
) {
    if (n < 2) return;

    const size_t nlft = n / 2;
    const size_t nrgt = n - nlft;

    char* ys = xs + nlft * s;

    mergesort0_impl(as, xs, nlft, s, cmp);
    mergesort0_impl(as, ys, nrgt, s, cmp);

    char* const bs = as + nlft * s;

    memcpy(as, xs, nlft * s);

    const char* i = as;
    const char* j = ys;
    for (; i != bs && j != xs; xs += s) {
        if (cmp(i, j) <= 0) {
            memcpy(xs, i, s);
            i += s;
        } else {
            memcpy(xs, j, s);
            j += s;
        }
    }
    if (i != bs)
        memcpy(xs, i, bs - i);
}

void mergesort0(
    void* xs, size_t n, size_t s,
    int (*cmp) (const void*, const void*)
) {
    if(n < 2) return;
    void* as = malloc_or_exit(n / 2 * s);
    mergesort0_impl(as, xs, n, s, cmp);
    free(as);
}


#include <stdio.h>

void test(int nr, const int xs[], size_t n) {
    int* a = malloc_or_exit(2 * n * sizeof *xs);
    int* b = a + n;
    memcpy(a, xs, n * sizeof *xs);
    memcpy(b, xs, n * sizeof *xs);
    qsort(a, n, sizeof *a, compare_int);
    mergesort0(b, n, sizeof *b, compare_int);
    printf("Test %d %s: ", nr, !memcmp(a, b, n * sizeof *xs) ? "OK" : "FAILED");
    for (size_t i = 0; i < n; ++i)
        printf("%d%c", xs[i], " \n"[i == n - 1]);
    free(a);
}

int main() {
    int xs[] = {1, 2, 3, 4, 5};
    int ys[] = {5, 4, 3, 2, 1};
    int zs[] = {3, 1, 2, 4, 5};
    int as[] = {1, 1, 1};
    int bs[] = {3, 2, 2};
    int nr = 0;
    #define TEST(a) test(nr++, a, sizeof a / sizeof *a)
    TEST(xs);
    TEST(ys);
    TEST(zs);
    TEST(as);
    TEST(bs);
    #undef TEST
}
\$\endgroup\$
1
\$\begingroup\$

The error handling is a bit harsh, but it's hard to see what you could do differently, given the signature of qsort().

If you were to implement qsort_s() (in C11), you would be able to return a reasonable error code instead of exiting. It's then reasonable to implement qsort() in terms of qsort_s() (and have (only) qsort() print to stderr and call exit() on failure).

In any case, it's polite to end your error message with a newline:

fprintf(stderr, "Failed to malloc %zu bytes: %s\n",
        size, strerror(errno));
\$\endgroup\$
  • 1
    \$\begingroup\$ You know that qsort_s is part of the optional Annex K, and has the same problems as all the other functions part of it? Unsurprisingly, those critical problems lead to a low rate of implementation and usage. \$\endgroup\$ – Deduplicator May 22 '17 at 20:42
  • 1
    \$\begingroup\$ I didn't spot that it's in Annex K; in this case, there's not a problem, because we are implementing the function, rather than relying on the library to provide it for us. So we get to be generous to our users, giving them the choice of qsort_s() or qsort() as they wish. \$\endgroup\$ – Toby Speight May 23 '17 at 8:00
  • \$\begingroup\$ Well, the main-problem with Annex K is the error-response depending on global state... \$\endgroup\$ – Deduplicator May 23 '17 at 16:35
  • \$\begingroup\$ That's a good point; can you turn it into a good suggestion for improving the error handling? I'm not happy when functions I use might call exit(), when I could take some other action without exiting. \$\endgroup\$ – Toby Speight May 23 '17 at 16:40
  • \$\begingroup\$ Simply don't make it qsort_s() but qsort_try(), without any dependency on some volatile global error-handler. \$\endgroup\$ – Deduplicator May 23 '17 at 17:01

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.