#include <stdint.h>
#include <stdlib.h>

struct Chunk {
  struct Chunk *prev;
  struct Chunk *next;
  int used;
  size_t size;
};

void
Chunk_ctor(struct Chunk *self, size_t size)
{
  self->prev = NULL;
  self->next = NULL;
  self->used = 0;
  self->size = size - sizeof(struct Chunk);
}

static struct Chunk *begin = NULL;

void
alloc_init(void *mem, size_t size)
{
  if (size < sizeof(struct Chunk)) return;

  begin = (struct Chunk *)mem;
  Chunk_ctor(begin, size);
}

void *
malloc(size_t size)
{
  if (begin == NULL) return NULL;

  // find free chunk that is at least (size + sizeof(struct Chunk))
  for (struct Chunk *iter = begin; iter != NULL; iter = iter->next) {
    if (iter->used != 0 || iter->size < size) continue;

    // if there's at least sizeof(struct Chunk) bytes left over, create a new Chunk
    if (iter->size >= (size + 2 * sizeof(struct Chunk))) {
      struct Chunk *next = (struct Chunk *)((uintptr_t)iter + sizeof(struct Chunk) + size);
      Chunk_ctor(next, iter->size - size - sizeof(struct Chunk));
      next->prev = iter;

      iter->size = size;
      iter->next = next;
    }

    iter->used = 1;
    return (void *)((uintptr_t)iter + sizeof(struct Chunk));
  }

  return NULL;
}

void
free(void *ptr)
{
  if (ptr == NULL) return;
  struct Chunk *chunk = (struct Chunk *)((uintptr_t)ptr - sizeof(struct Chunk));
  chunk->used = 0;

  // merge next chunk
  if (chunk->next != NULL && chunk->next->used == 0) {
    chunk->size += chunk->next->size + sizeof(struct Chunk);
    chunk->next = chunk->next->next;
    if (chunk->next != NULL) chunk->next->prev = chunk;
  }

  // merge into prev chunk
  if (chunk->prev != NULL && chunk->prev->used == 0) {
    chunk->prev->size += chunk->size + sizeof(struct Chunk);
    chunk->prev->next = chunk->next;
    if (chunk->next != NULL) chunk->next->prev = chunk->prev;
  }
}