Simple std::priority_queue-like container implemented in C99, without error handling and thread-safety

c99-heap.c

/*
 * c99-heap.c
 * - Description: Simple std::priority_queue-like container implemented in C99, without error handling and thread-safety
 * - Author: Shao-Chung Chen
 * - License: CC0
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct _c_heap {
    size_t capacity;
    size_t length;
    size_t element_size;
    int(*comp_func_p)(void*, void*);
    void *btree_p;
} c_heap;

static void
c_heap__resize(c_heap *c_heap_p, size_t new_capacity) {
    if (!c_heap_p || new_capacity < c_heap_p->length) return;
    c_heap_p->capacity = new_capacity;
    c_heap_p->btree_p = realloc(c_heap_p->btree_p, c_heap_p->capacity * c_heap_p->element_size);
}

static void
c_heap__swap_element(c_heap *c_heap_p, void *a_p, void *b_p) {
    if (!c_heap_p) return;
    unsigned char tmp[c_heap_p->element_size];
    memcpy(tmp, a_p, c_heap_p->element_size);
    memcpy(a_p, b_p, c_heap_p->element_size);
    memcpy(b_p, tmp, c_heap_p->element_size);
}

static void*
c_heap__at(c_heap *c_heap_p, size_t index) {
    if (!c_heap_p || index >= c_heap_p->length) return NULL;
    return (void*)((char*)c_heap_p->btree_p + (index * c_heap_p->element_size));
}

c_heap*
c_heap_init(c_heap *c_heap_p, size_t element_size, int(*comp_func_p)(void*,void*)) {
    if (!c_heap_p) return NULL;
    c_heap_p->capacity = 16;
    c_heap_p->length = 0;
    c_heap_p->element_size = element_size;
    c_heap_p->comp_func_p = comp_func_p;
    c_heap_p->btree_p = malloc(c_heap_p->capacity * element_size);
    return c_heap_p;
}

void
c_heap_destroy(c_heap *c_heap_p) {
    if (!c_heap_p) return;
    free(c_heap_p->btree_p);
    c_heap_p->capacity = 0;
    c_heap_p->length = 0;
    c_heap_p->element_size = 0;
    c_heap_p->btree_p = NULL;
}

size_t
c_heap_size(c_heap *c_heap_p) {
    if (!c_heap_p) return 0;
    return c_heap_p->length; 
}

bool
c_heap_empty(c_heap *c_heap_p) {
    return c_heap_size(c_heap_p) == 0;
}

void const*
c_heap_top(c_heap *c_heap_p) {
    if (!c_heap_p) return NULL;
    return c_heap_p->btree_p;
}

void*
c_heap_push(c_heap *c_heap_p, void *value_p) {
    if (!c_heap_p || !value_p) return NULL;
    if (c_heap_p->length+1 > c_heap_p->capacity) {
        /* out of capacity, re-allocate with buffer size doubled */
        c_heap__resize(c_heap_p, c_heap_p->capacity * 2);
    }
    ++c_heap_p->length;

    // insert to the bottom-right leaf
    size_t dest_index = c_heap_p->length - 1;
    void *dest_p = c_heap__at(c_heap_p, dest_index);
    memcpy(dest_p, value_p, c_heap_p->element_size);

    // perform bottom-up fix if necessary
    size_t current_index = dest_index,
                 parent_index = (current_index-1) / 2;
    while (current_index > 0) {
        void *current_p = c_heap__at(c_heap_p, current_index),
                 *parent_p = c_heap__at(c_heap_p, parent_index);
        if (c_heap_p->comp_func_p(parent_p, current_p) < 0) {
            // parent < current, swap(parent, current);
            c_heap__swap_element(c_heap_p, parent_p, current_p);
        }
        else {
            break;
        }
        current_index = parent_index;
        parent_index = (current_index-1) / 2;
    }

    return dest_p;
}

void
c_heap_pop(c_heap *c_heap_p) {
    if (!c_heap_p || !c_heap_p->length) return;

    if (c_heap_p->length == 1) {
        --c_heap_p->length;
        return;
    }

    // put last element to root, and decrease length
    void *last_p = c_heap__at(c_heap_p, c_heap_p->length-1);
    memcpy(c_heap_p->btree_p, last_p, c_heap_p->element_size);
    --c_heap_p->length;

    // perform top-down fix if necessary
    size_t current_index = 0;
    size_t child_index = (current_index * 2) + 1;
    while (child_index < c_heap_p->length) {
        void *child_p = c_heap__at(c_heap_p, child_index);
        // try to use the largest child among two children
        if (child_index+1 < c_heap_p->length) {
            void *left_child_p = child_p,
                     *right_child_p = c_heap__at(c_heap_p, child_index+1);
            if (c_heap_p->comp_func_p(left_child_p, right_child_p) < 0) {
                child_index = child_index + 1;
                child_p = right_child_p;
            }
        }
        void *current_p = c_heap__at(c_heap_p, current_index);
        if (c_heap_p->comp_func_p(current_p, child_p) < 0) {
            // current < child, swap(current, child)
            c_heap__swap_element(c_heap_p, current_p, child_p);
        }
        else {
            break;
        }
        current_index = child_index;
        child_index = (current_index * 2) + 1;
    }
}

////////////////////////////////////////////////////////////////////////////////

int compare_int (void *a, void *b) {
    int ai = *((int*)a), bi = *((int*)b);
    if (ai < bi) return -1;
    else if (ai > bi) return 1;
    else return 0; 
}

static void c_heap_push_int(c_heap *c_heap_p, int value) {
    c_heap_push(c_heap_p, &value);
    printf("heap.push(%d)\n", value);
}

static void c_heap_pop_int(c_heap *c_heap_p) {
    int top = *((int*)c_heap_top(c_heap_p));
    printf("heap.pop() = %d\n", top);
    c_heap_pop(c_heap_p);
}

int main() {
    c_heap h;
    c_heap_init(&h, sizeof(int), compare_int);

    for (int i = 0; i < 10; i++) {
        c_heap_push_int(&h, i);
    }

    c_heap_push_int(&h, 1);
    c_heap_push_int(&h, 5);
    c_heap_push_int(&h, 2);
    c_heap_push_int(&h, 4);
    c_heap_push_int(&h, 3);
    c_heap_push_int(&h, 6);
    c_heap_push_int(&h, 7);
    c_heap_push_int(&h, 8);
    c_heap_push_int(&h, 9);
    c_heap_push_int(&h, 0);
    c_heap_push_int(&h, 100);

    for (int i = 0; i < 21; i++) {
        c_heap_pop_int(&h);
    }
    
    c_heap_destroy(&h);
    return 0;
}