#include "alloc.h"
#include <unistd.h>

typedef struct alloc {
    int used, size;
    struct alloc *prev, *next;
} alloc_t;

alloc_t start = { 1, 0, NULL, NULL };

#define SZMIN 0x40

#define USABLE(al, sz) \
    (!((alloc_t *)(al))->used && ((alloc_t *)(al))->size >= (sz))

void *alloc(int size)
{
    size += -size % sizeof(long);

    alloc_t *palloc = &start;

    while (palloc->next && !USABLE(palloc, size)) {
        palloc = palloc->next;
    }
    if (USABLE(palloc, size) &&
        palloc->size - size - sizeof(alloc_t) >= SZMIN) {
        alloc_t *next = (char *)(palloc+1) + size;
        next->used = 0;
        next->size = palloc->size - size - sizeof(alloc_t);
        next->prev = palloc;
        next->next = palloc->next;
        palloc->next = next;
    } else {
        palloc->next = sbrk(sizeof(alloc_t) + size);
        palloc->next->prev = palloc;
        palloc = palloc->next;
        palloc->next = NULL;
    }
    palloc->used = 1;
    palloc->size = size;

    return palloc + 1;
}

void dealloc(void *_palloc)
{
    alloc_t *palloc = (alloc_t *)_palloc - 1;

    if (palloc->next) {
        palloc->used = 0;
        if (!palloc->next->used) {
            palloc->size += sizeof(alloc_t) + palloc->next->size;
            palloc->next = palloc->next->next;
        }
        if (!palloc->prev->used) {
            palloc->prev->size += sizeof(alloc_t) + palloc->size;
            palloc->prev->next = palloc->next;
        }
    } else {
        palloc->prev->next = NULL;
        brk(palloc);
    }
}