#include <stdio.h>
#include <assert.h>
#include <sys/mman.h>
#include <mach/vm_statistics.h>
#include <string.h>

struct block_meta {
  size_t size;
  struct block_meta* next;
  int free;
};
#define META_SIZE sizeof(struct block_meta)

void* base = NULL;

struct block_meta* request_space(struct block_meta* last, size_t size) {
  struct block_meta *block;
  block = mmap(0, size + META_SIZE, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, VM_MAKE_TAG(VM_MEMORY_MALLOC), 0);

  if (block == (void*) -1) return NULL;

  if (last) last->next = block;

  block->size = size;
  block->next = NULL;
  block->free = 0;
  return block;
}

struct block_meta* find_free_block(struct block_meta** last, size_t size) {
  struct block_meta* cur = base;
  while (cur && !(cur->free && cur->size >= size)) {
    *last = cur;
    cur = cur->next;
  }
  return cur;
}

void* malloc(size_t size) {
  struct block_meta* b;

  if (size <= 0) return NULL;

  if (!base) {
    b = request_space(0, size);

    if (!b) return NULL;

    base = b;
  } else {
    struct block_meta* l = base;
    b = find_free_block(&l, size);
    if (!b) {
      b = request_space(l, size);
      if (!b) return NULL;
    } else {
      b->free = 0;
    }
  }
  return b+1;
}

void free(void* ptr) {
  if (!ptr) return;

  struct block_meta* b = (struct block_meta*)ptr - 1;
  assert(b->free == 0);
  b->free = 1;
}

void* realloc(void* ptr, size_t size) {
  if (!ptr) return malloc(size);

  struct block_meta* b = (struct block_meta*)ptr - 1;
  if (b->size >= size) return ptr;

  void* new;
  new = malloc(size);
  if (!new) return NULL;

  memcpy(new, ptr, b->size);
  free(ptr);
  return new;
}

void* calloc(size_t n, size_t nsize) {
  size_t size = n * nsize;
  void *ptr = malloc(size);
  if (!ptr) return NULL;

  memset(ptr, 0, size);
  return ptr;
}

int main() {
  char* a;
  char* b;
  char* c;
  char* d;

  a = malloc(4);
  b = malloc(4);
  c = malloc(4);

  a = strcpy(a, "foo");

  printf("%p\n", (void*)a);
  printf("%p\n", (void*)b);
  printf("%p\n", (void*)c);
  printf("%s\n", a);

  free(b);

  d = malloc(4);
  printf("%p\n", (void*)d);

  free(a);
  free(c);
  free(d);
}