rbp.c

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

#include <tbx/types.h>

#include <rbp.h>

bool
rbp_node_init(rbp_node_t* node, unsigned int x, unsigned int y, unsigned width, unsigned int height)
{
    assert(node);

    node->x      = x;
    node->y      = y;
    node->width  = width;
    node->height = height;
    node->right  = NULL;
    node->left   = NULL;

    return true;
}

void
rbp_node_deinit(rbp_node_t* node)
{
    assert(node);

    if (node->right) {
        rbp_node_deinit(node->right);
        free(node->right);
    }

    if (node->left) {
        rbp_node_deinit(node->left);
        free(node->left);
    }

    memset(node, 0, sizeof(rbp_node_t));
}

void
rbp_node_delete(rbp_node_t* node)
{
    if (!node) {
        return;
    }

    rbp_node_deinit(node);
    free(node);
}

rbp_node_t*
rbp_node_create(unsigned int x, unsigned int y, unsigned width, unsigned int height)
{
    rbp_node_t* node = calloc(1, sizeof(rbp_node_t));
    if (!node) {
        return NULL;
    }

    if (!rbp_node_init(node, x, y, width, height)) {
        free(node);
        return NULL;
    }

    return node;
}

bool
rbp_init(rbp_t* packer, unsigned int width, unsigned int height)
{
    assert(packer);

    rbp_node_t* root = calloc(1, sizeof(rbp_node_t));
    if (!root) {
        return false;
    }

    root->left = NULL;
    root->right = NULL;
    root->width = width;
    root->height = height;

    packer->root = NULL;
    packer->padding = 2;
    packer->width = width;
    packer->height = height;
    packer->root = root;

    return true;
}

void
rbp_deinit(rbp_t* packer)
{
    assert(packer);

    if (packer->root) {
        rbp_node_delete(packer->root);
    }

    memset(packer, 0, sizeof(rbp_t));
}

rbp_t*
rbp_create(unsigned int width, unsigned int height)
{
    rbp_t* packer = calloc(1, sizeof(rbp_t));
    if (!packer) {
        return NULL;
    }

    if (!rbp_init(packer, width, height)) {
        free(packer);
        return NULL;
    }

    return packer;
}

void
rbp_delete(rbp_t* packer)
{
    if (!packer) {
        return;
    }

    rbp_deinit(packer);
    free(packer);
}

rbp_node_t*
rbp_node_insert(rbp_node_t* node, unsigned int width, unsigned int height)
{
    assert(node);

    // If not on a leaf node, insert into left then right
    if (node->left || node->right) {
        if (node->left) {
            struct rbp_node* new_node = rbp_node_insert(node->left, width, height);
            if (new_node) {
                return new_node;
            }
        }

        if (node->right) {
            struct rbp_node* new_node = rbp_node_insert(node->right, width, height);
            if (new_node) {
                return new_node;
            }
        }

        return NULL;
    }

    // If the new node will not fit
    if (width > node->width || height > node->height) {
        return NULL;
    }

    rbp_node_t* left = calloc(1, sizeof(rbp_node_t));
    if (!left) {
        // out of memory
        return NULL;
    }

    rbp_node_t* right = calloc(1, sizeof(rbp_node_t));
    if (!right) {
        // out of memory
        free(left);
        return NULL;
    }

    node->left  = left;
    node->right = right;

    unsigned int w = node->width - width;
    unsigned int h = node->height - height;

    if (w <= h) {
        left->x = node->x + width;
        left->y = node->y;
        left->width = w;
        left->height = height;

        right->x      = node->x;
        right->y      = node->y + height;
        right->width  = node->width;
        right->height = h;
    } else {
        // split the remaining in the vertical direction
        left->x       = node->x;
        left->y       = node->y + height;
        left->width   = width;
        left->height  = h;
        right->x      = node->x + width;
        right->y      = node->y;
        right->width  = w;
        right->height = node->height;
    }

    node->width  = width;
    node->height = height;

    return node;
}

rbp_node_t*
rbp_insert(rbp_t* packer, unsigned int width, unsigned int height)
{
    assert(packer);

    return rbp_node_insert(packer->root, width, height);
}

unsigned int
rbp_get_width(rbp_t* packer)
{
    return packer->width;
}

unsigned int
rbp_get_height(rbp_t* packer)
{
    return packer->height;
}

static void
rbp_traverse_nodes(rbp_node_t* node, vec_void_t* list)
{
    assert(node);
    assert(list);

    vec_void_push(list, node);

    if (node->left) {
        rbp_traverse_nodes(node->left, list);
    }

    if (node->right) {
        rbp_traverse_nodes(node->right, list);
    }
}

vec_void_t*
rbp_get_nodes(rbp_t* packer)
{
    assert(packer);
    assert(packer->root);

    vec_void_t* nodes = vec_void_create(32);
    if (!nodes) {
        return NULL;
    }

    rbp_traverse_nodes(packer->root, nodes);

    return nodes;
}

rbp.h

#pragma once

#include <tbx/types.h>
#include <vec/void.h>

typedef struct rbp_node
{
    struct rbp_node* right;
    struct rbp_node* left;

    unsigned int x;
    unsigned int y;
    unsigned int width;
    unsigned int height;
} rbp_node_t;

typedef struct rbp
{
    struct rbp_node* root;
    unsigned int width;
    unsigned int height;
    unsigned int padding;
} rbp_t;

bool rbp_init(rbp_t* packer, unsigned int width, unsigned int height);

void rbp_deinit(rbp_t* packer);

rbp_t* rbp_create(unsigned int width, unsigned int height);

void rbp_delete(rbp_t* packer);

rbp_node_t* rbp_insert(rbp_t* packer, unsigned int width, unsigned int height);

vec_void_t* rbp_get_nodes(rbp_t* packer);

unsigned int rbp_get_width(rbp_t* packer);

unsigned int rbp_get_height(rbp_t* packer);

rbp_test.c

#include <stdlib.h>

#include <tbx/mutest.h>
#include <img/pixbuf.h>
#include <img/png.h>
#include <vec/void.h>

#include <rbp.h>

typedef struct test_block
{
    unsigned int w;
    unsigned int h;
    unsigned int num;
} test_block_t;

// clang-format off
static test_block_t simple[3] = {
    { .w = 180, .h = 180, .num = 80 },
    { .w = 35,  .h = 200, .num = 40 },
    { .w = 150, .h = 50,  .num = 80 }
};

static test_block_t square[1] = {
    { .w = 50, .h = 50, .num = 100 }
};

static test_block_t power2[8] = {
    { .w =   2, .h =   2, .num = 256 },
    { .w =   4, .h =   4, .num = 128 },
    { .w =   8, .h =   8, .num =  64 },
    { .w =  16, .h =  16, .num =  32 },
    { .w =  32, .h =  32, .num =  16 },
    { .w =  64, .h =  64, .num =   8 },
    { .w = 128, .h = 128, .num =   4 },
    { .w = 256, .h = 256, .num =   2 }
};

static test_block_t tall[5] = {
    { .w = 50,  .h = 400, .num =  2 },
    { .w = 50,  .h = 300, .num =  5 },
    { .w = 50,  .h = 200, .num = 10 },
    { .w = 50,  .h = 100, .num = 20 },
    { .w = 50,  .h =  50, .num = 40 }
};

static test_block_t wide[5] = {
    { .w = 400, .h =  50, .num =  2 },
    { .w = 300, .h =  50, .num =  5 },
    { .w = 200, .h =  50, .num = 10 },
    { .w = 100, .h =  50, .num = 20 },
    { .w =  50, .h =  50, .num = 40 }
};

// alternate tall then wide
static test_block_t tallwide[6] = {
    { .w = 400, .h = 100, .num = 1 },
    { .w = 100, .h = 400, .num = 1 },
    { .w = 400, .h = 100, .num = 1 },
    { .w = 100, .h = 400, .num = 1 },
    { .w = 400, .h = 100, .num = 1 },
    { .w = 100, .h = 400, .num = 1 }
};
/* both odd and even sizes leaves little areas of whitespace */
static test_block_t oddeven[6] = {
    { .w =  50, .h =  50, .num = 20 },
    { .w =  47, .h =  31, .num = 20 },
    { .w =  23, .h =  17, .num = 20 },
    { .w = 109, .h =  42, .num = 20 },
    { .w =  42, .h = 109, .num = 20 },
    { .w =  17, .h =  33, .num = 20 },
};

static test_block_t complex[11] = {
    {.w = 100, .h = 100, .num =   3},
    {.w =  60, .h =  60, .num =   3},
    {.w =  50, .h =  20, .num =  20},
    {.w =  20, .h =  50, .num =  20},
    {.w = 250, .h = 250, .num =   1},
    {.w = 250, .h = 100, .num =   1},
    {.w = 100, .h = 250, .num =   1},
    {.w = 400, .h =  80, .num =   1},
    {.w = 80,  .h = 400, .num =   1},
    {.w =  10, .h =  10, .num = 100},
    {.w =   5, .h =   5, .num = 500}
};
// clang-format on

typedef struct test_img
{
    unsigned int id;
    unsigned int width;
    unsigned int height;
    rbp_node_t* node;
} test_img_t;

img_color_t
generate_fill(void)
{
    img_color_t fill = {};

    fill.r = rand() % 255;
    fill.g = rand() % 255;
    fill.b = rand() % 255;
    fill.a = 255;

    return fill;
}

static int
comp_images(const void* a, const void* b)
{
    const test_img_t* left = (test_img_t*)a;
    const test_img_t* right = (test_img_t*)b;

    int left_height = left->height;
    int left_width = left->width;
    int left_area  = left_width * left_height;

    int right_height = right->height;
    int right_width = right->width;
    int right_area = right_width * right_height;

    if (left_area < right_area) {
        return -1;
    }

    if (left_area > right_area) {
        return 1;
    }

    if (left_width + left_height < right_width + right_height) {
        return -1;
    }

    if (left_width + left_height > right_width + right_height) {
        return 1;
    }

    return 0;
}

void test_block_insertion(const char* name, test_block_t* blocks, size_t length)
{
    fprintf(stdout, "testing %s\n", name);
    rbp_t* rbp = rbp_create(2048, 2048);

    vec_void_t* test_imgs = vec_void_create(128);

    unsigned int id = 0;

    for(size_t i = 0; i < length; i++) {
        test_block_t* block = &blocks[i];
        for(size_t n = 0; n < block->num; n++) {
            test_img_t* img = calloc(1, sizeof(test_img_t));
            img->width = block->w;
            img->height = block->h;
            img->id = id;
            vec_void_push(test_imgs, img);
            id++;
        }
    }
    fprintf(stdout, "  test images created\n");

    vec_void_qsort(test_imgs, comp_images);

    fprintf(stdout, "  test images sorted\n");

    for(size_t i = 0; i < test_imgs->length; i++) {
        test_img_t* img  = vec_void_get(test_imgs, i);
        rbp_node_t* node = rbp_insert(rbp, img->width, img->height);
        mu_assert(node);

        img->node = node;
    }
    fprintf(stdout, "  images packed\n");

    img_pixbuf_t* buf = img_pixbuf_create(rbp_get_width(rbp), rbp_get_height(rbp));

    fprintf(stdout, "  filling in %zu images...\n", test_imgs->length);
    for(size_t i = 0; i < test_imgs->length; i++) {
        test_img_t* img  = vec_void_get(test_imgs, i);
        rbp_node_t* node = img->node;

        img_color_t fill = generate_fill();

        for(size_t y = 0; y < img->height; y++) {
            for(size_t x = 0; x < img->width; x++) {
                size_t posx = x + node->x;
                size_t posy = y + node->y;

                img_pixbuf_set_pixel(buf, posx, posy, &fill);
            }
        }
    }

    img_png_write(buf, name);

    img_pixbuf_delete(buf);

    // --------
    // clean up
    for(size_t i = 0; i < test_imgs->length; i++) {
        test_img_t* img = vec_void_get(test_imgs, i);
        free(img);
    }

    vec_void_delete(test_imgs);

    rbp_delete(rbp);
}

int
main(void)
{
    test_block_insertion("complex.png", complex, 11);
    test_block_insertion("oddeven.png", oddeven, 6);
    test_block_insertion("tallwide.png", tallwide, 6);
    test_block_insertion("wide.png", wide, 5);
    test_block_insertion("tall.png", tall, 5);
    test_block_insertion("power2.png", power2, 8);
    test_block_insertion("square.png", square, 1);
    test_block_insertion("simple.png", simple, 3);

    return EXIT_SUCCESS;
}