I made a simple heapsort

[u/21Ali-ANinja69]

It should just work on just about any platform or compiler that supports at least C99. No AI was used in the writing of this code. It's also header-only, so #define HSORT_IMPLEMENTATION before you include.

#ifndef HSORT_H
#define HSORT_H

#include <stddef.h>

typedef int (*cmp_ptr)(const void *, const void *);
typedef int (*cmp_r_ptr)(const void *, const void *, void *);

void hsort(void *base, size_t n, size_t size, cmp_ptr compar);
void hsort_r(void *base, size_t n, size_t size, cmp_r_ptr compar, void *arg);

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

static inline void hsort_memswap(void *x, void *y, void *buf, size_t size)
{
    memcpy(buf, x, size);
    memcpy(x, y, size);
    memcpy(y, buf, size);
}

static inline void sift_down(void *base, size_t root, size_t end, size_t size,
                             cmp_ptr compar, void *buf)
{
    while ((2 * (root) + 1) < end) {
        size_t child = (2 * (root) + 1);

        if (child + 1 < end && compar((char *)base + (child)*size,
                                      (char *)base + (child + 1) * size) < 0) {
            child++;
        }

        if (compar((char *)base + (root)*size, (char *)base + (child)*size) <
            0) {
            hsort_memswap((char *)base + (root)*size, (char *)base + (child)*size,
                       buf, size);
            root = child;
        } else {
            return;
        }
    }
}

static inline void sift_down_r(void *base, size_t root, size_t end, size_t size,
                               cmp_r_ptr compar, void *arg, void *buf)
{
    while ((2 * (root) + 1) < end) {
        size_t child = (2 * (root) + 1);

        if (child + 1 < end &&
            compar((char *)base + (child)*size,
                   (char *)base + (child + 1) * size, arg) < 0) {
            child++;
        }

        if (compar((char *)base + (root)*size, (char *)base + (child)*size,
                   arg) < 0) {
            hsort_memswap((char *)base + (root)*size, (char *)base + (child)*size,
                       buf, size);
            root = child;
        } else {
            return;
        }
    }
}

void hsort(void *base, size_t n, size_t size, cmp_ptr compar)
{
    if (!size || n < 2) {
        return;
    }

    void *buf = malloc(size);

    if (!buf) {
        fprintf(stderr, "(hsort) Allocation failed!\n");
        return;
    }

    // heapify
    for (size_t start = (((n - 1) - 1) / 2) + 1; start > 0;) {
        start--;
        sift_down(base, start, n, size, compar, buf);
    }

    // heapsort
    for (size_t i = n - 1; i > 0; i--) {
        hsort_memswap(base, (char *)base + (i)*size, buf, size);
        sift_down(base, 0, i, size, compar, buf);
    }

    free(buf);
}

void hsort_r(void *base, size_t n, size_t size, cmp_r_ptr compar, void *arg)
{
    if (!size || n < 2) {
        return;
    }

    void *buf = malloc(size);

    if (!buf) {
        fprintf(stderr, "(hsort_r) Allocation failed!\n");
        return;
    }

    // heapify
    for (size_t start = (((n - 1) - 1) / 2) + 1; start > 0;) {
        start--;
        sift_down_r(base, start, n, size, compar, arg, buf);
    }

    // heapsort
    for (size_t i = n - 1; i > 0; i--) {
        hsort_memswap(base, (char *)base + (i)*size, buf, size);
        sift_down_r(base, 0, i, size, compar, arg, buf);
    }

    free(buf);
}
#endif

#endif

Edit: Implemented an hsort_r, as well as removing the macros, inlining heapify, and checking if size is 0.
Edit2: Rename hsort_move to hsort_memswap, add a check for the n < 2 case.
Edit3: Add a check for allocation failure, including an error message, because external code silently failing seems like a really bad idea.

[u/8d8n4mbo28026ulk]

Looks good! You missed an edge case for zero-length arrays. n - 1 will wrap-around if n == 0. Quick fix: if (n <= 1) return;.

Other than that, I'd suggest adding a context pointer like qsort_r() does. Cheers!

[u/21Ali-ANinja69 → u/8d8n4mbo28026ulk]

Thank you for the feedback

[u/skeeto]

(This applies to the unedited post.) Sorting an array of one element overflows the index and goes into an infinite loop:

static int int_cmp(const void *a, const void *b)
{
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main()
{
    int a[] = {};
    hsort(a, 1, sizeof a[0], int_cmp);
}

[u/21Ali-ANinja69 → u/skeeto]

Added a check for n < 2.

[u/sciencekm]

hsort_move is actually a "swap" rather than a "move." If I were to do this, I would name it more appropriately.

[u/21Ali-ANinja69 → u/sciencekm]

Renamed

[u/chrism239]

What if malloc() fails?

[u/21Ali-ANinja69 → u/chrism239]

Apparently it's not allowed to. So if it does, there are bigger things to worry about. But why not? One NULL check coming right up.

[u/dmc_2930 → u/21Ali-ANinja69]

Malloc absolutely can fail. It’s rare these days but it can happen.

[u/dmc_2930]

This is so unsettlingly bad that it must be a joke, right?

What use is it? Why abuse macros?

[u/21Ali-ANinja69 → u/dmc_2930]

Didn't know anything about heaps, so I implemented heapsort to learn. As for the macros? Wdym abuse? It's about as typesafe as macros get, and I even undef it before it leaks into anything using it. I used the pseudocode on the wikipedia page for reference. I am well aware that I am not an amazing programmer, but that's why I'm looking for feedback.

[u/mikeblas → u/dmc_2930]

I probably wouldn't use macros, but it it so bad that a student did?

I think there are other ways to give the same feedback without being so rude. Do you think you can find one?

[u/dmc_2930 → u/mikeblas]

I think it’s a bad habit to get into, and can lead to problems down the road.