#ifndef _GNU_SOURCE
# define _GNU_SOURCE
#endif
#include <SDL.h>
#include <dlfcn.h>

static void *(*old_malloc)(size_t);
static void (*old_free)(void *);

typedef struct mem_chain {
    Uint8 *ptr;
    int size;
    struct mem_chain *next;
} mem_chain;
static mem_chain *head = NULL;

static Uint8 *surf_ptr = NULL;
static Uint8 *surf_end;

__attribute__((constructor)) static void init_videomalloc() {
    old_malloc = (void *(*)(size_t))dlsym(RTLD_NEXT, "malloc");
    old_free = (void (*)(void *))dlsym(RTLD_NEXT, "free");
}

void *malloc(size_t size) {
    mem_chain *cur = head, *prev = NULL;
    void *last_addr = NULL;

    if (size > 15) return old_malloc(size);

    if (!surf_ptr) {
        SDL_Surface *surf = SDL_GetVideoSurface();
        if (surf) {
            surf_ptr = (Uint8 *)surf->pixels;
            surf_end = surf_ptr
                + surf->pitch * surf->h * surf->format->BytesPerPixel;
        }
        else {
            return old_malloc(size);
        }
    }

    while (cur) {
        int s = -cur->size;
        if (cur->size < 0 && s >= (int)size) {
            if (s == (int)size) {
                cur->size = s;
                printf("FIT %p\n", cur->ptr);
                return cur->ptr;
            }
            else {
                cur = (mem_chain *)old_malloc(sizeof(mem_chain));
                cur->ptr = prev->ptr + size;
                cur->size = s-size;
                cur->next = prev->next;
                prev->size = size;
                prev->next = cur;
                printf("SPLIT %p\n", cur->ptr);
                return prev->ptr;
            }
        }

        last_addr = cur->ptr + cur->size;
        prev = cur;
        cur = cur->next;
    }

    if (prev && prev->ptr+prev->size+size >= surf_end) {
        printf("OVER\n");
        return malloc(size);
    }

    cur = (mem_chain *)old_malloc(sizeof(mem_chain));
    cur->size = size;
    cur->next = NULL;

    if (!last_addr) {
        head = cur;
        cur->ptr = surf_ptr;
        printf("INIT %p\n", cur->ptr);
    }
    else {
        prev->next = cur;
        cur->ptr = last_addr;
        printf("TAIL %p\n", cur->ptr);
    }
    return cur->ptr;
}

void free(void *ptr) {
    mem_chain *cur = head, *prev;
    while (cur) {
        if (cur->ptr == ptr) {
            cur->size = -cur->size;
            if (prev->size < 0) {
                prev->size += cur->size;
                prev->next = cur->next;
                old_free(cur);
                cur = prev;
            }
            prev = cur;
            cur = cur->next;
            if (cur && cur->size < 0) {
                prev->size += cur->size;
                prev->next = cur->next;
                old_free(cur);
            }
            return;
        }
        prev = cur;
        cur = cur->next;
    }
    old_free(ptr);
}